Author [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] Topic: Threshold signatures for Bitcoin wallets are finally here  (Read 394 times)

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 11958
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BTS: xeroc
  • GitHub: xeroc
Threshold signatures for Bitcoin wallets are finally here
« on: March 08, 2015, 04:46:04 PM »

https://freedom-to-tinker.com/blog/stevenag/threshold-signatures-for-bitcoin-wallets-are-finally-here/

stealth multisig sig ..

Shouldn't that also be possible in bitshares?

@bytemaster @toast @vikram @modprobe @pc
Give BitShares a try! Use the http://testnet.bitshares.eu provided by http://bitshares.eu powered by ChainSquad GmbH

Offline arhag

  • Hero Member
  • *****
  • Posts: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: Threshold signatures for Bitcoin wallets are finally here
« Reply #1 on: March 08, 2015, 06:51:46 PM »
Quote
I also discussed why building a threshold signature scheme that is compatible with the ECDSA signature scheme used by Bitcoin is so difficult. Our previous work presented a toolbox of options, none of which is perfect but which we believed were a useful starting point. Since that post, we had discussions with businesses that want to implement our techniques, and it turned out that they wanted the best-of-both-worlds properties from the crypto. In particular, they wanted a scheme that required no trusted precomputation, and in which they could realize a t-of-n access control for any t <= n.
These discussions motivated us to go back to the drawing board and see if we could build a scheme that fit the need of these businesses. We realized that we could generalize a well-known 2-out-of-2 signature scheme of Mackenzie and Reiter to an n-of-n threshold signature scheme. Once we have an n-of-n scheme, we could combinatorially build an t-of-n scheme.

YES! (But then I read more and realized it is not as good as I hoped. Read below to see why.)

My first concern is that since they achieve t-of-n combinatorially from (n choose t) t-of-t schemes, this can get a very expensive for large values for t and especially when t/n is close to 0.5. I still haven't read the paper fully to see how the performance is for the various parts (initial setup and actual signing). I assume the (n choose t) different schemes can be done in parallel for the initial setup. And there is no need to do the actual signing for more than ideally one (maybe a handful if the first one fails) of the (n choose t) subsets: choose the subset with the first t reliable nodes that claim they will participate in the transaction signing process. For backup, do transaction signing in parallel for ((t+1) choose t) = (t+1) subsets of the subset consisting of the first t+1 nodes that claim they will participate.

So there are a few problems with this if we wanted it for a BitShares Standard Gateway. If a 91-of-101 scheme was used, first it would require (101 choose 91) parallel constructions for the initial setup which is not acceptable (too large both from the perspective of the amount of computation necessary as well as the amount of storage necessary). This forces a choice for t closer to n. For example, a 99-of-101 scheme would require (101 choose 99) = 5050 parallel initial setups. This is still high, but since it can be done in parallel and it is only necessary when the set of delegates changes (which should be relatively infrequent), perhaps it is acceptable. Still, this is incredibly constraining on the selection of the t/n ratio. It means that if 3 of the delegates disappear or refuse to cooperate, the reserve in the BitShares Standard Gateway would be stuck.

The other problem is the amount of time it takes to generate the signature. Based on section 7.6 of the paper, apparently it takes about 1 minute for t = 10! Now, I am not sure what machine this was running on and whether the algorithm can be optimized much more, but that doesn't look good. Even worse, the dependence on t seems to be superlinear. So even with faster machines it doesn't look very good for a choice of t = 99.  :( Also I think the paper said it requires 3*t - 2 rounds, which for t = 99 would require 295 rounds, so network latency could be a big problem there as well.

In short, this isn't very interesting for the use cases I was hoping to use it for (large values of t and n). Regular multisig will work fine instead (even for Bitcoin with its 15-of-15 max limitation).

Now I wonder how the performance of their previous scheme with the t' = 2*t - 1 limitation compares to this? I also wonder how a threshold signature scheme with Schnorr signatures compares to both. Obviously a signature scheme using Schnorr signatures wouldn't be useful for Bitcoin (and thus not useful for a BitShares Standard Gateway), but it could still be useful for other places on the BitShares blockchain and for child DACs specifically, assuming its performance is reasonable for large values of t and n.
« Last Edit: March 08, 2015, 09:26:49 PM by arhag »

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 11958
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BTS: xeroc
  • GitHub: xeroc
Re: Threshold signatures for Bitcoin wallets are finally here
« Reply #2 on: March 08, 2015, 07:07:34 PM »
Yes .. I read about those drawbacks too .. posted the thread to early ..
I think, when it comes to security and robustness, we should stick to multisig and implement (3rd party) Shamir secret sharing ..
I will look at SSS for my paperwallets (and maybe more) when I can find some time
Give BitShares a try! Use the http://testnet.bitshares.eu provided by http://bitshares.eu powered by ChainSquad GmbH

Offline arhag

  • Hero Member
  • *****
  • Posts: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: Threshold signatures for Bitcoin wallets are finally here
« Reply #3 on: March 08, 2015, 09:26:37 PM »
By the way, this new threshold signature scheme combined with Bitcoin's multisig features provides better security properties for the BitShares Standard Gateway proposal without having it be too computationally inefficient.

With the previous threshold signature system there was the t' = 2*t - 1 restriction. That means with a 46-of-101 threshold scheme (t = 46, n = 101, t/n = 45.5%), it required t' = 2*t - 1 = 91 participants at a minimum to work together to generate a signature. This means with less than 90% delegate participation the gateway would halt and the reserves would be stuck. If I were to only look at the top 98 delegates rather than the top 101, and bump up the delegate participation requirement to 95%, this would give a value of n = 98 and t' = 93, which means t = (t' + 1)/2 = 47. So this would be a 47-of-98 threshold scheme (t/n = 48%).

