EIP-197 alt_bn128 pairing check precompile (Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128)

Final · EVM & execution · EIP status Final · created 2017-02-06

Adds a precompiled contract at address 0x8 that performs a pairing check on the elliptic curve alt_bn128. Combined with EIP-196, this enables zkSNARK proofs to be verified inside a smart contract within the block gas limit.

Why it is needed

Right now all Ethereum smart contract execution is public. Because who did what is fully visible, it is not suited to handling sensitive information such as location, identity, or past transaction history. zkSNARKs (zero knowledge succinct non interactive arguments of knowledge), a type of zero knowledge proof, can prove that something is true without revealing its content, which could be a solution to this problem. In theory the Ethereum Virtual Machine (EVM) can also verify zkSNARKs, but right now the cost is too high to fit within the block gas limit. So this proposal fixes the parameters of the basic operations needed for zkSNARKs in advance and provides them as dedicated contracts, making implementation more efficient and lowering gas costs. The original text explains that fixing the parameters does not limit the usefulness of zkSNARKs, and that it also allows some future zkSNARK research results to be adopted without an additional hard fork.

What changes

Today

After EIP-197

Who is affected

In depth

What is being checked: whether the sum of discrete logarithms is 0

For the input (a1, b1, a2, b2, ..., ak, bk), the precompile returns 1 if log_P1(a1) * log_P2(b1) + ... + log_P1(ak) * log_P2(bk) = 0 (in F_q) holds, and 0 otherwise. The call fails if the input length is wrong, if any input is not an element of the corresponding group, or if the encoding is incorrect. k is derived from the input as the input length divided by 192, and empty input is valid and returns 1. The original text also explains why the specification defines only this check rather than evaluation of the pairing function itself: the codomain of the pairing function is a complex field that could cause encoding issues, and every known use of zkSNARKs only needs this check.

Definition of the two groups G_1 and G_2

G_1 and G_2 are both cyclic groups of prime order q = 21888242871839275222246405745257275088548364400416034343698204186575808495617. G_1 is defined on the curve Y^2 = X^3 + 3 over the field F_p (p = 21888242871839275222246405745257275088696311157297823662689037894645226208583), with generator P1 = (1, 2). G_2 is defined on the curve Y^2 = X^3 + 3/(i+9) over the extension field F_p^2 = F_p[i] / (i^2 + 1), and the original text specifies the concrete coordinates of the generator P2. Checking membership in G_1 only requires confirming the coordinate encoding and the curve equation (or confirming the point at infinity encoding), but G_2 additionally requires checking that the element's order is q. The original text adds that since G_2 is the only group of order q on that curve, choosing a different generator would still yield the same group.

Encoding rule

An element of F_p is encoded as a 32 byte big endian number, and a value greater than or equal to p is invalid. An element a * i + b of F_p^2 is encoded as two F_p elements (a, b). This order was chosen to match the big endian encoding of the element itself. An elliptic curve point is encoded as a pair (X, Y), and the point at infinity is represented as (0, 0). Thus a G_1 point is 64 bytes and a G_2 point is 128 bytes, making each point pair 192 bytes. The return data length is always exactly 32 bytes, encoded as a 32 byte big endian number. An uncompressed point encoding was used because including the full y coordinate allows certain operations to be performed directly inside the contract, and because the absence of a third projective coordinate allows two encoded points to be compared directly.

Gas cost

The gas cost of the precompile is 80,000 * k + 100,000, where k is the number of point pairs, that is, the input length divided by 192. This structure splits the cost into a part proportional to input size and a fixed cost, so the cost increases linearly as the number of pairing terms to check grows. A generalized approach that would take the curve and field parameters as input was also considered but rejected, because it would complicate the specification, make it much harder to determine gas cost, and allow contracts to be called against targets that are not actual elliptic curves or that lack an efficient pairing implementation.

Implementation: equivalence with the optimal ate pairing

The spec is defined in terms of discrete logarithms, but the actual implementation uses the optimal ate pairing on the alt_bn128 curve, which can be computed efficiently. The pairing function e: G_1 x G_2 -> G_T satisfies bilinearity, e(m * P1, n * P2) = e(P1, P2)^(m * n), and non-degeneracy, so the condition that the sum of discrete logarithms equals 0 is equivalent to checking e(a1, b1) * ... * e(ak, bk) = 1. The original text names libff (C++), bn (Rust), and py_ecc's bn128_pairing (Python) as reference implementations.

Why the alt_bn128 curve

alt_bn128 was chosen because it fits particularly well with zkSNARKs, specifically the pairing function that is a core component of their verification. Choosing this curve also allows leveraging synergy with ZCash, reusing some of its components and outputs. The original Motivation section explains that the pairing function is used to perform the limited form of multiplicative homomorphic operation that current zkSNARKs require.

Activation timing and backwards compatibility

This precompile applies starting from blocks where block.number >= BYZANTIUM_FORK_BLKNUM. As is always the case when introducing a precompile, contracts already using that address will see a change in behavioral meaning, which is why the address was taken from the reserved range below 256. This EIP's status is Final, a finalized spec, and the original text's Test Cases section remains marked as to be written.

Original EIP · ← EIPs