Part III The technical architecture of the Aleo blockchain (AHP)

7 min readMar 14, 2024

AHP

AHP (Algebraic Holographic Proof) is essentially evolved from IOP (Interactive Oracle Proof). The distinction between AHP and IOP lies in the division of the verifier’s verification process into two phases: offline and online. The offline algorithm is known as the indexer algorithm, which can be understood as involving multiple rounds of interaction between the prover and the verifier. Additionally, the verifier can access the indexer oracle.

1. R1CS

R1CS primarily involves instance-witness pairs ((𝐴,𝐵,𝐶), (𝑥,𝑤)), where 𝐴,𝐵,𝐶 are matrices, and (𝑥,𝑤)∈ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹} satisfy (𝐴𝑧)∘(𝐵𝑧)=𝑐𝑧; 𝑧=(1,𝑥,𝑤). For a detailed explanation of R1CS, please refer to this example. We will not delve into further details here. If we use Lagrange interpolation to construct three univariate polynomials, \ℎ𝑎𝑡{𝑧}𝐴(𝑋), \ℎ𝑎𝑡{𝑧}𝐵(𝑋), \ℎ𝑎𝑡{𝑧}𝐶(𝑋), on a subgroup 𝐻 from the three sets of vectors 𝐴𝑧, 𝐵𝑧, 𝐶𝑧, then R1CS needs to prove the following:

entry-wise product：∀ 𝜅∈ 𝐻, \ℎ𝑎𝑡{𝑧}𝐴(𝜅)\ℎ𝑎𝑡{𝑧}𝐵(𝜅)-\ℎ𝑎𝑡{𝑧}𝐶(𝜅)=0
linear relation：∀ 𝑀∈ \{𝐴,𝐵,𝐶\},∀ 𝜅∈ 𝐻, \ℎ𝑎𝑡{𝑧}𝑀(𝜅)=\𝑠𝑢𝑚𝑖\𝑖ₙ 𝐻𝑀[𝜅,𝑖]\ℎ𝑎𝑡{𝑧}(𝑖)，meaning it needs to be proven that 𝐴𝑧, 𝐵𝑧, 𝐶𝑧 are indeed derived from the same linear combination 𝑧 of matrices 𝐴,𝐵,𝐶.

The entry-wise product can be easily proven using the aforementioned zeroTest, while the linear relation requires the use of the sumCheck protocol for proof.

2. Lemma

Lemma 1 (Univariate Sumcheck for Subgroups): Given a multiplicative subgroup 𝑆⊂\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}, for a polynomial 𝑓(𝑋), the sum \𝑠𝑢𝑚𝜅\𝑖ₙ 𝑆𝑓(𝜅) = 𝜎. If and only if 𝑓(𝑋) can be represented as 𝑓(𝑋)=ℎ(𝑋)∙ 𝑣𝑆(𝑋)+𝑋∙ 𝑔(𝑋) + 𝜎/|𝑆|, where 𝑣𝑆(𝑋) is the vanish polynomial over subgroup 𝑆, and 𝑆 denotes the number of elements in the subgroup 𝑆. This lemma is derived from the paper Aurora: Transparent Succinct Arguments for R1CS, and we will not delve into a detailed explanation of this lemma here.

3. AHP for R1CS

3.1. Offline: Index Algorithm

Due to the verification process of zk-SNARKs typically requiring “reading the description of the computation, in order to know what statement is being verified,” and the large computational load involved, which means the verification time is proportional to the computational effort, Marlin’s approach splits the verification process into two phases:

Offline phase: Produces a short summary for the given circuit, consisting of coefficient matrices (index).
Online phase: Uses this short summary to verify the proof, called instance.

The offline algorithm in Marlin is known as the indexer algorithm, which encodes the coefficient matrices.

The indexer 𝐼(\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}; (𝐻, 𝐾)⊂ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}; (𝐴,𝐵,𝐶)∈ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}𝐻× 𝐻), |𝐾| \𝑔𝑒 𝑚𝑎𝑥\{||𝐴||, ||𝐵||, ||𝐶||\}→\{\ℎ𝑎𝑡{𝑟𝑜𝑤}𝑀(𝑋), \ℎ𝑎𝑡{𝑐𝑜𝑙}𝑀(𝑋), \ℎ𝑎𝑡{𝑣𝑎𝑙}𝑀(𝑋)\}𝑀\𝑖ₙ \{𝐴,𝐵,𝐶\}, outputs nine univariate polynomials.

Based on the non-zero elements of matrices 𝐴,𝐵,𝐶, these non-zero elements are mapped into three vectors: row, col, val, and then polynomialized on subgroup 𝐻 using Lagrange interpolation. These nine univariate polynomials have degrees less than |𝐾| and ensure that the bivariate polynomial \ℎ𝑎𝑡{𝑀}(𝑋,𝑌) is a low-degree extension of 𝑀.

