The Mastic VDAF

3.1. Key Generation

The VIDPF-key generation algorithm run by each Client is listed below. The specification invokes auxiliary functions, namely extend(), convert(), and node_proof(), which are defined in Section 3.3. Its inputs are the input string alpha, the encoded weight beta, the application context string ctx (Section 4.1 of [VDAF]), a public nonce of length NONCE_SIZE, and the randomness consumed by the algorithm of length RAND_SIZE. Its outputs are the public sequence of "correction words", one for each level of the tree, and the secret keys, one for each Aggregator.¶

• TODO Give a high level overview of how IDPF works, in particular the seed/control-bit invariant for each level. Define CorrectionWord and explain the role of correction words and define node proofs, which are unique to VIDPF.¶

  TODO Specify bounds on the inputs, namely that the nonce has to be random. (This is inherited from IDPF security considerations.)¶

  TODO Explain functional differences between VIDPF and IDPF in Section 8 of [VDAF]. Namely, there is no distinction between inner and leaf nodes and the payload is supposed to be the same at each level.¶

def gen(self,
        alpha: tuple[bool, ...],
        beta: list[F],
        ctx: bytes,
        nonce: bytes,
        rand: bytes,
        ) -> tuple[list[CorrectionWord], list[bytes]]:
    '''
    The VIDPF key generation algorithm.

    Returns the public share (i.e., the correction word for each
    level of the tree) and two keys, one for each aggregator.

    Implementation note: for clarity, this algorithm has not been
    written in a manner that is side-channel resistant. To avoid
    leaking `alpha` via a side-channel, implementations should avoid
    branching or indexing into arrays in a data-dependent manner.
    '''
    if len(alpha) != self.BITS:
        raise ValueError("alpha out of range")
    if len(beta) != self.VALUE_LEN:
        raise ValueError("incorrect beta length")
    if len(nonce) != self.NONCE_SIZE:
        raise ValueError("incorrect nonce size")
    if len(rand) != self.RAND_SIZE:
        raise ValueError("randomness has incorrect length")

    keys = [rand[:self.KEY_SIZE], rand[self.KEY_SIZE:]]

    # [MST24, Fig. 15]: s0^0, s1^0, t0^0, t1^0
    seed = keys.copy()
    ctrl = [False, True]
    correction_words = []
    for i in range(self.BITS):
        idx = PrefixTreeIndex(alpha[:i+1])
        bit = alpha[i]

        # [MST24]: if x = 0 then keep <- L, lose <- R
        #
        # Implementation note: the value of `bit` is
        # `alpha`-dependent.
        (keep, lose) = (1, 0) if bit else (0, 1)

        # Extend: compute the left and right children the current
        # level of the tree. During evaluation, one of these children
        # will be selected as the next seed and control bit.
        #
        # [MST24]: s_0^L || s_0^R || t_0^L || t_0^R
        #          s_1^L || s_1^R || t_1^L || t_1^R
        (s0, t0) = self.extend(seed[0], ctx, nonce)
        (s1, t1) = self.extend(seed[1], ctx, nonce)

        # Compute the correction words for this level's seed and
        # control bit. Our goal is to maintain the following
        # invariant, after correction:
        #
        # * If evaluation is on path, then each aggregator will
        #   compute a different seed and their control bits will be
        #   secret shares of one.
        #
        # * If evaluation is off path, then the aggregators will
        #   compute the same seed and their control bits will be
        #   shares of zero.
        #
        # Implementation note: the index `lose` is `alpha`-dependent.
        seed_cw = xor(s0[lose], s1[lose])
        ctrl_cw = [
            t0[0] ^ t1[0] ^ (not bit),  # [MST24]: t_c^L
            t0[1] ^ t1[1] ^ bit,        # [MST24]: t_c^R
        ]

        # Correct.
        #
        # Implementation note: the index `keep` is `alpha`-dependent,
        # as is `ctrl`.
        if ctrl[0]:
            s0[keep] = xor(s0[keep], seed_cw)
            t0[keep] ^= ctrl_cw[keep]
        if ctrl[1]:
            s1[keep] = xor(s1[keep], seed_cw)
            t1[keep] ^= ctrl_cw[keep]

        # Convert.
        (seed[0], w0) = self.convert(s0[keep], ctx, nonce)
        (seed[1], w1) = self.convert(s1[keep], ctx, nonce)
        ctrl[0] = t0[keep]  # [MST24]: t0'
        ctrl[1] = t1[keep]  # [MST24]: t1'

        # Compute the correction word for this level's payload.
        #
        # Implementation note: `ctrl` is `alpha`-dependent.
        w_cw = vec_add(vec_sub(beta, w0), w1)
        if ctrl[1]:
            w_cw = vec_neg(w_cw)

        # Compute the correction word for this level's node proof. If
        # evaluation is on path, then exactly one of the aggregatos
        # will correct their node proof, causing them to compute the
        # same node value. If evaluation is off path, then both will
        # correct or neither will; and since they compute the same
        # seed, they will again compute the same value.
        proof_cw = xor(
            self.node_proof(seed[0], ctx, idx),
            self.node_proof(seed[1], ctx, idx),
        )

        correction_words.append((seed_cw, ctrl_cw, w_cw, proof_cw))

    return (correction_words, keys)

3.2. Key Evaluation

The VIDPF-key evaluation algorithm is listed below. See Section 3.3 for deferred auxiliary functions. Its inputs are the Aggregator's ID (either 0 or 1), the correction words, the Aggregator's key, the level of the tree, the sequence of prefixes, and the nonce associated with the report. Its outputs are the sequence of output shares for each prefix, and the evaluation proof.¶

