Algebraic Proof Systems in Aleo. From Groth16 to Marlin.

Zero-knowledge SNARKs (zk-SNARKs) are the cryptographic workhorse behind Aleo’s private smart contracts. They allow one to prove in zero-knowledge that a computation was performed correctly (for example, satisfying some relations $F(x,w)=y$) without revealing any secret inputs $w$, yet with proofs that are succinct (constant-sized) and fast to verify. Over the past decade the ecosystem of SNARK protocols has rapidly evolved. Early pairing-based SNARKs like Groth16 required a unique trusted setup for each circuit. Newer protocols (Sonic, PLONK, Marlin, etc.) shifted to universal and updatable setups at the cost of somewhat larger proofs or more prover work. Aleo’s SnarkVM (the private execution engine) and SnarkOS (the chain client) have similarly migrated from Groth16-like inner-SNARKs toward Marlin-based systems (specifically an Aleo-enhanced “Varuna” variant).

ZK-SNARKs 101. R1CS and Quadratic Programs

At the core of most pairing-based SNARKs is the Rank-1 Constraint System (R1CS) model. A computation (say a Leo smart contract function) is compiled into an arithmetic circuit over a finite field $\mathbb{F}$, with wires and gates (additions and multiplications). The R1CS view encodes this circuit by three sparse matrices $A,B,C$ and a vector of variables $z=(x,w)$ (public inputs $x$ and private witness $w$), enforcing the constraint

where “$\circ$” is entry-wise (Hadamard) product. Concretely, if $A_i$, $B_i$, $C_i$ are the $i$-th rows of $A,B,C$, this says for each gate $i$:

Groth16 (2016) was one of the first SNARKs to efficiently prove R1CS satisfiability. It does so by reducing the R1CS to a Quadratic Arithmetic Program (QAP). The idea is elegant: treat each gate’s constraint as a polynomial equation. Define polynomials

that encode all the left-input, right-input, and output wiring of the circuit (via Lagrange interpolation over gate indices). Then one shows that for a correct witness $z$, the polynomial

is divisible by the so-called vanishing polynomial

where $r_1,\dots,r_n$ are distinct points corresponding to each of the $n$ multiplication gates. In other words, $P(z)$ has roots at every gate index if and only if each gate constraint holds. Formally there exists a quotient polynomial $H(z)$ such that

The SNARK prover’s task is to convince the verifier that this polynomial divisibility holds, without revealing $H$ or the witness. Using a cryptographic trusted setup, both parties sample a random secret field element $s$ (discarded afterward) and publish a structured reference string containing commitments $g, g^s, g^{s^2},\dots,g^{s^d}$ in a pairing-friendly elliptic curve (degree $d$ covers circuit size). The prover then “evaluates” these polynomials at $z=s$ in the exponent: for instance, committing to the polynomial $P(z)$ by computing

Similarly $T(s)$ and $H(s)$ are committed. Using the bilinear pairing $e(\cdot,\cdot)$, the verifier checks

where $g^T = g^T(s)$ encodes $T(s)$, ensuring $P(s) = H(s),T(s)$ in the exponent. By the Schwartz–Zippel lemma, a single random check like this suffices for high confidence in the polynomial identity. In practice, Groth16 does a clever three-term pairing check, but the core idea is this division check.

Importantly, Groth16’s proof consists of just three group elements (on G1/G2), so verification takes only a couple of pairings — extremely fast and constant-time. However, the catch is the trusted setup: each new circuit (i.e. new program or changed program logic) requires generating a fresh SRS [$g, g^s, g^{s^2},\dots$] and then securely destroying $s$. If $s$ is leaked or reused, toxic waste could enable forging proofs. Thus, Groth16 offers minimal proof size and fast verification but at the cost of per-circuit ceremonies and a heavy initial overhead (a “one-time pad” for each circuit). In legacy Zcash-style UTXO systems this was acceptable (programs rarely change), but for a general smart contract platform it quickly becomes unmanageable.

Toward Universal SRS. Sonic and PLONK