Matrix 𝑀 corresponds to the row, col, and val matrices of all non-zero elements in matrices 𝐴,𝐵,𝐶. For example:

Based on the diagram, let’s briefly introduce the calculation process for 𝑟𝑜𝑤(𝜅): Essentially, it involves converting high-degree polynomials over the group 𝐾 into more low-degree polynomials over the group 𝐻 through mapping. This means calculating nine low-degree polynomials for 𝑟𝑜𝑤𝐴,𝐵,𝐶, 𝑐𝑜𝑙𝐴,𝐵,𝐶, 𝑣𝑎𝑙𝐴,𝐵,𝐶 on 𝐻.

Assume the subgroup 𝐻=\{ℎ₁,ℎ₂,\𝑙𝑑𝑜𝑡𝑠,ℎₙ\} has an order 𝑜𝑟𝑑(𝐻)=|𝐻|=𝑛, which is related to the constraints and the number of instances and witnesses. In the given example, 𝑛=6 corresponds to the number of columns in row, col, val, but for ease of FFT transformations, 𝑛=²³=8.
The subgroup 𝐾=\{𝑘₁,𝑘₂,\𝑙𝑑𝑜𝑡𝑠, 𝑘ₘ\} has an order 𝑜𝑟𝑑(𝐾)=|𝐾|=𝑚, which relates to the number of non-zero entries in the matrix 𝑀. In the example above, the total number of non-zero entries in matrices 𝐴,𝐵 𝑎𝑛𝑑 𝐶 is 14, but for FFT convenience, 𝑚=²⁴=16.
𝑟𝑜𝑤(𝜅): Let 𝜅 = 𝑘𝑗, then 𝜙𝐾(𝜅)=𝑗, and 𝑡𝜅 is the row index of the 𝑗th non-zero entry in matrix 𝑀, assumed to be 𝑖, hence 𝑟𝑜𝑤(𝜅)=𝜙𝐻⁻¹(𝑖)=ℎ𝑖. Using Lagrange interpolation based on (𝑥=𝜅=𝑘𝑗, 𝑦=𝑟𝑜𝑤(𝜅)=ℎ𝑖), the polynomial \ℎ𝑎𝑡{𝑟𝑜𝑤𝑀}(𝑋) can be derived.

3.2. Online: Proving and Verifying Algorithms

Let 𝑝𝑝=[\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}; (𝐻, 𝐾)⊂ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}; (𝐴,𝐵,𝐶)∈ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}𝐻× 𝐻), with |𝐾| \𝑔𝑒 𝑚𝑎𝑥\{||𝐴||, ||𝐵||, ||𝐶||\}].

Prover(𝑝𝑝, 𝑥, 𝑤): The prover’s inputs are an instance 𝑥∈\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}𝐻[\𝑙𝑒 |𝑥|] and a witness 𝑤∈\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}𝐻[\𝑔𝑒 |𝑥|].

Verifier(𝑝𝑝, 𝑥, indexer): The verifier’s inputs are an instance 𝑥∈\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}𝐻[\𝑙𝑒 |𝑥|] and access to the indexer oracle.

(1) Round 1 — Prover

