Flp: Let the circuit output be a vector?

[divergentdave]

While looking at #258, I was considering how one might implement the Prio2 or Prio3CountVec AFE while using Prio3 without joint randomness. No joint randomness means we can't use random linear combinations. Thus, I think we'd be left with taking the conjunction of multiple range check sub-circuits by raising each sub-circuit output to the power $p-1$, which would be pretty expensive. (I think you'd have to split the exponentiation into multiple gadgets for it to be feasible)

This conjunction could be avoided entirely if we let the circuit output a vector instead of a single field element, and require that it be equal to $\vec{0}$ instead of $0$. Circuits that take advantage of such a change would have a bigger verifier message, but it would give us more power/expressiveness without joint randomness.

I'm not sure if this change is actually worth making in the document, but I figure it would be a useful counterfactual in Prio2 vs. Prio3 benchmark conversations, and in the broader joint randomness discussion.

[cjpatton]

This seems like a reasonable change to me, but we need to spend some time thinking about how it impacts existing security analysis. At first blush I can't see how this would possibly be a problem.

I'm also slightly wary about feature creep. It's definitely worth including if it significantly improves performance for a concrete use case.

[junyechen1996]

I think having valid() return a vector, or using "verifier randomness" to perform reduction of multiple checks per #266 is for good practice, because it eliminates the need of specifically using joint randomness to perform reduction, if joint randomness doesn't have to be part of proof generation (e.g. joint randomness is still needed in the proof size reduction trick in Prio3SumVec, also mentioned in #266 ). Using the proposal in #266 is generally ok, except it introduces a small soundness error, if one does it carefully, i.e. chooses a randomness that is completely random and not known to prover. Returning a vector will not have such soundness error. But in either case, the goal should be to not let prover know how verifiers are verifying multiple checks in a particular FLP type, e.g. (1) whether verifiers are doing a reduction of multiple checks, and (2) what randomness verifiers use to perform reduction. However, currently in FLP interface, valid() requires a FLP to perform "some" reduction in order to return a single value, and the only randomness that is available is joint randomness, which prover has "some" control over. Logically, prover should just construct the proof for gadgets, and be done (theoretically it can always claim valid() return 0).

@divergentdave Regarding eliminating joint randomness specifically in Prio3SumVec, I think the current Histogram FLP type actually can accomplish this for 0/1 range check with polynomial x^2-x, with some tweaks, i.e. don't use joint randomness to perform reduction. (Obviously Prio3SumVec supports a more generic measurement type, which is a bit vector or sum vector, and Prio3Histogram supports one-hot vector, but 0/1 range check applies in both cases.)

Let's say the encoded measurement in Histogram is X, and len(X) = n.
From a code logic perspective, the heavy lifting logic is in call_gadget_on_vec_entries, which is called by Histogram.valid() function, and rnd is never fed into the gadget, so it won't be part of proof generation. So theoretically, prover can simply call g.call() on every vector entry and be done. The wire polynomial interpolation, and gadget polynomial construction will then be constructed by Flp.prove() method. So prover shouldn't need to know whether verifiers choose to do a reduction, and what randomness is used if a reduction is done.

Mathematically, I think there is only one "wire polynomial" here (arity=1), f, which is interpolated based on X (or secret shares of X for verifiers), and should have degree O(n), and prover obtains the gadget polynomial p, by feeding f as x into polynomial under verification: x^2 - x. The gadget polynomial allows each verifier to linearly evaluate its secret shares of X_i^2 - X_i, by evaluating gadget polynomial p at input i. Prover only passes verification, if verifiers sum up the secret shares for each index i, and all sums are 0.

Now to verify X_i^2-X_i for all i, verifier can either exchange secret shares for all i, as a vector per proposal of this issue, or exchange a reduction of all X_i^2 - X_i per issue #266 , with "verifier randomness". There is also an "one-hotness" property verified by Histogram.valid(), which verifiers can evaluate directly (since it's a degree-1 polynomial) and exchange the secret shares, or fold the one-hotness check into the reduction as well.

