Commit-and-Prove Marlin

[weikengchen]

This issue is just to remark a useful variant of Marlin with the property of commit-and-prove. Basically, the verifier does not know the input but instead obtains a commitment of the input. Later, separately, the prover may open the commitment.

Based on the diagram, it seems the main change is as follows:

• The prover sends a polynomial commitment of x and the evaluation of x on challenge \beta.
• The prover changes the corresponding opening information of the outer sumcheck.
• The verifier changes the outer sumcheck and changes the PC check for this outer sumcheck.

This variant can be a fork or a configuration option. The constraints PR would add an option for recursive, which commits the vanishing polynomials. This could be a separate option.

More discussion on commit-and-prove SNARK can be found in https://eprint.iacr.org/2019/142.

[weikengchen]

Note that the option is not a simple bool. It may be more appropriate as a usize, as for the hiding bound needed for the commitments, since the prover may want to open the polynomial many times.

The AHP would "consume" one hiding.

[Pratyush]

It's actually even a commit-and-prove SNARK wrt the witness

[weikengchen]

It is already a commit-and-prove SNARK wrt the witness.

[weikengchen]

It is now implemented in a separate branch: https://github.com/arkworks-rs/marlin/tree/commit-and-prove
Note that this branch should not be merged, since it only supports commit-and-prove, not the general use.

I guess we will leave it there for a moment.

[Pratyush]

We can merge this into masster, maybe by introducing a prove_committed and verify_committed API. Maybe these APIs should go into ark-snark as part of a new trait?