Stellar Soroban UltraHonk verifier

[qpzm]

Summary

We aims to bring Aztec's UltraHonk verifier to the Stellar ecosystem by:

1. Reviewing the TaceoLabs' rust implementation of UltraHonk by comparing with the paper and other implementations in C++ and solidity.
2. Developing a Soroban contract that can verify recursive UltraHonk proofs only locally due to the contract size limit.
3. (Optional) Write a CAP to support host-native BN254 elliptic curve library optimized for Soroban's WASM environment based on arkworks-rs/algebra.

We implemented a POC with basic elliptic curve operations using arkworks.
https://github.com/ModoriLabs/soroban-ultrahonk-verifier

Motivation

We considered building Honk with BLS12-381, but Honk requires a cycle of curves: BN254 and Grumpkin.

// Step 1: Split out the IPA proof from the main HONK proof
if constexpr (HasIPAAccumulator<Flavor>) {
    const size_t HONK_PROOF_LENGTH = Flavor::NativeFlavor::PROOF_LENGTH_WITHOUT_PUB_INPUTS - IPA_PROOF_LENGTH;
    // [...]
    output.ipa_proof = StdlibProof<Builder>(proof.begin() + honk_proof_with_pub_inputs_length, proof.end());
    honk_proof = StdlibProof<Builder>(proof.begin(), proof.end() + honk_proof_with_pub_inputs_length);
} else {
    honk_proof = proof;
}

// Step 2: Verify the main circuit (BN254-based operations)
transcript = std::make_shared<Transcript>(honk_proof);
// [...]

// Step 3: Verify the polynomial commitments (Grumpkin-based operations)
if constexpr (HasIPAAccumulator<Flavor>) {
    using PublicIpaClaim = PublicInputComponent<OpeningClaim<grumpkin<Builder>>>;
    output.ipa_claim = PublicIpaClaim::reconstruct(verification_key->public_inputs,
                                                 verification_key->verification_key->ipa_claim_public_input_key);
}

https://github.com/AztecProtocol/barretenberg/blob/master/cpp/src/barretenberg/stdlib/honk_verifier/ultra_recursive_verifier.cpp#L63

BLS12-381 does not have a well-known cycle of curves, so we have decided to implement non-native BN254 and pairing operations to test the UltraHonk prover on Soroban's local network.
Our strategy has two phases:

1. First, develop a pure no_std Rust implementation of BN254 and its pairing operation.
   1. Comparison to Ethereum: Soroban's 128 KiB contract size limit is more generous than Ethereum's 24 KiB limit, which should allow Soroban contracts to contain the verifier WASM even with non-native elliptic curve operations.
2. Second, propose native BN254 support through the Stellar CAP process for optimal performance.

Methodology

1. Theoretical research

UltraHonk is a combination of sumcheck and shplemini, and shplemini consists of Gemini and Shplonk.

SHPLONK is a more effective Plonk where k constraints at multiple points can be verified with just 2 pairings. It uses a variant of KZG commitment. This is unoptimized check of SHPLONK. I will explain the optimized process below.

Example of SHPLONK Section 4 ("Reducing Verifier Operations at the Expense of Proof Length")

Let's walk through a concrete example using the Section 4 scheme from the SHPLONK paper. This scheme reduces verifier operations (pairings) to only 2 pairings by adding an extra (G_1) element to the proof.

Problem Setup

• Polynomials:

  • $f_1(X) = X^2 + 1$
  • $f_2(X) = 2X + 3$

• Evaluation points:

  • $f_1$ at $z_1 = 5$ with claimed value $r_1 = f_1(5) = 26$
    • $r_1$ is a polynomial if you prove multiple points at $f_1$.
  • $f_2$ at $z_2 = 7$ with claimed value $r_2 = f_2(7) = 17$

Prover's Steps

1. Commit

$$ \text{cm}_1 = [f_1(\tau)]_1, \quad \text{cm}_2 = [f_2(\tau)]_1 $$

Let $\tau = 9$. $cm_1= [82]_1, cm_2 = [21]_1$.

2. Open

(a) Verifier sends random challenge $\gamma \in \mathbb{F}_p$

Let $\gamma = 3$

(b) Prover computes the combined polynomial

Let the evaluation set:

$$ T = {5,7}, \quad S_1 = {5}, \quad S_2 = {7} $$

The Lagrange denominators:

$$ Z_{T \setminus S_1}(X) = X-7, \quad Z_{T \setminus S_2}(X) = X-5 $$

The combined polynomial:

