Part II The technical architecture of the Aleo blockchain (Marlin and Varuna)

11 min readFeb 21, 2024

Marlin and Varuna

1. Overview of Zero-Knowledge Proof Technology

Zero-knowledge proofs are widely applied in blockchain applications and have become crucial tools for privacy and scalability. Among these, zk-SNARKs (succinct non-interactive arguments of knowledge) are favored for their short proof size and efficient verification. In practice, the efficiency of verification is significantly determined by the proof’s length/computational complexity, which is associated with the application’s circuit size. A typical SNARK protocol includes the following processes:

In general, the length of a SNARK proof has a sublinear relationship with the witness (the prover’s private input). Verifiers need to review the instance and circuit information during proof verification, making the verification complexity related to the instance length and the size of the circuit. Achieving succinct proofs and efficient verification ultimately boils down to the preprocessing setup, specifically the setup process illustrated above.

Proof Conciseness: To achieve shorter proofs, where the proof length is logarithmically related to the circuit gate size 𝑙𝑒𝑛(𝜋)=𝑂𝜆 (log (|𝐶|))
Verification Efficiency: If verifiers do not have time to review circuit-related information, the setup algorithm generates a verification key (vk), usually a short summary of the circuit.

In the specific schemes of zk-SNARKs widely used today, such as Groth16, Sonic, and Plonk, as well as optimized implementation protocols like Halo2 and Marlin, all these specific zero-knowledge proof schemes have a preprocessing setup process. During this process, some public parameters (common reference string, CRS) are secretly generated. These parameters will be involved in the subsequent proof generation and verification processes. The term “secret” here refers to the issue of “toxic waste” introduced during the generation of these public parameters. Anyone who can access this toxic waste could potentially forge proofs, making the management of this toxic waste especially critical. After the CRS is generated, it needs to be immediately destroyed to prevent misuse. Nowadays, MPC algorithm can avoid these problems.

Currently, there are three main types of preprocessing setup:

trusted setup per circuit: A representative scheme is Groth16. In this type of setup, each circuit has a corresponding toxic waste random number, which is crucial and must be permanently discarded after one use. Otherwise, if a prover gains access to this toxic waste, they could forge proofs. Therefore, any change in the circuit requires the regeneration of both the proving and verification parameters (pp and vp). Generating the Common Reference String (CRS) consumes a significant amount of computational and human resources, making this approach more suited for static, unchanging application scenarios. For instance, Zcash implements this scheme to facilitate privacy-preserving transactions based on the UTXO model.

𝑆(𝑐𝑖𝑟𝑐𝑢𝑖𝑡; 𝑟)

universal (updatable) setup: Sonic and Plonk are typical examples of this setup, with Plonk being an optimized scheme of Sonic. In such setup, the random number r/toxic waste is only involved in the generation of global parameters and is independent of the circuit; this algorithm runs only once. The algorithms for generating proving and verification parameters (pp and vp) are deterministic, depending on the global parameters (gp) and the circuit. For different circuits, it is only necessary to run this deterministic algorithm each time. Therefore, a universal SRS (Structured Reference String) can support a broader and more diverse range of application scenarios. Although a universal setup is more expensive and generates larger proofs compared to a circuit-specific setup, its ability to accommodate more complex and diverse application scenarios makes it more popular among users.

𝑆=(𝑆𝑖ₙ𝑖ₜ, 𝑆𝑖ₙ𝑑ₑₓ): 𝑆𝑖ₙ𝑖ₜ(𝜆 ,𝑟)→ 𝑔𝑝, 𝑆𝑖ₙ𝑑ₑₓ(𝑔𝑝, 𝐶𝑖𝑟𝑐𝑢𝑖𝑡)→ (𝑝𝑝,𝑣𝑝)

transparent setup: This setup does not contain any secret randomness, meaning there is no trusted setup process. The proving and verification parameters (pp and vp) it generates are only related to the circuit. A representative protocol is Bulletproofs, which are used for range proofs.

