Split squared norm equality check into a separate FLP

[albertpl]

This implements #53.

[albertpl]

I suppose we need thorough security review on this approach. The intuition is that eval_norm_check doesn't depend on joint randomness. Although we still use joint randomness to combine results of all sub-circuits, the degree of the joint randomness doesn't change. So this won't make it easy to guess the joint randomness (if the guess is uniformly distributed)?

[junyechen1996]

This like it adds a flag to make the squared norm equality and range checks optional? That's not quite what we need.

The circuit checks for five properties, as shown here:

https://github.com/junyechen1996/draft-chen-cfrg-vdaf-pine/blob/f06d5344b0b9879d678e9b5ea01878b9a899dd9c/poc/flp_pine.py#L230-L234

We always need to check all five of these properties: it's not acceptable to skip the squared norm equality or range check under any circumstances.

The idea behind #53 is that that we can split out the squared norm equality check into its own circuit. We would then generate FLPs for two circuits: one for the squared norm equality check and another for all the other checks. This saves us computation because the squared norm equality check can be done without joint randomness, so we only need to generate one proof for it.

Agreed. The current interface for PineValid makes it seem like norm equality check is optional. I think we should have one Valid circuit that just does the squared norm equality check which doesn't need joint randomness, something like PineValidSquaredNormEqualityCheck, and another Valid circuit that computes all other checks that require joint randomness, something like PineValidOtherChecks..?

[albertpl]

Let me double confirm.

• FLP1: squared norm equality check
• FLP2: all the other checks

In the context of multiple proofs, we will produce 1 proof for FLP1 and num_proofs proofs for FLP2. Both FLPs are consisted of ParallelSum gadget. These proofs are then concatenated.

[cjpatton]

Confirmed! Note you'll need to rebase this PR.

[albertpl]

Still WIP.
I will be out of office for the rest of the week. So plan to get it ready for review early next week.

[cjpatton]

Thanks @albertpl, this is heading in the right direction :)

[albertpl]

Rewrite this PR. May need more polishing but I want to collect feedback to make sure I am on the right track. Pls take another look.

[albertpl]

It seems like the pattern you want to follow is: PineValid implements the functionality shared by both circuits, then sub-classes implement the circuit-specific functionality. This pattern might make sense, but as it is, I think base class PineValid is doing too much: Not all parameters set by the constructor are relevant to both circuits The base class includes the sub-circuits that are used by PineValidOtherChecks but not by PineValidSquaredNormEqualityCheck The base class includes encoding routines that are not relevant to both I'd like to see a cleaner separation of the two circuits.

• I relocated all the evaluation sub-circuits.
• but the encoding routines are shared by both circuits such that both can be used individually.
• most of parameters are shared by both too. One reason is that we initialize them together, with dependencies on each other. Two initialization of these parameters would be a little bit tricky? Lots of the parameters are used by the shared routines as well, e.g. unpack_encoded_measurement.