$$ f(X) = (X-7)(f_1(X)-26) + \gamma (X-5)(f_2(X)-17) $$

Substituting $\gamma = 3$,

$$ f(X) = (X - 7) \cdot (X - 5) \cdot (X + 11) $$

Compute:

$$ h(X) = \frac{f(X)}{Z_T(X)}, \quad \text{where} \quad Z_T(X) = (X-5)(X-7) $$

$h(X) = X + 11$, so $\left[h(X)\right]_1 = [h(\tau)]_1 = [20]_1$

(c) Sample a random evaluation point $z \in \mathbb{F}_p$

Let $z = 4$
Prover sends $W = [h(x)]_1 = [15]_1$

(d) Prover computes the quotient polynomial

$$ L(X) = \sum_{i=1}^{2} \gamma^{i-1} \cdot Z_{T \setminus S_i}(z) \cdot (f_i(X) - r_i(z)) - Z_T(z) \cdot h(X) $$

In our example, $L(X) = −3X^2 −9X + 84$.

Prover sends:

$$ W' = \left[\frac{L(X)}{X - z}\right]_1 = \left[\frac{−3X^2−9X+84}{X-4}\right]_1 = \left[-3X-21\right]_1 $$

Verify (only 2 pairings)

Verifier computes:

Verifier checks the pairing equation:

$$ e(F + z W', [1]_2) = e(W', [x]_2) $$

This is an optimization of this equation to fix the trusted setup of $\mathbb{F}_2$.

