EIP-3068 BN256 hash-to-curve precompile (Precompile for BN256 HashToCurve Algorithms)
No call decision · Security & privacy · EIP status Stagnant · created 2020-10-23
Adds a hash-to-curve operation as a precompile, which converts an arbitrary message into a point on the BN256 elliptic curve, enabling BLS signature verification in the EVM at a cost comparable to a single pairing check.
Why it is needed
Verifying a BLS signature requires a hash-to-curve operation that converts a message into a point on an elliptic curve, but the EVM currently has no dedicated precompile for this operation. Implementing it directly in Solidity costs about as much as a single pairing check, even though the actual computation involved is an order of magnitude smaller. EIP-198 and EIP-1108 lowered the cost of addition, scalar multiplication, and pairing checks on BN256, which also reduced the cost of distributed key generation (DKG) protocols such as ETHDKG, but there was still no way to verify the partial signatures or group signatures produced by a DKG on the EVM. The MapToGroup method from the original BLS paper is non-deterministic, making its computational cost unpredictable on the EVM, and it could be replaced once Fouque and Tibouchi presented a deterministic mapping method and proved it indistinguishable from a random oracle.
What changes
Today
- The EVM has no hash-to-curve precompile for BN256
- Implementing hash-to-curve in Solidity costs about as much gas as a pairing check
- There is no way to verify ETHDKG's partial signatures or group signatures on the EVM
After EIP-3068
- The HashToG1 and HashToG2 precompiles deterministically map a message to a point on the BN256 curve
- BLS signature verification cost drops to the level of a pairing check
- Group signatures and partial signatures produced via ETHDKG can be verified on the EVM
Who is affected
- Smart contract developers: BLS signature verification logic can be replaced with a cheap precompile call.
- DKG and threshold signature protocols (such as ETHDKG): Group signatures and partial signatures created off-chain can be verified on-chain.
- Client implementation teams: New precompiles HashToG1 and HashToG2, along with their gas calculation rules, must be added to the EVM.
In depth
HashToG1: map twice, then add
The HashToG1(msg) function feeds the message into HashToBase with two different domain separation parameter pairs (dsp1, dsp2): 0x00/0x01 and 0x02/0x03, producing two field elements. Each of these two elements is mapped via the BaseToG1 function to a point on the BN256 G1 curve, and the final HashToG1 result is the sum of the two points via elliptic curve addition (ECAdd).
HashToBase: producing a field element with Keccak256
HashToBase(msg, dsp1, dsp2) first prepends dsp1 to the message and hashes it with Keccak256, and separately prepends dsp2 and hashes it, obtaining each result as a uint256. The first hash result is multiplied by a constant equal to 2^256 mod the field's prime (fieldPrime), then the second hash result is added, and the sum is reduced modulo fieldPrime to return a single field element.
BaseToG1: from field element to curve point
BaseToG1(t) computes three candidate x values (x1, x2, x3) from t, based on the BN256 G1 curve equation y^2 = x^3 + curveB. It checks whether x1^3+curveB and x2^3+curveB are each a quadratic residue in the field (is_square), selects whichever of the three candidates actually lies on the curve using a constant-time comparison (ConstantTimeEquality), and computes y as a square root whose sign is determined by sign0(t). The operations inverse, is_square, and sqrt are all performed within the field, and this algorithm follows the deterministic mapping of Fouque and Tibouchi.
HashToG2 and cofactor clearing
HashToG2(msg) calls HashToBase four times with four different domain separators, dsp 0x04 through 0x0b, to produce two elements (fieldElement0, fieldElement1) in GF(fieldPrime^2). Each element is mapped via the BaseToTwist function to a point on BN256's twist curve, the two are summed with ECAdd, and finally ClearCofactor (an operation that multiplies by the cofactor using ECMul) is applied to narrow the result down to a point actually in the G2 group. BaseToTwist has the same structure as BaseToG1, applied to the twist curve equation y^2 = x^3 + curveBPrime.
Design rationale: reference papers and open choices
The BaseToG1 algorithm is based on the paper by Fouque and Tibouchi, with some modifications drawn from the paper by Wahby and Boneh, while HashToG2 follows the Wahby-Boneh paper. The hash function used in HashToBase (here Keccak256) and the construction of HashToBase itself are left as choices that could change. The text also notes that replacing the sign0 call used at the end of BaseToG1/BaseToTwist with is_square would make it exactly match the original deterministic mapping proven in the Fouque-Tibouchi paper, so that the proof of indistinguishability from a random oracle applies directly, but it states that it is not proven whether this property still holds when sign0 is used as is.
Gas cost estimates
The author estimated the cost of other operations based on measuring ECMul at 68 microseconds per operation on a local machine, with ECMul's current gas cost of 6000 as the reference. HashToG1 took 94 microseconds for a 32-byte message and 105 microseconds for 1024 bytes, giving an estimated gas cost of 8500 + len(bytes). HashToG2 took 886 microseconds for 32 bytes and 912 microseconds for 1024 bytes, giving an estimated gas cost of 80000 + 3*len(bytes). These figures are estimates not confirmed by test cases or an implementation.
Security Considerations: Lowered security strength of BN256
The author states that following research related to exTNFS, the 128-bit security level once guaranteed by the BN256 curve no longer holds, and conservative estimates put it at around 100 bits. The author says this is still out of reach for most attackers but warrants caution. This issue is also mentioned in the MadNet whitepaper, where MadNet partially mitigated it by additionally requiring a Secp256k1 signature for a partial group signature to be valid. The author discloses affiliation with MadHive and involvement in MadNet development and whitepaper authorship. The author also explains that this security concern with BN256 is common to all operations using pairing checks and is independent of this EIP.
Status: Stagnant, incomplete items
This EIP presupposes EIP-198 and EIP-1108, and the original document's Test Cases and Implementation sections are both left blank as TBD. The status is Stagnant, meaning the specification has stalled without being verified by tests or an implementation. There is no record in call notes of separate fork-inclusion discussion for this EIP.