Implement draft-irtf-cfrg-vdaf-13

[divergentdave]

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

• Set up a new release branch for draft-08. Update the README, Dependabot, and cargo-vet configuration (to import from the main branch). (Setup for new release branch #1130)
• Poplar1 is_valid() now checks that the current candidate prefixes are descendents of previous candidate prefixes. (draft-09)
• Add Prio3MultiHotCountVec. (draft-10) (Implement Prio3MutlihotCountVec #1123)
• FLP circuit output may be a vector. If so, it is reduced using query randomness. (draft-10) (Make FLP Eval Return Vec<F> rather than a single F #1132)
• 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)
• Add an application context input, in addition to the nonce from the application. (draft-12) (Add context string to VDAF #1145)
• 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) (Make FLP Eval Return Vec<F> rather than a single F #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) (Added max_measurement field to Prio3Sum type #1150)
• 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) (Make FLP Eval Return Vec<F> rather than a single F #1132)
• Add the application context string to XOF calls inside the IDPF as well. (draft-12) (Added ctx string to DPF computation #1146)
• IDPF: Use XofTurboShake128 on the last level, instead of XofFixedKeyAes128. (draft-12)
• Changes to IDPF public share encoding and Poplar1 aggregation parameter encoding. Closes IDPF/Poplar1: Revisit use of bitvec::prelude::Lsb0 order #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) (partially done in Added ctx string to DPF computation #1146)
• All algorithm IDs were reassigned. (draft-12) (Update constants #1152)
• Streaming aggregation: Add associated methods to produce a 'zero' AggregateShare. Closes Expose method to retrieve AggregateShare identity element #569. (draft-13)
• Update the VERSION constant in domain separation tags. (Update constants #1152)

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:

libprio-rs/src/flp.rs

Lines 184 to 190 in d2fe428

	fn valid(
	&self,
	gadgets: &mut Vec<Box<dyn Gadget<Self::Field>>>,
	input: &[Self::Field],
	joint_rand: &[Self::Field],
	num_shares: usize,
	) -> Result<Self::Field, FlpError>;

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

libprio-rs/src/flp.rs

Lines 446 to 447 in d2fe428

	let validity = self.valid(&mut shims, input, joint_rand, num_shares)?;
	verifier.push(validity);

And later it is assumed that the number of eval elements is 1:

libprio-rs/src/flp.rs

Lines 480 to 491 in d2fe428

	if verifier.len() != self.verifier_len() {
	return Err(FlpError::Decide(format!(
	"unexpected verifier length: got {}; want {}",
	verifier.len(),
	self.verifier_len()
	)));
	}
	// Check if the output of the circuit is 0.
	if verifier[0] != Self::Field::zero() {
	return Ok(false);
	}

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:

libprio-rs/src/vdaf/poplar1.rs

Lines 1167 to 1172 in a8e48e7

	fn prepare_next(
	&self,
	state: Poplar1PrepareState,
	msg: Poplar1PrepareMessage,
	) -> Result<PrepareTransition<Self, SEED_SIZE, 16>, VdafError> {
	match (state.0, msg.0) {

where Poplar1PrepareMessage is:

libprio-rs/src/vdaf/poplar1.rs

Lines 512 to 521 in a8e48e7

	/// Poplar1 preparation message.
	#[derive(Clone, Debug, PartialEq, Eq)]
	pub struct Poplar1PrepareMessage(PrepareMessageVariant);
	#[derive(Clone, Debug, PartialEq, Eq)]
	enum PrepareMessageVariant {
	SketchInner([Field64; 3]),
	SketchLeaf([Field255; 3]),
	Done,
	}

[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