$$ e(F,[1]_2) = e(W',[x−z]_2) $$

In our example, the left hand side is the equation of these three: (1) - (2) - (3).

1. The sum over commitments: $\sum_{i=1}^{2} \gamma^{i-1} Z_{T \setminus S_i}(z) \cdot \text{cm}_i$
   In our example, the calculation goes as below:

   • 
   • $= 1 \cdot (-3) \cdot [82]_1 + 3 \cdot (-1) \cdot [21]_1$
   • $= [-246]_1 + [-63]_1 = [-309]_1$

2. The sum over claimed evaluations:

$$ \begin{aligned} \sum_{i=1}^{2} \gamma^{i-1} Z_{T \setminus S_i}(z) r_i(z) &= \gamma^0 \cdot (-3) \cdot 26 + \gamma^1 \cdot (-1) \cdot 17 \\ &= (-3) \cdot 26 + 3 \cdot (-1) \cdot 17 \\ &= -78 -51 = -129 \end{aligned} $$

3. The $Z_T(z) W$ term:

$$ Z_T(4) \cdot W = 3 \cdot [20]_1 = [60]_1 $$

The right hand side is

$$ e(\left[-3X - 21\right]_1 \cdot [X-4]_1, [1]_2) $$

Because $\tau$ = 9, it is $e([-240]_1, [1]_2)$ equal to the left hand side.

https://eprint.iacr.org/2020/081.pdf
https://hackmd.io/@walpo/shplonk

Gemini is a zero-knowledge proof system that is:

• Elastic: It allows the prover to trade off between time and space (memory) usage.
• FFT-free: Unlike many SNARKs (e.g., Groth16, PLONK) that rely on Fast Fourier Transforms (FFT) for polynomial operations, Gemini avoids FFTs, which can be a bottleneck or hard to implement in some environments.

Especially, UltraHonk uses the method to convert a multivariate PCS to a univariate PCS. This is useful when we can random linearly combine the KZG proof with other KZG proofs.

Let $f: {0,1}^n \rightarrow \mathbb{F}$ be a multilinear polynomial over n variables.
The univariatization map $\mathcal{U}_n$​ sends f to a univariate polynomial $\hat f(X) \in \mathbb{F}[X]$ of degree < $2^n$, defined as:

where:

• $\mathbf{i} = (i_0, \dots, i_{n-1}) \in {0,1}^n$
• $\text{bin}(\mathbf{i}) = i_0 + 2i_1 + 4i_2 + \cdots + 2^{n-1} i_{n-1}​$

Here is an example.
Suppose

• $g(x_0, x_1) = 1\cdot(1-x_0)(1-x_1) + 2x_0(1-x_1) + 3(1-x_0)x_1 + 4 x_0x_1$
• $\rho = (\rho_0, \rho_1) = (5, 6)$

I want to prove that $g(\rho) = 1 \cdot (1-5) \cdot (1-6) + 2 \cdot 5 \cdot (1-6) + 3 \cdot (1-5) \cdot 6 + 4 \cdot 5 \cdot 6 = 20 - 50 - 72 + 120 = 18$
Let $f(x) := \mathcal{U}_n(g)(x) = 1 + 2x + 3x^2 + 4x^3$

Through 2 foldings with $\rho_0, \rho_1$,
$f^{(i)}(x^2) = (1- \rho_{i-1})f_{even}(x) + \rho_{i-1} \cdot f_{odd}(x) = (1- \rho_{i-1})\frac{f^{(i-1)}(x) - f^{(i-1)}(-x)}{2} + \rho_{i-1} \cdot \frac{f^{(i-1)}(x) - f^{(i-1)}(x)}{2x}$

$f^{(1)}(x) = (1-\rho_0)(1 + 3x) + \rho_0(2+4x)= -4(1+3x) + 5(2+4x) = -4 -12x + 10 + 20x = 6 + 8x$

$f^{(2)}(x) = (1-\rho_1) \cdot 6 + \rho_1 \cdot 8 = -30 + 48 = 18$

This matches with the $g(\rho)$.

https://eprint.iacr.org/2022/420
https://github.com/arkworks-rs/gemini

2. Code review

Before adopting the codebase, we review each repo to ensure it has implemented the paper correctly.

• Verify TACEO's prover and verifier code is consistent with Barretenberg's Solidity verifier code
• Check for common security errors, such as missing inputs in transcripts for Fiat-Shamir transforms

Let's grasp the prover logic to make a safe verifier. In this explanation, I will skip zero-knowledgeness.

1. sumcheck reduces the circuit constraints check into a multivariate single point evalution.
2. gemini_prove transforms the multilinear function evaluation check to a batch evaluation check of univariate functions.
3. shplonk_prove proves it with k+1 pairings. In our code, k = 1.
   https://github.com/TaceoLabs/co-snarks/blob/main/co-noir/ultrahonk/src/decider/shplemini/prover.rs#L419

Sumcheck

$$ \sum\limits_{x\in{0,1}^m} GS(x) · [\sum_{j} α_j · R_j(x)] = 0 $$

Notation

• Let m = number of variables and n = 2^m.
• GS(x): gate separators for an input x.
• R_j: the j-th relation polyanoimal

Purpose

1. The sum-check protocol proves that the circuit's constraints are satisfied by showing their sum over a boolean hypercube equals 0.
2. It reduces verification from summing all $2^m$ assignments to a single point evaluation: $P(r_1, r_2, ..., r_m) = v$.

Relation separator $\alpha$
$\alpha$ prevents relation R_1 errors from cancelling R_2 errors.

Gate separators
In round i, let the round challenge of sum-check $u_i$.
The code is F::ONE + (round_challenge * (self.betas[self.current_element_idx] - F::ONE)) equal to $1 + u_i * (\beta_i - 1) = (1 - u_i) + u_i * \beta_i$.
Every input gate has $\prod_\limits{i={0\ldots d-1}} (1-u_i) + u_i \cdot \beta_i$ as its gate_separator.

1. If $u_i = 0$, it is 1.
2. If $u_i = 1$, it is $\beta_i$.

Example

1. GS(0,0) = (1-0)(1-0) = 1
2. GS(0,1) = $(1-0)(\beta_1) = \beta_1$
3. GS(1,0) = $(\beta_0)(1-0) = \beta_0$
4. GS(1,1) = $(\beta_0)(\beta_1) = \beta_0 \beta_1$

Every input gate has a different gate_separator. $GS(x)$ prevents input (0,0) errors from cancelling input (0,1) errors.

gemini_prove

1. Takes the multivariate challenge point $(r_1, r_2, ..., r_m)$ from the sumcheck output
2. Computes partially evaluated batched polynomials
   1. $F(X) = \sum_{i=0}^{m-1} \rho^i \cdot f_i(X)$
      1. $f_i(X)$ are the individual unshifted polynomials
      2. $m$ is the number of unshifted polynomials
      3. $\rho$ is the batching challenge
   2. $G(X) = \sum_{j=0}^{l-1} \rho^{m+j} \cdot g_j(X)$
      1. $g_j(X)$ are the individual to-be-shifted polynomials. These are witness polynomials that need to be evaluated at the next row, e.g. copy constraints.
   3. $A_{0}(X)=F(X)+G^{\curvearrowleft}(X)=F(X)+\frac{G(X)}{X}$
3. compute_fold_polynomials performs polynomial folding to create multiple fold polynomials $(A_{1}, A_{2}, ..., A_{l-1})$
   1. fold(A_l)[j] = (1-u_l) * even(A_l)[j] + u_l * odd(A_l)[j]
4. Commits to these fold polynomials
5. Obtains a challenge r from the transcript
6. construct_univariate_opening_claims evaluates polynomials at specific challenge points:
   1. For the initial polynomials: $A_{0,+}$ at point $r$ and $A_{0,-}$ at point $-r$
   2. For the fold polynomials: $A_l$ at points $-r^{2^l}$ for $l = 1, ..., d-1$
   3. Returns evaluation claims: $A_{0,+}(r)$, $A_{0,-}(-r)$, and $A_l(−r^{2ˡ})$ for $l = 1, ..., d-1$
7. Returns a vector of opening claims for $A_{0,+}(r), A_{0,-}(-r)$, and $A_l(−r^{2ˡ})$ for $l = 1, ..., d-1$.

shplonk_prove

1. Takes the opening claims generated by Gemini.
2. Challenge Generation: $\nu$
3. Compute gemini fold polymomials.
   1. Each fold polynomial needs to be evaluated at both positive $r^{2^i}$ and negative $-r^{2^i}$ evaluation points: $A_l(-r^{2^l}), A_l(r^{2^l})$
   2. $A_l(r^{2ˡ})$ for $l = 1, ..., d-1$ is calculated in compute_gemini_fold_pos_evaluations .
      1. $A_l(r^{2^d})$ is the result of folding d times, in other words, the batched polynomial evaluation at the multivariate challenge u from the sumcheck.
      2. From l = CONST_PROOF_SIZE_LOG_N to 1, calculate $A_{l-1}(r^{2^{l-1}})$.

$$ A_{l-1}(r^{2^{l-1}}) = \frac{2 \cdot r^{2^{l-1}} \cdot A_l(r^{2^l}) - A_{l-1}(-r^{2^{l-1}}) \cdot (r^{2^{l-1}} \cdot (1-u_{l-1}) - u_{l-1})}{r^{2^{l-1}} \cdot (1-u_{l-1}) + u_{l-1}} $$

4. Compute the batched quotient: $$Q(X) = \frac{A_{0,+}(X) - A_{0,+}(r)}{X - r} + \nu \cdot \frac{A_{0,-}(X) - A_{0,-}(-r)}{X - (-r)} + \sum_{l=1}^{\log n - 1} \left(\nu^{2l} \cdot \frac{A_l(X) - A_l(-r^{2^l})}{X - (-r^{2^l})} + \nu^{2l+1} \cdot \frac{A_l(X) - A_l(r^{2^l})}{X - r^{2^l}}\right)$$
5. Commit the batched quotient and get a challenge z.
6. Partial Evaluation:
   1. Compute a new polynomial $G(X)$ such that $G(z) = 0$:
   2. This effectively subtracts from $Q(X)$ the value it would have when evaluated at $z$.
   3. Return $G(X)$ as the final polynomial to be opened at point $z$ with claimed value 0.
7. Open $G(X)$ at x=z by sending $W[(\tau)]_1$.
   1. https://github.com/TaceoLabs/co-snarks/blob/main/co-noir/ultrahonk/src/decider/prover.rs#L109
   2. This KZG proof verification requires 2 pairings.
      1. The trusted setup for KZG is here: barretenberg/trusted_setup.md at master · AztecProtocol/barretenberg · GitHub
      2. The verifier will check $e([G(\tau) - G(z)]_1, [1]_2) = e([W(\tau)]_1, [\tau-z]_2)$
         1. Let $[G(\tau)]_1$ is the commitment of G(x).
         2. Let $W(x) = \frac{G(\tau) - G(z)}{\tau - z}$. In our case, G(z) = 0.
         3. This can be rewritten using bilinearity as:
            1. $e([G(\tau) - G(z)]_1, [1]_2) = e([W(\tau)]_1, [\tau]_2) \cdot e([W(\tau)]_1, -z[1]_2)$
            2. $e([G(\tau) - G(z)]_1, [1]_2) = e([W(\tau)]_1, [\tau]_2) \cdot e(-z W(\tau)]_1, [1]_2)$
            3. $e([G(\tau) - G(z)]_1 + z [W(\tau)]_1, [1]_2) \cdot e(-[W(\tau)]_1, [\tau]_2) = 1 \text{ in } {\mathbb{G}_T}$
            4. Since G(z) = 0, $e([G(\tau)]_1 + z [W(\tau)]_1, [1]_2) \cdot e(-[W(\tau)]_1, [\tau]_2) = 1 \text{ in } {\mathbb{G}_T}$
               1. This is the verification in https://github.com/TaceoLabs/co-snarks/blob/main/co-noir/ultrahonk/src/decider/verifier.rs#L133-L138.
               2. (1,2) is g1 in the trusted setup. so we scalar multiply (1,2) by $G(\tau) - G(z)$ to make $[G(\tau) - G(z)]_1$.
                  1. https://github.com/AztecProtocol/barretenberg/blob/master/sol/src/honk/BaseHonkVerifier.sol#L392-L393

