Secret Sharing and Threshold Signatures with BLS

I’ve been working on some BLS (Boneh-Lynn-Sacham) related topics for quite a few months already and there is one thing that I keep repeating to myself and others: BLS is pure Magic!

Why? Because it has a few very unique and simple properties which let it stand out compared to other signature schemes (like ECDSA). These properties might seem unimportant at first sight or at most result in a “Nice!”, but the implications of these properties are much larger than one might expect.

I’d suggest to first read this BLS article written by Stepan Snigirev. It explains the basics and the math behind BLS pretty well. His article also explains a few of the properties (e.g. aggregatable) and use cases of BLS. It also shows how to use aggregate signatures to implement a simple threshold scheme.

In this article, I’d like to highlight the implications of the unique BLS properties. After that, I’d like to introduce a secret sharing scheme for trustless and distributed key sharing and a threshold signatures scheme that is based on this. The proposed scheme results in single public keys and signatures on-chain and does not require to store meta information about public key shares or signers when sending to a m-of-n address or later spending the output. It in fact is indistinguishable from any normal 1-of-1 address or spend and thus improves privacy as a side-effect.

Some Properties of BLS

As already said, BLS has a few properties which seem to be quite unique in signature schemes. Without these, the later proposed secret sharing schemes would not be possible, or at least I’m not aware of how these would work without those properties.

Aggregatable

This was already shown in the linked article about BLS, but I’d like to add a few things to this. With BLS, it’s possible to aggregate all types of primitives (secret keys, public keys, signatures) and the result is always another valid primitive. For example, if you aggregate two secret keys, the result is a new valid secret key. If you aggregate the two corresponding public keys of the secret keys, the result is a new public key that matches the previously aggregated secret key’s public key. If you aggregate two signatures that were created with the two previously aggregated secret keys and the same message hash, the new signature would also validate against the aggregated public key. Primitives which were already aggregated can also be further aggregated, independent from the order in which it happens.

This can even be generalized. On any given set of secret key, public key and signature tuples, for any operation you perform on one of the primitives, you can repeat the same operation on the other primitives and obtain a new tuple where the primitives still correlate to each other. This will even apply if operations get nested and more complex. This allows some very interesting things which as far as I know are not possible with ECDSA. For example, polynomial evaluation and interpolation can be used with any BLS primitive, including the signature (which as I understand it, is hard and limited with ECDSA). I’ll explain later why this is interesting.

Uniqueness and determinism

BLS signatures are unique and deterministic. Meaning, that for any given pair of public key and message, there can only be one valid signature. It’s not possible to have two different signatures validating against the same public key and message. This is very different compared to ECDSA, where the use of randomness inside the signature results in uncountable amounts of possible signatures for the same public key and message.

This has a few positive effects when it comes to hashing of other messages which contain a BLS signature. Such a message (e.g. a Dash or Bitcoin transaction), will always result in the same hash and it’s impossible to modify a signature so that the message is still valid but the resulting hash differs.

This has a huge implication if BLS would be used in a cryptocurrency. It would once and for all fix transaction malleability, without the need for a specific malleability fix. BLS already has many other advantages over ECDSA and the malleability fix would “just” be a freebie. UPDATE: As pointed out by a user on reddit, this only holds true if spending scripts would not be able to perform operations on the signature before the actual validation. This can however be detected when the spending script is revealed (if the script is not a simple push+verify, it is possibly malleable).

Also, every operation you can perform on a BLS primitive is deterministic. This means, if you repeat an operation with the same inputs, e.g. create a signature from a pair of secret key and message hash, the resulting signature will always be the same. This is somewhat related to the uniqueness property of BLS, but also has some other implications. The determinism even holds if operations get nested and complex, allowing very interesting use cases and schemes. The most interesting scheme, at least for me, is probably threshold signing based on shared keys, which I’ll explain in the next section.

Shamir’s Secret Sharing and BLS

The described properties of BLS are already fascinating, but the real magic begins here. Shamir’s Secret Sharing is a threshold scheme that is known for quite some time already and proven to be secure if done correctly. It allows to take a secret and create a set of secret shares from it. A secret share does not leak any information about the original secret and thus is useless on its own. Only if enough shares (m-of-n) are gathered, it’s possible to recover the original secret from it. If someone only knows n-1 shares, he is as clueless as someone having no shares at all. The secret can be anything that is representable by a (possibly very large) integer, including arbitrary binary or text data, or more importantly; secret keys.

I’d suggest to read the Wikipedia article about Shamir’s Secret Sharing to understand how it works. Basically, polynomial evaluation is used to create the secret shares and polynomial interpolation is then used to recover the original secret. I’ll later also try to go deeper into how Shamir’s Secret Sharing is used, but I’ll not try to explain how/why it works on the mathematical level.

