Application of BLS algorithm on cryptocurrency: key sharing and threshold signature

In the last part , we elaborated on the characteristics and advantages of the cryptographic currency signature algorithm BLS. In this article, we will briefly analyze how BLS is applied to cryptocurrencies and how they work.

Apply BLS to cryptocurrency

 

The most obvious use of BLS is the multiple transactions of mn in cryptocurrencies, such as bitcoin. The user can ask his wallet for the m-of-n address and then get a single address and key sharing list. After that, it will assign "key sharing" to a different place (computer or hardware wallet). The wallet won't store these "keyshares", otherwise all of this will be meaningless.

The generated address is internally just the public key of the original key (and is no longer known). In addition, the address is no different from the normal 1-1BLS address, which means that no one can know that this is actually a mn multi-signature, nor how many keys or how many shares are needed to recover the key.

• Bitfinex and USDT stable currency puzzle
• After three years of lurking, Bitfinex was hacked and hackers began to transfer 300 bitcoins
• Exchange 5 hotspot tracking: The relationship between platform currency and IEO is like stocks and futures

As a result, no special processing is required for mn multiple transactions, because internally, verifying a simple signed transaction requires exactly the same verification (eg CHECKBLSSIG).

Currently, the mn budget based on ECDSA requires m public keys and m signatures as part of the transaction, which can easily lead to several kBs in the chain, which in turn impairs its ductility.

In addition, ECDSA also revealed information about the key used to sign the transaction. However, if a BLS-based threshold signature is used, the size of the budget is fixed (eg, 32 bytes), which is independent of the values ​​m and n, and there is no privacy leak.

Make it distributed and de- trusted ( trust -free)

The above solution itself is already very good, but it has a drawback that it only takes effect when the creator (the trader) is the recipient of the secret share. Therefore, it works fine only if you want to distribute your own key to avoid security issues.

If there are multiple parties involved in the transaction, there is a problem with the program. This requires absolute trust in a single trader. If the dealer is not trustworthy or compromised, the original key may be misused or compromised.

Fortunately, this problem can be easily fixed due to the nature of the BLS.

We can make each participant a trader and then aggregate the results of multiple parties so that the key can be agreed without anyone knowing.

Of course, it requires a verification by each participant to ensure that all other parties are honest. If you encounter a dishonest party, the whole process must be aborted.

This process needs to complement Shamir's secret sharing, so we first need to explain Shamir's secret sharing in more detail, then discuss the addition options we need to perform. These additions require some exchange of encrypted data, so the first thing each party must do is declare a BLS public key.

In Shamir's secret sharing, a polynomial S(x) with a degree of n-1 is created. The first value (free coefficient) of the polynomial is the original key, and the remaining n-1 coefficients are randomly generated keys. The polynomial can be represented internally as a simple key vector. The parameter "x" in the polynomial is a unique number that identifies the parties involved.

For example, it can be an index based on 1 for each participant, but can be any other known value (such as a public key or a hash value). Calculating this polynomial for each party gives the key sharing for each party.

If anyone knows the "m" shared by these secrets, then polynomial interpolation can be used to recover the original key, which is the basis for Shamir's secret sharing.

If we create a new polynomial P(x) of the same degree and set all the coefficients to the public key of the first polynomial using the key, we can use this new polynomial to generate the public key sharing corresponding to the key sharing.

This is due to the properties of the BLS primitive, where performing the same operation on two corresponding BLS primitives (eg, secret and public key) will generate a new tuple of the corresponding BLS primitive.

This polynomial can be shared publicly and will not reveal any information about the key. It can be used to verify that the received key share is actually the result of evaluating the polynomial S(x) without knowing the polynomial. This only requires P(x) to calculate the public key share and compare the result with the public key calculated from the received key share.

Now, in order to make it distributed and de-trusted, we let each party create its own polynomials S(x) and P(x). Then each party publishes P(x) so that all parties know the P(x) that exists.

Each party will then calculate S(x) for the other party and encrypt the result (key sharing) using the previously published public key. Each party then sends the encrypted secret share to the corresponding other party. In doing all of this, each party must also evaluate its own S(x).

After that, each party should receive an accurate "n" encryption key share, which means that each party should receive a key share from the other party. If any key sharing or polynomial P(x) is missing, the entire process is aborted.