3-1. Implement UltraHonk verifier: Sumcheck and shplemini

There are many implementations of UltraHonk. Follow this with no_std.

• rust: https://github.com/TaceoLabs/co-snarks/tree/main/co-noir/ultrahonk
• solidity: https://github.com/AztecProtocol/aztec-packages/tree/master/barretenberg/sol/src/honk

verifySumcheck

1. In the Sumcheck protocol, the prover sends a univariate polynomial in each round.
2. This polynomial has degree 7, so the prover sends 8 points at each round. The x coordinates are pre-determined.
   1. proof.sumcheckUnivariates[round][0] is the value evaluated at x=0.
   2. proof.sumcheckUnivariates[round][1] is the value evaluated at x=1.
   3. At each round, the verifier checks roundTarget == proof.sumcheckUnivariates[round][0] + proof.sumcheckUnivariates[round][1] .
3. Evaluate the given univariate at a point u (challenge).
4. At the last round, roundTarget must be equal to grandHonkRelationSum which a verifier can calculate.

$$\sum_{i=0}^{n-1} \alpha_i \cdot R_i(u_0, u_1, \ldots, u_{m-1}) \cdot \prod_{j=0}^{m-1} ((1-u_j) + u_j \cdot B_j)$$

• u_i is a sumcheck challenge.
• B_j is a gate challenge.
• alpha is a random value to random-linearly combine the constraints of the gates.
• R_i is a gate constraint.