To avoid repeated trusted setups, the SNARK community invented universal SRS schemes: generate one large common reference string that can handle many circuits (up to some size bound), and allow anyone to update it (adding new randomness) for extra security. Early such work includes Sonic (2019) and PLONK (2019-20), which build on Kate–Zaverucha–Goldberg (KZG) polynomial commitments. KZG commitments work as follows: pick a secret $\alpha$, publish the group powers $H = [g, \alpha g, \alpha^2 g,\dots,\alpha^d g]$ as the proving key. To commit to a polynomial $P(x)=\sum_{i=0}^d p_i x^i$, compute

a single group element. This hides $P(x)$ since $\alpha$ is secret. Later one can prove an evaluation $P(t)=y$ by providing a short opening proof (just a few group elements) using pairings.

PLONK uses KZG commitments to encode all circuit polynomials at once (e.g. wires, gates, permutation polynomials) and then verifies via a multi-point opening argument. A key innovation is the permutation (copy) argument: PLONK adds a polynomial that enforces that each wire’s value is consistently used across the circuit (so-called copy constraints). The result is a fully universal SRS: one KZG setup covers any circuit up to a size bound, and circuits are checked using only polynomial commitments and their openings. In practice, a PLONK proof is only moderately larger than Groth16’s (on the order of 3–5 group elements) and verification requires a handful of pairings. The prover is somewhat slower (since it opens and performs FFTs over the whole circuit), but no new setup is needed per circuit.

Sonic was an intermediate step toward universal SNARKs. It also achieves a universal setup, but its protocol was more complex and had higher overhead. Sonic builds on the idea of polynomial commitment but must commit to multiple polynomials (including helper polynomials) and does a linear-size verifiable computation. It was largely superseded by PLONK, which optimizes similar ideas. In essence, Sonic demonstrated that universal SNARKs were possible, but Marlin, PLONK, and others showed faster and smaller-proof constructions.

The Marlin Protocol. Algebraic Holographic Proofs

Marlin (2020) combines the best of both worlds: like PLONK, it has a universal and updatable SRS, but it further shrinks proof and verification cost via a new “holographic” PCP approach. Its core is an Algebraic Holographic Proof (AHP) for R1CS, which essentially is an interactive PCP over low-degree polynomials. In high-level terms, Marlin works like this:

1. Universal Setup (SRS) One sets a maximum circuit size $N$ and samples randomness $\alpha$ as above. Publish the full KZG parameters ${g,\alpha g,\alpha^2 g,\ldots,\alpha^N g}$ (and their pairing counterparts). This SRS is updatable – anyone can multiply each element by a new secret and re-publish, without altering the prior ability to prove new circuits. The resulting SRS is universal for all circuits up to size $N$.
2. Prover / Indexing Given a particular R1CS instance (matrices $A,B,C$) and a witness $w$, the prover compiles these into certain low-degree polynomials (via the AHP indexer). Intuitively, think of encoding each constraint equation into polynomial form, similar to QAP. Marlin’s indexing produces polynomial vectors (labeled $a(X), b(X), c(X), \ldots$) whose evaluations on a domain ${1,\dots,n}$ correspond to $Az, Bz, Cz$.
3. Proof Generation (Prover) The prover engages in a concise PCP: they commit (using KZG) to these indexed polynomials. Then via a Fiat-Shamir hash, the protocol randomly samples a field element $r$ and some challenge polynomials. The prover computes linear combinations and sum-checks of these polynomials at the random point $r$, generating a short proof of correctness. Concretely, Marlin’s prover produces just a handful of group elements: essentially commitments to certain combined polynomials and their evaluation proofs. Thanks to an algebraic sum-check technique, the final proof size is constant (a few G1 elements) independent of circuit size.
4. Verification The verifier checks pairings on those few group elements. It verifies the KZG openings at the challenge point and the polynomial identity $P(r) = H(r),T(r)$, now done in a vectorized way thanks to the PCP collapse. Crucially, Marlin achieves constant-time verification: one final check that runs in $O(1)$ pairings. This means even massive circuits incur only a fixed, small verification cost.

