Introduction

Vega is a zero-knowledge proof system for proving statements about existing signed credentials. A prover can hold signed data, such as a mobile driver’s license, and convince a verifier that a statement about that data is true without revealing anything beyond the statement. The implementation targets client devices, low proving latency, repeated presentations over the same signed data, and transparent setup.

What this book specifies

This book has two purposes.

1. It explains the design of Vega and the building blocks used by \(\mathrm{Vega}_{\mathrm{MC}}\), the multi-circuit prover: fields and groups, R1CS, Fiat–Shamir transcripts, sum-check, folding, polynomial commitments, and the verifier circuit.
2. It gives a specification precise enough for an independent team to build a prover whose proof bytes are accepted by the Vega verifier.

The focus is the multi-circuit, or MC, variant of the prover. The single-circuit variants exist in the repository, but they are outside the main line of this book.

Two implementations

The repository contains two implementations of \(\mathrm{Vega}_{\mathrm{MC}}\), and this book describes both.

• The Rust implementation is the production system: the optimized, low-latency prover and verifier that applications run, and the deployed verifier a proof must satisfy.
• The Python implementation, under reference/, is a simpler, unoptimized companion. It computes each value in the most direct way — favoring clarity over speed — and currently proves only the small worked example used throughout the book. It serves as an executable specification and is validated by mutual acceptance with the Rust implementation.

The two agree on every byte the verifier consumes, so either verifier accepts the other prover’s proofs. To keep the distinction crisp, this book calls the Python code the reference implementation (or reference prover) and the optimized code the Rust implementation (or shipped prover/verifier).

The problem Vega addresses

Digital credentials are often already issued and signed by systems that were not designed for zero knowledge. Vega works over those existing credentials rather than requiring a new credential format or a trusted setup ceremony. Its proving strategy is built around repeated structure: the same signed data may be presented many times, and many hashing or parsing steps have uniform circuit shape.

Vega uses fold-and-reuse proving. Repeated work across presentations is pushed into a rerandomizable precomputation. Uniform step-circuit instances are folded into one instance. For zero knowledge, the public-coin verifier-circuit instance is folded with a fresh random satisfying instance in every proof. Credential-specific arithmetization, such as lookup-heavy extraction from signed bytes, motivates the system but is outside this book; the proof system treats circuits abstractly.

Byte-equivalence contract

The specification chapters pin down the deterministic wire format and the Fiat–Shamir transcript schedule. An independent prover that follows those chapters produces proof bytes that the real Vega verifier accepts. When the independent prover and the reference prover are driven with identical inputs and identical randomness, their proofs are byte-identical. Across two honest zero-knowledge proofs for the same statement, the expected differences come from the fresh randomness used for hiding and rerandomization.

How to read this book

Readers learning the system should start with the design goals, architecture, and proving lifecycle, then read the building-block chapters as needed. Implementers should read the same overview, then proceed to the MC chapters and the specification scope, which explains where byte-level requirements begin.

Design goals and threat model

This chapter states the goals Vega optimizes for and the security properties expected from the multi-circuit proof system. It also separates the proof system from application-specific credential circuits.

Design goals

Low proving latency on client devices

Vega is designed for a prover running on a client device. The repository targets statements over signed data and optimizes for low zero-knowledge proving latency rather than batch throughput. \(\mathrm{Vega}_{\mathrm{MC}}\) supports this goal by moving reusable work out of the online presentation path and by folding many uniform step instances before proving the verifier’s algebraic checks.

Repeated presentations over the same signed data

A credential holder may present statements about the same signed data many times. Vega exposes a prep_prove phase that builds precommitted state for the step and core circuits. Later proofs rerandomize that state, so the prover reuses expensive preparation while producing fresh zero-knowledge proofs.

No trusted setup

The canonical implementation uses an engine whose polynomial commitment is Hyrax and whose transcript is Fiat–Shamir over Keccak256. The setup phase derives commitment material and circuit shapes from public parameters and the circuits; it does not rely on a toxic-waste setup ceremony.

Transparent, standard assumptions

Vega’s proof-system checks are expressed through R1CS, sum-check, folding, and an inner-product opening for homomorphic commitments. Security is reduced to the soundness of these algebraic protocols, the binding and hiding properties of the commitments, and the random-oracle-style Fiat–Shamir transform used to derive challenges.

Zero knowledge

A proof should reveal only that the public statement is true. Vega combines hiding commitments, a zero-knowledge opening argument, rerandomized precommitted state, and a final fold with a fresh random satisfying verifier-circuit instance. The random instance is sampled per proof, not once per setup.

Threat model and properties

What the proof establishes

Completeness means an honest prover with satisfying witnesses for the step circuits and the core circuit produces a proof accepted by the verifier. Soundness means a prover cannot convince the verifier unless the folded R1CS claims, the in-circuit verifier checks, and the committed witness openings are mutually consistent for the public statement encoded by the circuits.

The verifier learns the public input/output values returned by verification. For \(\mathrm{Vega}_{\mathrm{MC}}\), these include per-step public values and core public values.

What remains hidden

Zero knowledge hides private witnesses and credential contents that are not part of the public statement. The verifier sees commitments, folded instances, algebraic proof messages, and public values, but the hiding commitments and fresh per-proof randomness prevent these objects from identifying the underlying witness beyond the statement being proven.

What the verifier must trust

The verifier must use the intended verifier key. The verifier key contains the commitment verifier key, the step and core R1CS shapes, the verifier-circuit shape and key, and the number of step instances. The transcript is bound to a digest of this verifier key, so proofs are tied to the circuit shapes and parameters represented by that key.

What is out of scope

This book specifies the proof system. It does not specify how a credential format is parsed, how signatures are represented inside an application circuit, or which lookup-centric arithmetization is best for extracting values from credential bytes. Those choices determine the step and core circuits supplied to Vega; the proof system treats them as R1CS-producing circuits.

For the static structure of these components, continue to System architecture. For the runtime flow, continue to The proving lifecycle.

System architecture

This chapter describes the static components of \(\mathrm{Vega}_{\mathrm{MC}}\) and how data moves between them. Byte encodings and transcript order are deferred to the specification chapters.

Component diagram

The MC proof system is organized as the following components.

• Engine. The engine fixes the scalar field \(\mathbb{F}\), group \(\mathbb{G}\), Fiat–Shamir transcript, and polynomial commitment scheme. The canonical instantiation is T256HyraxEngine: T256 group, T256 scalar field, Keccak256 transcript, and Hyrax commitments. See Fields, groups, and the engine and The Fiat–Shamir transcript.
• Step circuit and core circuit. The application supplies a uniform step circuit \(C_1\), a core circuit \(C_2\), and a number of steps. Setup synthesizes both into split R1CS shapes. The step shape is instantiated many times; the core shape connects the batch. See R1CS and its variants.
• Sum-check. Sum-check reduces large multilinear claims about R1CS satisfaction to evaluations at verifier challenges. Vega uses a constraint-batching challenge \(\tau\), folding challenges \(\rho\), and round challenges such as \(r_x\) and \(r_y\). See The sum-check protocol.
• NeutronNova folding. Folding compresses many regular step R1CS instances into one folded instance and witness. The verifier later recomputes the same folding challenges from the transcript. See NeutronNova folding.
• In-circuit verifier. A second R1CS circuit checks the algebraic work performed by folding and sum-check. Its public input records the challenges and selected final values that the outer verifier recomputes. See The in-circuit verifier.
• Commitment and zero-knowledge opening. Hyrax commitments bind the witness vectors and support homomorphic folding. A zero-knowledge evaluation argument opens the folded witness commitment at the point required by the verifier. See Polynomial commitments and the ZK opening.

Data flow

Setup starts from \(C_1\), \(C_2\), and num_steps. It produces a prover key containing the split R1CS shapes, commitment key, verifier-circuit shape, and digest of the verifier key. It also produces a verifier key containing the corresponding verifier material and the number of step instances.

Preparation evaluates the shared and precommitted parts of the step and core witnesses. The resulting precommitted state is reusable because the online proof phase rerandomizes it before deriving proof objects.

Proof generation turns each prepared step circuit and the core circuit into split R1CS instances. The step instances share one commitment to the shared witness. The prover converts the split instances to regular instances for folding, folds the step batch, runs the outer and inner sum-checks for the folded step branch and the core branch, and records the verifier’s algebraic checks inside the verifier circuit.

After the verifier-circuit instance is built, the prover samples a fresh random satisfying relaxed instance and folds it with the real verifier-circuit instance. A single relaxed R1CS proof establishes satisfaction of the folded instance. A Hyrax/IPA evaluation argument opens the folded committed witness value used by the verifier checks.

Verification reconstructs the shared commitment, validates all public instances against the verifier key, recomputes transcript challenges, folds the step instances, verifies the folded verifier-circuit proof, recomputes the matrix-evaluation checks, and verifies the Hyrax opening. If all checks pass, it returns the step and core public values.

The runtime phases are described next in The proving lifecycle. Byte-level proof layout begins in Specification scope.

The proving lifecycle

This chapter follows the runtime path of the MC proof system. It describes what each public API phase consumes and produces, while the byte-level format is left to Specification scope.

Phase 1: setup

setup consumes a step circuit \(C_1\), a core circuit \(C_2\), and num_steps. The number of steps is the number of step instances that the verifier key is bound to; the implementation requires at least two step instances and pads internally where folding needs a power of two.

Setup synthesizes split R1CS shapes for \(C_1\) and \(C_2\), equalizes their split layouts, derives commitment material, constructs the verifier-circuit shape, and computes the verifier-key digest. It produces a prover key and verifier key.

Phase 2: prep_prove

prep_prove consumes the prover key, the concrete step circuits for one presentation batch, the core circuit, and the is_small optimization flag. It constructs the shared witness from the first step circuit, then constructs precommitted witness state for each step circuit and for the core circuit.

This is the first place where fold-and-reuse appears. The prepared state can be reused across presentations over the same signed data because the online proof phase rerandomizes the commitments before producing a proof. When the step shape has no challenge-dependent or rest variables, preparation also caches deterministic matrix-vector products for later folding.

Phase 3: prove

prove consumes the prover key, the step circuits, the core circuit, and a prepared state. It rerandomizes the prepared state in place, so each presentation receives fresh hiding randomness while retaining the expensive precomputation.

The prover then creates split R1CS instances and witnesses for every step circuit and for the core circuit. It folds the step instances with NeutronNova-style folding, using transcript-derived \(\tau\) and \(\rho\) challenges. It runs the outer and inner sum-checks for the folded step branch and the core branch, and it feeds the verifier’s algebraic checks into the MC verifier circuit.

For zero knowledge, the prover samples a fresh random satisfying relaxed instance for the verifier circuit and folds the real verifier-circuit instance with it. The prover proves satisfaction of the resulting relaxed instance and produces a zero-knowledge Hyrax/IPA opening for the committed witness evaluation needed by the checks.

The output proof contains the shared witness commitment, per-step split instances, a core instance, the verifier-circuit instance, the random relaxed instance, the folding proof for the verifier-circuit instance, the relaxed R1CS proof, and the Hyrax evaluation argument. The consumed prepared state is returned so the caller can reuse it.

Phase 4: verify

verify consumes the proof, the verifier key, and the expected number of step instances. It rejects if the proof’s step count is zero, differs from the supplied count, or differs from the count bound into the verifier key.

The verifier restores the shared commitment into the step and core instances, validates those instances against the verifier key, rebuilds the Fiat–Shamir transcript, recomputes \(\tau\), \(\rho\), and later sum-check challenges, and folds the step instances. It verifies the folded verifier-circuit proof, recomputes the matrix and public-value checks, and verifies the Hyrax evaluation argument.

If all checks pass, verification returns the per-step public values and the core public values. These values are the public statement exposed by the proof-system layer; application meaning is assigned by the circuits supplied to setup and proving.

Notation and conventions

This chapter fixes the notation and conventions used throughout the book. Every later chapter assumes them. The pedagogical chapters use this notation to build intuition; the specification chapters additionally fix exact byte encodings, on top of the mathematical objects defined here.

Fields and the group

Vega operates over a prime-order elliptic-curve group \(\mathbb{G}\) with scalar field \(\mathbb{F}\). Unless stated otherwise, all arithmetic of the proof system — witnesses, constraints, sum-check messages, and Fiat–Shamir challenges — happens in \(\mathbb{F}\).

• \(\mathbb{F}\): the scalar field of \(\mathbb{G}\), a prime field of order roughly \(2^{256}\). Field elements are written with lowercase italic letters, e.g. \(a, b, r, \tau, \rho\). Every element serializes to a fixed 32 bytes (the exact encoding is fixed in Serialization and encodings).
• \(\mathbb{G}\): the group, written additively. Group elements (curve points) are written with uppercase italic letters, e.g. \(P, Q\). Fixed public generators are written \(G, H, G_1, G_2, \dots\).
• The canonical instantiation fixes \(\mathbb{G}\) to the T256 curve and \(\mathbb{F}\) to its scalar field; see Fields, groups, and the engine.

Prover variants

Vega has two prover variants. \(\mathrm{Vega}_{\mathrm{MC}}\) is the multi-circuit prover: it folds many uniform step circuits together before proving, and it is the focus of this book. \(\mathrm{Vega}_{\mathrm{SC}}\) is the single-circuit prover it builds on. Unqualified, “the prover” means \(\mathrm{Vega}_{\mathrm{MC}}\).

Vectors, matrices, and indexing

• Vectors are bold lowercase, e.g. \(\mathbf{z}\); their entries are \(z_0, z_1, \dots\). All indices are 0-based.
• Matrices are uppercase, e.g. \(A, B, C\); the entry in row \(i\), column \(j\) is \(A_{i,j}\).
• \(\mathbf{a} \circ \mathbf{b}\) is the entrywise (Hadamard) product, and \(\langle \mathbf{a}, \mathbf{b}\rangle = \sum_i a_i b_i\) is the inner product.
• Bit-strings live in \(\{0,1\}^\ell\). An integer \(i \in \{0, \dots, 2^\ell - 1\}\) is identified with its bits least-significant-bit first: \(i = \sum_{k=0}^{\ell-1} i_k\, 2^k\), so \(i_0\) is the low bit. This LSB-first convention is used consistently for hypercube indexing.

The Boolean hypercube and multilinear extensions

A function \(f : \{0,1\}^\ell \to \mathbb{F}\) on the Boolean hypercube has a unique multilinear extension (MLE) \(\tilde{f} : \mathbb{F}^\ell \to \mathbb{F}\) that agrees with \(f\) on \(\{0,1\}^\ell\) and has degree at most one in each variable: \[ \tilde{f}(\mathbf{r}) \;=\; \sum_{\mathbf{x} \in \{0,1\}^\ell} \widetilde{\mathrm{eq}}(\mathbf{r}, \mathbf{x})\; f(\mathbf{x}). \] A vector \(\mathbf{v} \in \mathbb{F}^{2^\ell}\) is routinely identified with the function \(i \mapsto v_i\) and hence with its MLE \(\tilde{v}\). See the multilinear extensions primer for background.

Special polynomials

• Equality polynomial. For \(\mathbf{r}, \mathbf{x} \in \mathbb{F}^\ell\), \[ \widetilde{\mathrm{eq}}(\mathbf{r}, \mathbf{x}) \;=\; \prod_{k=0}^{\ell-1}\bigl(r_k x_k + (1 - r_k)(1 - x_k)\bigr). \] It is the MLE of the indicator \([\mathbf{r} = \mathbf{x}]\) on the hypercube.
• Powers polynomial. A challenge \(\tau \in \mathbb{F}\) induces the consecutive powers \(\bigl(1, \tau, \tau^2, \dots, \tau^{2^\ell - 1}\bigr)\) as weights on the hypercube: the Boolean point with index \(i\) receives weight \(\tau^i\). These weights are assembled from the \(\ell\) per-variable factors \(\tau^{2^0}, \tau^{2^1}, \dots, \tau^{2^{\ell-1}}\), whose product over the set bits of \(i\) reproduces \(\tau^i\). They batch many constraints into one; the precise definition and role are given in The sum-check protocol.

R1CS objects

A rank-1 constraint system (R1CS) over \(\mathbb{F}\) is given by matrices \(A, B, C \in \mathbb{F}^{m \times n}\). A vector \(\mathbf{z} \in \mathbb{F}^{n}\) satisfies it when \[ (A\mathbf{z}) \circ (B\mathbf{z}) \;=\; C\mathbf{z}. \] The vector \(\mathbf{z}\) is partitioned into a constant \(1\), the public input/output \(\mathbf{x}\), and the private witness \(\mathbf{w}\); the exact layout, together with the split, multi-round, and relaxed variants that Vega uses, is fixed in R1CS and its variants.

Commitments

\(\mathrm{Com}(\mathbf{v}; \rho)\) denotes a hiding commitment to a vector \(\mathbf{v}\) under blind \(\rho\). Vega uses an additively homomorphic Pedersen/Hyrax commitment, so \(\mathrm{Com}(\mathbf{a}; \rho_a) + \mathrm{Com}(\mathbf{b}; \rho_b) = \mathrm{Com}(\mathbf{a} + \mathbf{b}; \rho_a + \rho_b)\). When \(\mathbf{v}\) is long enough to span several committed rows, the blind is correspondingly a tuple with one scalar per row, and \(\rho\) denotes that tuple; a single-row commitment uses one scalar. The commitment key, the reshaping of long vectors, and the opening argument are described in Polynomial commitments and the ZK opening.

The transcript and challenges

Interactive protocols are made non-interactive with the Fiat–Shamir transform against a single running transcript. Two operations act on it:

• absorb(label, value) folds labeled data into the transcript;
• squeeze(label) derives the next verifier challenge in \(\mathbb{F}\).

Challenges are written with Greek letters — \(\tau\) (constraint batching), \(\rho\) (instance folding), and \(r\) with subscripts \(r_b, r_x, r_y\) (sum-check round challenges). The transcript’s exact byte-level behavior and the full ordered schedule of absorb/squeeze calls are fixed in The transcript schedule; reproducing that schedule exactly is what lets an independent prover derive identical challenges.

Logarithms, padding, and powers of two

• \(\log\) is base 2; we write \(\ell = \log_2 n\).
• Where an object’s size is not already a power of two, it is padded to the next power of two. The specific padding rule (what value is used and where) is stated in each place it matters, because it affects the committed and hashed bytes.

Fields, groups, and the engine

This chapter explains the algebraic choices collected by a Vega engine. An engine fixes the field and group in which the proof system operates, and it also selects the transcript and polynomial-commitment machinery used by the surrounding protocols.

What an engine fixes

Vega writes \(\mathbb{G}\) for the prime-order elliptic-curve group and \(\mathbb{F}\) for its scalar field. The engine binds these objects together as associated types:

• a base field for the curve coordinates;
• the scalar field \(\mathbb{F}\), used for proof-system arithmetic;
• the group \(\mathbb{G}\), whose scalar field is \(\mathbb{F}\);
• a Fiat–Shamir transcript engine;
• a polynomial-commitment scheme over scalars in \(\mathbb{G}\).

The base field is the field in which curve coordinates live. The scalar field is the field used by witnesses, constraints, multilinear polynomials, sum-check messages, and verifier challenges. These two fields need not be the same field, even when they have the same size scale.

The transcript engine is described in The transcript. The commitment scheme is described in Polynomial commitments and the ZK opening. Byte encodings are intentionally separate from the algebraic engine definition; see Encodings and Serialization and encodings.

The canonical instantiation

The canonical engine is T256HyraxEngine. It fixes

\[ \mathbb{G} = \text{T256}, \]

uses the T256 scalar field as \(\mathbb{F}\), uses a Keccak256-based Fiat–Shamir transcript, and uses the Hyrax polynomial-commitment scheme.

T256 is an elliptic curve in short-Weierstrass form, with group parameters exposed as coefficients \(A\), \(B\), the group order, and the base-field order. Its scalar field — the field \(\mathbb{F}\) used for all proof-system arithmetic — has prime order equal to the group order,

\[ p_{\mathrm{scal}} = \mathtt{0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff}, \]

and its base field, in which curve coordinates live, has prime order

\[ p_{\mathrm{base}} = \mathtt{0xffffffff0000000100000000000000017e72b42b30e7317793135661b1c4b117}. \]

Thus \(\mathbb{F} = \mathbb{F}_{p_{\mathrm{scal}}}\) for the canonical engine. Field elements are roughly 256 bits; the exact byte representation is specified in Serialization and encodings, not in this chapter.

The curve equation is \(y^2 = x^3 + Ax + B\) over \(\mathbb{F}_{p_{\mathrm{base}}}\), with

\[ A = p_{\mathrm{base}} - 3, \qquad B = \mathtt{0xb441071b12f4a0366fb552f8e21ed4ac36b06aceeb354224863e60f20219fc56}, \]

and cofactor one, so \(|\mathbb{G}| = p_{\mathrm{scal}}\). Its standard base point is

\[ G = \big(,3,\ \mathtt{0x5a6dd32df58708e64e97345cbe66600decd9d538a351bb3c30b4954925b1f02d},\big). \]

The commitment generators the prover uses are not this base point; they are derived by hashing, as Setup describes.

Relationship to P256

The scalar field of T256 coincides with the base field of the standard P256 curve:

\[ \text{T256 scalar field} = \text{P256 base field} = \mathbb{F}_{p_{\mathrm{scal}}}. \]

This shared prime is the only field the two curves have in common. The base field of T256 is a distinct prime and does not equal the scalar field of P256, so the pair form a one-directional chain rather than a full two-curve cycle. All proof-system arithmetic in the canonical engine takes place in \(\mathbb{F} = \mathbb{F}_{p_{\mathrm{scal}}}\); the group \(\mathbb{G} = \text{T256}\) supplies the commitment generators described below.

Group operations used by commitments

Vega uses \(\mathbb{G}\) additively. A scalar multiplication is written \(aG\), and a multi-scalar multiplication has the form

\[ \sum_i a_i G_i. \]

Hyrax commitments use this operation to commit to rows of a vector. For a row \((v_0, \dots,v_{m-1})\) and commitment-key generators \(G_0, \dots,G_{m-1}\), the non-hiding part is the MSM

\[ \sum_{i=0}^{m-1} v_i G_i. \]

The commitment key also contains a dedicated hiding generator \(h\). A blind \(\rho \in \mathbb{F}\) contributes the term \(\rho h\), so a row commitment has the conceptual form

\[ \sum_{i=0}^{m-1} v_i G_i + \rho h. \]

This additive form is the algebraic reason that commitments can be combined homomorphically, as summarized in Notation and conventions and used by Polynomial commitments and the ZK opening.

Byte encodings and serialization

This chapter specifies the primitive byte encodings used when algebraic objects are absorbed into the Fiat–Shamir transcript, and the inverse map used when transcript output is interpreted as a scalar challenge. The algebraic objects themselves are defined in Fields, groups, and the engine. The transcript operations that consume these bytes are described in The Fiat–Shamir transcript.

These encodings are not the proof-object wire format. The proof envelope and its serialized layout are specified separately in Serialization and encodings.

Transcript representation

Every value that can be absorbed into the transcript has a canonical byte string, exposed by to_transcript_bytes(). Absorbing a value appends the caller-supplied label followed immediately by this byte string to the running hash state.

There is no length prefix, domain separator, or delimiter between the label and the value bytes. There is also no delimiter between successive absorbed values. Unambiguous transcript construction therefore comes from the fixed protocol schedule and fixed-width primitive encodings, not from self-describing byte strings.