Reference: https://github.com/AztecProtocol/barretenberg/blob/master/sol/src/honk/BaseHonkVerifier.sol#L124

function computeNextTargetSum

Say the round univariate as p(x).
We set the evaluation domain as {0,1,2,3,4,5,6,7}.
$w_j = \frac{1}{\displaystyle\prod_{k \ne j} (x_j - x_k)}, \quad j = 0, \ldots, n$
Therefore, it is pre-calculated as [-5040, 720, -240, 144, -144, 240, -720, 5040].
This is the inverse of $w_j$.
For example w_0 = 1/(0-1)(0-2)...(0-7) = -1/5040.

We put x = round_challenge in the p(x) below to calculate the target sum.

$$ p(x) = \frac{ \displaystyle\sum_{j=0}^{n} \frac{w_j}{x - x_j} f_j }{ \displaystyle\sum_{j=0}^{n} \frac{w_j}{x - x_j} } $$

This function returns p(roundChallenge) * B(roundChallenge) where $B(x) = \displaystyle\sum_{j=0}^{n} \frac{w_j}{x - x_j}$.
It is a modified Barycentric intepolation to avoid division.

3-2. Implement UltraHonk verifier: Custom gates

UltraHonk consists of the following custom gates:

1. arithmetic constraints
2. copy constraints
3. logup-derivative lookup argument
   1. https://eprint.iacr.org/2022/1530
4. Elliptic curve
5. Poseidon
   1. external
   2. internal
6. Offline memory checking
   1. ROM consistency check
   2. RAM Consistency Check
   3. RAM Timestamp Consistency Check
   4. The complete RAM/ROM memory identity

This is a part of our ongoing review of custom gates.

AllEntities

pub(crate) struct AllEntities<T: Default> {
    pub(crate) witness: WitnessEntities<T>,
    pub(crate) precomputed: PrecomputedEntities<T>,
    pub(crate) shifted_witness: ShiftedWitnessEntities<T>,
}

• witness is the current row entities.
• shifted_witness is the next row entities.
  https://github.com/TaceoLabs/co-snarks/blob/main/co-noir/ultrahonk/src/types.rs#L45-L49

There are precomputed columns which depend only on the circuit structure, not on the inputs.

• id_i: uniquely identifies each "location" in the constraint system.
• sigma_i : for copy constraints
• lagrange_first: A polynomial that equals 1 at the first row and 0 elsewhere.
• lagrange_last: A polynomial that equals 1 at the last row and 0 elsewhere.
• q_m, q_l, q_r, q_o, q_c: coefficients for the arithmetic gates
• q_lookup: a selector for lookup gates.
• table_i: precomputed lookup tables