Assume the multiplicative subgroup 𝐻=\{ℎ₁, ℎ₂,\𝑙𝑑𝑜𝑡𝑠, ℎₙ\}, define the instance polynomial \ℎ𝑎𝑡{𝑥}(𝑋), 𝑥∈ 𝐻[\𝑙𝑒 |𝑋|]=\{ℎ₁, ℎ₁,\𝑙𝑑𝑜𝑡𝑠,ℎ|ₓ|\}.
Define the shifted witness polynomial \ℎ𝑎𝑡{𝑤}(𝑋) such that for 𝑋∈ 𝐻[\𝑔𝑒 |𝑋|]=\{ℎ|ₓ|₊₁,\𝑙𝑑𝑜𝑡𝑠, ℎₙ\}, its corresponding value is \𝑓𝑟𝑎𝑐{𝑤(𝛾)-\ℎ𝑎𝑡{𝑥}(𝛾)}{𝑣𝐻[\ₗₑ|ₓ|](𝛾)}, 𝛾∈ 𝐻[\𝑔𝑒 |𝑋|]. This construction is utilized because 𝑧=(𝑥,𝑤).
Let 𝑧=(𝑥;𝑤)∈ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}𝐻, construct \ℎ𝑎𝑡{𝑧}𝐴(𝑋), \ℎ𝑎𝑡{𝑧}𝐵(𝑋), \ℎ𝑎𝑡{𝑧}𝐶(𝑋)∈\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}<|𝐻|⁺𝑏[𝑋] based on the linear combination 𝑧𝐴=𝐴𝑧, 𝑧𝐵=𝐵𝑧,𝑧𝐶=𝐶𝑧 on subgroup 𝐻.
ZeroTest: Calculate the polynomial ℎ₀(𝑋) 𝑠.𝑡. \ℎ𝑎𝑡{𝑧}𝐴(𝑋)∙ \ℎ𝑎𝑡{𝑧}𝐵(𝑋)-\ℎ𝑎𝑡{𝑧}𝐶(𝑋)=ℎ₀(𝑋)∙ 𝑣𝐻(𝑋).
Note: \ℎ𝑎𝑡{𝑧}(𝑋)=\ℎ𝑎𝑡{𝑤}(𝑋)𝑣𝐻[\ₗₑ|ₓ|](𝑋)+\ℎ𝑎𝑡{𝑥}(𝑋) can also be directly constructed based on 𝑧=(𝑥;𝑤) in group 𝐻.
Construct a random polynomial 𝑠(𝑋)∈\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}<²|𝐻|⁺𝑏⁻¹[𝑋] and \𝑠𝑢𝑚𝜅\𝑖ₙ 𝐻𝑠(𝜅)=𝜎₁, also known as the mask polynomial, to satisfy the zero-knowledge property of the univariate sumcheck.
The prover sends \ℎ𝑎𝑡{𝑤}(𝑋), \ℎ𝑎𝑡{𝑧}𝐴(𝑋), \ℎ𝑎𝑡{𝑧}𝐵(𝑋), \ℎ𝑎𝑡{𝑧}𝐶(𝑋), ℎ₀(𝑋), 𝑠(𝑋), 𝜎₁.

(2) Round 1 — Verifier

Randomly sends 𝛼, 𝜂𝐴,𝜂𝐵,𝜂𝐶∈\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}, where 𝛼 is to reduce the linear check problem to a sumcheck problem, and 𝜂𝐴,𝜂𝐵,𝜂𝐶 is to bundle three sumcheck problems into one.

(3)Round2-Prover

> reduce lincheck problem to a sumcheck problem: the verifier samples a random element α ∈ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹} and sends it to Prover. Indeed, letting 𝑟(𝑋, 𝑌) = 𝑢𝐻(𝑋,𝑌).
> Prover is left to convince Verifier that the following univariate polynomial sums to 0 on 𝐻.

Following the provided reference, if it can be proven that the sum of polynomial 𝑞₁(𝑋) over 𝐻 equals 𝜎₁, then it demonstrates a linear relation between 𝑓₁(𝑋) and 𝑓₂(𝑋).

The polynomial 𝑞₁(𝑥)=𝑠(𝑋)+𝑟(𝛼,𝑋)𝑓₁(𝑋) -𝑟𝑀(𝛼, 𝑋)𝑓₂(𝑋) where 𝑓₁(𝑋)=𝜂𝐴∙ \ℎ𝑎𝑡{𝑧}𝐴(𝑋)+𝜂𝐵∙ \ℎ𝑎𝑡{𝑧}𝐵(𝑋)+𝜂𝐶∙ \ℎ𝑎𝑡{𝑧}𝐶(𝑋)𝑓₂(𝑋)=\ℎ𝑎𝑡{𝑧}(𝑋)

Next, the prover needs to demonstrate to the verifier the following polynomial \𝑠𝑢𝑚𝜅\𝑖ₙ 𝐻𝑞₁(𝜅)=𝜎₁, indicating that the value within the red box is zero, which corresponds to the linear relation that needs to be proven.

𝑟𝑀(𝛼, 𝑋)=\𝑠𝑢𝑚𝜅\𝑖ₙ 𝐻𝑟(𝛼,𝜅) \ℎ𝑎𝑡{𝑀}(𝜅, 𝑋)

𝑞₁(𝑋)=𝑠(𝑋)+\𝑓𝑟𝑎𝑐{𝑣𝐻(𝛼)-𝑣𝐻(𝑋)}{𝛼-𝑋}∙(𝜂𝐴∙ \ℎ𝑎𝑡{𝑧}𝐴(𝑋)+𝜂𝐵∙ \ℎ𝑎𝑡{𝑧}𝐵(𝑋)+𝜂𝐶∙ \ℎ𝑎𝑡{𝑧}𝐶(𝑋))- \{\𝑠𝑢𝑚𝜅\𝑖ₙ 𝐻[𝜂𝐴∙ 𝑟(𝛼,𝜅)∙\ℎ𝑎𝑡{𝐴}(𝜅, 𝑋)+𝜂𝐵∙ 𝑟(𝛼,𝜅)∙\ℎ𝑎𝑡{𝐵}(𝜅, 𝑋)+𝜂𝐶∙ 𝑟(𝛼,𝜅)∙\ℎ𝑎𝑡{𝐶}(𝜅, 𝑋)]\}∙ \ℎ𝑎𝑡{𝑧}(𝑋)

