Open Antonio95 opened 10 months ago
Thanks for the different proposals. I think that compared to 1 & 2, option 3 is a no-go. I agree that option 2. is the most user-friendly and the least error prone.
After some more thought, I've noticed the following: in the potential correction of Hyrax to match its hiding nature, the commitment to the evaluation would be included in the proof (there is no other place for it). However, on a semantic level, this is a distinguished field: the entire point of the scheme is that the verifier learns that that commitment is a commitment to the correct evaluation. In a way, this makes it as important as the evaluation in the non-hiding case, which perhaps means it should be either a separate argument, or be obtainable from the proof structure at the trait level (not by digging into it separately for each implementor, which might not even be possible).
Any ideas for whether this should be done, and if so, how? Some possibilities
I donno all the commitment schemes, but one pattern would be you make the commitment and opening proof normally, but output additional metadata for the zk opener. You then have a separate interface that transforms the opening proof and zk metadata into the zk opening proof.
An example of this metadata would be that a groth16 prover gives you (A,B,C) with B on G_2, but you need the copy of B on G_1 to rerandomize the groth16, which usually the groth16 prover only uses internally. Caulk works similarly, their B = [tau]_2 - x [1]_2
term in G_2 needs a [tau_1]_1 - x [1]_1
term in G_2 if you want to produce multiple identical but unlinkable openings.
We termed these preprove
and reprove
in our ring vrf + zk continuations paper, so preprove
would be roughly the existing trait, but adding the zk metadata, while reprove
would be another trait that uses the zk metadata to make the opening proof zk.
In general, you'll have extra glue proofs that your commencement gets opened in the right place too, which requires custom work from the user, so likely this metadata contains elements not required by the reprove
trait that adds zk, but which helps make the final thing sound. In particular, Caulk contains a correctness proof for the evaluation point, but this becomes unnecessary if your evaluation point gets constrained in another way.
Problem Definition
In many PCSs, a prover commits to a polynomial and is subsequently queried about the value of that committed polynomial at a point chosen by the verifier - letting the verifier learn that actual value during the process.
However, this is not the case for all PCSs: sometimes, the verifier just wants to be convinced that a committed polynomial, at a point of their choice, takes a value the prover only commits to without revealing it in plain. This is, for instance, the case of Hyrax (cf. section 6 here), which is currently PRed (see #130). It is not unthinkable that more such schemes will be added as the module grows.
The current
PolynomialCommitment
trait does not handle that situation very elegantly - in particular, the methodcheck
receives a list of expected evaluations. How Hyrax was patched to fit this paradigm is outlined in the linked PR.Proposal
Three possible ways forward come to mind:
check
method simply disregard the received evaluations in evaluation-hiding PCSs. This seems inelegant and might lead to misuse where the programmer passes a certain evaluation to that function, receives positive confirmation, and thinks those evaluations were matched against the proof and correspond to evaluations of the committed polynomial. This issue could be mitigated with good documentation.check
by anOption
wrapper around that. Each implementor, depending of which of the two paradigms it fits, would panic if it receives the opposite of what it expects and otherwise run business as usual. By what it expects I meanSome
for PCSs where evaluations are meant to be learnt by the verifier andNone
for evaluation-hiding ones. This change would indeed be breaking but the changes would be minimal.evaluation_hiding
flag inside the current trait. Here I don't have many specific proposals, but I am up for discussion. A point in favour of this is that evaluation-hiding PCSs pay a performance cost due to their nature and the plug-out-plug-in design aim of thePolynomialCommitment
trait in its current form would put them in the same bag as non-hiding PCSs.At this moment, the second option seems the most appealing. I am happy to explore other possibilities, though.
For Admin Use