This chapter specifies the primitive encodings: scalar-field elements, base-field elements, group elements, and slices of these. Aggregate objects — such as polynomials, commitments, and R1CS instances — implement their own to_transcript_bytes in terms of these primitives, and some add internal structure. For example, a Hyrax commitment brackets its point bytes with the literal marker strings poly_commitment_begin and poly_commitment_end, and a univariate polynomial is absorbed in a compressed form that omits its linear coefficient and uses the field backend’s native byte order. Those composite encodings are given below: the Hyrax commitment and round-polynomial encodings, then the R1CS instance encodings. They are transcript encodings, distinct from the proof wire format in Serialization and encodings, which serializes some of the same structs in a different field order.

Fixed-width primitive encodings

In the canonical engine, scalar-field elements and base-field elements occupy 32 bytes. An uncompressed group element occupies 64 bytes.

scalar in F        32 bytes    canonical integer, big-endian
base-field elem    32 bytes    canonical integer, little-endian
point in G         64 bytes    x-coordinate || y-coordinate (each a 32-byte little-endian base-field element)
slice &[T]          variable    enc(T[0]) || enc(T[1]) || ... || enc(T[n-1])
challenge scalar   64 bytes -> scalar by little-endian reduction mod p_scal

The scalar, base-field, point, and slice encodings in this table are transcript input encodings. Scalars and base-field elements use opposite byte orders, for the backend reason explained below. The challenge-scalar line is the transcript output decoding rule and uses little-endian byte order, as described at the end of the chapter.

Scalar-field elements

A scalar \(s \in \mathbb{F}\) is encoded as its canonical integer representative in \([0,p_{\mathrm{scal}})\), written as exactly 32 bytes in most-significant-byte-first order.

Equivalently:

enc_scalar(s) = be32(integer representative of s)

The to_transcript_bytes implementation takes the field backend’s native canonical byte representation and reverses it. The scalar field’s native representation is 32 little-endian bytes, so the scalar transcript encoding is big-endian.

Base-field elements

A base-field element is encoded by the same to_transcript_bytes reversal, but the base field’s native byte order is the opposite of the scalar field’s. The base field’s native canonical representation is 32 big-endian bytes, so reversing it yields a little-endian transcript encoding. A base-field element is therefore written as exactly 32 bytes in least-significant-byte-first (little-endian) order — the opposite of the scalar encoding.

enc_base(x) = le32(integer representative of x)

This is the coordinate encoding used inside group-element encodings.

Group elements

A group element is encoded in uncompressed affine form. If the input point is projective, it is first converted to affine form. Its affine coordinates are then encoded as base-field elements and concatenated:

enc_point(P) = enc_base(P.x) || enc_base(P.y)

The result is exactly 64 bytes: 32 bytes for the x-coordinate followed by 32 bytes for the y-coordinate. The affine and projective transcript encodings of the same group element are identical.

There is no compressed-point encoding. The encoding reads the affine coordinates of the point, so the identity (point at infinity), which has no affine coordinates, has no byte encoding — the implementation fails rather than emitting bytes for it. In the protocol, points absorbed into the transcript are non-identity commitments.

Slices and vectors

A slice &[T] of transcript-encodable values is encoded as the in-order concatenation of each element’s transcript bytes:

enc_slice([v0, v1, ..., v(n-1)]) =
    enc(v0) || enc(v1) || ... || enc(v(n-1))

There is no length prefix and no separator between elements. A vector of \(n\) scalars therefore encodes to exactly 32 * n bytes. A vector of \(n\) group elements encodes to exactly 64 * n bytes.

As with individual absorbs, the protocol schedule supplies the expected lengths and types. These slice encodings are not self-delimiting.

Commitments and round polynomials

A Hyrax commitment is absorbed as its point bytes bracketed by two literal ASCII marker strings:

enc(commitment) = "poly_commitment_begin"              (21 ASCII bytes)
               || enc(P_0) || enc(P_1) || ... || enc(P_{k-1})
               || "poly_commitment_end"                (19 ASCII bytes)

The markers are the raw ASCII bytes of those strings, absorbed inline with no length prefix. Each P_i is one row of the commitment, encoded as a 64-byte uncompressed point (the point in G primitive above).

A round polynomial produced by a sum-check is absorbed in compressed form. Compression drops the degree-1 (linear) coefficient — the verifier reconstructs it from the running claim — and encodes each remaining coefficient in little-endian byte order, the field backend’s canonical representation, rather than the big-endian form used for a standalone scalar. A degree-\(d\) round polynomial contributes \(d\) coefficients:

enc(round poly, degree d) = le(c_0) || le(c_2) || le(c_3) || ... || le(c_d)

Here le(c) is the 32-byte little-endian representation of coefficient c, and the degree-1 coefficient c_1 is omitted. A quadratic round polynomial contributes le(c_0) || le(c_2); a cubic one contributes le(c_0) || le(c_2) || le(c_3). This is the one place a composite transcript encoding departs from the big-endian scalar convention.

R1CS instances

The transcript schedule absorbs two composite instance types. A plain R1CSInstance — the core instance and each step instance in Phase B, and the real verifier instance U2 in Phase D — concatenates its witness commitment and its public-input slice:

enc(R1CSInstance) = enc(comm_W) || enc_slice(X)

A RelaxedR1CSInstance — the random mask U1 in Phase D — adds the error-vector commitment and the relaxation scalar:

enc(RelaxedR1CSInstance) = enc(comm_W) || enc(comm_E) || enc_scalar(u) || enc_slice(X)

Here enc(comm_W) and enc(comm_E) are the Hyrax commitment transcript encodings (bracketed point bytes; see Polynomial commitments), X is the public-input scalar slice, and u is a single scalar.

The relaxed instance absorbs u before X. This is deliberately not the proof wire order, where the same struct serializes as comm_W || comm_E || X || u (see The proof object). A prover that reuses the wire field order to build the transcript bytes absorbs u and X in the wrong order, squeezes the wrong folding challenge in Phase D, and is rejected.

Challenge decoding from transcript output

Transcript challenges are produced from exactly 64 output bytes. These 64 bytes are interpreted as a little-endian integer and reduced modulo the scalar-field prime \(p_{\mathrm{scal}}\), yielding a scalar in \(\mathbb{F}\).

from_uniform(bytes[0..64]) =
    little_endian_integer(bytes[0..64]) mod p_scal

This decoding is a self-contained rule, not the inverse of the input encodings. Scalars are absorbed as 32 big-endian bytes and base-field coordinates as 32 little-endian bytes, whereas a challenge squeezed from the transcript is decoded from 64 little-endian bytes before reduction.

The 64-byte input is wider than the scalar field size. Reducing this wide integer modulo \(p_{\mathrm{scal}}\) gives the challenge scalar with statistical uniformity appropriate for the canonical 256-bit scalar field.

The Fiat–Shamir transcript

The Vega transcript is the byte-level mechanism that turns prover messages into Fiat–Shamir challenges. For the canonical engine described in Fields, groups, and the engine, the transcript is based on Keccak256 and produces challenges in the scalar field \(\mathbb{F}\).

The transcript mechanism has four operations: new, absorb, squeeze, and dom_sep. This chapter specifies those operations byte-for-byte. It does not specify the protocol-level order in which \(\mathrm{Vega}_{\mathrm{MC}}\) absorbs proof objects and squeezes challenges; that ordered schedule is fixed in The transcript schedule. It also does not define how scalars, points, or vectors become bytes; those encodings are specified in Byte encodings and serialization.

State and constants

A transcript instance has three pieces of internal state:

• state: a 64-byte array. This carries entropy from one challenge to the next.
• round: a u16 counter. It starts at 0 and increments by one on every squeeze.
• transcript: a running Keccak256 hasher. It accumulates absorbed bytes since the last squeeze, and is reset to an empty Keccak256 hasher immediately after each squeeze.

The fixed byte constants are:

• PERSONA_TAG = "NoTR", four ASCII bytes, used once when a transcript is created;
• DOM_SEP_TAG = "NoDS", four ASCII bytes, used by squeeze and dom_sep;
• two one-byte challenge-half suffixes, 0x00 and 0x01;
• a transcript state size of 64 bytes.

Keccak256 here means the sha3 crate’s Keccak256 function, with a 32-byte digest.

The state-update primitive

All 64-byte transcript states and challenge preimages are produced by the same primitive. Given a Keccak256 hasher K and an input byte string input, compute_updated_state(K, input) performs the following steps:

1. update K with input;
2. clone the resulting hasher into two copies;
3. update the first copy with 0x00 and finalize it to obtain a 32-byte lo digest;
4. update the second copy with 0x01 and finalize it to obtain a 32-byte hi digest;
5. return lo ‖ hi, a 64-byte string.

Equivalently, if K already contains some byte prefix, the returned halves are:

lo = Keccak256(K_prefix ‖ input ‖ 0x00)
hi = Keccak256(K_prefix ‖ input ‖ 0x01)
output = lo ‖ hi

The notation K_prefix denotes the bytes already accumulated in the hasher before input is appended.

new(label)

new(label) initializes a fresh transcript under a static domain label.

The initial 64-byte state is computed from an empty Keccak256 hasher and the byte string "NoTR" ‖ label:

state = compute_updated_state(empty Keccak256, "NoTR" ‖ label)
round = 0
transcript = empty Keccak256

The PERSONA_TAG is used only in this initialization step. The running transcript hasher starts empty; the initial label affects state, not the running absorbed-byte buffer.

absorb(label, value)

absorb(label, value) appends bytes to the running hash:

transcript.update(label)
transcript.update(value.to_transcript_bytes())

There is no length framing, no delimiter, and no implicit separator between the label and the encoded value. Successive absorbs append to the same running Keccak256 hasher until the next squeeze. The byte representation of value is the transcript encoding defined in Byte encodings and serialization.

absorb does not change state or round directly. Its bytes affect the next squeeze, because that operation clones and extends the running transcript hasher.

squeeze(label)

squeeze(label) derives the next challenge scalar and rolls the transcript state forward.

First it builds the squeeze input:

squeeze input = "NoDS" ‖ round(2 B, little-endian) ‖ state(64 B) ‖ label

The 2-byte round field is the current u16 round counter in little-endian order. The 64-byte state is the current transcript state before this squeeze.

Next it computes a 64-byte output by applying the state-update primitive to a clone of the running transcript hasher:

output = compute_updated_state(transcript clone, squeeze input)

Because the cloned hasher already contains all bytes absorbed since the previous squeeze, the two output halves are exactly:

challenge half_b = Keccak256(
    absorbed_bytes_since_last_squeeze
    ‖ "NoDS"
    ‖ round(2 B, little-endian)
    ‖ state(64 B)
    ‖ label
    ‖ b
)   for b in {0x00, 0x01}

challenge output = half_0x00 ‖ half_0x01

After computing output, the transcript updates its internal state:

round = round + 1
state = output
transcript = empty Keccak256

The returned challenge is from_uniform(output): the 64-byte output interpreted as uniform input for a scalar in \(\mathbb{F}\). The scalar conversion is specified in Byte encodings and serialization.

dom_sep(bytes)

dom_sep(bytes) folds a static domain separator into the running hash:

transcript.update("NoDS")
transcript.update(bytes)

It does not squeeze a challenge, does not change state, and does not increment round. Its effect is to namespace later absorbed bytes in the same running hasher. For example, a sub-protocol can open by calling dom_sep before its own absorbs, so those absorbs are separated from the surrounding transcript context.

Determinism and verifier reconstruction

The transcript is the sole source of Fiat–Shamir challenges. Two runs that execute the same transcript operations with the same byte strings, in the same order, produce the same sequence of challenge scalars. Any difference in label bytes, encoded value bytes, domain separators, or squeeze positions changes the subsequent transcript state.

The verifier reconstructs the transcript by replaying the same public labels and proof bytes, then re-derives each challenge with squeeze. This binds every challenge to the bytes that preceded it in the transcript. The complete \(\mathrm{Vega}_{\mathrm{MC}}\) operation order is therefore part of the protocol specification and is given in The transcript schedule.

A small mechanism example

Consider a transcript created with a generic label:

T = new("example transcript")

Initialization sets:

state = compute_updated_state(empty Keccak256, "NoTR" ‖ "example transcript")
round = 0
transcript = empty Keccak256

Suppose two scalar values a and b are then absorbed under generic labels:

absorb("a", a)
absorb("b", b)

The running hasher now contains the plain concatenation:

"a" ‖ a.to_transcript_bytes() ‖ "b" ‖ b.to_transcript_bytes()

No state update has occurred yet. A subsequent challenge request

squeeze("challenge")

uses that absorbed byte string as the Keccak256 prefix, then appends:

"NoDS" ‖ 0x0000 ‖ state(64 B) ‖ "challenge" ‖ 0x00
"NoDS" ‖ 0x0000 ‖ state(64 B) ‖ "challenge" ‖ 0x01

to form the low and high halves of the 64-byte output. The transcript then sets state to that output, increments round to 1, resets the running hasher to empty, and returns from_uniform(output) as the challenge scalar.

Multilinear polynomials

This chapter describes Vega’s concrete representation of multilinear polynomials. The general existence, uniqueness, and Lagrange-basis formulas for multilinear extensions are reviewed in the multilinear extensions primer.

Evaluation tables as polynomials

A length-\(2^\ell\) vector is viewed as the evaluation table of a function

\[ f : \{0,1\}^\ell \to \mathbb{F}. \]

By the convention in Notation and conventions, an index \(i\) corresponds to bits \((i_0, \dots,i_{\ell-1})\) satisfying

\[ i = \sum_{k=0}^{\ell-1} i_k 2^k. \]

The table entry \(v_i\) is therefore the value at the Boolean point \((i_0, \dots,i_{\ell-1})\). Vega’s MultilinearPolynomial stores this table directly as the vector \(Z\), and the polynomial it represents is the MLE \(\widetilde{Z}\).

This representation is dense: all \(2^\ell\) Boolean evaluations are present. It is the natural form for sum-check rounds, because fixing one variable halves the table while preserving the remaining evaluation table.

Evaluation by equality weights

For a point \(\mathbf{r} \in \mathbb{F}^\ell\), Vega evaluates an MLE by weighting the Boolean table with the equality polynomial

\[ \widetilde{\mathrm{eq}}(\mathbf{r}, \mathbf{x}) = \prod_{k=0}^{\ell-1}\bigl(r_k x_k + (1-r_k)(1-x_k)\bigr). \]

Conceptually,

\[ \widetilde{Z}(\mathbf{r}) = \sum_{\mathbf{x} \in \{0,1\}^\ell} \widetilde{\mathrm{eq}}(\mathbf{r}, \mathbf{x})\; Z(\mathbf{x}). \]

The reusable EqPolynomial type stores the point and can evaluate a single equality polynomial or materialize the full vector of \(2^\ell\) equality weights. Polynomial commitments also reuse these weights when reducing an opening claim to inner products.

Vega also uses a powers polynomial as another reusable family of weights. For a challenge \(\tau\), the Boolean point with index \(i\) receives weight \(\tau^i\), so the weight vector is \(1, \tau, \tau^2, \dots, \tau^{2^\ell - 1}\); it is assembled from the per-variable factors \(\tau^{2^0}, \tau^{2^1}, \dots, \tau^{2^{\ell-1}}\). These weights batch constraint terms in sum-check. The concrete role belongs to The sum-check protocol.

Binding the top variable

Vega’s table-halving operation binds the top variable first. For a table \(Z\) of length \(2^\ell\), the top variable is the bit with index \(\ell-1\), the most-significant bit in the LSB-first integer labeling. The low half of the table contains entries with that bit equal to \(0\); the high half contains the corresponding entries with that bit equal to \(1\).

Given a challenge \(r \in \mathbb{F}\), bind_poly_var_top splits

\[ Z = (Z_{\mathrm{lo}} \;\|\; Z_{\mathrm{hi}}) \]

into two equal halves. For each position in the low half, let

\[ a = Z_{\mathrm{lo}}[j], \qquad b = Z_{\mathrm{hi}}[j]. \]

The bound table replaces \(a\) by

\[ (1-r)a + rb, \]

then discards the high half. The result has length \(2^{\ell-1}\) and is the evaluation table obtained by fixing the variable \(x_{\ell-1}=r\).

This is consistent with 0-based LSB-first indexing: bit \(0\) is the lowest-index variable, but the table operation starts from bit \(\ell-1\). After one binding, the next top variable is bit \(\ell-2\), and so on. Consequently, Vega’s sum-check challenge sequence binds variables high-to-low.

Interaction with sum-check

A sum-check prover repeatedly sends a univariate round polynomial, receives a verifier challenge, and restricts the remaining multilinear tables to that challenge. In Vega, that restriction is exactly the table-halving step above. Each round halves the live tables for the participating MLEs, so after \(j\) rounds a table that began with \(2^\ell\) entries has \(2^{\ell-j}\) entries.

The same high-to-low order is used for the tables that represent witness-derived values and for the auxiliary weights that participate in batching. Equality weights and powers weights are therefore not separate conventions; they are reusable polynomial families arranged to agree with the table order used by the sum-check implementation.

When these evaluations are checked inside a circuit, the same algebraic objects become circuit variables and constraints. That use is described in The in-circuit verifier. Exact serialized representations of tables, points, and proofs are specified in Serialization and encodings.

The sum-check protocol

This chapter describes the concrete sum-check building block used by Vega. The general interactive protocol is reviewed in the sum-check primer; here the focus is the generic shape of the round polynomials, the challenges derived by Fiat–Shamir, and the terminal claim returned to an enclosing protocol such as The Spartan argument.

What the proof object contains

A sum-check proof is a sequence of univariate round polynomials, one per round. In each round, the prover has a current claim \(C_{i-1}\) about a remaining hypercube sum. It sends a low-degree polynomial \(g_i(X)\), the verifier checks that \[ g_i(0) + g_i(1) = C_{i-1}, \] derives the next challenge from the Fiat–Shamir transcript, and updates the claim to \(C_i = g_i(r_i)\).

Vega stores each round polynomial in compressed form. The compression omits the linear coefficient. During verification, the verifier reconstructs that coefficient from the current claim, because the consistency equation determines it. For a quadratic round polynomial, the stored data contains the constant and quadratic coefficients; for a cubic round polynomial, it contains the constant, quadratic, and cubic coefficients. The verifier absorbs the round polynomial into the transcript in exactly this compressed form — the same bytes the prover sends, with the linear coefficient omitted — then squeezes the next challenge and evaluates the reconstructed polynomial at that challenge.

This re-derivation of challenges is the point where the interactive protocol is bound to Fiat–Shamir. A prover cannot choose later round polynomials independently of earlier messages, because every challenge is recomputed from the transcript state that includes the preceding round polynomial. The byte-level transcript labels and serialization of these messages are fixed in The transcript schedule, not in this pedagogical chapter.

The low-level sum-check verifier checks the number of rounds, checks the advertised degree, reconstructs each round polynomial so that the per-round consistency equation holds, and returns the final claim together with the challenge vector. The enclosing verifier then checks that terminal claim against the appropriate final evaluation for the particular sum-check instance.

Specialized prover shapes

Vega implements specialized sum-check provers by the degree and algebraic shape of the round polynomial they produce.

• The quadratic prover handles sums whose round polynomial comes from multiplying two multilinear tables. It constructs a degree-2 polynomial from three evaluations, compresses it, derives the round challenge from the transcript, and binds both tables to that challenge.
• The cubic-with-additive-term prover handles sums with a product term plus an additive term, optionally multiplied by another multilinear helper factor. It constructs a degree-3 polynomial from four evaluations, compresses it, derives the challenge, and binds the participating tables to that challenge.
• Batched zero-knowledge variants run the same degree shape for two branches under one transcript schedule. \(\mathrm{Vega}_{\mathrm{MC}}\) uses these variants when the folded step branch and core branch must share the same round challenges.
• Equality-polynomial and powers-polynomial helpers carry an extra multilinear factor through the rounds. This helper factor is what turns a product of two multilinear tables into a cubic round shape in applications such as The Spartan argument.

The names \(\tau\), \(r_x\), and \(r_y\) are used by Spartan’s row batching and sum-check reductions. The challenges \(\rho\) and \(r_b\) belong to the folding layer, where step instances are accumulated before the Spartan checks; see NeutronNova folding.

Payoff

The generic sum-check verifier does not evaluate a full hypercube sum. It checks a short sequence of low-degree univariate polynomial messages and returns a random evaluation point plus a terminal claim. The enclosing protocol supplies the meaning of that terminal claim and checks it against the relevant final evaluation.

For the R1CS application, The Spartan argument uses an outer sum-check to obtain \(r_x\), an inner matrix-evaluation sum-check to obtain \(r_y\), and a commitment opening for the final witness value. For background on the polynomial objects, see Multilinear polynomials and the sum-check primer. The \(\mathrm{Vega}_{\mathrm{MC}}\) proving flow is described in Proving, and byte-exact transcript behavior is specified in The transcript schedule.

R1CS and its variants

This chapter defines the rank-1 constraint systems used by Vega and the split forms that let the prover commit to different parts of a witness at different times. It is a building-block chapter: commitment schemes, transcripts, folding, and byte-exact proof objects are treated in their own chapters.

Standard R1CS

An R1CS shape over \(\mathbb{F}\) consists of three sparse matrices \[ A, B, C \in \mathbb{F}^{m \times n}. \] For an assignment vector \(\mathbf{z} \in \mathbb{F}^n\), the constraint system is satisfied when \[ (A\mathbf{z}) \circ (B\mathbf{z}) \;=\; C\mathbf{z}, \] where \(\circ\) is the entrywise product. Equivalently, for every row \(i \in \{0, \dots, m-1\}\), \[ \Bigl(\sum_j A_{i,j} z_j\Bigr) \Bigl(\sum_j B_{i,j} z_j\Bigr) \;=\; \sum_j C_{i,j} z_j. \]

The conceptual assignment is partitioned into public input/output \(\mathbf{x}\), the constant \(1\), and private witness \(\mathbf{w}\). Vega’s concrete R1CS matrices are laid out with the witness columns first, then the constant column, then the public columns, so the vector multiplied by the matrices is \[ \mathbf{z} \;=\; (\mathbf{w}, 1, \mathbf{x}). \] The standard instance carries the public vector \(\mathbf{x}\) and a commitment to \(\mathbf{w}\); the witness carries \(\mathbf{w}\) and the blind that opens that commitment.

The matrices are stored sparsely. A sparse matrix records the nonzero entries in data, their column positions in indices, row boundaries in indptr, and the total column count in cols. This is enough to compute each row of \(A\mathbf{z}\), \(B\mathbf{z}\), and \(C\mathbf{z}\) without materializing dense matrices. Byte-level encodings of verifier keys and proofs are specified in Verifier key and Proof object, not in this chapter.

R1CS is the algebraic layer beneath the polynomial protocols. The row products become claims about multilinear extensions in Multilinear extensions, and those claims are checked with the sum-check protocol. Witness commitments and openings are handled by Polynomial commitments and the ZK opening.

Relaxed R1CS

A relaxed R1CS instance uses the same matrices \((A,B,C)\), but changes the satisfaction equation to \[ (A\mathbf{z}) \circ (B\mathbf{z}) \;=\; u\,C\mathbf{z} + \mathbf{E}. \] Here \(u \in \mathbb{F}\) is a scalar carried by the instance, and \(\mathbf{E} \in \mathbb{F}^m\) is an error vector carried by the witness. In the concrete matrix layout, \[ \mathbf{z} \;=\; (\mathbf{w}, u, \mathbf{x}). \] The standard R1CS condition is the strict case \(u=1\) and \(\mathbf{E}=\mathbf{0}\).

