Protocol Primer

This page gives a conceptual map of the Longfellow ZK proof system for readers who are already comfortable with ZK terminology. Its goal is to orient you before you read the full IETF draft spec .

What Longfellow Is

Longfellow is a succinct non-interactive zero-knowledge argument (SNARG) that proves, for a given arithmetic circuit $C$ and public input $x$, that a prover knows a private witness $w$ such that $C(x, w) = 0$ — without revealing $w$.

Its design sits in a specific corner of the ZK landscape:

• No trusted setup, no common reference string. The scheme is instantiated entirely from a collision-resistant hash function (SHA-256 in the standard profile) and requires no other complexity-theoretic assumption.
• Interactive Oracle Proof (IOP) model. Longfellow is a member of the class of hash-based IOP schemes, placing it alongside systems like STARK and Ligero. This rules out pairing-based systems (Groth16, PLONK) but gives it straightforward trust assumptions.
• MPC-in-the-head + sumcheck. The system combines two components: the Ligero commitment scheme (based on the MPC-in-the-head paradigm) and a verifiable computation protocol based on the sumcheck protocol. These are described below.

The Three Building Blocks

The three components of Longfellow stack in the following way:

The Encrypted Sumcheck protocol produces an encrypted proof that the circuit was evaluated correctly. It also produces a set of linear and quadratic constraints that encode the relationship between the private inputs, the one-time pad, and the sumcheck transcript. The Ligero commitment scheme then proves those constraints are satisfied, using a witness committed in a Merkle-tree-backed tableau. The Fiat-Shamir transform replaces every verifier challenge in both sub-protocols with a hash-derived value, collapsing the interaction into a single message from prover to verifier.

Fiat-Shamir Transform

Because Longfellow’s underlying protocol is interactive, it uses the Fiat-Shamir transform to produce a non-interactive proof. The core mechanism is a transcript object parameterized by a hash function H (SHA-256 in the standard profile).

Writing to the transcript. Every prover message is appended to an internal string $\mathsf{tr}$ via transcript.write(msg). Three message types are supported: a single field element, a byte array, and an array of field elements. Each type is prefixed with a distinct byte designator and, where variable-length, a little-endian 8-byte length, so that every transcript string is uniquely decodable back to a protocol transcript.

Generating challenges. After a write, the transcript hashes the accumulated $\mathsf{tr}$ to produce a seed, then constructs a Fiat-Shamir Pseudo-random Function (FSPRF) object. The FSPRF is an infinite byte stream built from AES-256 in counter mode: block $i$ of the stream is $\mathrm{AES256}(\mathsf{seed},\ \mathrm{LE128}(i))$. The transcript exposes methods like generate_nat(m), generate_nats_wo_replacement(m, n), and generate_field_element(F) that consume bytes from this stream via rejection sampling, producing the verifier’s challenges.

First-message hardening. The first prover message receives special treatment to defend against a known correlation-intractability attack. After appending the prover’s first message, the transcript additionally appends: (1) the circuit identifier, (2) the serialized public input and output, and (3) a zero-byte string of length equal to the circuit’s quadratic term count (circuit.nterms()). This ordering and padding ensures it is computationally infeasible for a circuit with that many quadratic terms to compute the hash of a string whose random prefix is longer than that count.

Ligero Commitment Scheme

Ligero provides a commitment scheme and a method for proving linear and quadratic constraints on a committed witness vector $W$ in zero knowledge. In Longfellow, it plays the role of verifying that the encrypted sumcheck transcript was constructed honestly.

The Tableau

The prover builds a two-dimensional matrix $T$ of size $\mathtt{NROW} \times \mathtt{NCOL}$, called the tableau, by interleaving random padding rows with rows derived from the witness. Every row is the polynomial extension (via the extend function) of a shorter seed array:

The commitment is the root of a Merkle tree whose leaves are hashes of columns $\mathtt{DBLOCK} \ldots \mathtt{NCOL}$ of $T$. Revealing a column reveals a polynomial evaluation at a point outside the “message” region, enabling a low-degree test.

Key parameters

Constraint proofs