In other words, Marlin realized a linear PCP over polynomials (holographic proof) that can be tied into KZG commitments. The fancy words aside, the practical upshot is impressive: Marlin proofs are a few hundred bytes, verifiable in milliseconds, with no per-circuit trust ceremony beyond the one-time SRS generation.

Mathematically, a few highlights help intuition:

• Polynomial Commitment Base. Like PLONK, Marlin uses KZG commitments. For a polynomial $Q(X)=\sum q_i X^i$, the commit is $g^{Q(\alpha)}$ (one group element). Opening $Q$ at a challenge $r$ yields a small proof of size $O(1)$.
• Combined Checks. Marlin constructs polynomials for the three R1CS matrices $A,B,C$ (call their indexed versions $\tilde{A}(X),\tilde{B}(X),\tilde{C}(X)$ over the domain), along with auxiliary polynomials. The PCP step picks random challenges and checks an identity of the form A~(r) B~(r)−C~(r)=Q(r) T(r),\tilde{A}(r)\,\tilde{B}(r) - \tilde{C}(r) = Q(r)\,T(r), very much like the Groth16 idea but done in the exponent and collapsed via the random point $r$. (Here $T(r)$ is the vanishing polynomial of the domain.) The prover gives commitments to $\tilde{A},\tilde{B},\tilde{C},Q$ and proofs of their evaluations at $r$. The verifier uses pairings to check one final equation implying the constraint product holds.
• Efficiency Gains. Compared to Sonic, Marlin’s innovation was to reduce the number of such polynomial commitments and to optimize the linear checks. In practice, Marlin’s proof uses fewer group elements than Sonic (by “several”, per implementations) and the verifier time is ~3× faster. Moreover, Marlin speeds up the prover dramatically (10× over Sonic) by clever arithmetic, making its prover time comparable to circuit-specific SNARKs.

To summarize, Marlin gives us the best of both worlds: short proofs + constant verification (like Groth16) with only one universal setup (like PLONK). In fact, Marlin’s designers reported a performance table (Figure 2.2 in their thesis) showing Marlin’s proof size is just a few group elements for both Groth16 and PLONK-sized circuits, and its proving and verification are very practical.

Trade-offs. Proof Size, Time, and Setup

Every SNARK choice involves a trade-off. Here’s how Groth16, PLONK/Sonic, and Marlin compare in broad strokes:

• Proof Size. Groth16 wins with tiny proofs (3 group elements ~ 95 bytes). PLONK/Marlin proofs are typically a bit larger (on the order of 3–6 group elements, say 150–300 bytes) because they include multiple commitments and openings. Still, hundreds of bytes is negligible for blockchain use. Sonic’s proofs are larger, which is one reason it fell out of favor.
• Verification Time. All these pairing SNARKs have O(1) verify time (constant number of pairings) once parameters are set, so verification is very fast. Groth16 requires 3 pairings, PLONK around 5, Marlin maybe 2–3 (Marlin’s clever design actually achieves fewer pairings than older systems). In practice these all verify in milliseconds for real circuits. STARKs or Bulletproofs, by contrast, have much larger proofs or verification cost.
• Proving Time. Groth16 is relatively fast to prove (though large circuits still take time). PLONK and Marlin provers do extra work (FFT over the circuit, polynomial arithmetic). Sonic was notably slower. Marlin’s prover, however, was engineered for speed: it uses FFTs and linear algebra to get roughly Groth16-like speed (especially with good multi-threading). In short, Marlin’s prover is a few times slower than Groth16 in raw speed, but this is often acceptable for developers because it avoids repeated setups.
• Trusted Setup. This is often the deciding factor. Groth16’s circuit-specific setup (one SRS per circuit) is a dealbreaker for dynamic smart contracts. Sonic/PLONK/Marlin have a universal trusted setup: one ceremony generates a master SRS (plus updatability) covering all circuits up to a given size. After that, new programs require only a cheap public key derivation (no new randomness). The cost is that the universal SRS might be quite large (say gigabytes) if the max circuit size is huge. For Aleo, the team accepts that up-front: they ran an MPC to generate a massive SRS that covers the expected circuit sizes and allow updates.
• Expressivity. Some SNARKs support more than R1CS constraints. Plonky2 (from Polygon) and others allow custom gates or lookup arguments. Aleo’s current system, Varuna, is an extension of Marlin that supports “generalized R1CS” with custom gates and lookup tables. This makes it more like PLONK in expressivity. Groth16 is locked into plain R1CS (addition and multiplication), whereas PLONK/Varuna can optimize with precomputed lookups (e.g. fast SHA or range proofs) within one argument.