• TODO Define PrefixTreeIndex and PrefixTreeEntry.¶

  TODO Say why we also visit the siblings of nodes in the prefix tree (it's needed for Mastic).¶

def eval_next(self,
                node: PrefixTreeEntry,
                correction_word: CorrectionWord,
                ctx: bytes,
                nonce: bytes,
                idx: PrefixTreeIndex,
                ) -> PrefixTreeEntry:
    """
    Extend a node in the tree, select and correct one of its
    children, then convert it into a payload and the next seed.
    """
    (seed_cw, ctrl_cw, w_cw, proof_cw) = correction_word
    keep = int(idx.path[-1])

    # Extend.
    #
    # [MST24, Fig. 17]: (s^L, s^R), (t^L, t^R) = PRG(s^{i-1})
    (s, t) = self.extend(node.seed, ctx, nonce)

    # Correct.
    #
    # Implementation note: avoid branching on the value of control
    # bits, as its value may be leaked by a side channel.
    if node.ctrl:
        s[keep] = xor(s[keep], seed_cw)
        t[keep] ^= ctrl_cw[keep]

    # Convert and correct the payload.
    #
    # Implementation note: the conditional addition should be
    # replaced with a constant-time select in practice in order to
    # reduce leakage via timing side channels.
    (next_seed, w) = self.convert(s[keep], ctx, nonce)
    next_ctrl = t[keep]  # [MST24]: s^i, W^i, t'^i
    if next_ctrl:
        w = vec_add(w, w_cw)

    # Compute and correct the node proof.
    #
    # Implementation note: avoid branching on the control bit here.
    node_proof = self.node_proof(next_seed, ctx, idx)
    if next_ctrl:
        node_proof = xor(node_proof, proof_cw)

    return PrefixTreeEntry(next_seed, next_ctrl, w, node_proof)

Evaluating the prefix tree, plus the sibling of each n ode in the prefix tree:¶

def eval_with_siblings(self,
                        agg_id: int,
                        correction_words: list[CorrectionWord],
                        key: bytes,
                        level: int,
                        prefixes: tuple[tuple[bool, ...], ...],
                        ctx: bytes,
                        nonce: bytes,
                        ) -> tuple[list[list[F]], PrefixTreeEntry]:
    """
    The VIDPF key evaluation algorithm.

    The return value consists of the weights for each candidate prefix and
    the root of the prefix tree. The prefix tree includes the prefixes and
    the siblings of each node visited.
    """
    if agg_id not in range(2):
        raise ValueError("invalid aggregator ID")
    if len(correction_words) != self.BITS:
        raise ValueError("corrections words has incorrect length")
    if level not in range(self.BITS):
        raise ValueError("level too deep")
    for prefix in prefixes:
        if len(prefix) != level + 1:
            raise ValueError("prefix with incorrect length")
    if len(set(prefixes)) != len(prefixes):
        raise ValueError("candidate prefixes are non-unique")

    # Evaluate our share of the prefix tree, including the sibling of each
    # node we visit.
    #
    # Implementation note: we can save computation by storing the tree
    # across `eval()` calls for the same report.
    root = PrefixTreeEntry.root(key, bool(agg_id))
    out_share = []
    for prefix in prefixes:
        n = root
        for (i, bit) in enumerate(prefix):
            idx = PrefixTreeIndex(prefix[:i+1])
            if n.left_child is None:
                n.left_child = self.eval_next(n, correction_words[i], ctx,
                                                nonce, idx.left_sibling())
            if n.right_child is None:
                n.right_child = self.eval_next(n, correction_words[i], ctx,
                                                nonce, idx.right_sibling())
            n = n.right_child if bit else n.left_child
        out_share.append(n.w if agg_id == 0 else vec_neg(n.w))

    return (out_share, root)

Obtaining our share of beta, the payload programmed into the prefix tree:¶

def get_beta_share(
        self,
        agg_id: int,
        correction_words: list[CorrectionWord],
        key: bytes,
        ctx: bytes,
        nonce: bytes,
) -> list[F]:
    root = PrefixTreeEntry.root(key, bool(agg_id))
    left = self.eval_next(root, correction_words[0], ctx, nonce,
                          PrefixTreeIndex((False,)))
    right = self.eval_next(root, correction_words[0], ctx, nonce,
                           PrefixTreeIndex((True,)))
    beta_share = vec_add(left.w, right.w)
    if agg_id == 1:
        beta_share = vec_neg(beta_share)
    return beta_share

3.3. Auxiliary functions

def extend(self,
            seed: bytes,
            ctx: bytes,
            nonce: bytes,
            ) -> tuple[list[bytes], Ctrl]:
    '''
    Extend a seed into the seed and control bits for its left and
    right children in the VIDPF tree.
    '''
    xof = XofFixedKeyAes128(seed, dst(ctx, USAGE_EXTEND), nonce)
    s = [
        bytearray(xof.next(self.KEY_SIZE)),
        bytearray(xof.next(self.KEY_SIZE)),
    ]
    # Use the least significant bits as the control bit correction,
    # and then zero it out. This gives effectively 127 bits of
    # security, but reduces the number of AES calls needed by 1/3.
    t = [bool(s[0][0] & 1), bool(s[1][0] & 1)]
    s[0][0] &= 0xFE
    s[1][0] &= 0xFE
    return ([bytes(s[0]), bytes(s[1])], t)

def convert(self,
            seed: bytes,
            ctx: bytes,
            nonce: bytes,
            ) -> tuple[bytes, list[F]]:
    '''
    Convert a selected seed into a payload and the seed for the next
    level.
    '''
    xof = XofFixedKeyAes128(seed, dst(ctx, USAGE_CONVERT), nonce)
    next_seed = xof.next(XofFixedKeyAes128.SEED_SIZE)
    payload = xof.next_vec(self.field, self.VALUE_LEN)
    return (next_seed, payload)

def node_proof(self,
                seed: bytes,
                ctx: bytes,
                idx: PrefixTreeIndex) -> bytes:
    '''
    Compute the proof for this node.
    '''
    binder = \
        to_le_bytes(self.BITS, 2) + \
        to_le_bytes(idx.level(), 2) + \
        idx.encode()
    xof = XofTurboShake128(seed,
                            dst(ctx, USAGE_NODE_PROOF),
                            binder)
    return xof.next(PROOF_SIZE)

4.1. Sharding

The sharding algorithm takes in the measurement (the input and weight), the nonce, and the sharding randomness. The size of the nonce is 16 bytes; the size of the randomness is vidpf.RAND_SIZE + 2 * xof.SEED_SIZE, plus an additional xof.SEED_SIZE if the validity circuit takes joint randomness as input.¶

The public share is the sequence of correction words output by the VIPDF key generation algorithm. The contents of each input share, denoted MasticInputShare, depends on the Aggregator who receives it. We refer to the first Aggregator as the "Leader"; we refer to the second Aggregator as the "Helper". The components of the input share are:¶

1. The Aggregator's VIDPF key share.¶

2. An optional FLP proof share, a vector of field elements. This is set for the Leader only.¶

3. An optional seed. This is always set for the Helper, who uses it to derive its FLP proof share. This is set for the Leader of the circuit uses joint randomness.¶

4. The peer's FLP joint randomness seed, used to derive joint randomness for the FLP's validity circuit. This is set for both the Leader and Helper only if joint randomness is required (i.e., flp.JOINT_RAND_LEN > 0).¶

The behavior of the sharding algorithm depends on whether the circuit requires joint randomness:¶

def shard(self,
            ctx: bytes,
            measurement: tuple[tuple[bool, ...], W],
            nonce: bytes,
            rand: bytes,
            ) -> tuple[list[CorrectionWord], list[MasticInputShare]]:
    if self.flp.JOINT_RAND_LEN > 0:
        return self.shard_with_joint_rand(
            ctx, measurement, nonce, rand)
    return self.shard_without_joint_rand(
        ctx, measurement, nonce, rand)

When no FLP joint randomness is required, sharding involves the following steps:¶

1. Encode the weight weight as beta = [field(1)] + flp.encode(weight). The prefix [field(1)], is used to count how many reports share a prefix in common and is usesd during unsharding. More details in Section 4.5.¶

2. Generate the VIDPF correction words and keys for input alpha and beta as the payload.¶

3. Generate the FLP proof of validity for flp.encode(weight).¶

4. Compute the Leader's share of the proof.¶

• NOTE Each correction word has length flp.MEAS_LEN. We could save a little bit of communication by truncating the weights according to flp.truncate(). However, we still need to encode the full weight at least once, either separately or at the first level of the VIDPF tree. See issue #98 for details.¶

The complete algorithm is listed below:¶

def shard_without_joint_rand(
        self,
        ctx: bytes,
        measurement: tuple[tuple[bool, ...], W],
        nonce: bytes,
        rand: bytes,
) -> tuple[list[CorrectionWord], list[MasticInputShare]]:
    (vidpf_rand, rand) = front(self.vidpf.RAND_SIZE, rand)
    (prove_rand_seed, rand) = front(self.xof.SEED_SIZE, rand)
    (helper_seed, rand) = front(self.xof.SEED_SIZE, rand)
    assert len(rand) == 0  # REMOVE ME

    # Encode the inputs to VIDPF key generation. The output, denoted
    # `beta`, is a counter concatenated with the encoded weight.
    (alpha, weight) = measurement
    beta = [self.field(1)] + self.flp.encode(weight)

    # Generate VIDPF keys.
    (correction_words, keys) = \
        self.vidpf.gen(alpha, beta, ctx, nonce, vidpf_rand)

    # Generate FLP and split it into shares.
    prove_rand = self.prove_rand(ctx, prove_rand_seed)
    proof = self.flp.prove(beta[1:], prove_rand, [])
    helper_proof_share = self.helper_proof_share(ctx, helper_seed)
    leader_proof_share = vec_sub(proof, helper_proof_share)

    input_shares: list[MasticInputShare] = [
        (keys[0], leader_proof_share, None, None),
        (keys[1], None, helper_seed, None),
    ]
    return (correction_words, input_shares)

When FLP joint randomness is required, the Client must compute it from the shares of beta sent to each Aggregator:¶

1. Encode the weight weight as beta = [field(1)] + flp.encode(weight).¶

2. Generate the VIDPF correction words and keys for alpha and beta.¶

3. Compute each Aggregator's FLP joint randomness part by hashing its share of beta with its FLP seed, its VIDPF key, and the VIDPF correction words.¶

4. Compute the FLP joint randomness seed by hashing the joint randomness parts.¶

5. Derive the FLP joint randomness from the joint randomness seed.¶

6. Generate the FLP proof of beta's validity using the derived joint randomness.¶

7. Compute the Leader's share of the proof.¶

The joint randomness is also needed to verify the FLP and must therefore be recomputed during preparation (Section 4.2). To accomplish this, the Client includes in each Aggregator's input share the joint randomness part of its peer.¶

The complete algorithm is listed below:¶

def shard_with_joint_rand(
        self,
        ctx: bytes,
        measurement: tuple[tuple[bool, ...], W],
        nonce: bytes,
        rand: bytes,
) -> tuple[list[CorrectionWord], list[MasticInputShare]]:
    (vidpf_rand, rand) = front(self.vidpf.RAND_SIZE, rand)
    (prove_rand_seed, rand) = front(self.xof.SEED_SIZE, rand)
    (helper_seed, rand) = front(self.xof.SEED_SIZE, rand)
    (leader_seed, rand) = front(self.xof.SEED_SIZE, rand)
    assert len(rand) == 0  # REMOVE ME

    # Encode the inputs to VIDPF key generation. The output, denoted
    # `beta`, is a counter concatenated with the encoded weight.
    (alpha, weight) = measurement
    beta = [self.field(1)] + self.flp.encode(weight)

    # Generate VIDPF keys.
    (correction_words, keys) = \
        self.vidpf.gen(alpha, beta, ctx, nonce, vidpf_rand)

    # Generate FLP joint randomness.
    leader_beta_share = self.vidpf.get_beta_share(0, correction_words,
                                                    keys[0], ctx, nonce)
    helper_beta_share = self.vidpf.get_beta_share(1, correction_words,
                                                    keys[1], ctx, nonce)
    joint_rand_parts = [
        self.joint_rand_part(ctx, leader_seed, leader_beta_share[1:],
                                nonce),
        self.joint_rand_part(ctx, helper_seed, helper_beta_share[1:],
                                nonce),
    ]
    joint_rand = self.joint_rand(
        ctx, self.joint_rand_seed(ctx, joint_rand_parts))

    # Generate FLP and split it into shares.
    prove_rand = self.prove_rand(ctx, prove_rand_seed)
    proof = self.flp.prove(beta[1:], prove_rand, joint_rand)
    helper_proof_share = self.helper_proof_share(ctx, helper_seed)
    leader_proof_share = vec_sub(proof, helper_proof_share)

    leader_joint_rand_part: Optional[bytes] = joint_rand_parts[0]
    helper_joint_rand_part: Optional[bytes] = joint_rand_parts[1]
    input_shares = [
        (keys[0], leader_proof_share, leader_seed, helper_joint_rand_part),
        (keys[1], None, cast(Optional[bytes],
            helper_seed), leader_joint_rand_part),
    ]
    return (correction_words, input_shares)

4.2. Preparation

Each Aggregator initializes preparation with: the verification key shared by both Aggregators; its own ID, either 0 for the Leader and 1 for the Helper; the aggregation parameter; the report's nonce; the public share sent to each Aggregator; and the Aggregator's own input share.¶

The aggregation parameter has the following components:¶

1. the level of the VIDPF being evaluated¶

2. the sequence of VIDPF prefixes being evaluated¶

3. an indication of whether to verify the FLP¶

The FLP is verified exactly once, the first time the report is aggregated. See Section 4.3.¶

The outputs of the initialization algorithm include the Aggregator's prep state, denoted MasticPrepState, and its outbound prep share, denoted MasticPrepShare. The prep share includes the Aggregator's FLP verifier share, joint randomness part, and VIDPF proof. These are combined into the prep message in the next step.¶

Preparation initialization involves the following steps:¶

1. Evaluate the VIDPF share on the sequence of prefixes, obtaining our share of the prefix tree.¶

2. If applicable, run the FLP query generation algorithm on our share of the encoded weight to obtain our FLP verifier share. If joint randomness is required, then compute our joint randomness part and derive the joint randomness seed using our peer Aggregator's part provided by the Client. Note that the Client may have provided the wrong part, so we need to check that the seed was computed correctly before completing preparation.¶

3. Truncate each payload share according to the FLP encoding scheme and flatten them into a single vector of field elements. This constitutes Mastic's output share.¶

Moreover, when the Aggregators evaluate a Client's VIDPF, they verify three properties of the prefix tree:¶

1. One-hotness: at every level of the tree, at most one node has a non-zero payload.¶

2. Payload consistency: each payload is equal to the sum of the payloads of its children. If one-hotness holds, then this ensures the payload is equal to beta for each node along the alpha path.¶

3. Counter consistency: the counter of the non-zero payload is equal to field(1).¶

• TODO Define the "evaluation proof".¶

The complete algorithm is listed below:¶

def prep_init(
        self,
        verify_key: bytes,
        ctx: bytes,
        agg_id: int,
        agg_param: MasticAggParam,
        nonce: bytes,
        correction_words: list[CorrectionWord],
        input_share: MasticInputShare,
) -> tuple[MasticPrepState, MasticPrepShare]:
    (level, prefixes, do_weight_check) = agg_param
    (key, proof_share, seed, peer_joint_rand_part) = \
        self.expand_input_share(ctx, agg_id, input_share)

    # Evaluate the VIDPF.
    (out_share, root) = self.vidpf.eval_with_siblings(
        agg_id,
        correction_words,
        key,
        level,
        prefixes,
        ctx,
        nonce,
    )

    # Query the FLP if applicable.
    joint_rand_part = None
    joint_rand_seed = None
    verifier_share = None
    if do_weight_check:
        beta_share = self.vidpf.get_beta_share(agg_id, correction_words,
                                                key, ctx, nonce)
        query_rand = self.query_rand(verify_key, ctx, nonce, level)
        joint_rand = []
        if self.flp.JOINT_RAND_LEN > 0:
            assert seed is not None
            assert peer_joint_rand_part is not None
            joint_rand_part = self.joint_rand_part(ctx, seed,
                                                    beta_share[1:], nonce)
            if agg_id == 0:
                joint_rand_parts = [joint_rand_part, peer_joint_rand_part]
            else:
                joint_rand_parts = [peer_joint_rand_part, joint_rand_part]
            joint_rand_seed = self.joint_rand_seed(ctx, joint_rand_parts)
            joint_rand = self.joint_rand(ctx, joint_rand_seed)
        verifier_share = self.flp.query(
            beta_share[1:],
            proof_share,
            query_rand,
            joint_rand,
            2,
        )

    # Payload and onehot checks.
    payload_check_binder = b''
    onehot_check_binder = b''
    assert root.left_child is not None
    assert root.right_child is not None
    q = [root.left_child, root.right_child]
    while len(q) > 0:
        (n, q) = (q[0], q[1:])

        if n.left_child is not None and n.right_child is not None:
            # Update payload check. The weight of each node should equal
            # the sum of its children.
            payload_check_binder += self.field.encode_vec(
                vec_sub(n.w, vec_add(n.left_child.w, n.right_child.w)))
            q += [n.left_child, n.right_child]

        # Update the onehot check.
        onehot_check_binder += n.proof

    payload_check = self.xof(
        b'',
        dst_alg(ctx, USAGE_PAYLOAD_CHECK, self.ID),
        payload_check_binder,
    ).next(PROOF_SIZE)

    onehot_check = self.xof(
        b'',
        dst_alg(ctx, USAGE_ONEHOT_CHECK, self.ID),
        onehot_check_binder,
    ).next(PROOF_SIZE)

    # Counter check: the first element of beta should equal 1.
    #
    # Each aggregator holds an additive share of the counter, so
    # we have aggregator 1 negate its share and add 1 so that they
    # both compute the same value for `counter`.
    w0 = root.left_child.w
    w1 = root.right_child.w
    counter_check = self.field.encode_vec(
        [w0[0] + w1[0] + self.field(agg_id)])

    # Evaluation proof: if both aggregators compute the same
    # value, then they agree on the onehot proof, the counter, and
    # the payload.
    eval_proof = self.xof(
        verify_key,
        dst_alg(ctx, USAGE_EVAL_PROOF, self.ID),
        onehot_check + counter_check + payload_check,
    ).next(PROOF_SIZE)

    # Concatenate the output shares into one aggregatable output,
    # applying the FLP truncation algorithm on each FLP measurement
    # share.
    truncated_out_share = []
    for val_share in out_share:
        truncated_out_share += [val_share[0]] + \
            self.flp.truncate(val_share[1:])

    prep_state = (truncated_out_share, joint_rand_seed)
    prep_share = (eval_proof, verifier_share, joint_rand_part)
    return (prep_state, prep_share)

Next, the Aggregators' prep shares are combined into the prep message, denoted MasticPrepMessage:¶

1. Check that both Aggregators computed the same VIDPF proof. If so, then it is presumed that the output share is one-hot, has path consistency, and has counter consistency as defined in Section 3.¶

2. If applicable, combine the FLP verifier shares into the FLP verifier and run the FLP decision algorithm. If successful, then it is presumed that the weight is valid.¶

3. If applicable, compute the FLP joint randomness seed from the parts.¶

The prep message consists of the optional joint randomness seed. The complete algorithm is listed below:¶

def prep_shares_to_prep(
        self,
        ctx: bytes,
        agg_param: MasticAggParam,
        prep_shares: list[MasticPrepShare],
) -> MasticPrepMessage:
    (_level, _prefixes, do_weight_check) = agg_param

    if len(prep_shares) != 2:
        raise ValueError('unexpected number of prep shares')

    (eval_proof_0,
     verifier_share_0,
     joint_rand_part_0) = prep_shares[0]
    (eval_proof_1,
     verifier_share_1,
     joint_rand_part_1) = prep_shares[1]

    # Verify the VIDPF output.
    if eval_proof_0 != eval_proof_1:
        raise Exception('VIDPF verification failed')

    if not do_weight_check:
        return None
    if verifier_share_0 is None or verifier_share_1 is None:
        raise ValueError('expected FLP verifier shares')

    # Verify the FLP.
    verifier = vec_add(verifier_share_0, verifier_share_1)
    if not self.flp.decide(verifier):
        raise Exception('FLP verification failed')

    if self.flp.JOINT_RAND_LEN == 0:
        return None
    if joint_rand_part_0 is None or joint_rand_part_1 is None:
        raise ValueError('expected FLP joint randomness parts')

    # Confirm the FLP joint randomness was computed properly.
    prep_msg = self.joint_rand_seed(ctx, [
        joint_rand_part_0,
        joint_rand_part_1,
    ])
    return prep_msg

Finally, each Aggregator completes preparation by checking that the true FLP joint randomness seed is equal to the value they computed in the initialization step, prep_init(). This is only done if a weight check was required by the aggregation parameter and joint randomness was required by the FLP:¶

def prep_next(self,
                _ctx: bytes,
                prep_state: MasticPrepState,
                prep_msg: MasticPrepMessage,
                ) -> list[F]:
    (truncated_out_share, joint_rand_seed) = prep_state
    if joint_rand_seed is not None:
        if prep_msg is None:
            raise ValueError('expected joint rand confirmation')

        if prep_msg != joint_rand_seed:
            raise Exception('joint rand confirmation failed')

    return truncated_out_share

4.3. Validity of Aggregation Parameters

To guarantee secure execution of Mastic, care must be taken in choosing the VIDPF prefixes and whether to verify the FLP. In particular, it is only safe to consume the FLP once; and it is only safe to evaluate the VIDPF at most once at any given level of the tree.¶

• NOTE By "safe" we mean "covered by the analysis of [MPDST25]". It could be that we have a little more wiggle room, but we're not certain. If we find matching attacks, we should mention them in Section 5.¶

We further restrict aggregation by requiring that the level strictly increases at each step:¶

def is_valid(self,
                agg_param: MasticAggParam,
                previous_agg_params: list[MasticAggParam],
                ) -> bool:
    (level, _prefixes, do_weight_check) = agg_param

    # Check that the weight check is done exactly once.
    weight_checked = \
        (do_weight_check and len(previous_agg_params) == 0) or \
        (not do_weight_check and
            any(agg_param[2] for agg_param in previous_agg_params))

    # Check that the level is strictly increasing.
    level_increased = len(previous_agg_params) == 0 or \
        level > previous_agg_params[-1][0]

    return weight_checked and level_increased

4.4. Aggregation

Each output share consists of the truncated payload for each VIDPF prefix, flattened into a single vector. Aggregation involves simply adding these up:¶

def agg_init(self, agg_param: MasticAggParam) -> list[F]:
    (_level, prefixes, _do_weight_check) = agg_param
    agg = self.field.zeros(len(prefixes)*(1+self.flp.OUTPUT_LEN))
    return agg

def agg_update(self,
                agg_param: MasticAggParam,
                agg_share: list[F],
                out_share: list[F]) -> list[F]:
    return vec_add(agg_share, out_share)

def merge(self,
            agg_param: MasticAggParam,
            agg_shares: list[list[F]]) -> list[F]:
    (_level, prefixes, _do_weight_check) = agg_param
    agg = self.agg_init(agg_param)
    for agg_share in agg_shares:
        agg = vec_add(agg, agg_share)
    return cast(list[F], agg)

4.5. Unsharding

The aggregate result consists of a list of total weights, each corresponding to one of the prefixes. To compute it:¶

1. Add up the aggregate shares.¶

2. For each prefix, decode the corresponding vector chunk using the FLP's decoding algorithm (Section 7.1.1 of [VDAF]). This requires the prefix count, which is also encoded by the chunk.¶

The complete algorithm is listed below:¶

def unshard(self,
            agg_param: MasticAggParam,
            agg_shares: list[list[F]],
            _num_measurements: int,
            ) -> list[R]:
    agg = self.merge(agg_param, agg_shares)

    agg_result = []
    while len(agg) > 0:
        (chunk, agg) = front(self.flp.OUTPUT_LEN + 1, agg)
        meas_count = chunk[0].int()
        agg_result.append(self.flp.decode(chunk[1:], meas_count))
    return agg_result

4.6. Auxiliary Functions

def expand_input_share(
        self,
        ctx: bytes,
        agg_id: int,
        input_share: MasticInputShare,
) -> tuple[bytes, list[F], Optional[bytes], Optional[bytes]]:
    if agg_id == 0:
        (key, proof_share, seed, peer_joint_rand_part) = input_share
        assert proof_share is not None
    else:
        (key, _leader_proof_share, seed, peer_joint_rand_part) = input_share
        assert seed is not None
        proof_share = self.helper_proof_share(ctx, seed)
    return (key, proof_share, seed, peer_joint_rand_part)

def helper_proof_share(self, ctx, seed: bytes) -> list[F]:
    return self.xof.expand_into_vec(
        self.field,
        seed,
        dst_alg(ctx, USAGE_PROOF_SHARE, self.ID),
        b'',
        self.flp.PROOF_LEN,
    )

def prove_rand(self, ctx: bytes, seed: bytes) -> list[F]:
    return self.xof.expand_into_vec(
        self.field,
        seed,
        dst_alg(ctx, USAGE_PROVE_RAND, self.ID),
        b'',
        self.flp.PROVE_RAND_LEN,
    )

def joint_rand_part(
        self,
        ctx: bytes,
        seed: bytes,
        weight_share: list[F],
        nonce: bytes,
) -> bytes:
    return self.xof.derive_seed(
        seed,
        dst_alg(ctx, USAGE_JOINT_RAND_PART, self.ID),
        nonce + self.field.encode_vec(weight_share),
    )

def joint_rand_seed(self, ctx: bytes, parts: list[bytes]) -> bytes:
    return self.xof.derive_seed(
        b'',
        dst_alg(ctx, USAGE_JOINT_RAND_SEED, self.ID),
        concat(parts),
    )

def joint_rand(self, ctx: bytes, seed: bytes) -> list[F]:
    return self.xof.expand_into_vec(
        self.field,
        seed,
        dst_alg(ctx, USAGE_JOINT_RAND, self.ID),
        b'',
        self.flp.JOINT_RAND_LEN,
    )

def query_rand(self,
               verify_key: bytes,
               ctx: bytes,
               nonce: bytes,
               level: int) -> list[F]:
    return self.xof.expand_into_vec(
        self.field,
        verify_key,
        dst_alg(ctx, USAGE_QUERY_RAND, self.ID),
        nonce + to_le_bytes(level, 2),
        self.flp.QUERY_RAND_LEN,
    )

7.1. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

[VDAF]

Barnes, R., Cook, D., Patton, C., and P. Schoppmann, "Verifiable Distributed Aggregation Functions", Work in Progress, Internet-Draft, draft-irtf-cfrg-vdaf-14, 10 January 2025, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-14>.

7.2. Informative References

[BGI15]

Boyle, E., Gilboa, N., and Y. Ishai, "Function Secret Sharing", EUROCRYPT 2015 , 2015, <https://www.iacr.org/archive/eurocrypt2015/90560300/90560300.pdf>.

[CP22]

de Castro, L. and A. Polychroniadou, "Lightweight, Maliciously Secure Verifiable Function Secret Sharing", EUROCRYPT 2022 , 2022, <https://iacr.org/cryptodb/data/paper.php?pubkey=31935>.

[DAP]

Geoghegan, T., Patton, C., Rescorla, E., and C. A. Wood, "Distributed Aggregation Protocol for Privacy Preserving Measurement", Work in Progress, Internet-Draft, draft-ietf-ppm-dap-07, 14 September 2023, <https://datatracker.ietf.org/doc/html/draft-ietf-ppm-dap-07>.

[MPDST25]

Mouris, D., Patton, C., Davis, H., Sarkar, P., and N. G. Tsoutsos, "Mastic: Private Weighted Heavy-Hitters and Attribute-Based Metrics", PETS 2025 , 2025, <https://ia.cr/2024/221>.

[MST24]

Mouris, D., Sarkar, P., and N. G. Tsoutsos, "PLASMA: Private, Lightweight Aggregated Statistics against Malicious Adversaries", PETS 2024 , 2024, <https://ia.cr/2023/080>.

[RFC9110]

Fielding, R., Ed., Nottingham, M., Ed., and J. Reschke, Ed., "HTTP Semantics", STD 97, RFC 9110, DOI 10.17487/RFC9110, June 2022, <https://www.rfc-editor.org/rfc/rfc9110>.

[RZCGP24]

Rathee, M., Zhang, Y., Corrigan-Gibbs, H., and R. A. Popa, "Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs", IEEE S&P 2024 , 2024, <https://eprint.iacr.org/2024/666>.

[SHS]

"Secure hash standard", National Institute of Standards and Technology (U.S.), DOI 10.6028/nist.fips.180-4, 2015, <https://doi.org/10.6028/nist.fips.180-4>.

[W3C23]

W3C Working Group, "Network Error Logging", 2023, <https://www.w3.org/TR/network-error-logging>.

Network Error Logging

Network Error Logging (NEL) is a mechanism used by web browsers to report errors that occur while attempting to establish a connection to a server [W3C23]. Some of these errors are visible to the server, but not all: failures in DNS, TCP, TLS, and HTTP can occur without the server having any visibility into the issue. A small amount of connection errors is expected, even under normal operating conditions; but a sudden, substantial increase in errors may be an indication of an outage, or a configuration issue impacting millions of users. Without a reporting mechanism like NEL, these events would only manifest in the server's telemetry as a drop in overall traffic.¶

NEL is particularly important for content delivery networks that handle HTTP traffic for a large number of websites (typically millions). A content delivery network acts as a reverse proxy between clients and origin servers that provides a layer of caching and security services, such as DDoS protection.¶

Reports are comprised of the URL the client attempted to navigate to (e.g., "https://example.com"), the type of error that occurred, and metadata related to the attempt, such as the time that elapsed between when the connection attempt began and the error was observed (e.g., Section 7 of [W3C23]). Clients may also report successful connection attempts to give the server a sense of the error rate. The exact client behavior is determined by the reporting policy specified by the server (see Section 5.1 of [W3C23]).¶

NEL data is privacy-sensitive for two reasons. First, it exposes information that the server would not otherwise have access to, which can be abused to probe the client's network configuration as described in Section 9 of [W3C23]. Second, for operational reasons, the reporting endpoint may be organizationally separated from the server (i.e., run on different cloud infrastructures), leading to an increased risk of the client's browsing history being exposed (e.g., in a data breach).¶

MPC helps mitigate these risks by revealing to the endpoint only the information it needs to fulfill its service level objectives. This means, of course, we must be satisfied with limited functionality. Fortunately, Mastic allows us to preserve the most important functionality of NEL while minimizing privacy loss.¶

Mastic can be applied to a simplified version of NEL where each client reports a tuple (dom, err) consisting of a domain name dom (e.g., "example.com") and a value err that represents an error (e.g., "dns.unreachable") or an indication that no error occurred (e.g., "ok"). Notably, this can be easily extended in Mastic to represent more elaborate metrics. e.g., where each weight includes the time it took each browser to report the error (and the aggregate is the average error reporting time), user agent (browser type and version), etc. However, our main goal is to understand 1) the distribution of errors and 2) which domains are impacted.¶

We expect there to be a large number of distinct domain names (millions in the case of content delivery networks) and only a small number of error variants (the NEL spec [W3C23] defines 30 variants). The following Mastic parameters are suitable for this application.¶

Each input would encode the domain dom encoded with a number of bits sufficient to uniquely represent most of the domains; and each weight would represent the error variant dom. To compute the distribution of errors, we would encode each error variant as a distinct bucket of a histogram so that [1, 0, 0, ...] represents "ok", [0, 1, 0, ...] represents "dns.unreachable", and so on. (See ection 6 of [W3C23].), This is similar to Prio3Histogram (Section 7 of [VDAF].)¶

Attribute-Based Browser Telemetry

Web browsers collect telemetry generated by users as they navigate the web to gain insights into trends that guide product decisions. In many cases, Prio3 (Section 7 of [VDAF]) can be used to privately aggregate this telemetry. However, this comes at the cost of flexibility.¶

For example, Prio3 can be used to collect page load metrics from Browser for a list of known popular sites (e.g., "example.com"). The purpose of these metrics is to detect if changes to these sites cause regressions that might be correlated with an increased average load time or error rate. A subtle, but important requirement for this system is the ability to break down the metrics by client attributes. Suppose for example that we want to aggregate by 1) the software version, and 2) the information about the client's location.¶

