19 Proving knowledge and keeping secrets: Zero knowledge using pairings
This chapter introduces zk-SNARKs as a practical way to prove that a statement is true without revealing the secret witness behind it. It begins with the classic idea of zero knowledge through an interactive puzzle, then moves to the noninteractive setting where the proof is built from elliptic curve arithmetic and pairings. The core motivation is to let a prover demonstrate knowledge of hidden information while keeping that information private, even when the verifier can check the proof with high confidence.
The mathematical foundation is a quadratic arithmetic program, which turns a computation into a set of wire values and multiplication constraints. Lagrange interpolating polynomials are used to encode gate behavior so that the correct values satisfy a polynomial identity, while incorrect values break it. The chapter also explains how cross terms and the vanishing polynomial are used to absorb all the unwanted mixed products into an auxiliary term, making it possible to validate a computation over many gates without exposing the witness itself.
To turn the theory into a usable protocol, the chapter builds a common reference string containing carefully structured elliptic curve points derived from hidden trapdoor values. The prover combines this CRS with public statement values, private witness values, and fresh randomness to create proof points, and the verifier checks them with Tate pairings. The code walkthrough shows how the QAP, CRS, proof generation, and verification steps fit together, ending with a complete example where a record can be verified successfully while the sensitive patient data remains concealed.
Ali Baba’s cave illustrates the concept of zero-knowledge proof. The prover knows a secret and the verifier wants them to prove they know it, but the verifier doesn’t need to know the secret themselves.
Example quadratic arithmetic program
Connections betwe- en QAP coefficients and the right, left, and output functions
Illustration of exponent multiplication showing how all terms combine to prove equality
SNARK example code subroutine relationships
Index generation for \(l_i\) coefficients
Example table for root indexing
Algorithm to compute Lagrange polynomial coefficients
Matflat function operation
Assignment of values for each record in QAP example
Summary
- A zero-knowledge proof convinces a verifier that a prover knows a secret without divulging the secret. This is useful in financial and medical environments where amounts or ailments are not an issue for access to private information.
- Ali Baba’s cave is an interactive zero-knowledge proof. The first zero-knowledge cryptographic algorithms were interactive.
- Succinct noninteractive arguments of knowledge (SNARKs) are a noninteractive proof of knowledge. This eliminates the communication problems associated with interactive proofs.
- A quadratic arithmetic program (QAP) consists of sums and multiplications, with each multiply being a gate. It forms the basis for a noninteractive proof of knowledge.
- Each gate in a QAP is represented as a unique prime in the torsion field of a pairing-friendly curve. The unique prime allows the construction of functions which replicate the gate equation when a prime for that gate is the input to the QAP.
- Left, right, and output functions to each gate are Lagrange interpolant functions, which are 1 at a specific gate and 0 at all other gates. Every equation of the QAP can then be verified as having correct inputs or rejected by not being equal as required by the QAP.
- Inputs and outputs to gates are called wires. They must have values modulo the torsion field size. The values are specific for each record being verified.
- Output functions are squared to match the input left and right multiples to form the QAP. The QAP will not verify without this difference between inputs and outputs.
- The cross terms \(h(x)\) are formed by removing all squared terms in the fundamental QAP formula: \[h(x)t(x)=Σ_{i=1}^{m}a_i v_i(x)·Σ_{i=0}^{m}a_i w_i(x) -Σ_{i=0}^{m}a_i y_i(x)\]
- \(t(x)\) is the product \[t(x)=\prod_{j=0}^{n-1}(x-r_j)\]
where \(r_j\) are the primes for each gate. - To compute a proof, all Lagrange functions are multiplied out to find the coefficients of each power \(x^i\). This reduces the size of the common reference string (CRS).
- The CRS is created with random values which must be lost. These are called toxic waste in the literature. An adversary could create a proof using arbitrary inputs if these values became known.
- Public wires are called statement variables, and secret wires are called witness variables. The verifier only knows public information. The prover knows both public and secret information. The proof of knowledge will fail if any of the values do not satisfy the QAP formulas. This is why the verifier can trust the prover does know all the information.
- The prover knows both statement and witness values. The prover creates a proof for a statement using these values with the CRS. The prover also uses two random values to prevent information from leaking through multiple records. In this way, every record is a unique proof.
- The verifier only knows the statement values. The verifier uses the CRS and proof points to verify or reject a proof. The verifier’s task is much easier than the prover’s task because they only compute four pairing values for each record. The difference in difficulty is the essence of the SNARK concept to help ensure security.
- A SNARK is a Boojum!!
Elliptic Curve Cryptography for Developers ebook for free