arithmetic constraints
$w_{1\omega},w_{4\omega}$ mean the next row entities. It is shifted_witness in co-snarks implementation.
$$q_{arith} \cdot \left( \left( \frac{-1}{2} \cdot (q_{arith} - 3) \cdot q_m \cdot w_1 \cdot w_2 + q_1 \cdot w_1 + q_2 \cdot w_2 + q_3 \cdot w_3 + q_4 \cdot w_4 + q_c \right) + (q_{arith} - 1) \cdot \left( \alpha \cdot (q_{arith} - 2) \cdot (w_1 + w_4 - w_{1\omega} + q_m) + w_{4\omega} \right) \right) = 0$$
q_arith = 0 : Entire gate is disabled.

We can split the two halves.

The first half

$$ \left( \frac{-1}{2} \cdot (q_{arith} - 3) \cdot q_m \cdot w_1 \cdot w_2 + q_1 \cdot w_1 + q_2 \cdot w_2 + q_3 \cdot w_3 + q_4 \cdot w_4 + q_c \right) = 0 $$

1. q_arith = 1: $(-1/2) \cdot (q_{arith} - 3) = 1$ makes the standard PLONK equation.
2. q_arith = 2: The multiplication term is scaled by -1/2.
3. q_arith = 3: The multiplication term is completely disabled.
4. q_arith > 3: The Multiplication term is scaled by $-1/2 \cdot (q_{arith} - 3)$.

The second half

$$ (q_{arith} - 1) \cdot \left( \alpha \cdot (q_{arith} - 2) \cdot (w_1 + w_4 - w_{1\omega} + q_m) + w_{4\omega} \right)) = 0 $$

https://github.com/TaceoLabs/co-snarks/blob/main/co-noir/ultrahonk/src/decider/relations/ultra_arithmetic_relation.rs

permutation relations
Our barycentric interpolation does not use FFT, so the domain for interpolation is [0..domain_size]. It means the next row is accessible by z_perm(X+1) in the constraints.

$z_{perm}(0) = 1$
$$z_{perm}(X + 1) \cdot \prod_{i=1}^4 (\sigma_i(X) \cdot \beta + w_i(X) + \gamma) = z_{perm}(X) \cdot \prod_{i=1}^4 (id_i(X) \cdot \beta + w_i(X) + \gamma)$$

delta range relations
This gate checks the difference between two wires are in [0,1,2,3].

We will continue reviewing other constraint gates.

4. Implement BN254 with no_std (Optional)

Integrate BN254 as a host-native functions in rs-soroban-sdk using the arkworks bn254 implementation. This is a brief overview of the necessary functions.

BN curve is an elliptic curve of the form $y^2 = x^3 + b$ over $F_p$ where

• $p = 36x^4 + 36x^3 + 24x^2 + 6x + 1$
• $r = 36x^4 + 36x^3 + 18x^2 + 6x + 1$
• $t = 6 x^2 + 1$
• The parameter x is chosen so that p and r are prime and t is the trace of Frobenius of the curve, t = q + 1 − |E(F)|.

Elliptic curve operations

1. G_1 is $y^2 = x^3 + 3$ over a finite field F_p where the prime p is 254-bit number.
2. G_2 is sextic twist over $F_{p^2}$, $y'^2 = x'^3 + 3/(9+u)$.
   1. A twist of E: $y^2 = x^3 + ax + b$ is given by $E': y^2 = x^3 + a\omega^4x + b\omega^6$, with $\Psi: E' \rightarrow E: (x', y') \mapsto \left(\frac{x'}{\omega^2}, \frac{y'}{\omega^3}\right)$, $\omega \in \mathbb{F}_{q^k}$
   2. Sextic twists are only available when a = 0, so BN254 uses this.
3. Implement affine coordinates and projective coordinates.
   1. Jacobian coordinates are not necessary for this project.
   2. point addition, doubling, and negation.
   3. Keep the interface of bls12_381 in soroban-sdk.

Finite field operations

• A base field $F_p$
• Extension fields $F_{p^2}$, $F_{p^6}$, $F_{p^{12}}$

Subgroup check
If p does not divide r, then E[r] has the structure of $Z_r × Z_r$, so there are (r+1) subgroups of size r. Among them, we choose:

1. $\mathbb{G}_1[r] := E[r] \cap ker(π−[1])$
   1. If $\mathbb{F}$ is a prime field, the Frobenius endomorphism acts as the identity map due to Fermat's little theorem.
