The PREAMBLE VDAF

2.1. Domain Separation

Each invocation of an XOF is initialized with a domain separation tag built by dst_alg() below, which encodes the version of this document, an algorithm class byte, the 4-byte PREAMBLE algorithm identifier (Section 5 of [VDAF]), and a 2-byte code identifying how the XOF output is used.¶

The version of this document is a byte denoted VERSION. Its value SHALL be 0. The algorithm class byte is denoted ALG_CLASS and SHALL be 0.¶

• NOTE We'll bump VERSION whenever we publish a draft with incompatible changes from the previous draft.¶

Algorithms in the remainder use the following helper:¶

def dst_alg(usage: int, algorithm_id: int, ctx: bytes) -> bytes:
    assert usage in range(14)
    assert algorithm_id in range(2 ** 32)
    return byte(VERSION) \
        + byte(ALG_CLASS) \
        + to_be_bytes(algorithm_id, 4) \
        + to_be_bytes(usage, 2) \
        + ctx

Table 4 lists the usage codes referenced in the remainder of this document. Codes 2-7 are reused, unmodified, from Prio3's own domain separation scheme (Section 7.2 of [VDAF]); codes 11-13 are defined by this document. Prio3's code 1 (USAGE_MEAS_SHARE) is not used: PREAMBLE has no measurement share, because the FLP's encoded measurement is exactly the VDPF block (Section 3). Codes 3, 6, and 7 are derived only if flp.JOINT_RAND_LEN > 0. Codes 8-10 are RESERVED for future use and are not derived by this document.¶

4.1. Key Generation