Aleo uses the Varuna scheme, which is an improved version of the Marlin scheme. The main difference between Varuna and Marlin is that Marlin’s arithmetic language only allows R1CS, while Varuna can support both R1CS and custom gates and lookups(custom constraints lookup arguments), such as Plonkish. This means that in the arithmetic representation of circuits, Marlin is limited to three matrices, whereas Varuna can utilize a greater number of matrices, offering better extensibility. Beyond addition and multiplication circuits, Varuna can support various types of arithmetic circuits with corresponding distinct construction methods, referred to as generalized R1CS.

We will give a detailed introduction to the Marlin scheme.

2. Overview of the Marlin Protocol

The Marlin protocol encompasses three main processes: updatable setup, Prove, and Verify.

(1) Updatable Setup mainly includes two algorithms:

Setup Algorithm: A deterministic algorithm used for generating SRS, based on different polynomial commitment schemes and security assumptions. This algorithm, which needs to run only once and is independent of the circuit, can be found in Marlin’s GitHub repository. For detailed information, refer to marlin-poly-commit.

Index Algorithm: Based on the SRS generated above and different circuits, it generates a provingKey and a verifierKey. This deterministic algorithm can be run by anyone.

(2) Prove: The process where the prover generates a proof using the provingKey, instance, and witness.

https://github.com/arkworks-rs/marlin/blob/master/src/ahp/prover.rs

(3) Verify: The process where the verifier uses the verifierKey and instance to verify the proof.

https://github.com/arkworks-rs/marlin/blob/master/src/ahp/verifier.rs

Constructing an effective SNARK for a general circuit typically requires two main components:

Polynomial Commitment Scheme
IOP (Interactive Oracle Proof): Essentially a multi-round interactive protocol where the verifier sends a challenge in each round, and the prover responds with an oracle. Through this oracle, the verifier can make queries/inquiries.

The Marlin protocol discusses various polynomial commitment schemes under different security models, including:

Opening multiple polynomials with the same degree bound at a single point
Opening multiple polynomials with multiple degree bounds at a single point
Opening multiple polynomials with multiple degree bounds at multiple points

Let’s dive into a few specific schemes.

3. Polynomial Commitment Schemes

3.1. Definition of Polynomial Commitments

A polynomial commitment allows a prover to generate a commitment to a polynomial and later open this commitment at a specific point, producing a proof that the opened value matches the committed polynomial. The most straightforward method would be to send the polynomial to the verifier for direct validity verification, but this approach scales linearly with the polynomial’s degree(𝑑), which is impractical for polynomials of billion-degree (𝑑) magnitudes in real applications. Instead, the goal is to construct proofs that are both succinct and efficiently verifiable.

The polynomial commitment process involves the following algorithms:

𝐾𝑒𝑦𝐺𝑒𝑛/𝑠𝑒𝑡𝑢𝑝(1𝜆 )→ 𝑔𝑝: Generates a public key, public parameters, or a common reference string. This is represented directly by 𝑔𝑝 (global parameters).
𝑐𝑜𝑚𝑚𝑖𝑡(𝑔𝑝, 𝑓)→ 𝑐𝑜𝑚𝑓: Given the 𝑔𝑝(global parameters) and a polynomial, the prover can compute a commitment to the polynomial.
𝑒𝑣𝑎𝑙(𝑔𝑝, 𝑓, 𝑧)→ (𝑣, 𝜋): The prover computes the value 𝑣 of the polynomial at a point 𝑧, along with the proof 𝜋.
𝑣𝑒𝑟𝑖𝑓𝑦(𝑔𝑝, 𝑐𝑜𝑚𝑓, 𝑧, 𝑣, 𝜋) → 𝑎𝑐𝑐𝑒𝑝𝑡 ~ 𝑜𝑟~ 𝑟𝑒𝑗𝑒𝑐𝑡: The verifier checks the correctness of the value $$v$$computed by the polynomial at point 𝑧.

3.2. KZG Polynomial Commitment Scheme

This section details the specific algorithms of the KZG polynomial commitment scheme.

