ECIP: 1025 Title: Precompiled Contracts for zkSNARK Verification Author: Wei Tang <email@example.com> Status: Draft Type: Consensus (hard-fork) Created: 2017/06/29
Precompiled contracts for elliptic curve and pairing operations are required in order to perform zkSNARK verification within the block gas limit.
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).
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
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
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").
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
Input: two curve points
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.
Input: curve point and scalar
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.
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.
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
log_P(x) is the integer
n such that
n * P = x.
The precompiled contract is defined as follows, where the two groups
G_2 and their generators
P_2 are defined below (they have the same order
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.
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
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.
G_1 is a cyclic group on the above curve over the field
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583 with generator
P1 = (1, 2).
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 )
F_p are encoded as 32 byte big-endian numbers. An encoding value of
p or larger is invalid.
a * i + b of
F_p^2 are encoded as two elements of
Elliptic curve points are encoded as a Jacobian pair
(X, Y) where the point at infinity is encoded as
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.
suggest the following gas formula:
60000 * k + 40000
if we target 20000 gas per millisecond.
Awaiting benchmarks from other implementations.
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).
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.
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_2 are written additively,
G_T is written multiplicatively):
e(m * P1, n * P2) = e(P1, P2)^(m * n)
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)