2. $\mathbb{G}_2[r] := E[r] \cap ker⁡(π−[p])$. This is the set of points $P \in E$ such that $\pi(P) = [p]P$.

G_1 subgroup check

1. Since $|G_1| = |E(F_p)|$, $P \in E(F_p)$ is enough.

G_2 subgroup check is to confirm $P \in E(F_p^k)$ is in the r-torsion group, so $r[P] = O$. Instead of calculating $r[P]$, we will check $\psi(P) = [6x^2]P$.

Proof of the equivalence.

1. The base field is $\mathbb{F}_p$.
2. $E[r]$ is r-torsion group. $E[r] = {P \in E : [r]P = \mathcal{O}}.$
3. In BN254, $|E'(\mathbb{F}_{p^2})| = c_2r$, and $c_2 \neq 1$.
4. Def. Embedding degree k is the smallest positive integer such that $E[r] \subset E(\mathbb{F}_{q^k})$.

Suppose $[r]P = O$.

1. BN curves satisfies r = p - t + 1, so $[r]P = O$ is equivalent to $[p]P = [t - 1]P$.
2. We will use untwist-Frobenius-twist endomorphism $\psi := (x,y) \mapsto (x^p \cdot (u ^{(p-1)/3}), y^p \cdot (u ^ {(p-1)/2)})$:
   1. untwist $\Psi: E' \rightarrow E$
   2. Apply the Frobenius endomorphism $\phi_p := (x, y) \mapsto (x^p, y^p)$
   3. twist $\Psi^{-1}: E \rightarrow E'$
