status: draft · date: 2026-10-24 · question (owner): zippel answers "is this IOP complete" by Gröbner bases; do we become dependent on it? such checks are routine while developing — can we do it in eidos, and how do we guarantee soundness?
1. the picture
A proof system is three statements, and each has a different kind of proof:
| statement | kind | proved by |
|---|---|---|
| completeness: an honest run is accepted | a polynomial identity over the field, after substituting the prover's definitions and the relation | normalisation — a ring decision procedure; with hypotheses, a Nullstellensatz certificate checked by ring |
| soundness of the IOP: a false claim passes with probability ≤ ε | a counting theorem over the field: Schwartz–Zippel per round, degree bounds, a union bound | a library of lemmas about polynomials over F and one short theorem per protocol |
| soundness of the argument: binding of the commitment, Fiat–Shamir | reductions to named assumptions (hemera as a random oracle, the code's distance) | paper proofs of the reductions, conformance of the parameters; never "guaranteed", only made explicit |
zippel covers the first row by searching an ideal membership with Gröbner bases, and a fragment of the third (special soundness for protocols with a witness). The search is the expensive part; the certificate it finds is cheap to check. That is the whole design below: search anywhere, check in eidos.
2. dependency, answered
We depend on zippel for nothing in the stack and for one thing in the workflow: the oracle that says "complete" in 43 ms (zheng_spartan_fixed with ark-gb, 804 ms with Singular — the experiment). The protocol files are ours (zheng/specs/proto), the discipline — one choreography, the transcript derived from it — is ours to keep, and the verdict can be re-derived by any Gröbner engine (Singular today) or, after this proposal, checked by eidos from a certificate. So zippel is a tool like a SAT solver: replaceable, never trusted for truth once the certificate is checked at home.
3. the moves
3.1 protocols as eidos terms
An inductive Protocol in eidos: instance and witness types over F, a list of moves (send e, challenge, check e), with expressions as terms over F. prover, verifier and transcript are functions of the term — the projection zippel does by reachability becomes two definitions by recursion over the moves. transcript.rs is then generated from the same term (the absorb/squeeze order, the domain tags), which is the one way to make "the transcript is derived, not maintained" true in our code.
3.2 ring by reflection — the tactic eidos needs anyway
Completeness of a protocol term is ∀ x w c, R x w → accepts (verifier x c (prover x w c)) = true. After unfolding, each check is an equation between two polynomials in the free variables; without hypotheses the two sides normalise to the same canonical form. The tactic: a normaliser written as an eidos function over a reflected polynomial syntax, proven correct once (eval (normalise p) = eval p), applied by decide on the canonical forms. This is the standard proof by reflection; every field-arithmetic fact in cyber (hemera's rounds, the CCS encodings, the economy's fixed point) needs the same tactic, so it is not special to protocols.
With hypotheses (the relation a·b = c, or a verifier check from an earlier round), completeness is ideal membership: goal g = Σ hᵢ·qᵢ. The qᵢ are the certificate; the search for them is Gröbner (zippel, Singular, or our own later); the check is ring on g − Σ hᵢ·qᵢ = 0. Certificate size is small for everything in zheng/specs/proto (the ideals have tens of generators).
3.3 soundness of the IOP in eidos
The library: polynomials over F as lists of coefficients, degree, the root bound (a nonzero polynomial of degree d has at most d roots — a counting theorem, provable by induction), the multivariate Schwartz–Zippel, probabilities as counting over a finite challenge space (no measure theory: Pr is a ratio of counts over Fⁿ). The protocol theorem: if the verifier accepts and the claim is false, then in some round the sent polynomial differs from the true partial sum, and the next challenge is a root of their difference; the union over rounds gives ε ≤ Σ dᵢ / |F|. For SuperSpartan: the outer zero-check bound (the eq(τ,·) step), the batching with γ, and the inner sumcheck compose by the same union bound. This has been done in other assistants (sumcheck in Lean's ArkLib and in Isabelle); the shape is known, the size is thousands of lines of library and hundreds per protocol.
What this gives: a machine-checked ε for the IOP with oracle access to ẑ, which is exactly the statement zippel cannot make for us.
3.4 the argument: assumptions, named
The IOP becomes an argument through the lens (Brakedown now, WHIR in the family) and Fiat–Shamir with hemera. Neither is a field identity; both are reductions:
- the lens: binding and the proximity gap of the code, parameters checked by the lens's own vectors; the statement we rely on is written down with its constants (
lens/specs), not re-proved here; - Fiat–Shamir: round-by-round soundness of the IOP (which 3.3 gives, with the state-restoration argument) plus hemera modelled as a random oracle; the derived transcript guarantees the binding of every message and of the instance by construction, which is the condition the attacks on weak Fiat–Shamir exploit.
So "guarantee" means: every assumption has a name and a constant, every step between two assumptions is a theorem in eidos or a reduction in a paper we cite, and the executable spec is the thing the theorems are about.
3.5 implementation = spec
The theorems are about the protocol term, not about rs/src/spartan. The bridge today: the term and the Rust agree on every conformance vector and on the derived transcript. The bridge later: the verifier runs as a nox program and eidos reasons about that program (the kernel is already a nox program), closing the gap between "the spec is sound" and "the binary is sound". Until then the gap is explicit and tested, not hidden.
4. order
- eidos: reflected polynomial syntax +
ringby reflection, with its correctness theorem — the first decision procedure inspecs/tactics.mdbeyondomega/simp. Blocks everything else, serves everything else. - eidos:
Protocolterms, prover/verifier/transcript by recursion, the completeness statement; portzheng/specs/prototo terms; completeness ofzheng_inner,zheng_outer,zheng_spartan_fixedbyring(+ Nullstellensatz certificates searched by zippel/Singular, checked byring).transcript.rsgenerated from the term. - eidos: the polynomial library and the sumcheck soundness theorem; then SuperSpartan's bound.
- zheng: the gate switches from "zippel says complete" to "eidos checks the certificate"; zippel stays as a search engine and as a second opinion.
- the argument layer: the assumption page (lens constants, hemera as random oracle, the round-by-round condition) with the reductions cited; the nox verifier and its proof are the phase after.
5. acceptance
ringproves(a+b)² = a²+2ab+b²and the hemera round identities in eidos; the normaliser's correctness theorem is in the kernel's trusted output, not assumed;- completeness of the three protocols is an eidos certificate checked by the kernel, and the planted bug (
zheng_bug) has no certificate — the search fails and noringproof exists; - the sumcheck soundness theorem states ε ≤ Σ dᵢ/|F| and is accepted by the kernel; instantiated at Goldilocks and the zheng sizes it reproduces the bound on
specs/superspartan.md; transcript.rsis a generated file with the protocol term as its single source.
related: zippel · the experiment · eidos · the proven present