Inappropriate transcipt initiation

[krnak]

tl;dr: Crate does not enforce a transcript to be initiated with the circuit description. It follows that a circuit producer can manipulate circuit selectors to create a forged proof.

Problem description

If circuit description is not used to initiate a transcript, then the protocol is not sound, because a circuit producer can manipulate circuit selectors to forge a proof.

This would not be a problem for the Groth16, where the circuit production has to be trusted. However, Plonk belongs to the family of zk-SNARKs with so called universal setup, which means that some common reference string is fixed and then every (potentially untrusted) party can produce a circuit.

Currently, the crate does not enforce the transcript to be initiated with the circuit description. There exists a method for initiating the transcript appropriately (VerifierKey::seed_transcript), but a user of the crate is very unlikely to use it because of the current state of the crate API.

Proposed solution

• The transcript must be always initiated with a fingerprint of the circuit.
• The crate API must not allow user to skip transcript initialization.

Current state

There is no official documentation, how to use the crate. However, in Zprize 2023 assignment, the crate is used in this way:

1. A proving key and a verification key are computed using a "dummy circuit".

let (pk, (vk, _pi_pos)) =
    dummy_circuit.compile::<KZG10<Bls12_381>>(&pp).unwrap();

2. A proof is generated using a "real circuit".

let (proof, pi) =  real_circuit
    .gen_proof::<KZG10<Bls12_381>>(&pp, pk, b"Merkle tree")
    .unwrap()
};

Let me investigate Circuit::gen_proof:
2.1. Prover is initialized by Prover::new constructor

let mut prover = Prover::new(b"Merkle tree");

which sets

prover.preprocessed_transcript = Transcript::new(b"Merkle tree")

2.2 Constraints from the "dummy circuit" are cloned into the "real circuit".

self.gadget(prover.mut_cs())?;

2.3 Prover's key is set to the preprocessed key

prover.prover_key = Some(pk);

2.4. Prover is used to produce a proof

Ok((prover.prove(&ck)?, pi))

Since the prover.prover_key was set to Some(pk), prover.prove calls directly prove.prove_with_preprocessed. It follows that VerifierKey::seed_transcript was not called at all and prover.preprocessed_transcript remains set to Transcript::new(b"Merkle tree").

3. Proof is verified:

let verifier_data = VerifierData::new(vk, pi.clone());
let res = verify_proof::<Fr, EdwardsParameters, KZG10<Bls12_381>>(
    &pp,
    verifier_data.key.clone(),
    &proof,
    &verifier_data.pi,
    b"Merkle tree",
);

I.e. proof is verified with the Transcript::new(b"Merkle tree") transcript.

(See the full code here.)

To sum it up, circuit selectors were not used to initiate the transcript.

See also

#145