DRAFT: Precompiled contracts for pairing function check #197
EIP: to be assigned Title: Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128 Author: Vitalik Buterin <email@example.com>, Christian Reitwiessner <firstname.lastname@example.org> Type: Standard Track Category(*only required for Standard Track): Core Status: Draft Created: 2017-02-06
Precompiled contracts for elliptic curve pairing operations are required in order to perform zkSNARK verification within the block gas limit.
This EIP suggests to add precompiled contracts for a pairing function on a specific pairing-friendly elliptic curve. This can in turn be combined with #196 to verify zkSNARKs in Ethereum smart contracts. The general benefit of zkSNARKs for Ethereum 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).
Current smart contract executions on Ethereum are fully transparent, which makes them unsuitable for several use-cases that involve private information like the location, identity or history of past transactions. The technology of zkSNARKs could be a solution to this problem. While the Ethereum Virtual Machine can make use of zkSNARKs in theory, they are currently too expensive
Note that fixing these parameters will in no way limit the use-cases for zkSNARKs, it will even allow for incorporating some advances in zkSNARK research without the need for a further hard fork.
Pairing functions can be used to perform a limited form of multiplicatively homomorphic operations, which are necessary for current zkSNARKs. This precompile can be used to run such computations within the block gas limit. This precompiled contract only specifies a certain check, and not an evaluation of a pairing function. The reason is that the codomain of a pairing function is a rather complex field which could provide encoding problems and all known uses of pairing function in zkSNARKs only require the specified check.
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
The precompiled contract is defined as follows, where the two groups
Definition of the groups
Elliptic curve points are encoded as a Jacobian pair
Note that the number
The length of the returned data is always exactly 32 bytes and encoded as a 32 byte big-endian number.
To be determined.
The specific curve
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 or does not admit an efficient pairing implementation.
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).
The encoding of field elements in
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.
To be written.
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
Now observe that
if and only if
Furthermore, the left hand side of this equation is equal to
And thus, the precompiled contract can be implemented by verifying that
Implementations are available here:
For the P2 generator, it would be useful to specify the modulus polynomial (ie. P such that P(x) = 0 in the field). If it's just x^2 + 1 = 0, then using i in place of x could help with clarity.
Also, we should specify edge case input behavior. I would recommend:
Another way to define the precompile would be to say: let DLOG be the discrete log modulo any point (in the G2 case, any point in the correct subgroup). Returns 1 iff DLOG(a1) * DLOG(b1) + DLOG(a2) * DLOG(b2) + ... = 0 (mod n). The fact that optimal ate pairings are used to do this is "just" an implementation detail.