Is joint randomness optional
Closed this issue · 5 comments
The pseudo code in prio3 sharding(https://github.com/cfrg/draft-irtf-cfrg-vdaf/blob/main/draft-irtf-cfrg-vdaf.md#sharding) suggests joint randomness is optional, but the draft text never describes it that way.
Up to this point, the purpose of joint randomness is not specified yet (it is in the generic flp section later). How should people choose whether to use joint randomness or not? If the purpose is just for shortening the proof, then the text should compare proof size based on different Field size and soundness tolerance, and perhaps compare it with the case where joint randomness is not used.
For e.g. if I choose to NOT use joint randomness, and use Field32, do I essentially have a protocol similar to Prio2 with SNIP? Does it have a soundness error of 2^-32? If so then Prio3 with Field128 actually have a far bigger overall input share size compared to Prio2 with Field32, due to the 4x field size increase.
When clarifying this, we may want to explain that Prio3 produces a zero-knowledge proof over secret shared data by compiling either a fully linear probabilistically checkable proof (in the no-joint randomness case) or a 1.5-round public coin fully linear interactive oracle proof (in the joint randomness case). While the ultimate goal of the joint randomness is shorter proofs, the mechanism by which it achieves that is switching to an entirely different protocol topology, which enables new space-saving tricks in the proof circuit. I think whether to use joint randomness thus comes down to tradeoffs made when designing a new circuit.
When clarifying this, we may want to explain that Prio3 produces a zero-knowledge proof over secret shared data by compiling either a fully linear probabilistically checkable proof (in the no-joint randomness case) or a 1.5-round public coin fully linear interactive oracle proof (in the joint randomness case).
We already do explain this here: https://www.ietf.org/archive/id/draft-irtf-cfrg-vdaf-06.html#section-7.1-12
While the ultimate goal of the joint randomness is shorter proofs, the mechanism by which it achieves that is switching to an entirely different protocol topology, which enables new space-saving tricks in the proof circuit. I think whether to use joint randomness thus comes down to tradeoffs made when designing a new circuit.
Agreed, I'm working on a PR to explain this a bit more clearly.
Hmmm, looking at the text once more, it does seem like we try to explain how the joint randomness is intended to be used: https://www.ietf.org/archive/id/draft-irtf-cfrg-vdaf-06.html#section-7.3.1.1-2
@wangshan given this pointer, is there something else you'd like us to do here to make things more clear?
For what it's worth, @chris-wood's feedback on this section (#226) suggests it can do with rewrite. I suppose you'd advocate for the same thing?
Closing this as there doesn't seem to be any work to do here.