Mastic provides a simple solution to this problem. For the sake of presentation, we consider a simplified use case (the same approach can be applied to any aggregation task for which Prio3 (Section 7 of [VDAF]) is suitable). Each client reports a tuple (ver, loc, site, time) where: ver is a string representing the client's software version (e.g., "Browser/122.0"); loc is a string encoding its country code (e.g., "GR", "US", "IN", etc.); site is one of a fixed set of sites (e.g., "example.com", "example.org", etc.); and time is the load time of the site in seconds. The version and location are included in the Mastic input; the site and load time are encoded by the corresponding weight. Notably, this is just one example of what Mastic can do; the same idea can be applied to other types of metrics.¶

Compared to the private NEL application in Appendix "Network Error Logging", the number of possible inputs here is relatively small: there are less than 200 country codes and a handful of browser versions in wide use at any given time. This means the aggregators can enumerate a set of inputs of interest and evaluate them immediately. Consider the following parameters for Mastic, in its attribute-based metrics mode of operation Appendix "Attribute-based Metrics":¶

• Attributes: Two-letter country codes can easily be encoded in 2 bytes. Likewise, the number of distinct browser versions is easily less than 2^16, so 2 bytes are sufficient. Therefore, each attribute can be encoded with just 32 bits.¶

• Values: Similar to private NEL, each weight is a 0-vector except for a single 1 representing a bucket in a histogram. We represent (site, time) as a histogram bucket as follows. First, we quantize time (in seconds) into one of four buckets: [0, 0.1), [0.1, 1), [1, 5), and [5, inf). Let 0 < t <= 4 denote the time bucket for time. Next, suppose we wish to track metrics for 25 sites. Let 0 < s <= 25 denote the index of site in this list. Then the index of 1 is simply t * s.¶