3. $\psi$ satisfies the characteristic polynomial of the Frobenius operator, $\psi^2 - [t]\psi + [p] = O$.
4. $\psi^2(P) - [t]\psi(P) + [p]P = O$ is equivalent to $\psi^2(P) - [t]\psi(P) + [t-1]P = O$, so it is factored into $(\psi - [1])(\psi - [t - 1])(P) = O$.
5. Since the intersection of $\Psi(E'(\mathbb F_{p^2})) \cap E(\mathbb F_p)[r] = {O}$, $\psi(P) = [t-1]P$ holds.

Suppose $\psi(P) = [t-1]P$ holds.

1. From the characteristic polynomial of Frobenius, we know: $\psi^2(P) - [t]\psi(P) + [p]P = O$.
2. Substitute $\psi(P) = [t-1]P$ into this equation: $\psi([t-1]P) - [t][t-1]P + [p]P$ = O.
3. $[(t-1)^2]P - [t][t-1]P + [p]P$ = O.
4. $[-t + 1 + p]P = O$.
5. $[r]P = O$.

Pairing

The optimal Ate pairing e: G_1 × G_2 → G_T over the BN254 curve

1. Miller Loop
2. Final Exponentiation

Soroban

• Represent big numbers with native data types like u128 and u64 in Stellar.
• Use native data structures: Vec, BytesN
• All contracts should begin with #![no_std]. The size of Rust standard library is too big to put in a contract.

Timelines and Deliverables

Period	Task Description
Weeks 1–4	Review related papers and existing implementations
Weeks 5–10	Implement a Soroban verifier contract using the BN254 library from Arkworks
Weeks 11–14	Deploy and test the verifier locally
Weeks 15–18	Build Noir circuits (both simple and recursive), generate proofs using bb prove, and verify
Weeks 19–20	Write documentation detailing the verifier design, usage, and testing process
Weeks 21–24 (Optional)	Implement host-native BN254 operations and submit a CAP (Contract Authorization Proposal)
Weeks 25–28 (Optional)	Deploy and test on a forked Soroban node with native support

Team

ModoriLabs has developed semaphore.nr and integrated noir circuits in Pluto’s Web prover based on Supernova folding scheme. qpzm and teddav are also zk auditors in Electisec.

• @qpzm [email protected]
• @KyoungWan [email protected]
• @teddav ZK engineer. His recent work focuses on Noir-based real-world applications, including zk-tenant, a privacy-preserving identity verification system for apartment rentals, and co-match, a ZK dating app that matches users without exposing their sensitive profile data.
• @0xKarl98 [email protected]

Start Date

June 2025

Reference

• https://github.com/arkworks-rs/algebra/tree/master/curves/bn254
• https://hackmd.io/@Wimet/ry7z1Xj-2

[jayz22]

Hi @qpzm, I'm Jay from the core team at Stellar. Thanks for the proposal and detailed methodology description.
Just want to mention a few points regarding Soroban's curve support, which hopefully can help guiding your proposal (what @tomerweller mentioned in another thread):

• Soroban smart contracts are designed to be able to easily integrate 3rd party libraries. As shown in this example, you can import ark_bn254 in a contract and perform computation. Even though it won't fit into computation budget, this approach allows you to build up and test your project end-to-end, as if bn254 is natively supported.
• Eventually we would like to provide native support for bn254 by adding a suite of host functions (equivalent of precompiles, similar to this for BLS12-381). This process takes longer and requires more experience with Soroban, but we are open to taking contributions.
• We would like the UltraHonk verifier itself (mathematical correctness, code quality etc) to be the main focus, with goal of enabling the Noir ecosystem to build on Soroban. Building a new curves library from scratch in the contract would not be a worthy pursuit (the two options above are better alternatives).

Happy to answer any questions!

[qpzm]

@jayz22 Thank you for your suggestion. As you said, I updated the plan as follows:

1. Implement the Ultrahonk verifier using the arkworks' implementation of bn254. This is the main target of this grant, so we are focusing on the contract security through paper and code review.
2. Write a CAP for the host-native bn254. This will be decided through the discussion with Stellar foundation.

[qpzm]

@Savio-Sou There is a question reviewing the barrentenberg code.
https://discord.com/channels/1113924620781883405/1375742498709704735/1375742498709704735

In verifySumcheck, RelationsLib.accumulateRelationEvaluations inputs powPartialEvaluation as domainSep.
https://github.com/AztecProtocol/barretenberg/blob/master/sol/src/honk/BaseHonkVerifier.sol#L142-L144
Then, domainSep is multiplied in accumulateArithmeticRelation.
https://github.com/AztecProtocol/barretenberg/blob/master/sol/src/honk/Relations.sol#L72-L73
The same value is multiplied in accumulatePermutationRelation.
https://github.com/AztecProtocol/barretenberg/blob/master/sol/src/honk/Relations.sol#L122-L123
In fact, alpha is used for the random linear combination, so the purpose of domainSep (which is the same with powPartialEvaluation) is uncertain for me 😯.
https://github.com/AztecProtocol/barretenberg/blob/master/sol/src/honk/Relations.sol#L39

[qpzm]

In addition, the purpose of shifted columns is to access the next row: for example, we need Z_PERM_SHIFT in the permutation argument.
$f(\omega X)$ is the way to access the next row in Plonk, but it seems different in Ultrahonk as below. Are there any documentations for this?

 * So we define
 *  - A₀₊(X) = F(X) + G(X)/r
 *  - A₀₋(X) = F(X) − G(X)/r

https://github.com/AztecProtocol/barretenberg/blob/master/cpp/src/barretenberg/commitment_schemes/gemini/gemini_impl.hpp#L40-L42

[qpzm]

I found the answer for the second question.

If a polynomial $\hat g$ is represented by coefficients $(a_0, \ldots, a_{N-1})$, then its shift(left-shift-by-one) $\hat h$ is given by $(a_1, \ldots,a_{N-1},a_0)$. Therefore, we have the identity $X \hat h = \hat g + a_0 - a_0 X^N$.
If $a_0 = 0$, this reduces to simply $X \hat g = \hat g$.

https://hackmd.io/dlf9xEwhTQyE3hiGbq4FsA?view#Batched-ZeroMorph-with-Shifts

Also, a column of (1, 2, 3, 4) is interpolated to a multilinear polynomial $1 + 2 x_0 + 3 x_1 + 4 x_0 x_1$.
This is isomorphic to $1 + 2x + 3x^2 + 4 x^3$ according to the Zeromorph Section 2.5.

[qpzm]

In fact, alpha is used for the random linear combination, so the purpose of domainSep (which is the same with powPartialEvaluation) is uncertain for me 😯.
AztecProtocol/barretenberg@master/sol/src/honk/Relations.sol#L39

I found the answer for the first question and updated the proposal too.

Every input gate has an associated gate separator defined as

$$ \prod_{i=0}^{d-1} \left( (1 - u_i) + u_i \cdot \beta_i \right), $$

which we denote by $GS(x)$.

The role of $GS(x)$ is to prevent error terms corresponding to different inputs—such as $(0,0)$ and $(0,1)$ in 2-variate case—from cancelling each other out. It ensures that errors are isolated to their respective inputs.

Therefore, in the sumcheck protocol, we must multiply the gate separator $GS(x)$ for every input $x \in {0,1}^m$ in the outer sum:

$$ \sum\limits_{x\in{0,1}^m} GS(x) \cdot \left[ \sum_j \alpha_j \cdot R_j(x) \right] = 0. $$