# Considerations when interacting with Ethereum for BLS signatures ## Intro BLS signatures require of pairing friendly curves which have the following properties: - e(A+B, C) = e(A, C)e(B,C) - e(aP, G) = e(P, aG) Taking into consideration these properties an aggregated signature over the same message would simply look like $S_1 = H(M)*p_1$ $S_2 = H(M)*p_2$ $S_3 = H(M)*p_3$ $e(S, G) = e(S1+S2+..+S_N, G) = e(S1, G)...e(S_N, G) =$ $e(p_1H(M), G) * .. * e(p_NH(M), G) = e(H(M), p_1G) * .. * e(H(M), p_NG) =$ $e(H(M), P)$ Now lets deep dive a little bit into how these can be possible ## Curves and Fields First and foremost: the coordinates of a point come from a finite field that has a prime order, and that prime number is π‘ž. A pairing is a bilinear map that takes as input two points, each from a distinct group of the same order, π‘Ÿ. π‘Ÿ must be prime, and for security reasons needs to be large. Also, for rather technical reasons, **these two groups need to be distinct**. Let’s call them 𝐺1 and 𝐺2. With pairing friendly curves and BLS signatures we’re really dealing with two curves, not one. Both curves share more-or-less the same curve equation, but are defined over different fields. The simpler one, G1, is over the finite field πΉπ‘ž, which is just the integers mod π‘ž. So the curve has points only where the equation 𝑦2=π‘₯3+4 mod π‘ž. We shall call this curve 𝐸(πΉπ‘ž). The other curve is defined over an extension of πΉπ‘ž to πΉπ‘ž2 (think complex numbers). In this case, the curve equation is slightly modified to be 𝑦2=π‘₯3+4(1+𝑖), and we’ll call the curve 𝐸′(πΉπ‘ž2). How do we extend a field? Just check https://hackmd.io/@benjaminion/H1lkISO3JU. The simple curve 𝐸(πΉπ‘ž) has only a single large subgroup of order π‘Ÿ, so we can’t define a pairing based solely on 𝐸(πΉπ‘ž). However, if we keep extending the field over which 𝐸 is defined, it can be proved that we eventually find a curve that has more than one subgroup of order π‘Ÿ (in fact, π‘Ÿ+1 of them). For some π‘˜, 𝐸(πΉπ‘žπ‘˜) contains other subgroups of order π‘Ÿ that we can use. It turns out that πΉπ‘ž12 is the lowest extension achieving this. But there’s another challenge: doing arithmetic in πΉπ‘ž12 is horribly complicated and inefficient. And curve operations need a lot of arithmetic. A twist is something like a coordinate transformation. Rather wonderfully, this can be used to transform our 𝐸(πΉπ‘ž12) curve into a curve defined over a lower degree field that still has an order π‘Ÿ subgroup. Moreover, this subgroup has a simple mapping to and from our 𝐺2 group. Pairing friendly curves usually use a β€œsextic twist”. This means that it reduces the degree of the extension field by a factor of six. So 𝐺2 on the twisted curve can be defined over πΉπ‘ž2 instead of πΉπ‘ž12, which is a huge saving in complexity. ## What to operate in G1 and G2 Now that we have seen how G1 and G2 differ (and how one of them implies double the size to represent an element), we need to decide how we are going to check things with respect to BLS signatures. In a straight forward fasion we have 2 options: - $e(S, G_2) = e(H(M), P)$ which necessarily implies handling public keys in G2. The hash_to_try algorithm can be implemented in G1 and take advantage of a reduced size multiplication. - $e(G_1, S) = e(P, H(M))$ in this case the signatures would be performed in G2, the public keys would be handled in G1 and the hash_to_try algorithm would need to be performed for G2. As this implies a multiplication with the cofactor. This link http://hdiff.luite.com/cgit/elliptic-curve/commit?id=0.1.0 offers a nice idea on the order expected for the cofactors. ## The case of Ethereum: the BN256 curve Ethereum offers us 3 pre-compiled opcodes for the BN256 curve. This curve is caracterized for: - Having q=0xfffffffffffcf0cd46e5f25eee71a49f0cdc65fb12980a82d3292ddbaed33013 - Having r=0x0xfffffffffffcf0cd46e5f25eee71a49e0cdc65fb1299921af62d536cd10b500d - Having a cofactor on G1 h=1 - Having a cofactor on G2 h= LARGE NUMBER And the precompiles: - bn256Add: Adds points in G1 - bn256Mul: Multiplies points in G1 - bn256PairingCheck: computes e(A,B) = e(C,D) Now lets divide our potential approaches ### Approach 1: $e(S, G_2) = e(H(M), P)$ Lets assume we take this option. In this case our public keys would be defined in G2. As we need to aggregate public keys in the Block Relay, we would need to implement or utilize a function that offers us this feature. According to https://octolinker-demo.now.sh/musalbas/solidity-BN256G2/blob/master/BN256G2.sol it should take around 30000 gas to add two points, and here we need to add as many as ARS members we have. So this quickly becomes prohibitive in terms of gas ### Approach 2: $e(G_1, S) = e(P, H(M))$ In this case public keys live in G1, but hash to try needs to be implemented in G2. This is, we can add keys in G1 but the hash to try method to hash a message into G2 would need to multiply times the cofactor. As the cofactor for G2 is expected to be a large number, we can expect the multiplication to quickly become inefficient. Further, we would need to implement such a function in solidity. According to https://octolinker-demo.now.sh/musalbas/solidity-BN256G2/blob/master/BN256G2.sol this should take around 2000000 gas. ### Third option: where magic happens. If we think about it we can do everything in G1 by impliying an additional pairing check in the smart contract. Imagine bridge nodes know both the public key in G1 and G2. The bridge node could tell the smart contract to add the keys in G1 and to perform the following check, provided the summed keys in G2 $P_g2$. $e(P_g_{1,1}+P_g_{1,N}, G_2) =$ $e(P_g_{1,1}, G_2)...e(P_g_{1,N}, G_2) =$ $e(G1, P_g_{2,1})...e(G_1, P_g_{2,N}) = E(G1, P_g2)$ $e(G1, P2) = e(P1, G2)$ That is, we can efficiently add (https://github.com/ethereum/benchmarking/blob/master/analysis.md) for 1000 of gas, keys in G1 and then compute a couple of PrecompiledBn256Pairing for 160000 gas cost each. A total gas cost of 320000 + N*1000. For a high expectation of 1000 ARS members, a maximum of 1320000 gas cost should be expected for the verification. ### Comparison This table compares the three approaches for 10 and 1000 ARS members. | | Option 1 | Option 2 | Option3 | |:----------------:|----------|----------|---------| | 10 ARS members | 460000 | 2170000 | 330000 | | 1000 ARS members | 30160000 | 3160000 | 1360000 | From these numbers it seems obvious that the most reasonable thing to do is to manage keys in both groups in Witnet (See above how) and go with Option 3. ## Other curves What about supporting other curves? It is no secret that bn256 does not offer the expected 128 bit security level. For that reason most of the sharded implementations (Eth2.0, Cosmos, Polkadot) will use the BLS12-381 curve, which offers a higher security level. However, as of today the main focus of the node is to connect to Ethereum 1.0, so we will start supporting only bn256 keys. Migrating to BLS12-381 should be as easy as handling a representation of the public keys that takes into account secp256k1, BN256 and BLS12-381. ## Multi-key management The main question now is how to handle keys generated for different curves in Witnet. Essentially, a node paying willing to pay to an address pays to its script-hash instead. The script hash is nothing more than a sha256 of the public key of the node we wish to pay, taking the first 20 bytes of the output. Now how do we translate this P2PKH to a multi-curve system? Essentially we can create a merkle tree with each of the public keys of each curve acting as the leafs. In this sense, if secp256K1 keys are utilized to verify spendability of UTXOs one simply has to provide the merkle path to the address, and prove with a signature the possession of the private key associated with the corresponding public key. With secp256k1 and BN256 curves this would look like: ----------- | Root | | Addrs(20)| ----------- / \ / \ / \ --------- ------------- | H(BN256)| | H(secp256K1)| --------- ------------- Where BN256 may include public keys in G1, G2 or both. In the future we can establish a mechanisms to update the root of the address with an additional key coming from, e.g., BLS12-381. Essentially, a consistency proof in which the public key of the new curve is appended can be implemented, of course invalidating the previous address for the new root. ## Unsolved problems There is a major impediment to perform the aforementioned mechanisms. Even though the most efficient way of verifying BLS signatures was selected, we still omitted the fact that one needs to prove that the public keys belong to ARS members in Witnet. This is, even though we merklelize the addresses of the ARS members, we still need to input several public keys to be aggregated in the block relay. Public keys are 32 bytes, so if we have an ARS of 1000 members we can imagine the amount of limitation this poses. Solutions to be studied: - Subgroup multi-signatures. This, as specified in https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716 would imply that every node signs the index at which each public key stands, i.e., N signatures for N ARS members. Then the bridge node creates a membership key for every participant of the voting, which basically consits on the sum of the signatures of every other participant of their index. - SNARKS (a compact proof of knowledge of sufficient keys and paths) - Subgroups in the merkle tree ### A plausible solution: A plausible solution would be to rely on bridge nodes to understand what the optimal number of signatures to be inserted is.The size directly depends on the gas limit per blck. As of today we have a gas limit as stated in https://ethstats.net/ of 9M. In principle this should increase the number of keys we can send but the main issue that arises is that someone needs. At current gas prices (1gwei) inserting a transaction consuming 9M should yield a price of 0.009 eth, or is USD, 1.5 at current prices. However we know these numbers can severely change, and therefore we need to foresee this. With Grandpa, we know that the last valid signature of an ARS member that votes for a block or its extension is taken into account. Therefore, for a chain that looks like A-B-C-D-E-F-G with payable events (data request insertions, tallies) on each of the blocks (expected in the case the ARS is big), a bridge node could decide to insert as many signatures as the data requestor is willing to pay for in its reward. For example, if the sum of the data requests only pay for the insertion of 10% of the signatures, it is expected that bridge nodes insert only 10% of aggregated public keys backing block A. In the next block B which extends A, they can insert a different 10%, and continue doing this until at block G block A will be finalized. This means that **the finality wil be delayed with respect to the reward payed out by the sum of the data request creators for each of the blocks**. There exists a caveat with this idea though: until a new finalized block is achieved, the claimability of data request inclusions will always fall in the same bridge nodes. However, an altruist bridge node always has the possiblity of finalizing one of the blocks to change the VRF. The main concern we can foresee with this approach is the fact that we might be missing singatures for blocks that extend A if some ARS members dissapear in blocks B, C, D. However, bridges nodes are able to see the Witnet chain and therefore know in advance which members dissapear from the ARS, say in block B. It is thus expected that they priorize at the time of backing A the signatures of those ARS members that are likely to dissapear in block B. Analogously, it is expected to send signatures from those ARS members that dissapear in block C, backing block B, and subsequently. If there is a catastrophe and suddenly all ARS members dissapear, it is expected that the whole set of signatures is sent. There is an even more efficient solution, which basically implies that a bridge node inserts all 7 blocks at once, each backed by a different (but valid) set of ARS members. In this case, we have the triple $\sigma_i, apk_i, m_i$ for each of the blocks. The block relay would then: - Validate that each $P_i$ conforming each $apk_i$ is valid against the ARS root. - Aggregate all those $P_i$ in G1 to $apkg1$. - Check, for each aggregated $P_i$ that they match e($apkg1$, g2) = e(g1, $apk_1$)....e(g1, $apk_n$). - Aggregate those messages as $\sigma = \sigma_1 + \sigma_2 + ... + \sigma_N$ - Check that e($\sigma$, g2) = e(H0($m1$), $apk_1$)....e(H0($m_n$, $apk_n$). This is called batch verification and is explained in https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html. In this case, instead of doing 4*N pairing functions (where N is the number of blocks proposed), the bridge node would be doing 2N+1 pairing functions to evaluate in batch mode.