Weighted Heavy-Hitters

• NOTE See Appendix "Network Error Logging" for a motivating application and example_weighted_heavy_hitters_mode() in the reference implementation for an end-to-end example.¶

The primary use case for Mastic is a variant of the heavy-hitters problem, in which the prefix counts are replaced with a notion of weight that is specific to some application. For example, when measuring the performance of an ad campaign, it is useful to learn not only which ads led to purchases, but how much money was spent.¶

To support this use case, we view the Client's alpha value as its measurement and the beta value as the measurement's "weight". The range of valid values for beta are therefore determined by the FLP with which Mastic is instantiated. Concretely, validity of beta is expressed by a validity circuit (Section 7.3.2 of [VDAF]).¶

To compute the weighted heavy-hitters, the Collector and Aggregators proceed as described in Section 8 of [VDAF], except that the threshold represents a minimum weight rather than a minimum count. In addition:¶

1. The Aggregators MUST perform the range check (i.e., verify the FLP) at the first round of aggregation and remove any invalid reports before proceeding.¶

2. The level at which the reports are Aggregated MUST be strictly increasing.¶

Attribute-based Metrics

• NOTE See Appendix "Attribute-Based Browser Telemetry" for a motivating application and example_attribute_based_metrics_mode() in the reference implementation for an end-to-end example.¶