A handy analogy: think of each proof system as a way of giving away minimal hints about a secret computation. Groth16 is like giving a tiny fingerprint of the whole proof that only works for one precise program, whereas PLONK/Marlin is like carrying a “one-time master key” that can lock any door up to a certain size. Groth16’s key changes for each door (circuit), but PLONK/Marlin’s universal key fits many doors (circuits), as long as you don’t enlarge the door beyond the key’s design. The cost is that carrying the universal key bundle (SRS) is bulkier to begin with, but afterwards proving new doors is easy.

Aleo’s Use of Marlin (Varuna) in SnarkVM

Aleo’s SnarkVM synthesizer compiles Leo programs into R1CS and generates proofs. Early prototypes of Aleo did use Groth16 (for example, an “inner SNARK” model), but as Aleo matured the team settled on a Marlin-based system. In fact, Aleo’s code and documentation refer to Varuna, a Marlin-derived proof system supporting custom gates. Varuna is essentially Marlin “+” extra flexibility: while Marlin as published only encodes R1CS (three matrices), Varuna supports additional arithmetic constraints (Plonkish lookup tables, Range gates, etc.) for better efficiency on typical operations (e.g. SHA/Keccak acceleration).

The Aleo Engine works roughly as follows: a user writes a Leo program and executes it locally in SnarkVM. This produces an R1CS that enforces the program logic and the current state transitions. The SnarkVM prover (which can run on the user’s machine or a delegated server) then invokes Marlin/Varuna to produce a proof of correctness. That proof (along with the public inputs/outputs) is submitted as a transaction to SnarkOS. Validators quickly verify the proof using Marlin’s verification key (derived from Varuna’s universal setup).

// Pseudocode: Generating and verifying a Marlin proof in SnarkVM (Rust)
use snarkvm_marlin::{Marlin, SRS};
use snarkvm_r1cs::{Circuit, Prover, Verifier};

// 1. Load or generate universal SRS (trusted ceremony output) covering up to size N
let srs: SRS<bls12_377::Engine> = SRS::load_or_generate("marlin_srs.params", 2u64.pow(20))?;

// 2. Define the R1CS for our computation (e.g., a Leo function)
let circuit: Circuit<bls12_377::Fr> = MyLeoProgram::compile_to_r1cs()?;

// 3. Run setup (derives PK/VK from the universal SRS and this circuit)
let (pk, vk) = Marlin::setup(&srs, &circuit)?;

// 4. Prover creates a proof given a witness `witness`
let proof = Marlin::prove(&pk, &circuit, &witness)?;

// 5. Verifier checks the proof against the public inputs
let valid = Marlin::verify(&vk, &circuit.public_input(), &proof)?;
assert!(valid, "Proof failed verification");

The above schematic code shows how one would use SnarkVM’s Marlin library to prove and verify an R1CS circuit. The real SnarkVM hides much of this complexity: it handles loading the SRS (downloaded once), synthesizing the circuit, and batching tasks. But under the hood it is exactly using Marlin (via an Arkworks-based implementation).

Because Marlin/Varuna is a preprocessing SNARK, Aleo must perform one big MPC ceremony to create the initial SRS for all its R1CS constraints. Aleo did this! The Aleo community ran a multi-party computation yielding universal parameters. After that, any change in an Aleo program (e.g. updating a smart contract) does not require a new MPC—only re-compiling to R1CS and a quick local setup step to derive the circuit-specific proving/verification keys from the universal SRS. This is a huge practical benefit for developers (no recurring ceremonies or trusted launch keys).

