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, . [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, DOI 10.17487/RFC4086, June 2005, . [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, . 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, . [additivefft] Lin, S., Chung, W., and Y. Han, "Novel polynomial basis and its application to Reed-Solomon erasure codes", 2014, . [ligero] Ames, S., Hazay, C., Ishai, Y., and M. Venkitasubramaniam, "Ligero: Lightweight Sublinear Arguments Without a Trusted Setup", 2022, . [longfellow] Frigo, M. and a. shelat, "Anonymous credentials from ECDSA", 2024, . 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]