The scalar \(u\) and error vector \(\mathbf{E}\) make the relation closed under the linear combinations used by folding. Instead of requiring every folded object to remain a strict R1CS instance at each intermediate step, the accumulated discrepancy is represented explicitly as \(\mathbf{E}\). The relaxed instance commits to both \(\mathbf{w}\) and \(\mathbf{E}\), while the relaxed witness contains the two vectors and their blinds.

Vega also samples random relaxed instance/witness pairs by choosing a full random assignment, taking \(u\) from the assignment’s constant-position slot, and defining \[ \mathbf{E} \;=\; (A\mathbf{z}) \circ (B\mathbf{z}) - u\,C\mathbf{z}. \] This construction makes the sampled pair satisfy the relaxed equation by definition.

Folding many standard objects

Standard witnesses and instances provide fold_multiple operations. Given challenges \(r_b\), Vega derives folding weights and forms linear combinations of witness vectors, public vectors, witness blinds, and witness commitments. The result is a single witness/instance pair whose components represent the weighted combination of many inputs. The algebra that justifies these combinations belongs to NeutronNova folding; this chapter only records the R1CS objects that participate in that interface.

Split R1CS

A split R1CS shape keeps the same matrices \((A,B,C)\) but partitions the private witness columns into named segments: \[ \mathbf{w} \;=\; (\mathbf{w}_{\mathrm{shared}}, \mathbf{w}_{\mathrm{precommitted}}, \mathbf{w}_{\mathrm{rest}}). \] The shape records the number of constraints, the padded and unpadded sizes of the three witness segments, the number of public values, and the number of transcript-derived challenges. Its sizes() method returns a fixed ten-entry summary: unpadded constraint count; unpadded shared, precommitted, and rest sizes; padded constraint count; padded shared, precommitted, and rest sizes; public-value count; and challenge count.

A split instance contains separate commitments for the shared, precommitted, and rest witness segments, together with public values and derived challenges. The shared and precommitted commitments are optional exactly when their corresponding segments are empty; the rest commitment is always present for the rest segment, including padding. The split assignment uses \[ \mathbf{z} \;=\; (\mathbf{w}_{\mathrm{shared}}, \mathbf{w}_{\mathrm{precommitted}}, \mathbf{w}_{\mathrm{rest}}, 1, \mathbf{x}, \boldsymbol{\chi}), \] where \(\boldsymbol{\chi}\) denotes the challenge values stored with the instance.

The split exists so that different pieces of the witness can be committed at the time they become determined. Shared witness variables are synthesized and committed once, then reused across step instances and the core instance. Precommitted variables are synthesized during preparation, before challenge-dependent rest variables are available. The rest segment is committed after the transcript has produced the challenges needed to finish the witness. This arrangement lets many step instances share one witness commitment component while preserving the single committed witness expected by the ordinary R1CS interface.

The bridge back to ordinary R1CS is explicit. to_regular_shape() adds the three witness segment sizes into one num_vars value and treats public values plus challenges as the regular public vector. to_regular_instance() combines the present segment commitments into one witness commitment and sets \[ \mathbf{X} \;=\; (\mathbf{x}, \boldsymbol{\chi}). \] After this conversion, the usual R1CS satisfaction and commitment checks apply.

The step circuit and the core circuit can have different split layouts. equalize() pads both shapes to the same constraint count and the same total witness-column count, extending the rest segment when necessary and moving public/challenge columns consistently. This gives later folding and verification code uniform dimensions to work with.

Transcript-derived challenges in a split instance

A split instance validates its challenge vector through the transcript. Validation absorbs the shared witness commitment if present, absorbs the precommitted witness commitment if present, squeezes the required number of field challenges, compares them with the instance’s stored challenges, and then absorbs the rest commitment. This means the rest commitment is bound after the challenges that determine the rest witness, while the earlier commitments are bound before those challenges are derived.

The exact transcript byte schedule belongs to the transcript schedule. This chapter only uses the mathematical consequence: the challenge vector stored in a split instance must be the vector obtained from the commitments and public context that precede it.

Multi-round split R1CS

The in-circuit verifier uses a multi-round split form. A SplitMultiRoundR1CSShape partitions the witness by rounds rather than by shared/precommitted/rest segments. It records the number of rounds, the padded and unpadded witness size for each round, the number of challenges produced after each round, the number of public values, a commitment width, and the matrices \((A,B,C)\).

A SplitMultiRoundR1CSInstance contains one witness commitment per round, the public values, and the challenges grouped by round. During witness generation, a round synthesizes that round’s variables, commits to the padded round segment, absorbs that commitment into the transcript, and squeezes the next round’s challenges. Validation performs the same transcript reconstruction: for each round it checks the commitment length, absorbs the round commitment, squeezes the configured number of challenges, and compares the result with the stored round challenges.

The ordinary R1CS view is again obtained by combining commitments and flattening public data. to_regular_shape() sums all per-round witness sizes and all per-round challenge counts. to_regular_instance() combines all round commitments into one witness commitment and sets the public input vector to \[ \mathbf{X} \;=\; (\boldsymbol{\chi}, \mathbf{x}), \] with the flattened challenges before the public values. This ordering matches the way the multi-round circuit inputizes its challenges.

The multi-round split is the shape used by the verifier circuit described in In-circuit verifier. It relies on the same transcript abstraction as the rest of the proof system, and it feeds the same commitment-opening machinery described in Polynomial commitments and the ZK opening. The proof and verifier-key chapters specify how these objects appear in serialized artifacts: Verifier key and Proof object.

Polynomial commitments and the ZK opening

This chapter describes Vega’s Hyrax polynomial commitment and the zero-knowledge opening used for the final committed-witness evaluation. The algebraic background is reviewed in the polynomial-commitment primer; the field and group conventions come from Fields, groups, and the engine and Notation and conventions.

Commitment key and row-wise commitments

Vega commits to vectors over \(\mathbb{F}\) using a Pedersen-style commitment over \(\mathbb{G}\). The commitment key contains a row width, a vector of commitment bases, and a dedicated hiding generator. In the canonical monolithic setting the width is \[ \mathtt{num_cols}=2048. \] The key therefore contains bases \[ G_0, G_1, \dots, G_{2047}\in\mathbb{G} \] and a hiding generator \(H\in\mathbb{G}\).

The row width is a parameter of each commitment key rather than a global constant. The application commitment key uses the monolithic width above; the in-circuit verifier’s key vc_ck fixes the width to 32, so its bases are \(G_0,\dots,G_{31}\) with \(H\) in the same hiding role. The reshaping and opening described below apply to either width.

A length-\(n\) vector \(\mathbf{v}\) is reshaped row-wise into \[ \left\lceil \frac{n}{w}\right\rceil \] rows, where \(w\) is that key’s row width (\(2048\) for the application key, \(32\) for vc_ck). Each row uses the same generator vector. For row \(i\), with entries \(v_{i,0},\dots,v_{i,m_i-1}\) and blind \(\rho_i\), the row commitment is \[ C_i = \sum_{j=0}^{m_i-1} v_{i,j}G_j + \rho_i H. \] The full commitment is the vector of row commitments \[ \mathbf{C}=(C_0, C_1, \dots). \] The blind is likewise a vector, one scalar per committed row.

The commitment is hiding because each row has its own fresh multiple of \(H\). It is binding under the discrete-log relation assumption for the public bases, as in the Pedersen commitment described in the primer. Its additive form makes it homomorphic row by row: \[ \alpha\mathbf{C}^{(1)}+\beta\mathbf{C}^{(2)} \] is the commitment to the same linear combination of the underlying row vectors, with blinds combined by the same coefficients.

The prover-side is_small parameter used by commitment routines is only a speed hint for choosing a multi-scalar-multiplication path. Verification does not receive or trust this hint; it checks the resulting group commitments and opening equations.

Combining and folding commitments

Vega’s folding protocols repeatedly replace several committed witnesses by one committed linear combination. Hyrax supports this directly. Given commitments \(\mathbf{C}^{(k)}\) and folding weights \(\lambda_k\), the folded commitment has rows \[ C_i^* = \sum_k \lambda_k C_i^{(k)}. \] The folded blind has rows \[ \rho_i^* = \sum_k \lambda_k \rho_i^{(k)}. \] By homomorphism, \[ C_i^* = \sum_j \left(\sum_k \lambda_k v_{i,j}^{(k)}\right)G_j + \rho_i^* H. \] Thus the folded commitment opens as a commitment to the folded witness. This property is what lets NeutronNova folding keep a single committed witness opening after many instances have been combined.

Vega also supports concatenating commitments and blinds when separate committed pieces become one longer committed vector. Concatenation preserves the row-wise interpretation: the combined commitment is the sequence of all row commitments, and the combined blind is the matching sequence of row blinds.

Evaluation opening by matrix factorization

The final opening treats the committed vector as the evaluation table of an MLE, described in Multilinear polynomials. For a point \(\mathbf{r}\), the Hyrax evaluation argument splits the point into a row part and a column part: \[ \mathbf{r}=(\mathbf{r}_{\mathrm{row}},\mathbf{r}_{\mathrm{col}}). \] The split is determined by the number of committed rows and the fixed row width. The row part has one coordinate for each row variable; the column part has one coordinate for each column variable.

Let \(Z\) be the row-wise matrix represented by the committed vector. The prover and verifier derive equality-weight vectors \[ \mathbf{L} = \bigl(\widetilde{\mathrm{eq}}(\mathbf{r}_{\mathrm{row}},i)\bigr)_i, \qquad \mathbf{R} = \bigl(\widetilde{\mathrm{eq}}(\mathbf{r}_{\mathrm{col}},j)\bigr)_j. \] The prover computes the row-combined vector \[ \mathbf{a} = \sum_i L_i Z_{i,*} \] and the matching row-combined blind \[ \rho_a = \sum_i L_i \rho_i. \] The verifier computes the corresponding row-combined commitment directly from the public commitment rows: \[ C_a = \sum_i L_i C_i. \] By homomorphism, \(C_a=\mathrm{Com}(\mathbf{a};\rho_a)\).

The MLE evaluation then reduces to one inner product: \[ \tilde{v}(\mathbf{r}) = \langle \mathbf{a},\mathbf{R}\rangle. \] The claimed scalar evaluation is itself committed with the evaluation commitment supplied by the surrounding protocol. The Hyrax opening proves that the row-combined commitment and the evaluation commitment are consistent with the inner product against the public vector \(\mathbf{R}\).

Linear inner-product opening

Vega’s inner-product argument is the linear-size Pedersen sigma protocol described in the primer. The statement contains a commitment to \(\mathbf{a}\), a public vector \(\mathbf{b}\), and a commitment to \(c\), with the relation \[ c=\langle \mathbf{a},\mathbf{b}\rangle. \] In the Hyrax opening, \(\mathbf{b}\) is the equality-weight vector \(\mathbf{R}\) for the column half of the evaluation point.

The prover samples a fresh mask vector \(\mathbf{d}\) and fresh blinds. It sends two cross-commitments: delta, a commitment to \(\mathbf{d}\), and beta, a commitment to \(\langle\mathbf{b},\mathbf{d}\rangle\). Fiat–Shamir produces one challenge. The prover answers with the masked response vector z_vec and the corresponding masked blinds: \[ \mathbf{z}=r\mathbf{a}+\mathbf{d}. \] The verifier checks two Pedersen equations: one for the vector commitment and one for the scalar inner-product commitment.

This argument is linear-size. It sends a response vector of column width, and it is not a logarithmic recursive folding argument. Its zero-knowledge property comes from the fresh mask \(\mathbf{d}\) and fresh blinding terms, which hide the row-combined witness vector while still allowing the verifier to check the linear equations. Its soundness comes from binding and from the fact that two valid responses to different challenges determine the committed vector and scalar relation.

The public vector \(\mathbf{b}\) is omitted from the inner-product transcript representation by design. In this use, \(\mathbf{b}\) is recomputed by the verifier from the transcript-derived evaluation point, so omitting it from the bytes absorbed for the inner-product instance does not weaken the binding of the checked relation.

Role in the MC proof

In \(\mathrm{Vega}_{\mathrm{MC}}\), the sum-check and folding layers produce one committed witness evaluation that remains to be opened. Vega first folds the relevant witness commitments and their evaluation commitments using the same challenge, then invokes the Hyrax evaluation argument on the folded commitment. Verification recomputes the same folded commitments and checks the Hyrax opening against the derived evaluation point.

This opening is the mechanism that hides the committed witness evaluation while proving that it is the value required by the verifier’s algebraic checks. The surrounding zero-knowledge construction is described in Zero-knowledge. Exact transcript scheduling and proof-object layout are specified separately in The transcript schedule and Proof object; this chapter intentionally describes only the algebraic protocol.

The Spartan argument

This chapter describes the R1CS-specific reduction that sits above the generic sum-check protocol. Spartan turns satisfaction of an R1CS instance into an outer zero-check over constraint rows, an inner matrix-evaluation sum-check over columns, and one final polynomial commitment opening for the committed witness.

From R1CS rows to a zero-check

For R1CS matrices \(A,B,C\) and assignment \(\mathbf{z}\), satisfaction means \[ (A\mathbf{z}) \circ (B\mathbf{z}) = C\mathbf{z}. \] Equivalently, the row error \[ \mathbf{e} = (A\mathbf{z}) \circ (B\mathbf{z}) - C\mathbf{z} \] vanishes at every constraint row. The vectors \(A\mathbf{z}\), \(B\mathbf{z}\), and \(C\mathbf{z}\) are viewed as tables on the padded row hypercube. If \(\ell_x=\log_2 m\), the outer layer batches all row equations into one weighted sum: \[ \sum_{\mathbf{x} \in \{0,1\}^{\ell_x}} W_\tau(\mathbf{x})\bigl(\widetilde{Az}(\mathbf{x})\widetilde{Bz}(\mathbf{x}) - \widetilde{Cz}(\mathbf{x})\bigr) = 0. \] The sum-check reduces this claim to one random row point \(r_x\). The summand contains a multilinear weight multiplied by the product \(\widetilde{Az}\,\widetilde{Bz}\), so an outer round polynomial can have degree three. Vega therefore uses cubic-with-additive-term prover routines for this layer.

Row weights in the two Vega variants

\(\mathrm{Vega}_{\mathrm{SC}}\) uses the equality-polynomial weight \[ W_\tau(\mathbf{x}) = \widetilde{\mathrm{eq}}(\tau,\mathbf{x}). \] In the reference implementation, the outer zero-check routine prove_cubic_with_additive_term_zk returns \(r_x\). The verifier recomputes \(\widetilde{\mathrm{eq}}(\tau,r_x)\) as tau_at_rx and checks the public values \[ \bigl[\tau_{r_x},\,\widetilde{X}(r_y’),\,\widetilde{A}(r_x,r_y)+r\widetilde{B}(r_x,r_y)+r^2\widetilde{C}(r_x,r_y)\bigr]. \]

\(\mathrm{Vega}_{\mathrm{MC}}\), the focus of this book, uses a powers-polynomial weight derived from \(\tau\). The powers polynomial is the multilinear extension whose Boolean evaluations are \(1,\tau,\tau^2,\dots\), with the bit ordering fixed by Notation and conventions. The folded step branch and the core branch pass through one batched outer round schedule rather than two independent schedules.

For \(\mathrm{Vega}_{\mathrm{MC}}\), the verifier recomputes the powers weight at \(r_x\) as tau_at_rx. It also recomputes \(\widetilde{\mathrm{eq}}(r_b,\rho)\), written eq_rho_at_rb, from the NeutronNova fold. The six public values pinned by the verifier circuit are, in order, \[ \tau_{r_x},\quad \widetilde{X}_{\mathrm{step}}(r_y’),\quad \widetilde{X}_{\mathrm{core}}(r_y’),\quad \widetilde{\mathrm{eq}}(r_b,\rho),\quad Q_{\mathrm{step}},\quad Q_{\mathrm{core}}, \] where \[ Q_\star = \widetilde{A}_\star(r_x,r_y)+r\widetilde{B}_\star(r_x,r_y)+r^2\widetilde{C}_\star(r_x,r_y) \] for \(\star\in\{\mathrm{step},\mathrm{core}\}\). The public-input polynomials \(\widetilde{X}_\star\) are evaluated at \(r_y’ = r_y[1..]\) — the inner point with its leading selector coordinate \(r_{y,0}\) dropped — while the matrix evaluations \(Q_\star\) use the full \(r_y\).

The inner matrix-evaluation sum-check

After the outer layer fixes \(r_x\), the matrix row variables are bound and the three matrices are combined with a fresh challenge \(r\): \[ \widetilde{ABC}_{r_x,r}(\mathbf{y}) = \widetilde{A}(r_x,\mathbf{y}) + r\,\widetilde{B}(r_x,\mathbf{y}) + r^2\,\widetilde{C}(r_x,\mathbf{y}). \] The inner sum-check proves the column-side claim \[ \sum_{\mathbf{y}} \widetilde{ABC}_{r_x,r}(\mathbf{y})\,\widetilde{z}(\mathbf{y}) \] over the padded column hypercube and reduces it to one column point \(r_y\). The summand is a product of two multilinear tables, so each inner round polynomial is quadratic. The generic routines for this shape are prove_quad and the batched zero-knowledge variant prove_quad_batched_zk; \(\mathrm{Vega}_{\mathrm{MC}}\) uses the batched variant to carry the folded step and core branches through the same challenge schedule.

Hand-off to the witness opening

The terminal inner claim contains \(\widetilde{z}(r_y)\). The verifier recomputes the public-input contribution directly from the public vector and the equality weights induced by \(r_y\). The witness contribution is obtained from the polynomial-commitment opening at \(r_y[1..]\). In \(\mathrm{Vega}_{\mathrm{MC}}\), this opening is the zero-knowledge linear inner-product argument stored as eval_arg.

The verifier then compares the resulting value of \(\widetilde{z}(r_y)\), together with the terminal matrix evaluation, against the final inner sum-check claim. This is the boundary between Spartan and Polynomial commitments and the ZK opening.

Challenge ownership

The challenges \(\tau\), \(r_x\), and \(r_y\) belong to Spartan’s row batching and sum-check reductions. The challenges \(\rho\) and \(r_b\) belong to NeutronNova folding, which produces the folded step instance that Spartan proves.

For background, see Multilinear polynomials, the sum-check primer, R1CS and its variants, and the generic sum-check protocol. The surrounding \(\mathrm{Vega}_{\mathrm{MC}}\) proving flow is described in Proving, and byte-exact transcript ordering is fixed in the transcript schedule.

NeutronNova folding

This chapter describes the first fold in \(\mathrm{Vega}_{\mathrm{MC}}\): accumulation of the many uniform step-circuit R1CS instances into one folded step instance before that instance is proved by The Spartan argument.

Inputs to the step fold

The step instances all use the same R1CS shape. Each input starts in strict form, so its assignment \(\mathbf{z}\) must satisfy

\[ (A\mathbf{z})\circ(B\mathbf{z}) = C\mathbf{z} \]

with relaxation scalar \(u=1\) and error \(\mathbf{E}=\mathbf{0}\). The prover evaluates the three matrix-vector products for every padded step instance. For row \(i\), the local residual is

\[ (A\mathbf{z})_i (B\mathbf{z})_i - (C\mathbf{z})_i. \]

A satisfied strict instance has zero residual in every row. The fold checks a random compression of these residuals rather than carrying every row of every step instance forward.

Two independent randomizers

The fold uses two layers of randomization. First, the transcript supplies \(\tau\), which combines the constraint coordinates inside one step instance. This turns the residual vector into one scalar target. If any row residual is nonzero, the \(\tau\)-weighted scalar is nonzero except with Schwartz–Zippel probability over \(\mathbb{F}\).

Second, the transcript supplies one \(\rho\) value for each batch-folding round. These values combine the padded list of step instances. If at least one instance has a nonzero \(\tau\)-compressed residual, the \(\rho\)-layer catches it except with another Schwartz–Zippel error. The byte-level labels and ordering for deriving \(\tau\), the \(\rho\) values, and the later verifier-circuit challenges are fixed in the transcript schedule, not in this chapter.

Round polynomials and verifier-circuit state

For a padded batch of \(2^{\ell_b}\) step instances, the fold runs \(\ell_b\) rounds. In each round the prover constructs a cubic univariate polynomial for the current batch axis and writes its four coefficients into the in-circuit verifier state. Processing that verifier-circuit round commits the round witness and returns one challenge; the sequence of these challenges is \(r_b\).

After a round challenge is known, the prover folds the adjacent layers of the precomputed \(A\mathbf{z}\), \(B\mathbf{z}\), and when needed \(C\mathbf{z}\) tables by the affine rule determined by that challenge. The next round operates on half as many batch entries. The verifier-circuit state checks that the cubic-polynomial messages maintain the folded claim, in the same folding style explained in the folding primer.

The final step error value

At the end of the \(r_b\) rounds, the prover has one accumulated target. The target is normalized by the equality-polynomial value at the point selected by \(r_b\) and the transcript-derived \(\rho\) values. The normalized scalar is stored in the verifier circuit as t_out_step, while the equality value is stored as eq_rho_at_rb.

The in-circuit verifier later pins this scalar to the folding transcript by enforcing

\[ \mathrm{eq\_rho\_at\_rb}\,\mathrm{t\_out\_step} = \mathrm{claim}. \]

This constraint prevents the prover from choosing an arbitrary folded error after the verifier-circuit challenges are fixed: the claimed folding result must equal the equality-weighted normalized output.

Folding the committed step instance

The same \(r_b\)-derived weights used by the polynomial fold also combine the concrete step witnesses and instances. For padded step index \(i\in{0,\dots,2^{\ell_b}-1}\), the weight is the equality polynomial evaluated at \(r_b\), \[ w_i = \prod_{t=0}^{\ell_b-1}\big((1-r_b[t])\ \text{if bit } t \text{ of } i \text{ is } 0,\ \text{else } r_b[t]\big), \] with \(t=0\) the least significant bit of \(i\). fold_multiple forms linear combinations of witness entries, public inputs, witness commitments, and commitment blinds under these weights. The result is one ordinary step witness/instance pair with the same dimensions as a single step instance.

That folded step instance is then batched with the core branch and proved by The Spartan argument. The overall \(\mathrm{Vega}_{\mathrm{MC}}\) proving flow is described in Proving. This chapter only describes the first fold; the second fold, which masks the verifier-circuit instance for zero knowledge, is described in Nova folding for zero-knowledge.

Nova folding for zero-knowledge

This chapter describes the second fold in \(\mathrm{Vega}_{\mathrm{MC}}\): the verifier-circuit instance is folded with a fresh random satisfying relaxed instance before the final relaxed-R1CS proof is produced.

From verifier circuit to ordinary R1CS

The in-circuit verifier is first materialized as a multi-round split R1CS instance. Its round commitments and transcript-derived challenges are validated through the transcript, then the instance is converted to an ordinary R1CS instance. This ordinary instance carries one combined witness commitment and one public vector containing the flattened verifier-circuit challenges followed by the verifier-circuit public values.

This real verifier-circuit instance is not proved directly. Instead, \(\mathrm{Vega}_{\mathrm{MC}}\) samples an independent relaxed R1CS instance and witness of the same shape.

Sampling the masking instance

The sampled relaxed pair is satisfying by construction. The sampler chooses a full random assignment \(\mathbf{z}\), takes the relaxation scalar \(u\) from the assignment slot used for the constant/relaxation coordinate, and defines the error vector by

\[ E = (A\mathbf{z})\circ(B\mathbf{z}) - u\,C\mathbf{z}. \]

This makes the relaxed equation true for the sampled pair. The sampler also commits to the random witness and to the computed error vector, so the sampled instance has the same public shape as any other relaxed instance used by Relaxed Spartan.

