online demo<\/a>. I\u2019d suggest to play around with this demo a little bit.<\/p>\nApplying Shamir\u2019s 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\u2019s not easily possible to avoid this with ECDSA, because to create a signature it\u2019s 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\u2019d 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.<\/p>\n
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 \u201cjust\u201d signature shares and only validate against the public key of the secret key share. So, these are useless on it\u2019s own and no-one would be able to do anything useful with these.<\/p>\n
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\u2019ll 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\u2019t do any meaningful operations on the signatures.<\/p>\n
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\u2019re 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.<\/p>\n
Applying this to cryptocurrencies<\/h3>\n 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\u2019d 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.<\/p>\n
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\u2019s impossible for anyone to know that this is actually a m-of-n multisig. It\u2019s also unknown how many keys are involved or how many shares are required to recover it.<\/p>\n
This also means that there is no special handling required for m-of-n multisig transactions, as internally it\u2019s exactly the same verification (e.g. CHECKBLSSIG) required to verify a simple single signature transaction.<\/p>\n
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.<\/p>\n
Making this distributed and trustless<\/h3>\n The above scheme is already nice on it\u2019s 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.<\/p>\n
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.<\/p>\n
Luckily, this is easy to fix\u2026again, 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.<\/p>\n
The process requires some additions to Shamir\u2019s Secret Sharing, so I\u2019ll first have to explain Shamir\u2019s 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\u2019t really matter for encryption) public key. It should be possible to verify the authenticity of these public keys, but I won\u2019t get into detail for this.<\/p>\n
In Shamir\u2019s 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 \u201cx\u201d 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 \u201cm\u201d of these secret shares, polynomial interpolation can be used to recover the original secret key. This is the basis of the simple Shamir\u2019s Secret sharing.<\/p>\n
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.<\/p>\n
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.<\/p>\n
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.<\/p>\n
After this, every party should have received exactly \u201cn\u201d 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.<\/p>\n
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.<\/p>\n
At this stage, each party should have \u201cn\u201d polynomials P(x) and \u201cn\u201d 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.<\/p>\n
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.<\/p>\n
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).<\/p>\n
As individual parties might have decided to abort the process at this stage (e.g. some other party was sending invalid shares), it\u2019s 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\u2019s the same as they aggregated. Only if a party observes all \u201cn\u201d expected agreements, it should consider the m-of-n public key to be a good one.<\/p>\n
From now on, we\u2019re back to what we did with the simple Shamir\u2019s 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.<\/p>\n
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).<\/p>\n
If more privacy is required, each party should send each P(x) and secret share individually encrypted to all other members.<\/p>\n
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.<\/p>\n
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 \u201cGenerate m-of-n address\u201d\u00a0?<\/p>\n
More decentralization and automation<\/h3>\n 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\u2019t 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.<\/p>\n
One of the critics you\u2019ll 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\u2019ll write about this in one of my next articles, but I\u2019ll give a teaser: The situation is not as bad as generally assumed, it\u2019s actually more than acceptable.<\/p>\n","protected":false},"excerpt":{"rendered":"
Secret Sharing and Threshold Signatures with\u00a0BLS<\/h1>\r\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[290],"tags":[225,281,220],"class_list":["post-13940","post","type-post","status-publish","format-standard","hentry","category-blog","tag-blockchain","tag-cryptography","tag-dash"],"acf":[],"yoast_head":"\nSecret Sharing and Threshold Signatures with BLS - Dash<\/title>\n \n \n \n \n \n \n \n \n \n \n \n \n\t \n\t \n\t \n \n \n \n \n \n\t \n\t \n\t \n