Overview

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.
figure
Example quadratic arithmetic program
figure
Connections betwe- en QAP coefficients and the right, left, and output functions
figure
Illustration of exponent multiplication showing how all terms combine to prove equality
figure
SNARK example code subroutine relationships
figure
Index generation for \(l_i\) coefficients
figure
Example table for root indexing
figure
Algorithm to compute Lagrange polynomial coefficients
figure
Matflat function operation
figure
Assignment of values for each record in QAP example
figure

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!!

FAQ

What is a zk-SNARK in this chapter’s context?A zk-SNARK is a succinct noninteractive argument of knowledge that also provides zero-knowledge, meaning it lets a prover demonstrate knowledge of a witness without revealing the witness itself.
What is the main idea behind a zero-knowledge proof?The prover shows they know something secret, while the verifier can become convinced of that fact without learning the secret. The chapter uses Ali Baba’s cave to illustrate this idea.
Why is Ali Baba’s cave a good example of zero knowledge?Because Paul can repeatedly prove he knows how to open the magic door, but Veronica never learns the secret itself. The chance of cheating successfully drops exponentially with repeated rounds.
What is a quadratic arithmetic program (QAP)?A QAP is the algebraic structure used to express the computation being proved in a SNARK. It uses wires and multiplication gates, and it links the public statement and private witness through polynomial equations.
What is the difference between the statement and the witness in a SNARK?The statement is the public input that everyone can see, while the witness is the private data known only to the prover. The proof shows the witness satisfies the QAP for that statement.
Why are Lagrange interpolant functions used in the QAP?They let each gate be represented by a polynomial that is 1 at one gate position and 0 at the others. This makes it possible to encode gate-specific constraints cleanly in polynomial form.
Why does the chapter introduce the polynomial t(x)?t(x) is the product of all gate roots. It is used so that cross terms can be absorbed into the term h(x)t(x), which helps enforce the QAP identity.
What is the purpose of the common reference string (CRS)?The CRS gives both prover and verifier shared public parameters needed for proof creation and verification. It is generated from secret “toxic waste” values that must never be exposed.
What do the points A, B, and C represent in the proof?They are the prover’s elliptic-curve proof elements built from the CRS, the witness, and randomizers r and s. Together they encode the proof that the witness satisfies the QAP.
How does the verifier check the proof?The verifier computes a point V from the public statement and CRS, then compares pairings involving A, B, C, and V. If the pairing equation holds, the record verifies; otherwise, it is rejected.

pro $24.99 per month

  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose one free eBook per month to keep
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime

lite $19.99 per month

  • access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more


Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free