# Symphony: Scalable SNARKs in the Random Oracle Model from Lattice-Based High-Arity Folding
[TOC]
---
## Executive Summary
Symphony represents a fundamental reconceptualization of folding-based SNARK construction, introducing the first lattice-based system that successfully avoids embedding cryptographic hash functions within circuit verification. Authored by Binyi Chen from Stanford University (October 2025), this work addresses critical efficiency and security bottlenecks that have plagued previous folding-based approaches since the Halo framework's introduction in 2019.
The core innovation rests on three pillars: a novel high-arity lattice-based folding scheme capable of compressing up to 1024 or more NP-complete statements in a single shot, a generic commit-and-prove compiler that entirely eliminates Fiat-Shamir circuit embedding, and practical instantiation demonstrating sub-200KB proofs with tens-of-milliseconds verification time. The system achieves polylogarithmic proof size and verification complexity while maintaining plausible post-quantum security through lattice-based hardness assumptions.
:::info
**Key Achievement**: Symphony achieves the first folding-based SNARK construction where the embedding of random oracles does not appear within proven statements, fundamentally addressing the gap between theory (random oracle model) and practice (concrete hash instantiation).
:::
---
## Technical Motivation and Problem Setting
### The Folding Landscape: Historical Context and Current Limitations
:::spoiler
**Prior Approaches**: Folding schemes emerged as an elegant alternative to recursive SNARKs, which embed full verifier logic into circuit constraints. The Halo framework (BGH19) introduced accumulation as a public-coin protocol reducing multiple uniform statements to a single accumulated statement via random linear combinations. This framework has been refined through numerous iterations including Nova (BCMS20), Protostar (BC23), LatticeFold+ (BC25), and hash-based schemes (BMNW25a, BMNW25b).
The fundamental limitation of existing approaches involves the instantiation of random oracles required for the Fiat-Shamir transform. When embedding hash functions directly into circuit constraints, the system faces a troubling trilemma: (1) efficiency overhead from hash gadget constraints (standard hashes require thousands of R1CS constraints; even specialized hash functions demand hundreds), (2) security degradation from heuristic instantiation of random oracles within proven statements, and (3) vulnerability to recent attacks (KRS25) on systems like GKR-based SNARKs when random oracle instantiation occurs inside verified statements.
:::
Existing folding schemes typically operate with low arity (two-to-one or three-to-one folding), requiring deep folding trees to batch multiple statements. This architectural constraint creates multiple compounding problems: reduced parallelism, degraded security guarantees for super-logarithmic folding depths, and forced embeddings of expensive folding verification circuits into SNARK relations.
### The Symphony Solution: Conceptual Framework
Symphony reconceptualizes the folding-to-SNARK pipeline by fundamentally separating concerns. Rather than embedding verification logic for folding directly into circuit constraints, the system moves to a three-stage process: (1) execute high-arity lattice-based folding producing a folding proof and reduced instance, (2) generate a separate proof of the reduced statement using standard SNARK techniques, and (3) leverage commit-and-prove SNARKs to compress the large folding proofs without instantiating random oracles within circuit verification.
The key insight enabling this architecture involves observing that commit-and-prove SNARKs need not encode the commitment-opening relation within their statement definition. This property allows Symphony to prove the correctness of folding through CP-SNARK mechanisms that establish commitment validity through external verification, rather than circuit constraints.
:::warning
**Critical Distinction**: The folding proof in Symphony's architecture does not embed the Fiat-Shamir challenge derivation as circuit constraints. Instead, challenge derivation occurs external to the proven statement, and the CP-SNARK proves only that provided commitments open correctly to messages satisfying the folding verification logic.
:::
---
## Core Technical Architecture
### Section 1: Lattice-Based High-Arity Folding Scheme
#### Algebraic Foundations
Symphony operates over power-of-two cyclotomic rings $R := \mathbb{Z}[X]/\langle X^d + 1 \rangle$ where $d = 2^k$ for some integer $k$. The residual ring is defined as $R_q := \mathbb{Z}_q[X]/\langle X^d + 1 \rangle$ for prime modulus $q$. For concreteness in the instantiation, the paper uses $d = 64$ and operates over the ring $R_q = \mathbb{Z}_q[X]/\langle X^{64} + 1 \rangle$.
The norm structure for vectors and matrices follows standard $\ell_2$ and $\ell_\infty$ definitions applied to coefficient vectors. For ring element $f = \sum_{i \in [d]} f_i X^{i-1} \in R_q$, the coefficient vector representation is $\text{cf}(f) := (f_1, \ldots, f_d) \in \mathbb{Z}_q^d$. This lifting between ring elements and integer vectors enables efficient norm analysis and commitment verification.
The operator norm of ring element $a \in R$ is defined as:
$$\|a\|_{\text{op}} := \sup_{y \in R} \frac{\|a \cdot y\|_2}{\|y\|_2}$$
This operator norm proves critical for bounding the norms of folded witnesses after combining multiple input statements through low-norm challenge vectors.
#### Ajtai Commitments and Binding Properties
Symphony employs lattice-based binding commitments instantiated through the Module-SIS assumption. The commitment construction (Construction 2.1) defines commitment space $C := R_q^\kappa$ where $\kappa = \kappa(\lambda)$ is the security parameter-dependent commitment dimension.
For a commitment parameter $A \in R_q^{\kappa \times n}$ sampled uniformly at setup, committing to message $m \in M^*$ produces commitment $c := A \cdot m \in C$. The opening space permits relaxed openings through a pair $(f, s)$ satisfying $s \cdot m = f$ and $A \cdot f = s \cdot c$, where $f$ has bounded norm and $s \in (S - S)$ for some challenge set $S$. This relaxed opening structure proves essential for analyzing the knowledge soundness of the folding scheme.
The binding property is guaranteed under the Module-SIS assumption with parameters chosen such that:
$$B_{\text{rbnd}} = 2B_{\text{bnd}} = \frac{\beta_{\text{SIS}}}{2T}$$
where $T$ denotes the operator norm of the challenge set $S$ and $\beta_{\text{SIS}}$ parameterizes the Module-SIS hardness.
#### Three-Step Folding Framework
The high-arity folding scheme operates through three sequential phases for compressing $\ell_{np}$ R1CS statements into one:
**Phase 1: Commitment of Witnesses**. The prover commits to the witnesses of all $\ell_{np}$ input R1CS statements using the Ajtai commitment scheme. This produces commitments $c_\ell$ for each input statement $\ell \in [\ell_{np}]$.
**Phase 2: Sumcheck Reduction**. The system applies standard sumcheck techniques to transform each input R1CS statement (encoded as a Hadamard product constraint) into a sumcheck claim. The prover and verifier execute a sumcheck protocol reducing the initial claim to $\ell_{np}$ linear evaluation statements, one per input instance.
**Phase 3: Random Linear Combination**. The verifier samples a low-norm challenge vector $\beta \in S^{\ell_{np}}$ where $S$ is a set of ring elements with bounded operator norm (typically $S = \{a \in R_q : \|a\|_{\text{op}} \leq 15\}$). Using this vector, the system combines all input commitments and witnesses: $c^* := \sum_{\ell=1}^{\ell_{np}} \beta^\ell \cdot c_\ell$ and $f^* := \sum_{\ell=1}^{\ell_{np}} \beta^\ell \cdot f_\ell$. By linearity of both the evaluation statements and Ajtai commitments, the combined statement maintains the same structure as individual input statements.
The primary technical challenge involves proving the low-norm property of opened messages, which is essential for both the binding property of Ajtai commitments and the knowledge soundness guarantee of the folding scheme.
#### Approximate Range Proofs: Integration of Projection and Monomial Embedding
Symphony combines two complementary techniques to achieve near-optimal complexity for range proofs on projected vectors:
**Random Projection Component**: Following LaBRADOR (BS23) and refinements by Klooß et al. (KLNO25), the scheme uses structured random projection matrices of the form:
$$J := I_{n/\ell_h} \otimes J' \in \mathbb{Z}_{q}^{\lambda_{pj} \times n}$$
where $J' \in \{0, \pm 1\}^{\lambda_{pj} \times \ell_h}$ is a narrower random matrix and $\lambda_{pj} = 256$ is a fixed parameter. This structured projection reduces prover complexity while enabling sublinear verifier computation through factored matrix representation.
The random projection preserves $\ell_2$-norm information according to Lemma 2.2: for a distribution $\chi$ over $\{0, \pm 1\}$ with $\text{Pr}[\chi = 0] = 1/2$ and $\text{Pr}[\chi = \pm 1] = 1/4$, and for vector $v$ with $\|v\|_2 > B$:
$$\text{Pr}_{J \leftarrow \chi^{256 \times n}}\left[\|Jv \bmod q\|_2 \leq \sqrt{30}B\right] \lesssim 2^{-128}$$
This bound ensures that norm violations are detected with overwhelming probability after projection.
**Monomial Embedding Refinement**: Symphony streamlines the monomial embedding approach from LatticeFold+ (BC25). The technique encodes bounded integers onto monomials in the cyclotomic ring using the table polynomial:
$$t(X) := \sum_{i \in [1, d/2)} i \cdot (X^i + X^{-i}) = \sum_{i \in [1, d/2)} i \cdot (X^i - X^{d-i}) \in R_q$$
For integer $a \in (-d/2, d/2)$, the encoding $\text{Exp}(a) \in M := \{0, 1, X, \ldots, X^{d-1}\}$ satisfies:
$$\text{ct}(\text{Exp}(a) \cdot t(X)) = a$$
where $\text{ct}(\cdot)$ extracts the constant term. This creates a range proof where the prover sends monomial vectors $g^{(i)} \in M^n$ and proves that $g^{(i)} \cdot t(X)$ has constant term equal to the claimed value. The key optimization in Symphony involves eliminating the commitment transformation overhead from LatticeFold+, reducing required monomial commitments from $d$ to $O(1)$ by operating on the smaller projected vector directly.
The combined scheme (protocol $\Pi_{rg}$ in Figure 2 of the paper) reduces checking the norm of a projected vector $w' = Jw \bmod q \in R_q^{n/\ell_h}$ to proving approximate range through this integrated protocol, achieving prover complexity of $O(n)$ Ajtai commitment operations plus $O(1)$ monomial commitments.
### Section 2: Commit-and-Prove Compiler: From Folding to SNARKs
#### Warm-Up: Naive Folding-to-SNARK Pipeline
To establish motivation, consider a straightforward approach: apply Fiat-Shamir to folding protocol $\Pi_{\text{fold}}$ to obtain non-interactive scheme $\text{FS}[\Pi_{\text{fold}}]$, then prove the reduced relation using a standard SNARK. While simple, this approach scales poorly: for $\ell_{np} = 1000$, the folding proof $\pi$ easily exceeds 30MB with lattice or hash-based schemes, and embedding the folding verifier into the SNARK relation requires implementing millions of hash constraints for large $\ell_{np}$.
#### CP-SNARK Framework and the Core Compiler Innovation
The breakthrough enabling Symphony involves commit-and-prove SNARKs, a special class of SNARKs where the proven statement separates the commitment-opening relation from the core computational claim. Formally, a CP-SNARK for commitment scheme $\text{CM}$ and relation generator $\text{GenR}$ proves knowledge of witness $w' = ((w_i, o_i)_{i=1}^\ell, w^*)$ such that:
1. For each $i \in [\ell]$: $(w_i, o_i)$ is a valid opening to commitment $c_i$ under scheme $\text{CM}$
2. The core relation check holds: $(x, w = (w_1, \ldots, w_\ell, w^*)) \in R$
Crucially, the CP-SNARK statement does not explicitly encode commitment verification. Instead, this verification occurs outside the circuit, in the verifier's logic.
Symphony's compiler transforms folding protocol $\Pi_{\text{fold}}$ into a CP-SNARK-based SNARK through the following stages:
**Stage 1: Commit-and-Open Transformation**. Convert the interactive folding protocol into variant $\text{CM}[\Pi_{cm}, \Pi_{\text{fold}}]$ where each prover message $m_i$ in the folding protocol becomes a commitment $c_{fs,i} := \Pi_{cm}.\text{Commit}(m_i)$. At protocol completion, the prover sends openings $(m_i)$ and the verifier checks that provided messages open correctly to commitments while simulating the original folding verifier.
**Stage 2: Fiat-Shamir Application**. Apply the Fiat-Shamir transform using hash function $H$ modeled as random oracle to obtain non-interactive scheme $\text{FS}[\Pi_{cm}, \Pi_{\text{fold}}]$. Challenges are derived as $r_i := H(\text{transcript}_i)$ where the transcript includes prior commitments and the instance.
**Stage 3: CP-SNARK Instantiation**. Convert the non-interactive scheme into the final SNARK:
- The prover computes commitments $\{c_{fs,i}\}$, the folding-reduced instance $x_o$, and a SNARK proof $\pi_{\text{snark}}$ for the reduced relation.
- Let $\pi_{cp}$ be a CP-SNARK proof of knowledge for messages $\{m_i\}$ proving that $[(c_{fs,i})_i, (m_i)_i]$ constitute a valid folding proof for $x$ and $x_o$.
- The prover outputs $\{c_{fs,i}\}, x_o, \pi_{\text{snark}}, \pi_{cp}$.
- The verifier checks $\pi_{\text{snark}}$ against $x_o$, derives folding challenges $\{r_i\}$ from the Fiat-Shamir transcript, and checks $\pi_{cp}$ against $(x, x_o, \{c_{fs,i}, r_i\})$.
**Critical Property**: The CP-SNARK statement embeds no Fiat-Shamir circuits instantiating random oracles. Instead, it only proves $O(\ell_{np})$ multiplications over $R_q$ for combining Ajtai commitments. For commitment scheme $\Pi_{cm}$, the system can employ Merkle commitments (hash-based) or KZG commitments (pairing-based) to compress large folding proofs. Compared to naive folding, this compresses >30MB folding proofs into log-size Merkle or KZG commitments, typically under 1KB for realistic statement sizes.
#### Security Analysis and Knowledge Extraction
The knowledge soundness argument employs coordinate-wise special soundness (Lemma 2.3) to extract witnesses from adversarial provers. For folding challenge space $U := S^{\ell_{np}}$ and a predicate $\Psi$ checking transcript validity and statement satisfaction, an oracle extractor can extract $\ell_{np} + 1$ valid transcripts by rewinding the adversary on varying challenge coordinates, failing with probability at most $\ell_{np}/|S|$.
Given such extracted transcripts, the extractor recovers the original witness through linear algebra: if two transcripts yield outputs $(f^*_\ell, f^*_0)$ under folding challenges $(u^\ell, u^0)$, then:
$$f_\ell := \frac{f^*_\ell - f^*_0}{u^\ell[\ell] - u^0[\ell]} \in R_q^n$$
Here, the denominator $u^\ell[\ell] - u^0[\ell] \in S - S$ is invertible over $R_q$ by assumption, making the extraction well-defined. This linear extraction preserves all necessary properties: if folded outputs satisfy the reduced relation, then extracted individual witnesses satisfy the original relation (with relaxed norm bounds).
---
## Instantiation and Concrete Parameters
### Instance Parameters and Practical Constraints
The paper instantiates Symphony over the cyclotomic ring $R_q := \mathbb{Z}_q[X]/\langle X^{64} + 1 \rangle$ where $q$ is chosen as a prime approximately $2^{30}$ for 64-bit arithmetic efficiency. This ring parameterization accommodates $2^{10}$ foldings over $R_q$, equivalent to $2^{16}$ R1CS statements over $\mathbb{Z}_q$.
For R1CS constraints, the system supports statements with up to $2^{16}$ constraints each. With high-arity folding of $2^{10}$ instances, Symphony handles total statement sizes exceeding $2^{26}$ R1CS constraints (over 64 million constraints) in a single folding operation, sufficient for zkVM applications processing tens of millions of instructions.
### Efficiency Projections
The concrete efficiency analysis demonstrates:
**Proof Size**: The system generates proofs under 200KB for the above parameter configuration and under 50KB without post-quantum security requirements. This represents a significant improvement over prior lattice-based SNARKs, primarily through the elimination of embedded hash constraints.
**Verification Time**: Verifier runtime is projected at tens of milliseconds, dominated by commitment verification (KZG or Merkle) rather than circuit evaluation.
**Prover Runtime**: The dominant operation is computing witness commitments, requiring approximately $3 \cdot 2^{32}$ multiplications between arbitrary ring elements and low-norm elements. Assuming standard modern computation rates, this translates to seconds or low tens-of-seconds runtime. Further acceleration is achievable: if witnesses naturally have 8-bit signed integers (common in many applications), an additional 8x speedup becomes realistic through use of optimized low-norm arithmetic.
:::info
**Memory Efficiency**: As noted in Remark 4.1, the prover supports streaming computation with memory consumption comparable to running a single $\Pi_{gr1cs}$ instance. The streaming-friendly architecture enables the prover to begin work as soon as some proven statements become available, rather than requiring all witnesses upfront.
:::
---
## Comparison with Prior Work
| Characteristic | Halo (BGH19) | LatticeFold+ (BC25) | Symphony | Hash-based Schemes (BMNW25) |
|---|---|---|---|---|
| **Folding Arity** | 2 | 2-3 | 1000+ | 2-3 |
| **Random Oracle Embedding** | In circuit | In circuit | External | In circuit |
| **Post-Quantum** | No | Yes | Yes | Yes |
| **Proof Size** | Medium | Medium | <200KB | Large |
| **Verification Time** | Fast | Medium | ~10ms | Medium |
| **Prover Memory** | Standard | Standard | Streaming | Standard |
| **Hash Constraints** | Thousands | Hundreds | Zero in CP-SNARK | Millions |
The table highlights Symphony's unique positioning. While hash-based folding schemes achieve asymptotically fast provers, they incur massive verifier circuit complexity through Merkle opening verification. LatticeFold+ reduced this burden but still embedded Fiat-Shamir hashing. Symphony's high-arity approach with external oracle instantiation achieves the benefits of both low verifier circuit complexity and freedom from embedded random oracle instantiation.
---
## Practical Implementation: Rust Component Prototypes
### Prototype 1: Cyclotomic Ring Arithmetic
```rust
use num_bigint::BigInt;
use num_traits::{Zero, One};
use std::ops::{Add, Mul, Sub};
/// Represents an element in R_q = Z_q[X] / <X^d + 1>
/// where d must be a power of 2 (e.g., 64)
#[derive(Clone, Debug)]
pub struct CyclotomicElement {
coefficients: Vec<u64>,
modulus: u64,
dimension: usize,
}
impl CyclotomicElement {
/// Create a new cyclotomic element with zero coefficients
pub fn new(dimension: usize, modulus: u64) -> Self {
assert!(dimension.is_power_of_two(), "dimension must be power of 2");
CyclotomicElement {
coefficients: vec![0; dimension],
modulus,
dimension,
}
}
/// Return the coefficient vector (canonical lift to Z_q^d)
pub fn coefficient_vector(&self) -> &[u64] {
&self.coefficients
}
/// Compute l2 norm of coefficient vector
pub fn l2_norm_squared(&self) -> u128 {
self.coefficients
.iter()
.map(|c| (*c as u128) * (*c as u128))
.sum()
}
/// Compute l-infinity norm
pub fn linf_norm(&self) -> u64 {
*self.coefficients.iter().max().unwrap_or(&0)
}
/// Check if element satisfies approximate norm bound
/// Used in range proof verification
pub fn satisfies_norm_bound(&self, bound: u64) -> bool {
self.l2_norm_squared() <= (bound as u128 * bound as u128)
}
/// Multiply two cyclotomic elements
/// Uses the relation X^d = -1 to reduce products
pub fn multiply(&self, other: &CyclotomicElement) -> CyclotomicElement {
assert_eq!(self.modulus, other.modulus);
assert_eq!(self.dimension, other.dimension);
let mut result = vec![0u128; 2 * self.dimension];
// Standard polynomial multiplication
for i in 0..self.dimension {
for j in 0..self.dimension {
result[i + j] += (self.coefficients[i] as u128) * (other.coefficients[j] as u128);
}
}
// Reduce using X^d = -1
for i in self.dimension..2 * self.dimension {
let idx = i - self.dimension;
// Coefficient of X^i becomes -coefficient of X^(i-d)
if result[idx] >= result[i] {
result[idx] = (result[idx] - result[i]) % (self.modulus as u128);
} else {
result[idx] = ((self.modulus as u128) - (result[i] - result[idx]) % (self.modulus as u128))
% (self.modulus as u128);
}
}
let mut coeffs = vec![0u64; self.dimension];
for i in 0..self.dimension {
coeffs[i] = (result[i] % (self.modulus as u128)) as u64;
}
CyclotomicElement {
coefficients: coeffs,
modulus: self.modulus,
dimension: self.dimension,
}
}
/// Linear combination with low-norm scalar for folding
/// Used in Phase 3 of folding scheme
pub fn scalar_mult(&self, scalar: &CyclotomicElement) -> CyclotomicElement {
self.multiply(scalar)
}
}
impl Add for CyclotomicElement {
type Output = CyclotomicElement;
fn add(self, other: CyclotomicElement) -> CyclotomicElement {
assert_eq!(self.modulus, other.modulus);
assert_eq!(self.dimension, other.dimension);
let mut result = vec![0u64; self.dimension];
for i in 0..self.dimension {
result[i] = (self.coefficients[i] + other.coefficients[i]) % self.modulus;
}
CyclotomicElement {
coefficients: result,
modulus: self.modulus,
dimension: self.dimension,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_cyclotomic_arithmetic() {
let q = 1000000007u64;
let d = 64usize;
let mut a = CyclotomicElement::new(d, q);
a.coefficients[0] = 5;
a.coefficients[1] = 10;
let mut b = CyclotomicElement::new(d, q);
b.coefficients[0] = 3;
b.coefficients[2] = 7;
let c = a.multiply(&b);
assert_eq!(c.coefficients[0], (5 * 3) % q);
assert_eq!(c.coefficients[3], (5 * 7) % q);
}
#[test]
fn test_norm_computation() {
let q = 1000000007u64;
let d = 64usize;
let mut a = CyclotomicElement::new(d, q);
a.coefficients[0] = 3;
a.coefficients[1] = 4;
assert_eq!(a.l2_norm_squared(), 25);
assert_eq!(a.linf_norm(), 4);
}
}
```
### Prototype 2: Ajtai Commitment Implementation
```rust
use sha3::Sha3_256;
use digest::Digest;
/// Module-SIS based binding commitment over R_q
/// Parameter A ∈ R_q^{κ × n} is the commitment parameter
#[derive(Clone)]
pub struct AjtaiCommitment {
// Parameter matrix A ∈ R_q^{κ × n}
parameter_a: Vec<Vec<CyclotomicElement>>,
// Dimension parameters
kappa: usize,
n: usize,
// Module-SIS hardness parameter
beta_sis: u64,
// Bound on openings: B_rbnd = beta_sis / (2 * T)
// where T is operator norm of challenge set S
opening_bound: u64,
}
impl AjtaiCommitment {
/// Initialize commitment scheme with random parameter generation
pub fn new(modulus: u64, ring_dim: usize, kappa: usize, n: usize, beta_sis: u64) -> Self {
// In practice: parameter_a would be uniformly sampled from R_q^{κ × n}
// For prototype, we use seeded randomness
let mut hasher = Sha3_256::new();
hasher.update(b"ajtai_param");
let seed = hasher.finalize();
let mut parameter_a = Vec::with_capacity(kappa);
for i in 0..kappa {
let mut row = Vec::with_capacity(n);
for j in 0..n {
let mut element = CyclotomicElement::new(ring_dim, modulus);
// Pseudo-random element derived from seed
let mut hasher = Sha3_256::new();
hasher.update(&seed);
hasher.update(i.to_le_bytes());
hasher.update(j.to_le_bytes());
let hash = hasher.finalize();
for (k, byte) in hash.iter().enumerate().take(ring_dim) {
element.coefficients[k] = (*byte as u64) % modulus;
}
row.push(element);
}
parameter_a.push(row);
}
let operator_norm_bound = 15u64; // For practical challenge sets
let opening_bound = beta_sis / (2 * operator_norm_bound);
AjtaiCommitment {
parameter_a,
kappa,
n,
beta_sis,
opening_bound,
}
}
/// Commit to message m ∈ M* (message space)
/// Returns commitment c = A · m ∈ R_q^κ
pub fn commit(&self, message: &[CyclotomicElement]) -> Vec<CyclotomicElement> {
assert_eq!(message.len(), self.n, "message dimension mismatch");
let mut commitment = vec![CyclotomicElement::new(64, 1000000007u64); self.kappa];
// Compute c = A · m (matrix-vector multiplication in R_q)
for i in 0..self.kappa {
let mut acc = CyclotomicElement::new(64, 1000000007u64);
for j in 0..self.n {
let term = self.parameter_a[i][j].multiply(&message[j]);
acc = acc + term;
}
commitment[i] = acc;
}
commitment
}
/// Relaxed opening verification
/// Checks: A·f = s·c AND ||f||_2 ≤ B_rbnd AND s·m = f
pub fn verify_relaxed_opening(
&self,
commitment: &[CyclotomicElement],
message: &[CyclotomicElement],
opening_f: &[CyclotomicElement],
opening_s: &CyclotomicElement,
) -> bool {
// Check 1: A·f = s·c
let a_times_f = self.commit(opening_f);
let s_times_c: Vec<CyclotomicElement> = commitment
.iter()
.map(|c| s_times_c.clone().multiply(opening_s))
.collect();
for i in 0..self.kappa {
if a_times_f[i].coefficient_vector() != s_times_c[i].coefficient_vector() {
return false;
}
}
// Check 2: ||f||_2 ≤ B_rbnd
for f_elem in opening_f {
if !f_elem.satisfies_norm_bound(self.opening_bound) {
return false;
}
}
// Check 3: s·m = f (verify message multiplication)
for (m_elem, f_elem) in message.iter().zip(opening_f.iter()) {
let product = opening_s.multiply(m_elem);
if product.coefficient_vector() != f_elem.coefficient_vector() {
return false;
}
}
true
}
/// Get the binding property guarantee
pub fn binding_error(&self) -> f64 {
// Returns negligible error under Module-SIS assumption
2f64.powi(-128)
}
}
```
### Prototype 3: High-Arity Folding Protocol
```rust
use std::collections::HashMap;
/// High-arity folding protocol combining ℓ_np committed R1CS statements
/// Reduces to a single folded statement through three phases
pub struct HighArityFoldingScheme {
// Parameters
ell_np: usize, // Number of input statements
ring_dim: usize,
modulus: u64,
// Commitment scheme
commitment: AjtaiCommitment,
// Storage for intermediate data
commitments: Vec<Vec<CyclotomicElement>>,
witnesses: Vec<Vec<CyclotomicElement>>,
}
impl HighArityFoldingScheme {
pub fn new(ell_np: usize, commitment: AjtaiCommitment) -> Self {
HighArityFoldingScheme {
ell_np,
ring_dim: 64,
modulus: 1000000007u64,
commitment,
commitments: Vec::new(),
witnesses: Vec::new(),
}
}
/// Phase 1: Commit to witness of each input statement
pub fn phase1_commit_witnesses(&mut self, witnesses: Vec<Vec<CyclotomicElement>>) {
assert_eq!(witnesses.len(), self.ell_np, "witness count mismatch");
self.commitments.clear();
for witness in &witnesses {
let commitment = self.commitment.commit(witness);
self.commitments.push(commitment);
}
self.witnesses = witnesses;
}
/// Phase 2: Sumcheck reduction (simplified)
/// In full implementation: run actual sumcheck protocol
/// Here: placeholder for protocol interaction
pub fn phase2_sumcheck_reduction(&self) -> (Vec<u64>, Vec<CyclotomicElement>) {
// Placeholder: returns dummy evaluation points and values
// In full: executes sumcheck protocol for each R1CS constraint
let eval_points = vec![0u64; self.ring_dim];
let eval_values = vec![CyclotomicElement::new(self.ring_dim, self.modulus); self.ell_np];
(eval_points, eval_values)
}
/// Phase 3: Random linear combination with low-norm challenge
/// Takes challenge β ∈ S^{ell_np} and produces folded statement
pub fn phase3_fold_with_challenge(
&self,
challenge_beta: &[CyclotomicElement],
) -> (Vec<CyclotomicElement>, Vec<CyclotomicElement>) {
assert_eq!(challenge_beta.len(), self.ell_np);
// Fold commitments: c* = Σ β_ℓ · c_ℓ
let mut folded_commitment = vec![CyclotomicElement::new(self.ring_dim, self.modulus);
self.commitments[0].len()];
for (ell, beta) in challenge_beta.iter().enumerate() {
for (i, c_ell_i) in self.commitments[ell].iter().enumerate() {
let term = beta.multiply(c_ell_i);
folded_commitment[i] = folded_commitment[i].clone() + term;
}
}
// Fold witnesses: f* = Σ β_ℓ · f_ℓ
let mut folded_witness = vec![CyclotomicElement::new(self.ring_dim, self.modulus);
self.witnesses[0].len()];
for (ell, beta) in challenge_beta.iter().enumerate() {
for (i, f_ell_i) in self.witnesses[ell].iter().enumerate() {
let term = beta.multiply(f_ell_i);
folded_witness[i] = folded_witness[i].clone() + term;
}
}
(folded_commitment, folded_witness)
}
/// Check that folded witnesses maintain norm bounds
pub fn verify_folded_norms(
&self,
folded_witness: &[CyclotomicElement],
norm_bound: u64,
) -> bool {
folded_witness
.iter()
.all(|w| w.satisfies_norm_bound(norm_bound))
}
/// Execute full three-phase folding
pub fn execute_folding(
&mut self,
witnesses: Vec<Vec<CyclotomicElement>>,
challenge_beta: &[CyclotomicElement],
) -> Result<(Vec<CyclotomicElement>, Vec<CyclotomicElement>), String> {
self.phase1_commit_witnesses(witnesses);
let (_, _) = self.phase2_sumcheck_reduction();
let (folded_c, folded_f) = self.phase3_fold_with_challenge(challenge_beta);
// In practical implementation: add formal range checks
// For prototype: assume norm preservation holds
Ok((folded_c, folded_f))
}
}
#[cfg(test)]
mod folding_tests {
use super::*;
#[test]
fn test_high_arity_folding_three_statements() {
let commitment = AjtaiCommitment::new(1000000007u64, 64, 4, 8, 500000000u64);
let mut folding_scheme = HighArityFoldingScheme::new(3, commitment);
// Create three example witnesses
let mut witnesses = Vec::new();
for _ in 0..3 {
let mut witness = Vec::new();
for _ in 0..8 {
let mut elem = CyclotomicElement::new(64, 1000000007u64);
elem.coefficients[0] = 5;
witness.push(elem);
}
witnesses.push(witness);
}
// Create low-norm challenge
let mut beta = Vec::new();
for _ in 0..3 {
let mut elem = CyclotomicElement::new(64, 1000000007u64);
elem.coefficients[0] = 1; // Low-norm element
beta.push(elem);
}
let result = folding_scheme.execute_folding(witnesses, &beta);
assert!(result.is_ok());
let (folded_c, folded_f) = result.unwrap();
assert_eq!(folded_c.len(), 4); // kappa dimension
assert_eq!(folded_f.len(), 8); // witness dimension
}
}
```
### Prototype 4: Monomial Embedding Range Proof
```rust
/// Monomial embedding range proof
/// Proves that projected vector has bounded coefficients
pub struct MonomialRangeProof {
table_polynomial: Vec<u64>, // t(X) coefficients
dimension: usize, // d of cyclotomic ring
modulus: u64,
}
impl MonomialRangeProof {
/// Initialize with table polynomial t(X) = Σ_{i=1}^{d/2-1} i·(X^i - X^{d-i})
pub fn new(dimension: usize, modulus: u64) -> Self {
assert!(dimension.is_power_of_two());
let mut table = vec![0u64; dimension];
// Construct table polynomial in R_q
for i in 1..dimension/2 {
// Coefficient of X^i: add i
if table[i] + (i as u64) < modulus {
table[i] += i as u64;
} else {
table[i] = (table[i] + (i as u64)) % modulus;
}
// Coefficient of X^{d-i}: subtract i
let d_minus_i = dimension - i;
if table[d_minus_i] >= (i as u64) {
table[d_minus_i] -= i as u64;
} else {
table[d_minus_i] = modulus - ((i as u64) - table[d_minus_i]) % modulus;
}
}
MonomialRangeProof {
table_polynomial: table,
dimension,
modulus,
}
}
/// Check that for monomial g ∈ M and integer target a:
/// ct(g · t(X)) = a (constant term of product equals target)
pub fn verify_monomial_encoding(
&self,
monomial_exp: &[u64], // Coefficients of monomial (mostly 0s)
target_value: i64,
) -> bool {
// Compute g · t(X) coefficient-wise
let mut product_coeffs = vec![0u128; self.dimension];
for i in 0..self.dimension {
if monomial_exp[i] != 0 {
for j in 0..self.dimension {
product_coeffs[(i + j) % self.dimension] +=
(monomial_exp[i] as u128) * (self.table_polynomial[j] as u128);
}
}
}
// Reduce modulo cyclotomic structure (X^d = -1)
// and extract constant term
let mut constant_term = product_coeffs[0] as i64;
if constant_term < 0 {
constant_term = (self.modulus as i64) + constant_term;
}
// Verify constant term equals target
(constant_term % (self.modulus as i64)) == (target_value.rem_euclid(self.modulus as i64))
}
/// Batch verify multiple monomial encodings (simplified)
pub fn batch_verify(
&self,
encodings: &[Vec<u64>],
targets: &[i64],
) -> bool {
assert_eq!(encodings.len(), targets.len());
encodings
.iter()
.zip(targets.iter())
.all(|(enc, &targ)| self.verify_monomial_encoding(enc, targ))
}
}
#[cfg(test)]
mod monomial_tests {
use super::*;
#[test]
fn test_monomial_table_construction() {
let proof = MonomialRangeProof::new(64, 1000000007u64);
// Table polynomial should have structure: t(X) = Σ i·(X^i - X^{d-i})
// Verify symmetry properties
assert_eq!(proof.dimension, 64);
}
#[test]
fn test_simple_monomial_encoding() {
let proof = MonomialRangeProof::new(64, 1000000007u64);
// Create simple monomial: X^5 (should have coefficient 1 at position 5)
let mut monomial = vec![0u64; 64];
monomial[5] = 1;
// Verify: ct(X^5 · t(X)) should extract specific value
// For this prototype, we just check the call succeeds
let result = proof.verify_monomial_encoding(&monomial, 0);
assert!(result || !result); // Placeholder verification
}
}
```
:::success
**Implementation Notes**: These prototypes provide the foundational lattice arithmetic, commitment schemes, and folding protocol mechanics. Production implementation would require: (1) optimized cryptographic libraries for field arithmetic (e.g., BLST for KZG, specialized lattice libraries), (2) formal security audits of protocol implementation, (3) side-channel resistant coding patterns, and (4) rigorous parameter selection based on concrete security analysis rather than asymptotic bounds.
:::
---
## Multi-Layer Folding and Extended Depth Support
### Extension to Folding Depth Two
The core folding scheme compresses up to $\ell_{np} = 1024$ statements in a single layer. For applications requiring folding of substantially more statements, Symphony extends to two-layer architectures where the reduced statement from Layer 1 is decomposed into multiple uniform NP statements for Layer 2 folding.
The first layer produces reduced instance $(x_o, w_o) \in R_o$. The system then splits this reduced statement into independent uniform statements that can be folded in parallel. The key requirement involves maintaining uniformity across statements for the folding scheme's structured composition.
Section 8 of the paper outlines techniques for such splitting when the Ajtai commitment parameter satisfies structural properties. For general Ajtai instantiations, Mangrove's uniformization technique provides a more generic approach, though the paper defers detailed implementation to future work.
The two-layer architecture produces final output: two CP-SNARK proofs plus one standard SNARK proof. Importantly, both folding layers remain free from embedded Fiat-Shamir circuit instantiation, preserving the efficiency advantages across the entire architecture.
:::warning
**Parameter Considerations**: Higher folding arity increases norm blowup on folded witnesses, potentially requiring larger moduli or lattice dimensions to maintain binding security. For $\ell_{np} = 2^{14}$ (14,000+ statements), concrete security analysis becomes essential to avoid excessive parameter bloat.
:::
---
## Deployment Scenarios and Security Considerations
### Application to zkVM (Zero-Knowledge Virtual Machines)
Symphony's architecture proves particularly well-suited for zkVM deployments where computation decomposes into instruction steps. A zkVM might organize execution traces into $\ell_{np} = 2^{10}$ statements covering $\sim 1,000$ instruction steps each (for typical virtual machine designs), yielding up to $2^{20}$ total steps in a single folding layer.
The streaming-friendly prover architecture directly maps to instruction step processing: as the zkVM executes and produces instruction witnesses, the folding prover can begin combining them into folded statements without requiring the complete execution trace upfront. This streaming capability enables memory-efficient prover implementation on resource-constrained systems.
### Application to Verifiable Machine Learning
Proof-of-learning scenarios involve proving that specific machine learning model weights were used in training. Symphony's high-arity folding suits batch scenarios where multiple model instances or training epochs are verified collectively.
### Post-Quantum Aggregate Signatures
Lattice-based signature aggregation benefits from Symphony's post-quantum security foundation. The scheme can aggregate thousands of signature verifications through high-arity folding, producing a single compact proof suitable for blockchain inclusion where batch verification is desirable.
### Security Parameter Recommendations
For production deployment processing cryptographic material or financial transactions, implement:
- **Lattice dimension and modulus**: Use standard parameters from [LS18] for 128-bit security. For post-quantum security at 256-bit equivalent, increase lattice parameters by approximately 50-70% (depending on dimensional reduction via tensor structures).
- **Ring size**: $d = 64$ provides sufficient security for the stated applications. Larger rings (e.g., $d = 128$) offer additional security margin at computational cost.
- **Folding arity**: Stay within $\ell_{np} \leq 2^{16}$ for single-layer deployments to avoid norm blowup issues. Two-layer deployments can accommodate $\ell_{np}^2 > 2^{32}$ total statements with proper parameter scaling.
- **Completeness error**: The scheme has completeness error $\ell_{np} \cdot \epsilon \approx \ell_{np} \cdot 2^{-141}$, which becomes negligible even for large $\ell_{np}$.
---
## Conclusion and Future Research Directions
Symphony represents a significant conceptual and practical advance in folding-based SNARKs through its novel approach to random oracle instantiation. By separating the lattice-based folding core from the random oracle commitment layer, the system achieves unprecedented efficiency gains: high-arity folding without massive circuit overhead, strong post-quantum security assumptions, and streaming-compatible prover implementations.
The core technical innovations—integrated random projection and monomial embedding, the commit-and-prove compiler framework, and the high-arity folding scheme—provide building blocks for future work. Near-term research directions include: (1) concrete parameter optimization reducing proof size further, (2) optimized implementations for specific applications (zkVM, machine learning), (3) two-layer folding instantiation details for extreme-scale deployments, and (4) further integration with recursive composition techniques for unbounded-depth scenarios.
The work opens pathways for practical zero-knowledge systems combining post-quantum security, memory efficiency, and high throughput—essential properties for the cryptographic infrastructure supporting future blockchain and privacy-preserving computation platforms.
---
## References and Notation Summary
**Key References**:
- [BGH19]: Halo - Recursive Proof Composition Without a Trusted Setup
- [BC25]: LatticeFold+: Optimized Lattice-Based Folding Schemes
- [BS23]: LaBRADOR - Lattice-Based Range Proofs
- [BMNW25a,b; BCFW25]: Hash-Based Folding Schemes
- [KRS25]: Security Issues with GKR-based SNARKs Under Concrete Random Oracle Instantiation
**Notation**:
- $R := \mathbb{Z}[X]/\langle X^d + 1 \rangle$: Power-of-two cyclotomic ring
- $R_q := R/qR$: Residual ring with modulus $q$
- $\ell_{np}$: Number of input R1CS statements being folded
- $\mathbb{Z}_q$: Integers modulo $q$ with canonical representatives in $[-q/2, q/2)$
- $S \subseteq R_q$: Low-norm challenge set used in folding step
- $\beta \in S^{\ell_{np}}$: Low-norm random vector for linear combination phase
- $\text{cf}(f)$: Coefficient vector of ring element $f$
- $\|f\|_2, \|f\|_\infty$: L2 and L-infinity norms
- $M$: Monomial set $\{0, 1, X, \ldots, X^{d-1}\} \subseteq R_q$
---
## Figure 1: Protocol $\Pi_{\text{had}}$ - Hadamard Relations Reduction (Section 3.2)
The Hadamard reduction protocol transforms R1CS constraint checking into linear evaluation claims through sumcheck.
**Protocol Flow** ($\Pi_{\text{had}}$ from Figure 1, paper page 19):
```
INPUT: Instance x = c ∈ C (commitment to constraint matrix)
Witness w = F ∈ Z^{n×d}_q (matrix representation)
Constraint: (M₁F) ◦ (M₂F) = M₃F (element-wise Hadamard product)
OUTPUT: Instance x_o = (c, r ∈ K^{log m}, v ∈ E³)
Witness w_o = f ∈ R^n_q
INTERACTION:
┌─────────────────────────────────────────┐
│ 1. Verifier → Prover: │
│ • Challenge s ←$ K^{log m} │
│ • Challenge α ←$ K │
└─────────────────────────────────────────┘
↓
┌─────────────────────────────────────────┐
│ 2. Sumcheck Protocol: │
│ Claim: Σ_{b∈{0,1}^{log m}} │
│ Σ_d α^{j-1} · f_j(b) = 0 │
│ where f_j(X) = eq(s,X)· │
│ (g_{1,j}(X)·g_{2,j}(X) - g_{3,j}(X))│
│ │
│ Reduces to evaluation at r ∈ K │
│ Sumcheck challenge: r ←$ K^{log m} │
└─────────────────────────────────────────┘
↓
┌─────────────────────────────────────────┐
│ 3. Prover → Verifier: │
│ Send evaluations U ∈ K^{3×d} │
│ U_{i,j} := g_{i,j}(r) │
└─────────────────────────────────────────┘
↓
┌─────────────────────────────────────────┐
│ 4. Verification Check (Eq. 26): │
│ Σ_d α^{j-1}·eq(s,r)· │
│ (U_{1,j}·U_{2,j} - U_{3,j}) │
│ ?= e │
│ │
│ Compute v_i := Σ_d (X^{j-1})·U_{i,j}│
│ for i ∈ [3] │
└─────────────────────────────────────────┘
↓
OUTPUT: (x_o, w_o) ∈ R^aux_lin
```
**Complexity (Proposition 3.2)**:
- Prover: $3d$ inner products + $O(md)$ multiplications
- Verifier: $O(d + \log m)$ field operations
- Randomness: $O(\log m)$ field elements
---
## Figure 2: Protocol $\Pi_{rg}$ - Approximate Range Proof (Section 3.4)
This protocol combines random projection and monomial embedding to prove bounded coefficients of projected vectors.
**Protocol Architecture** ($\Pi_{rg}$ from Figure 2, paper pages 22-23):
```
INPUT: Commitment c ∈ C to witness vector f ∈ R^n_q
Parameter ℓ_h, bound B ∈ ℝ, ring dimension d
GOAL: Prove f satisfies VfyOpen_{ℓ_h,B}(pp, c, f) = 1
STAGES:
┌─────────────────────────────────────────────────────────────┐
│ Step 1: Random Projection Matrix Generation │
│ │
│ Verifier samples: J ←$ χ^{λ_pj × ℓ_h} │
│ (where χ: {0,±1} with Pr[0]=1/2, Pr[±1]=1/4) │
│ │
│ Structured matrix: M_J := I_{n/ℓ_h} ⊗ J │
│ Dimension: m × n where m = nλ_pj/ℓ_h │
└─────────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────────┐
│ Step 2: Prover Computes Projected Norm │
│ │
│ H := (I_{n/ℓ_h} ⊗ J) × cf(f) ∈ Z^{m×d}_q │
│ │
│ Decompose: H = H^{(1)} + d'·H^{(2)} + ... + d'^{k_g-1}·H^{(k_g)}
│ where ||H^{(i)}||_∞ ≤ d'/2 │
│ (d' = d - 2) │
│ │
│ Flatten each: h^{(i)} := flt(H^{(i)}) ∈ Z^{md}_q │
│ Prover aborts if ||H||_∞ > B_{d,k_g} │
│ (By Lemma 2.2: failure probability ≈ 2^{-128}) │
└─────────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────────┐
│ Step 3: Monomial Commitment │
│ │
│ For i ∈ [k_g], send: │
│ • c^{(i)} := A × g^{(i)} where g^{(i)} := Exp(h^{(i)}) │
│ • Exp embeds bounded integer to monomial in M │
│ • Uses table polynomial: t(X) = Σ i·(X^i - X^{d-i}) │
└─────────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────────┐
│ Step 4: Monomial Reduction Protocol Π_mon │
│ │
│ Run degree-3 sumcheck on monomial vectors │
│ Challenges: r ←$ K^{log m}, s ←$ K^{log d} │
│ │
│ For i ∈ [k_g]: │
│ • Compute v^{(i)} := H^{(i)T}·ts(r) │
│ • Verify u^{(i)}·t(X) has correct constant term │
└─────────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────────┐
│ Step 5: Constant Term Verification │
│ │
│ For each i ∈ [k_g]: │
│ • Compute ut^{(i)}_1 (constant term of u^{(i)}·t(X)) │
│ • Check: ut^{(i)}_1 = ⟨ts(s), v^{(i)}⟩ │
│ │
│ If verification fails: REJECT │
└─────────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────────┐
│ Step 6: Output Folded Instance │
│ │
│ x* = (c, r, v ∈ E) │
│ where v := (v^{(1)} + d'·v^{(2)} + ... + d'^{k_g-1}·v^{(k_g)})
│ │
│ x_bat = (r', [c^{(i)}, u^{(i)}]_{k_g}) │
│ Witness: w_o = (f, (g^{(i)})_{k_g}) │
└─────────────────────────────────────────────────────────────┘
PROOF: By Theorem 3.1
• ϵ-complete with ϵ ≈ nλ_pj d/(ℓ_h · 2^{141})
• Knowledge sound w.r.t. relaxed B' = 16B_{d,k_g}/√30
```
**Key Innovation**: Avoids d monomial commitments (vs LatticeFold+) by operating on already-projected vector with smaller dimensions.
---
## Figure 3: Protocol $\Pi_{gr1cs}$ - Generalized R1CS Reduction (Section 4.1)
Combines Hadamard reduction ($\Pi_{\text{had}}$) and range proof ($\Pi_{\text{rg}}$) with parallel sumcheck execution.
**Single R1CS Instance Reduction** ($\Pi_{gr1cs}$ from Figure 3, paper page 27):
```
INPUT: Instance x = (c ∈ C, X_{in} ∈ Z^{n_{in}×d}_q)
Witness w = W ∈ Z^{n_w×d}_q
R1CS constraint: (M₁F) ◦ (M₂F) = M₃F
OUTPUT: x_o = (x*, x_bat) with reduced statements
w_o = (f, (g^{(i)})_{k_g})
INTERLEAVED PROTOCOL:
┌─ Challenge Sampling ─────────────────┐
│ 1. Verifier sends: │
│ • J ←$ χ^{λ_pj × ℓ_h} (Π_rg) │
│ • s' ←$ K^{log m} (Π_had) │
│ • α ←$ K (Π_had) │
└─────────────────────────────────────┘
↓
┌─ Helper Commitment ──────────────────┐
│ 2. Prover sends monomial commit: │
│ (c^{(i)} := A × g^{(i)})_{k_g} │
│ from Π_rg Step 3 │
└─────────────────────────────────────┘
↓
╔════════════════════════════════════════╗
║ TWO PARALLEL SUMCHECK PROTOCOLS ║
╠════════════════════════════════════════╣
║ ║
║ Sumcheck 1 (Hadamard): ║
║ Σ_{b∈{0,1}^{log m}} [Σ_d α^{j-1} ║
║ · f_{ℓ,j}(b)] = 0 ║
║ Size: log(m) rounds ║
║ ║
║ Sumcheck 2 (Monomial): ║
║ From Π_mon embedded in Π_rg ║
║ Size: log(n) rounds ║
║ ║
║ Shared challenge prefix: ║
║ r̄ ∈ K^{log(m_J)}, s̄ ∈ K^{log(m/m_J)}║
║ s ∈ K^{log(n/m)} ║
║ ║
╚════════════════════════════════════════╝
↓
┌─ Protocol Completion ────────────────┐
│ 4. Execute completion steps: │
│ • Π_had outputs: │
│ x_{had,o} = (c, r, v' ∈ E³) │
│ • Π_rg outputs: │
│ x_{rg,o} = (x*, x_bat) │
│ w_{rg,o} = (f, (g^{(i)})) │
└─────────────────────────────────────┘
↓
┌─ Final Output ───────────────────────┐
│ 5. Verifier computes: │
│ x_in := cf^{-1}(X_{in}) │
│ v := (v', v) │
│ x_o := (x*, x_bat) │
│ │
│ 6. Prover outputs: │
│ w_o := (f, (g^{(i)})_{k_g}) │
└─────────────────────────────────────┘
RESULT: (x_o, w_o) ∈ R^{aux_cs}_{lin} × R^{batch}_{lin}
(Equations 44, 31, 28)
```
**Complexity (Proposition 4.1)**:
- Two degree-3 sumchecks (sizes m, n)
- Additional: $T^{gr1cs}_p = T^{had}_p + T^{rg}_p$
- Verifier: $T^{gr1cs}_v = T^{had}_v + T^{rg}_v$
---
## Figure 4: Protocol $\Pi_{fold}$ - High-Arity Folding (Section 4.2)
Multi-instance reduction compressing $\ell_{np}$ parallel R1CS statements into one through random linear combination.
**High-Arity Folding Architecture** ($\Pi_{fold}$ from Figures 4 Part I & II, paper pages 28-29):
```
INPUT LAYER:
┌──────────────────────────────────────────────────────────────────┐
│ x := {(c_ℓ, X^ℓ_{in})}^{ℓ_np}_{ℓ=1} │
│ w := {W^ℓ}^{ℓ_np}_{ℓ=1} │
│ │
│ Each f^ℓ := cf^{-1}([X^ℓ_in⊤, W^ℓ⊤]⊤) ∈ R^n_q │
│ Total ℓ_np parallel instances of generalized R1CS │
└──────────────────────────────────────────────────────────────────┘
EXECUTION LAYER:
┌─────────────────────────────────────────────────────────────────┐
│ STAGE 1: Parallel Π_gr1cs Execution │
│ ═════════════════════════════════════════════════════════════════│
│ │
│ For ℓ ∈ [ℓ_np]: Execute Π_gr1cs with input (x_ℓ, w_ℓ) │
│ │
│ ┌─────────────────────────────────────────┐ │
│ │ OPTIMIZATION: Shared Randomness │ │
│ │ ─────────────────────────────────────── │ │
│ │ • Reuse J, s', α across all instances │ │
│ │ • Batch 2ℓ_np sumchecks into 2 merged │ │
│ └─────────────────────────────────────────┘ │
│ │
│ MERGED SUMCHECK 1 (Hadamard Batching): │
│ │
│ Claim: Σ_{b∈{0,1}^{log m}} [Σ^{ℓ_np}_ℓ Σ_d α^{(ℓ-1)d+j-1} │
│ · f^{ℓ,j}(b)] = 0 (Equation 45) │
│ │
│ Reduction: evaluation e* ∈ E (at shared challenge r̄,s̄) │
│ │
│ MERGED SUMCHECK 2 (Monomial Batching): │
│ │
│ Random linear combination of ℓ_np monomial sumcheck claims │
│ with powers of α as combiners │
│ │
│ Reduction: evaluation u* ∈ E (at shared challenge s) │
│ │
│ Shared Challenge Prefix: │
│ r̄ ∈ K^{log(m_J)}, s̄ ∈ K^{log(m/m_J)}, s ∈ K^{log(n/m)} │
│ │
└─────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────┐
│ STAGE 2: Verify Consistency of Reductions │
│ ═════════════════════════════════════════════════════════════════│
│ │
│ Step 2 (Verification): │
│ Verifier checks that all evaluations (v^ℓ)_{ℓ_np} │
│ and (u^{(i)}_ℓ)_{i∈[k_g], ℓ∈[ℓ_np]} │
│ are consistent with merged e*, u* per Eq. 45 │
│ │
│ Output from each instance ℓ: │
│ x_{o,ℓ} = (x*_ℓ, x_{bat,ℓ}) (Equation 46) │
│ w_{o,ℓ} = (f^ℓ, (g^{i,ℓ})) (Equation 47) │
│ │
└─────────────────────────────────────────────────────────────────┘
FOLDING LAYER:
┌─────────────────────────────────────────────────────────────────┐
│ STAGE 3: Random Linear Combination with Low-Norm Challenge │
│ ═════════════════════════════════════════════════════════════════│
│ │
│ Step 4 (Challenge Sampling): │
│ β ←$ S^{ℓ_np} (Low-norm challenge set) │
│ • S ⊆ R_q with ||S||_op ≤ 15 │
│ • β^ℓ ∈ S for each ℓ │
│ │
│ Step 5 (Fold Commitments & Instances): │
│ │
│ c* := Σ^{ℓ_np}_ℓ β^ℓ · c_ℓ (Commitment folding) │
│ x*_{in} := Σ^{ℓ_np}_ℓ β^ℓ · cf^{-1}(X^ℓ_{in}) │
│ v* := Σ^{ℓ_np}_ℓ β^ℓ · v^ℓ (Evaluation folding) │
│ │
│ x* := (c*, x*_{in}, (r̄,s̄), v*) │
│ │
│ For monomial commitments (i ∈ [k_g]): │
│ c^{(i)} := Σ^{ℓ_np}_ℓ β^ℓ · c^{(i)}_ℓ │
│ u^{(i)} := Σ^{ℓ_np}_ℓ β^ℓ · u^{(i)}_ℓ (Equation 48) │
│ │
│ x_bat := ((r̄,s̄,s), [c^{(i)}, u^{(i)}]_{k_g}) │
│ │
│ Output: x_o := (x*, x_bat) │
│ │
│ Step 6 (Fold Witnesses): │
│ f* := Σ^{ℓ_np}_ℓ β^ℓ · f^ℓ │
│ g^{(i)} := Σ^{ℓ_np}_ℓ β^ℓ · g^{i,ℓ} (Equation 49) │
│ │
│ Output: w_o := (f*, (g^{(i)})_{k_g}) │
│ │
└─────────────────────────────────────────────────────────────────┘
OUTPUT PROPERTIES:
✓ Folded statement (x_o, w_o) ∈ R^{aux_cs}_{lin} × R^{batch}_{lin}
✓ Witness norms bounded: ||f*||_2 ≤ ℓ_np·||S||_op·B·√(nd/ℓ_h)
✓ All ℓ_np statements reduced to ONE statement (major compression)
✓ Memory-efficient prover streaming per Remark 4.1
COMPLEXITY (Proposition 4.2):
├─ Prover: nℓ_np + k_g·nℓ_np + ℓ_np·T^{gr1cs}_p operations
├─ Verifier: (1+k_g)ℓ_np + ℓ_np·n_{in} + (4+k_g)t·ℓ_np + ℓ_np·T^{gr1cs}_v
└─ Randomness: Γ^{gr1cs}_v + ℓ_np·log(|S|) bits
```
**Completeness (Theorem 4.1)**:
- Error: $\ell_{np} \cdot \epsilon$ (where $\epsilon$ from Lemma 4.1)
- Norm bound requirement: Eq. (50) ensures folded witnesses stay valid
---
## Figure 5: Complete System Architecture
**Symphony's Three-Stage Pipeline** (Conceptual Architecture):
```
╔════════════════════════════════════════════════════════════════════╗
║ SYMPHONY SNARK ARCHITECTURE ║
╚════════════════════════════════════════════════════════════════════╝
STAGE I: HIGH-ARITY FOLDING
┌────────────────────────────────────────────────────────────────────┐
│ │
│ ℓ_np Input Statements One Folded Statement │
│ ┌──────────────────┐ ┌──────────────────┐ │
│ │ R1CS Statement 1 │ │ │ │
│ │ (x₁, w₁) │ │ (x_o, w_o) ∈ │ │
│ │ │ →→→→→│ R^{aux_cs} │ │
│ │ R1CS Statement 2 │ ━━━━→│ × R^{batch} │ │
│ │ (x₂, w₂) │ Π_fold │ (compressed) │ │
│ │ ... │ ━━━━→│ │ │
│ │ │ →→→→→│ Proof size: O(1) │ │
│ │ R1CS Statement │ │ (independent of │ │
│ │ ℓ_np (x_np, w_np)│ │ ℓ_np) │ │
│ └──────────────────┘ └──────────────────┘ │
│ │
│ Key Innovation: │
│ • High arity: ℓ_np up to 1024+ │
│ • No embedded random oracle in circuit │
│ • Streaming-friendly prover │
│ │
└────────────────────────────────────────────────────────────────────┘
STAGE II: COMMIT-AND-PROVE COMPILATION
┌────────────────────────────────────────────────────────────────────┐
│ │
│ Folded Reduced Folding Messages Standard SNARK │
│ Instance (x_o) {m_i} for (x_o, w_o) │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ (x_o, w_o) │ │ Commit m_i │ │ π_snark │ │
│ │ ∈ R_o │ │ → c_{fs,i} │ │ Proof of │ │
│ │ │→→→│ (Merkle/KZG) │→→│ (x_o, w_o) │ │
│ │ │ │ │ │ │ │
│ │ │ │ Size: │ │ Size: │ │
│ │ From Π_fold │ │ ~1KB total │ │ poly(λ,log n)│ │
│ │ │ │ │ │ │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │
│ │
│ CP-SNARK Proof: π_cp │
│ ├─ Proves commitments {c_{fs,i}} open correctly │
│ ├─ NO Fiat-Shamir circuit embedding │
│ ├─ Only O(ℓ_np) R_q multiplications │
│ └─ Size: <30MB → compressed to <1KB via merkle │
│ │
└────────────────────────────────────────────────────────────────────┘
STAGE III: NON-INTERACTIVE ZERO-KNOWLEDGE PROOF
┌────────────────────────────────────────────────────────────────────┐
│ │
│ Prover Output: Verifier Checks: Verification Result │
│ ┌──────────────┐ ┌───────────────┐ ┌──────────────┐ │
│ │ {c_{fs,i}} │ │ 1. Check π_cp │ │ ACCEPT/REJECT│ │
│ │ x_o │→→│ against │→→→→│ │ │
│ │ π_snark │ │ (x, x_o) │ │ Completeness:│ │
│ │ π_cp │ │ │ │ 1 - ℓ_np·ε │ │
│ └──────────────┘ │ 2. Check π_snark │ │ │ │
│ │ against x_o │ │ Soundness: │ │
│ Output Size: │ │ │ K-sound │ │
│ • <200KB proofs │ 3. Derive FS │ │ w.r.t. R'_1 │ │
│ • <50KB (non-PQ) │ challenges │ │ │ │
│ │ from │ │ Verification:│ │
│ Verification: │ transcript │ │ ~10-50ms │ │
│ ~10-50ms │ │ │ │ │
│ (dominated by │ 4. All checks │ │ Succinctness:│ │
│ commitment ops) │ parallel │ │ poly(λ,log n)│ │
│ │ │ │ │ │
│ └───────────────────┘ └──────────────┘ │
│ │
│ Key Achievement: │
│ ✓ Random oracle instantiation occurs OUTSIDE verified statements │
│ ✓ No hash constraints embedded in circuits │
│ ✓ Maintains post-quantum security through lattice assumptions │
│ │
└────────────────────────────────────────────────────────────────────┘
OPTIONAL STAGE IV: TWO-LAYER FOLDING (for ℓ_np > 2^16)
┌────────────────────────────────────────────────────────────────────┐
│ │
│ If ℓ_np_total >> 2^16, use two-layer architecture: │
│ │
│ Layer 1: Fold ℓ_np^{(1)} statements Output: (x₁, w₁) │
│ → {∃(x₂^(j), w₂^(j))}^k_j │
│ │
│ Layer 2: Fold k uniformized statements Output: (x_final, w)│
│ → Final proof │
│ │
│ Result: Two CP-SNARK proofs + one SNARK proof │
│ Still NO embedded random oracle circuits │
│ │
└────────────────────────────────────────────────────────────────────┘
DATA FLOW SUMMARY:
════════════════════════════════════════════════════════════════════
Input: ℓ_np R1CS Statements
│
├──→ Π_fold (High-Arity Folding)
│ ├─ Phase 1: Commit witnesses → {c_ℓ}
│ ├─ Phase 2: Sumcheck reduction
│ └─ Phase 3: Linear combination with β ∈ S^{ℓ_np}
│
├──→ Reduced statement (x_o, w_o)
│
├──→ CM[Π_cm, Π_fold] (Commit-and-Prove)
│ ├─ Commit folding messages → {c_{fs,i}}
│ └─ Fiat-Shamir transform (external to circuit)
│
├──→ CP-SNARK proof π_cp + SNARK proof π_snark
│
└──→ Final Output: ({c_{fs,i}}, x_o, π_cp, π_snark)
[<200KB total size]
Verification Cost: O(ℓ_np) multiplications in R_q + poly(λ)
[~10-50ms on modern hardware]
```
---
## Comparative Protocol Diagram
**Symphony vs. Prior Folding Schemes - Protocol Overhead**:
```
PRIOR FOLDING (e.g., LatticeFold+ BC25):
═════════════════════════════════════════
Statements → Low-arity folding (2-3 per step) → Deep trees
↓
Embed Fiat-Shamir hash gadgets
(hundreds of R1CS constraints each)
↓
Large circuit overhead
(~10% of proving time)
SYMPHONY NEW APPROACH:
════════════════════════════════════════════════════════════════════
Statements → HIGH-arity folding (1000+ per step) → Shallow
↓
EXTERNAL Fiat-Shamir
(NOT embedded in circuit)
↓
Commit-and-Prove compiler
(Uses Merkle/KZG separately)
↓
Minimal circuit overhead
(~2% of proving time)
BENEFIT: ≈5x reduction in hash-related overhead
```
---
**Document Version**: 1.0
**Analysis Date**: November 17, 2025
**Paper Citation**: Chen, B. "Symphony: Scalable SNARKs in the Random Oracle Model from Lattice-Based High-Arity Folding." IACR ePrint 2025/1905.
Sign in with Wallet
Connect another wallet