One can argue eliminating joint randomness here is (marginally?) more secure, because now prover doesn't need to know joint randomness. Per the current FLP architecture that Histogram is implemented based on, prover actually knows verifiers are not exactly checking X_i^2-X_i for all i, instead, they are verifying r_1 * (\sum_i r_0^i * (X_i^2 - X_i)) + r_1^2 * ((\sum_i X_i) - 1), where r_0 and r_1 are joint randomness, derived based on the PRG hash function that includes the secret shares of X in Prio3 types, which prover still has "some" control over. Prover can try to brute force and find out a r_0 and r_1 that makes verification return 0, and soundness error therefore increases per Theorem 1 of VDAF paper. If we eliminate joint randomness, we no longer have this attack surface, and therefore, can potentially reduce the field size used in Histogram today (it currently uses Field128). Proof size wise, I think Prio3Histogram is still more expensive than Prio2 though, 2 * ((n + 1).next_power_of_two() - 1) + 2 vs (n + 1).next_power_of_two() + 3 (taken from libprio-rs).

Another consideration on which approach we should take between this issue and #266 : if we try to tackle #177 in the future, I don't know yet which approach will accommodate an implementation for #177 better, because to do multiple proofs for a FLP that needs joint randomness, one needs the flexibility to evaluate valid() twice, with different gadget polynomials, or one has to reduce the outputs from multiple gadget polynomials with "verifier randomness" in #266.

@divergentdave @cjpatton What do you guys think?

[cjpatton]

I think having valid() return a vector, or using "verifier randomness" to perform reduction of multiple checks per #266 is for good practice, because it eliminates the need of specifically using joint randomness to perform reduction, if joint randomness doesn't have to be part of proof generation (e.g. joint randomness is still needed in the proof size reduction trick in Prio3SumVec, also mentioned in #266 ). Using the proposal in #266 is generally ok, except it introduces a small soundness error, if one does it carefully, i.e. chooses a randomness that is completely random and not known to prover.

It's true the soundness error goes up, but not by very much. If there are a constant number of checks, then the soundness error increase is constant as well, something like O(1/|F|). And users like Prio3 will have to take care to make sure the verifier randomness is produced securely (as they must do for the query randomness).

Another consideration on which approach we should take between this issue and #266 : if we try to tackle #177 in the future, I don't know yet which approach will accommodate an implementation for #177 better, because to do multiple proofs for a FLP that needs joint randomness, one needs the flexibility to evaluate valid() twice, with different gadget polynomials, or one has to reduce the outputs from multiple gadget polynomials with "verifier randomness" in #266.

I think that we'd get the benefit either way.

@divergentdave @cjpatton What do you guys think?

I think it's a good idea to make the circuit output a vector, as @divergentdave suggests, but I don't think increasing the size of the size of the verifier shares by N field elements is acceptable, in particular for circuits whose outputs are linear in the input length, as @junyechen1996 suggests.

Combining the two ideas, we could do something like this?

• Circuit.valid(input: Vec[Field], joint_rand: Vec[Field]) -> Vec[Field] called by both prover and verifier
• Circuit.valid_finish(intermediate_output: Vec[Field], verifier_rand: Vec[Field]) -> Field called by the verifier only on the output of valid()

[divergentdave]

We could borrow from #266, but fix the verifier-only valid_finish() part to always be a random linear combination using pseudorandom vectors derived from the verification key. Having an additional fully general circuit would complicate both security analysis and design of new types of circuits.

[cjpatton]

That sounds like a good idea! WDYT @junyechen1996?

[cjpatton]

So the current proposal would be:

1. Let valid() output a vector
2. Have the verifier check that the output vector is $\vec{0}$ by taking a random linear combination with verifier-generated randomness (probably just the query randomness)?

While at it, I want to suggest that we do away with the FlpGeneric thing and just say "this is how we instantiate Flp".

[junyechen1996]