As already said, Shamir’s Secret Sharing is already known for quite some time and also found some useful applications. One example is a simple command line tool called “ssss”, which also has a nice online demo. I’d suggest to play around with this demo a little bit.

Applying Shamir’s Secret Sharing to public key crypto and especially ECDSA however poses a problem; whoever is the one that recovers the secret key from a m-of-n set of secret key shares, will obtain the original secret key. It’s not easily possible to avoid this with ECDSA, because to create a signature it’s required to have the full secret key. This is partly ok if you are the only participant and just use this scheme to divide your secret key into multiple secret key shares which you’d like to store in different places. It however gets problematic when at recovery time your computer is somehow compromised and thus the secret key is also at risk.

With BLS however, this changes. Creating the secret key shares stays identical to how it would be done with ECDSA. The difference is, that the resulting secret key shares are also valid secret keys which can be used to sign a message and thus create a valid signature. These signatures are however “just” signature shares and only validate against the public key of the secret key share. So, these are useless on it’s own and no-one would be able to do anything useful with these.

The magic comes now: If you take m-of-n of these signature shares, and perform the same polynomial interpolation as you would usually do with the secret shares, you’ll recover a new signature which is identical to what would have been created if the original secret key would have been used. This is only possible due to the properties described in the previous section. With ECDSA, this is not easily possible because you can’t do any meaningful operations on the signatures.

This means, that the original secret key is never observed again, in no place in the world, not even for a nano second. Now you’re able to leave the secret key shares where they are and never have to temporarily copy them just to sign a single message. Instead, you sign the message multiple times on different computers, hardware wallets, or whatever and just collect the signature shares on a single computer so you can recover the final signature.

Applying this to cryptocurrencies

The most obvious use for this are m-of-n multisig transactions in cryptocurrencies like Dash or Bitcoin. A user could ask his wallet for a m-of-n address and get a single address and a list of secret key shares. He’d then distribute the secret key shares to different places (computers or hardware wallets). The wallet would not store these secret key shares as otherwise all this would be pointless.

The generated address is internally just the public key of the original secret key (which is not known anymore). Also, that address is indistinguishable from a normal 1-of-1 BLS address, which means that it’s impossible for anyone to know that this is actually a m-of-n multisig. It’s also unknown how many keys are involved or how many shares are required to recover it.

This also means that there is no special handling required for m-of-n multisig transactions, as internally it’s exactly the same verification (e.g. CHECKBLSSIG) required to verify a simple single signature transaction.

Currently an ECDSA based m-of-n spend requires to have m public keys and m signatures as part of the transaction. This can easily result in several kB on-chain and thus does not scale well. It also leaks information about which keys were used to sign a transaction. With BLS based threshold signatures, the size of a spend is fixed (e.g. 32 bytes), independent from the values m and n. There is also no privacy leakage.

Making this distributed and trustless

The above scheme is already nice on it’s own, but it has a drawback; it only works well if the creator (the dealer from now on) is also the receiver of the secret shares. So it really only works well if you want to distribute your own secret key as a matter of secure disaster avoidance.

If multiple parties are involved where m-of-n parties are required to sign a transaction, this scheme is problematic. It would require absolute trust in a single dealer. If the dealer is not trustworthy or simply compromised, the original key might be misused or leaked.

Luckily, this is easy to fix…again, thanks to the properties of BLS. We can let every party be a dealer and then aggregate the results of each, which in turn results on agreement on the secret key without anyone ever knowing it or having influence on it. It, however, requires some verification performed by each party to make sure that all other parties are honest. If any dishonest party is encountered, the whole process must be aborted.

The process requires some additions to Shamir’s Secret Sharing, so I’ll first have to explain Shamir’s Secret Sharing in more detail and then explain the additions we need to perform. The additions require some exchange of encrypted data and thus the first thing that must be done by every party is to announce a BLS (or ECC, doesn’t really matter for encryption) public key. It should be possible to verify the authenticity of these public keys, but I won’t get into detail for this.

In Shamir’s Secret Sharing, a polynomial S(x) of degree n-1 is created. The first value (the free coefficient) in this polynomial is the original secret key while the remaining n-1 coefficients are some randomly generated secret keys. The polynomial can be internally represented as a simple vector of secret keys. The parameter “x” in the polynomial is a unique number that identifies the participating parties. It can for example be the 1-based index of each party, but could also be any other publicly known value (e.g. a public key or some hash). Evaluating this polynomial for each party gives the secret key share for each party. If anyone knows “m” of these secret shares, polynomial interpolation can be used to recover the original secret key. This is the basis of the simple Shamir’s Secret sharing.

If we create a new polynomial P(x) of the same degree and set all coefficients to the public keys of the secret keys used in the first polynomial, we can use the new polynomial to generate the public key shares corresponding to the secret key shares. This works due to the properties of BLS primitives, where the same operations performed on two corresponding BLS primitives (e.g. secret and public key) will result in a new tuple of corresponding BLS primitives.