setup: \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}ₚ is a finite field of prime order 𝑝, and \𝑚𝑎𝑡ℎ𝑏𝑏{𝐺} is a cyclic group with a generator 𝐺. In this algorithm, 𝛽 represents the toxic waste that must be permanently destroyed. In practice, Multi-Party Computation (MPC) is introduced to generate this value. In actual schemes, particularly in universal setup zero-knowledge proof schemes, this algorithm functions as 𝑆𝑖ₙ𝑖ₜ, participating only in the generation of 𝑔𝑝 and being independent of the circuit. The size of 𝑔𝑝 is linearly related to 𝑑, where 𝑑 is typically on the order of billions, implying that 𝑔𝑝 is very large.
commit: Making a commitment to a polynomial involves calculating the value of the polynomial at 𝛽, even though the value of 𝛽 is not known. However, this calculation can be performed using 𝑔𝑝.
eval: The computational effort required for the prover to calculate the quotient polynomial 𝑞(𝑋) is substantial, as the degree 𝑑 of this polynomial is typically very large, often on the order of billions. After calculating the quotient polynomial, a commitment to this polynomial must be made. This means that the computational effort for proof is very large. How to optimize this in practice will be discussed later.
verify: The verification equation (𝛽 — 𝑧)∙ 𝑐𝑜𝑚𝑞 = 𝑐𝑜𝑚𝑓 — 𝑣∙ 𝐺 involves the toxic waste 𝛽, but the verifier cannot know the information about 𝛽. Therefore, it is necessary to introduce bilinear mapping/pairing for the final verification step.

3.3. MarlinKZG10

In the marlin-poly-commit repository, several polynomial commitment schemes are implemented, including:

Inner-product-argument Polynomial Commitment (PC)
Marlin variant of the Kate-Zaverucha-Goldberg (KZG) Polynomial Commitment: marlinKZG10
Sonic/AuroraLight variant of the KZG Polynomial Commitment
Marlin variant of the Papamanthou-Shi-Tamassia multivariate Polynomial Commitment: Marlin-PST13

This article will not detail every scheme but will focus on some of the representative ones.

Marlin requires polynomial commitment schemes to satisfy:

Extractability: A stronger notion than binding.
Efficiency:

(1) For the prover: The time to create a polynomial commitment should be short, implying the need to reduce the polynomial’s degree d (low-degree); the verification of proofs should be efficient, meaning the size of the generated proof/quotient polynomial commitment should be proportional to the polynomial’s degree, not to the highest degree D.

(2) For the verifier: the commitment size, proof size, time to verify an opening must be independent of the claimed degrees for the polynomials

hiding：commitments and proofs of evaluation reveal no information about the committed polynomial beyond the publicly stated degree bound and the evaluation itself.

To meet the functional and security requirements specified in the Marlin project, Marlin employs an extended Kate-Zaverucha-Goldberg (KZG) polynomial commitment scheme, achieving extractability within the algebraic group model (AGM).

(1) Setup In the code, g = G, gamma_g = 𝛾 𝐺, where 𝛾 is introduced to provide the hiding feature for commitments. If the hiding feature is not considered, then the components marked in blue in the scheme are not necessary.

(2) Commit

The process of committing to a univariate polynomial is as follows: Normally, the commitment to a polynomial 𝑝(𝑋)=𝑎₀ + 𝑎₁𝑋+\𝑙𝑑𝑜𝑡𝑠+𝑎ₜ𝑋𝑡 would be 𝑐𝑜𝑚𝑚𝑖𝑡(𝑝(𝑋))=𝑝(𝛽)∙ 𝐺. However, this method does not offer the hiding property since it reveals the value of the polynomial at 𝛽. To ensure hiding, a random blinding polynomial, \𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒{𝑝(𝑋)}, is added to the calculation. The final commitment is 𝑐𝑜𝑚𝑚𝑖𝑡(𝑝(𝑋))=𝑝(𝛽)∙ 𝐺+\𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒{𝑝(𝛽)}∙𝛾 𝐺.
For multiple univariate polynomials, represented as [𝑝𝑖]𝑖₌₁ⁿ, to achieve hiding, it’s not necessary to add a random blinding polynomial \𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒{𝑝𝑖(𝑋)} to every univariate polynomial. It depends on the randomly generated vector \𝑣𝑒𝑐{𝑤}=[𝑤𝑖]𝑖₌₁ⁿ.

(3) Eval -> (𝜋)

The open algorithm in the code, specifically the ‘compute_witness_polynomial && open_with_witness_polynomial’, essentially generates a commitment/proof for the quotient polynomial/witness polynomial.