I think it sounds good. For

Have the verifier check that the output vector is 0 by taking a random linear combination with verifier-generated randomness (probably just the query randomness)?

I think using query randomness here sounds good. I don’t see a particular reason to introduce another type of randomness.

[cjpatton]

Another question: Could/should Prio3Sum and Prio3Histogram be changed to drop joint rand in favor of query rand?

[junyechen1996]

Another question: Could/should Prio3Sum and Prio3Histogram be changed to drop joint rand in favor of query rand?

I don't see any downside of dropping joint randomness. Ideally we should avoid using joint randomness in verification if it's not used in proof generation. It doesn't seem like joint randomness is needed by Prio3Sum or Prio3Histogram in proof generation. But the current limitation is valid() function only has access to joint randomness, but I think it will be relaxed if this change takes place.

[divergentdave]

Prio3Sum and Prio3Histogram both use joint randomness in proof generation, it's passed in via the rnd argument of the call_gadget_on_vec_entries() function linked. When at least one joint randomness element is used in a circuit's definition, (see the figures for Histogram and Sum in the draft) this will always be the case, as the client needs it to produce the circuit output.

If the proposed change here were applied to these Prio3 instances, the valid() method would return a vector of field elements, and joint randomness could be removed from the circuit.

[cjpatton]

right, the suggestion is that we change the Histgram and Sum circuits so that the they don't use joint rand and instead do the reduction on the output of valid. I think this would work for both of these.

To be clear: I'm not suggesting we do away with joint rand altogether. Wherever a gadget input takes in the joint rand the prover will need to know the value that's used.

[junyechen1996]

Yes I should be clearer as well. Regarding

I don't see any downside of dropping joint randomness.

I meant if the type doesn't need joint randomness during proof generation like @cjpatton said, i.e. joint randomness is not fed into any gadget. I think neither Sum nor Histogram feeds joint randomness into gadgets, so I think using "verifier randomness" to perform reduction would be better since prover doesn't need to know joint randomness.

Joint randomness is still needed in SumVec, which uses the proof reduction trick with joint randomness feeding as inputs to gadgets.

[cjpatton]

I've spent some time thinking about this and I so no reason why this change would break anything. I'd only add one requirement: we need to document this in https://www.ietf.org/archive/id/draft-irtf-cfrg-vdaf-06.html#section-7.3.1.1 as an extension of the FLP from {{BBCGGI19}} so that it's clear to reviewers that we're doing something slightly different.

That said, I'm not aware of any Flp user that would benefit significantly from this change. Prio3Histogram was cited as an example where we could avoid Fiat-Shamir, but as of #284 we'll need to do it anyway. Prio3Sum would benefit a little, but it's already quite fast.

[cjpatton]

Are folks OK with punting this discussion until after the next draft? Or do we want it for draft-07? cc/ @junyechen1996

[junyechen1996]

I don't think there is any rush to implement this for draft-07.

[cjpatton]

This issue has been open for several months without much movement. Is there still interest in adding this feature to FLP?

I believe the only circuits for which we get savings are those for which joint randomness is not passed into a gadget and used only to reduce the outputs:

• This is TRUE for Prio3Sum. In fact, by removing joint randomness and changing the field from Field128 to Field64, we reduce the number of bits uploaded by the client (the public share and two input shares) from 1376 bytes to about 700. The number of bytes exchanged during preparation wouldn't change significantly. (Note that using the circuit as-is, but using Field64 and 2 proofs is about the same cost as with Field64 and 1 proof.)

• This is NOT TRUE for Prio3Histogram or Prio3SumVec. Though as @divergentdave points, for small vectors it may be worth dropping the ParallelSum trick in favor of something linear.

• I think this is currently NOT TRUE for PINE because the ParallelSum trick is applied to the wraparound tests. However if we take Optimization: Require all wraparound checks to pass junyechen1996/draft-chen-cfrg-vdaf-pine#60, then this may no longer be necessary.

[junyechen1996]

