Longfellow ZK
draft-google-cfrg-libzk-02
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
| Document | Type | Active Internet-Draft (individual) | |
|---|---|---|---|
| Authors | Matteo Frigo , abhi shelat | ||
| Last updated | 2026-07-22 | ||
| RFC stream | (None) | ||
| Intended RFC status | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-google-cfrg-libzk-02
Network Working Group M. Frigo
Internet-Draft a. shelat
Intended status: Informational Google
Expires: 23 January 2027 22 July 2026
Longfellow ZK
draft-google-cfrg-libzk-02
Abstract
This document defines an algorithm for generating and verifying a
succinct non-interactive zero-knowledge argument that for a given
input x and a circuit C, there exists a witness w, such that C(x,w)
evaluates to 0. The technique here combines the MPC-in-the-head
approach for constructing ZK arguments described in Ligero [ligero]
with a verifiable computation protocol based on sumcheck for proving
that C(x,w)=0.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 23 January 2027.
Copyright Notice
Copyright (c) 2026 IETF Trust and the persons identified as the
document authors. All rights reserved.
Frigo & shelat Expires 23 January 2027 [Page 1]
Internet-Draft Longfellow ZK July 2026
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. The Longfellow system . . . . . . . . . . . . . . . . . . 4
2. Basic Operations and Notation . . . . . . . . . . . . . . . . 4
2.1. Array primitives . . . . . . . . . . . . . . . . . . . . 5
2.2. Polynomial operations . . . . . . . . . . . . . . . . . . 5
2.2.1. Extend method in Field F_p . . . . . . . . . . . . . 5
2.2.2. Extend method in Field GF 2^k . . . . . . . . . . . . 6
3. Fiat-Shamir primitives . . . . . . . . . . . . . . . . . . . 7
4. Ligero ZK Proof . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Merkle trees . . . . . . . . . . . . . . . . . . . . . . 7
4.1.1. Constructing a Merkle tree from n digests . . . . . . 7
4.1.2. Constructing a proof of inclusion . . . . . . . . . . 8
4.1.3. Verifying a proof of inclusion . . . . . . . . . . . 9
4.2. Common parameters . . . . . . . . . . . . . . . . . . . . 12
4.2.1. Constraints on parameters . . . . . . . . . . . . . . 12
4.3. Ligero commitment . . . . . . . . . . . . . . . . . . . . 13
4.4. Ligero Prove . . . . . . . . . . . . . . . . . . . . . . 16
4.4.1. Low-degree test . . . . . . . . . . . . . . . . . . . 16
4.4.2. Linear and Quadratic constraints . . . . . . . . . . 16
4.4.3. Selection of challenge indicies . . . . . . . . . . . 17
4.4.4. Ligero Prover procedure . . . . . . . . . . . . . . . 17
4.5. Ligero verification procedure . . . . . . . . . . . . . . 20
5. Overview of the Longfellow protocol . . . . . . . . . . . . . 23
5.1. Parameters needed to define Longfellow . . . . . . . . . 24
6. Sumcheck . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.1. Special conventions for sumcheck arrays . . . . . . . . . 24
6.2. The EQ[] array . . . . . . . . . . . . . . . . . . . . . 25
6.2.1. Remark . . . . . . . . . . . . . . . . . . . . . . . 26
6.3. Circuits . . . . . . . . . . . . . . . . . . . . . . . . 27
6.3.1. Layered circuits . . . . . . . . . . . . . . . . . . 27
6.3.2. Quad representation . . . . . . . . . . . . . . . . . 27
6.3.3. In-circuit assertions . . . . . . . . . . . . . . . . 27
6.4. Representation of polynomials . . . . . . . . . . . . . . 28
6.5. Transcript encryption and deferred verification . . . . . 29
6.6. Transform circuit and wires into a padded proof . . . . . 32
6.7. Generate constraints from the public inputs and the padded
proof . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Frigo & shelat Expires 23 January 2027 [Page 2]
Internet-Draft Longfellow ZK July 2026
7. Serializing objects . . . . . . . . . . . . . . . . . . . . . 41
7.1. Serializing structs . . . . . . . . . . . . . . . . . . . 42
7.2. Serializing Field elements . . . . . . . . . . . . . . . 42
7.2.1. Serializing a single field element . . . . . . . . . 43
7.2.2. Serializing an element of a subfield . . . . . . . . 44
7.3. Serializing a Sumcheck Transcript . . . . . . . . . . . . 44
7.4. Serializing a Ligero Proof . . . . . . . . . . . . . . . 44
7.5. Serializing a Sequence of proofs . . . . . . . . . . . . 45
8. Security Considerations . . . . . . . . . . . . . . . . . . . 46
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 46
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 46
10.1. Normative References . . . . . . . . . . . . . . . . . . 46
10.2. Informative References . . . . . . . . . . . . . . . . . 47
Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 47
Appendix B. Test Vectors . . . . . . . . . . . . . . . . . . . . 47
B.1. Test Vectors for Merkle Tree . . . . . . . . . . . . . . 47
B.1.1. Vector 1 . . . . . . . . . . . . . . . . . . . . . . 47
B.2. Test Vectors for Fiat-Shamir . . . . . . . . . . . . . . 48
B.2.1. Vector 1: WriteBytes . . . . . . . . . . . . . . . . 48
B.2.2. Vector 2: WriteFieldElement . . . . . . . . . . . . . 48
B.2.3. Vector 3: WriteFieldElementArray . . . . . . . . . . 49
B.2.4. Vector 4: Nat . . . . . . . . . . . . . . . . . . . . 49
B.2.5. Vector 5: Choice . . . . . . . . . . . . . . . . . . 49
B.3. Test Vectors for Circuit . . . . . . . . . . . . . . . . 50
B.3.1. Vector 1 . . . . . . . . . . . . . . . . . . . . . . 50
B.4. Test Vectors for Sumcheck . . . . . . . . . . . . . . . . 50
B.4.1. Vector 1 . . . . . . . . . . . . . . . . . . . . . . 50
B.5. Test Vectors for Ligero . . . . . . . . . . . . . . . . . 50
B.5.1. Vector 1 . . . . . . . . . . . . . . . . . . . . . . 50
B.6. Test Vectors for libzk . . . . . . . . . . . . . . . . . 51
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 51
1. Introduction
A zero-knowledge (ZK) scheme allows a Prover who holds an arithmetic
circuit C defined over a finite field F and two inputs (x,w) to
convince a Verifier who holds only (C,x) that the Prover knows w such
that C(x,w) = 0 without revealing any extra information to the
Verifier.
The concept of a zero-knowledge scheme was introduced by Goldwasser,
Micali, and Rackoff [GMR], and has since been rigourously explored
and optimized in the academic literature.
There are several models and efficiency goals that different ZK
schemes aim to achieve, such as reducing prover time, reducing
verifier time, or reducing proof size. Some ZK schemes also impose
other requirements to achieve their efficienc goals. This document
Frigo & shelat Expires 23 January 2027 [Page 3]
Internet-Draft Longfellow ZK July 2026
considers the scenario in which there are no common reference
strings, or trusted parameter setups that are available to the
parties. This immediately rules out several succinct ZK scheme from
the literature. In addition, this document also focuses on schemes
that can be instantiated from a collision-resistant hash function and
require no other complexity theoretic assumption. Again, this rules
out several schemes in the literature. All of the ZK schemes from
the literature that remain can be defined in the Interactive Oracle
Proof (IOP) model, and this document specifies a family of them that
enjoys both efficiency and simplicity.
1.1. The Longfellow system
This document specifies the Longfellow ZK scheme described in the
paper [longfellow]. The scheme is constructed from two components:
the first is the Ligero scheme, which provides a cryptographic
commitment scheme that supports an efficient ZK argument system that
enables proving linear and quadratic constraints on the committed
witness, and the second is a public-coin interactive protocol (IP)
for producing an argument that C(x,w)=0 where C is such a circuit, x
is a public input, and w is a private witness. The overall scheme
works by having the Prover commit to the witness w as well as a pad
used to commit the transcript of the IP, then to run the IP with the
verifier in a way that produces a commitment to the transcript of the
IP, and finally, by running the Ligero proof system to prove that the
transcript in the commitment induces the IP verifier to accept.
A companion document specifies how the circuit C is specified.
Another companion document specifies the security parameter profiles
for Longfellow.
2. Basic Operations and Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Additionally, the key words "*MIGHT*", "*COULD*", "*MAY WISH TO*",
"*WOULD PROBABLY*", "*SHOULD CONSIDER*", and "*MUST (BUT WE KNOW YOU
WON'T)*" in this document are to interpreted as described in RFC 6919
[RFC6919].
Except if said otherwise, random choices in this specification refer
to drawing with uniform distribution from a given set (i.e., "random"
is short for "uniformly random"). Random choices can be replaced
with fresh outputs from a cryptographically strong pseudorandom
generator, according to the requirements in [RFC4086], or
pseudorandom function.
Frigo & shelat Expires 23 January 2027 [Page 4]
Internet-Draft Longfellow ZK July 2026
2.1. Array primitives
The notation A[0..N] refers to the array of size N that contains
A[0],A[1],...,A[N-1], i.e., the right-boundary in the notation X..Y
is an exclusive index bound. The following functions are used
throughout the document:
* copy(n, Dst, Src): copies n elements from Src to Dst with
different strides
* axpy(n, Y, A, X): sets Y[i] += A*X[i] for 0 <= i < n.
* sum(n, A): computes the sum of the first n elements in array A
* dot(n, A, Y): computes the dot product of length n between arrays
A and Y.
* add(n, A, Y): returns the array [A[0]+Y[0], A[1]+Y[1], ...,
A[n-1]+Y[n-1]].
* prod(n, A, Y): returns the array [A[0]*Y[0], A[1]*Y[1], ...,
A[n-1]*Y[n-1]].
* equal(n, A, Y): true if A[i]==Y[i] for 0 <= i < n and false
otherwise.
* gather(n, A, I): returns the array [A[I[0]], A[I[1]], ...,
A[I[n-1]].
* A[n][m] = [0]: initializes the 2-dimensional n x m array A to all
zeroes.
* A[0..NREQ] = X : array assignment, this operation copies the first
NREQ elements of X into the corresponding indicies of the A array.
2.2. Polynomial operations
This section describes operations on and associated with polynomials
that are used in the main protocol.
2.2.1. Extend method in Field F_p
The extend(f, n, m) method interprets the array f[0..n] as the
evaluations of a polynomial P of degree less than n at the points
0,...,n-1, and returns the evaluations of the same P at the points
0,...,m-1. For sufficiently large fields |F_p| = p >= m, polynomial
P is uniquely determined by the input, and thus extend is well
defined.
As there are several algorithms for efficiently performing the extend
operation, the implementor can choose a suitable one. In some cases,
the brute force method of using Lagrange interpolation formulas to
compute each output point independently may suffice. One can employ
a convolution to implement the extend operation, and in some cases,
either the Number Theoretic Transform or Nussbaumer's algorithm can
be used to efficiently compute a convolution.
Frigo & shelat Expires 23 January 2027 [Page 5]
Internet-Draft Longfellow ZK July 2026
2.2.2. Extend method in Field GF 2^k
The previous section described an extend method that applies to odd
prime-order finite fields which contain the elements 0,1,2...,m. In
the special case of GF(2^k), the extend operator is defined in an
opinionated way inspired by the Additive FFT algorithm by Lin et al
[additivefft]. Lin et al. define a novel polynomial basis for
polynomials as an alternative to the usual monomial basis x^i, and
give an algorithm for evaluating a degree-(d-1) polynomial at all d
points in a subspace, for d=2^ell, and for polynomials expressed in
the novel basis.
Specifically, this document implements GF(2^128) as GF{2}[x] / (Q(x))
where
Q(x) = x^{128} + x^{7} + x^{2} + x + 1
With this choice of Q(x), x is a generator of the multiplicative
group of the field. Next, choose GF(2^16) as the subfield of
GF(2^128) with g=x^{(2^{128}-1) / (2^{16}-1)} as its generator, and
beta_i=g^i^ for 0 <= i < 16 as the basis of the subfield. For
relevant problem sizes, this allows encoding elements in a commitment
scheme with 16-bits instead of 128.
Writing j_i for the i-th bit of the binary representation of j, that
is,
j = sum_{0 <= i < k} j_i 2^i j_i \in {0,1}
inject integer j into a field element inj(j) by interpreting the bits
of j as coordinates in terms of the basis:
inj(j) = sum_{0 <= i < k} j_i beta_i
In this setting, define the extend operator to interpret the array
f[0..n] to consist of the evaluations of a polynomial p(x) of degree
at most n-1 at the n points x \in { inj(i) : 0 <= i < n } and to
return the set { p(inj(i)) : 0 <= i < m} which consist of the
evaluations of the same polynomial p(x) at the injected points
0,...,m-1.
This convention allows this operation to be completed efficiently
using various forms of the additive FFT as described in [longfellow]
[additivefft].
Frigo & shelat Expires 23 January 2027 [Page 6]
Internet-Draft Longfellow ZK July 2026
3. Fiat-Shamir primitives
A ZK protocol may in general be interactive whereby the Prover and
Verifier engage in multiple rounds of communication. However, in
practice, it is often more convenient to deploy a so-called non-
interactive or single-message protocol that only requires a single
message from Prover to Verifier. It is possible to apply the Fiat-
Shamir heuristic to transform a special class of interactive
protocols into single-message protocols. See {{draft-irtf-cfrg-fiat-
shamir-02}} for details on how to instantiate this heuristic for an
Interactive Oracle Protocol.
4. Ligero ZK Proof
This section specifies the construction and verification method for a
Ligero commitment and zero-knowledge argument. The Ligero system as
described by Ames, Hazay, Ishai, and Venkitasubramaniam [ligero],
consists of a commitment scheme, and a method for proving linear and
quadratic constraints on the committed values in zero-knowledge. The
later interface is sufficient to prove arbitrary circuits, but in the
Longfellow scheme, it suffices to describe how to use such
constraints to directly verify an IP transcript.
4.1. Merkle trees
This section describes how to construct a Merkle tree from a sequence
of n strings, and how to verify that a given string x was placed at
leaf i in a Merkle tree. These methods do not assume that n is a
power of two. This construction is parameterized by a cryptographic
hash function such as SHA-256 [RFC6234]. In this application, a leaf
in a tree is a message digest instead of an arbitrary string; for
example, if the hash function is SHA-256, then the leaf is a 32-byte
string.
A tree that contains n leaves is represented by an array of 2 * n
message digests in which the input digests are written at indicies
n..(2*n - 1). The tree is constructed by iteratively hashing the
concatenation of the values at indicies 2*j and 2*j+1, starting at
j=n-1, and continuing until j=1. The root is at index 1. In this
specification, the prover and verifier will already know the value of
n when they produce or verify a Merkle tree.
4.1.1. Constructing a Merkle tree from n digests
Frigo & shelat Expires 23 January 2027 [Page 7]
Internet-Draft Longfellow ZK July 2026
class MerkleTree:
def __init__(self, n: int) -> None:
self.n = n
self.a = [b''] * (2 * n)
def set_leaf(self, pos: int, leaf: bytes) -> None:
assert 0 <= pos < self.n, f"{pos} is out of bounds"
self.a[pos + self.n] = leaf
def build_tree(self) -> bytes:
for i in range(self.n - 1, 0, -1):
left = self.a[2 * i]
right = self.a[2 * i + 1]
self.a[i] = hash(left + right)
return self.a[1]
4.1.2. Constructing a proof of inclusion
This section describes how to construct a Merkle proof that k input
digests at indicies i[0],...,i[k-1] belong to the tree. The simplest
way to generate such a proof is to produce independent proofs for
each of the k leaves. However, this turns out to be wasteful in that
internal nodes may be included multiple times along different paths,
and some nodes may not need to be included at all because they are
implied by nodes that have already been included.
To address these inefficiencies, this section explains how to produce
a batch proof of inclusion for k leaves. The main idea is to start
from the requested set of leaves and build all of the implied
internal nodes given the leaves. For example, if sibling leaves are
included, then their parent is implied, and the parent need not be
included in the compressed proof. Then it suffices to revisit the
same tree and include the necessary siblings along all of the Merkle
paths. It is assumed that the verifier already has the leaf digests
that are at the indicies, and thus the proof only contains the
necessary internal nodes of the Merkle tree that are used to verify
the claim.
It is important in this formulation to treat the input digests as a
sequence, i.e. with a given order. Both the prover and verifier of
this batch proof must use the same order of the requested_leaves
array.
Frigo & shelat Expires 23 January 2027 [Page 8]
Internet-Draft Longfellow ZK July 2026
def mark_tree(
self,
requested_leaves: list[int],
) -> list[bool]:
marked = [False] * (2 * self.n)
for i in requested_leaves:
assert 0 <= i < self.n, f"invalid requested index {i}"
marked[i + self.n] = True
for i in range(self.n - 1, 0, -1):
marked[i] = marked[2 * i] or marked[2 * i + 1]
return marked
def compressed_proof(
self,
requested_leaves: list[int],
) -> list[bytes]:
proof = []
marked = self.mark_tree(requested_leaves)
for i in range(self.n - 1, 0, -1):
if marked[i]:
child = 2 * i
# If the left child is marked, we need the right
# child (sibling).
if marked[child]:
child += 1
# If the identified child/sibling is NOT marked,
# we must provide its hash in the proof so the
# verifier can calculate the parent.
if not marked[child]:
proof.append(self.a[child])
return proof
4.1.3. Verifying a proof of inclusion
This section describes how to verify a compressed Merkle proof. The
claim to verify is that "the commitment root defines an n-leaf Merkle
tree that contains k digests s[0], ..., s[k-1] at corresponding
indices i[0], ..., i[k-1]." The strategy of this verification
procedure is to deduce which nodes are needed along the k
verification paths from index to root, then read these values from
the purported proof, and then recompute the Merkle tree and the
consistency of the root digest. As an optimization, the defined[]
Frigo & shelat Expires 23 January 2027 [Page 9]
Internet-Draft Longfellow ZK July 2026
array avoids recomputing internal portions of the Merkle tree that
are not relevant to the verification. By convention, a proof for the
degenerate case of k=0 digests is defined to fail. It is assumed
that the indices[] array does not contain duplicates.
Frigo & shelat Expires 23 January 2027 [Page 10]
Internet-Draft Longfellow ZK July 2026
def verify_merkle(
self,
root: bytes,
n: int,
k: int,
s: list[bytes],
indices: list[int],
proof: list[bytes]) -> bool:
tmp: list[None | bytes] = [None] * (2 * n)
defined = [False] * (2 * n)
proof_index = 0
if n != self.n: return False
marked = self.mark_tree(indices)
for i in range(n - 1, 0, -1):
if marked[i]:
child = 2 * i
if marked[child]:
child += 1
if not marked[child]:
if proof_index >= len(proof):
return False
tmp[child] = proof[proof_index]
proof_index += 1
defined[child] = True
for i in range(k):
pos = indices[i] + n
tmp[pos] = s[i]
defined[pos] = True
for i in range(n - 1, 0, -1):
if defined[2 * i] and defined[2 * i + 1]:
left = tmp[2 * i]
right = tmp[2 * i + 1]
assert left is not None
assert right is not None
tmp[i] = hash(left + right)
defined[i] = True
return defined[1] and (tmp[1] == root)
Frigo & shelat Expires 23 January 2027 [Page 11]
Internet-Draft Longfellow ZK July 2026
4.2. Common parameters
The Prover and Verifier in Ligero must agree on the following
parameters. These parameters can be agreed upon out of band.
* F: The finite field over which the commit is produced.
* NREQ: The number of columns of the commitment matrix that the
Verifier requests to be revealed by the Prover.
* rate: The inverse rate of the error correcting code. This
parameter, along with NREQ and Field size, determines the
soundness of the scheme.
* BLOCK: the size of each row, in terms of number of field elements
* DBLOCK: 2 * BLOCK - 1
* WR: the number of witness values included in each row.
* QR: the number of quadratic constraints written in each row
* IW: Row index at which the witness values start, usually IW = 2.
* IQ: Row index at which the quadratic constraints begin, it is the
first row after all of the witnesses have been encoded.
* NL: Number of linear constraints.
* NQ: Number of quadratic constraints.
* NWROW: Number of rows used to encode witnesses.
* NQT: Number of row triples needed to encode the quadratic
constraints.
* NQW: NWROW + NQT, rows needed to encode witnesses and quadratic
constraints.
* NROW: Total number of rows in the witness matrix, NQW + 2
* NCOL: Total number of columns in the tableau matrix.
A row of the tableau consists of
| NREQ | WR | ... DBLOCK | ... NCOL | | random pad | witness values |
polynomial evaluations |
4.2.1. Constraints on parameters
* BLOCK < |F| The block size must be smaller than the field size.
* BLOCK > NREQ The block size must be larger than the number of
columns requested.
* BLOCK = NREQ + WR
* BLOCK >= 2 * (NREQ + QR) + (NREQ + WR) - 2
* WR >= QR.
* BLOCK >= 2 * (NREQ + WR) - 1.
Frigo & shelat Expires 23 January 2027 [Page 12]
Internet-Draft Longfellow ZK July 2026
* QR >= NREQ (and thus WR >= NREQ) to avoid wasting too much space.
4.3. Ligero commitment
The first step of the proof procedure requires the Prover to commit
to a witness vector W. The witness vector is assumed to be padded
with zeros at the end so that its length is an even multiple of WR.
The commitment is the root of a Merkle tree. The leaves of the
Merkle tree are a sequence of columns of the tableau matrix T[][].
This tableau matrix is constructed row-by-row by applying the extend
procedure to arrays that are formed from random field elements and
elements copied from the witness vector. Matrix T[][] has size NROW
x NCOL and has the following structure:
row ILDT = 0 : RANDOM row for low-degree test
row IDOT = 1 : RANDOM row for linear test
row IQD = 2 : RANDOM row for quadratic test
row i for IW = IDOT + 1 <= i < IQ : witness rows
row i for IQ <= i < NROW : quadratic rows
1) The first ILDT row is defined as
extend(RANDOM[BLOCK], BLOCK, NCOL)
by selecting BLOCK random field elements and applying extend.
2) The second IDOT row is defined as
Z = RANDOM[DBLOCK] such that
sum_{i = NREQ ... NREQ + WR - 1} Z_i = 0
extend(Z, DBLOCK, NCOL)
by first selecting DBLOCK random field elements such that the
subarray from index NREQ to NREQ + WR sums to 0 and then applying
extend. The first step can be performed by selecting DBLOCK-1
random field elements, and then setting element of the specified
range to be the additive inverse of the sum of elements from
NREQ...NREQ + WR - 1.
3) The third IQD row is defined as ZQ = RANDOM[DBLOCK] ZQ[NREQ ...
NREQ + WR - 1] = 0 extend(ZQ, DBLOCK, NCOL) by first selecting
DBLOCK random field elements, and then setting the portion
coresponding to the witness values to 0 and then applying extend.
Frigo & shelat Expires 23 January 2027 [Page 13]
Internet-Draft Longfellow ZK July 2026
4) The next rows from IW=3,...,IQ are _padded witness_ rows that
contain random elements and portions of the witness vector.
Specifically, row i is formed by applying extend to an array that
consists of NREQ random elements and then WR elements from the
vector W:
extend([RANDOM[NREQ], W[(i-2) * WR .. (i-1) * WR]], BLOCK, NCOL)
When the finite field contains a subfield, and if all of the
witness elements in a given row are elements from this subfield,
then the randomness for that row can also be chosen from the
subfield. Consequently, the extend method for that row produces
polynomial evaluations that are elements of the subfield. When
these elements are serialized, they will require less space. The
simplest way to apply this optimization is for the commiting
process to maintain an index SF such that witnesses at indices
0..SF belong to the subfield, and the rest do not. This value SF
can be conveyed to the verifier as part of the proof, or part of
the circuit.
5) The final portion of the witness matrix consists of _padded
quadratic_ rows that consists of NREQ random elements and WR
quadratic constraint elements:
extend([RANDOM[NREQ], QX[WR]], BLOCK, NCOL)
extend([RANDOM[NREQ], QY[WR]], BLOCK, NCOL)
extend([RANDOM[NREQ], QZ[WR]], BLOCK, NCOL)
The specific elements in the QX, QY, QZ array are determined by
the quadratic constraints on the witness values that are verified
by the proof.
The second step of the procedure is to compute a Merkle tree on
columns of the tableau matrix. Specifically, the i-th leaf of the
tree is defined to be columns DBLOCK...NCOL of the i-th row of the
tableau T.
Input:
* The witness vector W.
* Array of quadratic constraints lqc[], which consists of triples
(x,y,z) that represent the constraint that W[x] * W[y] = W[z].
Output:
* A digest; root of a Merkle tree formed from columns of the
tableau.
Frigo & shelat Expires 23 January 2027 [Page 14]
Internet-Draft Longfellow ZK July 2026
def commit(W[], lqc[]) {
T[NROW][NCOL] = [0]; // 2d array initialized with 0
layout_zk_rows(T);
layout_witness_rows(T, W);
layout_quadratic_rows(T, W, lqc);
MerkleTree M;
FOR DBLOCK <= j < NCOL DO
M.set_leaf(j - BLOCK,
hash( T[0][j] || T[1][j] || .. || T[NROW][j]) );
return M.build_tree();
}
def layout_zk_rows(T) {
T[0][0..NCOL] = extend(random_row(BLOCK), BLOCK, NCOL);
Z = random_row(DBLOCK)
s = SUM_{i = NREQ ... NREQ + WR - 2} Z_i
Z[NREQ + WR - 1] = -s
T[1][0..NCOL] = extend(Z, DBLOCK, NCOL)
ZQ = random_row[DBLOCK]
ZQ[NREQ ... NREQ + WR - 1] = 0
T[2][0..NCOL] = extend(ZQ, DBLOCK, NCOL)
}
def layout_witness_rows(T, w) {
FOR IW <= i <= IQ DO
bool subfield = false;
IF W[i * WR .. (i+1) * WR] are all in the subfield {
subfield = true;
}
row[0...NREQ-1] = random_row(NREQ, subfield)
row[NREQ..BLOCK] = W[i * WR .. (i+1) * WR]
T[i + IW][0..NCOL] = extend(row, BLOCK, NCOL)
}
Frigo & shelat Expires 23 January 2027 [Page 15]
Internet-Draft Longfellow ZK July 2026
def layout_quadratic_rows(T, w, lqc[]) {
FOR 0 <= i < NQT DO
qx[0..NREQ] = random_row(NREQ)
qy[0..NREQ] = random_row(NREQ)
qz[0..NREQ] = random_row(NREQ)
FOR 0 <= j < BLOCK DO
IF (j + i * Q < NQ)
assert( W[ lqc[j].x ] * W[ lqc[j].x ] == W[ lqc[j].z ] )
qx[NREQ + j] = W[ lqc[j].x ]
qy[NREQ + j] = W[ lqc[j].y ]
qz[NREQ + j] = W[ lqc[j].z ]
T[IQ + i * NQT ][0..NCOL] = extend(qx, BLOCK, NCOL)
T[IQ + i * NQT + 1][0..NCOL] = extend(qy, BLOCK, NCOL)
T[IQ + i * NQT + 2][0..NCOL] = extend(qz, BLOCK, NCOL)
}
4.4. Ligero Prove
This section specifies how a Ligero proof for a given sequence of
linear constraints and quadratic constraints on the committed witness
vector W is constructed. The proof consists of a low-degree test on
the tableau, a linearity test, and a quadratic constraint test.
4.4.1. Low-degree test
In the low-degree test, the verifier sends a challenge vector
consisting of NROW field elements, u[0..NROW]. This challenge is
generated via the Fiat-Shamir transform. The prover computes the sum
of u[i]*T[i] where T[i] is the i-th row of the tableau, and returns
the first BLOCK elements of the result. The verifier applies the
extend method to this response, and then verifies that the extended
row is consistent with the positions of the Merkle tree that the
verifier will later request from the Prover.
The Prover's task is therefore to compute a summation. For
efficiency, set u[0]=1 because this first row corresponds to a random
row meant to ``pad" the witnesses for zero-knowledge.
4.4.2. Linear and Quadratic constraints
The linear test is represented by a matrix A, and a vector b, and
aims to verify that A*W = b. The constraint matrix A is given as
input in a sparse form: it is an array of triples (c,j,k) in which c
indicates the constraint number or row of A, j represents the index
of the witness or column of A, and k represents the constant factor.
For example, if the first constraint (at index 0) is W[2] + 2W[3] =
Frigo & shelat Expires 23 January 2027 [Page 16]
Internet-Draft Longfellow ZK July 2026
3, then the linear constraints array contains the triples (0,2,1),
(0,3,2) and the b vector has b[0]=3.
The quadratic constraints are given as input in an array lqc[] that
contains triples (x,y,z); one such triple represents the constraint
that W[x] * W[y] = W[z]. To process quadratic constraints, tableau T
is augmented with 3 extra rows, called Qx, Qy, and Qz which hold
_copied_ witnesses and their products. If the i-th quadratic
constraint is (x,y,z), then the prover sets Qx[i] = W[x], Qy[i] =
W[y] and Qz[i] = W[x] * W[y]. Next, the prover adds a linear
constraint that Qx[i] - W[x] = 0, Qy[i] - W[y] = 0 and Qz[i] - W[z] =
0 to ensure that the copied witness is consistent.
In this sense, the quadratic constraints are reduced to linear
constraints, and the additional requirement for the verifier to check
that each index of the Qz row is the product of its counterpart in
the Qx and Qy row.
4.4.3. Selection of challenge indicies
The last step of the prove method is for the verifier to select a
subset of unique indices (i.e., they are sampled without replacement)
from the range DBLOCK...NCOL and request that the prover open these
columns of tableau T. These opened columns are then used to verify
consistency with the previous messages sent by the prover.
4.4.4. Ligero Prover procedure
The context argument is application-dependent and includes
information about the theorem statement that is proven.
Frigo & shelat Expires 23 January 2027 [Page 17]
Internet-Draft Longfellow ZK July 2026
def prove(transcript, context, linear[], lqc[]) {
transcript.write(context)
u = transcript.generate_challenge([BLOCK]);
ldt[0..BLOCK] = T[ILDT][0..BLOCK]
for(i=3; i < NROW; ++i) {
ldt[0..BLOCK] += u[i] * T[i][0..BLOCK]
}
alpha_l = transcript.generate_challenge([NL])
alpha_q = transcript.generate_challenge([NQ,3])
A = inner_product_vector(linear, alpha_l, lqc, alpha_q)
dot = dot_proof(A);
uquad = transcript.generate_challenge([NQT])
qpr = quadratic_proof(lqc, uquad)
transcript.write(ldt);
transcript.write(dot);
transcript.write(qpr);
challenge_indicies = transcript.generate_nats_wo_replacement(
NCOL - DBLOCK,
NREQ,
);
columns = requested_columns(challenge_indicies, DBLOCK);
mt_proof = M.compressed_proof(challenge_indicies);
return (ldt, dot, qpr, columns, mt_proof)
}
Input:
- linear: array of (w,c,k) triples specifying the linear constraints
- alpha_l: array of challenges for the linear constraints
- lqc: array of (x,y,z) triples specifying the quadratic constraints
- alpha_q: array of challenges for the quadratic constraints
Output:
- A: a vector of size WR x NROW that contains the combined
witness constraints.
The first NW * W positions correspond to coefficients
Frigo & shelat Expires 23 January 2027 [Page 18]
Internet-Draft Longfellow ZK July 2026
for the linear constraints on witnesses.
The next 3*NQ positions correspond to coefficients
for the quadratic constraints.
def inner_product_vector(A, linear, alpha_l, lqc, alpha_q) {
A = [0]
// random linear combinations of the linear constraints
FOR 0 <= i < NL DO
assert(linear[i].w < NW)
assert(linear[i].c < NL)
A[ linear[i].w ] += alpha_l[ linear[i].c ] * linear[i].k
// pointers to terms for quadratic constraints
a_x = NW * W
a_y = NW * W + (NQ * W)
a_z = NW * W + 2 * (NQ * W)
FOR 0 <= i < NQT DO
FOR 0 <= j < QR DO
IF (j + i * QR < NQ)
ilqc = j + i * QR // index into lqc
ia = j + i * WR // index into Ax,Ay,Az sub-arrays
(x,y,z) = lqc[ilqc]
// add constraints that the copies are correct
A[a_x + ia] += alpha_q[ilqc][0]
A[x] -= alpha_q[ilqc][0]
A[a_y + ia] += alpha_q[ilqc][1]
A[y] -= alpha_q[ilqc][1]
A[a_z + ia] += alphaq[ilqc][2]
A[z] -= alphaq[ilqc][2]
return A
}
def dot_proof(A) {
y = T[IDOT][0..BLOCK]
Aext[0..BLOCK] = [0]
FOR 0 <= i < NQW DO
Aext[0..NREQ] = [0]
Aext[NREQ..NREQ + WR] = A[i * WR..(i+1) * WR]
Af = extend(Aext, BLOCK, DBLOCK)
axpy(DBLOCK, y[0..DBLOCK], Af[0..DBLOCK], T[i + IW][0...DBLOCK])
Frigo & shelat Expires 23 January 2027 [Page 19]
Internet-Draft Longfellow ZK July 2026
return y
}
def quadratic_proof(lqc, uquad) {
y[0..DBLOCK] = T[IQD][0..DBLOCK]
iqx = IQ;
iqy = iqx + NQT
iqz = iqy + NQT
FOR 0 <= i < NQT
// y += uquad[i] * (z[i] - x[i] * y[i])
tmp = T[iqz + i][0..DBLOCK]
// tmp -= x[i] \otimes y[i]
sub(DBLOCK, tmp[0...DBLOCK],
mul(DBLOCK, T[iqx][0..DBLOCK],
T[iqy][0..DBLOCK]))
// y += u_quad[i] * tmp
axpy(DBLOCK, y[0..DBLOCK], uquad[i], tmp[0..DBLOCK])
}
// sanity check: the Witness part of Y is zero
assert(y[NREQ...BLOCK] == 0)
// extract the non-zero parts of y
return y[0..NREQ], y[BLOCK..DBLOCK]
}
def requested_columns(challenge_indicies, offset) {
cols = [] // array of columns of T
FOR (index i : challenge_indicies) {
cols.append( [ T[0..NROW][i + offset] ] )
}
return cols
}
4.5. Ligero verification procedure
This section specifies how to verify a Ligero proof with respect to a
common set of linear and quadratic constraints.
Frigo & shelat Expires 23 January 2027 [Page 20]
Internet-Draft Longfellow ZK July 2026
Input:
- commitment: the first Prover message that commits to the witness
- proof: Prover's proof
- transcript: Fiat-Shamir
- linear: array of (w,c,k) triples specifying the linear constraints
- b: the vector b in the constraint equation A*w = b.
- lqc: array of (x,y,z) triples specifying the quadratic constraints
Output:
- a boolean
def verify(commitment, proof, transcript,
linear[], digest, b[], lqc[]) {
u = transcript.generate_challenge([BLOCK]);
transcript.write(digest)
alpha_l = transcript.generate_challenge([NL]);
alpha_q = transcript.generate_challenge([NQ,3]);
transcript.write(proof.ldt);
transcript.write(proof.dot);
challenge_indicies = transcript.generate_challenge([NREQ]);
A = inner_product_vector(linear, alpha_l, lqc, alpha_q);
// check the putative value of the inner product
want_dot = dot(NL, b, alpha_l);
proof_dot = sum(proof.dot);
return
verify_merkle(commitment.root, BLOCK*RATE, NREQ,
proof.columns, challenge_indicies, mt_proof.mt)
AND quadratic_check(proof)
AND low_degree_check(proof, challenge_indicies, u)
AND dot_check(proof, challenge_indicies, A)
AND want_dot == proof_dot
}
def quadratic_check(proof, challenge_indices) {
iqx = IQ;
iqy = iqx + NQT
iqz = iqy + NQT
yc = proof.iquad
FOR 0 <= i < NQT {
// yc += u_quad[i] * (z[i] - x[i] * y[i])
tmp = proof.z[iqz + i][0..DBLOCK]
Frigo & shelat Expires 23 January 2027 [Page 21]
Internet-Draft Longfellow ZK July 2026
// tmp -= x[i] \otimes y[i]
sub(DBLOCK, tmp[0...DBLOCK],
mul(DBLOCK, T[iqx][0..DBLOCK],
T[iqy][0..DBLOCK]))
// y += u_quad[i] * tmp
axpy(DBLOCK, yc[0..DBLOCK], u_quad[0..DBLOCK], tmp[0..DBLOCK])
}
yquad = proof.qpr[0..NREQ] || 0 || proof.qpr[BLOCK...DBLOCK]
yp = extend(yquad, DBLOCK, NCOL)
// Verify that yp and yc agree at the challenge indices.
want = gather(NREQ, yp, challenge_indices)
return equal(NREQ, want, yc[{idx}])
}
def low_degree_check(proof, u, challenge_indicies) {
got = proof.columns[ILDT][0..NREQ]
FOR 1 <= i < NROW DO {
axpy(NREQ, got, u[i], proof.columns[i][...])
}
row = extend(proof.ldt, BLOCK, NCOL)
want = gather(NREQ, row, challenge_indicies)
return equal(NREQ, got, want)
}
def dot_check(proof, challenge_indicies, A) {
yc = proof.columns[IDOT][0..NREQ]
Aext[0..BLOCK] = [0]
FOR 0 <= i < NQW DO
Aext[0..R] = [0]
Aext[R..R + WR] = A[i * WR..(i+1) * WR]
Af = extend(Aext, R + WR, BLOCK)
Areq = gather(NREQ, Af, challenge_indicies);
// Accumulate z += A[j] \otimes W[j].
sum( yc, prod(NCOL, Areq[0..NREQ],
proof.columns[i][0..NREQ]))
row = extend(proof.dot, BLOCK, NCOL)
yp = gather(NREQ, row, challenge_indicies)
Frigo & shelat Expires 23 January 2027 [Page 22]
Internet-Draft Longfellow ZK July 2026
return equal(NREQ, yp, yc)
}
5. Overview of the Longfellow protocol
The Longfellow ZK protocol uses two protocol components. The first
is a variant of the sumcheck protocol, modified to support zero
knowledge. Informally, the standard sumcheck prover takes the
description of a circuit and the concrete values of all the wires in
the circuit, and produces a proof that all wires have been computed
correctly. The proof itself is a sequence of field elements.
Longfellow uses an encrypted-variant of the sumcheck prover that also
takes as input a random and secret one-time pad and outputs an
"encrypted" proof such that each element in this proof is the
difference of the element in the standard sumcheck proof and its
corresponding element in the pad. (The choice of "difference"
instead of "sum" is a matter of convention.)
In this encrypted sumcheck variant, the verifier cannot check the
proof directly because it cannot access the one-time pad. Instead of
running the sumcheck verifier directly, a commitment scheme is used
to hide the one-time pad, and the sumcheck verifier is translated
into a sequence of linear and quadratic constraints on the inputs and
the one-time pad. A secondary proof system is then used to produce a
proof with respect to the commitment that the constraints are
satisfied.
The protocol requires both parties to agree on a circuit as part of
the theorem statement. The wire format of a circuit is defined in a
separate document.
Some of the wires of the circuit are _inputs_, i.e., set outside the
circuit and not computed by the circuit itself. Some of the inputs
are _public_, i.e., known to both parties, and some are _private_,
i.e., known only to the prover. Sumcheck does not use the
distinction between public and private inputs. This document
distinguishes private inputs from the one-time pad. The commitment
scheme does not use public inputs at all, but it does treat private
inputs and the one-time pad elements equally. These constraints
motivate the following terminology.
* _public inputs_: inputs to the circuit known to both parties.
* _private inputs_: inputs to the circuit known to the prover but
not to the verifier.
* _inputs_: both public and private inputs. When forming an array
of all inputs, the public inputs come first, followed by the
private inputs.
Frigo & shelat Expires 23 January 2027 [Page 23]
Internet-Draft Longfellow ZK July 2026
* _witnesses_: the private inputs and the elements in the one-time
pad. When forming an array of all witnesses, the private inputs
come first, followed by the one-time pad.
Thus, at a high level, the sequence of operations in the ZK protocol
is the following:
1. The prover commits to all witness values.
2. The prover runs the encrypted sumcheck prover on the witness
values to producing an encrypted proof, all-the-while sending the
encrypted proof to the verifier.
3. Both the prover and the verifier take the public inputs and the
encrypted proof and produce a sequence of constraints.
4. Using the commitment scheme and the witnesses, the prover
generates a proof that the constraints from step 3 are satisfied.
5. The verifier uses the proof from step 4 and the constraints from
step 3 to check the constraints.
Steps 2 and 3 are referred to as "sumcheck", and the rest as
"commitment scheme". While the classification of step 3 as
"sumcheck" is arbitrary, there are situations where one might want to
use a commitment scheme other than the Ligero protocol specified in
this document. In this case, the "commitment scheme" can change
while the "sumcheck" remains unaffected.
5.1. Parameters needed to define Longfellow
Longfellow is parameterized by a sumcheck protocol, a commitment
protocol, and a Fiat-Shamir instantiation. A selection of all three
defines a Longfellow profile. This document introduces one
opinionated profile that uses (a) The longfellow sumcheck described
below, (b) the Ligero commitment described above, (c) the Fiat-Shamir
instantiation defined above and using SHA-256 as the function H.
6. Sumcheck
6.1. Special conventions for sumcheck arrays
The square brackets A[j] denote generic array indexing.
For the arrays of field elements used in the sumcheck protocol,
however, it is convenient to use the conventions that follow.
Frigo & shelat Expires 23 January 2027 [Page 24]
Internet-Draft Longfellow ZK July 2026
The sumcheck array A[i] is implicitly assumed to be defined for all
nonnegative integers i, padding with zeroes as necessary. Here,
"zero" is well defined because A[] is an array of field elements.
Arrays can be multi-dimensional, as in the three-dimensional array
Q[g, l, r]. It is understood that the array is padded with
infinitely many zeroes in each dimension.
Depending on the context, some arrays may consist of almost all non-
zero values, while other arrays may be sparse, containing very few
non-zero values (ignoring the zero-padding convention above).
Implementations should use dense or sparse representations of arrays
as appropriate.
Given array A[] and field element x, the function bind(A, x) returns
the array B such that
B[i] = (1 - x) * A[2 * i] + x * A[2 * i + 1]
In case of multiple dimensions such as Q[g, l, r], always bind across
the first dimension. For example,
bind(Q, x)[g, l, r] =
(1 - x) * Q[2 * g, l, r] + x * Q[2 * g + 1, l, r]
This bind can be generalized to an array of field elements as
follows:
bindv(A, X) =
A if X is empty
bindv(bind(A, X[0]), X[1..]) otherwise
Two-dimentional arrays can be transposed in the usual way:
transpose(Q)[l, r] = Q[r, l] .
6.2. The EQ[] array
EQ_{n}[i, j] is a special 2D array defined as
EQ_{n}[i, j] = 1 if i = j and i < n
0 otherwise
The sumcheck literature usually assumes that n is a power of 2, but
this document allows n to be an arbitrary integer. When n is clear
from context or unimportant, the subscript is omitted like EQ[i, j].
EQ[] is important because the general expansion
Frigo & shelat Expires 23 January 2027 [Page 25]
Internet-Draft Longfellow ZK July 2026
V[i] = SUM_{j} EQ[i, j] V[j]
commutes with binding, yielding
bindv(V, X) = SUM_{j} bindv(EQ, X)[j] V[j] .
That is, one way to compute bindv(V, X) is via dot product of V with
bindv(EQ, X). This strategy may or may not be advantageous in
practice, but it becomes mandatory when bindv(V, X) must be computed
via a commitment scheme that supports linear constraints but not
binding.
This document only uses bindings of EQ and never EQ itself, and
therefore the whole array never needs to be stored explicitly. For n
= 2^l and X of size l, bindv(EQ_{n}, X) can be computed recursively
in linear time as follows.
def bindeq(
field: FiniteField,
challenges: list[FiniteRingElement],
) -> list[FiniteRingElement]:
log_n = len(challenges)
if log_n == 0:
return [field.one()]
n = 2 ** log_n
b = [field.zero() for _ in range(n)]
a = bindeq(field, challenges[1:])
for i in range(n // 2):
b[2 * i] = (field.one() - challenges[0]) * a[i]
b[2 * i + 1] = challenges[0] * a[i]
return b
For m <= n, bindv(EQ_{n}, X)[i] and bindv(EQ_{m}, X)[i] agree for 0
<= i < m, and thus bindv(EQ_{m}, X)[i] can be computed by padding m
to the next power of 2 and ignoring the extra elements. With some
care, it is possible to compute bindeq() in-place on a single array
of arbitrary size m and eliminate the recursion completely.
6.2.1. Remark
Let m <= n, A = bindv(EQ_{m}, X) and B = bindv(EQ_{n}, X). It is
true that A[i] = B[i] for i < m. However, it is also true that A[i]
= 0 for i >= m, whereas B[i] is in general nonzero. Thus, care must
be taken when computing a further binding bindv(A, Y), which is in
general not the same as bindv(B, Y). A second binding is not needed
in this document, but certain closed-form expressions for the binding
found in the literature agree with these definitions only when m is a
power of 2.
Frigo & shelat Expires 23 January 2027 [Page 26]
Internet-Draft Longfellow ZK July 2026
6.3. Circuits
This section describes a circuit in Longfellow. A companion document
specifies how a circuit is serialized.
6.3.1. Layered circuits
A circuit consists of NL _layers_. By convention, layer j computes
wires V[j] given wires V[j + 1], where each V[j] is an array of field
elements. A _wire_ is an element V[j][w] for some j and w. Thus,
V[0] denotes the output wires of the entire circuit, and V[NL]
denotes the input wires.
A circuit is intended to check that some property of the input holds,
and by convention, the check is considered successful if all output
wires are 0, that is, if V[0][w] = 0 for all w.
6.3.2. Quad representation
The computation of circuit is defined by a set of _quads_ Q[j], one
per layer. Given the output of layer j + 1, the output of of layer j
is given by the following equation:
V[j][g] = SUM_{l, r} Q[j][g, l, r] V[j + 1][l] V[j + 1][r] .
The quad Q[j][] is thus a three-dimensional array in the indices g,
l, and r where 0 <= g < NW[j] and 0 <= l, r < NW[j + 1]. In
practice, Q[j][] is sparse.
The specification of the circuit contains an auxiliary vector of
quantities LV[j] with the property that V[j][w] = 0 for all w >=
2^{LV[j]}. Informally, LV[j] is the number of bits needed to name a
wire at layer j, but LV[j] may be larger than the minimum required
value.
6.3.3. In-circuit assertions
In the libzk system, a theorem is represented by a circuit such that
the theorem is true if and only if all outputs of the circuit are
zero. It happens in practice that many output wires are computed
early in the circuit (i.e., in a layer closer to the input), but
because of layering, they need to be copied all the way to output
layer in order to be compared against zero. This copy seems to
introduce large overheads in practice.
A special convention can mitigate this problem. Abstractly, a layer
is represented by _two_ quads Q and Z, and the operation of the layer
is described by the two equations
Frigo & shelat Expires 23 January 2027 [Page 27]
Internet-Draft Longfellow ZK July 2026
V[j][g] = SUM_{l, r} Q[j][g, l, r] V[j + 1][l] V[j + 1][r]
0 = SUM_{l, r} Z[j][g, l, r] V[j + 1][l] V[j + 1][r]
Thus, the Z quad asserts that, for given layer j and output wire g, a
certain quadratic combination of the input wires is zero.
The actual protocol verifies a random linear combination of those two
equations, effectively operating on a combined quad QZ = Q + beta * Z
for some random beta.
To allow for a compact representation of the two quads without losing
any real generality, the following conditions are imposed:
* The two quads Q and Z are disjoint: for all layers j and output
wire g, if any Q[j][g, ., .] are nonzero, then all Z[j][g, ., .]
are zero, and vice versa.
* Z is binary: Z[j][g, l, r] \in {0, 1}
With these choices, the two quads allow a compact sparse
representation as a single list of 4-tuples (g, l, r, v) with the
following conventions:
* If v = 0, the 4-tuple represents an element of Z, and Z[j][g, l,
r] = 1.
* If v != 0, the 4-tuple represents an element of Q, and Q[j][g, l,
r] = v.
* All other elements of Q and Z not specified by the list are zero.
Moreover, this compact representation can be transformed into a
representation of QZ = Q + beta * Z by replacing all v = 0 with v =
beta.
6.4. Representation of polynomials
In a generic sumcheck protocol, the prover sends to the verifier
polynomials of a degree specified in advance. In the present
document, the polynomials are always of degree two, and are
represented by their evaluations at three points P0 = 0, P1 = 1, and
P2, where 0 and 1 are the additive and multiplicative identities in
the field. The choice of P2 depends upon the field. For fields of
characteristic greater than 2, set P2 = 2 (= 1 + 1 in the field).
For GF(2^128) expressed as GF(2)[X] / (X^128 + X^7 + X^2 + X + 1),
set P2 = inj(2) as defined in Section 2.2.2. This document does not
prescribe a choice of P2 for binary fields other than GF(2^128).
At the start of each round of communication in a sumcheck protocol,
both the prover and the (virtual) sumcheck verifier agree on a claim
value, which represents the sum of the evaluation of some function at
Frigo & shelat Expires 23 January 2027 [Page 28]
Internet-Draft Longfellow ZK July 2026
all inputs {0,1}^*. The polynomials computed by the prover represent
the sum of the evaluations of the multilinear extension of that same
function, with one argument fixed to P0, P1, or P2, and all other
arguments chosen from {0,1}. Therefore, the sum of p(P0) + p(P1) is
equal to the claim from the start of the sumcheck round, and the
prover only needs to send two field elements in order for the parties
to agree on the entire degree two polynomial. Here, p(P0) and p(P2)
are sent to the (virtual) sumcheck verifier, and p(P1) is
reconstructed from p(P0) and the claim.
6.5. Transcript encryption and deferred verification
The sumcheck protocol produces a series of polynomials and claim
values, computed from the circuit input values, to prove that the
circuit was evaluated correctly. As described in Section 5, these
polynomials and claims are not directly revealed to the verifier.
Rather, the field elements that make up these values are encrypted
with a one-time pad by subtracting a randomly chosen pad value from
each field element, and the difference is sent to the verifier.
When the verifier executes the sumcheck protocol, it does not have
direct access to all the circuit inputs, and it is only given the
one-time pad encrypted forms of the sumcheck polynomials and per-
layer claims, not the corresponding plaintext values. Therefore, the
prover and verifier defer part of the verification by producing a
series of linear and quadratic constraints, relating the private
input values and the one-time pad values, so that those constraints
can be checked with the Ligero zero-knowledge system (see Section 4).
The variables used in these constraints are assigned sequentially,
first to the private circuit inputs, then to elements of the one-time
pad. Variables for one-time pad values are assigned to values for
circuit layers in order, starting with the output layer. Within each
layer, variables are first assigned to one-time pad values for
sumcheck polynomials, then to the per-layer claim values. The number
of sumcheck polynomials for each layer is equal to double the value
of log_num_input_wires for that layer of the circuit. The
polynomials are represented by two field elements each, one for the
evaluation at P0 = 0, and one for the evaluation at P2. At the end
of the variables for each layer, three variables are assigned for
claim-related values. Two variables are used for the one-time pad
values for the claims vl and vr. Then, a variable is used for the
product of those two one-time pad values.
Frigo & shelat Expires 23 January 2027 [Page 29]
Internet-Draft Longfellow ZK July 2026
def construct_symbolic_variables(
field: FiniteField,
circuit: Circuit,
) -> tuple[
tuple[MPolynomial, ...],
list[LayerPad[MPolynomial]],
]:
num_private_inputs = circuit.ninputs - circuit.pub_in
witness_length = (
num_private_inputs
+ sum(l.log_num_input_wires for l in circuit.layers) * 4
+ len(circuit.layers) * 3
)
ring = PolynomialRing(field, witness_length, "w")
variables = ring.gens()
witness_variables = variables[:num_private_inputs]
pad_variables = variables[num_private_inputs:]
return (
witness_variables,
construct_symbolic_pad(field, circuit, pad_variables)
)
def construct_symbolic_pad(
field: FiniteField,
circuit: Circuit,
variables: Sequence[MPolynomial],
) -> list[LayerPad[MPolynomial]]:
it = iter(variables)
layers = []
for layer in circuit.layers:
evals: list[list[SumcheckPolynomial[MPolynomial]]] = []
for round in range(layer.log_num_input_wires):
evals.append([])
for _ in range(2):
evals[round].append(
SumcheckPolynomial(
next(it),
next(it),
),
)
vl = next(it)
vr = next(it)
vl_vr = next(it)
layers.append(LayerPad(
evals,
vl,
vr,
Frigo & shelat Expires 23 January 2027 [Page 30]
Internet-Draft Longfellow ZK July 2026
vl_vr,
))
return layers
def construct_concrete_pad(
field: FiniteField,
circuit: Circuit,
pad_prg: Callable[
[FiniteField],
FiniteRingElement,
] = random_element,
) -> tuple[
list[LayerPad[FiniteRingElement]],
list[FiniteRingElement],
]:
"""
Chooses one-time pad values, and returns them in structured and
flattened forms.
"""
layers = []
flattened = []
for layer in circuit.layers:
evals: list[list[SumcheckPolynomial[FiniteRingElement]]] = []
for round in range(layer.log_num_input_wires):
evals.append([])
for _ in range(2):
p0 = pad_prg(field)
p2 = pad_prg(field)
evals[round].append(SumcheckPolynomial(p0, p2))
flattened.append(p0)
flattened.append(p2)
vl = pad_prg(field)
vr = pad_prg(field)
vl_vr = vl * vr
layers.append(LayerPad(
evals,
vl,
vr,
vl_vr,
))
flattened.append(vl)
flattened.append(vr)
flattened.append(vl_vr)
return (layers, flattened)
Frigo & shelat Expires 23 January 2027 [Page 31]
Internet-Draft Longfellow ZK July 2026
6.6. Transform circuit and wires into a padded proof
The prover constructs a padded proof by executing the sumcheck
protocol in order to certify that the wires at each layer of the
circuit are correctly calculated from the wires at the preceding
layer.
The goal is to prove that, for some layer index j, and every output
wire index g in that layer, the following all hold with high
probability.
V[j][g] = SUM_{l, r} Q[j][g, l, r] V[j + 1][l] V[j + 1][r]
0 = SUM_{l, r} Z[j][g, l, r] V[j + 1][l] V[j + 1][r]
These equations are combined into one equation after multiplying them
by random verifier challenges. This equation is of the form
claim = SUM_{l, r} QUAD[j][l, r] V[j + 1][l] V[j + 1][r]
If we reinterpret the wire indices l and r as binary numbers,
replacing them both with log_num_input_wires many variables having
value 0 or 1, then this equation has the form needed to apply the
sumcheck protocol.
At each layer, both parties start with two claims that each represent
a linear combination of the layer's output wire values. Concretely,
the claims for the layer's outputs are bind(V[j], G[0]) and
bind(V[j], G[1]) where G[0] and G[1] are arrays of verifier
challenges. These two claim values get combined into one using a
random challenge value. In each successive round of communication,
the function inside the summation is replaced with a new function
having one fewer parameter, one of the output wire arrays is halved
in size by binding it with a random challenge, and the claim value is
replaced with a newly computed claim value. The prover proves that
the new claim values and the new function at each round are
consistent with those in the previous round by evaluating the
multilinear extension of the function at multiple points, including
points with a random challenge coordinate. The prover computes a
degree two polynomial by summing this multilinear extension at many
points, with the polynomial's parameter determining the last
parameter of the multilinear extension. Two evaluations of this
polynomial are sent to the verifier, though as noted above these
evaluations get encrypted with a one-time pad. After several rounds
of communication, the function being summed is replaced with a
constant, and both output wire arrays are replaced with two new claim
values. Concretely, the new claims will be bind(V[j + 1], G'[0]) and
bind(V[j + 1], G'[0]), where V[j + 1] is the input wires of layer j,
Frigo & shelat Expires 23 January 2027 [Page 32]
Internet-Draft Longfellow ZK July 2026
and G'[0] and G'[1] are a fresh set of verifier challenges, chosen at
each round of the sumcheck protocol. These two claim values are
encrypted with a one-time pad and sent to the verifier.
Before the first round, a fixed number of verifier challenges are
generated and discarded. These are reserved for possible future
extensions to the protocol. Additionally, a fixed number of
challenges are generated for binding the output wires before the
first round, with the remainder of the challenges being discarded.
In both of these cases, MAX_BINDINGS = 40 challenges are generated.
For all subsequent layers, challenges used for binding output wires
are generated one at a time, with no extra unused challenges.
Frigo & shelat Expires 23 January 2027 [Page 33]
Internet-Draft Longfellow ZK July 2026
def sumcheck_circuit(
field: FiniteField,
circuit: Circuit,
wires: list[list[FiniteRingElement]],
pad: list[LayerPad[FiniteRingElement]],
transcript: Transcript) -> list[LayerProof]:
for _ in range(MAX_BINDINGS):
# Discard initial challenges. These are reserved for possible
# future use.
_ = transcript.generate_field(field)
challenges = [
transcript.generate_field(field)
for _ in range(MAX_BINDINGS)
]
G = (
challenges[:circuit.log_num_outputs],
challenges[:circuit.log_num_outputs],
)
proof: list[LayerProof] = []
for j, layer in enumerate(circuit.layers):
alpha = transcript.generate_field(field)
# Form the combined quad, QZ = Q + beta * Z, to handle
# in-circuit assertions.
beta = transcript.generate_field(field)
QZ = layer.quad + beta * layer.Z
# QZ is three-dimensional, QZ[g, l, r].
QUAD = QZ.bindv(G[0]) + alpha * QZ.bindv(G[1])
# Having bound g, QUAD is now effectively two-dimensional,
# QUAD[l, r].
QUAD = QUAD.drop_dimension()
layer_proof, G = sumcheck_layer(
field,
QUAD,
wires[j + 1],
layer.log_num_input_wires,
pad[j],
transcript,
)
proof.append(layer_proof)
return proof
Frigo & shelat Expires 23 January 2027 [Page 34]
Internet-Draft Longfellow ZK July 2026
def sumcheck_layer(
field: FiniteField,
QUAD: SparseArray,
wires: list[FiniteRingElement],
log_num_input_wires: int,
layer_pad: LayerPad[FiniteRingElement],
transcript: Transcript) -> tuple[
LayerProof,
tuple[list[FiniteRingElement], list[FiniteRingElement]],
]:
VL = DenseArray(field, wires)
VR = DenseArray(field, wires)
P2 = sumcheck_p2(field)
evals: list[list[SumcheckPolynomial[FiniteRingElement]]] = []
G: tuple[list, list] = ([], [])
for round in range(log_num_input_wires):
evals.append([])
for hand in range(2):
# Consider the following polynomial.
#
# p(x) = \sum_{l, r} bind(QUAD, x)[l, r]
# * bind(VL, x)[l]
# * VR[r]
#
# We evaluate this polynomial at the points P0 and P2.
# The sum of p(P0) and p(P1) is implicitly known already,
# so p(P1) does not need to be calculated.
#
# Implementation note: this can be computed more
# efficiently by first computing the intermediate array
# defined as follows:
#
# A[l] = \sum_{r} QUAD[l, r] * VR[r]
#
# This allows performing only one pass over the quad, and
# binding only 1-D arrays with length equal to the number
# of wires.
eval_p0 = sum(
(
v * VL[k[hand]] * VR[k[1 - hand]]
for (k, v) in QUAD.entries.items()
if k[hand] & 1 == 0
),
start=field.zero(),
)
QUAD_bind_p2 = QUAD.bind(P2, axis=hand)
VL_bind_p2 = VL.bind(P2)
eval_p2 = field.zero()
Frigo & shelat Expires 23 January 2027 [Page 35]
Internet-Draft Longfellow ZK July 2026
for (k, v) in QUAD_bind_p2.entries.items():
eval_p2 += v * VL_bind_p2[k[hand]] * VR[k[1 - hand]]
blinded_p0 = eval_p0 - layer_pad.evals[round][hand].p0
blinded_p2 = eval_p2 - layer_pad.evals[round][hand].p2
evals[round].append(SumcheckPolynomial(
blinded_p0,
blinded_p2,
))
transcript.write_field(blinded_p0)
transcript.write_field(blinded_p2)
challenge = transcript.generate_field(field)
G[hand].append(challenge)
# Bind the current index variable to the challenge.
VL = VL.bind(challenge)
QUAD = QUAD.bind(challenge, axis=hand)
# Swap VL and VR.
(VL, VR) = (VR, VL)
layer_proof = LayerProof(
evals,
VL[0] - layer_pad.vl,
VR[0] - layer_pad.vr,
)
transcript.write_field_element_array([
layer_proof.vl,
layer_proof.vr,
])
return (layer_proof, G)
6.7. Generate constraints from the public inputs and the padded proof
This section defines a procedure constraints_circuit for transforming
the proof returned by sumcheck_circuit into constraints to be checked
by the commitment scheme. Specifically, each layer produces one
linear constraint and one quadratic constraint. One additional
linear constraint is added after processing the input layer.
The main difficulty in describing the algorithm is that it operates
not on concrete witnesses, but on expressions in which the witnesses
are symbolic quantities. Symbolic manipulation is necessary because
the verifier does not have access to the witnesses. To avoid
overspecifying the exact representation of such symbolic expressions,
the convention is that the prefix sym_ indicates not a concrete
value, but a symbolic representation of the value. Thus, w[3] is the
fourth concrete witness in the w array, and sym_w[3] is a symbolic
representation of the fourth element in the w array. The algorithm
Frigo & shelat Expires 23 January 2027 [Page 36]
Internet-Draft Longfellow ZK July 2026
does not need arbitrarily complex symbolic expressions. It suffices
to keep track of affine symbolic expressions of the form k + SUM_{i}
a[i] sym_w[i] for some (concrete, nonsymbolic) field elements k and
a[].
def constraints_circuit(
field: FiniteField,
circuit: Circuit,
public_inputs: list[FiniteRingElement],
sym_private_inputs: Sequence[MPolynomial],
sym_pad: list[LayerPad[MPolynomial]],
transcript: Transcript,
proof: list[LayerProof]) -> tuple[
list[MPolynomial],
list[QuadraticConstraint],
]:
"""
Processes a sumcheck proof, and produces lists of constraints for
verification.
Linear constrants are returned as expressions of the form
`k + SUM_{i} a[i] sym_w[i]`, representing
`k + SUM_{i} a[i] sym_w[i] = 0`, and quadratic constraints are
returned as objects holding three variables, representing
`w_x * w_y = w_z`.
"""
for _ in range(MAX_BINDINGS):
# Discard initial challenges. These are reserved for possible
# future use.
_ = transcript.generate_field(field)
challenges = [
transcript.generate_field(field)
for _ in range(MAX_BINDINGS)
]
G = (
challenges[:circuit.log_num_outputs],
challenges[:circuit.log_num_outputs],
)
linear_constraints = []
quadratic_constraints = []
claim_0: MPolynomial | FiniteRingElement
claim_1: MPolynomial | FiniteRingElement
for j, layer in enumerate(circuit.layers):
alpha = transcript.generate_field(field)
beta = transcript.generate_field(field)
QZ = layer.quad + beta * layer.Z
QUAD = QZ.bindv(G[0]) + alpha * QZ.bindv(G[1])
QUAD = QUAD.drop_dimension()
Frigo & shelat Expires 23 January 2027 [Page 37]
Internet-Draft Longfellow ZK July 2026
if j == 0:
claim_0 = field.zero()
claim_1 = field.zero()
else:
claim_0 = claim_0 + sym_pad[j - 1].vl
claim_1 = claim_1 + sym_pad[j - 1].vr
(
G,
(claim_0, claim_1),
linear_constraint,
quadratic_constraint,
) = constraints_layer(
field,
QUAD,
layer.log_num_input_wires,
sym_pad[j],
transcript,
proof[j],
(claim_0, claim_1),
alpha,
)
linear_constraints.append(linear_constraint)
quadratic_constraints.append(quadratic_constraint)
# Add a constraint checking that the two final claims equal the
# binding of sym_inputs with G[0] and G[1].
gamma = transcript.generate_field(field)
# eq2 = bindv(EQ, G[0]) + gamma * bindv(EQ, G[1])
eq2 = [
a + gamma * b
for a, b in zip(
bindeq(field, G[0]),
bindeq(field, G[1]),
)
]
sym_layer_pad = sym_pad[-1]
num_private_inputs = circuit.ninputs - circuit.pub_in
final_constraint = (
sum(
(
eq2[i] * public_inputs[i]
for i in range(circuit.pub_in)
),
start=field.zero(),
)
+ sum(
(
eq2[i + circuit.pub_in] * sym_private_inputs[i]
Frigo & shelat Expires 23 January 2027 [Page 38]
Internet-Draft Longfellow ZK July 2026
for i in range(num_private_inputs)
),
start=field.zero(),
)
- claim_0
- sym_layer_pad.vl
- gamma * claim_1
- gamma * sym_layer_pad.vr
)
linear_constraints.append(final_constraint)
return linear_constraints, quadratic_constraints
def constraints_layer(
field: FiniteField,
QUAD: SparseArray,
log_num_input_wires: int,
sym_layer_pad: LayerPad[MPolynomial],
transcript: Transcript,
layer_proof: LayerProof,
claims: tuple[
MPolynomial | FiniteRingElement,
MPolynomial | FiniteRingElement,
],
alpha: FiniteRingElement) -> tuple[
tuple[list[FiniteRingElement], list[FiniteRingElement]],
tuple[FiniteRingElement, FiniteRingElement],
MPolynomial,
QuadraticConstraint,
]:
# Initial claim. This is a known constant during the first round,
# but it will be a symbolic affine expression in subsequent
# rounds.
sym_claim = claims[0] + alpha * claims[1]
# Lagrange basis polynomials
R = field["x"]
lag_0 = R.lagrange_polynomial([
(field.zero(), field.one()),
(field.one(), field.zero()),
(sumcheck_p2(field), field.zero()),
])
lag_1 = R.lagrange_polynomial([
(field.zero(), field.zero()),
(field.one(), field.one()),
(sumcheck_p2(field), field.zero()),
])
lag_2 = R.lagrange_polynomial([
(field.zero(), field.zero()),
Frigo & shelat Expires 23 January 2027 [Page 39]
Internet-Draft Longfellow ZK July 2026
(field.one(), field.zero()),
(sumcheck_p2(field), field.one()),
])
G: tuple[list[FiniteRingElement], list[FiniteRingElement]] = (
[],
[],
)
for round in range(log_num_input_wires):
for hand in range(2):
hp = layer_proof.evals[round][hand]
sym_hpad = sym_layer_pad.evals[round][hand]
transcript.write_field(hp.p0)
transcript.write_field(hp.p2)
challenge = transcript.generate_field(field)
G[hand].append(challenge)
# After decrypting, the polynomial evaluations are
# expected to be:
#
# p(P0) = hp.p0 + sym_hpad.p0
# p(P2) = hp.p2 + sym_hpad.p2
sym_p0 = hp.p0 + sym_hpad.p0
sym_p2 = hp.p2 + sym_hpad.p2
# Compute the implied evaluation, p(P1) = claim - p(P0),
# in symbolic form.
sym_p1 = sym_claim - sym_p0
# Given p(P0), p(P1), and p(P2), interpolate the new
# claim symbolically.
sym_claim = (
lag_0(challenge) * sym_p0
+ lag_1(challenge) * sym_p1
+ lag_2(challenge) * sym_p2
)
QUAD = QUAD.bind(challenge, axis=hand)
# Now the bound QUAD is a 1x1 array.
Q = QUAD.drop_dimension().drop_dimension()[()]
# We want to verify that
#
# sym_claim = Q * VL * VR
#
# where VL = layer_proof.vl + sym_layer_pad.vl
Frigo & shelat Expires 23 January 2027 [Page 40]
Internet-Draft Longfellow ZK July 2026
# and VR = layer_proof.vr + sym_layer_pad.vr
#
# To keep this constraint linear, we expand the multiplication,
# and replace sym_layer_pad.vl * sym_layer_pad.vr with
# sym_layer_pad.vl_vr, checking that these quantities are equal
# in a separate quadratic constraint.
linear_constraint = (
sym_claim - Q * (
layer_proof.vl * layer_proof.vr
+ layer_proof.vr * sym_layer_pad.vl
+ layer_proof.vl * sym_layer_pad.vr
+ sym_layer_pad.vl_vr
)
)
quadratic_constraint = QuadraticConstraint(
sym_layer_pad.vl,
sym_layer_pad.vr,
sym_layer_pad.vl_vr,
)
transcript.write_field_element_array([
layer_proof.vl,
layer_proof.vr,
])
return (
G,
(layer_proof.vl, layer_proof.vr),
linear_constraint,
quadratic_constraint,
)
7. Serializing objects
This section explains how a proof consists of smaller, related
objects, and how to serialize each such component. First, the
standard methods for serializing integers and arrays are used:
* write_size(n): serializes an integer in [0, 2^{24} - 1] that
represents the size of an array or an index into an array. The
integer is serialized in little endian order.
* write_array(arr): A variable-sized array is represented as type
array[] and serialized by first writing its length as a size
element, and then serializing each element of the array in order.
* write_fixed_array(arr): When the length of the array is explicitly
known to be n, it is specified as type array[n] and in this case,
the array length is not written first.
Frigo & shelat Expires 23 January 2027 [Page 41]
Internet-Draft Longfellow ZK July 2026
7.1. Serializing structs
When a section includes just a struct definition, it is serialized in
the natural way, starting from the top-most component and proceeding
to the last one, each component is serialized in order.
7.2. Serializing Field elements
This section describes a method to serialize field elements,
particularly when the field structure allows efficient encoding for
elements of subfields.
Before a field element can be serialized, the context must specify
the finite field. In most cases, the Circuit structure will specify
the finite field, and all other aspects of the protocol will be
defined by this field.
A finite field or FieldID is specified using a variable-length
encoding. Common finite fields have been assigned special 1-byte
codes. An arbitrary prime-order finite field can be specified using
the special 0xF_ byte followed by a variable number of bytes to
specify the prime in little-endian order. For example, the 3 byte
sequence f11001 specifies F_257. Similarly, a quadratic extension
using the polynomial x^2 + 1 can be specified using the 0xE_
designators.
Frigo & shelat Expires 23 January 2027 [Page 42]
Internet-Draft Longfellow ZK July 2026
+==============================+===========+
| Finite field | FieldID |
+==============================+===========+
| p256 | 0x01 |
+------------------------------+-----------+
| p384 | 0x02 |
+------------------------------+-----------+
| p521 | 0x03 |
+------------------------------+-----------+
| GF(2^128) | 0x04 |
+------------------------------+-----------+
| GF(2^16) | 0x05 |
+------------------------------+-----------+
| 2^128 - 2^108 + 1 | 0x06 |
+------------------------------+-----------+
| 2^64 - 59 | 0x07 |
+------------------------------+-----------+
| 2^64 - 2^32 + 1 | 0x08 |
+------------------------------+-----------+
| F_{2^64 - 59}^2 | 0x09 |
+------------------------------+-----------+
| secp256k1 | 0x0a |
+------------------------------+-----------+
| F_{2^({0--15})-byte prime}^2 | 0xe{0--f} |
+------------------------------+-----------+
| F_{2^({0--15})-byte prime} | 0xf{0--f} |
+------------------------------+-----------+
Table 1: Finite field identifiers.
The GF(2^128) field uses the irreducible polynomial x^128 + x^7 + x^2
+ x + 1. The p256 prime is equal to
115792089210356248762697446949407573530086143415290314195533631308867097853951,
which is the base field used by the NIST P256 elliptic curve. The
p384 prime is equal to
39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
which is the base field used by the NIST P384 curve. The p512 prime
is equal to 2^521 - 1. The F_p64^2 field is the quadratic field
extension of the base field defined by prime 18446744073709551557
using polynomial x^2 + 1, i.e. by injecting a square root of -1 to
the field.
7.2.1. Serializing a single field element
Unless specified otherwise, a field element, referred to as an Elt,
is serialized to bytes in little-endian order. For example, a
256-bit element of the finite field F_p256 is serialized into
32-bytes starting with the least-significant byte.
Frigo & shelat Expires 23 January 2027 [Page 43]
Internet-Draft Longfellow ZK July 2026
* write_elt(e, F): produces a byte encoding of a field element e in
field F.
7.2.2. Serializing an element of a subfield
In some cases, when both Prover and Verifier can explicitly conclude
that a field element belongs to a smaller subfield, then both parties
can use a more efficient sub-field serialization method. This
optimization can be used when the larger field F is a field extension
of a smaller field, and both parties can conclude that the serialized
element belongs to the smaller subfield.
* write_subfield(Elt e, F2, F1): produce a byte encoding of a field
element e that belongs to a subfield F2 of field F1.
7.3. Serializing a Sumcheck Transcript
struct {
PaddedTranscriptLayer layers[]; // NL layers
} PaddedTranscript;
struct {
Elt wires[]; // array of 2 * log_w Elts that store the
// evaluations of deg-2 polynomial at 0, 2
Elt wc0;
Elt wc1;
} PaddedTranscriptLayer;
The padded transcript incorporates the optimization in which the eval
at 1 is omitted and reconstructed from the expected value of the
previous challenge.
7.4. Serializing a Ligero Proof
def serialize_ligero_proof(C, ldt, dot, columns, mt_proof) {
write_array(ldt, C.BLOCK)
write_array(dot, C.BLOCK)
write_runs(columns, C.NREQ * C.NROW, C.subFieldID, C.FieldID)
write_merkle(mt_proof)
}
The concept of a run allows saving space when a long run of field
elements belong to a subfield of the Finite field. Runs consist of a
4-byte size element, and then size Elt elements that are either in
the field or the subfield. Runs alternate, beginning with full field
elements. In this way, rows that consist of subfield elements can
save space. The maximum run length is set to 2^25.
Frigo & shelat Expires 23 January 2027 [Page 44]
Internet-Draft Longfellow ZK July 2026
def write_runs(columns, N, F2, F) {
bool subfield_run = false
FOR 0 <= ci < N DO
size_t runlen = 0
while (ci + runlen < N &&
runlen < kMaxRunLen &&
columns[ci + runlen].is_in_subfield(F2) == subfield_run
) {
++runlen;
}
write_size(runlen, buf);
for (size_t i = ci; i < ci + runlen; ++i) {
if (subfield_run) {
write_subfield(columns[i], F2, F);
} else {
write_elt(columns[i], F);
}
}
ci += runlen;
subfield_run = !subfield_run;
}
def write_merkle(mt_proof) {
FOR (digest in mt_proof) DO
write_fixed_array(digest, HASH_LEN)
}
7.5. Serializing a Sequence of proofs
For the multi-field optimization, the proof string consists of a
sequence of two proofs. This is handled by using the circuit
identifier to specify the sequence of proofs to parse.
struct {
Public pub; // Public arguments to all circuits
Proof proofs[]; // array of Proof
} Proofs;
Frigo & shelat Expires 23 January 2027 [Page 45]
Internet-Draft Longfellow ZK July 2026
struct {
uint8 oracle[32]; // nonce used to define the random oracle,
Digest com; // commitment to the witness
PaddedTranscript sumcheck_transcript;
LigeroProof lp;
} Proof;
struct {
char* arguments[]; // array of strings representing
// public arguments to the circuit
} Public;
8. Security Considerations
Both the Ligero and Longfellow systems satisfy the standard
properties of a zero-knowledge argument system: completeness,
soundness, and zero-knowledge.
Frigo and shelat [longfellow] provide an analysis of the soundness of
the system, as it derives from the Soundness of the Ligero proof
system and the sumcheck protocol. Similarly, the zero-knowledge
property derives almost entirely from the analysis of Ligero
[ligero]. It is a goal to provide a mechanically verifiable proof
for a high-level statement of the soundness.
9. IANA Considerations
This document does not make any requests of IANA.
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker,
"Randomness Requirements for Security", BCP 106, RFC 4086,
DOI 10.17487/RFC4086, June 2005,
<https://www.rfc-editor.org/info/rfc4086>.
[RFC6919] Barnes, R., Kent, S., and E. Rescorla, "Further Key Words
for Use in RFCs to Indicate Requirement Levels", RFC 6919,
DOI 10.17487/RFC6919, April 2013,
<https://www.rfc-editor.org/info/rfc6919>.
Frigo & shelat Expires 23 January 2027 [Page 46]
Internet-Draft Longfellow ZK July 2026
10.2. Informative References
[GMR] Goldwasser, S., Micali, S., and C. Rackoff, "THE KNOWLEDGE
COMPLEXITY OF INTERACTIVE PROOF SYSTEMS", 1989.
[RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
(SHA and SHA-based HMAC and HKDF)", RFC 6234,
DOI 10.17487/RFC6234, May 2011,
<https://www.rfc-editor.org/info/rfc6234>.
[additivefft]
Lin, S., Chung, W., and Y. Han, "Novel polynomial basis
and its application to Reed-Solomon erasure codes", 2014,
<https://arxiv.org/abs/1404.3458>.
[ligero] Ames, S., Hazay, C., Ishai, Y., and M. Venkitasubramaniam,
"Ligero: Lightweight Sublinear Arguments Without a Trusted
Setup", 2022, <https://eprint.iacr.org/2022/1608>.
[longfellow]
Frigo, M. and a. shelat, "Anonymous credentials from
ECDSA", 2024, <https://eprint.iacr.org/2024/2010>.
Appendix A. Acknowledgements
Appendix B. Test Vectors
This section contains test vectors. Each test vector in specifies
the configuration information and inputs. All values are encoded in
hexadecimal strings.
B.1. Test Vectors for Merkle Tree
B.1.1. Vector 1
* Leaves:
4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a
dbc1b4c900ffe48d575b5da5c638040125f65db0fe3e24494b76ea986457d986
084fed08b978af4d7d196a7446a86b58009e636b611db16211b65a9aadff29c5
e52d9c508c502347344d8c07ad91cbd6068afc75ff6292f062a09ca381c89e71
e77b9a9ae9e30b0dbdb6f510a264ef9de781501d7b6b92ae89eb059c5ab743db
* Root:
f22f4501ffd3bdffcecc9e4cd6828a4479aeedd6aa484eb7c1f808ccf71c6e76
* Proof for leaves (0,1):
084fed08b978af4d7d196a7446a86b58009e636b611db16211b65a9aadff29c5
f03808f5b8088c61286d505e8e93aa378991d9889ae2d874433ca06acabcd493
Frigo & shelat Expires 23 January 2027 [Page 47]
Internet-Draft Longfellow ZK July 2026
* Proof for leaves (1,3):
e77b9a9ae9e30b0dbdb6f510a264ef9de781501d7b6b92ae89eb059c5ab743db
084fed08b978af4d7d196a7446a86b58009e636b611db16211b65a9aadff29c5
4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a
B.2. Test Vectors for Fiat-Shamir
Let
p=115792089237316195423570985008687907853269984665640564039457584007908834671663
and Fp be the 4-word field defined by p.
B.2.1. Vector 1: WriteBytes
* Description: Using Fp, the test steps are to (a) initialize the
transcript object with the 4-byte string test; (b) write an array
of bytes of size 100 that contains the integers 0, 1, 2, ..., 99;
(c) generate 16 field elements:
- 0x8b297f0bffd583c6c6b6796385d5fd20a08665733b833970ebdd1054bbbc1b14
- 0x0667c08ad7f38efec5f30dc8aa4f20d749cdcf96d63a770f9810ac5c0ca8dcb1
- 0xc8037fc12d4da00b5dc7597e3042f33f72a06f970cb71fb6b103ebb5419d8a6b
- 0xfbbcfa1eac48728fbfdacc1c21e2f78119457e0846337e46140e38e62856c4c5
- 0x5358ae603691cc759faeb572fb6642654ea1c3dbc8f81d00276dd8c4df95aa58
- 0x5266158c3c895dede5a23b6ce85a9f564b8059ebfcd1741f54497ec58189873e
- 0x3ecea4b2343c007fc32f2aff40dc7320945f101ecae5d52494db21ad326e9739
- 0x6462dd575e6b874118607212feec7ce5417ae3bf0f2e86604596f35d48bbaea2
- 0x6d56c703c369edea3595db6b958241580ae9b4a76fead961413ed9e9e5852dcd
- 0x6d31073cee650212a71b7b13e9f951e00ef3b14a008a79dd95047b26a4a83d06
- 0x1b9e2a6666da63c43e52227d91a8a7f0bd5311f63c2e3a18839133375639e6cb
- 0x332ea49dd23dd4745631ecbb15696192b1fa127256baf7a0483fd27db6f09a48
- 0x43e735927ccbdc4d5ce912675d638d6d3dc8eef3def34504304e938846f157d6
- 0xdc4a8868ae75e733a7257a8589230392a98d78594836dfccd01304742b5b3ad5
- 0x976353931711c634f2691e507b119fd7f6e653d419a2620676122db08db18765
- 0x332729ab436dca654866a9382deaee0add6fb7e90a80261f1488e56598e8bc99
B.2.2. Vector 2: WriteFieldElement
* Starting from the state at the end of Vector 1, (a) write the
field element '7' in Fp; (b) generate 16 field elements
- 0x609db3e9a8f548df038519fa46cef23eb8c6553d3c1f698604e60a51613a738e
- 0x1cb69cb31999eb88e83c7586aac53f5e3286b084b0cf9e43619b48df01e0a310
- 0x3bf36e3ddc690a1b12b417628c115959b373d056c90c42dc2417baf46f538868
- 0xe336594f29dcda52e48896517b5cdb2d062ffd861ab02db5f8ca197aacc635f6
- 0xc1f396a8bad16bb0f57da6d380402a25b571bd4691226d11449a741440e325c8
- 0x5195336ec73751de066e3a8939b40c3c5555f1a513486dfc50dcf4c2d47e6ff2
- 0x8dcf872f3ded2b7ed1d1ee9a2b125bedc6eacd3c09b3a4a5286d8fc2fc3a6634
- 0x950dd2ef7be25eab686a6688497962ee4ad521da12b9ff3d8e56ad9435885b12
- 0xe14389d1d8448678cac33fdbc9aab20dba019e75149d170dd2f353891cd4b84f
Frigo & shelat Expires 23 January 2027 [Page 48]
Internet-Draft Longfellow ZK July 2026
- 0xe84906c09cd6423865baf64e48027cc598d52bdb90b17524c87ea892e53b5200
- 0x493cea587f1ec5622c04221cd6e5a41c26c1c1c24c0375f7aaa367d9678d83bc
- 0x5aca0010aced30bcb3b84a7f10ea39c4269ab7c92fcb6cff52958d8921ef2cc5
- 0x4498fa8340f41467c0fa813bd0ca83ef6e1c4b85c7b1168a94339fd9e8296139
- 0xf9a95b738a8e775421b1baa503abbeed2d283b236ebba25e1954b3c993d30a3d
- 0x98178711d03a0b1204ebb56b37bd3a2724dfb08e4dc925609391768b126d21f2
- 0x79251f49534f5c4b10b798b2dbf6e80a3b07593f616ce6a9617ccc61040aac78
B.2.3. Vector 3: WriteFieldElementArray
* Starting from the state at the end of Vector 2, (a) write the
2-long array of field elements [8, 9]; (b) generate 16 field
elements:
- 0xae1a921288590205fc24543303ff527476359b8db4a983b2886a133b02f3217e
- 0x8c5d52a04b295f9fdb45ab66100fa00ca32c9634aa87cbbdb2bc3e1912459feb
- 0x12f82963b5b242156f6e9eb756eddee7652b60c7d6394403f7bd995e0b9bcd9c
- 0x880aa50b049b3939055deb7933749d338bb3fb5f64a9adf95019e6cfc232995c
- 0xf8558f693f0fa6df20a37147a898fb4c678831f566d80113bbe2cdcd18285da2
- 0xbbcc8d9b46f88bc8c6cec0ad2d5e49508b7db91d548548eddc61800de1329e1c
- 0x479a17244398caae8155a73438a22583df7de10a8a2e12ad53ddd3bc7305fac9
- 0x9ba1917f1227932250288a843f64b4e7b7f47a5fbc16c111f6e1f76235ccf38c
- 0xd1582138045d1636fb7f677c9e8a4a4143ce2b2bb54fb4f49fb0ad1fee5df6b4
- 0x5331e5b8508f79c017a8dfbbb805f3f8c5e3e4bc417e44849b9212439646331
- 0xb6b95862194ca52dcaa9ee651b7fc5b708f43feae108bb9a7f95213f4d069048
- 0xe86b1602f0a54c4e237867ebaf05e7581464fd238e50f6ed9c3cea63909c8e60
- 0xb7280439f3b21b113ff29cefe39292d5e2d137709c3d3cec36473a0f97a24e62
- 0xbeaa5e08257d232506fb3e46c6daa29e0859c34c7d0cd673bc6706ee261ae059
- 0x691ead55728cd087a1952b22b6628ba4e26fbefc8debeec5e6fbc3a16f637be
- 0x47dc31f6d8bc9c44290781176df3e4b95ac8793a4a42fa5859c564d92d6d5af5
B.2.4. Vector 4: Nat
* Starting from the state at the end of Vector 3, (a) write the
4-byte string "nats"; (b) call generate_nat with the following
list of parameters: [1, 1, 1, 2, 2, 2, 7, 7,7, 7, 32, 32, 32, 32,
256, 256, 256, 256, 1000, 10000, 60000, 65535, 100000, 100000].
The result of each call should correspond to the list of results:
- [0, 0, 0, 0, 0, 0, 3, 0, 4, 5, 10, 30, 27, 22, 100, 189, 3, 92,
999, 3105, 40886, 51590, 56367, 10678]
B.2.5. Vector 5: Choice
* Starting from the state at the end of Vector 4, (a) write the
6-byte string "choice"; (b) perform the following calls to
generate_natgenerate_nats_wo_replacement
- m=31, k=20: [10, 29, 30, 11, 4, 15, 16, 28, 19, 21, 25, 18, 17,
3, 5, 23, 24, 22, 6, 1]
Frigo & shelat Expires 23 January 2027 [Page 49]
Internet-Draft Longfellow ZK July 2026
- m=32, k=20: [3, 17, 18, 8, 30, 7, 14, 19, 25, 23, 12, 4, 31,
16, 0, 6, 20, 27, 11, 10]
- m=63, k=20: [9, 56, 61, 45, 35, 53, 51, 3, 39, 32, 31, 6, 59,
58, 54, 22, 27, 62, 55, 19]
- m=64, k=20: [12, 52, 39, 17, 51, 38, 58, 2, 28, 27, 46, 63, 61,
50, 40, 55, 47, 13, 56, 32]
- m=1000, k=20: [157, 668, 572, 138, 913, 994, 797, 249, 440,
723, 489, 241, 383, 108, 710, 341, 406, 585, 42, 692]
- m=65535, k=20: [40745, 48408, 17108, 44500, 53993, 10008,
24910, 52200, 61265, 54989, 41237, 25958, 28697, 61187, 34729,
3525, 9005, 38627, 9724, 12169]
B.3. Test Vectors for Circuit
B.3.1. Vector 1
* Description: Circuit C(n, m, s) = 0 if and only if n is the m-th
s-gonal number in F_p128. This circuit verifies that 2n =
(s-2)m^2 - (s - 4)*m.
* Field: 2^128 - 2^108 + 1 (Field ID 6)
* Depth: 3 Quads: 11 Terms: 11
* Serialization:
01060000010000010000020000040000020000040000ffffffffffffffffffffffffffefffff00000000000000000000000000f0ffff01000000000000000000000000000000fdffffffffffffffffffffffffefffff030000060000030000000000020000000000000000000000080000040000010000000000030000020000020000020000040000080000000000000000000000020000060000000000000000000000040000000000000000030000090000020000000000020000020000020000000000020000020000020000000000020000040000000000000000020000030000030000040000020000
B.4. Test Vectors for Sumcheck
B.4.1. Vector 1
* Description: Circuit C(n, m, s) = 0 if and only if n is the m-th
s-gonal number in F_p128. This circuit verifies that 2n =
(s-2)m^2 - (s - 4)*m.
* Field: 2^128 - 2^108 + 1 (Field id 6)
* Fiat-Shamir initialized with
* Serialization:
90e734c42b5f14ee432a0ed95ba2ada05c3f9ecc9b026ded61f00bf57434f93c6f70e9c8b6e3de005ba8b4da93b5fa35fc3efae1e6068399c7f7d009ab5a2711084c97cd5a6e28dd30c598907b328d81915e487c34dbf80aa5da14f0621011a33d838a7b0d9a03533c63c6606f5360f88cf97c728630afdcb9755894a6f5c9068e1fc29f97efc125ba580de64089c6e72433de2a3267b90daeaf418ac8a3df3bbddc6cb141c764c8262346baac2e28033778b1a71f153ba571e80ab29951f9440ba93fede225a35accf6e0114d5240ae92df02d2870e5258ebba416f3d815e1554b05627998fc9d3bf354b89394b27b39f69c6538dbc968a779369e47f214252e0955624e9f4d6dc2a95cf41c57703b8749b959315458d4076f0daf5fdbde23e16c10394ac884ab9cad0782e8f472cb4edb69682d17465363691aafc31b83cd764fb909b50e2fe907fd2137566ddb8c47cc13974957e7f76180860571035f7a4d2658a82e1be8fe155353bc10feae9541365926f0646b4a5351907cbd5d9dbb4
B.5. Test Vectors for Ligero
B.5.1. Vector 1
* Description: Circuit C(n, m, s) = 0 if and only if n is the m-th
s-gonal number in F_p128. This circuit verifies that 2n =
(s-2)m^2 - (s - 4)*m.
* Field: 2^128 - 2^108 + 1 (Field id 6)
* Witness vector: [1, 45, 5, 6]
* Pad elements: [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 4]
* Parameters:
Frigo & shelat Expires 23 January 2027 [Page 50]
Internet-Draft Longfellow ZK July 2026
- NREQ: 6
- RATE: 4
- WR: 20
- QR: 2
- NROW: 7
- NQ: 1
- BLOCK: 51
* Commitment:
738d2ffb3a8bf24e7aedb94be59041fb2dc13da30fe6b05ebe5126ef8fc36ec2
* Proof size: 3180 bytes
* Proof:
fa8d88a73b3a0f9c067658c45bb394a602000000000000000000000000000000fa8d8...2cd5f61cd2b2eb84c79e1707cbad0048fcd820c716584f31991cf1628fb041
B.6. Test Vectors for libzk
Authors' Addresses
Matteo Frigo
Google
Email: matteof@google.com
abhi shelat
Google
Email: shelat@google.com
Frigo & shelat Expires 23 January 2027 [Page 51]