Implement perfect zero-knowledge

[irakliyk]

Proofs currently generated by the library leak info. This is not an issue when the primary use case for proofs is succinctness (e.g. light client, signature aggregation), but this is not desirable for use cases which need to hide private data (e.g. anon token, hash pre-image). Ideally, we should have an option to enable perfect zero-knowledge for proofs.

This will require the following changes:

• Inject random values at the end of execution trace of each register.
• Combine composition polynomial with a random low-degree polynomial before running it through FRI protocol.
• Use salted Merkle commitment scheme for execution trace commitment.

[saholmes]

Is there any update on the status and plan to implement this? Curious as it looks like all items are specified but it seems to have not been assigned for a while now?

[irakliyk]

With #84 I think we have the first point more or less covered (i.e., we can inject random values at the end of the trace without affecting the design of AIR constraints too much).

The third point can probably be covered by generalizing Merkle trees to generic Vector commitments. Maybe that's something to include in the next release.

[Nashtare]

If at some point this feature is integrated to winterfell, will you consider also having constant-time arithmetic? I guess in the end it depends on the applications relying on this crate (private executions within a chain where it is needed VS L2 rollup where you'd only need provers to have the ZK feature), but the burden incurred by CT arithmetic is not negligible, hence my question :D

[irakliyk]

I think this would be interesting. I do wonder which parts need to be made constant-time. One obvious part is field arithmetic. This can be fairly easily done even now without effecting other parts of the system by providing a different implementation for a given field (e.g. f64ct). Assuming field arithmetic is constant-time, are there any other parts which need to be updated?

[Nashtare]

Else than constant-time arithmetic, I would think of constant-time branching / selectors. For the latter you have several crates doing this. The suble crate documentation explains how this is achieved (or at least tried to be achieved).
I believe blake / sha crates already implement these so that would need to be implemented for the Rescue instantiations, and probably many other places as well. Though there will always be a portion left to the end user, for instance when creating the execution trace, which may be even more critical, as dealing directly with the witness.

I'm not sure about the different implementation of fields, as the verifier doesn't need to use constant-time arithmetic, and hence would suffer unnecessary burden.

[Nashtare]

Also, do you see it as a non-optional feature? Or something passed as argument? (similarly to the custom proof options like grinding factor, extension size, ...?)

[Sean4572435243]

In the file
https://github.com/facebook/winterfell/blob/main/examples/src/rescue/mod.rs
on line 131

fn verify(&self, proof: StarkProof) -> Result<(), VerifierError> {
        let pub_inputs = PublicInputs {
            seed: self.seed,
            result: self.result,
        };
        winterfell::verify::<RescueAir, H>(proof, pub_inputs)
    }

I'm seeing the seed is required for the verify. Am I missing something? Where is the zero-knowledge aspect?

[Nashtare]

First, ZK is not implemented yet in winterfell.

Second, ZK doesn't mean there is no information at all about the statement we are proving. It means a verifier will not be able to retrieve any information they could not get from the public information already attached to the proof or present in the statement. Here, we want to convince a verifier that given an initial seed, and a hash chain length, the claimed final hash output is correct. Hence, proving is only used here for succinctness (the verifier does not have to compute the whole chain themselves).

[Sean4572435243]

Ok, I see. I was assuming because of the title of this thread that there was 'some' degree of zero-knowledge. I do understand the value of succinct verifications. Thanks for the response.