I think these all sound right. I'm not particularly worried about computing a random linear combination of multiple circuit outputs, which only increases soundness error by a negligible amount if field size is large. But if we use joint randomness to do this reduction, it complicates the security analysis a bit, because now client has control over this reduction.

Btw, I don't think this will be a breaking change for the wire format between client and server, assuming field size remains the same? If joint randomness is not used in proof generation, aggregators can just use their private randomness to reduce the circuit outputs. I believe all our VDAFs first generate joint randomness field elements used in proof generation, then generate more if they are needed to reduce circuit outputs. We can just avoid generating those joint randomness field elements for reducing circuit outputs?

[cjpatton]

I think these all sound right. I'm not particularly worried about computing a random linear combination of multiple circuit outputs, which only increases soundness error by a negligible amount if field size is large. But if we use joint randomness to do this reduction, it complicates the security analysis a bit, because now client has control over this reduction.

It complicates analysis insofar as we have to account for attacks on Fiat-Shamir, hence the larger field (or more proof). Did you have anything else in mind beyond this?

Btw, I don't think this will be a breaking change for the wire format between client and server, assuming field size remains the same?

I agree, we can make this change without breaking changes to existing circuits. That said, we may consider modifying existing circuits to make them ore efficient, such as Sum.

If joint randomness is not used in proof generation, aggregators can just use their private randomness to reduce the circuit outputs.

This should work:

• each aggregator $j$ chooses a random $r_j$ and broadcasts $[M]_j = v_0 + r_j \cdot [v_1]_j + r_j^2 \cdot [v_2]_j + \cdots$ where $[v_i]$ is its share of the $i$-th circuit output.
• to finish preparation, compute $M = [M]_1 + \cdots + [M]_S = v_0 + (r_1 + \cdots r_S) \cdot v_1 + (r_1^2 + \cdots r_S^2) \cdot v_2 + \cdots$ and check if $M=0$.

One problem is that we would like preparation to be de-randomized. To do this, we'd have each aggregator derive their verification randomness $r_j$ from the verification key, similar to how they derive the query randomness.

I would also simplify this further by having each aggregator compute a share of the same verification randomness $r$. We do this in the circuit with joint randomness by dividing by the number of shares $S$.

I believe all our VDAFs first generate joint randomness field elements used in proof generation, then generate more if they are needed to reduce circuit outputs. We can just avoid generating those joint randomness field elements for reducing circuit outputs?

We only generate joint randomness if Flp.JOINT_RAND_LEN > 0.

[junyechen1996]

Did you have anything else in mind beyond this?

Not really. Maybe if the circuit already needs joint randomness to do proof generation, using more joint randomness to reduce circuit outputs isn't a terrible thing..?

This should work:

I don't quite get this part. Shouldn't $r_j$ be agreed upon among aggregators? It should be like this?

• aggregators agree on a verification randomness $r$, derived from the verification key, similarly as query randomness.
• each aggregator j broadcasts $M_j = [v_0]_j + r * [v_1]_j + r^2 * [v_2]_j + ...$, where $[v_i]_j$ is aggregator $j$'s share of the i-th circuit output.
• to finish preparation among $S$ aggregators, compute $M=M_1 + ... + M_S = ([v_0]_1 + ... + [v_0]_S) + r * ([v_1]_1 + ... + [v_1]_S) + r^2 * ([v_2]_1 + ... + [v_2]_S) + ...$, and check if $M$ is 0.

[cjpatton]

Yeah that what I was suggesting here:

I would also simplify this further by having each aggregator compute a share of the same verification randomness $r$.

[cjpatton]

There's a PR up for extending FLP. I'm going to assume there's no appetite to modify the circuits for which we don't get any performance benefit. This leaves Prio3Sum as the only possible breaking change. I suggest we close this issue as completed once the PR lands and consider what to do with Prio3Sum in #306.

[cjpatton]

@junyechen1996 noted to me offline that this optimization doesn't help all that much with PINE.