BLS Signatures in Tendermint

Author: Hyunsik Jeong<rbtree@kodebox.io>

Created: 2019-10-20

1. Introduction

In Tendermint, each node in the committee creates a vote message in the prevote and precommit stage, signs the message and sends it. As the size of the committee grows, the total size of all signatures also grows, and this increases the block size. To solve this problem, we need to ‘compress’ the signatures as much as possible.

One such solution is signature aggregation. Signature aggregation is a technique to merge multiple signatures into one aggregated signature. Aggregated signatures may have the same form as single signatures and be verified by the single-signature verification method.

One of the most famous aggregation schemes is MuSig [6], which is used to aggregate Schnorr signatures [7] that are currently used in CodeChain because of its signing/verification speed. However, MuSig has a problem when used in Tendermint because generating an aggregated signature requires the set of signers to be specified first. In Tendermint, messages are constantly sent to each node, and it is hard to specify which nodes vote yes or no at a specific block height. Thus, we can say that signature aggregations on Schnorr signatures are not available in Tendermint as of now.

One possible solution is using Boneh-Lynn-Shacham (BLS) signatures. BLS signatures can be easily aggregated, non-interactively. In this proposal, we introduce how to use BLS signatures in Tendermint.

2. Background

1. What are BLS signatures?

The Boneh–Lynn–Shacham (BLS) signature scheme is a digital signature scheme based on pairing-based cryptography. It is efficient in signature aggregations as it uses pairing for verification. In this proposal, we briefly explain about pairing. For the strict definition of pairing, please check [10].

Pairing is a map defined over two elliptic curves E and E’. It consumes a point A on E and a point B on E’ and outputs a value over a finite field F. Let e be a pairing function (E x E’) → F. Then the function e satisfies a special property, bilinearity: for any point A on E, point B on E’, and integers a and b, e(aA, bB) = e(A, B)^{a * b}. Pairings are not always defined over every two elliptic curves E and E’. There are several elliptic curves called ‘pairing-friendly curves’, which can construct pairings.

In BLS signatures, key pairs are defined in the same manner as other signature schemes. If there is a private key x, which is an integer, the matching public key is X = xB, where B is the base point of the elliptic curve E. When signing, we hash m to the curve E’. Let’s say there is a hashed point H. Then, the signature of the message m is σ = xH. When verifying, we use the pairing function. It is very simple: check e(B, σ) = e(X, H). If σ is valid, we can easily show: e(B, σ) = e(B, xH) = e(B, H)^x = e(xB, H) = e(X, H). Therefore, the equation must hold if the signature is valid.

Signature aggregation in the BLS signature scheme is also simple. For signatures σ1, σ2, …, σk which regards to the same message m, just add all the signatures: σ = σ1 + σ2 + … + σk. If the sum of the public keys is X = X1 + X2 + … + Xk, then we can easily show that e(B, σ) = e(X, H): e(B, σ) = e(B, σ1 + σ2 + … + σk) = e(B, (x1 + x2 + … + xk)*H) = e((x1 + x2 + … + xk)*B, H) = e(X1 + X2 + … + Xk, H) = e(X, H).

However, the naive signature aggregation scheme described above is vulnerable to the rogue public-key attack described in [4]. The scheme in [4] solves this problem, by defining a hash function H1, which consumes n of public keys and outputs n of values from R = {1, 2, 2^2, … , 2^128}. Still, it’s non-interactive, which is different from aggregation schemes on Schnorr signatures.

2. Pairing functions, and pairing-friendly curve selection

When it comes to pairing functions, there exists several pairings, such as Weil pairing, Tate pairing, and optimal Ate pairing[8]. In particular, optimal Ate pairing is considered to be efficient for computations and mainly used for practical implementations. [10]

Moreover, there are two famous curve groups that construct optimal Ate pairing: Barreto-Naehrig (BN) curves[3] and Barreto-Lynn-Scott (BLS) curves[2]. However, it is shown that pairing-friendly curves are vulnerable to an attack called exTNFS. By using this attack method, private keys can be efficiently computed from public keys. [5] Even though it is still possible to attain high security levels by adjusting curve parameters, it is considered impractical to use BN curves to gain 192/256 bits of security. [1]