Note:

The bivariate polynomial 𝑟(𝑋,𝑌)=𝑢𝐻(𝑋,𝑌)=\𝑓𝑟𝑎𝑐{𝑣𝐻(𝑋)-𝑣𝐻(𝑌)}{𝑋-𝑌}, where 𝑣𝐻(𝑋) is the vanishing polynomial on 𝐻.
If 𝐻 is a multiplicative subgroup, then 𝑢𝐻(𝑋,𝑌)=\𝑓𝑟𝑎𝑐{𝑣𝐻(𝑋)-𝑣𝐻(𝑌)}{𝑋-𝑌}=\𝑓𝑟𝑎𝑐{𝑋|𝐻|-𝑌|𝐻|}{𝑋-𝑌}; 𝑢𝐻(𝑋,𝑋)=|𝐻|𝑋|𝐻|⁻¹=𝑛𝑋ⁿ⁻¹.

Next, the prover needs to prove to the verifier the following polynomial \𝑠𝑢𝑚𝜅\𝑖ₙ 𝐻𝑞₁(𝜅)=𝜎₁, in accordance with the lemma mentioned in section 5.2.

(4) Round 2 — Verifier

Randomly selects 𝛽₁∈ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}\𝐻.

(5) Round 3 — Prover: Sumcheck

𝜎₂=\𝑠𝑢𝑚𝜅\𝑖ₙ 𝐻𝑞₂(𝜅) requires finding polynomials ℎ₂(𝑋),𝑔₂(𝑋).

(6) Round 3 — Verifier

Randomly selects 𝛽₂∈ \𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}\𝐻.

(7) Round 4 — Prover: Sumcheck

Using the calculation formula for \ℎ𝑎𝑡{𝑀}(𝑋,𝑌):

𝑓₃(𝑋)=𝑋𝑔₃(𝑋)+𝜎₃/|𝐾|, this equation proves that 𝑓₃ sums to 𝜎₃ over 𝐾.
𝑎(𝑋)-𝑏(𝑋)𝑓₃(𝑋)=ℎ₃(𝑋)𝑣𝐾(𝑋), this equation demonstrates that 𝑓₃ agrees with the correct addends over 𝐾.

These two equations can be combined into one: ℎ₃(𝑋)𝑣𝐾(𝑋)=𝑎(𝑋)-𝑏(𝑋)(𝑋𝑔₃(𝑋)+𝜎₃/|𝐾|).

(8)Round4-Verifier

Summary:

Offline: 9 univariate polynomials define the low-degree extension of matrix $$M$$, leading to the output of 9 polynomial commitments.
Online: The verifier queries each of the 9 indexer polynomials and 12 prover polynomials at exactly one location, which amounts to 21 queries.:

The prover outputs 12 commitments, 21 evaluations, and 3 evaluation proofs.
12 commitments:

At point 𝛽₁: \ℎ𝑎𝑡{𝑤}, \ℎ𝑎𝑡{𝑧𝐴},\ℎ𝑎𝑡{𝑧𝐵},\ℎ𝑎𝑡{𝑧𝐶}, ℎ₀, 𝑠, ℎ₁,𝑔₁
At point 𝛽₂: ℎ₂, 𝑔₂
At point 𝛽₃: ℎ₃,𝑔₃, \ℎ𝑎𝑡{𝑟𝑜𝑤}𝑀,\ℎ𝑎𝑡{𝑐𝑜𝑙}𝑀, \ℎ𝑎𝑡{𝑣𝑎𝑙𝑀}, 𝑀∈\{𝐴,𝐵,𝐶\}.
Overall: 27 \𝑚𝑎𝑡ℎ𝑏𝑏{𝐺}₁ + 24\𝑚𝑎𝑡ℎ𝑏𝑏{𝐹}𝑞.

4. Optimizations for AHP

Elimination of ℎ₀ and \ℎ𝑎𝑡{𝑧𝐶}:

Research indicates it’s possible to omit proving the zeroTest, simply by replacing \ℎ𝑎𝑡{𝑧𝐶}(𝑋) directly with \ℎ𝑎𝑡{𝑧𝐴}(𝑋)∙\ℎ𝑎𝑡{𝑧𝐵}(𝑋) in subsequent proofs.

2. Minimal Zero Knowledge Query Bound: