EIP-196 alt_bn128 curve addition and multiplication precompile (Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128)
Final · EVM & execution · EIP status Final · created 2017-02-02
Adds precompiled contracts for elliptic curve (alt_bn128) point addition and scalar multiplication at addresses 0x6 and 0x7. These are the basic operations needed to make zkSNARK verification feasible within the block gas limit.
Why it is needed
Because Ethereum smart contract execution is fully public, it is not suited to handling private information such as location, identity, or past transaction history. zkSNARKs, a zero knowledge proof technology, can prove a computation is correct without revealing its content, which could solve this problem. The Ethereum Virtual Machine (EVM) can in theory handle zkSNARKs, but right now the computation cost is too high to fit within the block gas limit. So this EIP proposes fixing the parameters of a few basic operations that make up zkSNARKs in advance so clients can implement them efficiently and lower the gas cost. Fixing the parameters might seem to limit their usefulness, but the original text explains that these operations are basic enough to be flexibly combined, and can accommodate future zkSNARK research progress without requiring an additional hard fork.
What changes
Today
- All contract execution content is fully transparent and public, making it hard to build applications that handle private information
- Implementing zkSNARK verification purely in EVM code costs more than the block gas limit
- Addresses 0x6 and 0x7 have no defined functionality
After EIP-196
- Elliptic curve point addition (ADD) can be used directly at address 0x6, and scalar multiplication (MUL) at address 0x7
- Combined with the pairing check in EIP-197, zkSNARKs can be verified inside a smart contract
- The cost is fixed at 500 gas for ECADD and 40000 gas for ECMUL
Who is affected
- Users: The properties of zero knowledge proofs enable privacy preserving applications, and succinct proofs with efficient verification could also serve as a scalability solution.
- App and contract developers: Instead of writing curve operations directly in EVM code, a zkSNARK verification contract can be built by calling the two precompiles.
- Client teams: The two precompiles must be implemented starting from the Byzantium fork block, matching the original text's rules for handling invalid input and gas consumption.
- Existing contracts: Contracts already using these addresses will have their meaning changed, but the impact is limited because the addresses were chosen from the reserved region below 256.
In depth
The added precompiles and the curve definition
If block.number is greater than or equal to BYZANTIUM_FORK_BLKNUM, the elliptic curve alt_bn128 point addition (ADD) and scalar multiplication (MUL) precompiles are added. ADD is at address 0x6 and MUL is at address 0x7. The curve is defined by Y^2 = X^3 + 3, and the prime p of the field F_p is 21888242871839275222246405745257275088696311157297823662689037894645226208583.
Encoding rule
Field elements and scalars are encoded as 32 byte big endian numbers. A curve point is written as two field elements (x, y), and the point at infinity is written as (0, 0). Multiple objects are passed concatenated. If the input is shorter than expected it is treated as padded with zeros at the end, which is consistent with the semantics of the CALLDATALOAD instruction. If the input is longer than expected, the extra trailing bytes are ignored. The length of the return data always matches the specification exactly and is never shortened.
Exact semantics and failure conditions
Both contracts fail and consume all the gas provided if an input point is not on the curve, or if a field element used as a point coordinate is greater than or equal to p. A scalar, on the other hand, may be any number from 0 to 2**256-1. ADD takes two curve points (x, y) and returns the result x + y of point addition on alt_bn128. MUL takes a curve point and a scalar (x, s) and returns the result s * x of scalar multiplication. The test cases include items stating that a point which becomes valid only after reducing its coordinates mod p must fail, that empty input must succeed, and that scalar multiplication with a scalar larger than the order of the group or the order of the field must succeed.
Gas cost
The gas cost of ECADD is 500 and the gas cost of ECMUL is 40000. Because the curve and parameters are fixed, this cost can be set in advance. The original Rationale states that an approach taking the curve and field parameters as input was also considered, but was rejected because it would make determining gas cost much harder and would allow contracts to be called against something that is not an actual elliptic curve, complicating the specification.
Why alt_bn128
alt_bn128 was chosen because it is particularly well suited to zkSNARKs, specifically to the pairing function that is a core building block of their verification. Choosing this curve also lets the project leverage synergy with ZCash, reusing some of its components and outputs. An uncompressed point encoding was chosen because including the full y coordinate allows certain operations to be performed inside the contract, and because the absence of a third projective coordinate allows two encoded points to be compared directly for equality. The implementations mentioned are libff (C++), bn (Rust), and py_pairing (Python), and both codebases refer to this group as G1.
Backwards Compatibility and Status
Whenever any new precompile is introduced, it changes the meaning of any contract already using that address. For this reason the address was taken from the reserved region below 256. This EIP's status is Final, and as specified it is part of the Byzantium hard fork, taking effect from BYZANTIUM_FORK_BLKNUM. Combined with the pairing check in EIP-197, it enables zkSNARK verification in Ethereum smart contracts.