Linear constraints are given as sparse triples $(c, j, k)$ meaning constraint $c$ involves witness index $j$ with coefficient $k$, and a target vector $b$ such that $A \cdot W = b$.

Quadratic constraints are triples $(x, y, z)$ meaning $W[x] \cdot W[y] = W[z]$. These are handled by copying witnesses into the Qx, Qy, Qz rows and reducing to additional linear consistency constraints.

The Ligero prove procedure computes three sub-proofs from the tableau — a low-degree test (ldt), a dot-product proof (dot), and a quadratic proof (qpr) — writes them to the Fiat-Shamir transcript, then opens $\mathtt{NREQ}$ randomly chosen columns of $T$ together with a Merkle batch inclusion proof.

The Ligero verify procedure reconstructs the same random challenges, recomputes the inner-product vector from the linear and quadratic constraints, and checks four conditions: Merkle consistency, low-degree consistency, dot-product consistency, and quadratic consistency.

Encrypted Sumcheck Protocol

Layered circuits and the quad representation

Longfellow operates on layered arithmetic circuits. A circuit with $\mathtt{NL}$ layers is represented by wire arrays $V[0]$ (outputs) through $V[\mathtt{NL}]$ (inputs). Each layer $j$ is defined by a sparse three-dimensional array $Q[j][g, l, r]$:

An additional sparse array $Z[j]$ encodes in-circuit assertions — quadratic combinations of wires that must equal zero. The two are merged into a single combined quad $QZ = Q + \beta \cdot Z$ using a random verifier challenge $\beta$, keeping the representation compact.

The one-time pad

The standard sumcheck prover sends plaintext polynomial evaluations. Longfellow’s prover instead encrypts every field element in the sumcheck transcript by subtracting a randomly chosen one-time pad value before sending it. The pad is structured: for each layer and each sumcheck round, the pad assigns values to the $p_0$ and $p_2$ evaluations of the degree-2 polynomials, and to the per-layer claim values $v_l$ and $v_r$ (plus their product $v_l \cdot v_r$).

The verifier never sees the plaintext sumcheck transcript. It receives only the differences.

Deferred verification via constraints

Because the verifier cannot check the encrypted transcript directly, it defers verification. The prover and verifier jointly execute the Fiat-Shamir-driven protocol and, from the public inputs and the encrypted transcript, derive:

• One linear constraint per circuit layer, relating the encrypted per-layer claim values to the circuit structure and random challenges.
• One quadratic constraint per circuit layer, of the form $v_l \cdot v_r = v_{l \cdot r}$, ensuring the pad product is consistent.
• One additional final linear constraint tying the last pair of claims to a linear combination of the circuit inputs (public and private).

These constraints are then handed off to the Ligero scheme. The witness for Ligero is the concatenation of the circuit’s private inputs and the one-time pad values. Ligero proves the constraints are satisfied with respect to the committed witness, completing the argument.

Full Protocol Flow

Putting all three components together, the end-to-end protocol proceeds as follows.

The complete proof string that the prover sends is: a session nonce, the Merkle commitment, the encrypted sumcheck transcript, and the Ligero proof. Everything is deterministically serialized.

Security Properties

Completeness. An honest prover who knows $w$ such that $C(x, w) = 0$ always produces a proof that the verifier accepts.

Soundness. A cheating prover who does not know a valid $w$ can cause the verifier to accept only with negligible probability, derived from the soundness of the Ligero proof system and the sumcheck protocol.

Zero-knowledge. The proof reveals nothing about $w$ beyond the fact that a valid witness exists, derived almost entirely from the zero-knowledge property of the Ligero scheme. The one-time pad ensures the sumcheck transcript is information-theoretically hidden.

Assumptions. The scheme requires only a collision-resistant hash function (for the Merkle tree and Fiat-Shamir oracle) and the AES block cipher (for the FSPRF). There is no trusted setup and no common reference string.

Where to go next

• Get Started — install Longfellow and walk through a minimal end-to-end example.
• Guides — composition patterns that turn the primer’s components into working ZK systems.
• Reference / Proof System — the file-by-file layout of sumcheck, Ligero, Merkle, and transcript.
• Longfellow paper  and IETF draft  — the authoritative specifications this primer summarizes.