In this mode of operation, we take the beta value to be the Client's measurement and alpha to be an arbitrary "attribute". For a given sequence of attributes, the goal of the Collector is to aggregate the measurements that share the same attribute. This provides functionality similar to Prio3 [VDAF], except that the aggregate is partitioned by Clients who share some property. For example, the attribute might encode the Client's user agent [RFC9110].¶

Mastic requires each alpha to have the same length (Vidpf.BITS). Thus, it is necessary for each application to choose a scheme for encoding attributes as fixed-length strings. The following scheme is RECOMMENDED. Choose a cryptographically secure hash function, such as SHA256 [SHS], compute the hash of the Client's input string, and interpret each bit of the hash as a bit of the VIDPF index.¶

• TODO Are we comfortable recommending truncating the hash? Collisions aren't so bad since the Client can just lie about alpha anyway. The main thing is to pick a value for BITS that is large enough to avoid accidental collisions.¶

The Aggregators MAY aggregate a report any number times, but:¶

1. They MUST perform the range check (i.e., verify the FLP) the first time the reports are aggregated and remove any invalid reports before aggregating again.¶

2. The aggregation parameter MUST specify the last level of the VIDPF tree (i.e., level MUST be Vidpf.BITS-1).¶

• TODO Figure out if these requirements are strict enough. We may need to tighten aggregation parameter validity if we find out that aggregating at the same level more than once is not safe.¶

