Implement draft-irtf-cfrg-vdaf-13

[divergentdave]

Here's a summary of what we'll need to implement, based on the changelog.

• [x] Set up a new release branch for draft-08. Update the README, Dependabot, and cargo-vet configuration (to import from the main branch). (#1130)
• [x] Poplar1 is_valid() now checks that the current candidate prefixes are descendents of previous candidate prefixes. (draft-09)
• [x] Add Prio3MultiHotCountVec. (draft-10) (#1123)
• [x] FLP circuit output may be a vector. If so, it is reduced using query randomness. (draft-10) (#1132)
• [x] Poplar1: change handling of an edge case in the first round preparation message. (it's possible we may not need to do anything here) (draft-10)
• [x] Add an application context input, in addition to the nonce from the application. (draft-12) (#1145)
• [x] Prio3: Soundness improvement in places where we use the Schwartz-Zippel lemma, both reducing vectors inside various circuits and reducing the vector output of the circuit. (draft-12) (#1132)
• [ ] Prio3: Reuse one seed for the helper's measurement share and proof share (draft-12)
• [ ] Prio3Sum: Change the circuit to allow specifying a maximum measurement, instead of the number of bits, and remove the use of joint randomness (and change the field). (draft-12)
• [x] Prio3Histogram and Prio3MultihotCountVec: Move the last random linear combination of two values from inside the circuit (using joint randomness) to outside the circuit (using query randomness). (draft-12) (#1132)
• [ ] Add the application context string to XOF calls inside the IDPF as well. (draft-12)
• [ ] IDPF: Use XofTurboShake128 on the last level, instead of XofFixedKeyAes128. (draft-12)
• [ ] Changes to IDPF public share encoding and Poplar1 aggregation parameter encoding. Closes #508. (draft-12)
  • [ ] We should double check that all IdpfInput methods make sense when compared to new draft. (draft-12)
• [ ] Double the SEED_SIZE of XofTurboShake128, and allow variable-size seeds in the Xof trait. (draft-12)
• [ ] XofTurboShake128 and XofFixedKeyAes128: Change the length prefix for the domain separation tag from one to two bytes. (draft-12)
• [ ] All algorithm IDs were reassigned. (draft-12)
• [ ] Streaming aggregation: Add associated methods to produce a 'zero' AggregateShare. Closes #569. (draft-13)
• [ ] Update the VERSION constant in domain separation tags.

This will also be a good opportunity for other breaking changes we want to make.

[rozbb]

@divergentdave looking at the entry:

FLP circuit output may be a vector. If so, it is reduced using query randomness. (draft-10)

Is this already reflected in the code? Specifically in trait Type: https://github.com/divviup/libprio-rs/blob/d2fe428cadaf690a56a74f4c682f62326f959f06/src/flp.rs#L184-L190 The output is a single field element, rather than a vector, so this is already done. Am I missing something?

[divergentdave]

The fundamental difference is that we want to, for example, combine the range check and sum check values in the Histogram circuit via a random linear combination with query randomness values, rather joint randomness values. The way we've divided this up between abstraction layers in the spec is that we changed the circuit interface to return a vector of field elements, instead of a single field element, and then added the optional compression with query randomness values in the query algorithm of the FLP we define. (note that query randomness is passed to query(), but not passed into the validity circuit) Thus I think we should change the signature of Type::valid() to return a vector of field elements.

[rozbb]

Ah ok, will do

[rozbb]

Is there a nontrivial relation between VERIFIER_LEN and EVAL_OUTPUT_LEN? Here, there is 1 element added to the verifier list https://github.com/divviup/libprio-rs/blob/d2fe428cadaf690a56a74f4c682f62326f959f06/src/flp.rs#L446-L447 And later it is assumed that the number of eval elements is 1: https://github.com/divviup/libprio-rs/blob/d2fe428cadaf690a56a74f4c682f62326f959f06/src/flp.rs#L480-L491 This means that self.verifier_len() should probably be self.eval_output_len() + A where A is the sum of the gadget arities, rather than just 1 + A, right?

[divergentdave]

Here's the definition of verifier length in draft-10: https://www.ietf.org/archive/id/draft-irtf-cfrg-vdaf-10.html#figure-22. EVAL_OUTPUT_LEN does not affect the verifier length, because the query algorithm only uses one verifier field element to do a probabilistic check that the validity circuit output is the zero vector. See https://www.ietf.org/archive/id/draft-irtf-cfrg-vdaf-10.html#section-7.3.3.2-2.4.1 and https://www.ietf.org/archive/id/draft-irtf-cfrg-vdaf-10.html#section-7.3.3.2-3.

The overall breakdown of the verifier is one field element for the whole output vector, then for each gadget, as many field elements as the arity of the gadget for evaluations of the wire polynomials at a query randomness point, plus one more field element for the evaluation of the gadget polynomial at the same point. (so $1 + \sum_i{(A_i+1)}$)

[rozbb]

Ah, so to be clear: the thing to do here is to replace the verifier.push(validity) line with something that does a random dot product, and then pushes that to verifier, right?

[rozbb]

Poplar1: change handling of an edge case in the first round preparation message. (it's possible we may not need to do anything here) (draft-10)

I think you're right that this is moot. The prepare_next() function in the draft permits prep_msg to be None, but the Rust does not: https://github.com/divviup/libprio-rs/blob/a8e48e7548b4653ed85fab7bc4e51127611dc6ee/src/vdaf/poplar1.rs#L1167-L1172 where Poplar1PrepareMessage is: https://github.com/divviup/libprio-rs/blob/a8e48e7548b4653ed85fab7bc4e51127611dc6ee/src/vdaf/poplar1.rs#L512-L521

[rozbb]

Separate question: does the current codebase validate aggregation parameters at all? I'm trying to impl the draft-09 changes, but can't even find where the basic level replay check is done.

[divergentdave]

No, that isn't implemented at all currently. See #1133.

[rozbb]

Prio3: Soundness improvement in places where we use the Schwartz-Zippel lemma, both reducing vectors inside various circuits and reducing the vector output of the circuit. (draft-12)

Is there any change here outside of the FLP query specification?

[divergentdave]

Yes, we also changed circuits using the ParallelSum gadget to use more joint randomness values. They now use one new joint randomness value with each gadget call. This affected the SumVec, Histogram, and MultihotCountVec circuits. See cfrg/draft-irtf-cfrg-vdaf#436.

[rozbb]

Ok, in that case I think that subtask is completed. This is the valid() compression, and this is the parallel sum update

[rozbb]

Design question. I'm adding ctx strings to the codebase, and there are two big options here.

1. I could modify all the methods in Aggregator to accept ctx: &[u8] as an input. This would allow users to call different methods with different contexts. However, I suspect that that's really not the intended use case. So...
2. I could simply add a ctx field to everything that impls Aggregator, e.g., Prio3. So the trait would make no mention of ctx, but the constructors of aggregators would all require a ctx field.

If that's a fair description of the scenario, then I'm pro option 2. What do you think?

[branlwyd]

The only objection to #2 that I can think of: a DAP implementation might currently cache a VDAF instantiation keyed on the VDAF & parameters for cross-task use. Since the application context string used by DAP is task-specific, this implementation strategy would be disallowed if we took implementation strategy #2. That said, none of the DAP implementations I'm aware of do this, and all the VDAF instantiations I'm aware of are cheap enough to instantiate that I don't think we necessarily need to support this use-case.

Barring other objections, I like #2.

[rozbb]

Understood, that makes sense. Okay I’ll go with 2 for now.

[branlwyd]

Hmm, the collector's operation (roughly, calling Vdaf.unshard) does not use a context string; but if we moved the context string to the constructor, collector implementations would need to care about this parameter.

[rozbb]

Ah, yeah. And also thinking about it more, it seems that this ctx would be the only state that these structs carry, aside from num_shares. Maybe this isn’t ideal