The landing page says "the sponsor checks a proof and learns nothing else." This page
derives exactly what that proof is, made of, why checking it works, and why it can't
be faked. It uses the real circuit from this project
(circuits/eligibility.circom) as the running example.
A SNARK doesn't operate on "integers" the way a normal program does. Every value (age, a diagnosis code, a hash, the proof itself) is an element of a finite field \(\mathbb{F}_p\): the integers \(0\) through \(p-1\), where all addition and multiplication wraps around modulo a fixed prime \(p\).
This project uses the BN128 (also called BN254 / alt_bn128) curve, the same one Ethereum's precompiles support. Its scalar field modulus, the \(p\) every number in this system lives under, is:
That's roughly \(2.19 \times 10^{76}\), a 254-bit number. An
arithmetic circuit is a directed graph of only two gate types,
addition and multiplication, defined over this field. Circom is a language for describing
such circuits; when you compile eligibility.circom, every line
becomes some combination of \(+\) and \(\times\) gates wired
together.
The catch: a finite field has no built-in notion of "greater than." \(17 + 1 = 18\) wraps around just like any other addition. There's no sign, no ordering, nothing that says 18 is "less than" 65 in a way a circuit can directly test. Section 03 shows how the circuit fakes ordering using only \(+\) and \(\times\).
In ordinary integers mod 6, "dividing by 2" is impossible: no integer times 2 gives 1 mod 6, so 2 has no inverse. A prime modulus fixes this. When \(p\) is prime, every non-zero element \(a\) is coprime to \(p\), so by Bezout's theorem, there's always an integer \(b\) with \(ab \equiv 1 \pmod p\). That \(b\) is \(a^{-1}\). A concrete small example: in \(\mathbb{F}_{19}\), \(3^{-1} = 13\) because \(3 \times 13 = 39 = 2 \times 19 + 1 \equiv 1\).
Fermat's little theorem gives a formula that works for any prime \(p\): \(a^{-1} \equiv a^{p-2} \pmod p\). It follows from the fact that \(a^{p-1} \equiv 1 \pmod p\) for any non-zero \(a\), so \(a \cdot a^{p-2} = a^{p-1} = 1\). This is how division is computed inside the BN254 field, exponentiation with a huge exponent using repeated squaring, roughly 254 multiplications.
The BN254 prime is chosen specifically to match the scalar field of the BN128 elliptic curve, making the curve's group order and this field compatible. That compatibility is what makes the pairing in Section 05 possible. A different, arbitrary prime would break the pairing equation entirely.
A Rank-1 Constraint System represents the whole circuit as one big list of "witness" values and a set of multiplication constraints over them.
First, every signal in the circuit (inputs, outputs, and every intermediate value) gets stacked into one vector called the witness:
The leading \(1\) is a fixed constant wire (used to express plain constants).
\(x_1 \dots x_\ell\) are the public inputs: here, commitment
and target_code. Everything else (\(w_1 \dots w_{m-\ell}\))
is private: age, the 14 diagnosis code slots, consent, and every intermediate signal the
compiler generated.
The whole circuit is then just a list of \(n\) constraints. For each constraint \(j\), three fixed vectors \(a_j, b_j, c_j \in \mathbb{F}_p^{\,m+1}\) (chosen at compile time, baked into the circuit) must satisfy:
"\(a_j \cdot s\)" just means the dot product: pick out the relevant witness values, multiply each by its fixed coefficient, and add. So each constraint is: (some linear combination of wires) × (another linear combination) = (a third linear combination). That's it. The entire eligibility check, including the Poseidon hash, compiles down to a long list of constraints in exactly this shape.
A trivial example from this circuit, the consent check consent === 1,
becomes the constraint:
Here \(a_j\) picks out the consent wire, \(b_j\) and \(c_j\) are both the constant-1 wire. The only way this holds is consent = 1.
Suppose the witness has 3 entries: \(s = (1,\ \texttt{consent},\ \texttt{age})\)
at positions 0, 1, 2. For consent === 1:
\(a_j = (0, 1, 0)\) → \(a_j \cdot s = 0 \cdot 1 + 1 \cdot \texttt{consent} + 0 \cdot \texttt{age} = \texttt{consent}\)
\(b_j = (1, 0, 0)\) → \(b_j \cdot s = 1 \cdot 1 = 1\)
\(c_j = (1, 0, 0)\) → \(c_j \cdot s = 1\)
So the constraint \((a_j \cdot s)(b_j \cdot s) = (c_j \cdot s)\) becomes
\(\texttt{consent} \times 1 = 1\). Satisfied only when
consent = 1. The real circuit has hundreds of wire positions
(age, 14 code slots, lab value, 8 medication codes, public inputs, and hundreds of
intermediate signals), but every constraint is still just three sparse vectors dotted
with the same long witness.
The \(a_j, b_j, c_j\) coefficient vectors are fixed at compile time by
Circom and baked into the .r1cs file. The prover fills in the
actual witness values at proof time. "Satisfying the circuit" means finding a witness
\(s\) such that all \(n\) equations hold simultaneously. If
even one fails, no valid proof exists for that input.
Here's every rule in the real circuit, what it compiles to, and the trick used to make it work in a field with no native comparisons or boolean logic.
Normally, "is this person between 18 and 65?" means: read the number, compare it. Here, the verifier never gets the number at all, just a proof.
Think of it like a vending machine that only accepts exact change through a slot too small to see into. The patient's real age goes in on the prover's side. The circuit runs a fixed sequence of math steps on it, the same steps every time, written into the circuit ahead of time. Those steps are built so that they only come out "clean" (satisfy every equation) if the hidden number was actually between 18 and 65. Any other number makes at least one equation fail.
The proof the verifier receives basically says "I ran your fixed steps on some private number, and everything checked out," backed by the elliptic-curve math from Section 06 so the prover can't fake that result. The verifier confirms the steps were followed correctly without ever being told what the number was. The bit-by-bit breakdown below is how those steps are built so a yes/no range check is possible using only addition and multiplication.
Since \(\mathbb{F}_p\) has no "≥", the circuit first proves that
age is an 8-bit number by decomposing it into bits
\(b_0, \dots, b_7\) and constraining each one to be binary:
The second equation is the standard "bit" gadget: \(b(b-1)=0\) only holds
for \(b \in \{0,1\}\): one R1CS constraint per bit. Once age is known
to be an 8-bit number (0-255), the circuit computes
\(\texttt{age} - 18 + 256\), re-decomposes that into 9 bits, and
reads off bit 8 (the "did it overflow past 256" bit). If \(\texttt{age} \ge 18\),
the sum is \(\ge 256\) and bit 8 is 1, and that bit is the
"greater-or-equal" answer. .out === 1 forces that bit to be 1.
42 in 8-bit binary is 00101010
(\(32 + 8 + 2 = 42\)). Each bit is 0 or 1, so
\(b_i(b_i-1)=0\) holds for all 8. Now:
\(42 - 18 + 256 = 280\). In 9-bit binary, 280 is
100011000. Bit 8 (the leftmost) is 1, so
gte18.out = 1. Constraint satisfied.
Try age = 12 (should fail): \(12 - 18 + 256 = 250\). In 9-bit binary, 250 is 011111010. Bit 8 is 0. The constraint forces this bit to equal 1, so no valid witness exists and proof generation returns "not eligible." Crucially, the verifier never learns that it was the age check that failed, or what the age was, just that no valid proof could be made.
Mirror image of constraint 1: LessEqThan(8) computes
\(65 - \texttt{age} + 256\) and checks the overflow bit the same way.
Together, constraints 1 and 2 pin age to the integer range
\([18, 65]\), using only bit-decomposition and multiplication, the
only tools a finite field gives you.
The simplest constraint in the circuit: directly \((\texttt{consent})\cdot(1)=(1)\) as shown in Section 02. No range check needed since consent is already constrained to be a single field element that must literally equal 1.
IsEqual is itself a gadget, since "\(=\)" isn't a
native field operation either. For inputs \(x, y\), the circuit computes
\(d = x - y\) and needs a witness value \(d^{-1}\) (the
prover supplies \(0\) if \(d = 0\), otherwise the true modular
inverse). Two constraints enforce correctness:
If \(d=0\) (codes match): the first equation forces \(\texttt{out}=1\) (since \(d \cdot d^{-1}\) can be 0). If \(d \ne 0\): the second equation forces \(\texttt{out}=0\) because \(d \cdot d^{-1}=1\) for the true inverse. A dishonest prover can't fake this: supplying a wrong \(d^{-1}\) breaks one of the two equations.
The circuit runs this across all 14 diagnosis-code slots, sums the 14 binary
out values into match_sum_1, and uses
another GreaterEqThan gadget to require
\(\texttt{match\_sum\_1} \ge 1\): at least one slot equals
target_code.
A second required diagnosis code, checked with the exact same IsEqual /
running-sum gadget as constraint 4, just against target_code_2
and its own match_sum_2. Constraints 4 and 5 are two independent
\((\cdot)\cdot(1)=(1)\) equations that both have to hold, which is what gives
the AND: the patient's diagnosis list must contain both codes (e.g.
E11.9 and I10, a
comorbidity requirement), not just one.
The same bit-decomposition trick from constraints 1-2, run on
lab_value instead of age. The
difference is that the bounds aren't hardcoded: lab_min and
lab_max are public inputs supplied per trial
(e.g. HbA1c × 10, so "7.0%-10.0%" is lab_min=70,
lab_max=100). The verifier sees the range it's checking against,
but never the patient's actual lab value, only that it falls inside that range.
The mirror image of constraints 4 and 5: same IsEqual /
running-sum gadget over the 8 medication slots, but instead of requiring
\(\texttt{match\_sum} \ge 1\), this constraint requires the sum to be
exactly 0. None of the patient's medication codes may equal
excluded_med_code. For example, the patient must not be on
warfarin if the trial drug interacts with it. Padding unused medication slots with
\(0\) is safe here because excluded_med_code is
always a non-zero encoded ICD/medication code, so a padding slot can never accidentally
match it.
This is the constraint that ties the whole proof to one specific patient record.
commitment is a public input: the
verifier knows it (it's the value the hospital published when the patient record was
stored).
circomlib's Poseidon gadget tops out at 16 inputs per call, and
this circuit now has 25 private values to commit to (age + 14 codes + consent + lab_value
+ 8 medications), too many for one hash. So the commitment is built like a tiny
two-level Merkle tree: hasherA hashes the original 16 inputs
(age, codes, consent, unchanged from the first version of this circuit),
hasherB hashes the 9 new inputs (lab value + medications), and
hasherFinal hashes those two outputs together into the single
public commitment.
A prover who plugs in different values for any of the 25 private inputs,
even ones that would otherwise satisfy constraints 1-7, changes at least one
of hasherA.out / hasherB.out, which
changes hasherFinal.out, which breaks this constraint. Section 07
covers Poseidon itself.
In total: 3 range checks (≈18 constraints each for bit decomposition + comparison,
covering age and the lab value), 1 equality constraint (consent), 3 running-sum membership
checks over IsEqual gadgets (28 for the two required diagnosis
codes, 8 for the medication exclusion), and three Poseidon hashes: two 16/9-input
hashes plus a final 2-input hash combining them (Section 07 covers why Poseidon is cheap
enough to do this three times). Altogether the compiled circuit has on the order of a
thousand R1CS constraints, still small enough that proof generation takes well under
a second.
Checking hundreds of constraints one at a time inside a proof would be slow. The Quadratic Arithmetic Program (QAP) transformation turns "all \(n\) constraints hold" into a single polynomial divisibility test.
Pick \(n\) distinct points \(r_1, \dots, r_n \in \mathbb{F}_p\), one per constraint. For every wire \(i\) in the witness, use Lagrange interpolation to build three degree-\((n-1)\) polynomials \(u_i(x), v_i(x), w_i(x)\) such that:
i.e. evaluating \(u_i\) at point \(r_j\) recovers the coefficient that constraint \(j\) assigned to wire \(i\) in its \(a\) vector (similarly for \(v_i, w_i\) and the \(b\)/\(c\) vectors).
Given \(n\) points \((r_1, y_1), \dots, (r_n, y_n)\), Lagrange interpolation produces the unique polynomial of degree at most \(n-1\) that passes through all of them:
The product \(\prod_{k \ne j}\frac{x-r_k}{r_j-r_k}\) is called the \(j\)-th Lagrange basis polynomial. It equals 1 when \(x=r_j\) (because every factor becomes \(\frac{r_j-r_k}{r_j-r_k}=1\)) and equals 0 when \(x=r_k\) for any \(k \ne j\) (because one factor in the product is \(\frac{r_k-r_k}{r_j-r_k}=0\)). So the sum picks out exactly \(y_j\) at each \(r_j\) and nothing interferes.
Tiny worked example. Suppose we have 2 constraints and wire 1 carries some signal. Pick evaluation points \(r_1=1, r_2=2\). Say constraint 1 assigns coefficient \(a_{1,1}=3\) to wire 1, and constraint 2 assigns \(a_{2,1}=5\). We want \(u_1(x)\) such that \(u_1(1)=3\) and \(u_1(2)=5\). Lagrange gives:
Check: \(u_1(1)=2(1)+1=3\) and \(u_1(2)=2(2)+1=5\). The
polynomial correctly encodes the constraint coefficients at the matching evaluation point.
In the real circuit, this is done for every wire (hundreds of them) and every constraint
(\(n \approx 1000\)), producing degree-999 polynomials over
\(\mathbb{F}_p\). This computation runs once during snarkjs setup,
not at proof time, so the prover doesn't repeat it.
Given a witness assignment \(s = (a_0, a_1, \dots, a_m)\) (the actual numbers, this patient's age, codes, etc.), define:
By construction, \(A(r_j)B(r_j) - C(r_j) = 0\) for every \(j\) if and only if constraint \(j\) is satisfied by this witness. So the polynomial \(A(x)B(x) - C(x)\) has roots at every \(r_1, \dots, r_n\), meaning it's divisible by the vanishing polynomial:
The factor theorem says: a polynomial \(f(x)\) has a root at \(r\) (meaning \(f(r)=0\)) if and only if \((x-r)\) divides \(f(x)\). Applied \(n\) times: if \(f(r_1)=f(r_2)=\cdots=f(r_n)=0\), then \((x-r_1)(x-r_2)\cdots(x-r_n) = Z(x)\) divides \(f(x)\), meaning there exists a polynomial \(H(x)\) with \(f(x) = H(x)Z(x)\).
Apply this to \(f(x) = A(x)B(x)-C(x)\). By construction, \(f(r_j) = A(r_j)B(r_j)-C(r_j)\). Substituting the QAP polynomial definitions, this equals \((a_j \cdot s)(b_j \cdot s)-(c_j \cdot s)\), which is the \(j\)-th R1CS constraint's left-hand side minus right-hand side. So \(f(r_j)=0\) iff constraint \(j\) holds. If all \(n\) constraints hold, \(f\) has roots at all \(n\) evaluation points and \(Z(x)\) divides \(f(x)\). If any single constraint fails, \(f(r_j) \ne 0\) for some \(j\), so \(Z(x)\) does not divide \(f(x)\), and no valid quotient \(H(x)\) exists.
All n original constraints hold ⇔ there exists a polynomial \(H(x)\) such that:
This single equation is what Groth16 actually proves. By the Schwartz-Zippel lemma, two different polynomials of bounded degree agree at a random point with only negligible probability, so checking this identity at one secret evaluation point \(\tau\) is, for all practical purposes, as good as checking it everywhere. That single secret point \(\tau\) is exactly what the trusted setup generates.
Two distinct polynomials of degree \(d\) can agree at most \(d\) points. So if we pick a random \(\tau\) from a field of size \(p\), the probability that a wrong polynomial \(A'(x)B'(x)-C'(x) \ne H(x)Z(x)\) coincidentally agrees with the right one at \(\tau\) is at most \(d/p\).
Here, \(d \approx 2n \approx 2{,}000\) (degree of \(A(x)B(x)\)) and \(p \approx 2^{254}\). That's a false-positive probability of at most \(2{,}000 / 2^{254} \approx 2^{-243}\), smaller than the probability of randomly guessing a 243-bit key on the first try. Checking one point is computationally equivalent to checking everywhere.
The setup ceremony samples secret "toxic waste" values and encodes powers of them into elliptic curve points, so anyone can use them to build and check proofs, but no one can recover the secrets themselves.
An elliptic curve over \(\mathbb{F}_p\) is the set of points \((x, y)\) satisfying \(y^2 \equiv x^3 + b \pmod p\), plus a special "point at infinity" \(\mathcal{O}\) that acts as the identity. These points form a group under a geometric addition rule: to add two distinct points \(P\) and \(Q\), draw the line through them, find the third intersection with the curve, then reflect over the x-axis. Doubling a point uses the tangent line instead.
What makes this useful: adding a point \(G\) to itself \(x\) times (written \([x]G\) or \(xG\)) is scalar multiplication. Going forward is fast via double-and-add (about \(\log_2 x \approx 254\) steps). Going backward, given \([x]G\) and \(G\), finding \(x\) is the Elliptic Curve Discrete Logarithm Problem (ECDLP). No efficient algorithm for this is known, and the best attacks on BN128 require roughly \(2^{128}\) operations. Everything in Sections 05 and 06 is secure because of this gap.
BN128 uses two separate curve groups \(G_1\) and \(G_2\) (over different field extensions) plus a target group \(G_T\). The groups have the same prime order \(p\) as the scalar field from Section 01, which is why the QAP polynomials and the curve arithmetic live in the same universe.
Groth16 works over a pairing, a function \(e: G_1 \times G_2 \to G_T\) between three groups derived from the BN128 elliptic curve, with the property \(e([x]_1, [y]_2) = e([1]_1,[1]_2)^{xy}\) for any field elements \(x, y\). Notation: \([x]_1\) means "the point you get by adding the \(G_1\) generator to itself \(x\) times," meaning \(x\) is encoded "in the exponent." Given \([x]_1\), recovering \(x\) requires solving the elliptic curve discrete log problem, believed to be computationally infeasible.
"Bilinear" means linear in both arguments: \(e([a]_1, [b]_2) = e([1]_1, [1]_2)^{ab}\). This lets you "multiply in the exponent." Normally, given only \([A]_1\) and \([B]_2\) as curve points, there's no way to compute \(AB\) as a scalar (that would be breaking discrete log). But the pairing computes \(e([A]_1, [B]_2)\) and the result in \(G_T\) encodes \(AB\) as an exponent, without revealing it. This is the one mathematical trick that makes zk-SNARK verification possible: the verifier can check multiplicative relationships between secret values through their curve-point encodings.
The setup samples five random field elements and never reveals them. This is the "toxic waste":
It then publishes a proving key and verification key
containing only curve points, never the raw values. The verification key for this
project's circuit (in build/verification_key.json) literally
contains:
The 3 IC points correspond to the constant-1 wire plus this
circuit's two public signals (commitment and
target_code), matching \(n_{\text{public}}=2\).
Each IC\(_i\) is the curve point
\([(\beta u_i(\tau) + \alpha v_i(\tau) + w_i(\tau))/\gamma]_1\): the
QAP polynomials for wire \(i\), evaluated at the secret \(\tau\),
combined with \(\alpha, \beta, \gamma\), all "in the exponent."
Note: this worked example uses the original, smaller version of the
circuit (\(n_{\text{public}}=2\)) to keep the numbers readable. The live
circuit in Section 03 has grown to six public signals
(commitment, target_code,
target_code_2, lab_min,
lab_max, excluded_med_code), so
\(n_{\text{public}}=6\) and IC has 7 points
instead of 3. The mechanism is identical: just one more
\([(\beta u_i(\tau) + \alpha v_i(\tau) + w_i(\tau))/\gamma]_1\) term per
extra public signal, so the rest of this walkthrough still applies unchanged.
The proving key additionally contains \([u_i(\tau)]_1, [v_i(\tau)]_2\) for every wire, and \([\tau^k Z(\tau)/\delta]_1\) for the powers needed to encode \(H(\tau)\). If \(\tau, \alpha, \beta, \gamma, \delta\) are genuinely destroyed after this step, nobody, including the people who ran the ceremony, can forge a proof for a false statement. This is why a production deployment needs an audited, multi-party trusted setup (this project uses a single-machine development setup, fine for testing, not for real patient data).
In a multi-party ceremony, many independent participants each contribute their own random secret \(\tau_i\). The final toxic waste is the product (or some combination) of all contributions, so the attacker would need to know every single participant's secret to reconstruct it. As long as at least one participant honestly destroys their piece and never reveals it, the combined \(\tau\) is unknown to anyone, including the ceremony organizers.
Real-world examples: the Zcash Sapling ceremony had 90 participants; the Hermez Powers of Tau ceremony had over 175. An attacker would need to compromise all of them retroactively. This is why the ceremony's participant list and their attestations are public record, so anyone can verify that enough independent, geographically distributed people participated to make collusion implausible.
The prover knows the full witness \(s=(a_0,\dots,a_m)\), including age, diagnosis codes, and consent. It picks two fresh random blinding values \(r, s \xleftarrow{\$} \mathbb{F}_p\) (different \(s\) from the witness vector, an unfortunate notation collision that's standard in the literature) and computes three group elements:
\(B_1\) is the same linear combination as \(B\) but computed in \(G_1\) instead of \(G_2\) (needed because \(C\) lives in \(G_1\)). The \(r, s\) blinding terms are what make the proof zero-knowledge: they randomize \(A, B, C\) so that the same witness produces a different-looking proof every time, with no residual information about \(a_i\) leaking through.
Without blinding, running the prover twice with the same patient record produces identical \(A, B, C\) points every time. An observer who sees multiple proofs for the same commitment could correlate them, or use algebraic relationships between the point values to narrow down possible witness values.
With fresh random \(r, s\): \(A\) is shifted by \(r[\delta]_1\), \(B\) by \(s[\delta]_2\), and \(C\) is adjusted by a compensating combination that keeps the pairing equation satisfied. The \(\delta\) terms cancel algebraically in the verification equation, but because the verifier never knows \(r\) or \(s\), the resulting \((A, B, C)\) triple looks uniformly random. The simulator argument (Section 08) formalizes this: a simulator who knows only the public parameters can produce triples that are statistically indistinguishable from real proofs, without knowing any private witness values.
The proof is just \(\pi = (A, B, C)\): two \(G_1\) points (64 bytes each, uncompressed) and one \(G_2\) point (128 bytes), about 256 bytes total, regardless of how large or complex the original circuit was.
The verifier has the verification key and the two public inputs
\(a_0=1, a_1=\)commitment,
\(a_2=\)target_code. It computes one
combined point:
Then it checks one pairing equation:
This is precisely snarkjs.groth16.verify(vkey, public_signals, proof)
in verifier/app.js. Algebraically, this equation holds
if and only if \(A(\tau)B(\tau) - C(\tau) = H(\tau)Z(\tau)\) for
the witness encoded inside \(A, B, C\), meaning if and only if
every one of the original R1CS constraints (age range, code match, consent, Poseidon
commitment) is satisfied.
Crucially, the verifier never sees \(\tau\), \(a_i\), \(r\), \(s\), or \(H(x)\), only three curve points and the result of one equation: true or false. Pairing checks on BN128 take a few milliseconds, independent of circuit size. This is why verification is fast even though the underlying circuit has hundreds of constraints.
Substituting the formulas for \(A\), \(B\), and \(C\) into the pairing equation and using bilinearity, the left side \(e(A,B)\) expands to \(e([1]_1,[1]_2)^{A(\tau)\cdot B(\tau)}\) (roughly, with the blinding terms included). The right side expands to match when \(A(\tau)B(\tau)-C(\tau) = H(\tau)Z(\tau)\), which is exactly the QAP identity from Section 04.
The \(\alpha, \beta\) terms in \(e([\alpha]_1,[\beta]_2)\) account for the \([\alpha]_1\) and \([\beta]_2\) added to \(A\) and \(B\) during proof generation. The \(\gamma\) term isolates the public-wire contribution (the IC sum) and the \(\delta\) term handles the private-wire contribution through \(C\). Together, these prevent a cheating prover from combining parts of different valid proofs (a "malleability" attack), because mixing in a different \(C\) would break the \(\delta\) balance.
The commitment that binds a proof to one patient record is a Poseidon hash, not SHA-256. Here's why that choice matters.
SHA-256 is built from bitwise operations (AND, OR, XOR, bit rotations) that are cheap on a normal CPU but expensive inside an arithmetic circuit, where every operation must be expressed as \(+\) and \(\times\) over \(\mathbb{F}_p\). A single SHA-256 call can cost on the order of 20,000-30,000 R1CS constraints. Poseidon is designed from scratch to be "circuit-friendly": it uses only field addition, field multiplication, and one nonlinear step, getting a 16-input hash down to a few hundred constraints.
To see why, count constraints per operation. Field addition is free (it's just wiring, no multiplication needed, so 0 constraints). Field multiplication costs 1 constraint (it's directly one R1CS equation). A single \(x^5\) evaluation costs 3 multiplications: compute \(x^2 = x \cdot x\), then \(x^4 = x^2 \cdot x^2\), then \(x^5 = x^4 \cdot x\). Compare XOR: to express "XOR on 32-bit words" in the field, you first decompose both operands into 32 bits (64 range-check constraints), XOR each bit pair (32 more), and reconstruct the result (32 more), totaling roughly 130 constraints for one 32-bit XOR. SHA-256 uses thousands of them. This is why the constraint count difference is so dramatic.
Poseidon is a sponge construction built around a fixed permutation \(P\) applied to a state vector of \(t\) field elements (\(t = \) number of inputs + 1, so \(t=17\) for a 16-input call). This circuit calls Poseidon three times with three different \(t\) values (17, 10, and 3; see constraint 8 in Section 03), but it's the same permutation each time, just sized to the input count. The permutation alternates two operations over \(R\) rounds:
A sponge has two phases. In the absorb phase: load the first block of inputs into the "rate" portion of the state (all positions except a reserved "capacity" element), apply the full permutation \(P\), repeat until all input is absorbed. In the squeeze phase: read output elements from the rate portion of the state.
For Poseidon as used here: with \(t=17\), 16 input values fill positions 0-15 (the rate) and position 16 (the capacity) starts at zero and is never directly loaded. After one application of \(P\), position 0 of the state is the hash output. The capacity element, the one slot never directly written, is what provides security: to find two different inputs producing the same hash, an attacker would need to also control the capacity element's state after the permutation, which requires inverting \(P\), believed to be infeasible.
Add a different fixed constant to each state element, derived from the circuit's parameters. These constants are public and the same for every hash. They exist purely to break symmetry between rounds.
The only nonlinear step. Full rounds apply \(x^5\) to every element of the state; partial rounds (used for most of the permutation, for efficiency) apply it to only the first element. The exponent 5 is chosen because \(\gcd(5, p-1)=1\) for the BN254 scalar field, which makes \(x \mapsto x^5\) a bijection (no collisions introduced) while needing only 3 multiplications per evaluation (\(x^2, x^4, x^5\)).
After the S-box, a MixLayer multiplies the entire state vector by a fixed \(t \times t\) MDS (Maximum Distance Separable) matrix, a linear step that spreads each element's influence across the whole state, similar in spirit to the diffusion layer in AES:
An MDS matrix is one where every square submatrix is invertible. In practice, this means every output element depends on every input element, and changing any single input changes every output. This provides full diffusion: after one MixLayer step, a single changed input value has propagated to all \(t\) state positions, so the nonlinearity from the S-box has been mixed everywhere.
Poseidon alternates nonlinear S-box steps (which prevent algebraic attacks from linearizing the permutation) with linear MixLayer steps (which spread that nonlinearity across the state). This is the same design principle as AES: SubBytes for nonlinearity (confusion), MixColumns for diffusion. Without diffusion, an attacker could attack the permutation one "column" at a time. Without confusion, a linear algebraic attack would work. Both are required.
Why partial rounds: applying \(x^5\) to all \(t\) elements every round is expensive (3 constraints per element per round). Poseidon applies the full nonlinear S-box to all elements only in the first and last few rounds (full rounds), and applies it only to the first state element in the middle rounds (partial rounds). The MixLayer after each partial round still propagates that single nonlinear update across all positions, so the security margin is preserved while the total constraint count drops significantly.
The number of full vs. partial rounds is chosen (per the Poseidon paper) to give a
128-bit security margin against known algebraic attacks (interpolation, Gröbner basis,
statistical attacks) for the given \(t\). circomlib's Poseidon(16)
implements this with parameters from the reference Poseidon specification.
What this buys the protocol: when the record is first stored, the prover commits to
\(\texttt{hasherA} = \mathrm{Poseidon}(\texttt{age}, \texttt{codes}[0..13], \texttt{consent})\)
and \(\texttt{hasherB} = \mathrm{Poseidon}(\texttt{lab\_value}, \texttt{meds}[0..7])\),
then \(\texttt{commitment} = \mathrm{Poseidon}(\texttt{hasherA}, \texttt{hasherB})\),
a small two-level tree, needed because circomlib's Poseidon
gadget caps out at 16 inputs and this record has 25 private values to commit to. Every
later proof must reproduce that exact three-hash chain from the private values it's using,
so a proof is cryptographically tied to one specific, previously-committed record,
not just "some values that happen to satisfy the rules."
Every zk-SNARK is judged against three definitions. Here's what each one means mathematically, and what it means for this specific system.
\( \forall \) witnesses \(s\) satisfying the R1CS, an honest prover's \(\pi\) is accepted with probability 1.
If a patient genuinely is 18-65, has the right diagnosis code, and consented, and the hospital's server runs the real circuit honestly, the proof always verifies as eligible. No false negatives from the cryptography itself.
\( \forall \) PPT provers, \(\Pr[\text{verifier accepts} \mid \text{no valid witness exists}] \approx \mathrm{negl}(\lambda)\)
"PPT" means probabilistic polynomial time: any realistic computer. If no age/codes/
consent combination would actually satisfy the circuit and hash to the public
commitment, no one, not even a malicious hospital,
can produce a proof that verifies, except with probability so small it's
treated as zero. This relies on the elliptic curve discrete log assumption on BN128
and an honestly-run trusted setup.
\( \exists \) a simulator \(S\) s.t. \(S(\text{public inputs})\) is indistinguishable from a real proof, without seeing the witness.
A simulator that doesn't know the patient's age, codes, or consent can produce something statistically identical to a real proof. So whatever the verifier learns from a real proof, it could have "learned" from nothing, meaning the proof itself carries zero information about the private values, beyond the single bit "eligible: true."
Put together: the prover can't lie (soundness), the system never wrongly rejects a true eligible patient (completeness), and the sponsor's verifier provably learns nothing about the patient beyond the eligibility result (zero-knowledge). The honest caveats are the ones already listed on the main page: trusted setup integrity, key management, and real EHR integration. None of these are weaknesses in the math itself, but in how it's deployed.
Regular soundness says a cheating prover can't make the verifier accept a false statement. Knowledge soundness is strictly stronger: it requires that a "knowledge extractor" algorithm exists, which, given a prover that produces valid proofs, can efficiently extract the actual witness from that prover (by running it multiple times with different random inputs if needed). In other words, if a prover consistently convinces the verifier, it must actually "know" a valid witness, not just stumble into one by coincidence.
For this circuit: knowledge soundness says any algorithm that consistently outputs a
valid proof for a given commitment must know the actual age,
diagnosis codes, lab value, medications, and consent that hash to that commitment.
Without knowledge soundness, a prover might forge a proof without knowing a valid
patient record, which would be catastrophic for this application.
A function \(f(\lambda)\) is negligible if it shrinks faster than any inverse polynomial: for every constant \(c\), \(f(\lambda) < \lambda^{-c}\) for large enough \(\lambda\). The security parameter \(\lambda = 128\) bits in this system.
Concretely: "negligible probability of forging a proof" means the probability is below \(2^{-128}\) for any realistic adversary. For reference: randomly guessing a 128-bit key succeeds with probability \(2^{-128}\); there are roughly \(2^{33}\) seconds in 250 years; and the fastest known algorithms for ECDLP on BN128 require approximately \(2^{128}\) operations. At \(10^{18}\) operations per second (a billion computers at a billion operations per second), running \(2^{128}\) operations would take about \(10^{20}\) years, roughly 10 billion times the age of the universe.
Zero-knowledge is proven by constructing a simulator: an algorithm
that, given only the public inputs (the verification key and public signals like
commitment), produces proof triples \((A, B, C)\)
indistinguishable from real proofs, without ever seeing the witness (age, codes, etc.).
The simulator exists in the Groth16 scheme because the blinding factors \(r, s\) effectively make each proof a fresh random-looking triple. The simulator picks its own random \((A, B, C)\) and adjusts them to satisfy the pairing equation directly (it can do this because it knows the trapdoor from the trusted setup). A real verifier cannot distinguish the simulator's outputs from a real prover's outputs.
The implication: whatever the verifier computes from the proof, it could have computed from the simulator's output alone, without any patient data. So the verifier gains zero information about the patient beyond "eligible: true."