Plain Heavy-Hitters with VIDPF-Proof Aggregation

• TODO Take "silently verifiable proofs" from [RZCGP24] into account here, which allows us to aggregate the FLPs as well.¶

The total communication cost of using Mastic (or Poplar1 [VDAF]) for heavy hitters is O(num_measurements * Vidpf.BITS) bits exchanged between the Aggregators, where num_measurements is the number of reports being aggregated. For plain heavy-hitters, this can be reduced to O(Vidpf.BITS) in the best case.¶

The idea is to take advantage of the feature of VIDPF evaluation whereby the Aggregators compute identical VIDPF proofs if and only if the report is valid. This allows the proofs themselves to be aggregated: if each report in a batch of reports is valid, then the hash of their proofs will be equal as well; on the other hand, if one report is invalid, then the hash of the proofs will not be equal.¶

To facilitate isolation of the invalid report(s), the proof strings are arranged into a Merkle tree. During aggregation, the Aggregators interactively traverse the tree to detect the subtree(s) containing invalid reports and remove them from the batch.¶

• TODO Decide if we should spell this out in greater detail. This feature is not compatible with [DAP]; if we wanted to extend DAP to support this, then we'd need to specify the wire format of the messages exchanged between the Aggregators.¶

In the worst case, isolating invalid reports requires O(num_measurements * Vidpf.BITS) bits of communication and Vidpf.BITS many rounds of communication between the Aggregators. However, this behavior would only be observed under attack conditions in which the vast majority of Clients are malicious.¶