The Nova NIFS fold

Nova NIFS folds the random satisfying relaxed instance with the real verifier-circuit R1CS instance. Let the random relaxed pair be \((U_1,W_1)\), and let the real verifier-circuit pair be \((U_2,W_2)\). The prover computes the cross-term vector \(T\), commits to it as comm_T, absorbs \(U_1\), \(U_2\), and comm_T into the transcript, and squeezes the folding challenge \(r\).

The folded witness is

\[ \mathbf{W}_\star = \mathbf{W}_1 + r\mathbf{W}_2, \qquad E_\star = E_1 + rT, \]

and the folded public scalar and public vector are

\[ u_\star = u_1 + r, \qquad \mathbf{X}_\star = \mathbf{X}_1 + r\mathbf{X}_2. \]

The folded instance commitments use the same linear combination: the witness commitment is the random witness commitment plus \(r\) times the real witness commitment, and the error commitment is the random error commitment plus \(r\) times comm_T.

Why this gives zero knowledge

This fold is the zero-knowledge mechanism. The real verifier-circuit witness appears only with transcript challenge coefficient \(r\), while an independently sampled full-length random satisfying relaxed witness appears with coefficient \(1\). The subsequent relaxed proof runs on the masked folded instance, not on the original verifier-circuit instance. Since the mask is sampled fresh for each proof and has the full relaxed shape, the later non-ZK relaxed proof leaks no information about the real verifier-circuit witness beyond the public statement.

Verification repeats the same transcript step: it absorbs the random relaxed instance, the real verifier-circuit instance, and comm_T, then squeezes \(r\) and folds only the instance commitments and public data. The verifier does not know \(\mathbf{W}_\star\). Satisfiability of the folded relaxed instance is supplied later by Relaxed Spartan, and the surrounding \(\mathrm{Vega}_{\mathrm{MC}}\) privacy flow is summarized in Zero-knowledge. For the general folding algebra, see the folding primer.

Relaxed Spartan

This chapter describes the Spartan argument used for a relaxed R1CS instance. In Vega this crate-internal argument proves the single folded relaxed instance produced by the Nova zero-knowledge fold.

Relaxed relation

A relaxed R1CS instance uses the same matrices \(A,B,C\) as strict R1CS, but carries a relaxation scalar \(u\) and an error vector \(\mathbf{E}\). For assignment \(\mathbf{z}\), satisfaction is \[ (A\mathbf{z}) \circ (B\mathbf{z}) = u\,C\mathbf{z} + \mathbf{E}. \] Strict R1CS is the special case \(u=1\) and \(\mathbf{E}=\mathbf{0}\). The relaxed relation is closed under the linear combinations used by folding, with accumulated discrepancy represented by \(\mathbf{E}\).

Prover transcript and outer check

RelaxedR1CSSpartanProof contains an outer sum-check proof, the three outer terminal claims, an inner sum-check proof, and direct openings for the committed witness \(\mathbf{W}\) and error vector \(\mathbf{E}\). Its transcript intentionally absorbs only the relaxed scalar and public vector:

• b"u_relaxed" absorbs \(u\);
• b"X_relaxed" absorbs \(\mathbf{X}\).

The commitments comm_W and comm_E are not absorbed by this argument. They must already be bound by the enclosing folding protocol.

The prover squeezes \(\ell_x\) row challenges with label b"t" and uses them as the equality-polynomial weight in the relaxed outer zero-check: \[ \sum_{\mathbf{x}} \widetilde{\mathrm{eq}}(t,\mathbf{x})\bigl(\widetilde{Az}(\mathbf{x})\widetilde{Bz}(\mathbf{x}) - u\,\widetilde{Cz}(\mathbf{x}) - \widetilde{E}(\mathbf{x})\bigr)=0. \] The routine prove_cubic_with_three_inputs returns the row point \(r_x\) and the terminal claims for \(\widetilde{Az}(r_x)\), \(\widetilde{Bz}(r_x)\), and \(u\widetilde{Cz}(r_x)+\widetilde{E}(r_x)\). The prover absorbs these three values under b"claims_outer".

Inner check and openings

The prover squeezes the combining challenge b"r", binds the matrix row variables at \(r_x\), and forms the row-bound combination for \(A\), \(B\), and \(uC\). It then runs the quadratic inner sum-check with prove_quad, reducing the column-side claim to \(r_y\).

The witness and error openings are the zero-knowledge-relevant distinction from the main Spartan opening. Relaxed Spartan uses direct, non-hiding reduced-linear-combination openings:

• prove_direct opens \(\mathbf{W}\) at \(r_y[1..]\), producing \((v_W,\mathrm{blind}_W)\);
• prove_direct opens \(\mathbf{E}\) at \(r_x\), producing \((v_E,\mathrm{blind}_E)\).

The prover absorbs b"v_W" and b"v_E" after producing those direct opening vectors. It does not use the zero-knowledge linear IPA described in Polynomial commitments and the ZK opening.

Why direct openings are safe in this use

A direct opening would not be zero-knowledge for an arbitrary relaxed instance. Vega runs this argument only on the fold output of the Nova zero-knowledge fold. That fold combines the real verifier-circuit instance with a fresh full-length random satisfying relaxed instance. The random mask supplies the zero-knowledge property; the direct opening is made on the masked folded object, not on the unmasked verifier-circuit witness.

This composition is described from the user-facing proof perspective in Zero-knowledge. Relaxed Spartan relies on that composition rather than adding another hiding opening inside this crate-internal argument.

Verification

Verification mirrors the prover transcript. It absorbs b"u_relaxed" and b"X_relaxed", squeezes the b"t" challenges for the outer equality weight, verifies the cubic outer sum-check, absorbs the three outer claims, squeezes b"r", and verifies the quadratic inner sum-check. It then verifies the direct opening of \(\mathbf{E}\) at \(r_x\) and of \(\mathbf{W}\) at \(r_y[1..]\), recomputes the terminal matrix and assignment evaluations, and absorbs b"v_W" and b"v_E".

The byte-exact labels and ordering are fixed in the transcript schedule. This chapter records the algebraic role of the messages and why the direct openings are valid only in the Nova zero-knowledge composition.

The in-circuit verifier

The in-circuit verifier is the R1CS object that turns Vega’s verifier algebra into a committed witness. Instead of asking the outer verifier to execute the full folding and sum-check computation natively, the prover supplies a multi-round R1CS instance whose constraints check that computation. The outer verifier then checks one folded relaxed-R1CS instance and one polynomial-commitment opening, while still recomputing a small set of public values outside the circuit.

The verifier as an R1CS circuit

The MC proof system uses VegaMcVerifierCircuit as its verifier circuit. It is a multi-round circuit: each round produces witness variables, commits to that round’s witness, and then receives the Fiat–Shamir challenges for later rounds. This is the setting described by SplitMultiRoundR1CS in R1CS and its variants. The single-circuit sibling, VegaVerifierCircuit, has the same role for a single verifier computation; the MC path uses VegaMcVerifierCircuit because it must also account for folding the step instances.

The MC circuit has three algebraic regions. First, it checks the folding sum-check over the step batch. Second, it checks the outer sum-checks for the folded step branch and the core branch. Third, it checks the inner sum-checks for the same two branches. These regions are not separate proofs inside the book’s proof object; they are rounds of one multi-round R1CS instance. Exact transcript labels and byte layout belong to The transcript schedule and The proof object.

If the step batch is padded to \(2^{\ell_b}\), the step constraint system has \(2^{\ell_x}\) constraints, and the combined witness/public vector has size \(2^{\ell_y-1}\) before the extra selector coordinate used by the inner check, then the verifier-circuit challenge rounds have the shape

\[ \ell_b \;+ \ell_x \;+ 1 \;+ \ell_y . \]

The first \(\ell_b\) challenges are the folding/sum-check challenges \(r_b\). The next \(\ell_x\) challenges are the outer sum-check challenges \(r_x\). The single bridge challenge batches the three matrix claims. The final \(\ell_y\) challenges are the inner sum-check challenges \(r_y\).

Sum-check consistency inside the circuit

Each sum-check round sends a univariate polynomial. Inside the circuit, enforce_sc_claim checks the local sum-check relation: the polynomial’s evaluations at \(0\) and \(1\) add to the previous claim. With coefficient vectors, this is enforced as the sum of all coefficients plus the constant coefficient equaling the current claim. eval_poly_horner evaluates the previous round polynomial at the next challenge, and alloc_coeffs allocates the round polynomial coefficients as witness variables.

The folding region ends by enforcing that the final folding claim equals the accumulated equality weight times the folded step target \(t_{\mathrm{step}}\) — the evaluation/error term the NeutronNova fold carries for the step batch. Conceptually, the circuit checks

\[ \widetilde{\mathrm{eq}}(r_b, \rho)\, t_{\mathrm{step}} = q_b, \]

where \(q_b\) is the final claim obtained from the folding-round polynomials. The equality value \(\widetilde{\mathrm{eq}}(r_b,\rho)\) is later exposed as a public value so the native verifier can compare it with its own transcript-derived computation.

For each of the step and core branches, enforce_outer_sc_final_check checks the final outer zero-check relation. In notation matching the R1CS identity \((A\mathbf{z}) \circ (B\mathbf{z}) = C\mathbf{z}\), the checked relation is

\[ q_x = \widetilde{\mathrm{eq}}(\tau, r_x)\, \bigl( \widetilde{A\mathbf{z}}(r_x)\, \widetilde{B\mathbf{z}}(r_x) - \widetilde{C\mathbf{z}}(r_x) \bigr). \]

Here \(q_x\) is the final outer sum-check claim, and \(\widetilde{\mathrm{eq}}(\tau,r_x)\) is represented in the implementation by the public value tau_at_rx. The MC circuit applies this relation once to the folded step branch and once to the core branch.

The bridge into the inner sum-check uses compute_joint_claim. Given the three final matrix-vector claims, it forms the batched claim

\[ q_{ABC} = q_A + r q_B + r^2 q_C, \]

where \(r\) is the bridge challenge. This is the claim that the inner sum-check reduces to matrix evaluations.

Finally, enforce_inner_sc_final_check checks the inner final relation. The first inner coordinate selects between the witness part and the public-input part of \(\mathbf{z}\):

\[ z(r_y) = (1-r_{y,0})\,W(r_y’) + r_{y,0}\,X(r_y’), \]

where \(r_y’\) is the remaining suffix of \(r_y\). Let \(q_y\) be the terminal inner sum-check claim, and let

\[ Q = \widetilde{A}(r_x,r_y) + r\,\widetilde{B}(r_x,r_y) + r^2\,\widetilde{C}(r_x,r_y) \]

be the combined matrix evaluation at the inner point. The terminal claim factors as \(q_y = Q\, z(r_y)\), so the circuit enforces the quotient relation

\[ Q\, z(r_y) = q_y, \]

exposing \(Q = q_y / z(r_y)\) as a public value. This \(Q\) is the terminal matrix evaluation, not the initial batched claim \(q_{ABC}\) formed above. The native verifier independently recomputes \(Q = \widetilde{A}+r\widetilde{B}+r^2\widetilde{C}\) at \((r_x,r_y)\) for the folded step branch and the core branch and compares both values.

Public values that close the check

The MC verifier circuit exposes six public values:

These public values are deliberately small. The circuit constrains the transcript-dependent algebra, but it does not by itself recompute every sparse matrix evaluation or every public-input evaluation natively. The outer verifier recomputes these six values from the verifier key, public instances, and transcript challenges, then requires equality with the verifier-circuit public input. This native comparison closes the quotient relations that would otherwise be under-constrained by the circuit alone. The full verification path is described in MC verification.

Fiat–Shamir binding across rounds

The verifier-circuit challenges are not arbitrary witness values. During validation of a SplitMultiRoundR1CSInstance, the verifier processes the committed rounds in order. For each round, it checks that the round commitment has the expected size, absorbs the commitment into the running transcript, squeezes that round’s challenges, and compares the derived challenges with the challenges stored in the instance. This makes the in-circuit challenges equal to the transcript challenges without placing the transcript hash function inside the R1CS circuit. The transcript abstraction is introduced in The Fiat–Shamir transcript.

Why the circuit enables zero knowledge

Once the verifier’s algebra has become one committed R1CS instance, Vega can apply the same folding machinery used elsewhere. The prover samples a fresh random satisfying relaxed instance for the verifier-circuit shape and folds it with the real verifier-circuit instance. The proof then opens the folded committed witness at the point needed by the verifier checks, rather than exposing the original verifier-circuit witness directly.

This structural move is what keeps the native verifier small: it checks satisfaction of the folded relaxed-R1CS instance, verifies the single polynomial-commitment opening, and compares the six public values described above. The relevant background is NeutronNova folding and Nova folding for zero-knowledge, and the \(\mathrm{Vega}_{\mathrm{MC}}\) zero-knowledge flow is described in Zero knowledge. For the sum-check equations used by the circuit, see The sum-check protocol.

Protocol overview

Part II defined each primitive in isolation. This part assembles them into the end-to-end multi-circuit prover \(\mathrm{Vega}_{\mathrm{MC}}\): setup fixes the keys, proving turns a batch of circuit instances into a single zero-knowledge proof, and verification defines exactly when that proof is accepted. The runtime phases are summarized in The proving lifecycle; the chapters here give the structural detail, one stage at a time. Byte-level formats are deferred to the implementable specification.

What the protocol proves

A statement consists of \(n\) instances of a step circuit \(C_1\) together with one instance of a core circuit \(C_2\). The core circuit joins the batch: every step instance and the core instance share one committed witness. The prover convinces the verifier that it knows satisfying assignments for all \(n+1\) instances, revealing nothing beyond the public inputs and outputs that verification returns. The batch size \(n\) is fixed at setup and must be at least two; a single instance is the domain of the single-circuit prover \(\mathrm{Vega}_{\mathrm{SC}}\).

The four stages

The protocol is exposed as four operations, each with its own chapter:

• Setup synthesizes the circuit shapes and produces the prover and verifier keys.
• Rerandomizable precomputation builds the reusable committed prover state that proving rerandomizes into a fresh proof.
• Proving folds the batch and runs the sum-checks, emitting the proof object below.
• Verification is the canonical acceptance predicate.

Zero-knowledge cuts across proving and verification and is treated on its own in Zero-knowledge.

How the building blocks compose

Proving threads the batch through the building blocks of Part II in a fixed order.

The prover first forms a split R1CS instance and witness for each step circuit and for the core circuit. All of them reuse a single shared witness commitment, so the batch commits its common data once. NeutronNova folding then accumulates the \(n\) step instances into one folded step instance, using transcript-derived challenges \(\tau\) and \(\rho\).

The folded-step branch and the core branch are reduced by the Spartan outer and inner sum-checks, which bind the challenge vectors \(r_x\) and \(r_y\) and produce six algebraic values: the power-polynomial evaluation \(\mathrm{tau\_at\_rx}\), the public-input evaluations \(\mathrm{eval\_X\_step}\) and \(\mathrm{eval\_X\_core}\), the equality evaluation \(\mathrm{eq\_rho\_at\_rb}\), and the matrix-quotient values \(\mathrm{quotient\_step}\) and \(\mathrm{quotient\_core}\). These six values are exactly what the in-circuit verifier exposes as public output.

The in-circuit verifier instance is then made zero-knowledge by Nova folding: the prover samples a fresh random satisfying instance and folds it with the real verifier instance, masking it. The masked instance is proved with relaxed Spartan, and the committed-witness evaluation the checks need — folded across the step and core branches — is opened by the zero-knowledge linear IPA at the point \(r_y[1..]\).

Two distinct folding schemes appear, for two distinct purposes:

• NeutronNova folding accumulates the many step instances into one, shrinking the batch to a single instance to prove.
• Nova folding masks the in-circuit verifier instance for zero-knowledge, folding it with a fresh random instance so nothing about the real witness leaks.

The proof object

Proving emits one object whose fields carry everything verification needs:

The exact byte layout of these fields is specified in The proof object.

The acceptance predicate at a glance

Verification mirrors proving. It rebuilds the Fiat–Shamir transcript from the same absorbs, revalidates the split instances, refolds the batch, and checks the Nova fold and the relaxed-Spartan proof. It then recomputes the six public values in the clear from the keys and instances it holds and rejects unless each one matches the value the circuit exposed, and finally verifies the witness opening. That native recomputation is what ties the in-circuit argument to the real statement; Verification gives the full ordered checklist.

Reading guide

The remaining chapters follow the stages in order: Setup, Rerandomizable precomputation, Proving, Verification, and Zero-knowledge.

Setup

This chapter describes the setup phase for \(\mathrm{Vega}_{\mathrm{MC}}\). Setup fixes the step shape, the core shape, the commitment material, the verifier-circuit shape, and the verifier-key digest that later binds the Fiat–Shamir transcript to those choices.

Inputs and invariant

setup consumes a step circuit \(C_1\), a core circuit \(C_2\), and num_steps. It returns a prover key and a verifier key. The verifier key is tied to the supplied number of step instances, so proofs for a different step count are outside that key’s statement.

num_steps must be at least two. The step branch is folded as a batch by the NeutronNova building block, and that batch has at least two step instances. A single instance belongs to the single-circuit prover \(\mathrm{Vega}_{\mathrm{SC}}\) rather than this multi-circuit path. Where folding needs a power-of-two batch size, the implementation pads the step count internally before deriving round counts.

Split R1CS shapes

Setup synthesizes a split R1CS shape for the step circuit and another split R1CS shape for the core circuit. A split shape separates the witness columns into shared, precommitted, and rest segments, while retaining the R1CS matrices and public-value layout described in R1CS and split shapes.

After synthesis, setup equalizes the two split shapes. Equalization aligns their split layouts so the step and core branches use compatible segment boundaries under one commitment scheme. The resulting shapes are stored as S_step and S_core in both keys.

Commitment material

Setup builds one shared commitment key ck sized for both split shapes and derives the PCS verifier key vk_ee. The same ck is used for the step and core witness commitments. The PCS precompute step is then applied to ck, so later commitments can use the prepared commitment material described in Polynomial commitments.

The reference implementation sets DEFAULT_COMMITMENT_WIDTH to 2048. This width is the commitment-row width used when split witness segments are padded and when the shared commitment key is generated.

The generators are derived by hashing rather than sampled. A commitment key of width \(n\) comes from a fixed byte label: setup reads a SHAKE256(label) extendable-output stream as \(n+1\) consecutive 32-byte messages and maps each message to a group element with the RFC 9380 random-oracle hash_to_curve for T256. That map is the suite T256_XMD:SHA-256_SSWU_RO_ — expand_message_xmd over SHA-256 producing two field elements per point, each reduced big-endian from 48 output bytes, the simplified SWU map applied directly to T256 with non-square \(Z = -2\), and cofactor one — run under the domain-separation tag from_uniform_bytes concatenated with the suite name, itself suffixed with its one-byte length to form the RFC 9380 DST_prime. The first \(n\) points become the column generators \(G_0,\dots,G_{n-1}\); the last is the hiding base \(h\).

Both ck and the verifier-circuit key vc_ck are derived from the single label ck, so the shorter vc_ck point sequence is a prefix of the ck sequence, and vk_ee and vc_vk reuse the generators of ck and vc_ck. Because every point comes from a public hash with no sampled randomness, no one knows a discrete-logarithm relation among the generators (under the random-oracle heuristic for the hash) — the assumption Hyrax binding rests on — and any implementation that repeats this derivation obtains byte-identical generators. This is what lets the verifier key serve as a reproducible root of trust: it is not a value the verifier accepts on faith, but one an independent party can regenerate and check.

Verifier circuit

Setup also constructs the verifier circuit used later inside the proof. Its shape depends on the public setup data:

• num_rounds_b is the base-two logarithm of the padded step count num_steps.next_power_of_two();
• num_rounds_x is the base-two logarithm of the number of step constraints;
• num_rounds_y is one more than the base-two logarithm of the total number of step witness variables.

Those dimensions parameterize the in-circuit verifier described in The in-circuit verifier. Shape synthesis for that verifier circuit produces vc_shape, vc_ck, and vc_vk; setup also derives vc_shape_regular from vc_shape. The verifier-circuit commitment key is precomputed before the keys are returned.

Verifier-key digest

The verifier-key digest is the protocol binding for setup. It is computed from the verifier key with bincode::DefaultOptions::new().with_little_endian().with_fixint_encoding() except for the two split R1CS shapes, which use their raw shape byte writer. The digest input order is:

1. ck, serialized with the bincode options above;
2. vk_ee, serialized with the same bincode options;
3. raw shape bytes for S_step;
4. raw shape bytes for S_core;
5. vc_shape, serialized with the same bincode options;
6. vc_shape_regular, serialized with the same bincode options;
7. vc_ck, serialized with the same bincode options;
8. vc_vk, serialized with the same bincode options;
9. num_steps, serialized with the same bincode options.

The digest is memoized in the verifier key’s OnceCell. The prover key stores the same digest as vk_digest. During proving and verification, the digest is absorbed into the Keccak Fiat–Shamir transcript before instance validation and before the folding transcript, so the transcript is bound to the fixed setup material. The transcript mechanism is described in Fiat–Shamir transcript. The exact byte layout of the verifier key belongs to Verifier key and Serialization.

Key contents

Setup hands these fixed objects to rerandomizable precomputation, which fills in reusable committed witness state for concrete step and core circuits.

Rerandomizable precomputation

This chapter describes prep_prove, the reusable precomputation phase for \(\mathrm{Vega}_{\mathrm{MC}}\). Preparation builds committed prover state once; each call to prove then rerandomizes that state before emitting a fresh zero-knowledge proof.

Input and output

prep_prove consumes the prover key, a slice of concrete step circuits, the concrete core circuit, and the is_small speed hint. It returns VegaMcPrepZkSNARK, which contains:

The output is prover-private state. It is not a proof object and is not part of verifier input.

Shared witness

Preparation first synthesizes the shared witness from the first step circuit. That shared witness and its commitment are then reused by every step instance and by the core instance. The result is a single shared commitment, comm_W_shared, that represents the common shared segment across the whole presentation.

This shared commitment appears once in the emitted proof object. The per-step instances and the core instance carry compatible shared-commitment data internally, and verification checks that all instances agree with the core instance. The proof-level storage avoids repeating the same shared commitment for every step.

Precommitted states

After the shared witness is available, preparation builds one step precommitted state for each supplied step circuit. Each step state starts from a clone of the shared state, then fills and commits its step-specific precommitted segment.

The core state reuses the original shared state and fills the core-specific precommitted segment. The prepared result therefore has a one-to-one ps_step entry for each step circuit plus a single ps_core entry for the core circuit.

The online prove call later checks that the number of prepared step states still matches the number of step circuits it receives. A mismatch is rejected before proof generation proceeds.

Prover-internal caches

The cache fields are deterministic speed optimizations. They do not define the public proof format, and they do not add verifier input. A byte-equivalent reference prover may omit these caches and compute the same matrix-vector data during proving instead; see the byte-equivalence boundary in Specification scope.

cached_step_matvec is populated only when the step shape has no challenge variables and no unpadded rest variables. In that case the full step vector is known during preparation, so the step matrix products can be computed early. cached_step_i64 stores a small-integer representation for faster folding arithmetic; large_positions records entries that must be corrected with field arithmetic. cached_step_public_values records the public values used when the cache was computed.

Before using a cached matrix-vector product, prove recomputes each step circuit’s public values and compares them with cached_step_public_values. If the public values changed between preparation and proving, the cache is stale and proving is rejected.

Rerandomization per proof