However, with this new threshold signature scheme combined with multisig (Bitcoin should now allow up to 15-of-15 I believe) can let us do better. First I divide the top 98 delegates into 14 disjoint regions each consisting of 7 delegates. For each region, the 7 delegates in that region initialize (7 choose 2) = 21 5-of-5 threshold schemes, one for each of the 21 unique subsets consisting of 5 delegates from the 7 in the region. Through this initialize process, each region should come up with its own threshold public key for that region. The Bitcoin reserve is then a 13-of-14 multisig where the 14 keys are the threshold public keys from each of the 14 regions.

Under this scheme, the worst case scenario for halting the gateway is if 2 regions are unable to generate a threshold signature. For a region to not be able to generate a threshold signature, there must be at least 3 of the 7 delegates in that region that are not participating. So that is a total of 6 delegates, at a minimum, from the top 98 that must be not participating. Therefore, the gateway will not halt if at least 93 of the 98 delegates are participating (n = 98, t' = 93, just like in the previous version stated above). However, the previous version had a t = 47, while this version has much better security properties. In the worst case scenario, it takes 13 regions to generate signatures for a malicious transaction and each of these regions would generate the signature with the minimum 5 delegates participating in the threshold signature scheme for each region. So that is a minimum of 65 delegates that need to collude to compromise the reserve (t = 65, t/n = 66.3%). This is much better than in the previous version stated above. In the previous version a colluding group of at least 48% of the top 98 delegates could compromise the reserve, but in this version a colluding group of at least 66% of the top 98 delegates could compromise the reserve.

Another option is to make the multisig 11-of-14 and the threshold scheme of each region 6-of-7. In this case halting the gateway requires at least 4 regions to be unable to generate a threshold signature and each region requires 2 non-cooperating delegates, which would at a minimum require 8 non-cooperating delegates. This means if at least 91 of the 98 delegates are participating the gateway with not halt (n = 98, t' = 91). The minimum number of colluding delegates required to compromise the reserve would be 66 in this case (t = 66, t/n = 67.3%). You can see the table of tuples (t/n, t'/n) for a variety of possible solutions using a similar scheme here.

Finally, what about computational efficiency. First, requiring the delegates in each 5-of-5 region to store 21x the number of secrets is not a big deal (it is even less of an issue to store 7x in the case of 6-of-6 regions). Also doing 21x (or 7x in the 6-of-6 case) computations in parallel each time the number of delegates in that region changes is also no big deal. The more interesting metric is how long it takes to generate signatures for the 5-of-5 or 6-of-6 threshold scheme. It would take only 3*5 - 2 = 13 rounds to generate the signature for each 5-of-5 region and only 3*6 - 2 = 16 rounds to generate the signature of each 6-of-6 region. The amount of time it would take to do this (according to the paper) is approximately 10 seconds for the 5-of-5 regions and less than 20 seconds for the 6-of-6 regions.
« Last Edit: March 08, 2015, 10:24:21 PM by arhag »

Offline arhag

  • Hero Member
  • *****
  • Posts: 1213
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: Threshold signatures for Bitcoin wallets are finally here
« Reply #4 on: March 09, 2015, 05:03:18 AM »
Alright, I have another approach that uses this threshold scheme, the previous ECDSA threshold scheme (with the t' = 2*t - 1 limitation), and Bitcoin's multisig. This scheme is more flexible. When delegate participation is at least 93, the reserve cannot be compromised by a colluding group of less than 49 delegates. If delegate participation drops below 93, it is possible (under normal circumstances) to enter a recovery mode in which the reserve can be recovered by at least 73 participating delegates (however, between the time of entering this recovery mode and fully recovering the reserve, the reserve is vulnerable to a colluding group of 28 delegates).

Procedure:

Segment the top 100 delegates into 10 disjoint regions of 10 delegates each. Each region can use a 7-of-10 threshold scheme (the one without the t' = 2*t - 1 limitation). This requires setting up (10 choose 7) = 120 different 7-of-7 subsets for each region. Since signature generation in each region will require a 7-of-7 scheme, it means it will require 19 rounds and take approximately 30 seconds.

If 97 of the top 100 delegates participate in a threshold signature scheme (the old t' = 2*t - 1 limited one) to create a backup key, it means 49 of the top 100 delegates can collude to recover the backup private key.

We can require a 9-of-15 multisig to protect the reserve where 10 of the keys are the threshold public keys for each region and the remaining 5 keys are copies of the backup key.

If the right 49 delegates collude they can generate 7 signatures corresponding to 7 of the first 10 keys in the multisig, as well as recover the backup key for a total of 8 signatures corresponding to 12 of the 15 keys (this satisfies the 9-of-15 multisig). However, if any 48 of the top 100 delegates collude they can only generate 6 signatures corresponding to 6 of the first 10 keys in the multisig and they cannot reconstruct the backup key and therefore do not have the necessary signatures to compromise the reserve.

Under normal operation, the backup key should not be used. In this case all 9 signatures must come from regions. In the worst case scenario (in terms of halting the gateway), all 10 regions could have at least 6 participating delegates each (total of 60 so far) and in addition 8 of these 10 would each have all 10 participating delegates. This gives a total of 92 participating delegates but only 8 signatures. To generate the last signature under normal operation would require one more participating delegate for a total of 93 of the top 100 delegates participating.

However, under fallback operation the backup key could be recovered and so only 4 signatures corresponding to the first ten keys would be needed. In the worst case scenario (in terms of halting the gateway), all 10 regions could have at least 6 participating delegates each (total of 60 so far) and in addition 3 of these 10 would each have all 10 participating delegates. This gives a total of 72 participating delegates but only 3 signatures. To generate the last signature one more participating delegates would be needed for a total of 73 of the top 100 delegates participating. Also, when one of the chosen delegates is able to recover the backup private key this delegate could collude with a minimum of 27 other delegates to compromise the reserve. Thus in fallback mode the minimum number of colluding delegates needed to compromise the reserve is actually 28 not 49.

Finally, if it was not possible to get at least 97 of the top 100 delegates to participate in the generation of the backup key, then this scheme must fallback to using a 7-of-10 multisig instead where the 10 keys are again the threshold public keys for each region. In this case, if less than 85 of the top 100 delegates are participating, the reserve could potentially be stuck. Also, it would take a minimum of 49 of the top 100 delegates to collude to compromise the reserve.

Summary:

As long as the backup private key is never reconstructed (only needs to happen during fallback operation), then it is not possible for less than 49 of the top 100 delegates to ever compromise the reserve by colluding together. If the private key is reconstructed during fallback operation, then 28 colluding delegates of the top 100 delegates could potentially compromise the reserve if the private key was reconstructed on the machine of a delegate that was one of the colluding 28.

There are three different modes of operation: normal mode, no-fallback-available mode, fallback-activated mode. There is a minimum number of participating delegates for each mode that will guarantee that the gateway will be able to function (below that number it is possible, but not necessarily likely, that the gateway will halt unless the fallback operation is activated if possible). Under normal mode, if at least 93 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, it is possible to active fallback operation). Under no-fallback-available-mode, if at least 85 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, there is no fallback to rely on). Under fallback-activate mode, if at least 73 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, there is no additional fallback to rely on).

When initiating the scheme, normally the keys and multisig will be set up to allow normal mode of operation. This however requires at least 97 of the (new) top 100 delegates to participate in the set up process for the keys each time the set of top 100 delegates changes. If this is not possible at the time of a change to the set of top 100 delegates, then the keys and multisig will be set up (with the new top 100 delegates) to allow a no-fallback-available mode of operation. During the no-fallback-available mode, if at any time at least 97 of the top 100 delegates become available (even without the set of top 100 delegates changing) the keys and multisig can be updated (and the Bitcoin reserve moved) to upgrade the mode of operation back to normal mode.

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 11958
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BTS: xeroc
  • GitHub: xeroc
Re: Threshold signatures for Bitcoin wallets are finally here
« Reply #5 on: March 09, 2015, 07:05:31 AM »
Alright, I have another approach that uses this threshold scheme, the previous ECDSA threshold scheme (with the t' = 2*t - 1 limitation), and Bitcoin's multisig. This scheme is more flexible. When delegate participation is at least 93, the reserve cannot be compromised by a colluding group of less than 49 delegates. If delegate participation drops below 93, it is possible (under normal circumstances) to enter a recovery mode in which the reserve can be recovered by at least 73 participating delegates (however, between the time of entering this recovery mode and fully recovering the reserve, the reserve is vulnerable to a colluding group of 28 delegates).

Procedure:

Segment the top 100 delegates into 10 disjoint regions of 10 delegates each. Each region can use a 7-of-10 threshold scheme (the one without the t' = 2*t - 1 limitation). This requires setting up (10 choose 7) = 120 different 7-of-7 subsets for each region. Since signature generation in each region will require a 7-of-7 scheme, it means it will require 19 rounds and take approximately 30 seconds.

If 97 of the top 100 delegates participate in a threshold signature scheme (the old t' = 2*t - 1 limited one) to create a backup key, it means 49 of the top 100 delegates can collude to recover the backup private key.

We can require a 9-of-15 multisig to protect the reserve where 10 of the keys are the threshold public keys for each region and the remaining 5 keys are copies of the backup key.

If the right 49 delegates collude they can generate 7 signatures corresponding to 7 of the first 10 keys in the multisig, as well as recover the backup key for a total of 8 signatures corresponding to 12 of the 15 keys (this satisfies the 9-of-15 multisig). However, if any 48 of the top 100 delegates collude they can only generate 6 signatures corresponding to 6 of the first 10 keys in the multisig and they cannot reconstruct the backup key and therefore do not have the necessary signatures to compromise the reserve.

Under normal operation, the backup key should not be used. In this case all 9 signatures must come from regions. In the worst case scenario (in terms of halting the gateway), all 10 regions could have at least 6 participating delegates each (total of 60 so far) and in addition 8 of these 10 would each have all 10 participating delegates. This gives a total of 92 participating delegates but only 8 signatures. To generate the last signature under normal operation would require one more participating delegate for a total of 93 of the top 100 delegates participating.

However, under fallback operation the backup key could be recovered and so only 4 signatures corresponding to the first ten keys would be needed. In the worst case scenario (in terms of halting the gateway), all 10 regions could have at least 6 participating delegates each (total of 60 so far) and in addition 3 of these 10 would each have all 10 participating delegates. This gives a total of 72 participating delegates but only 3 signatures. To generate the last signature one more participating delegates would be needed for a total of 73 of the top 100 delegates participating. Also, when one of the chosen delegates is able to recover the backup private key this delegate could collude with a minimum of 27 other delegates to compromise the reserve. Thus in fallback mode the minimum number of colluding delegates needed to compromise the reserve is actually 28 not 49.

Finally, if it was not possible to get at least 97 of the top 100 delegates to participate in the generation of the backup key, then this scheme must fallback to using a 7-of-10 multisig instead where the 10 keys are again the threshold public keys for each region. In this case, if less than 85 of the top 100 delegates are participating, the reserve could potentially be stuck. Also, it would take a minimum of 49 of the top 100 delegates to collude to compromise the reserve.

Summary:

As long as the backup private key is never reconstructed (only needs to happen during fallback operation), then it is not possible for less than 49 of the top 100 delegates to ever compromise the reserve by colluding together. If the private key is reconstructed during fallback operation, then 28 colluding delegates of the top 100 delegates could potentially compromise the reserve if the private key was reconstructed on the machine of a delegate that was one of the colluding 28.

There are three different modes of operation: normal mode, no-fallback-available mode, fallback-activated mode. There is a minimum number of participating delegates for each mode that will guarantee that the gateway will be able to function (below that number it is possible, but not necessarily likely, that the gateway will halt unless the fallback operation is activated if possible). Under normal mode, if at least 93 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, it is possible to active fallback operation). Under no-fallback-available-mode, if at least 85 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, there is no fallback to rely on). Under fallback-activate mode, if at least 73 of the top 100 delegates are participating then the gateway is guaranteed to continue operating (if this is not true and the gateway is stuck, there is no additional fallback to rely on).

When initiating the scheme, normally the keys and multisig will be set up to allow normal mode of operation. This however requires at least 97 of the (new) top 100 delegates to participate in the set up process for the keys each time the set of top 100 delegates changes. If this is not possible at the time of a change to the set of top 100 delegates, then the keys and multisig will be set up (with the new top 100 delegates) to allow a no-fallback-available mode of operation. During the no-fallback-available mode, if at any time at least 97 of the top 100 delegates become available (even without the set of top 100 delegates changing) the keys and multisig can be updated (and the Bitcoin reserve moved) to upgrade the mode of operation back to normal mode.
wow .. I am impressed! +5%

Funny thing is, if you take a look from the outside, we can take bitcoin tech and apply it where bitcoin cannot compete :)

When I am done with my PhD I need to read most of you posts again ..
Give BitShares a try! Use the http://testnet.bitshares.eu provided by http://bitshares.eu powered by ChainSquad GmbH

 

Google+