--- # System prepended metadata title: BLS Signatures in Solidity --- # BLS Signatures in Solidity *Thank Onur, Jannik, and Mikerah for the review and the advice* published version https://ethresear.ch/t/bls-signatures-in-solidity/7919 [TOC] ## Who should read this? This article targets developers who want to perform BLS signature verification in Eth1 contracts. For readers interested in the BLS signature in Eth2, I highly recommend "BLS12-381 For The Rest Of Us"[^ben-bls] by Ben Edgington, which provides long but not too long answers to common questions. The article also assumes the readers heard of the terms like $G_1$, $G_2$, and pairings. "BLS12-381 For The Rest Of Us" is also a good source for understanding those. ## Introduction When we talk about the BLS signature, we are talking about the signature aggregation technique. The BLS here is the name of three authors Boneh, Lynn, and Shacham. [^bls] ## Which curve should I use? BLS signature aggregation works on pairing friendly curves. Ｗe have to choose which of the following curves to use. - alt_bn128: Barreto-Naehrig curve. [^bn] - BLS12-381: This BLS is Barreto, Lynn, and Scott. [^bls-curve] At the time of writing this document (2020-Aug), we can only use alt_bn128 curve in contracts. The alt_bn128 curve is specified in EIP-196[^eip196] (curve point addition and multiplication) and EIP-197[^eip197] (curve pairing) and introduced in Byzantium hardfork October 16, 2017[^byzantium-fork]. The cost is further reduced in EIP-1108[^eip1108], and was live on mainnet in Istanbul-fork[^istanbul-fork]. The BLS12-381 curve is specified in EIP-2537[^eip2537] and expected to go live in the Berlin hardfork[^eip2070]. The alt_bn128(BN256) is shown in 2016 to have less than 100-bits of security[^ietf]. To target 128-bits security use BLS12-381 whenever possible. We use alt_bn128 in the examples hereafter. ### alt_bn128, bn256, bn254, why so many names and so confusing? - Originally named alt_bn128 for targeting theoretic security at 128 bits. - It works on a 254 bit prime field, so people also call it bn254. - Some also call it bn256 for unknown reason. ## Notes on size of the elements | | alt_bn128 | BLS12-381 | Note | | ----------------------- | ------------------:| --------------------:| ------------------------------------ | | $F_q$ | 254 bits (32 bytes) | 381 bits (48 bytes) | has leading zero bits | | $F_{q^2}$ | 64 bytes | 96 bytes | | | $\Bbb G_1$ Uncompressed | 64 bytes | 96 bytes | has x and y coordinates as $F_q$ | | $\Bbb G_2$ Uncompressed | 128 bytes | 192 bytes | has x and y coordinates as $F_{q^2}$ | A curve point's y coordinate can be compressed to 1 bit and recovered by x. | | alt_bn128 | BLS12-381 | | --------------------- | ---------:| ---------:| | $\Bbb G_1$ compressed | 32 bytes | 48 bytes | | $\Bbb G_2$ compressed | 64 bytes | 96 bytes | ## Big Signatures or Big public keys? This is a decision you'll face in the project. Choose either: - Use $\Bbb G_2$ for signatures and messages, and $\Bbb G_1$ for public keys, or - Use $\Bbb G_2$ for public keys, and $\Bbb G_1$ for signatures and messages. $\Bbb G_2$ is 128 bytes (`uint256[4]` in Solidity) and $\Bbb G_1$ is 64 bytes (`uint256[2]` in Solidity). Also field/curve operations on $\Bbb G_2$ are more expensive. The option saves more gas in your project is better. We'll use the big public keys in the examples hereafter. ## BLS cheat sheet We have a curve. The points on the curve can form a subgroup. We define $\Bbb G_2$ to be the subgroup of points where the curve's x and y coordinates defined on $F_{q^2}$. And subgroup $\Bbb G_1$ with coordinates on $F_q$. ### Tips - **Field operations**: We are talking about arithmetics of field elements $F_q$ or $F_{q^2}$. $F_q$ can be added, subtracted, multiplied, and divided by other $F_q$. Same applies for $F_{q^2}$. - **Curve operations**: We are talking about operations of curve elements $\Bbb G_1$ or $\Bbb G_2$. An element in $\Bbb G_1$ can be added to another element in a geometrical way. An element can be added to itself multiple times, so we can define **multiplications** of an element in $\Bbb G_1$ with an integer in $Z_q$[^ecmul]. Same applies for $\Bbb G_2$. ### Pairing function $$ e:\Bbb G_1 \times \Bbb G_2 \to \Bbb G_T $$ $G_1$, $G_2$ are the generators of $\Bbb G_1$ and $\Bbb G_2$ respectively Pairing function has bilinear property, which means for $a, b \in Z_q$, $P \in \Bbb G_1$, and $Q \in \Bbb G_2$, we have: $$ e( a \times P, b \times Q) = e( ab \times P, Q) = e( P, ab \times Q) $$ ### Hash function It maps the message to an element of $\Bbb G_1$ $$ H_0: \mathcal{M} \to \Bbb G_1 $$ ### Key Generation Secret key: $$ \alpha \gets \Bbb Z_q $$ Public key: $$ h \gets \alpha \times G_2 \in \Bbb G_2 $$ ### Signing $$ \sigma \gets \alpha \times H_0(m) \in \Bbb G_1 $$ ### Verification $$ e(\sigma, G_2)\stackrel{?}{=} e(H_0(m), h) $$ ### Proof of why verification works $$ e(\sigma, G_2) \\ = e( \alpha \times H_0(m), G_2) \\ = e( H_0(m), \alpha \times G_2) \\ = e(H_0(m), h) $$ ## Contracts / Precompiles Developers usually work with a wrapped contract that has clear function names and function signatures. However, the core of the implementation could be confusing. Here we provide a simple walkthrough. ### Verify Single Below shows an example Solidity function that verifies a single signature. It is the small signature and big public key setup. A signature is a 64 bytes $\Bbb G_1$ group element, and its calldata is a length 2 array of uint256. On the other hand, a public key is a 128 bytes $\Bbb G_2$ group element, and its calldata is a length 4 array of uint256. EIP 197 defined a pairing precompile contract at address `0x8` and requires input to a multiple of 192. This assembly code calls the precompile contract at address `0x8` with inputs. ``` function verifySingle( uint256[2] memory signature, \\ small signature uint256[4] memory pubkey, \\ big public key: 96 bytes uint256[2] memory message ) internal view returns (bool) { uint256[12] memory input = [ signature[0], signature[1], nG2x1, nG2x0, nG2y1, nG2y0, message[0], message[1], pubkey[1], pubkey[0], pubkey[3], pubkey[2] ]; uint256[1] memory out; bool success; // solium-disable-next-line security/no-inline-assembly assembly { success := staticcall(sub(gas(), 2000), 8, input, 384, out, 0x20) switch success case 0 { invalid() } } require(success, ""); return out[0] != 0; } ``` We translate the above code into math formula. Where the `nG2` is the negative "curve" operation of the $G_2$ group generator. $$ e(\text{signature}, neg(G_2)) e(\text{message}, \text{pubkey}) \stackrel{?}{=} 1 $$ If the above formula is not straight forward, let's derive from the pairing check we usually see. The message here is the raw message hashed to $G_1$. $$ e(\text{message}, \text{pubkey}) \\ = e(\text{message}, \text{privkey} \times G_2 ) \\ = e(\text{privkey} \times \text{message}, G_2 ) \\ = e(\text{signature}, G_2) $$ $$ e(\text{message}, \text{pubkey}) \stackrel{?}{=} e(\text{signature}, G_2) $$ ### Hash to curve We can choose from Hash and pray approach or Fouque Tibouchi approach: - Hash and pray approach is easy to implement, but since it is non-constant time to run it has a security issue[^hash-and-pray-issue]. Each iteration is expensive in solidity and attacker can grind a message that's too expensive to check on chain. - Fouque Tibouchi is constant time, but more difficult to implement. #### Attempts to fix hash and pray Avg 30k gas for hash and pray https://github.com/thehubbleproject/RedditHubble/runs/1011657548#step:7:35 A sqrt iteration takes 14k gas due to the call to modexp precompile. Attempt to replace modexp with a series of modmul. optimized cost is 6.7k https://github.com/ChihChengLiang/modexp Kobi has a proposal that user provides outputs of modexp and onchain we use 1 modmul to verify. https://gist.github.com/kobigurk/b9142a4755691bb12df59fbe999c2a1f#file-bls_with_help-sol-L129-L154 ## Gas Consumption Post EIP-1108, k pairings cost `34 000 * k + 45 000` gas. So as the above example, to validate a single signature takes 2 pairings and thus 113000 gas. Validating n different messages takes n + 1 pairings, which costs `80 000 + 34000*n` gas. In comparison, ECDSA takes 3000 gas, see `ecrecover`[^ethgastable]. Here are cases to consider the aggregate signature: - When there's only one message, but many signatures to verify. The aggregate signature takes 2 pairings (113000 gas), and it wins ECDSA when you have 38 more signatures to verify. - When you need to store or log signatures on chain. Storing a word (32 bytes) costs 20000 or 5000 gas, and logging costs 8 gas per byte. The aggregate signature (48 bytes * 1 sig) wins ECDSA (65 bytes * n sigs) easily in this case. ## Packages to do BLS ### JavaScript/TypeScript https://github.com/kilic/evmbls ### Python https://github.com/ChihChengLiang/bls_solidity_python ## Cookbook ### Aggregations TODO - how to create private keys, public keys, and signatures (just listing the formulas should be enough, everyone can then use their favorite library to implement them). - test data for one cycle (a private key, a public key, a message, and a signature) - a note on encodings: The solidity code just uses the plain uints, but at least for BLS12-381 there are standardized encodings, aren't there? Not sure if it makes sense to go into details, but just mentioning that they exist with maybe a link could be helpful - public key aggregation (my problem basically): My understanding from our discussion yesterday is that it's not easily possible on-chain with bn128 and public keys from G2. I looked into the EIP fro BLS12-381 and they have a precompile for G2 additions, so with that it should be easy. [^ben-bls]:https://hackmd.io/@benjaminion/bls12-381 [^bls]:https://www.iacr.org/archive/asiacrypt2001/22480516.pdf [^bls-curve]:https://eprint.iacr.org/2002/088.pdf [^bn]:https://eprint.iacr.org/2005/133 [^eip196]:https://eips.ethereum.org/EIPS/eip-196 [^eip197]:https://eips.ethereum.org/EIPS/eip-197 [^eip2537]:https://eips.ethereum.org/EIPS/eip-2537 [^eip1108]:https://eips.ethereum.org/EIPS/eip-1108 [^eip2070]:https://eips.ethereum.org/EIPS/eip-2070 [^byzantium-fork]:https://blog.ethereum.org/2017/10/12/byzantium-hf-announcement/ [^istanbul-fork]:https://eips.ethereum.org/EIPS/eip-1679 [^ethgastable]:https://ethgastable.info/ [^ietf]:https://www.ietf.org/id/draft-irtf-cfrg-pairing-friendly-curves-07.html [^ecmul]:https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication [^hash-and-pray-issue]:https://github.com/thehubbleproject/RedditHubble/issues/171