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