In the simple case where the beta value is a constant (e.g., 1) we can replace the FLP check with a simpler check. FLPs are not compatible with proof aggregation the way VIDPFs are. In order to perform the range check without FLPs, we use an extension of VIDPF described by [MST24]. The high-level idea here is that the Aggregators can evaluate the empty string and verify that they have shares of the constant beta. Next, as described in Section 4, we use the "one-hot verifiability" and "path verifiability" checks to verify that each level is non-zero at only a single point and that the same constant beta is propagated down the tree correctly. Note that this trick is not suitable for weighted heavy-hitters, since it expects that each beta value is constant (e.g., 1).¶

• TODO Proof aggregation could work with plain Mastic, but we would need to check the FLPs at the first round of aggregation, leading to best-case communication cost would be O(num_measurements + Vidpf.BITS). This would be OK, but we would still want to support a mode for plain heavy-hitters that is as good as we can get.¶

  One idea is to always do the PLASMA 0/1 check alongside the FLP. This would be useful for another reason: Usually FLP decoding requires num_measurements as a parameter. We currently don't support this because we currently don't have a pure counter as part of the VIDPF output.¶

Robustness Against a Malicious Aggregator

Next, we describe an enhancement that allows Mastic to achieve robustness in the presence of a malicious Aggregator. The two-party Mastic (as well as Poplar1) is susceptible to additive attacks by a malicious Aggregator. In more detail, if one of the Aggregators starts acting maliciously, they can arbitrarily add to the aggregation result (simply by adding to their own aggregation shares) without the honest Aggregator noticing.¶

We can solve this problem in Mastic by using a technique from [MST24] that lifts the two-party semi-honest secure PLASMA to the three-party maliciously secure setting. Rather than having two Aggregators as in the previous setting, this flavor involves three Aggregators, where every pair of Aggregators communicate over a different channel. In essence, each pair of Aggregators will run one session of the VDAF with unique randomness but on the same Client measurement. The following changes are necessary:¶

1. The Client needs to generate three pairs of VIDPF keys all corresponding to the same alpha and beta values. We represent the keys based on the session as follows:¶

   1. Session 0 (between Aggregators 0 and 1): key_01, key_10¶

   2. Session 1 (between Aggregators 1 and 2): key_12, key_21¶

   3. Session 2 (between Aggregators 2 and 0): key_20, key_02¶

   Each pair of Aggregators cannot check that the Client input is consistent across two sessions without the involvement of the third Aggregator. To address this, we let two Aggregators (i.e., Aggregators 0 and 1) to run all three sessions so that they can check that the Client input is consistent across three sessions. The third Aggregator (i.e., Aggregator 2) is involved as an attestator in two of the sessions. The check involves field addition and subtraction and then hash comparisons.¶

2. The Client sends the following keys to the Aggregators:¶

   1. Aggregator 0 receives: key_01, key_02, and key_21¶

   2. Aggregator 1 receives: key_10, key_12, and key_20¶

   3. Aggregator 2 receives: key_21 and key_20¶

3. The Aggregators need to verify that the Client's input is consistent across the different sessions (i.e., that all the keys correspond to the same alpha and beta values). Aggregators 0 and 1 check that:¶

   1. Their output shares of Session 0 minus their output shares of Session 1 are shares of zero¶

   2. Their output shares of Session 1 minus their output shares of Session 2 are shares of zero.¶

   The subtraction is a local operation and verifying that two Aggregators possess a sharing of zero requires exchanging one hash.¶

Using a third Aggregator, we can lift the security of Mastic from the semi-honest setting to malicious security. While more complex to implement than 2-party Mastic, this mode allows achieves both privacy and robustness against a malicious Aggregator.¶