Finally, Aleo (SnarkOS) includes proof-of-prover incentives (Aleo’s “puzzles”) which actually encourage people to build specialized proving hardware (even GPUs) to generate Marlin proofs faster. This means Aleo isn’t just using off-the-shelf SNARKs: it’s co-designing hardware and protocols. But regardless of hardware, the cryptographic core is this Marlin/Varuna framework.

Strengths, Limitations, and Aleo’s Edge

Strengths. Marlin/Varuna gives Aleo succinct proofs with no per-circuit setup. Verification time is minimal (great for on-chain use), and proof sizes are small (keeps transaction bandwidth low). The SNARK supports general arithmetic circuits, so any Leo program can be proven. The algebraic design means proofs rely only on established assumptions (pairings) and enjoy full zero-knowledge. Aleo specifically leverages advanced features (custom gates, lookups) to make ZK-proving as efficient as possible for typical operations (hashes, etc.).

Limitations. The initial trusted setup (SRS) is still a significant chore: you need a big ceremony and careful distribution. Also, polynomial-based SNARKs require a pairing-friendly curve (Aleo uses BLS12-377 by choice), which means they’re not post-quantum secure. The prover work, while optimized, is still substantial for very large circuits (hence Aleo’s interest in hardware acceleration). Compared to transparently setup STARKs, Marlin proofs are smaller but rely on trusted randomness and pairings. Lastly, if Aleo’s requirements outgrow its SRS bound, a new setup with a larger size would be needed (so Aleo must anticipate growth).

What Makes Aleo Unique. Aleo is one of the first platforms built from the ground up on zkSNARKs with general programmability. While many chains may use privacy SNARKs just for transactions, Aleo’s vision is privacy-first programmability: write any logic in Leo and deploy it privately. The use of Marlin/Varuna is central to that: it provides a universal proving infrastructure. Aleo’s SnarkVM ties this into a full virtual machine. By open-sourcing SnarkVM and using the Marlin theory in code, Aleo lets developers experiment with ZK proofs as first-class artifacts. The extensibility of this platform is key: developers could imagine adding new proof gadgets or recursive proofs down the line. In fact, Aleo’s roadmap discusses possible integration of “proof-carrying data” (Darlin, recursive composition) on top of Marlin.

The real practical upshot is: as an Aleo developer you get zero-knowledge by default. Behind the scenes, SnarkVM uses these complex algebraic protocols to ensure your program’s execution is sound, without any extra effort on your part besides writing correct Leo code. The “magic” of SNARKs is hidden behind the familiar contract paradigm. But understanding Groth16→PLONK→Marlin illuminates how this magic works, and why Aleo chose Marlin/Varuna: it hits the sweet spot of efficiency and flexibility for a smart contract platform.

References and Further Reading

• Groth16 -Jens Groth, On the Size of Pairing-Based Non-interactive Arguments (EUROCRYPT 2016).
• Marlin - Chiesa et al., Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS (EUROCRYPT 2020).
• PLONK - Gabizon et al., PLONK: Permutations over Lagrange-bases (2020).
• Sonic - Maller et al., Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable SRS (CCS 2019).
• Aleo Docs - Core architecture (SnarkVM/SnarkOS), FAQs, and the Varuna spec.
• SnarkVM Code - GitHub - AleoNet/snarkVM (with crates like snarkvm-marlin, snarkvm-synthesizer).
• VeriZexe (Zulu, 2022) - A specification that uses Marlin/Sonic for private transactions.
• Alpen Labs Survey - Practical comparisons of SNARKs (Groth16, PLONK, Marlin).

Write by alexanderblv for the Aleo, May 2025 https://x.com/alexander_blv ERC20 - 0x1e1Aa06ff5DC84482be94a216483f946D0bC67e7