3. Design

1. Changing Schnorr Signatures to BLS Signatures

CodeChain makes extensive use of Schnorr signatures. It needs to be changed to use BLS signatures only when using Tendermint. To achieve this, we can introduce a BLS signature library and modify Tendermint to be able to use it, and finally, blocks can be sealed with aggregate signatures. The signature aggregation scheme will follow [4].

2. BLS curve

Regarding BLS curves, BLS12-381 can be used for 128-bit security and BLS48-581 for 256-bit security. BLS12-381 is commonly used, by Ethereum [14], Zcash [15], and Harmony [13]. Among those, CodeChain is going to use BLS12-381 in BLS signatures.

In BLS curves, there are two curves E1 and E2. Actually, it doesn’t matter whether we use E1 as the public key curve and E2 as the signature curve, or vice versa. In BLS12-381, the length of bytes to represent a point on E1 is 96, while E2 is 48. Furthermore, multiplication on E1 is slower than E2. Since our purpose is to reduce the block size, we are going to use E1 as the public key curve, and E2 as the signature curve.

3. BLS signature library

Currently there are two options. One is Zcash’s pairing library [11]. It implements the basics of BLS12-381 curves. To use it, we need to implement hash_to_curve function based on [12], and the aggregation scheme based on [4]. The other option is the BLS12-381 Rust implementation based on Apache Milagro Cryptographic Library[16]. It’s not fully implemented and tested, but we may consult it to implement CodeChain’s own BLS signature library.

4. References

Papers

[1] Barbulescu, R., & Duquesne, S. (2018). Updating Key Size Estimations for Pairings. Journal of Cryptology, 32(4), 1298–1336. doi: 10.1007/s00145-018-9280-5
[2] Barreto, P. S. L. M., Lynn, B., & Scott, M. (2003). Constructing Elliptic Curves with Prescribed Embedding Degrees. Security in Communication Networks Lecture Notes in Computer Science, 257–267. doi: 10.1007/3-540-36413-7_19
[3] Barreto, P. S. L. M., & Naehrig, M. (2006). Pairing-Friendly Elliptic Curves of Prime Order. Selected Areas in Cryptography Lecture Notes in Computer Science, 319–331. doi: 10.1007/11693383_22
[4] Boneh, D., Drijvers, M., & Neven, G. (2018). Compact Multi-signatures for Smaller Blockchains. Lecture Notes in Computer Science Advances in Cryptology – ASIACRYPT 2018, 435–464. doi: 10.1007/978-3-030-03329-3_15
[5] Kim, T., & Barbulescu, R. (2016). Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case. Advances in Cryptology – CRYPTO 2016 Lecture Notes in Computer Science, 543–571. doi: 10.1007/978-3-662-53018-4_20
[6] Maxwell, G., Poelstra, A., Seurin, Y., & Wuille, P. (2019). Simple Schnorr multi-signatures with applications to Bitcoin. Designs, Codes and Cryptography, 87(9), 2139–2164. doi: 10.1007/s10623-019-00608-x
[7] Schnorr, C. P. (1989). Efficient Identification and Signatures for Smart Cards. Lecture Notes in Computer Science Advances in Cryptology — EUROCRYPT ’89, 688–689. doi: 10.1007/3-540-46885-4_68
[8] Vercauteren, F. (2010). Optimal Pairings. IEEE Transactions on Information Theory, 56(1), 455–461. doi: 10.1109/tit.2009.2034881

Websites

[9] https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-00
[10] https://tools.ietf.org/html/draft-yonezawa-pairing-friendly-curves-02
[11] https://github.com/zkcrypto/pairing
[12] https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04
[13] https://github.com/harmony-one/harmony
[14] https://medium.com/prysmatic-labs/ethereum-2-0-development-update-17-prysmatic-labs-ed5bcf82ec00
[15] https://electriccoin.co/blog/new-snark-curve/
[16] https://github.com/lovesh/signature-schemes