The prepared state is reusable because prove owns it by value, rerandomizes it in place, and returns it together with the proof. A caller passes the returned VegaMcPrepZkSNARK into the next prove call to reuse the expensive preparation.

At the start of each proof, prove rerandomizes the core precommitted state. It then takes the core state’s refreshed shared commitment and blind, and rerandomizes every step state with that same shared commitment and blind. This keeps the shared segment consistent across all instances while giving the proof fresh hiding randomness.

This fresh commitment randomness is the per-proof zero-knowledge input for prepared state reuse. The surrounding zero-knowledge construction is described in Zero knowledge.

The small-value hint

is_small is a prover-side speed hint indicating whether witness values fit in machine words. It selects faster commitment and witness paths when the values satisfy that condition. The verifier still checks the resulting commitments and algebraic claims, so the hint is not trusted as a statement of soundness. It does not change the proof format; with valid inputs it is an implementation choice rather than serialized data.

Preparation feeds the rerandomized state into the online prover described in Proving, and the resulting proof is checked by Verification.

Proving

This chapter describes the online proving pipeline for \(\mathrm{Vega}_{\mathrm{MC}}\). It follows the structural order of the prover: what each stage constructs, what the transcript binds, and which building block carries the algebra. The exact byte order for transcript absorbs, squeezes, and serialization belongs to Transcript schedule and Serialization.

Ordered pipeline

1. Rerandomize and validate the prepared state

The prover consumes the prepared state from Preparation and rerandomizes it in place. The core prepared state receives fresh commitment randomness, and each step prepared state is rerandomized with the same shared witness commitment and blind. The prover then checks that the number of step circuits matches the prepared step state. If the matrix-vector cache is active, it also recomputes each step circuit’s public values and rejects stale cached public data.

2. Build split R1CS instances and witnesses

For every step circuit, the prover opens a per-instance Fiat–Shamir transcript, absorbs the verifier-key digest, the number of step circuits, the step circuit index, and that step circuit’s public values. The core branch opens the same transcript domain, absorbs the verifier-key digest and the core public values, and omits the step count and index. Each branch then invokes the split R1CS assignment machinery to commit the round witnesses and produce a SplitR1CSInstance with its witness. The shared witness commitment is stored once and reused by all step and core instances.

3. Open the main protocol transcript

The main protocol transcript starts in the same domain and absorbs the verifier-key digest and the regularized core instance. The step instances are absorbed by the NeutronNova folding procedure, followed by the initial cross-term target \(T = 0\). The folding procedure then squeezes \(\tau\) and the sequence of \(\rho\) challenges that parameterize step-instance folding. Byte-level labels and ordering are specified in Transcript schedule.

4. Fold all step instances with NeutronNova

Vega-MC NeutronNova folding folds the many regular step instances into one folded step instance and one folded step witness. During the fold, the prover records the folding sum-check polynomials in the verifier-circuit witness, computes the accumulated equality value \(\mathrm{eq\_rho\_at\_rb}\), and carries the folded step error through the target term \(\mathrm{t\_out\_step}\).

5. Run the outer sum-check

The prover prepares multilinear tables for the folded step branch and for the core branch. For the step branch it uses the folded \(Az\), \(Bz\), and \(Cz\) layers returned by NeutronNova; for the core branch it multiplies the core shape by the core witness, unit coordinate, public values, and challenges. It then invokes the batched cubic Spartan outer reduction, with an additive step target, through the generic sum-check. This binds \(r_x\), records the claimed \(Az\), \(Bz\), and \(Cz\) evaluations for step and core, and records \(\mathrm{tau\_at\_rx}\).

6. Process the verifier-circuit batching round

The prover advances the in-circuit verifier by one round after the outer sum-check. That round absorbs the committed verifier-circuit witness data and squeezes the batching challenge \(r\). The prover forms the two inner joint claims \[ \mathrm{claim\_inner\_joint}_\star = \mathrm{eval\_A}_\star + r \, \mathrm{eval\_B}_\star + r^2 \, \mathrm{eval\_C}_\star \] for \(\star \in {\mathrm{step}, \mathrm{core}}\).

7. Run the inner sum-check

The prover binds the row variables at \(r_x\), constructs the joint matrix-evaluation tables, and builds the folded-step and core \(z\) vectors. It invokes the batched quadratic Spartan inner reduction to bind \(r_y\). The result yields \(\mathrm{eval\_X}\) and \(\mathrm{eval\_W}\) for the folded step branch and for the core branch. The first coordinate \(r_y[0]\) separates the witness half from the public-value half, and the remaining point \(r_y[1..]\) is the committed-witness evaluation point.

8. Finalize the verifier-circuit instance

The prover feeds the inner final-equality round and the two witness-evaluation commitment rounds into VegaMcVerifierCircuit. The finalized U_verifier is a SplitMultiRoundR1CSInstance whose public values are, in order, \(\mathrm{tau\_at\_rx}\), \(\mathrm{eval\_X\_step}\), \(\mathrm{eval\_X\_core}\), \(\mathrm{eq\_rho\_at\_rb}\), \(\mathrm{quotient\_step}\), and \(\mathrm{quotient\_core}\), where \(\mathrm{quotient}_\star = \mathrm{eval\_A}_\star + r \, \mathrm{eval\_B}_\star + r^2 \, \mathrm{eval\_C}_\star\). The prover also converts this split multi-round instance to a regular R1CS instance for the zero-knowledge fold.

9. Apply the zero-knowledge mask fold

For the verifier-circuit regular shape, the prover samples a fresh random satisfying relaxed instance and witness with sample_random_instance_witness. It then invokes the Nova NIFS zero-knowledge fold from Nova ZK folding: U1 is the random mask random_U with coefficient \(1\), and U2 is the real verifier-circuit instance with coefficient \(r\). This stage produces the NIFS proof and the folded relaxed verifier-circuit witness described in Zero-knowledge.

10. Prove the folded verifier instance with relaxed Spartan

The prover invokes the relaxed-Spartan direct opening proof on the folded verifier-circuit relaxed instance. This proof establishes satisfiability of the folded instance. It is non-hiding by itself, and its zero-knowledge role depends on the fresh random mask folded in the previous stage.

11. Open the witness evaluation with ZK PCS

The verifier circuit committed separately to \(\mathrm{eval\_W\_step}\) and \(\mathrm{eval\_W\_core}\). After those commitments are already bound to the transcript, the prover squeezes \(c_\mathrm{eval}\), folds the step and core witness commitments, folds their blinds, folds the witness vectors, and folds the two evaluation commitments and blinds with coefficients \(1\) and \(c_\mathrm{eval}\). It then opens the folded commitment at \(r_y[1..]\) using the Hyrax PCS with ZK linear IPA, producing eval_arg.

12. Assemble the proof and return reusable state

The prover extracts the shared witness commitment, removes that shared commitment from each stored step and core split instance, and assembles the eight proof fields: comm_W_shared, step_instances, core_instance, eval_arg, U_verifier, nifs, random_U, and relaxed_snark. The method returns the proof together with the consumed prepared state, which can be reused after another rerandomization pass.

Neighboring chapters

For the inputs to this pipeline, see Setup and Preparation. For the verifier’s reconstruction of the same transcript and checks, see Verification. For the hiding argument behind the deterministic stages, see Zero-knowledge.

Verification

This chapter states the canonical acceptance predicate for \(\mathrm{Vega}_{\mathrm{MC}}\). It describes the verifier’s ordered structural checks; byte-exact absorb and squeeze order is fixed separately in the transcript schedule.

Verifier interface

The verifier entry point has the shape

#![allow(unused)]
fn main() {
verify(&self, vk: &VegaMcVerifierKey<E>, num_instances: usize)
  -> Result<(Vec<Vec<E::Scalar>>, Vec<E::Scalar>), VegaError>
}

The proof is accepted exactly when every check below succeeds, in this order. Failure at any step rejects the proof. The returned value is the per-step public values and the core public values; these vectors are the public statement exposed by the proof-system layer.

Canonical acceptance predicate

1. Check the step count. The supplied num_instances must be nonzero. It must equal the number of step instances carried by the proof, and it must equal the num_steps value bound into the verifier key. These checks prevent a proof for one step count from being replayed under another count.

2. Restore the shared witness commitment. The proof stores one shared witness commitment, comm_W_shared. The verifier attaches that same commitment to every step instance and to the core instance before any instance validation. After this point, each split instance is interpreted as if it had carried the shared commitment inline.

3. Validate the split step and core instances. Each step instance is validated against the step split shape. For step index \(i\), the verifier creates a fresh Keccak Fiat–Shamir transcript, absorbs the verifier-key digest, the number of step circuits, the circuit index, and that instance’s public values, then calls the split-instance validation routine described in R1CS and its variants. Validation checks public-value length, checks the commitments required by the shape, absorbs the early witness commitments, re-derives the stored Fiat–Shamir challenges, compares them exactly, and absorbs the rest commitment. The core instance is validated similarly against the core split shape, with the verifier-key digest and core public values as its public transcript context. After validation, the verifier checks that every step instance and the core instance carry the same comm_W_shared.

4. Convert split instances to regular R1CS instances. The step list is padded to a power of two by repeating the first step instance when necessary. Each padded step instance is converted to a regular instance by combining its split witness commitments and setting its public vector to public values followed by split challenges. The core instance is converted the same way, without step-count padding. This is the strict R1CS layer; relaxed R1CS appears only after the later Nova fold.

5. Reconstruct the main protocol transcript. The verifier starts the protocol transcript in the same domain as the prover, absorbs the verifier-key digest, the regular core instance, every regular step instance, and the scalar \(T=0\). It computes the padded step-folding round count, the step row round count, and the inner round count. It then draws \(\tau\) and the \(\rho\) challenges used by NeutronNova folding. This chapter records the structure; the transcript schedule fixes the byte-level labels and order.

6. Validate the verifier-circuit instance and read its public input. The proof’s U_verifier is a multi-round split R1CS instance for the verifier circuit. The verifier validates it against vc_shape, using the live protocol transcript, then converts it to regular form. In regular form, the public vector is the flattened verifier-circuit challenges followed by the verifier-circuit public values, as described in the in-circuit verifier. The verifier requires the challenge prefix length to be

   \[ \ell_b + \ell_x + 1 + \ell_y, \]

   where \(\ell_b\) is the step-folding round count, \(\ell_x\) is the outer row round count, and \(\ell_y\) is the inner round count. The six public values must follow immediately, in this order:

   Position	Value
   0	tau_at_rx
   1	eval_X_step
   2	eval_X_core
   3	eq_rho_at_rb
   4	quotient_step
   5	quotient_core

   The challenge prefix is parsed as \(r_b\), then \(r_x\), then the single bridge challenge \(r\), then \(r_y\).

7. Fold the step instances and verify the Nova fold. Using \(r_b\), the verifier calls fold_multiple on the regular step instances. This derives the NeutronNova folding weights and linearly combines the step public vectors and witness commitments into one folded step instance. In parallel with that computation, the verifier checks the Nova folding for zero-knowledge proof: it absorbs the random relaxed instance, the regular verifier-circuit instance, and the cross-term commitment, squeezes the Nova fold challenge, and obtains the folded relaxed verifier-circuit instance. The folding background is in NeutronNova folding.

8. Verify the relaxed-Spartan proof. The verifier runs the Relaxed Spartan verifier over the folded relaxed verifier-circuit instance, using the regular verifier-circuit shape and verifier-circuit commitment key from the verifier key. This proves satisfaction of the masked folded verifier-circuit relation produced by the Nova fold.

9. Pin the six soundness-binding public values natively. The verifier recomputes the six public values outside the circuit and compares them with the six values exposed by U_verifier. This is the soundness-binding step.

   First, it evaluates the step and core matrix tables at the native verifier points. The row point is \(r_x\), and the column point is the full \(r_y\). For \(\star \in \{\mathrm{step},\mathrm{core}\}\), the verifier computes

   \[ Q_\star = \widetilde{A}_\star(r_x,r_y) + r\,\widetilde{B}_\star(r_x,r_y) + r^2\,\widetilde{C}_\star(r_x,r_y). \]

   The implementation names these values quotient_step and quotient_core. This quotient convention matches the Spartan argument: the batched matrix evaluation is eval_A + r·eval_B + r²·eval_C.

   Next, it evaluates the folded step public-input polynomial and the core public-input polynomial at \(r_y[1..]\). Each public-input table is formed from the leading constant \(1\) followed by the regular instance public vector. It also computes tau_at_rx from the powers polynomial determined by \(\tau\) at \(r_x\), and computes eq_rho_at_rb as the equality-polynomial value \(\widetilde{\mathrm{eq}}(r_b,\rho)\).

   The verifier then applies an exact six-way equality gate:

   \[ (\mathrm{tau\_at\_rx},\mathrm{eval\_X\_step},\mathrm{eval\_X\_core},\mathrm{eq\_rho\_at\_rb},\mathrm{quotient\_step},\mathrm{quotient\_core}) = (x_0,x_1,x_2,x_3,x_4,x_5). \]

   Here \((x_0,\ldots,x_5)\) are the six public values read from U_verifier. Any mismatch rejects.

   This native recomputation is mandatory. The verifier circuit proves the folding and sum-check relations, but the six exposed openings must be tied to the actual verifier key, step instances, core instance, and transcript challenges held by the native verifier. The equality gate closes the soundness gap that would remain if the verifier trusted only the circuit-exposed values.

10. Verify the final PCS opening. The transcript supplies the folding challenge c_eval. The verifier folds the folded-step witness commitment with the core witness commitment using coefficients \(1\) and c_eval. It also folds the two verifier-circuit evaluation commitments with the same coefficients. The prover-side relation folds the matching blinds. The verifier then checks the zero-knowledge Hyrax/IPA polynomial-commitment opening at the point \(r_y[1..]\), using the folded witness commitment, the folded evaluation commitment, and eval_arg.

Result

If all ten checks pass, verification returns the original per-step public values and the original core public values. Those values are not reinterpreted by the proof system; their application meaning is supplied by the circuits used in setup and proving. The surrounding proving flow is described in Proving, and the privacy layer is described in Zero knowledge.

Zero-knowledge

This chapter identifies where \(\mathrm{Vega}_{\mathrm{MC}}\) obtains zero-knowledge in the online proof and why the deterministic algebraic checks do not reveal the witness. It complements the structural proving pipeline in Proving and the verifier behavior in Verification.

System zero-knowledge comes from masking

The verifier-circuit proof is protected by a fresh relaxed-R1CS mask. For each proof, the prover samples random_U and its witness as a full-length random satisfying relaxed instance for the verifier-circuit shape. The sampled error vector need not be zero; it is chosen so the relaxed relation is satisfied for the sampled witness, public values, and scalar \(u\).

The prover then invokes the Nova NIFS fold described in Nova ZK folding. The first input U1 is the mask instance random_U with coefficient \(1\). The second input U2 is the real verifier-circuit instance with coefficient \(r\), where \(r\) is squeezed after both inputs and the cross-term commitment are absorbed. The folded scalar fields have the form mask plus \(r\) times real data, so the folded relaxed instance is masked by fresh full-length randomness.

The folded instance is then proved with a relaxed-Spartan direct opening. This relaxed-Spartan proof is deliberately non-hiding on its own: it opens linear combinations of the folded witness and folded error. It reveals nothing about the real verifier-circuit witness because those opened values belong to the masked fold. The proof stores random_U, and the verifier replays the same Nova NIFS fold with random_U, the real U_verifier, and the NIFS commitment.

Witness-evaluation hiding comes from the PCS opening

The main Spartan checks need one committed-witness evaluation for the folded step branch and one for the core branch. The prover folds those two evaluation claims and opens the folded witness commitment at \(r_y[1..]\). The opening argument is the Hyrax PCS evaluation argument backed by the zero-knowledge linear IPA. The IPA samples fresh masking vector and scalar randomness before responding to the transcript challenge, so the opened evaluation is checked without exposing the committed witness vector.

Folded sum-check transcript hiding

The NeutronNova and Spartan sum-check stages feed the in-circuit verifier through committed multi-round witnesses. Round polynomials and evaluation values are assigned inside the verifier-circuit witness; the transcript absorbs the corresponding commitments and then squeezes the next challenges. The public transcript therefore sees commitments to those values rather than the raw witness values. The generic algebra is described in sum-check, and the step-folding use of these rounds is described in NeutronNova.

Deterministic stages are safe

After setup inputs, circuits, public values, and randomness are fixed, the online prover is deterministic: it builds the same split instances, derives the same Fiat–Shamir challenges, runs the same folding and sum-check reductions, and assembles the same proof fields. Fresh randomness is the only honest-prover divergence between two proofs of the same statement. It enters wherever the prover commits or opens with fresh hiding randomness: the rerandomized prepared state in Preparation, the per-round commitments of the in-circuit verifier, the cross-term commitment of the Nova fold, the fresh relaxed mask random_U, and the zero-knowledge IPA opening.

This supports the byte-equivalence goal developed in Specification scope: an independent prover driven with identical inputs and identical randomness produces identical proof bytes. Different honest proofs of the same statement differ only because the rerandomization and zero-knowledge openings consume fresh randomness.

Scope and the conformance contract

This chapter is the entry point to the implementable specification for \(\mathrm{Vega}_{\mathrm{MC}}\). It defines the conformance contract for an independently built prover and maps the chapters that pin the bytes, transcript, verifier key, proof object, reference prover, and test vectors.

Canonical engine

The specification fixes one concrete instantiation: the T256 elliptic curve, a Keccak-based Fiat–Shamir transcript, and the Hyrax polynomial commitment scheme. This instantiation is the canonical engine. Other curve or engine choices may exist in an implementation, but they are outside this specification.

All proof-system arithmetic is over the scalar field \(\mathbb{F}\) of the canonical curve, a roughly 256-bit prime field defined in Fields, groups, and the engine. The group is \(\mathbb{G}\), and this part specifies the multi-circuit prover \(\mathrm{Vega}_{\mathrm{MC}}\), the book’s focus.

Verifier acceptance is the ground truth

The verifier’s decision procedure is the acceptance predicate. A proof is valid exactly when verify accepts it under the verifier key. verify takes the verifier key and the number of instances; it does not take the public values as an argument. Instead it recomputes them from the proof and returns them, and the application compares the returned values against the statement it intended to prove. A prover conforms at the acceptance level when every proof it emits for a satisfied statement is accepted by that verifier.

This chapter does not restate verification. Verification gives the verifier procedure, and the following specification chapters pin every input the verifier consumes.

Proof bytes and determinism

A proof is a structured value serialized to a byte string by the fixed deterministic serialization in Serialization. Every serialized field is a deterministic function of four inputs:

• the verifier key;
• the public values;
• the witness;
• the prover’s random tape.

These inputs are mediated by the fixed Fiat–Shamir transcript. Two provers that implement the same transcript schedule, use the same encodings, and consume identical randomness produce byte-identical proofs.

The only nondeterminism in an honest proof is zero-knowledge randomness: the commitment blinds and one freshly sampled random masking instance drawn once per proof. Because the honest prover samples this randomness fresh, two runs on the same statement normally produce different proof bytes, and both proofs verify. Byte equality is therefore relative to a fixed random tape; validity holds for any well-formed zero-knowledge randomness.

This gives two useful conformance notions:

• An accept-conforming prover emits proofs accepted by verify.
• A byte-conforming prover, when driven with the same inputs and identical randomness, reproduces the reference prover’s exact serialized proof bytes.

What must be reproduced

A conforming implementation must reproduce exactly:

1. the Fiat–Shamir transcript schedule: every absorbed label, absorbed value, absorbed encoding, and squeezed challenge, in order;
2. the proof object’s contents and their deterministic serialization.

Nothing else is part of the conformance surface. Prover-internal choices such as delayed modular reduction, small-integer matrix–vector arithmetic, caches, memory layout, batching, and parallelism affect performance but not the emitted proof bytes or the transcript. A direct unoptimized prover can therefore be byte-equivalent to an optimized library while being easier to implement and audit.

Given the same verifier key, public values, witness, and random tape, exact agreement on the transcript schedule and serialized proof object yields the same verifier challenges and proof bytes. Given any well-formed zero-knowledge randomness, exact agreement on the transcript schedule and proof object yields proofs accepted by the canonical verifier.

Specification map

The remaining chapters in this part fix the byte-exact contract:

• Serialization specifies the wire byte format, including integer, sequence, enum, field, and point encodings.
• The transcript schedule specifies the exact ordered sequence of transcript absorbs and squeezes.
• The verifier key specifies the verifier key contents and its digest.
• The proof object specifies the proof’s field-by-field byte layout.
• The reference prover specifies a direct unoptimized prover that realizes this specification.
• Test vectors specifies conformance test vectors and how to check them.

Two building-block chapters supply primitives used by this part: Transcript primitive encodings specifies the values absorbed into transcripts, and The Fiat–Shamir transcript specifies the transcript mechanism.

Out of scope

This specification part does not give the verifier’s soundness or zero-knowledge security arguments, which are treated conceptually in Design goals and threat model. It also excludes non-canonical engines and performance characteristics of any particular prover implementation.

Serialization and encodings

This chapter specifies the canonical byte string for a Vega proof object in the canonical T256 + Hyrax instantiation: the proof wire format. This is separate from the Fiat–Shamir transcript encodings in Byte encodings and serialization: transcript encodings decide which bytes are hashed into challenges, while wire serialization decides the bytes carried by the proof.

Serialization domain

A proof is serialized by applying the rules in this chapter to the proof object. The reference implementation obtains the same bytes by calling bincode::serialize(&proof) with bincode 1.3.3.

The effective bincode configuration is:

integer encoding: fixed-width integers (fixint), not varint
byte order:       little-endian for integer primitives
byte limit:       none

Equivalently, the emitted bytes match DefaultOptions::new().with_little_endian().with_fixint_encoding(). This equivalence concerns the produced bytes only; trailing-byte handling is a deserialization policy and does not change the serialized output. The verifier-key digest reuses this bincode configuration for most of its fields but encodes the constraint-system matrices through a separate manual byte routine; its object and digest domain are specified in Verifier key and digest.

An implementation does not need to use bincode. The following sections are the complete wire-format rules.

Rust-shaped values

The proof object is a structured value whose fields are serialized recursively. Primitive integers use fixed widths; containers carry lengths where the table says they do.

Worked examples:

usize value 5:
05 00 00 00 00 00 00 00

Vec<u8> value [aa, bb]:
02 00 00 00 00 00 00 00  aa bb

Option<u32> value Some(1):
01  01 00 00 00

Option<u32> value None:
00

enum unit variant at index 0:
00 00 00 00

enum variant at index 1 carrying u8 value 7:
01 00 00 00  07

String value "hi":
02 00 00 00 00 00 00 00  68 69

Struct serialization has no enclosing marker. A single-field struct serializes exactly as its field.

Scalar-field elements

A scalar in \(\mathbb{F}\) serializes as the field element’s canonical 32-byte to_repr output. For the scalar field in the canonical engine, this representation is little-endian.

wire_scalar(s) = le32(integer representative of s)

Examples:

scalar 1:
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

scalar 258 = 0x0102:
02 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

The transcript encoding of a scalar is different: the transcript chapter encodes scalar-field elements as 32 big-endian bytes. The transcript path reverses the scalar field’s native little-endian representation; the wire path uses that native representation directly.

Base-field elements

A base-field element serializes on the wire as its canonical 32-byte to_repr output. For the base field in the canonical engine this representation is little-endian, exactly as for the scalar field.

wire_base(x) = le32(integer representative of x)