When the parties receive an encrypted secret share, they will first decrypt and verify the shares. Verification is performed by computing P(x), where x is its own identifier (the index in the list of participants). If the result of the calculation (public key sharing) does not match the calculated public key shared by the received key, the entire process is aborted.

At this stage, each party should have "n" polynomials P(x) and "n" verified secret shares. Remember that the free coefficient (first value) of the polynomial S(x) used by secret sharing is the same as the original key. This in turn means that the free coefficient of P(x) is the corresponding public key of the original key.

Now we aggregate all polynomials P(x) into a final polynomial FP(x). Due to the properties of the BLS primitive, the free coefficient of FP(x) matches the public key of the final key.

However, the final key is unknown because all parties only know the respective polynomial S(x), so no one can aggregate the coefficients. The free coefficient (first value) of FP(x) is the last mn public key and is then used as the payment address.

We also aggregate all received key shares into a final key share. Similarly, due to the BLS primitive properties, the resulting key share matches the polynomial evaluation of FS(x). However, FS(x) is also unknown because it also needs to aggregate all single-party polynomials S(x).

Since the various parties may have decided to suspend the process at this stage, it is important that all parties must first declare the process successful before considering any payment using the mn public key. Otherwise, even if some other party cannot provide signature sharing later, it may spoof the unilateral use of the public key.

Therefore, in order to indicate success (protocol), the parties must issue a protocol message and sign it using the previously published public key's key (not the key share, but the first one).

In addition, the protocol message must contain a locally aggregated mn public key so that other parties can verify that it is the same as the aggregated public key. It is considered that the mn public key is a good public key only if one party complies with all the agreements expected by "n".

From now on, we will return to the simple Shamir secret sharing program. Each party has its own key share and is able to create signature shares. If mn signature sharing is collected, polynomial interpolation can be used to recover the final signature.

This signature is also a normal BLS signature, which is verified against the mn public key, which is the free coefficient of FP(x). As you might guess, there is no need to specialize with these mn addresses and signatures. A generic CHECKBLSSIG is sufficient.

The whole process may sound a lot of interaction and communication. However, this can be simplified to several messages that need to be exchanged.

Each party can package P(x) and all individually encrypted key shares into a single message, reducing the required communication to three messages per party, namely public key announcements, shared assignments, and protocols.

However, this will allow the viewer to see which public key has been agreed (the key is still unknown to anyone).

If more privacy is required, each party should send each P(x) and secret share separately to each other member.

To make it more usable, you can use a central service (where multiple services exist, you can choose one) as a proxy/scheduler while still retaining individual encryption.

Regardless of the solution, it can be integrated into the wallet so that all internal structures can be hidden. Finally, each party simply selects the other party and clicks on "Generate mn address".

More decentralized and automated

 

The process described above can be completely decentralized and automated. This involves a multi-phase network protocol that can handle and tolerate failures in the process. Tolerance failure (failure) means that the protocol can kick out the participants from the distributed key generation instead of aborting the entire process.

BLS performance

Previously Stepan mentioned in his article that BLS signature verification is an order of magnitude more complex than ECDSA. When verifying the aggregate signature of 1000 transactions in the block, 1000 pairing calculations are still required, which may be slower than when using ECDSA (verification for 1000 individual signatures). The only benefit is that you can put more transactions in the block, after all, the aggregate signature is only 32 bytes.

Unlike BLS, the Schnorr verification algorithm is very efficient, it can verify signatures together and is three times more efficient than the ECDSA algorithm. In this way, the question comes, which is more important to us for efficiency and safety?

In fact, the BLS signature algorithm is good enough. It can aggregate the signatures in the block into a single signature; it can perform key aggregation and mn multiple signatures (no additional communication required); avoid using random number generators.

These advantages make the BLS so simple and elegant. Of course, there is still room for improvement, and standardization and optimization will take time. But I hope that one day, it will be good enough to be included in the Bitcoin protocol. In this way, we can not only get its excellent features, but also enjoy the benefits of a smaller, more aggregated signature algorithm.

Translation: Sharing Finance Lam Responsible Editor: Alian

We will continue to update Blocking; if you have any questions or suggestions, please contact us!