The key generation algorithm is run by the Client. Its inputs are leaf_index: int (an integer in [0, num_leaf_nodes) identifying which block is nonzero, that is, the path through the tree, encoded as a bit tuple), values: list[F] (the nonzero block's encoded contents), the report nonce, and RAND_SIZE bytes of randomness. Its outputs are the VDPF-related portion of the public share, denoted CorrectionWords, and two private input shares, one for each Aggregator, each consisting of a seed.¶

The object CorrectionWords carries one correction word per tree level plus two additional correction words for the leaf level, each playing a different role in making the two Aggregators' otherwise-independent seed trees agree at every node off the path to leaf_index:¶

• An Internal Correction Word (one per level) carries a single seed correction word, applied identically to both children's expanded seeds, and two separate control bit correction words, ctrl_bit_left and ctrl_bit_right, one per child. The construction of these seeds and control bits maintains the following invariant at each node: the two Aggregators' seeds and control bits differ if and only if the node is on-path. If an Aggregator's control bit for the node being expanded is nonzero, it applies the correction word for that level to the seeds and control bits of the node's two children (Section 4.4, eval_next_children()). At an off-path node the two control bits are equal, so both Aggregators apply the correction or neither does, and their seeds and control bits stay equal in every off-path descendant. At an on-path node the two control bits differ, so exactly one Aggregator applies the correction. The correction words are chosen so that the off-path child ends up with equal seeds and control bits for both Aggregators, while the on-path child keeps differing seeds and control bits.¶

• The Leaf Correction Word is a vector of leaf_size field elements. Added into a leaf's field elements by whichever Aggregator has that leaf's control bit set (Section 4.4, eval_all()), it cancels out (both Aggregators apply it, or neither does) at every leaf other than leaf_index, and makes the two Aggregators' shares of the leaf at leaf_index sum to values.¶

• The Proof Correction Word does the analogous thing for the leaf-level sparsity proof (Section 4.3): it makes the two Aggregators' proof shares combine to the same value at every leaf except leaf_index, which is what lets Section 5.3 check one-block-sparsity without revealing leaf_index.¶

The wire-format encoding of these types is given in Section 5.7.1.¶

class InternalCorrectionWord:
    def __init__(self, seed_cw: bytes, ctrl_bit_left: bool,
                 ctrl_bit_right: bool):
        self.seed_cw = seed_cw
        self.ctrl_bit_left = ctrl_bit_left
        self.ctrl_bit_right = ctrl_bit_right

LeafCorrectionWord: TypeAlias = list[F]
ProofCorrectionWord: TypeAlias = bytes

class CorrectionWords(Generic[F]):
    def __init__(self,
                 internal_cws: list[InternalCorrectionWord],
                 leaf_cw: LeafCorrectionWord,
                 proof_cw: ProofCorrectionWord):
        self.internal_cws = internal_cws
        self.leaf_cw = leaf_cw
        self.proof_cw = proof_cw

The algorithm invokes the auxiliary functions extend() and compute_leaf_level(), defined in Section 4.4. It walks the tree from the root toward leaf_index, maintaining the same seed/control-bit invariant as Mastic's own key generation (Section 3.1 of [Mastic], informally): at every level, exactly one of the two children the Client is not traveling toward gets a correction word that, when applied by exactly one Aggregator, makes both Aggregators' seeds and control bits agree off the path and disagree on the path.¶

def gen(self,
        leaf_index: int,
        values: list[F],
        ctx: bytes,
        nonce: bytes,
        rand: bytes,
        ) -> tuple[CorrectionWords[F], list[bytes]]:
    '''
    Returns this DPF's correction words (the VDPF-only slice of the
    public share: the correction word for each internal level and
    leaf level of the tree, plus the proof correction word), and the
    two initial seeds, one for each Aggregator. The public share's
    other field, `joint_rand_parts`, is computed separately by the
    caller, though it binds the encoded correction words returned
    here.
    '''
    if leaf_index < 0 or leaf_index >= self.num_leaf_nodes:
        raise ValueError("leaf_index out of range")
    if len(nonce) != self.NONCE_SIZE:
        raise ValueError("incorrect nonce size")
    if len(rand) != self.RAND_SIZE:
        raise ValueError("randomness has incorrect length")

    # Step 1: Initial seeds sent to leader and helper.
    initial_seeds = [rand[:self.KEY_SIZE], rand[self.KEY_SIZE:]]
    # Seeds that are updated in each level of the tree.
    seeds = initial_seeds.copy()
    # Step 2: Signal for each aggregator whether to apply correction
    # words.
    # We maintain the invariant such that:
    # - If a node is on path, ctrl[0] ^ ctrl[1] = 1.
    # - If a node is off path, ctrl[0] ^ ctrl[1] = 0.
    # Initially set the helper's index to be True, so helper applies
    # the correction word.
    ctrl_bits_initial = [False, True]
    # Compute the internal-level correction words sent to both
    # aggregators.
    internal_cws: list[InternalCorrectionWord] = []
    # Step 3: Loop through each internal level of the DPF tree.
    for i in range(self.depth):
        bit = bool((leaf_index >> (self.depth - 1 - i)) & 1)

        # Step 4: Expand PRG into seed and control bit for both
        # aggregators.
        (s0, t0) = self.extend(seeds[0], ctx, nonce)
        (s1, t1) = self.extend(seeds[1], ctx, nonce)

        # Steps 5 and 6: If the current level is a 1, we will
        # traverse the right child (`keep` set to 1).
        # Otherwise, traverse the left child (`keep` set to 0).
        (keep, lose) = (1, 0) if bit else (0, 1)

        # Steps 7, 8, 9: 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
        # `leaf_index`-dependent.
        seed_cw = xor(s0[lose], s1[lose])
        ctrl_bits = [
            t0[0] ^ t1[0] ^ (not bit),
            t0[1] ^ t1[1] ^ bit,
        ]

        # Steps 10 and 11: Correct.
        #
        # Implementation note: the index `keep` is
        # `leaf_index`-dependent, as is `ctrl`.  If the control
        # bit is set, apply the correction words.
        if ctrl_bits_initial[0]:
            s0[keep] = xor(s0[keep], seed_cw)
            t0[keep] ^= ctrl_bits[keep]
        if ctrl_bits_initial[1]:
            s1[keep] = xor(s1[keep], seed_cw)
            t1[keep] ^= ctrl_bits[keep]

        # After correction, they become next level's seeds and
        # control bits.
        seeds[0] = s0[keep]
        seeds[1] = s1[keep]
        ctrl_bits_initial[0] = t0[keep]
        ctrl_bits_initial[1] = t1[keep]

        internal_cws.append(
            InternalCorrectionWord(
                seed_cw, ctrl_bits[0], ctrl_bits[1]))

    # Sample leader and helper's random field elements and also the
    # proofs for block sparsity from their seeds at the leaf level.
    # During generation, we use the full path which is leaf_index
    # (the block index).
    leaf_index_bytes = leaf_index.to_bytes(
        (self.depth + 7) // 8, byteorder='big')
    (w0, proof0) = self.compute_leaf_level(
        seeds[0], ctx, nonce + leaf_index_bytes)
    (w1, proof1) = self.compute_leaf_level(
        seeds[1], ctx, nonce + leaf_index_bytes)
    leaf_cw = vec_add(vec_sub(values, w0), w1)

    if ctrl_bits_initial[1]:
        leaf_cw = vec_neg(leaf_cw)
    proof_cw = xor(proof0, proof1)
    return (CorrectionWords(internal_cws, leaf_cw, proof_cw),
            initial_seeds)

4.2. Key Evaluation

The key evaluation algorithm is run independently by each Aggregator. Its inputs are the report nonce, the Aggregator's ID (0 for the first, 1 for the second), the Aggregator's key (one of the two seeds output by gen()), the Aggregator's initial control bit (0 for one Aggregator, 1 for the other), and the public share (consisting of the leaf correction word, proof correction word, and internal correction words and control bits). Its outputs are the Aggregator's share of every coordinate of the shared vector F, and one sparsity proof for the leaf.¶

def eval_all(self,
             ctx: bytes,
             nonce: bytes,
             agg_id: int,
             initial_seed: bytes,
             initial_ctrl_bit: bool,
             cws: CorrectionWords[F],
             ) -> tuple[list[F], list[bytes]]:
    '''
    Evaluate the field elements expanded from the leaf nodes. Every
    leaf contributes its full `leaf_size` field elements, so the
    result has exactly `num_leaf_nodes * leaf_size` field elements.
    '''
    root_node = EvalNode(level=0, seed=initial_seed,
                         ctrl_bit=initial_ctrl_bit)
    if self.depth == 0:
        # Nothing to traverse, only need to expand the leaf node.
        internal_nodes = []
        leaf_nodes = [root_node]
    else:
        internal_nodes = [root_node]
        leaf_nodes = []
    # Run BFS on the tree.
    while len(internal_nodes) > 0:
        node = internal_nodes.pop(0)
        (left_child, right_child) = self.eval_next_children(
            ctx, nonce, node, cws.internal_cws)
        if node.level < self.depth - 1:
            internal_nodes.append(left_child)
            internal_nodes.append(right_child)
        else:
            leaf_nodes.append(left_child)
            leaf_nodes.append(right_child)

    assert len(leaf_nodes) == self.num_leaf_nodes
    field_elems: list[F] = []
    proofs: list[bytes] = []
    for leaf_node in leaf_nodes:
        leaf_index_bytes = leaf_node.leaf_index.to_bytes(
            (self.depth + 7) // 8, byteorder='big')
        (w, proof) = self.compute_leaf_level(
            leaf_node.seed, ctx, nonce + leaf_index_bytes)
        if leaf_node.ctrl_bit:
            w = vec_add(w, cws.leaf_cw)
            proof = xor(proof, cws.proof_cw)
        if agg_id == 1:
            # Helper negates its share.
            w = vec_neg(w)
        field_elems.extend(w)
        proofs.append(proof)
    return field_elems, proofs

4.3. Node Identity and the Leaf-Level Sparsity Proof

Every leaf node's field elements and sparsity proof are sampled from an XOF whose binder is nonce + leaf_index_bytes, that is, the report nonce concatenated with the encoding of that specific leaf's own index (compute_leaf_level(), Section 4.4). This binds each leaf's output to its identity within the tree. The concatenated sparsity proofs are hashed into a one-hot check value, see (Section 5.3) for more details.¶

4.4. Auxiliary Functions

class EvalNode:
    def __init__(self, level: int, seed: bytes, ctrl_bit: bool,
                leaf_index: int = 0):
        self.level = level
        self.seed = seed
        self.ctrl_bit = ctrl_bit
        self.leaf_index = leaf_index

def eval_next_children(self,
                       ctx: bytes,
                       nonce: bytes,
                       node: EvalNode,
                       internal_cw_list:
                           list[InternalCorrectionWord],
                       ) -> tuple[EvalNode, EvalNode]:
    seed_cw = internal_cw_list[node.level].seed_cw
    ctrl_left_cw = internal_cw_list[node.level].ctrl_bit_left
    ctrl_right_cw = internal_cw_list[node.level].ctrl_bit_right
    (s, t) = self.extend(node.seed, ctx, nonce)
    if node.ctrl_bit:
        s[0] = xor(s[0], seed_cw)
        t[0] ^= ctrl_left_cw
        s[1] = xor(s[1], seed_cw)
        t[1] ^= ctrl_right_cw
    left_child = EvalNode(level=node.level + 1, seed=s[0],
                          ctrl_bit=t[0],
                          leaf_index=node.leaf_index << 1)
    right_child = EvalNode(level=node.level + 1, seed=s[1],
                           ctrl_bit=t[1],
                           leaf_index=(node.leaf_index << 1) | 1)
    return (left_child, right_child)

def extend(self,
           seed: bytes,
           ctx: bytes,
           nonce: bytes,
           ) -> tuple[list[bytes], list[bool]]:
    '''
    Extend a seed into the seed and control bits for its left and
    right children in the tree.
    '''
    xof = self.xof(
        seed, dst_alg(USAGE_EXTEND, self.algorithm_id, ctx), 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 compute_leaf_level(self,
                       seed: bytes,
                       ctx: bytes,
                       nonce: bytes) -> tuple[list[F], bytes]:
    '''
    Compute the field elements and sparsity proof at a leaf node,
    expanded from the seed. `nonce` is the report nonce concatenated
    with the leaf's identity; see {{node-identity}}.
    '''
    xof = self.xof(
        seed, dst_alg(USAGE_CONVERT, self.algorithm_id, ctx), nonce)
    vals: list[F] = xof.next_vec(self.field, self.leaf_size)
    proof: bytes = xof.next(PROOF_SIZE)
    return (vals, proof)

5.1. Fully Linear Proof

PREAMBLE checks the contents of the nonzero block with a Fully Linear Proof (FLP) system flp, which is a parameter of the construction. PREAMBLE uses flp only through the FLP interface of Section 7.1 of [VDAF]:¶

In addition to implementing that interface, an FLP used with PREAMBLE MUST satisfy the following:¶

1. flp.field is the field over which the VDPF is instantiated (Section 5). The VDPF secret-shares the encoded block, and each Aggregator queries the proof directly on its share of it.¶

2. flp.truncate is linear. Each Aggregator applies it to its share of every block, including the blocks whose shares sum to zero, and sums the results into its output share (Section 5.3). Prio3 relies on the same property when it truncates a measurement share (Section 7.2.2 of [VDAF]).¶

The FLP specified in Section 7.3 of [VDAF], FlpBBCGGI19, implements this interface for any validity circuit, so the requirements above restrict only the choice of circuit. Section 5.9 fixes the circuits for which this document defines a PREAMBLE instantiation.¶

The field flp.JOINT_RAND_LEN MAY be zero, as for a circuit such as Count that uses no joint randomness. As in Prio3 (Section 7.2.1 of [VDAF]), PREAMBLE then omits the joint randomness machinery altogether: the Clients derive no blinds, the Aggregators derive no joint randomness parts, and there is no joint randomness seed to cross-check. The proof is unaffected. It is still generated, secret-shared, and checked with flp.decide(), and flp.prove() and flp.query() are invoked with an empty joint randomness. Everything in this document that concerns joint randomness applies only when flp.JOINT_RAND_LEN > 0, and Section 5.2, Section 5.3, and Section 5.7 say what changes otherwise.¶

• TODO When flp.JOINT_RAND_LEN > 0, each part binds the nonce, the encoded public share, and the VDPF seed. The public share and the VDPF seed determine the Aggregator's share, so they take the place of the measurement share that Prio3's and Mastic's parts bind alongside the nonce. This document does not prove that binding them is equivalent, that is, that a Client cannot choose its shares after seeing the joint randomness.¶

PREAMBLE's implementation of the VDAF interface (Section 5 of [VDAF]) is specified in the following sections.¶

5.2. Sharding

The sharding algorithm takes the measurement, the report nonce, and sharding randomness of length RAND_SIZE, defined below. Its output is a public share, PreamblePublicShare, and a pair of input shares, PreambleInputShare, one for the Leader (Aggregator 0) and one for the Helper (Aggregator 1).¶

The sharding randomness is consumed as the VDPF's RAND_SIZE bytes (one initial seed per Aggregator; Table 5), followed by four more seeds: the Helper's proof-share seed, one joint-randomness blind per Aggregator, and one prove-randomness seed. If flp.JOINT_RAND_LEN == 0, the two blinds are omitted, leaving two more seeds. There is no measurement-share seed, because the FLP's encoded measurement is exactly the VDPF block, which the VDPF already secret-shares; the only secret a Client shares explicitly is the proof.¶

RAND_SIZE = (self.vdpf.RAND_SIZE
             + (1 + self.SHARES + 1) * self.xof.SEED_SIZE)
             # if flp.JOINT_RAND_LEN > 0

RAND_SIZE = (self.vdpf.RAND_SIZE
             + (1 + 1) * self.xof.SEED_SIZE)
             # if flp.JOINT_RAND_LEN == 0

5.3. Verification

1. Evaluate the VDPF share (Section 4.2) over all num_leaf_nodes * leaf_size coordinates to obtain the Aggregator's share of the encoded vector, along with one sparsity proof per leaf. Derive a one-hot check value by hashing the concatenation of those proofs, in leaf order, under the shared verify_key. The two Aggregators' proofs agree at every leaf exactly when at most one leaf is on-path, so verification rejects the report unless the two check values are equal.¶

2. Sum the encoded vector share block-wise to obtain the Aggregator's share of encoded_block, the FLP-encoded measurement produced by shard(). Separately, apply flp.truncate() to each block of the encoded vector share; the concatenation of the results is the Aggregator's output share.¶

3. If flp.JOINT_RAND_LEN > 0, recompute the Aggregator's own joint-randomness part from its blind, the nonce, the encoded public share, and its VDPF seed, exactly as shard() did. Combine it with the peer's part supplied in the public share to derive the corrected joint-randomness seed, and expand that into the joint randomness. The corrected seed is cross-checked against the verifier message in verify_next(), as in Section 7.2.2 of [VDAF]. Otherwise, there is no joint randomness, and the Aggregator uses an empty one in the next step.¶

4. For each of the PROOFS proofs, query the Aggregator's share of encoded_block and its share of that proof, obtaining a verifier share.¶

The Aggregators then exchange verifier shares, and verifier_shares_to_message() rejects the report if the one-hot check values differ or if flp.decide() fails on any combined verifier, and otherwise outputs the joint-randomness seed derived from both Aggregators' parts as the verifier message. If flp.JOINT_RAND_LEN == 0, there are no parts to combine, and the verifier message is empty.¶

def verifier_shares_to_message(
        self,
        ctx: bytes,
        agg_param: None,
        verifier_shares: list[PreambleVerifierShare[F]],
        ) -> PreambleVerifierMessage:
    assert len(verifier_shares) == self.SHARES
    (share_0, share_1) = verifier_shares
    if share_0.one_hot_check != share_1.one_hot_check:
        raise ValueError("One-hot check failed")

    # Unshard the verifier shares into the verifier message.
    verifiers = vec_add(share_0.verifiers_share,
                        share_1.verifiers_share)

    # Verify that each proof is well-formed and the input is valid.
    for _ in range(self.PROOFS):
        (verifier, verifiers) = front(
            self.flp.VERIFIER_LEN, verifiers)
        if not self.flp.decide(verifier):
            raise ValueError(
                "Decision function failed after combining all "
                "verifier shares.")

    if self.flp.JOINT_RAND_LEN == 0:
        return None

    # Combine the joint randomness parts computed by the Aggregators
    # into the true joint randomness seed, which is checked by all
    # Aggregators.
    (part_0, part_1) = (verifier_shares[0].joint_rand_part,
                        verifier_shares[1].joint_rand_part)
    if part_0 is None or part_1 is None:
        raise ValueError("expected joint randomness parts")
    return self.joint_rand_seed(ctx, [part_0, part_1])

5.4. Validity of Aggregation Parameters

PREAMBLE does not use an aggregation parameter. Every input share MUST be used only once:¶

def is_valid(self, agg_param, previous_agg_params):
    return len(previous_agg_params) == 0

5.5. Aggregation

An output share is this Aggregator's share of every block's aggregatable form: num_leaf_nodes consecutive groups of flp.OUTPUT_LEN field elements in all (Section 5).¶

Aggregating a set of output shares sums them element-wise:¶

def agg_init(self, agg_param: None) -> PreambleAggShare[F]:
    return self.field.zeros(self.output_len)

def agg_update(
        self,
        agg_param: None,
        agg_share: PreambleAggShare[F],
        out_share: PreambleOutputShare[F],
) -> PreambleAggShare[F]:
    return vec_add(agg_share, out_share)

def merge(
        self,
        agg_param: None,
        agg_shares: list[PreambleAggShare[F]],
) -> PreambleAggShare[F]:
    agg = self.agg_init(agg_param)
    for agg_share in agg_shares:
        agg = vec_add(agg, agg_share)
    return agg

def encode_agg_param(self, agg_param: None) -> bytes:
    return b""

5.6. Unsharding

To unshard, the Collector adds up the aggregate shares element-wise, then decodes each block's flp.OUTPUT_LEN field elements with the circuit that validated it, using the blocks() helper (Section 5.8) to split the flat aggregate into one slice per block. The result is one FLPResult per block, in block order:¶

def unshard(self,
            agg_param: None,
            agg_shares: list[PreambleAggShare[F]],
            num_measurements: int) -> PreambleAggResult[FLPResult]:
    agg = self.merge(agg_param, agg_shares)
    # The aggregate is one truncated block after another, and each
    # block is decoded by the circuit that validated it -- so the
    # result is one FLP aggregate result per block, in leaf
    # order.
    return [
        self.flp.decode(block, num_measurements)
        for block in self.blocks(agg, self.flp.OUTPUT_LEN)
    ]

5.7. Message Serialization

struct {
    uint8 seed_cw[KEY_SIZE];
    uint8 ctrl_bit_left;   /* MUST be 0 or 1 */
    uint8 ctrl_bit_right;  /* MUST be 0 or 1 */
} InternalCorrectionWord;

struct {
    InternalCorrectionWord internal_cws[depth];
    F leaf_cw[flp.MEAS_LEN];
    uint8 proof_cw[PROOF_SIZE];
} CorrectionWords;

struct {
    CorrectionWords cws;
    /* only if flp.JOINT_RAND_LEN > 0 */
    uint8 joint_rand_parts[2 * xof.SEED_SIZE];
} PreamblePublicShare;

def encode_correction_words(self, cws: CorrectionWords[F]) -> bytes:
    result = bytes()
    for internal_cw in cws.internal_cws:
        result += internal_cw.seed_cw
        result += byte(internal_cw.ctrl_bit_left)
        result += byte(internal_cw.ctrl_bit_right)
    result += self.field.encode_vec(cws.leaf_cw)
    result += cws.proof_cw
    return result

def correction_words_size(self) -> int:
    return (self.depth * (self.KEY_SIZE + 2) +
            self.field.ENCODED_SIZE * self.leaf_size +
            PROOF_SIZE)

def decode_correction_words(
        self, encoded: bytes) -> CorrectionWords[F]:
    if len(encoded) != self.correction_words_size():
        raise ValueError("correction words have incorrect length")
    internal_cws = []
    for _ in range(self.depth):
        (seed_cw, encoded) = front(self.KEY_SIZE, encoded)
        (ctrl_bits, encoded) = front(2, encoded)
        if any(b > 1 for b in ctrl_bits):
            raise ValueError("invalid control bit")
        internal_cws.append(InternalCorrectionWord(
            seed_cw, bool(ctrl_bits[0]), bool(ctrl_bits[1])))
    (leaf_bytes, encoded) = front(
        self.field.ENCODED_SIZE * self.leaf_size, encoded)
    leaf_cw = self.field.decode_vec(leaf_bytes)
    return CorrectionWords(internal_cws, leaf_cw, encoded)

struct {
    uint8 vdpf_seed[KEY_SIZE];
    F proof_share[flp.PROOF_LEN * PROOFS];
    /* only if flp.JOINT_RAND_LEN > 0 */
    uint8 joint_rand_blind[xof.SEED_SIZE];
} PreambleLeaderShare;

struct {
    uint8 vdpf_seed[KEY_SIZE];
    uint8 proof_share[xof.SEED_SIZE];
    /* only if flp.JOINT_RAND_LEN > 0 */
    uint8 joint_rand_blind[xof.SEED_SIZE];
} PreambleHelperShare;

struct {
    uint8 one_hot_check[PROOF_SIZE];
    F verifiers_share[flp.VERIFIER_LEN * PROOFS];
    /* only if flp.JOINT_RAND_LEN > 0 */
    uint8 joint_rand_part[xof.SEED_SIZE];
} PreambleVerifierShare;

/* only if flp.JOINT_RAND_LEN > 0 */
PreambleVerifierMessage = uint8[xof.SEED_SIZE]

agg_share = out_share = F[num_leaf_nodes * flp.OUTPUT_LEN];

5.8. Auxiliary

def blocks(self, vec: list[F], block_len: int) -> list[list[F]]:
    """
    Split a flat vector into one slice per block of the vector
    space, in leaf order.

    Both vectors Preamble handles have this shape: the encoded one
    that `vdpf.eval_all()` returns (`block_len == vdpf.leaf_size`)
    and the truncated one that is aggregated (`block_len ==
    flp.OUTPUT_LEN`).  Neither is typed as `list[list[F]]`, because a
    flat vector is what the wire encoding and `vec_add` want -- an
    output share is summed across Clients element-wise, and its block
    boundaries carry no information the shape doesn't already fix. So
    the boundaries live here instead, in one place, rather than as
    index arithmetic at each use.

    """
    expected = self.vdpf.num_leaf_nodes * block_len
    if len(vec) != expected:
        raise ValueError(
            f"expected {expected} field elements "
            f"({self.vdpf.num_leaf_nodes} blocks of {block_len}), "
            f"got {len(vec)}.")
    return [vec[i * block_len:(i + 1) * block_len]
            for i in range(self.vdpf.num_leaf_nodes)]

The joint randomness seed is derived from the Aggregators' parts as in Prio3 (Section 7.2.6 of [VDAF]), except that the domain separation tag is built with dst_alg() (Section 2.1):¶

def joint_rand_seed(self,
                    ctx: bytes,
                    joint_rand_parts: list[bytes]) -> bytes:
    """Derive the joint randomness seed from its parts."""
    return self.xof.derive_seed(
        zeros(self.xof.SEED_SIZE),
        dst_alg(USAGE_JOINT_RAND_SEED, self.ID, ctx),
        concat(joint_rand_parts),
    )

5.9. Variants

This section defines four instantiations of PREAMBLE. Each fixes the validity circuit wrapped by flp (Section 5.1) to one of the Prio3 circuits of Section 7.4 of [VDAF] or, for PreambleL1BoundSum, to the circuit of [Prio3L1BoundSum], and the XOF to XofTurboShake128 (Section 6.2.1 of [VDAF]). In PreambleMultihotCountVec, PreambleSumVec and PreambleL1BoundSum, block_size is the circuit's length parameter: the number of entries in the block content a Client submits, not the number of field elements that content encodes to. In PreambleCount, block_size is fixed to 1. Each instantiation has its own algorithm identifier, which feeds every domain separation tag (Section 2.1), including the VDPF's.¶

Like Prio3, each instantiation uses Field128 and a single proof.¶

8.1. Normative References

[Prio3L1BoundSum]

Thomson, M. and D. Cook, "A Prio Instantiation for Vector Sums with an L1 Norm Bound on Contributions", Work in Progress, Internet-Draft, draft-ietf-ppm-l1-bound-sum-02, 29 April 2026, <https://datatracker.ietf.org/doc/html/draft-ietf-ppm-l1-bound-sum-02>.

[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-18, 30 January 2026, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-18>.

8.2. Informative References

[BBCGGI19]

Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., and Y. Ishai, "Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs", CRYPTO 2019 , 2019, <https://ia.cr/2019/188>.

[DP22]

deCastro, L. and A. Polychroniadou, "Lightweight, Maliciously Secure Verifiable Function Secret Sharing", EUROCRYPT 2022 , 2022, <https://doi.org/10.1007/978-3-031-06944-4_6>.

[Mastic]

Davis, H., Mouris, D., Patton, C., and N. G. Tsoutsos, "The Mastic VDAF", Work in Progress, Internet-Draft, draft-mouris-cfrg-mastic-04, 23 January 2025, <https://datatracker.ietf.org/doc/html/draft-mouris-cfrg-mastic-04>.

[PINE]

Chen, J. and C. Patton, "Private Inexpensive Norm Enforcement (PINE) VDAF", Work in Progress, Internet-Draft, draft-chen-cfrg-vdaf-pine-02, 4 February 2025, <https://datatracker.ietf.org/doc/html/draft-chen-cfrg-vdaf-pine-02>.

[PREAMBLE]

Asi, H., Feldman, V., Keller, H., Rothblum, G., and K. Talwar, "PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors", 2025, <https://arxiv.org/abs/2503.11897>.