Both fields therefore serialize little-endian on the wire. The two fields differ only in the transcript path: the scalar field’s transcript encoding is big-endian, while the base field’s is little-endian (the transcript chapter). That asymmetry comes from the field backends’ to_bytes methods — little-endian for the scalar field and big-endian for the base field — which the transcript reverses. The wire path uses to_repr, which is little-endian for both fields, so it is unaffected by that asymmetry.

A bare base-field element never appears as a standalone value in the proof object. The base field reaches the wire only as the x-coordinate inside a compressed group element, described next, where the point-compression routine writes it big-endian.

Group elements

A group element in \(\mathbb{G}\) serializes to exactly 33 bytes in compressed form:

wire_point(P) = flag_byte || x

flag_byte: 1 byte
x:         32 bytes, the affine x-coordinate in big-endian byte order

The x-coordinate occupies the 32 bytes following the flag byte, written as a 32-byte big-endian integer. This big-endian order is produced by the point-compression routine, which uses the base field’s to_bytes method; it is not the little-endian wire_base encoding used for a standalone base-field element.

The flag byte uses two bits. All other bits are zero.

The identity serializes as the identity flag followed by a zero x-coordinate:

40 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

The canonical generator has x-coordinate 3 and an odd y-coordinate. Its compressed wire encoding is:

80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03

The transcript encoding of a group element is different: the transcript chapter uses the uncompressed 64-byte string x || y, where each coordinate is a 32-byte little-endian base-field element (defined for non-identity points; the transcript path does not encode the identity). The wire encoding uses the compressed 33-byte string flag || x, where x is big-endian and the identity is encoded explicitly. The same point therefore has two byte representations in two domains: transcript input and proof wire serialization.

Commitment example

A HyraxCommitment is a vector of group elements wrapped in a single-field struct. Since single-field structs serialize exactly as their field, a commitment’s wire bytes are the vector bytes:

wire_commitment([P0, P1, ..., P(n-1)]) =
    u64_le(n) || wire_point(P0) || wire_point(P1) || ... || wire_point(P(n-1))

For a one-point commitment to the canonical generator, the bytes are an 8-byte count followed by the 33-byte compressed generator:

01 00 00 00 00 00 00 00
80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03

This example shows how the primitive rules compose. The exact top-level proof fields and their declaration order are specified in The proof object. The transcript schedule that consumes proof components is specified in The transcript schedule, and the transcript byte encodings themselves are specified in Byte encodings and serialization.

The transcript schedule

The transcript schedule is the exact ordered sequence of absorb, squeeze, and dom_sep operations that derives every Fiat–Shamir challenge in \(\mathrm{Vega}_{\mathrm{MC}}\). The canonical order is the order performed by verify; a byte-conforming prover reproduces the identical operation stream. The transcript mechanism is specified in The Fiat–Shamir transcript, and the value bytes fed to absorb are specified in Byte encodings and serialization. Every transcript in this chapter is created with the domain label b"neutronnova_prove".

Notation

This chapter writes transcript operations as:

absorb(label, value)
squeeze(label) -> challenge
dom_sep(bytes)

The label argument is a fixed ASCII byte string. The value argument is encoded as specified by Byte encodings and serialization. A count written Scalar(n) — for example Scalar(num_steps) — denotes the integer n reduced into \(\mathbb{F}\) and absorbed with the scalar transcript encoding, not as a machine word. A squeeze consumes the transcript state produced by all preceding operations, including everything absorbed since the previous squeeze. Ordering disambiguates reused labels: b"r", b"challenge", and b"p"/b"c" appear in more than one place.

Symbolic counts are used here. Concrete verifier-key dimensions and proof-object field shapes are pinned by The verifier key and The proof object.

num_steps        = vk.num_steps
padded_steps     = next_pow2(num_steps)
num_rounds_b     = log2(padded_steps)
num_vars         = S_step.num_shared + S_step.num_precommitted + S_step.num_rest
num_rounds_x     = log2(S_step.num_cons)
num_rounds_y     = log2(num_vars) + 1
outer_rounds     = log2(vc_shape_regular.num_cons)
inner_rounds     = log2(next_pow2(vc_shape_regular.num_vars)) + 1

The verifier-instance challenges are concatenated as r_b | r_x | r | r_y, with lengths num_rounds_b, num_rounds_x, 1, and num_rounds_y.

During setup every R1CS shape has its constraint count padded to a power of two, and the step and core shapes S_step and S_core also have their variable counts padded to a power of two. So num_rounds_x, num_rounds_y, and outer_rounds are exact base-two logarithms. The one exception is vc_shape_regular.num_vars: it is the sum of the verifier circuit’s per-round witness widths and is not itself padded to a power of two — it is 640 in the cubic fixture — so inner_rounds rounds it up with next_pow2, exactly as the shipped relaxed-Spartan verifier does. Every round count is a fixed non-negative integer determined by the shapes rather than by the witness.

Phases at a glance

1. Instance validation.
2. Main setup.
3. Verifier-instance rounds.
4. NIFS fold.
5. Relaxed Spartan.
6. PCS opening.

Phase A — Instance validation

Instance validation uses independent throwaway transcripts, one per instance. The prover produces these per-instance challenges during witness commitment, and the verifier replays the same stream to re-derive and check them.

For each step instance i, in increasing order from 0 through num_steps - 1, the step-instance preamble absorbs b"vk", b"num_circuits", b"circuit_index", and b"public_values". The validation body is then run for S_step.

new transcript: TE::new(b"neutronnova_prove")
absorb(b"vk", vk_digest)
absorb(b"num_circuits", Scalar(num_steps))
absorb(b"circuit_index", Scalar(i))
absorb(b"public_values", step_i.public_values)

if S_step.num_shared > 0:
    absorb(b"comm_W_shared", comm_W_shared)
if S_step.num_precommitted > 0:
    absorb(b"comm_W_precommitted", comm_W_precommitted)
repeat S_step.num_challenges times:
    squeeze(b"challenge") -> checked against step_i.challenges
absorb(b"comm_W_rest", comm_W_rest)

The core instance uses the same transcript domain and validation body, but its preamble omits b"num_circuits" and b"circuit_index". The body is run with S_core dimensions.

new transcript: TE::new(b"neutronnova_prove")
absorb(b"vk", vk_digest)
absorb(b"public_values", core.public_values)

if S_core.num_shared > 0:
    absorb(b"comm_W_shared", comm_W_shared)
if S_core.num_precommitted > 0:
    absorb(b"comm_W_precommitted", comm_W_precommitted)
repeat S_core.num_challenges times:
    squeeze(b"challenge") -> checked against core.challenges
absorb(b"comm_W_rest", comm_W_rest)

Phase B — Main setup

Phase B creates the single main transcript that is carried through Phase F. It binds the verifier-key digest, the regular core instance, every padded regular step instance, and the initial zero scalar b"T" before deriving \(\tau\) and the rho vector.

new transcript: TE::new(b"neutronnova_prove")
absorb(b"vk", vk_digest)
absorb(b"core_instance", core_instance_regular)        // R1CSInstance
// step_instances_regular has num_steps entries; pad to padded_steps
// by repeating the first entry, step_instances_regular[0].
for each U in the padded step-instance list, in order:
    absorb(b"U", U)                                     // R1CSInstance
absorb(b"T", Scalar::ZERO)
squeeze(b"tau") -> tau
repeat num_rounds_b times:
    squeeze(b"rho") -> next rho

Phase C — Verifier-instance rounds

Phase C validates the split multi-round verifier instance on the main transcript. Each round absorbs that round’s witness commitment and then squeezes exactly that round’s challenge count.

for each round in 0..vc_shape.num_rounds, in order:
    absorb(b"comm_w_round", comm_w_per_round[round])
    repeat num_challenges_per_round[round] times:
        squeeze(b"challenge") -> checked against challenges_per_round[round]

The concatenated squeezed challenges are the in-circuit challenges r_b | r_x | r | r_y.

Phase D — NIFS fold

Phase D performs the transcript part of nifs.verify on the main transcript. The concurrent fold performed alongside it does not touch the transcript.

absorb(b"U1", random_U)                         // RelaxedR1CSInstance
absorb(b"U2", U_verifier_regular)               // R1CSInstance
absorb(b"comm_T", nifs.comm_T)
squeeze(b"r") -> folding challenge

Phase E — Relaxed Spartan

Phase E verifies the relaxed Spartan proof on the main transcript. The first two absorbs bind the folded relaxed verifier instance, then outer_rounds squeezes derive the outer sumcheck evaluation point.

absorb(b"u_relaxed", folded_U_verifier.u)
absorb(b"X_relaxed", folded_U_verifier.X)
repeat outer_rounds times:
    squeeze(b"t") -> next outer challenge

A sumcheck round absorbs the round’s univariate polynomial as b"p", encoded as a UniPoly, and then squeezes b"c". The outer sumcheck uses degree bound 3 and runs for outer_rounds rounds.

repeat outer_rounds times:
    absorb(b"p", round_poly)                    // UniPoly, degree bound 3
    squeeze(b"c") -> next outer sumcheck challenge

The transcript then binds the three outer claims, derives the inner-combination challenge, runs the inner sumcheck with degree bound 2, and absorbs the witness and error evaluations.

absorb(b"claims_outer", [claim_Az, claim_Bz, claim_uCzE])
squeeze(b"r") -> inner-combination challenge
repeat inner_rounds times:
    absorb(b"p", round_poly)                    // UniPoly, degree bound 2
    squeeze(b"c") -> next inner sumcheck challenge
absorb(b"v_W", v_W)
absorb(b"v_E", v_E)

Phase F — PCS opening

Phase F derives the folded evaluation challenge, verifies the Hyrax opening, and then verifies the linear IPA subargument. The b_vec value is intentionally omitted from the IPA instance absorb because the verifier recomputes it from public transcript state and opening inputs.

squeeze(b"c_eval") -> folded evaluation challenge

absorb(b"poly_com", comm)                       // folded HyraxCommitment

dom_sep(b"inner product argument (linear)")
absorb(b"U", ipa_instance)                       // comm_a_vec || comm_c; b_vec omitted
absorb(b"delta", delta)
absorb(b"beta", beta)
squeeze(b"r") -> IPA challenge

The encodings for HyraxCommitment, group elements, scalar slices, and IPA values are defined in Byte encodings and serialization. The polynomial-commitment context is described in Polynomial commitments.

Complete ordered schedule

This block is the end-to-end reference summary. It preserves the ordering from Phase A through Phase F.

Phase A: independent validation transcript for each step instance i = 0..num_steps - 1
    new transcript: TE::new(b"neutronnova_prove")
    absorb(b"vk", vk_digest)
    absorb(b"num_circuits", Scalar(num_steps))
    absorb(b"circuit_index", Scalar(i))
    absorb(b"public_values", step_i.public_values)
    if S_step.num_shared > 0:
        absorb(b"comm_W_shared", comm_W_shared)
    if S_step.num_precommitted > 0:
        absorb(b"comm_W_precommitted", comm_W_precommitted)
    repeat S_step.num_challenges times:
        squeeze(b"challenge")
    absorb(b"comm_W_rest", comm_W_rest)

Phase A: independent validation transcript for the core instance
    new transcript: TE::new(b"neutronnova_prove")
    absorb(b"vk", vk_digest)
    absorb(b"public_values", core.public_values)
    if S_core.num_shared > 0:
        absorb(b"comm_W_shared", comm_W_shared)
    if S_core.num_precommitted > 0:
        absorb(b"comm_W_precommitted", comm_W_precommitted)
    repeat S_core.num_challenges times:
        squeeze(b"challenge")
    absorb(b"comm_W_rest", comm_W_rest)

Phase B: main transcript setup
    new transcript: TE::new(b"neutronnova_prove")
    absorb(b"vk", vk_digest)
    absorb(b"core_instance", core_instance_regular)
    // pad step_instances_regular to padded_steps by repeating its first entry
    for each U in the padded step-instance list, in order:
        absorb(b"U", U)
    absorb(b"T", Scalar::ZERO)
    squeeze(b"tau")
    repeat num_rounds_b times:
        squeeze(b"rho")

Phase C: verifier-instance rounds on the main transcript
    for each round in 0..vc_shape.num_rounds, in order:
        absorb(b"comm_w_round", comm_w_per_round[round])
        repeat num_challenges_per_round[round] times:
            squeeze(b"challenge")

Phase D: NIFS fold on the main transcript
    absorb(b"U1", random_U)
    absorb(b"U2", U_verifier_regular)
    absorb(b"comm_T", nifs.comm_T)
    squeeze(b"r")

Phase E: relaxed Spartan on the main transcript
    absorb(b"u_relaxed", folded_U_verifier.u)
    absorb(b"X_relaxed", folded_U_verifier.X)
    repeat outer_rounds times:
        squeeze(b"t")
    repeat outer_rounds times:
        absorb(b"p", round_poly)       // outer sumcheck, degree bound 3
        squeeze(b"c")
    absorb(b"claims_outer", [claim_Az, claim_Bz, claim_uCzE])
    squeeze(b"r")
    repeat inner_rounds times:
        absorb(b"p", round_poly)       // inner sumcheck, degree bound 2
        squeeze(b"c")
    absorb(b"v_W", v_W)
    absorb(b"v_E", v_E)

Phase F: PCS opening on the main transcript
    squeeze(b"c_eval")
    absorb(b"poly_com", comm)
    dom_sep(b"inner product argument (linear)")
    absorb(b"U", ipa_instance)
    absorb(b"delta", delta)
    absorb(b"beta", beta)
    squeeze(b"r")

What a conforming prover must reproduce

A byte-conforming prover must reproduce the exact operation stream: the same transcript domain label, the same absorb, squeeze, and dom_sep calls, the same labels, the same ordering, and the same value encodings. This is the transcript component of the conformance contract defined in Scope and the conformance contract.

For adjacent byte-exact rules, see Byte encodings and serialization for transcript input encodings, The Fiat–Shamir transcript for the transcript primitive, The verifier key for verifier-key dimensions and digest construction, and The proof object for proof fields consumed by this schedule.

Verifier key and digest

The verifier key is the public parameter set that verify consumes. It is produced once by setup from the step and core circuits and the canonical curve, and it is shared unchanged by the prover and the verifier. The verifier key is not serialized into the proof. Its role in the byte-exact contract is indirect but decisive: a 32-byte digest of the verifier key is the first value absorbed into the Fiat–Shamir transcript, so every later challenge depends on it. A byte-equivalent prover must therefore compute the identical digest, which requires both the identical verifier-key contents and the identical digest algorithm specified here.

Verifier key contents

The verifier key is a structure with nine serialized fields, in this declaration order:

A tenth field caches the digest once computed; it is marked non-serialized and never contributes bytes.

The contents of these fields are fixed by setup and fully reproducible: the same step circuit, core circuit, num_steps, and canonical curve produce the same verifier key, down to the byte. That determinism is a security property rather than a convenience. The verifier key is the protocol’s root of trust — verify must be run against the one canonical key for a statement, not an arbitrary key handed over with a proof — and its commitment generators are nothing-up-my-sleeve points obtained by hashing fixed labels to the curve (see Setup), so no party knows a discrete-logarithm relation among them. Because the derivation is fully determined, an independent implementation can regenerate this key and check it rather than take it on trust; the reference prover does exactly that. This chapter does not respecify setup; it specifies how the digest is computed from an existing verifier key.

To load an existing key rather than regenerate it, note that the serialized vk.bin is the ordinary bincode serialization of these nine fields in declaration order — identical to the digest stream below except that S_step and S_core appear in their ordinary bincode split-R1CS-shape form instead of the shape_raw encoding, and the cached digest field is skipped. The byte-critical requirement for a byte-equivalent prover is the digest specified here, so this chapter pins that stream exactly; an implementation that needs to parse vk.bin itself can follow the reference vk.py, or simply regenerate the key via Setup and check its digest.

The digest

The digest is the SHA-256 hash of a single byte string \(D\) built from the verifier-key fields. The hash input is streamed field by field; there is no domain-separation tag, length prefix, or trailing marker around \(D\).

digest = SHA-256(D)          // 32-byte output

D = bincode(ck)
 || bincode(vk_ee)
 || shape_raw(S_step)
 || shape_raw(S_core)
 || bincode(vc_shape)
 || bincode(vc_shape_regular)
 || bincode(vc_ck)
 || bincode(vc_vk)
 || bincode(num_steps)

This order is fixed by the verifier key’s digest routine, which writes the fields in the declaration order above; a byte-equivalent prover must reproduce this exact sequence rather than rely on any automatic struct serialization. Two encodings appear:

• bincode(v) is the little-endian fixint encoding of Serialization, applied recursively to the value’s type. bincode(num_steps) is therefore an 8-byte little-endian u64. This is the raw number of step instances passed to setup; it is not rounded up to a power of two. The power-of-two padding used elsewhere in the protocol affects only the number of folding rounds, never this stored count.
• shape_raw is a compact hand-written encoding used only for the two circuit shapes. It is not bincode: it exists so the large constraint-system matrices hash quickly, and it is the reason the digest is a mix of two encodings rather than one uniform bincode call.

The nested layouts of the bincode-encoded fields (ck, vk_ee, vc_shape, vc_shape_regular, vc_ck, vc_vk) are pinned field by field in Bincode object layouts below, using the primitive, sequence, field, and point encodings from Serialization.

Shape and matrix raw encoding

A split R1CS shape hashes as ten dimension counts followed by its three constraint matrices:

shape_raw(S) =
     u64_le(S.num_cons)
  || u64_le(S.num_cons_unpadded)
  || u64_le(S.num_shared_unpadded)
  || u64_le(S.num_precommitted_unpadded)
  || u64_le(S.num_rest_unpadded)
  || u64_le(S.num_shared)
  || u64_le(S.num_precommitted)
  || u64_le(S.num_rest)
  || u64_le(S.num_public)
  || u64_le(S.num_challenges)
  || matrix_raw(S.A)
  || matrix_raw(S.B)
  || matrix_raw(S.C)

Each matrix is stored in compressed sparse row form: a data array of nonzero field values, a parallel indices array of column indices, an indptr array of row-start offsets, and a cols column count. It hashes as three lengths and the column count, followed by the three arrays:

matrix_raw(M) =
     u64_le(len(M.data))
  || u64_le(len(M.indices))
  || u64_le(len(M.indptr))
  || u64_le(M.cols)
  || for d in M.data:    le32(d)      // scalar-field value, 32 little-endian bytes
  || for i in M.indices: u64_le(i)
  || for p in M.indptr:  u64_le(p)

The data values are scalar-field elements written with the same little-endian 32-byte encoding as a scalar on the wire (Serialization); to_repr for the scalar field is little-endian. The indices and indptr entries are machine-word indices written as 8-byte little-endian u64 values. All four length and count headers are 8-byte little-endian u64 values, even though the underlying values are register-sized.

Bincode object layouts

The six bincode-encoded fields of the digest — ck, vk_ee, vc_shape, vc_shape_regular, vc_ck, and vc_vk — expand by the recursive serialization rules. This section pins each type’s field order so the expansion is unambiguous. Throughout, a usize is an 8-byte little-endian u64, a Vec<T> is an 8-byte little-endian length followed by its elements, a group element is a 33-byte compressed point, and a scalar is 32 little-endian bytes.

Commitment and verifier keys

ck and vc_ck are commitment keys; vk_ee and vc_vk are the matching PCS verifier keys. Both types encode the same three fields, in this order:

A commitment key additionally holds two precomputed fixed-base tables; both are #[serde(skip)] and emit no bytes, so a commitment key and a verifier key of the same width serialize identically. Because vk_ee reuses ck’s generators and vc_vk reuses vc_ck’s, bincode(vk_ee) equals bincode(ck) and bincode(vc_vk) equals bincode(vc_ck), byte for byte.

Verifier-circuit shapes

vc_shape is a split multi-round shape; vc_shape_regular is the same constraint system viewed as a single-round R1CS shape. Their fields serialize in these orders:

Both types also carry a #[serde(skip)] cached digest that emits no bytes.

Bincode sparse matrix

Inside the two verifier-circuit shapes, each matrix is bincode-encoded, which is not the matrix_raw layout used for S_step and S_core. The bincode form length-prefixes each array inline and places cols last:

bincode(M) =
     u64_le(len(M.data))    || for d in M.data:    le32(d)
  || u64_le(len(M.indices)) || for i in M.indices: u64_le(i)
  || u64_le(len(M.indptr))  || for p in M.indptr:  u64_le(p)
  || u64_le(M.cols)

The matrix_raw form above instead groups all four counts first and then the three arrays. Both carry the same numbers; S_step/S_core use matrix_raw in the digest, while vc_shape/vc_shape_regular use this bincode form.

The digest in the transcript

The 32-byte SHA-256 output is the digest. It enters the transcript as raw bytes:

transcript.absorb("vk", digest)

The digest’s transcript encoding is its 32 bytes in order, with no reversal and no field reduction: it is hashed as an opaque byte string, not as a field element. The exact position of this absorb in the schedule is specified in The transcript schedule.

The proof object

This chapter specifies the byte-exact layout of VegaMcZkSNARK, the value that \(\mathrm{Vega}_{\mathrm{MC}}\)’s verify procedure consumes. The proof is the bincode serialization of this struct, applied recursively until every field resolves to a primitive. All primitive encodings — scalars, group elements, sequences, options, and tuples — live in Serialization; this chapter specifies structure: which fields exist, in which order, and of which type.

The proof path contains no user-defined enums — so the enum variant-index encoding never appears — and no cached or skipped fields. The only sum types are the Option<Commitment> values: comm_W_shared at the top level and the two Option<Commitment> fields inside each SplitR1CSInstance, all of which use the one-byte Option tag encoding. Every other field contributes bytes unconditionally.

Single-field struct transparency

Several types in the proof tree are single-field structs. The struct rule in Serialization states that a single-field struct serializes exactly as its field, with no extra tag, length prefix, or padding. Treating these as opaque containers and inserting framing bytes produces incorrect output. The affected types are:

A Commitment is a type alias for HyraxCommitment, so every commitment in the proof is transparently a length-prefixed vector of 33-byte compressed group elements. The commitment example in the serialization chapter works through the encoding in full.

Top-level object: VegaMcZkSNARK

The proof has eight fields in this declaration order:

VegaMcZkSNARK =
     comm_W_shared
  || step_instances
  || core_instance
  || eval_arg
  || U_verifier
  || nifs
  || random_U
  || relaxed_snark

Shared-witness optimization. When several step circuits share a common witness prefix, its commitment is identical across every step instance and the core instance. The prover sets the top-level comm_W_shared to a clone of the first step instance’s comm_W_shared, then sets the per-instance comm_W_shared to None in every element of step_instances and in core_instance. In the serialized proof, each instance’s comm_W_shared is therefore always the single tag byte 00; the shared commitment, when present, appears only at the top level. When the circuits declare no shared witness prefix — as in the cubic fixtures, where num_shared == 0 — the first step instance’s comm_W_shared is itself None, so the top-level field is also None (a lone 00 tag byte) and no shared-commitment bytes appear anywhere in the proof. The verifier copies the top-level value back into each instance before checking.

R1CS instance types

SplitR1CSInstance

Each element of step_instances and the core_instance field are of this type. Five fields in declaration order:

SplitR1CSInstance =
     comm_W_shared        (Option<Commitment>)
  || comm_W_precommitted  (Option<Commitment>)
  || comm_W_rest          (Commitment)
  || public_values        (Vec of Scalar)
  || challenges           (Vec of Scalar)

Each Option<Commitment> follows the Option encoding: one tag byte (00 = None, 01 = Some), then the commitment bytes if the tag is 01.

SplitMultiRoundR1CSInstance

The U_verifier field is of this type. Three fields:

SplitMultiRoundR1CSInstance =
     comm_w_per_round     (Vec of Commitment)
  || public_values        (Vec of Scalar)
  || challenges_per_round (Vec of Vec of Scalar)

challenges_per_round is a Vec of Vecs. The outer Vec carries an 8-byte u64 count; each inner Vec carries its own 8-byte count followed by its scalars. There is no extra framing between the inner vectors beyond what the Vec rule provides.

RelaxedR1CSInstance

The random_U field is of this type. Four fields:

RelaxedR1CSInstance =
     comm_W  (Commitment)
  || comm_E  (Commitment)
  || X       (Vec of Scalar)
  || u       (Scalar, 32 bytes)

Evaluation argument

HyraxEvaluationArgument

HyraxEvaluationArgument is a single-field struct whose sole field is ipa : InnerProductArgumentLinear. Its wire bytes are those of the InnerProductArgumentLinear directly, with no wrapper framing.

InnerProductArgumentLinear

Five fields:

InnerProductArgumentLinear =
     delta   (33-byte compressed point, no length prefix)
  || beta    (33-byte compressed point, no length prefix)
  || z_vec   (Vec of Scalar)
  || z_delta (Scalar, 32 bytes)
  || z_beta  (Scalar, 32 bytes)

delta and beta are bare group elements, not Commitment structs: each is a single 33-byte compressed point with no preceding u64 count. The point encoding is flag || x(BE) as specified in Serialization.

Folding proof

NovaNIFS

NovaNIFS is a single-field struct whose sole field is comm_T : Commitment. Its wire bytes are those of that commitment: an 8-byte u64 count followed by compressed points.

NovaNIFS = comm_T  (Commitment)

Relaxed Spartan proof

RelaxedR1CSSpartanProof

Seven fields in declaration order:

RelaxedR1CSSpartanProof =
     sc_proof_outer   (SumcheckProof)
  || claims_outer.0   (Scalar, 32 bytes)
  || claims_outer.1   (Scalar, 32 bytes)
  || claims_outer.2   (Scalar, 32 bytes)
  || sc_proof_inner   (SumcheckProof)
  || v_W              (Vec of Scalar)
  || blind_W          (Scalar, 32 bytes)
  || v_E              (Vec of Scalar)
  || blind_E          (Scalar, 32 bytes)

claims_outer is a 3-tuple of scalars. Tuples carry no tag, length prefix, or padding (see Serialization), so these three scalars occupy exactly 96 consecutive bytes with no intervening count.

SumcheckProof

SumcheckProof is a single-field struct whose sole field is compressed_polys : Vec<CompressedUniPoly>. Its wire bytes are those of the Vec directly. For a sum-check with \(r\) rounds:

SumcheckProof =
     u64_le(r)            (8-byte round count)
  || CompressedUniPoly_0
  || CompressedUniPoly_1
  || ...
  || CompressedUniPoly_{r-1}

CompressedUniPoly

CompressedUniPoly is a single-field struct whose sole field is coeffs_except_linear_term : Vec<Scalar>. Its wire bytes are those of the Vec directly. A degree-\(d\) round polynomial has \(d + 1\) coefficients; the single linear (degree-1) coefficient is omitted, so exactly \(d\) coefficients are stored — the constant term followed by the degree-2 through degree-\(d\) coefficients:

CompressedUniPoly =
     u64_le(d)     (number of stored coefficients = degree of the round polynomial)
  || Scalar_0      (constant term, degree 0)
  || Scalar_1      (degree 2)
  || ...
  || Scalar_{d-1}  (degree d)

The linear term (the coefficient of the degree-1 monomial) is absent from the proof. The verifier recovers it from the sum-check invariant for the round; no extra bytes are needed. Every stored coefficient is written as a 32-byte little-endian scalar per the scalar encoding.

The complete type tree established here, together with the primitive rules in Serialization, fully determines the byte string for any VegaMcZkSNARK value. The companion chapter A simple reference prover shows how these fields are populated, and Conformance and test vectors provides byte-exact examples that an implementation can check against.

A simple reference prover

The preceding specification chapters pin every byte the verifier consumes: the encodings, the transcript schedule, the verifier key, and the proof object. This chapter supplies the last piece: a complete, runnable prover. Rather than restate the procedure in prose, it points at a working implementation.

Status — preliminary. This reference is an executable specification and teaching aid, not a production prover. It currently proves only the fixed cubic circuit below, favors clarity over speed, and is validated by mutual acceptance with the shipped Rust prover and verifier — but it has not had an independent security audit, and its internals may still change.

The implementation is the specification

The repository ships a small pure-Python reference implementation under reference/pyvega. It omits the performance optimizations in the shipped Rust library — delayed modular reduction, small-value integer arithmetic, multi-scalar-multiplication caches, and parallelism — and computes each value in the most direct way. It is slower than the shipped Rust prover, but its control flow follows the protocol step by step.

A written algorithm can drift from the code it describes; a reference prover cannot, because it is executed and checked against the shipped Rust verifier. The prose in this book explains the design and the wire format; the reference prover is the procedure of record.

Conformance is mutual acceptance, not byte identity

An honest \(\mathrm{Vega}_{\mathrm{MC}}\) proof is randomized: it carries commitment blinds and one freshly sampled random masking instance drawn once per proof (see Zero-knowledge). Two honest runs on the same statement therefore emit different bytes, and both verify. Conformance between two implementations is consequently defined at the level of verifier acceptance, in both directions:

• a proof from the shipped Rust prover is accepted by the reference verifier, and
• a proof from the reference prover — under a verifier key that the reference setup itself produced — is accepted by the shipped Rust verifier.

The reference implementation establishes both directions on the canonical cubic example; the mechanics are described in Conformance and test vectors.

What the reference covers

The reference implements the entire acceptance path end to end, so an implementer can read a working counterpart to each specification chapter:

The worked circuit

To stay self-contained and hand-checkable, the reference proves the tiny cubic relation \(y = x^3 + x + 5\) with \(x = 2\), \(y = 15\) — the same CubicCircuit the Rust test suite uses. Its R1CS has four constraints, yet proving it drives every phase of the protocol: the in-circuit verifier, both folding schemes, both sum-checks, relaxed Spartan, and the zero-knowledge opening. An implementer who reproduces acceptance on this example has therefore exercised every protocol phase, though only at this fixture’s dimensions — two step instances and single-row witness commitments — not for arbitrary circuits.

Because setup is also implemented in Python (setup.py generates the Hyrax generators by hash-to-curve and serializes the verifier key), the reference runs with no dependency on the shipped Rust library at all: it performs setup, proving, and verification itself, and the shipped Rust verifier independently accepts the result.

Conformance and test vectors

This chapter describes how an independent implementation demonstrates conformance: the fixtures it can check against, and the executable gates that establish mutual acceptance with the shipped Rust prover and verifier.

What conformance means here

As established in Scope and the conformance contract, an honest proof is randomized, so conformance is not byte equality of proofs. It is verifier acceptance. Two layers of test make this precise:

1. Deterministic vectors. Some artifacts are fixed functions of their inputs and can be checked byte-for-byte: the parse of a given proof, the Fiat–Shamir challenges derived from a fixed transcript, and the verifier-key digest. An implementation that disagrees on any of these is non-conformant.
2. Acceptance gates. The proof as a whole is checked by running the other side’s verifier and asserting it accepts.

Deterministic fixtures

The directory reference/fixtures/cubic holds vectors for the canonical cubic circuit. The single committed fixture is transcript_vector.json, a frozen Keccak transcript known-answer vector; every other fixture – keys, proofs, digests, and meta.json – is git-ignored and regenerated on demand, because the keys are large and the proofs are randomized (zero-knowledge). Regenerate them with the commands below before running the tests on a fresh checkout.

The reference implementation checks each deterministic layer against these:

• Proof parsing — test_proof_parse.py parses proof.bin and asserts the cursor consumes every byte, confirming the proof object layout.
• Transcript — test_transcript.py reproduces the recorded challenges byte-for-byte from the committed transcript_vector.json, confirming the transcript primitive and value encodings. The full transcript schedule is exercised end-to-end by the acceptance gates below.
• Verifier-key digest — test_vk_digest.py recomputes \(\mathrm{SHA\text{-}256}(D)\) over the digest stream and matches vk_digest.bin, confirming the verifier-key encoding.

Acceptance gates

Acceptance is checked in both directions.

Rust prover → reference verifier. test_verify.py runs the reference verifier on the Rust-produced proof.bin and asserts acceptance, recovering the expected public values. This exercises the entire acceptance predicate — instance validation, both folds, both sum-checks, relaxed Spartan, the pinned public values, and the final commitment opening — against bytes the reference did not produce.

Reference prover → Rust verifier. The reference prover emits a proof that the shipped Rust verifier accepts. Two #[ignore] harnesses in the Rust test-suite (tests/reference_conformance.rs) deserialize the Python-produced artifacts and call the real verify:

• verify_python_proof — the reference proof against the Rust-exported verifier key; and
• verify_python_standalone — the reference proof against a verifier key that the Python setup.py itself generated, so the shipped Rust library plays no part in setup, proving, or key generation. Only verification is Rust.

Both recover the public value \(15\).

Reproducing the gates

# deterministic vectors (byte-exact)
python3 reference/tests/test_proof_parse.py
python3 reference/tests/test_transcript.py
python3 reference/tests/test_vk_digest.py

# Rust prover -> reference verifier
python3 reference/tests/test_verify.py

# reference prover self-check, and write the stand-alone fixtures
python3 reference/tests/test_prove_finish.py
python3 reference/tests/test_standalone.py

# reference prover -> Rust verifier (both directions of acceptance)
cargo test --test reference_conformance verify_python_proof      -- --ignored --nocapture
cargo test --test reference_conformance verify_python_standalone -- --ignored --nocapture

An independent prover conforms when its proofs pass the same acceptance gate: the shipped Rust verifier, run on the prover’s serialized proof and verifier key, returns success and the expected public values.

Dependencies

The reference implementation is pure Python and runs under a stock python3 interpreter. Its only third-party dependency is pycryptodome, used for Keccak-256 in the transcript; the field, curve, polynomial, encoding, and protocol logic are implemented directly with Python integers. The base field and the T256 curve arithmetic live in curve.py, with the curve constants in params.py, so the arithmetic can be reimplemented against any curve backend without touching the protocol logic.

Primer: multilinear extensions

This appendix gives the background on multilinear extensions used throughout the book. It treats multilinear extensions as a general finite-field tool; Vega-specific uses are described in Multilinear polynomials.

Functions on the Boolean hypercube

Fix a field \(\mathbb{F}\) and an integer \(\ell \ge 0\). A function on the Boolean hypercube is a map \[ f : \{0,1\}^\ell \to \mathbb{F}. \] Its input is a bit-string \(\mathbf{x} = (x_0,\dots,x_{\ell-1})\). The book uses 0-based, least-significant-bit-first indexing: an integer \(i \in \{0,\dots,2^\ell-1\}\) corresponds to the bit-string satisfying \[ i = \sum_{k=0}^{\ell-1} x_k 2^k. \] Thus a length-\(2^\ell\) vector \(\mathbf{v}\) defines a hypercube function by \(f(\mathbf{x}) = v_i\) for this index \(i\).

An extension of \(f\) is a polynomial function \[ \tilde{f} : \mathbb{F}^\ell \to \mathbb{F} \] that agrees with \(f\) at every Boolean input: \[ \tilde{f}(\mathbf{x}) = f(\mathbf{x}) \qquad \text{for all } \mathbf{x} \in \{0,1\}^\ell. \] The extension is multilinear when each variable has degree at most one. Equivalently, after all other variables are fixed, the polynomial is affine in the remaining variable.

Existence and uniqueness

Every hypercube function \(f : \{0,1\}^\ell \to \mathbb{F}\) has a unique multilinear extension. Existence follows from the Lagrange basis on the hypercube. For each Boolean point \(\mathbf{x}\), define the basis polynomial \[ L_{\mathbf{x}}(\mathbf{r}) = \prod_{k=0}^{\ell-1} \bigl(r_k x_k + (1-r_k)(1-x_k)\bigr). \] Then \(L_{\mathbf{x}}\) is multilinear, and for every Boolean \(\mathbf{y} \in \{0,1\}^\ell\), \[ L_{\mathbf{x}}(\mathbf{y}) = \begin{cases} 1 & \text{if } \mathbf{x} = \mathbf{y},\\ 0 & \text{otherwise.} \end{cases} \] The polynomial \[ \tilde{f}(\mathbf{r}) = \sum_{\mathbf{x} \in \{0,1\}^\ell} L_{\mathbf{x}}(\mathbf{r}) f(\mathbf{x}) \] therefore agrees with \(f\) on the hypercube and has degree at most one in each variable.

Uniqueness follows because the vector space of multilinear polynomials in \(\ell\) variables has basis \[ \prod_{k \in S} r_k \qquad \text{for } S \subseteq \{0,\dots,\ell-1\}, \] so its dimension is \(2^\ell\), the same as the number of hypercube evaluations. The Lagrange polynomials above give \(2^\ell\) multilinear polynomials whose evaluation table is the identity matrix. Hence the hypercube evaluations determine exactly one multilinear polynomial.

Evaluation and eq representations

There are two standard representations of the same object.

The evaluation form stores the table \[ \bigl(f(\mathbf{x})\bigr)_{\mathbf{x} \in \{0,1\}^\ell}, \] ordered by the LSB-first integer associated with \(\mathbf{x}\). This is the representation used when a vector is identified with its MLE.

The Lagrange, or eq, form expands the polynomial in the hypercube basis. The equality polynomial is \[ \widetilde{\mathrm{eq}}(\mathbf{r}, \mathbf{x}) = \prod_{k=0}^{\ell-1}\bigl(r_k x_k + (1 - r_k)(1 - x_k)\bigr). \] For Boolean \(\mathbf{x}\), this is the basis polynomial \(L_{\mathbf{x}}(\mathbf{r})\). The MLE evaluation formula is \[ \tilde{f}(\mathbf{r}) = \sum_{\mathbf{x} \in \{0,1\}^\ell} \widetilde{\mathrm{eq}}(\mathbf{r}, \mathbf{x})\; f(\mathbf{x}). \] This formula evaluates the extension at any point \(\mathbf{r} \in \mathbb{F}^\ell\), not only at Boolean points.

Linear-time evaluation from a table

Given the full evaluation table of size \(2^\ell\), the formula above evaluates \(\tilde{f}(\mathbf{r})\) in \(O(2^\ell)\) field operations: compute the \(2^\ell\) eq weights for \(\mathbf{r}\), multiply each by the corresponding table entry, and sum.

The same computation has a useful partial-evaluation view. To fix the first variable to \(r_0\), pair table entries whose indices differ only in bit \(0\). For each remaining Boolean suffix, replace the two values \[ a = f(0, x_1,\dots,x_{\ell-1}), \qquad b = f(1, x_1,\dots,x_{\ell-1}) \] by \[ (1-r_0)a + r_0 b. \] The table size halves. Repeating this for \(r_1,r_2,\dots,r_{\ell-1}\) leaves one field element, equal to \(\tilde{f}(\mathbf{r})\). This “fix one variable” operation is the basic table-halving step exploited by sum-check protocols.

Worked example over \(\mathbb{F}_7\)

Let \(\ell=2\), and work in the field \(\mathbb{F}_7\). With LSB-first indexing, the table \[ \mathbf{v} = (3,5,6,1) \] means \[ f(0,0)=3,\quad f(1,0)=5,\quad f(0,1)=6,\quad f(1,1)=1. \] Evaluate the MLE at \(\mathbf{r}=(2,3)\).

The eq weights are \[ \begin{aligned} \widetilde{\mathrm{eq}}((2,3),(0,0)) &= (1-2)(1-3) = 2,\\ \widetilde{\mathrm{eq}}((2,3),(1,0)) &= 2(1-3) = 3,\\ \widetilde{\mathrm{eq}}((2,3),(0,1)) &= (1-2)3 = 4,\\ \widetilde{\mathrm{eq}}((2,3),(1,1)) &= 2\cdot 3 = 6, \end{aligned} \] where all arithmetic is modulo \(7\). Their sum is \(2+3+4+6=15=1\), as expected for Lagrange weights.

Therefore \[ \tilde{f}(2,3) = 2\cdot 3 + 3\cdot 5 + 4\cdot 6 + 6\cdot 1 = 51 = 2 \pmod 7. \]

The table-halving evaluation gives the same answer. First fix \(x_0=2\): \[ \begin{aligned} g(0) &= (1-2)f(0,0) + 2f(1,0) = (-1)3 + 2\cdot 5 = 0,\\ g(1) &= (1-2)f(0,1) + 2f(1,1) = (-1)6 + 2\cdot 1 = 3. \end{aligned} \] Then fix \(x_1=3\): \[ (1-3)g(0) + 3g(1) = (-2)0 + 3\cdot 3 = 2 \pmod 7. \]

This primer fixes variables low-to-high (\(x_0\) first) for exposition. Vega’s implementation instead restricts the top variable first — high-to-low — as described in Multilinear polynomials; because the multilinear extension is symmetric in the order its variables are fixed, both orders yield the same value.

Why MLEs matter in proof systems

MLEs let protocols treat a vector \(\mathbf{v} \in \mathbb{F}^{2^\ell}\) as a low-degree object \(\tilde{v} : \mathbb{F}^\ell \to \mathbb{F}\). This changes statements about many coordinates into statements about one polynomial evaluated at a verifier-chosen point.

For example, suppose two vectors \(\mathbf{a},\mathbf{b} \in \mathbb{F}^{2^\ell}\) are claimed to be equal. They are equal exactly when their MLEs \(\tilde{a}\) and \(\tilde{b}\) are the same polynomial. If \(\mathbf{a} \ne \mathbf{b}\), then \(\tilde{a}-\tilde{b}\) is a nonzero polynomial of total degree at most \(\ell\). By the Schwartz–Zippel lemma, for uniformly random \(\mathbf{r} \in \mathbb{F}^\ell\), \[ \Pr\bigl[\tilde{a}(\mathbf{r}) = \tilde{b}(\mathbf{r})\bigr] \le \frac{\ell}{|\mathbb{F}|}. \] Thus equality or consistency of long vectors can be checked by comparing MLE evaluations at random points, with soundness error controlled by the field size. Sum-check and polynomial-commitment protocols build on this reduction from vector relations to low-degree polynomial evaluations.

Primer: the sum-check protocol

This appendix gives a self-contained account of the sum-check protocol as a general interactive proof. It is background for Vega’s concrete sum-check building block, not a description of the protocol instances used by the implementation.

The sum being checked

Let \(g(X_1,\dots,X_\ell) \in \mathbb{F}[X_1,\dots,X_\ell]\) be a polynomial whose degree in each variable is bounded. The prover claims that \[ S \;=\; \sum_{\mathbf{x} \in \{0,1\}^\ell} g(\mathbf{x}). \] The verifier wants to check this claim without evaluating \(g\) on all \(2^\ell\) Boolean points. The protocol reduces the exponential-size sum to one evaluation of \(g\) at a random point \((r_1,\dots,r_\ell) \in \mathbb{F}^\ell\).

This setting is common when \(g\) is built from multilinear extensions. The sum-check protocol does not require \(g\) itself to be multilinear; it only needs a known degree bound for each univariate round polynomial.

Round polynomials

The protocol maintains a current claim \(C_{i-1}\). Initially \(C_0 = S\). In round \(i \in \{1,\dots,\ell\}\), the variables \(X_1,\dots,X_{i-1}\) have already been bound to verifier challenges \(r_1,\dots,r_{i-1}\). The prover sends the univariate polynomial \[ g_i(X) \;=\; \sum_{(x_{i+1},\dots,x_\ell) \in \{0,1\}^{\ell-i}} g(r_1,\dots,r_{i-1}, X, x_{i+1},\dots,x_\ell). \] For \(i=\ell\), the sum is over the empty set, so \[ g_\ell(X) \;=\; g(r_1,\dots,r_{\ell-1},X). \] The degree of \(g_i\) is at most the degree of \(g\) in variable \(X_i\), because the other variables are either fixed or summed over Boolean values.

The verifier checks the consistency equation \[ g_i(0) + g_i(1) \;=\; C_{i-1}. \] If it fails, the verifier rejects. If it holds, the verifier samples a fresh random challenge \(r_i \in \mathbb{F}\) and updates the claim to \[ C_i \;=\; g_i(r_i). \] After \(\ell\) rounds, the claim is \(C_\ell\), a claimed value for \[ g(r_1,\dots,r_\ell). \]

Final check

The verifier makes one oracle evaluation of \(g\) at the random point and accepts exactly when \[ g(r_1,\dots,r_\ell) \;=\; C_\ell. \] This final evaluation is the only place where the verifier needs access to \(g\) away from the Boolean hypercube. In deployed proof systems, the verifier often obtains this value through a polynomial commitment opening rather than by holding the whole polynomial.

Completeness and cost

Completeness is immediate from the definition of each round polynomial. If the initial claim \(S\) is correct and the prover sends the honest \(g_i\), then \[ g_i(0) + g_i(1) \] is exactly the previous sum with \(X_i\) left unbound, split into the two cases \(X_i=0\) and \(X_i=1\). The final value \(g_\ell(r_\ell)\) is exactly \(g(r_1,\dots,r_\ell)\).

The prover usually does work proportional to the table of values being summed, while the verifier checks only \(\ell\) low-degree univariate polynomials and one final evaluation. If every round polynomial has degree at most \(d\), the verifier’s round work is \(O(\ell \cdot d)\), plus the cost of the final oracle evaluation or commitment opening.

Soundness intuition

Suppose the claimed sum is false. A cheating prover may send a first polynomial \(h_1\) that passes \[ h_1(0) + h_1(1) = S \] even though \(h_1\) is not the honest round polynomial. Once the verifier sends a random \(r_1\), the next claim becomes \(h_1(r_1)\). For the prover to stay consistent with the true restricted sum, the false polynomial must agree with the honest polynomial at the sampled point.

By the Schwartz–Zippel lemma, two distinct univariate polynomials of degree at most \(d\) agree at a random field point with probability at most \(d/|\mathbb{F}|\). Across \(\ell\) rounds, a union bound gives cheating probability at most \[ \frac{\ell d}{|\mathbb{F}|} \] when every round has degree at most \(d\). More generally, the bound is \((d_1+\cdots+d_\ell)/|\mathbb{F}|\), where \(d_i\) is the degree bound in round \(i\).

A two-round example

Consider the Boolean predicate “exactly one bit is \(1\)” on two variables. Its indicator polynomial over \(\mathbb{F}\) is \[ g(X_1,X_2) \;=\; (1-X_1)X_2 + X_1(1-X_2) \;=\; X_1 + X_2 - 2X_1X_2. \] Over \(\{0,1\}^2\), it is \(1\) on \((1,0)\) and \((0,1)\), and \(0\) on the other two points. The claimed sum is therefore \(S=2\).

In round 1, the prover sends \[ g_1(X) = g(X,0) + g(X,1) = X + (1-X) = 1. \] The verifier checks \[ g_1(0)+g_1(1)=1+1=2=S \] and samples \(r_1\). The updated claim is \(C_1=g_1(r_1)=1\).

In round 2, the prover sends \[ g_2(X) = g(r_1,X) = r_1 + X - 2r_1X = r_1 + (1-2r_1)X. \] The verifier checks \[ g_2(0)+g_2(1)=r_1 + (1-r_1)=1=C_1 \] and samples \(r_2\). The updated claim is \[ C_2 = g_2(r_2)=r_1+r_2-2r_1r_2. \] The final oracle evaluation is \[ g(r_1,r_2)=r_1+r_2-2r_1r_2, \] which equals \(C_2\), so the verifier accepts.

