Support for evaluation-hiding PCSs

[Antonio95]

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 method check 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:

• Leave the trait untouched and have the 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.
• Small-impact breaking change: replace the evaluations (which are elements of a finite field) passed to check by an Option 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 mean Some for PCSs where evaluations are meant to be learnt by the verifier and None for evaluation-hiding ones. This change would indeed be breaking but the changes would be minimal.
• Larger refactor: a separate trait could be added for those schemes, or perhaps an 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 the PolynomialCommitment 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

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[mmagician]

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.

[Antonio95]

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

• Letting it go for now, which I'd be okay with.
• Changing the evaluations argument to an implementor of a new trait, which would represent an evaluation or a commitment to one. This sounds tricky and more involved in terms of refactors, but also better.

[burdges]

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.