ECIP 1025: Precompiled Contracts for zkSNARK Verification

Motivation

Precompiled contracts for elliptic curve and pairing operations are required in order to perform zkSNARK verification within the block gas limit.

Abstract

zkSNARK verification will allow anonymous transaction to be executed on the Ethereum Classic network. See this for how a simple mixer contract can be implemented using zkSNARK verification. This ECIP implements three primitive operations in order to perform zkSNARK verification. This allows changes of zkSNARK algorithms without requiring another hard fork.

The general benefit of zkSNARKs for Ethereum and Ethereum Classic is that it will increase the privacy for users (because of the Zero-Knowledge property) and might also be a scalability solution (because of the succinctness and efficient verifiability property).

This combines EIP-212 and EIP-213.

Specification for Addition and Scalar Multiplication on the Elliptic Curve alt_bn128

Add precompiled contracts for point addition (ADD) and scalar multiplication (MUL) on the elliptic curve “alt_bn128”.

Address of ADD: 0x6 Address for MUL: 0x7

The curve is defined by:

Y^2 = X^3 + 3
over the field F_p with
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583

Encoding

Field elements and scalars are encoded as 32 byte big-endian numbers. Curve points are encoded as two field elements (x, y), where the point at infinity is encoded as (0, 0).

Tuples of objects are encoded as their concatenation.

For both precompiled contracts, if the input is shorter than expected, it is assumed to be virtually padded with zeros at the end (i.e. compatible with the semantics of the CALLDATALOAD opcode). If the input is longer than expected, surplus bytes at the end are ignored.

The length of the returned data is always as specified (i.e. it is not “unpadded”).

Exact semantics

Invalid input: For both contracts, if any input point does not lie on the curve or any of the field elements (point coordinates) is equal or larger than the field modulus p, the contract fails. The scalar can be any number between 0 and 2**256-1.

ADD

Input: two curve points (x, y). Output: curve point x + y, where + is point addition on the elliptic curve alt_bn128 specified above. Fails on invalid input and consumes all gas provided.

MUL

Input: curve point and scalar (x, s). Output: curve point s * x, where * is the scalar multiplication on the elliptic curve alt_bn128 specified above. Fails on invalid input and consumes all gas.

Gas costs

To be determined.

Specification for Optimal Ate Pairing Check on the Elliptic Curve alt_bn128

Add a precompiled contracts for a bilinear function on groups on the elliptic curve “alt_bn128”. We will define the precompiled contract in terms of a discrete logarithm. The discrete logarithm is of course assumed to be hard to compute, but we will give an equivalent specification that makes use of elliptic curve pairing functions which can be efficiently computed below.

Address: 0x8

For a cyclic group G (written additively) of prime order q let log_P: G -> F_q be the discrete logarithm on this group with respect to a generator P, i.e. log_P(x) is the integer n such that n * P = x.

The precompiled contract is defined as follows, where the two groups G_1 and G_2 and their generators P_1 and P_2 are defined below (they have the same order q):

Input: (a1, b1, a2, b2, ..., ak, bk) from (G_1 x G_2)^k
Output: If the length of the input is incorrect or any of the inputs are not elements of
        the respective group or are not encoded correctly, the call fails.
        Otherwise, return one if
        log_P1(a1) * log_P2(b1) + ... + log_P1(ak) * log_P2(bk) = 0
        (in F_q) and zero else.

Note that k is determined from the length of the input. k == 0 is valid and results in returning one.

In order to check that an input is an element of G_1, verifying the encoding of the coordinates and checking that they satisfy the curve equation (or is the encoding of infinity) is sufficient. For G_2, in addition to that, the order of the element has to be checked to be equal to the group order q = 21888242871839275222246405745257275088548364400416034343698204186575808495617.

Definition of the groups

The groups G_1 and G_2 are cyclic groups of prime order q = 21888242871839275222246405745257275088548364400416034343698204186575808495617 on the elliptic curve alt_bn128 defined by the curve equation Y^2 = X^3 + 3.

The group G_1 is a cyclic group on the above curve over the field F_p with p = 21888242871839275222246405745257275088696311157297823662689037894645226208583 with generator P1 = (1, 2).

The group G_2 is a cyclic group on the same elliptic curve over a different field F_p^2 = F_p[i] / (i^2 + 1) (p is the same as above) with generator

P2 = (
  11559732032986387107991004021392285783925812861821192530917403151452391805634 * i +
  10857046999023057135944570762232829481370756359578518086990519993285655852781,
  4082367875863433681332203403145435568316851327593401208105741076214120093531 * i +
  8495653923123431417604973247489272438418190587263600148770280649306958101930
)

Encoding

Elements of F_p are encoded as 32 byte big-endian numbers. An encoding value of p or larger is invalid.

Elements a * i + b of F_p^2 are encoded as two elements of F_p, (a, b).

Elliptic curve points are encoded as a Jacobian pair (X, Y) where the point at infinity is encoded as (0, 0).

Note that the number k is derived from the input length.

The length of the returned data is always exactly 32 bytes and encoded as a 32 byte big-endian number.

Gas costs

Benchmarks run on cpp-ethereum

suggest the following gas formula:

60000 * k + 40000

if we target 20000 gas per millisecond.

Awaiting benchmarks from other implementations.

Rationale

The specific curve alt_bn128 was chosen because it is particularly well-suited for zkSNARKs, or, more specifically their verification building block of pairing functions. Furthermore, by choosing this curve, we can use synergy effects with ZCash and re-use some of their components and artifacts.

The feature of adding curve and field parameters to the inputs was considered but ultimately rejected since it complicates the specification: The gas costs are much harder to determine and it would be possible to call the contracts on something which is not an actual elliptic curve.

A non-compact point encoding was chosen since it still allows to perform some operations in the smart contract itself (inclusion of the full y coordinate) and two encoded points can be compared for equality (no third projective coordinate).

Backwards Compatibility

As with the introduction of any precompiled contract, contracts that already use the given addresses will change their semantics. Because of that, the addresses are taken from the “reserved range” below 256.

Implementation

Optional Ate Pairing Check

The precompiled contract can be implemented using elliptic curve pairing functions, more specifically, an optimal ate pairing on the alt_bn128 curve, which can be implemented efficiently. In order to see that, first note that a pairing function e: G_1 x G_2 -> G_T fulfills the following properties (G_1 and G_2 are written additively, G_T is written multiplicatively):

(1) e(m * P1, n * P2) = e(P1, P2)^(m * n) (2) e is non-degenerate

Now observe that

log_P1(a1) * log_P2(b1) + ... + log_P1(ak) * log_P2(bk) = 0

if and only if

e(P1, P2)^(log_P1(a1) * log_P2(b1) + ... + log_P1(ak) * log_P2(bk)) = e(P1, P2)

Furthermore, the left hand side of this equation is equal to

e(log_P1(a1) * P1, log_P2(b1) * P2) * ... * e(log_P1(ak) * P1, log_P2(bk) * P2)
= e(a1, b1) * ... * e(ak, bk)

And thus, the precompiled contract can be implemented by verifying that e(a1, b1) * ... * e(ak, bk) = e(P1, P2)