The Use of IPA in Nova
Inner Product Argument (IPA) in Nova
Nova uses an Inner Product Argument (IPA), which uses Pedersen commitments. It does not need a trusted setup and its security is based on the discrete log problem (DLP). IPA is different from other common commitment schemes, such as KZG, which uses elliptic curve pairings and needs a trusted setup. For proof sizes and verification times, KZG is better since an IPA with Pedersen commitments needs linear work by the verifier, with proof size depending on the input (KZGβs proof and verification time are fixed). However, we can fix these weaknesses in systems like Halo.
An instance (that is, the public variables) for a committed relaxed R1CS is given by π₯, the public input and output variables, π’ and the commitments to πΈ, πππ(πΈ) and πππ(π€). We can put these in the tuple (π₯, πππ(π€), πππ(πΈ), π’). The instance is met by a witness (secret variables) (πΈ, ππΈ, π€, ππ€) if
where π§ = (π€, π₯, π’). Namely, the witness meets the instance if the public variables πππ(πΈ) and πππ(π€) are really the commitments to the private variables πΈ, π€ using randomness ππΈ, ππ€, respectively and they follow the relaxed R1CS equations.
The Folding Protocol
The prover and verifier can see two cases of relaxed R1CS, (π₯1, πππ(π€1), πππ(πΈ1), π’1) and (π₯2, πππ(π€2), πππ(πΈ2), π’2). Also, the prover has (πΈ1, ππΈ1, π€1, ππ€1) and (πΈ2, ππΈ2, π€2, ππ€2).
Fiat-Shamir method can be used to make the folding protocol presented above noninteractive. With this method, we can do IVC by updating the parameters after folding. The prover can then use a zkSNARK to prove that he has indeed the valid witness (πΈ, ππΈ, π€, ππ€) for the committed relaxed R1CS in ZK without revealing its value.
Last updated