Cryptography Primitives

1. Pairing Groups on BN-254

Aztec uses the Ethereum-native version of the BN254 elliptic curve for its principal group:

First pairing source group

A BN curve of size $2^{254}$, with field size $2^{254}$, and security of roughly 110 bits (practically, this can be closer to 128 bits as the stronger attacks require unproven assumptions related to number field sive algorithms and have never been fully specified or implemented).

• Equation $E: X^2 = Y^3 + 3$
• Parameters
  • Field $\mathbb{F}_p$ for prime $p = 21888242871839275222246405745257275088696311157297823662689037894645226208583$ in decimal representation (size$\sim 2^{254}$)
  • Group $\mathbb{G}_1 = E / \mathbb{F}_p$ of prime order $r = 21888242871839275222246405745257275088548364400416034343698204186575808495617$ (size$\sim 2^{254}$)
  • Generator $P_1 = (1, 2) \in \mathbb{G}_1$

We have $2^{253}<r<p<2^{254}$. As usual, we use a subgroup of a twist of the above curve for efficient pairings:

Second pairing source group

A subgroup of size $\sim 2^{254}$, of a curve over field size $2^{254\times2}$. This is a degree-2 field extension of $\mathbb{F}_{q}$, via $\mathbb{F}_{q^2} = \mathbb{F}_{q}[X] / (X^2 + 1)$. Note that $(X^2 + 1)$ is the ideal generated by $f(X) = X^2 + 1$, whose roots are $±i$.

• Equation $E: X^2 = Y^3 + \frac{3}{(i+9)}$
• Parameters
  • Field $\mathbb{F}_{p^2}$ for $p$ as above.
  • Group $\mathbb{G}_2$ = subgroup of $E / \mathbb{F}_{p^2}$ of the same prime order $r$ as $\mathbb{G}_1$.
  • Generator $P_2 = ( 11559732032986387107991004021392285783925812861821192530917403151452391805634 * i + 10857046999023057135944570762232829481370756359578518086990519993285655852781, 4082367875863433681332203403145435568316851327593401208105741076214120093531 * i + 8495653923123431417604973247489272438418190587263600148770280649306958101930 ) \in \mathbb{G}_2$

Pairing

We use the Ethereum-native Ate pairing, a bilinear map taking:

$\epsilon: \mathbb{G}_1 \times \mathbb{G}_2 \longrightarrow \mathbb{G}_T$

Where $\mathbb{G}_T$ is a field extension of $\mathbb{F}_q$ of degree 12.

Further details may be found here.

2. Grumpkin - A curve on top of BN-254 for SNARK efficient group operations.

Grumpkin is in fact a curve cycle together with BN-254, meaning that the field and group order of Grumpkin are equal to the group and field order of (the first pairing group of) BN-254:

• Equation $E: Y^2 = X^3 -17$
• Parameters
  • Group $\mathbb{G}$ of order $p = 21888242871839275222246405745257275088696311157297823662689037894645226208583$
  • Base field $F_r$ for $r= 21888242871839275222246405745257275088548364400416034343698204186575808495617$

3. Hashes

The Aztec 2.0 system relies on two types of hashes:

• Pedersen Hashes (for collision resistance)
• Blake2 Hashes (for pseudorandomness)

Aztec relies overwhelmingly on Pedersen Hashes; as most of the time collision resistance is sufficient.

Pedersen Hashes

Let $\mathbb{G}$ be an additive group of prime order $p$.

In its classical setting a pedersen hash is defined as a map $H: \mathbb{F} \times \mathbb{F} \longrightarrow \mathbb{G}$ as follows:

$$H(m_1,m_2) = m_1.g + m_2.h$$

for generators $g,h \in \mathbb{G}$ chosen independently by public randomness (e.g. hueristically as distinct outputs of a random oracle simulating hash function).

We wish to define a variant of Pedersen to enable hashing strings of any desired length. As our group $\mathbb{G}$ we will use the Grumpkin curve group described above.

We generate a sequence of generators $h_0, ... h_k$ as hash outputs -- these are network parameters, fixed for the life of the protocol. They are simply chosen to be the first Keccak-256 outputs that correspond to group elements. See the derive_generators method in the barretenberg code and the Global Constants section below for exact details.

Hashing field elements

Our basic component for hashing will be the hash_single method. Given a field element $a\in F_r$ and hash index $i$, we essentially hash 252 bits of $a$ with $h_{2i}$ and the the remaining 2 bits of $a$ with $h_{2i+1}$. This is not precisely the case, as we use a wnaf representation - see page 4 here. See the comments above hash_single in the code for exact details. The point is that while enforcing the wnaf representation to represent an integer smaller than $r$, this is a collision resistant function from $F_r$ under DL, even when outputting only the $x$-coordinate.

Now, given a vector $a_1,\ldots,a_t\in F_r$ we define the pedersen hash as

$$H(a_1,\ldots,a_t)=\sum_{i=1}^t\text{hash single}(a_i,i).x$$

Hashing byte arrays:

Given a message $M$ of arbitrary size, we first divide it up into $31$-byte chunks $M = M_0 M_2 ... M_k$; in other words:

$$M = \sum_{i=0}^{k} M_i.2^{31\cdot i}.$$

We now identify each $M_i$ with a field element $a_i\in F_r$ in the natural way. and now we define $H(M)\triangleq H(a_1,\ldots,a_t)$

For details on how $h_i$ have been generated, please see Global Constants.

Blake2s Hash

We use the Blake2s Hash more sparingly, because it is not SNARK-friendly, but it does exhibit psuedorandomness not offered by Pedersen. That is, it is considered a reasonable hueristic to use it in place of a random oracle used for a security proof.

We employ the standard implementation of the Blake2s hash, which is fully documented here.

The Blake2s hash is utilized for computing nullifiers and for generating pseudorandom challenges, when verifying Schnorr signatures and when recursively verifying Plonk proofs.

Pedersen Hash 'h' Elements

There are additionally $\{h_i\} \subset \mathbb{G}_1$ elliptic curve group points used in the computation of Pedersen hashes.

For example:

1. $h_i, i>0$: used to compute hashes for large data strings with inputs of size $> 31 \text{ bytes}$
2. $h_0, h_1, h_2, h_3$ are used for all Pedersen Hashes in the Note Tree and Nullifier Tree

The generator algorithm for computing the $h_i$ in pseudocode is:

counter = 0
h = []

do
  {
    compute x = keccak256(pad(i)), pad(i) = 32-byte pad of i 
    find y = sqrt (x³ + ax + b))
    if y = error
      {
        \\ unsuccessful: point does not exist (50% chance)
      }
    else
      {
        \\ successful: point exists and add to list (50% chance)
        set h[counter] = (x, y)
      }
    counter = counter + 1
  }
while counter < 1024