This polynomial can be publicly shared and does not leak any information about the secret key. It can be used to verify that a received secret key share is actually the result of the evaluation of the polynomial S(x) without knowing the polynomial. This is simply done by evaluating the public key share with P(x) and comparing the result to the public key calculated from the received secret key share.

Now, to make this distributed and trustless, we let every party create his own polynomial S(x) and P(x). Every party will then publish P(x) so that every party knowns every P(x). After this, every party will evaluate S(x) for every other party and encrypt the result (the secret key share) using the previously announced public key. Each party then sends the encrypted secret shares to the corresponding other parties. While doing all this, every party must also perform the evaluations of S(x) for itself.

After this, every party should have received exactly “n” encrypted secret key shares, meaning that each party should have received one secret key share from each other party. If any secret key share or polynomial P(x) is missing, the whole process is aborted.

When the individual parties receive their encrypted secret shares, they will first decrypt and validate these. Validation is performed by evaluating P(x) with x being the own identifier (e.g. own index in the parties list). If the result of the evaluation (the public key share) does not match the calculated public key of the received secret key share, the whole process is aborted.

At this stage, each party should have “n” polynomials P(x) and “n” validated secret shares. Remember that the free coefficient (the first value) of the secretly used polynomials S(x) was identical to the original secret key. This in turn means that the free coefficient of P(x) is the corresponding public key of the original secret key.

We now aggregate all polynomials P(x) into a single final polynomial FP(x). Due to the properties of BLS primitives, the free coefficient of FP(x) matches the public key of the final secret key. The final secret key however is unknown as all individual parties only know their individual polynomial S(x) and thus no-one is able to aggregate the coefficients. The free coefficient (first value) of FP(x) is the final m-of-n public key which is later used as the address for payments.

We also aggregate all received secret key shares into a final secret key share. Again, due to the properties of BLS primitives, the resulting final secret key share matches the result of the polynomial evaluation of FS(x). However, FS(x) is also unknown as it would also require the aggregation of all individual polynomials S(x).

As individual parties might have decided to abort the process at this stage (e.g. some other party was sending invalid shares), it’s important that all parties must first announce success of the process before any of the parties considers using the m-of-n public key for any payments. Otherwise a single party might get tricked into using the public key even though some other parties are later unable to provide signature shares. To signal success/agreement, each party must thus publish some kind of agreement message, signed with the secret key of the previously announced public key (not the secret key share, but the one from the very beginning). The agreement message must include the m-of-n public key that was locally aggregated so that other parties can verify that it’s the same as they aggregated. Only if a party observes all “n” expected agreements, it should consider the m-of-n public key to be a good one.

From now on, we’re back to what we did with the simple Shamir’s Secret Sharing scheme. Each party has his own secret key share and is able to create signature shares. If m-of-n signature shares are gathered, polynomial interpolation can be used to recover the final signature. This signature is again, just a normal BLS signature and it validates against the m-of-n public key, which is the free coefficient of FP(x). As you probably already guessed, there is again no special handling of these m-of-n addresses and signatures required, a generalized CHECKBLSSIG is enough.

The whole process might sound like a lot of interactivity and communication is involved. This can, however, be reduced to just a few messages that need to be exchanges. Each party can pack P(x) and all individually encrypted secret key shares into a single message and thus reduce the needed communication to 3 messages per party: announcement of public keys, distribution of shares and agreement. This would, however, allow observers to see which public key was agreed on (secret key will still be unknown by anyone).

If more privacy is required, each party should send each P(x) and secret share individually encrypted to all other members.

To make this more usable, a central service (of which multiple would exist, so that you can choose one) could be used as a proxy/dispatcher, with individual encryption still in place.

Whatever the solution is, it can be integrated into a wallet so that all internals are hidden. In the end, each party should be able to just choose the other parties and click on “Generate m-of-n address” ?

More decentralization and automation

The previously described process can be fully automated and made fully decentralized. This involves a multi-stage network protocol that is able to handle and tolerate failures in the process. With tolerating failure, I mean that instead of aborting the whole process, the protocol is able to kick individual parties from the distributed key generation. I won’t describe this further in this post but instead consider writing another one in the future which fully concentrates on this protocol and how all this is related to Dash.

Performance of BLS

One of the critics you’ll hear about BLS is that it performs about a magnitude slower that ECDSA. This is true, but only of you use BLS in the most naive way. There are some optimizations possible which fully leverage the unique properties of BLS. I’ll write about this in one of my next articles, but I’ll give a teaser: The situation is not as bad as generally assumed, it’s actually more than acceptable.

Author: Alexander Block
Original link: https://blog.dash.org/secret-sharing-and-threshold-signatures-with-bls-954d1587b5f