For a univariate polynomial:

(1) The witness polynomial 𝑤(𝑋)=\𝑓𝑟𝑎𝑐{𝑝(𝑋)-𝑝(𝑧)}{𝑋-𝑧}, and its proof is 𝑤(𝛽)∙ 𝐺.

(2) To maintain the hiding feature, \𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒{𝑤(𝑋)}=\𝑓𝑟𝑎𝑐{\𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒{𝑝(𝑋)}-\𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒{𝑝(𝑧)}}{𝑋-𝑧}, and its proof is \𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒{𝑤(𝛽)}∙𝛾 𝐺. Since the prover introduces a new polynomial, the value of this new polynomial at point 𝑧 cannot be obtained through SRS, thus the generated proof includes an extra term\𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒 𝑣=\𝑜𝑣𝑒𝑟𝑙𝑖𝑛𝑒{𝑝}(𝑧).

For multiple univariate polynomials, a linear combination is used with a value 𝜉 randomly chosen by the verifier.

(4) Verify

For a single variable polynomial, the verification algorithm is consistent with KZG and is not further derived here.
For multiple univariate polynomials, the verification method is a batch check, which essentially introduces 𝜉 for a linear combination.

3.4. Marlin-PST13

The KZG polynomial commitment scheme is not only applicable to univariate polynomials but also to multivariate polynomials and supports batch proofing. The PST13 scheme, utilizing KZG for multivariate 𝑘-𝑣𝑎𝑟𝑖𝑎𝑡𝑒 polynomial commitments, achieves batch proofs.

Assume the verifier has commitment values 𝑐𝑜𝑚𝑓₁,\𝑙𝑑𝑜𝑡𝑠,𝑐𝑜𝑚𝑓ₙ.
The prover aims to prove 𝑓𝑖(𝑢𝑖,𝑗=𝑣𝑖,𝑗), 𝑖∈[1,𝑛],𝑗∈[1,𝑚], and can generate a batch proof 𝜋, which requires only a single group element.

4. Proof Properties of Polynomial Commitments

Combining polynomials commitment with Interactive Oracle Proofs (IOP), they are frequently used in protocols like zeroTest, sumcheck, and productCheck. The proof system in Marlin mainly utilizes the zeroTest and sumcheck protocols. Before introducing these protocols, it’s necessary to discuss the concept of vanishing polynomials.

4.1. Vanishing Polynomial

In a prime field \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}ₚ, let 𝜴 be a subgroup of the field with order 𝑘. A vanish polynomial 𝑍𝜴(𝑋) takes the value 0 for all elements of 𝜴. If the subgroup is a cyclic group generated by 𝜴, and if 𝜴=\{1,𝜴, \𝑙𝑑𝑜𝑡𝑠, 𝜴𝑘⁻¹\}, the vanishing polynomial 𝑍𝜴(𝑋)=(𝑋-1)(𝑋-𝜔)(𝑋-𝜔²)\𝑙𝑑𝑜𝑡𝑠(𝑋-𝜔𝑘⁻¹)=𝑋𝑘 — 1. The definition of a vanishing polynomial plays a significant role here. Instead of calculating the product of 𝑘 polynomials, one only needs to compute 𝑋𝑘-1. For 𝑧∈ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}ₚ , computing 𝑍𝜴(𝑟) requires ≤ 2log₂ 𝑘 field operations.

If 𝜴 is a multiplicative subgroup, then 𝑍𝜴(𝑋)=𝑥𝑘-1.
If 𝜴 is a 𝜉-𝑐𝑜𝑠𝑒𝑡 of some multiplicative subgroup 𝜴₀, then 𝜴=𝜉 𝜴₀, 𝑍𝜴(𝑋)=𝑋𝑘 — 𝜉𝑘

4.2. ZeroTest on 𝜴

The prover has a polynomial 𝑓(𝑋) and needs to prove that 𝑓(𝑋) equals 0 over the entire multiplicative subgroup 𝜴, which essentially means proving that 𝑓(𝑋) can be divided by the vanishing polynomial of the multiplicative subgroup 𝑍𝜴(𝑋)=𝑋𝑘 — 1