Sending the round polynomial

A round polynomial can be transmitted by coefficients or by enough evaluations to interpolate it. For a degree-\(d\) polynomial, \(d+1\) field elements are sufficient. Implementations may compress the message further: the consistency check \(g_i(0)+g_i(1)=C_{i-1}\) already constrains the polynomial, so one of the \(d+1\) values is redundant and only \(d\) need to be sent.

The interactive verifier’s random challenges can be made non-interactive with Fiat–Shamir: the prover absorbs each round polynomial into the transcript, then derives \(r_i\) by hashing the transcript. Vega’s exact transcript schedule is specified in The transcript schedule.

Vega’s concrete sum-check construction is described in The sum-check protocol. Its use inside folding is described in NeutronNova folding.

Primer: polynomial commitments

This appendix gives a self-contained account of vector and polynomial commitments. It treats commitments as a general finite-field and group tool; concrete uses in this book are described in Polynomial commitments and the ZK opening.

Commitment goals

A vector commitment lets a prover publish a short group element that stands for a vector \(\mathbf{v} \in \mathbb{F}^n\). Later, the prover can open the commitment to a value derived from \(\mathbf{v}\), such as an entry, an inner product, or an evaluation of the multilinear extension \(\tilde{v}\). The verifier checks the opening against the original commitment without receiving the whole vector.

The basic security and algebraic properties are the following.

• Binding. After a commitment is fixed, the prover cannot open it as two different vectors except with negligible probability. For discrete-log commitments, binding follows from the hardness of finding linear relations among independently generated group bases.
• Hiding. The commitment does not reveal the committed vector. A fresh blinding term makes commitments to different vectors indistinguishable to a verifier that does not know the blind.
• Additive homomorphism. Commitments can be added. If \[ C_a = \mathrm{Com}(\mathbf{a};\rho_a), \qquad C_b = \mathrm{Com}(\mathbf{b};\rho_b), \] then \[ C_a + C_b = \mathrm{Com}(\mathbf{a}+\mathbf{b};\rho_a+\rho_b). \] The same identity extends to arbitrary linear combinations.

A polynomial commitment in this setting is a vector commitment applied to the evaluation table of a polynomial. For a length-\(2^\ell\) vector \(\mathbf{v}\), the committed polynomial is the multilinear extension \(\tilde{v} : \mathbb{F}^\ell \to \mathbb{F}\) of that table.

Pedersen vector commitments

Fix public group elements \(G_0, G_1, \dots, G_{n-1}, H \in \mathbb{G}\). A Pedersen commitment to \(\mathbf{v}=(v_0,\dots,v_{n-1})\) with blind \(\rho \in \mathbb{F}\) is \[ \mathrm{Com}(\mathbf{v};\rho) = \sum_{i=0}^{n-1} v_i G_i + \rho H. \] The group \(\mathbb{G}\) is written additively, so the expression is a multi-scalar multiplication plus a blinding generator.

Binding comes from the discrete-log assumption. If a prover can open the same commitment as both \((\mathbf{v},\rho)\) and \((\mathbf{v}‘,\rho’)\), then \[ \sum_i (v_i-v_i’)G_i + (\rho-\rho’)H = 0. \] For distinct openings this gives a nontrivial linear relation among the public bases. The commitment setup chooses the bases so that such a relation is computationally infeasible to find.

Hiding comes from the term \(\rho H\). For a fresh blind, the commitment is shifted by an unknown multiple of \(H\), so the visible group element does not determine the vector. The blind also participates in the homomorphism: \[ \alpha\,\mathrm{Com}(\mathbf{a};\rho_a) + \beta\,\mathrm{Com}(\mathbf{b};\rho_b) = \mathrm{Com}(\alpha\mathbf{a}+\beta\mathbf{b}; \alpha\rho_a+\beta\rho_b). \] This identity is why later protocols can fold many committed vectors into one committed vector.

Matrix view of an MLE opening

Let \(\mathbf{v}\in\mathbb{F}^{2^\ell}\) be the evaluation table of \(\tilde{v}\). Choose integers \(s,c\ge 0\) with \(s+c=\ell\), and reshape the table as a matrix \(Z\in\mathbb{F}^{2^s\times 2^c}\). The row index uses one block of Boolean variables, and the column index uses the remaining block. A point \(\mathbf{r}\in\mathbb{F}^\ell\) splits accordingly as \[ \mathbf{r}=(\mathbf{r}_{\mathrm{row}},\mathbf{r}_{\mathrm{col}}). \]

Let \[ L_i = \widetilde{\mathrm{eq}}(\mathbf{r}_{\mathrm{row}}, i), \qquad R_j = \widetilde{\mathrm{eq}}(\mathbf{r}_{\mathrm{col}}, j) \] be the equality weights for row and column Boolean indices. The MLE evaluation factors as \[ \tilde{v}(\mathbf{r}) = \sum_i\sum_j L_i Z_{i,j} R_j = \left\langle \sum_i L_i Z_{i,*},\; \mathbf{R}\right\rangle. \] Here \(Z_{i,*}\) is row \(i\), and \(\mathbf{R}=(R_j)_j\).

This factorization turns one evaluation opening into two smaller tasks. First, the prover forms the row-combined vector \[ \mathbf{a} = \sum_i L_i Z_{i,*}. \] Second, the claimed evaluation becomes the inner product \[ \tilde{v}(\mathbf{r}) = \langle \mathbf{a}, \mathbf{R}\rangle. \] If the original commitment is row-wise and additively homomorphic, the verifier can form the matching row-combined commitment from the public row commitments. The remaining proof is an inner-product proof for the committed vector \(\mathbf{a}\) against the public vector \(\mathbf{R}\).

A linear inner-product argument

The inner-product statement has the following form. The verifier knows a commitment \(C_a=\mathrm{Com}(\mathbf{a};\rho_a)\), a public vector \(\mathbf{b}\), and a commitment \(C_c=\mathrm{Com}(c;\rho_c)\). The prover claims \[ c = \langle \mathbf{a},\mathbf{b}\rangle. \]

A sigma-protocol proof masks the witness before the verifier’s challenge is known. The prover samples a fresh random vector \(\mathbf{d}\) and fresh blinds. It sends one commitment to \(\mathbf{d}\) and one commitment to \(\langle \mathbf{d},\mathbf{b}\rangle\). The verifier samples a challenge \(r\). The prover answers with the masked linear response \[ \mathbf{z} = r\mathbf{a}+\mathbf{d}, \] plus the corresponding masked blinds. The verifier checks that \(\mathbf{z}\) opens the challenged combination of the vector commitments and that \(\langle \mathbf{z},\mathbf{b}\rangle\) opens the challenged combination of the scalar commitments.

The mask gives zero knowledge: before the challenge, \(\mathbf{d}\) is fresh and hides \(\mathbf{a}\), and the response is distributed as a masked vector. Soundness comes from the same linearity. A prover that can answer two different challenges for the same first messages can be rewound algebraically to recover two incompatible openings unless the committed inner-product relation is true. The proof is linear-size because the response contains a vector of the same length as \(\mathbf{a}\); no logarithmic recursive folding is involved.

This primer supplies the background for the concrete polynomial commitment opening, which combines the matrix factorization above with a linear inner-product argument.

Primer: folding schemes

This appendix gives a self-contained account of folding for relaxed R1CS. Folding is the accumulation step that replaces several constraint instances with one instance, so a verifier can carry a small state and defer the expensive opening or satisfiability proof to the end.

Relaxed R1CS

For matrices \(A,B,C \in \mathbb{F}^{m \times n}\), a strict R1CS instance is satisfied by \(\mathbf{z} \in \mathbb{F}^n\) when \[ (A\mathbf{z}) \circ (B\mathbf{z}) \;=\; C\mathbf{z}. \] A relaxed instance adds a scalar \(u \in \mathbb{F}\) and an error vector \(E \in \mathbb{F}^m\): \[ (A\mathbf{z}) \circ (B\mathbf{z}) \;=\; u\,C\mathbf{z} + E. \] A strict instance is the special case \(u=1\) and \(E=\mathbf{0}\). Relaxation is what makes folding closed: after combining two witnesses linearly, the quadratic terms that appear can be recorded in the new error vector instead of requiring another full R1CS instance.

Folding two instances

Consider two relaxed instances over the same matrices \(A,B,C\). Their satisfying assignments are \[ (A\mathbf{z}_1) \circ (B\mathbf{z}_1) = u_1 C\mathbf{z}_1 + E_1 \] and \[ (A\mathbf{z}_2) \circ (B\mathbf{z}_2) = u_2 C\mathbf{z}_2 + E_2. \] The verifier samples a challenge \(r \in \mathbb{F}\), and the folded assignment uses the linear combinations \[ \mathbf{z} = \mathbf{z}_1 + r\mathbf{z}_2, \qquad u = u_1 + r u_2. \] Expanding the left side gives \[ (A\mathbf{z}) \circ (B\mathbf{z}) = (A\mathbf{z}_1)\circ(B\mathbf{z}_1) + r\bigl((A\mathbf{z}_1)\circ(B\mathbf{z}_2) + (A\mathbf{z}_2)\circ(B\mathbf{z}_1)\bigr) + r^2 (A\mathbf{z}_2)\circ(B\mathbf{z}_2). \] The mixed degree-one part is the cross-term. The prover commits to the corresponding vector as \(\overline{T}\), and the folded error is chosen so the expanded equation has the relaxed form \[ (A\mathbf{z}) \circ (B\mathbf{z}) \;=\; u\,C\mathbf{z} + E. \] For a general relaxed-relaxed fold, \(E\) contains the linear combination of the input errors together with the committed cross-term, with coefficients determined by \(r\). For the common relaxed-with-strict case \((u_2=1, E_2=\mathbf{0})\), this specializes to an error of the form \[ E = E_1 + rT. \]

The commitment \(\overline{T}\) binds the prover to the mixed term before the challenge is used to form the folded instance. If both input instances are satisfied and \(T\) is computed honestly, the folded instance is satisfied. Conversely, if an input equation is false or the cross-term is inconsistent, the folded relaxed equation becomes a nonzero low-degree polynomial in the verifier challenge; it can vanish at a random \(r\) only with small probability.

Folding a batch

A batch of \(k\) uniform instances can be folded by a random linear combination. The verifier derives challenges that determine weights \(\lambda_0, \dots, \lambda_{k-1} \in \mathbb{F}\), and the folded witness and public data are formed coordinate-wise: \[ \mathbf{z}_\star = \sum_{i=0}^{k-1} \lambda_i \mathbf{z}_i, \qquad u_\star = \sum_{i=0}^{k-1} \lambda_i u_i. \] The error vector collects the corresponding linear combination of input errors and the cross-terms introduced by the quadratic constraint. Commitments are folded with the same weights, using the additively homomorphic property of the commitment scheme.

Soundness follows the same principle as the sum-check protocol. If at least one input equation is false, the folded check represents a nonzero polynomial in the verifier’s random choices. Its degree is linear in the number of folded instances, so the Schwartz–Zippel lemma bounds the probability that the false batch survives by \[ O\!\left(\frac{k}{|\mathbb{F}|}\right). \] The bound is small when \(|\mathbb{F}|\) is large and the challenges are sampled after the prover has committed to the data being folded.

Verifier shape

Folding turns many satisfiability claims into one accumulated claim. During the batch, the verifier keeps only the folded public data, folded commitments, and the transcript challenges that define the random linear combination. The verifier does not open every witness commitment immediately. Instead, it checks the folding messages as they arrive and defers the single remaining satisfiability proof or commitment opening to the end.

This is the same economy exploited by sum-check: many local equalities are compressed into one random claim, and the final proof opens only the value needed to finish verification. See the sum-check primer, R1CS, and polynomial commitments for the surrounding building blocks.

Glossary

Terms as they are used in this book.

Absorb / squeeze. absorb(label, value) appends labeled encoded data to the running Fiat–Shamir transcript. squeeze(label) derives the next scalar challenge in \(\mathbb{F}\), updates the transcript state, and resets the running absorb buffer. (see The Fiat–Shamir transcript)

Accept-conforming prover. A prover that emits proofs accepted by verify under the verifier key. (verify returns the public values it recomputes; the application checks them against the intended statement.) It need not reproduce the reference prover’s exact proof bytes. (see Scope and the conformance contract)

Base field. The field in which coordinates of \(\mathbb{G}\) live. In the canonical engine it is distinct from the scalar field used for proof-system arithmetic. (see Fields, groups, and the engine)

Blind. A scalar, or row-indexed tuple of scalars, used with the hiding generator when committing to a vector. Blinds combine linearly when Hyrax commitments are folded or concatenated. (see Polynomial commitments and the ZK opening)

Byte-conforming prover. A prover that, given the same verifier key, public values, witness, and random tape, reproduces the reference prover’s exact serialized proof bytes. This requires exact agreement on the transcript schedule, encodings, proof-object fields, and randomness consumption. (see Scope and the conformance contract)

Canonical engine. The concrete engine fixed by the specification: T256 as \(\mathbb{G}\), its scalar field as \(\mathbb{F}\), a Keccak256-based Fiat–Shamir transcript, and Hyrax polynomial commitments. Other engines are outside the byte-exact specification. (see Scope and the conformance contract)

Challenge. A scalar in \(\mathbb{F}\) derived by squeeze from the transcript. Challenges such as \(\tau\), \(\rho\), \(r\), \(r_b\), \(r_x\), and \(r_y\) are owned by specific folding or sum-check layers.

Commitment key. The public Hyrax generator material used to commit to vectors: a row width, vector bases, and a hiding generator. Setup creates the keys used for step/core witnesses and for the verifier-circuit witness. (see Polynomial commitments and the ZK opening)

Core circuit. The circuit instance \(C_2\) that joins the step batch in \(\mathrm{Vega}_{\mathrm{MC}}\). The core branch shares the same committed witness prefix where configured and is proved alongside the folded step branch.

Eq polynomial. The equality polynomial \(\widetilde{\mathrm{eq}}(\mathbf{r},\mathbf{x})\), the MLE of the equality indicator on the Boolean hypercube. Vega uses it for MLE evaluation weights, folding checks such as eq_rho_at_rb, and some row-batching computations. (see Multilinear polynomials)

Fiat–Shamir transcript. The Keccak-based state machine that turns protocol messages into deterministic verifier challenges. The mechanism defines new, absorb, squeeze, and dom_sep; the MC protocol’s exact operation order is fixed separately by the transcript schedule. (see The Fiat–Shamir transcript)

Folding / NIFS. A non-interactive folding step that replaces two or more instances by one linearly combined instance under transcript-derived challenges. In this book, NeutronNova folding accumulates step instances, while Nova NIFS folds a random relaxed instance with the real verifier-circuit instance.

Group \(\mathbb{G}\). The prime-order elliptic-curve group used additively for commitments. Scalars from \(\mathbb{F}\) multiply group generators in Hyrax commitments and multi-scalar multiplications. (see Fields, groups, and the engine)

Hiding generator. The dedicated Hyrax commitment-key generator \(H\) (or \(h\)) multiplied by the blind in each row commitment. It supplies the Pedersen hiding term independent of the vector bases. (see Polynomial commitments and the ZK opening)

Hyrax commitment. Vega’s row-wise Pedersen-style vector commitment over \(\mathbb{G}\). A vector is reshaped into fixed-width rows, each row is committed with the same generator vector and a fresh blind, and the resulting commitment is the vector of row commitments. (see Polynomial commitments and the ZK opening)

In-circuit verifier. The multi-round R1CS circuit that checks Vega’s verifier algebra inside the proof. Its public values are later recomputed natively by the outer verifier and compared against the circuit’s outputs. (see The in-circuit verifier)

Multilinear extension (MLE). The unique multilinear polynomial \(\widetilde{f}:\mathbb{F}^\ell\to\mathbb{F}\) that agrees with a table \(f:{0,1}^\ell\to\mathbb{F}\) on the Boolean hypercube. Vega represents MLEs by dense evaluation tables with LSB-first indexing and binds variables high-to-low in sum-check. (see Multilinear polynomials)

NeutronNova folding. The first fold in \(\mathrm{Vega}_{\mathrm{MC}}\), which accumulates many strict step R1CS instances into one folded step instance. It uses \(\tau\) to compress constraint residuals and \(\rho\) / \(r_b\) challenges to fold the padded step batch. (see NeutronNova folding)

Nova folding. The zero-knowledge fold that combines a fresh random satisfying relaxed instance with the real verifier-circuit instance. The resulting masked relaxed instance is the one proved by relaxed Spartan. (see Nova folding for zero-knowledge)

num_steps. The number of step instances fixed at setup and stored in the verifier key. It must be at least two for \(\mathrm{Vega}_{\mathrm{MC}}\), and its raw value is digested into the verifier key even though folding may pad it to a power of two. (see Setup)

Polynomial commitment scheme (PCS). The commitment and opening machinery used for witness vectors viewed as multilinear-polynomial tables. In the canonical engine, this is Hyrax with a zero-knowledge evaluation opening for the final committed-witness evaluation. (see Polynomial commitments and the ZK opening)

Powers polynomial. The MLE whose Boolean evaluations are \(1,\tau,\tau^2,\dots\) under the book’s LSB-first hypercube indexing. \(\mathrm{Vega}_{\mathrm{MC}}\) uses it as the Spartan row weight derived from \(\tau\). (see The Spartan argument)

Precommitted witness segment. The split-R1CS witness segment synthesized and committed during preparation, before challenge-dependent rest variables are available. Its commitment is optional exactly when the segment is empty. (see R1CS)

Public values. The public scalar vector carried by an R1CS instance or exposed by the verifier circuit. In the MC verifier circuit these include tau_at_rx, eval_X_step, eval_X_core, eq_rho_at_rb, quotient_step, and quotient_core.

R1CS. A rank-1 constraint system over \(\mathbb{F}\) with matrices \(A,B,C\) and satisfaction equation \((A\mathbf{z})\circ(B\mathbf{z})=C\mathbf{z}\). Vega’s standard assignment layout is \(\mathbf{z}=(\mathbf{w},1,\mathbf{x})\). (see R1CS)

Relaxed R1CS. The R1CS variant with equation \((A\mathbf{z})\circ(B\mathbf{z})=u,C\mathbf{z}+\mathbf{E}\). The scalar \(u\) and error vector \(\mathbf{E}\) make the relation closed under folding. (see R1CS)

Relaxed Spartan. The Spartan argument Vega uses for a single folded relaxed R1CS instance. In the MC proof it runs after Nova folding and uses direct openings on the masked folded witness and error. (see Relaxed Spartan)

Rest witness segment. The split-R1CS witness segment committed after transcript-derived challenges are available. It contains variables that depend on those challenges and is always represented by a rest commitment, including padding. (see R1CS)

Round polynomial. The univariate polynomial sent in one sum-check round. Vega stores it compressed by omitting the linear coefficient, which the verifier reconstructs from the current claim. (see The sum-check protocol)

Scalar field \(\mathbb{F}\). The field used for witnesses, constraints, MLEs, sum-check messages, blinds, and Fiat–Shamir challenges. In the canonical engine it is the scalar field of T256. (see Fields, groups, and the engine)

Shared witness segment. The split-R1CS witness segment synthesized and committed once, then reused across step instances and the core instance. The proof object may hoist this shared commitment to the top level and set per-instance shared commitments to None. (see R1CS)

Spartan. The R1CS argument that reduces satisfaction to an outer zero-check over rows, an inner matrix-evaluation sum-check over columns, and a final committed-witness opening. \(\mathrm{Vega}_{\mathrm{MC}}\) runs Spartan jointly on the folded step branch and the core branch. (see The Spartan argument)

Split R1CS shape. An R1CS shape whose witness columns are partitioned into shared, precommitted, and rest segments, with public values and transcript-derived challenges tracked separately. It lets Vega commit to witness pieces at the time they become determined while converting back to the ordinary R1CS interface. (see R1CS)

Step circuit. The repeated circuit \(C_1\) in the MC statement. Setup fixes num_steps copies, and NeutronNova folding accumulates those step instances into one folded step branch.

Sum-check protocol. The protocol that checks a hypercube-sum claim through a sequence of low-degree univariate round polynomials and transcript challenges. Vega uses specialized quadratic, cubic, and batched zero-knowledge prover shapes. (see The sum-check protocol)

T256 curve. The canonical elliptic curve used as \(\mathbb{G}\). Its scalar field is \(\mathbb{F}\), and its base field supplies group-coordinate encodings. (see Fields, groups, and the engine)

Verifier key. The public setup object consumed by verify, containing commitment material, step/core shapes, verifier-circuit shapes and keys, and num_steps. It is not serialized into the proof. (see Verifier key)

Verifier-key digest. The 32-byte SHA-256 digest of the verifier-key fields in their specified order and encodings. It is absorbed into the transcript as vk, binding every later challenge to the setup material. (see Verifier key)

\(\mathrm{Vega}_{\mathrm{MC}}\) vs \(\mathrm{Vega}_{\mathrm{SC}}\). \(\mathrm{Vega}_{\mathrm{MC}}\) is the multi-circuit prover described by this book: it folds many step circuits and one core circuit. \(\mathrm{Vega}_{\mathrm{SC}}\) is the single-circuit prover that the MC construction builds on; unqualified “the prover” means \(\mathrm{Vega}_{\mathrm{MC}}\). (see Notation and conventions)

Witness. The private assignment data committed by the prover. In standard R1CS it appears as \(\mathbf{w}\) in \(\mathbf{z}=(\mathbf{w},1,\mathbf{x})\); in split R1CS it is divided into shared, precommitted, and rest segments.

Zero-knowledge opening (inner-product argument / IPA). The Hyrax evaluation opening used for the final committed-witness evaluation. It proves an inner-product relation with fresh masks and blinds, sending delta, beta, z_vec, z_delta, and z_beta while hiding the row-combined witness vector. (see Polynomial commitments and the ZK opening)

Bibliography

The proof system documented here builds on a line of work on transparent zkSNARKs and folding schemes. These are its primary references; each entry notes where the construction appears in the book.

Vega. Darya Kaviani and Srinath Setty. Vega: Low-Latency Zero-Knowledge Proofs over Existing Credentials. Cryptology ePrint Archive, Paper 2025/2094. https://eprint.iacr.org/2025/2094

The system this book specifies; \(\mathrm{Vega}_{\mathrm{MC}}\) is its multi-circuit prover.

Spartan. Srinath Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. CRYPTO 2020. Cryptology ePrint Archive, Paper 2019/550. https://eprint.iacr.org/2019/550

The R1CS argument that reduces constraint satisfaction to an outer and inner sum-check and a committed-witness opening. See The Spartan argument.

Nova. Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla. Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. CRYPTO 2022. Cryptology ePrint Archive, Paper 2021/370. https://eprint.iacr.org/2021/370

The folding scheme whose blinding property underlies the zero-knowledge fold of the verifier-circuit instance. See Nova folding for zero-knowledge.

HyperNova. Abhiram Kothapalli and Srinath Setty. HyperNova: Recursive arguments for customizable constraint systems. CRYPTO 2024. Cryptology ePrint Archive, Paper 2023/573. https://eprint.iacr.org/2023/573

Recursive arguments for customizable constraint systems, and the sum-check-based folding lineage this system draws on.

NeutronNova. Abhiram Kothapalli and Srinath Setty. NeutronNova: Folding everything that reduces to zero-check. Cryptology ePrint Archive, Paper 2024/1606. https://eprint.iacr.org/2024/1606

The zero-check folding scheme that accumulates the many step instances into one. See NeutronNova folding.