* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
@ 2014-04-03 12:41 Nikita Schmidt
2014-04-03 21:42 ` Matt Whitlock
0 siblings, 1 reply; 90+ messages in thread
From: Nikita Schmidt @ 2014-04-03 12:41 UTC (permalink / raw)
To: bitcoin-development
Matt Whitlock wrote:
> Okay, you've convinced me. However, it looks like the consensus here is
> that my BIP is unneeded, so I'm not sure it would be worth the effort
> for me to improve it with your suggestions.
I need your BIP.
We are going to implement SSS and we'd rather stick with something
publicly discussed, even if it has not formally become a BIP, than
invent our own stuff.
I'll go ahead and comment on the current proposal here. BIP or no
BIP, I propose to finalise this spec anyway for those who want to
implement SSS now or in future.
I agree with the recently mentioned suggestion to make non-essential
metadata, namely key fingerprint and degree (M), optional. Their
4-byte and 1-byte fields can be added individually at an
implementation's discretion. During decoding, the total length will
determine which fields are included.
For example, as a compromise between usability and security, the
metadata can be supplied out-of-band, like in plain text accompanying
the Base-58 encoded share.
Encoding for the testnet is not specified.
Speaking of encoding, is it not wasteful to allocate three different
application/version bytes just for the sake of always starting with
'SS'? It would be OK if it were accepted as a BIP, but merely as a
de-facto standard it should aim at minimising future chances of
collision.
I'd add a clause allowing the use of random coefficients instead of
deterministic, as long as the implementation guarantees to never make
another set of shares for the same private key or master seed.
What about using the same P256 prime as for the elliptic curve? Just
for consistency's sake.
Also, I'm somewhat inclined towards using the actual x instead of j in
the encoding. I find it more direct and straightforward to encode the
pair (x, y). And x=0 can denote a special case for future extensions.
There is no technical reason behind this, it's just for (subjective)
clarity and consistency.
^ permalink raw reply [flat|nested] 90+ messages in thread* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-03 12:41 [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys Nikita Schmidt @ 2014-04-03 21:42 ` Matt Whitlock 2014-04-04 13:51 ` Nikita Schmidt 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-03 21:42 UTC (permalink / raw) To: bitcoin-development On Thursday, 3 April 2014, at 4:41 pm, Nikita Schmidt wrote: > I agree with the recently mentioned suggestion to make non-essential > metadata, namely key fingerprint and degree (M), optional. Their > 4-byte and 1-byte fields can be added individually at an > implementation's discretion. During decoding, the total length will > determine which fields are included. The fingerprint field, Hash16(K), is presently specified as a 16-bit field. Rationale: There is no need to consume 4 bytes just to allow shares to be grouped together. And if someone has more than 100 different secrets, they probably have a good system for managing their shares and won't need the hash anyway. > Encoding for the testnet is not specified. Hmm, is that actually needed? > Speaking of encoding, is it not wasteful to allocate three different > application/version bytes just for the sake of always starting with > 'SS'? It would be OK if it were accepted as a BIP, but merely as a > de-facto standard it should aim at minimising future chances of > collision. I agree on principle, however I think the more user-acceptable behavior is for all base58-encoded Shamir shares to begin with a common prefix, such as "SS". Users are accustomed to relying on the prefix of the base58 encoding to understand what the object is: "1" for mainnet pubkey hash, "3" for mainnet script hash, "5" for uncompressed private key, "P" for passphrase-protected private key, etc. > I'd add a clause allowing the use of random coefficients instead of > deterministic, as long as the implementation guarantees to never make > another set of shares for the same private key or master seed. I'm not sure that's necessary, as this is an Informational BIP. Implementations are free to ignore it. Shares with randomly selected coefficients would work just fine in a share joiner that conforms to the BIP, so I would expect implementors to feel free to ignore the deterministic formula and use randomly selected coefficients. > What about using the same P256 prime as for the elliptic curve? Just > for consistency's sake. The initial draft of this BIP used the cyclic order (n) of the generator point on the secp256k1 elliptic curve as the modulus. The change to the present scheme was actually done for consistency's sake, so all sizes of secret can use a consistently defined modulus. > Also, I'm somewhat inclined towards using the actual x instead of j in > the encoding. I find it more direct and straightforward to encode the > pair (x, y). And x=0 can denote a special case for future extensions. > There is no technical reason behind this, it's just for (subjective) > clarity and consistency. There is a technical reason for encoding j rather than x[j]: it allows for the first 256 shares to be encoded, rather than only the first 255 shares. If you want a sentinel value reserved for future extensions, then you might take notice that 0xFFFF is an invalid key fingerprint, along with several other values, and also that 0xFF is an unusable value of M−2, as that would imply M=257, but the scheme can only encode up to 256 shares, so one would never have enough shares to meet the threshold. I considered having the two optional fields be mandatory and allowing 0xFFFF and 0xFF as "redacted" field values, but I like allowing the shares to be shorter if the optional fields are omitted. (Imagine engraving Shamir secret shares onto metal bars by hand with an engraving tool. Fewer characters is better!) ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-03 21:42 ` Matt Whitlock @ 2014-04-04 13:51 ` Nikita Schmidt 2014-04-04 14:14 ` Gregory Maxwell 2014-04-04 16:03 ` Matt Whitlock 0 siblings, 2 replies; 90+ messages in thread From: Nikita Schmidt @ 2014-04-04 13:51 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development On 4 April 2014 01:42, Matt Whitlock <bip@mattwhitlock•name> wrote: > The fingerprint field, Hash16(K), is presently specified as a 16-bit field. Rationale: There is no need to consume 4 bytes just to allow shares to be grouped together. And if someone has more than 100 different secrets, they probably have a good system for managing their shares and won't need the hash anyway. Right, of course. Sorry, I didn't notice there was an update. Two bytes are plenty. I'm worried however about the dependency on SHA-512, which may be stretching it for a tiny embedded application. The other uses of HashL can be avoided. We are balancing here between consistency with the rest of this proposal, where everything is done via HashL, and consistency with the general practice of generating fingerprints with SHA-256, like in Base58Check. Similarly, re-assembly software suddenly finds itself having to implement Hash16 just to check this particular fingerprint. So I'd vote for a more traditional approach here, also considering that HashL is designed specifically to generate numbers in a finite field. > >> Encoding for the testnet is not specified. > > Hmm, is that actually needed? It's been a tradition to support it in general, however I guess it's not really needed here. I'm happy without a dedicated testnet encoding. > >> Speaking of encoding, is it not wasteful to allocate three different >> application/version bytes just for the sake of always starting with >> 'SS'? It would be OK if it were accepted as a BIP, but merely as a >> de-facto standard it should aim at minimising future chances of >> collision. > > I agree on principle, however I think the more user-acceptable behavior is for all base58-encoded Shamir shares to begin with a common prefix, such as "SS". Users are accustomed to relying on the prefix of the base58 encoding to understand what the object is: "1" for mainnet pubkey hash, "3" for mainnet script hash, "5" for uncompressed private key, "P" for passphrase-protected private key, etc. Yes, "5" for uncompressed private key and "K" or "L" for compressed private key. One A/VB and three prefixes in base58. Am I the only one to see this as a counter-example? However, thinking about this, I can find logic in wanting to stabilise text prefixes at a cost of six A/V bytes (as per the latest spec). There are only 58 first characters versus 256 AVBs, so we should rather be saving the former. >> What about using the same P256 prime as for the elliptic curve? Just >> for consistency's sake. > > The initial draft of this BIP used the cyclic order (n) of the generator point on the secp256k1 elliptic curve as the modulus. The change to the present scheme was actually done for consistency's sake, so all sizes of secret can use a consistently defined modulus. Fair enough. Although I would have chosen the field order (p) simply because that's how all arithmetic already works in bitcoin. One field for everybody. It's also very close to 2^256, although still smaller than your maximum prime. Now of course with different bit lengths we have to pick one consistency over others. > >> Also, I'm somewhat inclined towards using the actual x instead of j in >> the encoding. I find it more direct and straightforward to encode the >> pair (x, y). And x=0 can denote a special case for future extensions. >> There is no technical reason behind this, it's just for (subjective) >> clarity and consistency. > > There is a technical reason for encoding j rather than x[j]: it allows for the first 256 shares to be encoded, rather than only the first 255 shares. Wow, big deal. It's hard to imagine anyone needing exactly 256 shares, but who knows. And with j = x (starting from 1) we'd get user-friendly share numbering and simpler formulas in the spec and possibly in the implementation, with no off-by-one stuff. And M instead of M-2... > > If you want a sentinel value reserved for future extensions, then you might take notice that 0xFFFF is an invalid key fingerprint, along with several other values, and also that 0xFF is an unusable value of M-2, as that would imply M=257, but the scheme can only encode up to 256 shares, so one would never have enough shares to meet the threshold. I considered having the two optional fields be mandatory and allowing 0xFFFF and 0xFF as "redacted" field values, but I like allowing the shares to be shorter if the optional fields are omitted. (Imagine engraving Shamir secret shares onto metal bars by hand with an engraving tool. Fewer characters is better!) Exactly. Thank you. Without these fields, a secret share still fits into a 29x29 QR code. Add one more byte and it'll need a 33x33. Imagine engraving that onto metal plates! Or the hassle of going above 32 bits per line in a tiny embedded system. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 13:51 ` Nikita Schmidt @ 2014-04-04 14:14 ` Gregory Maxwell 2014-04-04 16:05 ` Matt Whitlock 2014-04-04 16:03 ` Matt Whitlock 1 sibling, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-04 14:14 UTC (permalink / raw) To: Nikita Schmidt; +Cc: bitcoin-development On Fri, Apr 4, 2014 at 6:51 AM, Nikita Schmidt <nikita@megiontechnologies•com> wrote: > Fair enough. Although I would have chosen the field order (p) simply > because that's how all arithmetic already works in bitcoin. One field > for everybody. It's also very close to 2^256, although still smaller > than your maximum prime. Now of course with different bit lengths we > have to pick one consistency over others. Operation mod the group order is how secret keys must be combined in type-2 private derivation for BIP-32. It's also absolutely essential if you want to build a secret sharing scheme in which the shares are usable for threshold ECDSA. I still repeat my concern that any private key secret sharing scheme really ought to be compatible with threshold ECDSA, otherwise we're just going to have another redundant specification. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 14:14 ` Gregory Maxwell @ 2014-04-04 16:05 ` Matt Whitlock 2014-04-04 16:25 ` Gregory Maxwell 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-04 16:05 UTC (permalink / raw) To: Gregory Maxwell; +Cc: bitcoin-development On Friday, 4 April 2014, at 7:14 am, Gregory Maxwell wrote: > I still repeat my concern that any private key secret sharing scheme > really ought to be compatible with threshold ECDSA, otherwise we're > just going to have another redundant specification. I have that concern too, but then how can we support secrets of sizes other than 256 bits? A likely use case for this BIP (even more likely than using it to decompose Bitcoin private keys) is using it to decompose BIP32 master seeds, which can be 512 bits in size. We can't use secp256k1_n as the modulus there. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 16:05 ` Matt Whitlock @ 2014-04-04 16:25 ` Gregory Maxwell 2014-04-04 16:36 ` Matt Whitlock 0 siblings, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-04 16:25 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development On Fri, Apr 4, 2014 at 9:05 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > On Friday, 4 April 2014, at 7:14 am, Gregory Maxwell wrote: >> I still repeat my concern that any private key secret sharing scheme >> really ought to be compatible with threshold ECDSA, otherwise we're >> just going to have another redundant specification. > > I have that concern too, but then how can we support secrets of sizes other than 256 bits? A likely use case for this BIP (even more likely than using it to decompose Bitcoin private keys) is using it to decompose BIP32 master seeds, which can be 512 bits in size. We can't use secp256k1_n as the modulus there. Well, if you're not doing anything homorphic with the result the computation should probably be over a small field (for computational efficiency and implementation simplicity reasons) and the data split up, this also makes it easier to deal with many different data sizes, since the various sizes will more efficiently divide into the small field. The field only needs to be large enough to handle the number of distinct shares you wish to issue, so even an 8 bit field would probably be adequate (and yields some very simple table based implementations). If that route is taken, rather than encoding BIP32 master keys, it would probably be prudent to encode the encryption optional version https://bitcointalk.org/index.php?topic=258678.0 ... and if we're talking about a new armored private key format then perhaps we should be talking about Mark Friedenbach's error correcting capable scheme: https://gist.github.com/maaku/8996338#file-bip-ecc32-mediawiki (though it would be nicer if we could find a decoding scheme that supported list decoding without increasing the complexity of a basic implementation, since an advanced recovery tool could make good use of a list decode) I'd think that changing to a small field with a simple implementation, and encoding the form with encryption, etc. probably makes it distinct enough from an implementation of ECDSA thresholding that redundancy isn't a problem. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 16:25 ` Gregory Maxwell @ 2014-04-04 16:36 ` Matt Whitlock 2014-04-04 17:08 ` Gregory Maxwell 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-04 16:36 UTC (permalink / raw) To: Gregory Maxwell; +Cc: bitcoin-development On Friday, 4 April 2014, at 9:25 am, Gregory Maxwell wrote: > On Fri, Apr 4, 2014 at 9:05 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > > On Friday, 4 April 2014, at 7:14 am, Gregory Maxwell wrote: > >> I still repeat my concern that any private key secret sharing scheme > >> really ought to be compatible with threshold ECDSA, otherwise we're > >> just going to have another redundant specification. > > > > I have that concern too, but then how can we support secrets of sizes other than 256 bits? A likely use case for this BIP (even more likely than using it to decompose Bitcoin private keys) is using it to decompose BIP32 master seeds, which can be 512 bits in size. We can't use secp256k1_n as the modulus there. > > Well, if you're not doing anything homorphic with the result the > computation should probably be over a small field (for computational > efficiency and implementation simplicity reasons) and the data split > up, this also makes it easier to deal with many different data sizes, > since the various sizes will more efficiently divide into the small > field. The field only needs to be large enough to handle the number > of distinct shares you wish to issue, so even an 8 bit field would > probably be adequate (and yields some very simple table based > implementations). Are you proposing to switch from prime fields to a binary field? Because if you're going to "break up" a secret into little pieces, you can't assume that every piece of the secret will be strictly less than some 8-bit prime modulus. And if you're going to do a base conversion, then you have to do arbitrary-precision integer math anyway, so I don't see that the small field really saves you any code. > If that route is taken, rather than encoding BIP32 master keys, it > would probably be prudent to encode the encryption optional version > https://bitcointalk.org/index.php?topic=258678.0 ... and if we're > talking about a new armored private key format then perhaps we should > be talking about Mark Friedenbach's error correcting capable scheme: > https://gist.github.com/maaku/8996338#file-bip-ecc32-mediawiki > (though it would be nicer if we could find a decoding scheme that > supported list decoding without increasing the complexity of a basic > implementation, since an advanced recovery tool could make good use of > a list decode) Weren't you just clamoring for implementation *simplicity* in your previous paragraph? :) ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 16:36 ` Matt Whitlock @ 2014-04-04 17:08 ` Gregory Maxwell 2014-04-04 17:16 ` Matt Whitlock 0 siblings, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-04 17:08 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development On Fri, Apr 4, 2014 at 9:36 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > Are you proposing to switch from prime fields to a binary field? Because if you're going to "break up" a secret into little pieces, you can't assume that every piece of the secret will be strictly less than some 8-bit prime modulus. And if you're going to do a base conversion, then you have to do arbitrary-precision integer math anyway, so I don't see that the small field really saves you any code. Yes, I'm proposing using the binary extension field of GF(2^8). There are many secret sharing and data integrity applications available already operating over GF(2^8) so you can go compare implementation approaches without having to try them our yourself. Obviously anything efficiently encoded as bytes will efficiently encode over GF(2^8). > Weren't you just clamoring for implementation *simplicity* in your previous paragraph? :) I do think there is a material difference in complexity that comes in layers rather than at a single point. It's much easier to implement a complex thing that has many individually testable parts then a single complex part. (Implementing arithmetic mod some huge P is quite a bit of work unless you're using some very high level language with integrated bignums— and are comfortable hoping that their bignums are sufficiently consistent with the spec). ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 17:08 ` Gregory Maxwell @ 2014-04-04 17:16 ` Matt Whitlock 2014-04-04 17:51 ` Gregory Maxwell 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-04 17:16 UTC (permalink / raw) To: Gregory Maxwell; +Cc: bitcoin-development On Friday, 4 April 2014, at 10:08 am, Gregory Maxwell wrote: > On Fri, Apr 4, 2014 at 9:36 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > > Are you proposing to switch from prime fields to a binary field? Because if you're going to "break up" a secret into little pieces, you can't assume that every piece of the secret will be strictly less than some 8-bit prime modulus. And if you're going to do a base conversion, then you have to do arbitrary-precision integer math anyway, so I don't see that the small field really saves you any code. > > Yes, I'm proposing using the binary extension field of GF(2^8). There > are many secret sharing and data integrity applications available > already operating over GF(2^8) so you can go compare implementation > approaches without having to try them our yourself. Obviously anything > efficiently encoded as bytes will efficiently encode over GF(2^8). Honestly, that sounds a lot more complicated than what I have now. I made my current implementation because I just wanted something simple that would let me divide a private key into shares for purposes of dissemination to my next of kin et al. > > Weren't you just clamoring for implementation *simplicity* in your previous paragraph? :) > > I do think there is a material difference in complexity that comes in > layers rather than at a single point. It's much easier to implement a > complex thing that has many individually testable parts then a single > complex part. (Implementing arithmetic mod some huge P is quite a bit > of work unless you're using some very high level language with > integrated bignums— and are comfortable hoping that their bignums are > sufficiently consistent with the spec). I already have a fairly polished implementation of my BIP, and it's not written in a "very high-level language"; it's C++, and the parts that do the big-integer arithmetic are basically C. I'm using the GMP library: very straightforward, very reliable, very fast. Do you have a use case in mind that would benefit from byte-wise operations rather than big-integer operations? I mean, I guess if you were trying to implement this BIP on a PIC microcontroller, it might be nice to process the secret in smaller bites. (No pun intended.) But I get this feeling that you're only pushing me away from the present incarnation of my proposal because you think it's too similar (but not quite similar enough) to a threshold ECDSA key scheme. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 17:16 ` Matt Whitlock @ 2014-04-04 17:51 ` Gregory Maxwell 2014-04-04 18:53 ` Matt Whitlock 0 siblings, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-04 17:51 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development On Fri, Apr 4, 2014 at 10:16 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > Honestly, that sounds a lot more complicated than what I have now. I made my current implementation because I just wanted something simple that would let me divide a private key into shares for purposes of dissemination to my next of kin et al. I suggest you go look at some of the other secret sharing implementations that use GF(2^8), they end up just being a couple of dozen lines of code. Pretty simple stuff, and they work efficiently for all sizes of data, there are implementations in a multitude of languages. There are a whole bunch of these. > I already have a fairly polished implementation of my BIP, and it's not written in a "very high-level language"; it's C++, and the parts that do the big-integer arithmetic are basically C. I'm using the GMP library: very straightforward, very reliable, very fast. With respect for the awesome work that GMP is— It's 250,000 lines of LGPLed code. It's not just "pic microcontrollers" that would find that scale of a dependency unwelcome. > Do you have a use case in mind that would benefit from byte-wise operations rather than big-integer operations? I mean, I guess if you were trying to implement this BIP on a PIC microcontroller, it might be nice to process the secret in smaller bites. (No pun intended.) But I get this feeling that you're only pushing me away from the present incarnation of my proposal because you think it's too similar (but not quite similar enough) to a threshold ECDSA key scheme. It lets you efficiently scale to any size data being encoded without extra overhead or having additional primes. It can be compactly implemented in Javascript (there are several implementations you can find if you google), it shouldn't be burdensome to implement on a device like a trezor (much less a real microcontroller). And yea, sure, it's distinct from the implementation you'd use for threshold signing. A threshold singing one would lack the size agility or the easy of implementation on limited devices. So I do think that if there is to be two it would be good to gain the advantages that can't be achieved in an threshold ECDSA compatible approach. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 17:51 ` Gregory Maxwell @ 2014-04-04 18:53 ` Matt Whitlock 0 siblings, 0 replies; 90+ messages in thread From: Matt Whitlock @ 2014-04-04 18:53 UTC (permalink / raw) To: Gregory Maxwell; +Cc: bitcoin-development On Friday, 4 April 2014, at 10:51 am, Gregory Maxwell wrote: > On Fri, Apr 4, 2014 at 10:16 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > > Honestly, that sounds a lot more complicated than what I have now. I made my current implementation because I just wanted something simple that would let me divide a private key into shares for purposes of dissemination to my next of kin et al. > > I suggest you go look at some of the other secret sharing > implementations that use GF(2^8), they end up just being a couple of > dozen lines of code. Pretty simple stuff, and they work efficiently > for all sizes of data, there are implementations in a multitude of > languages. There are a whole bunch of these. Okay, I will. > > Do you have a use case in mind that would benefit from byte-wise operations rather than big-integer operations? I mean, I guess if you were trying to implement this BIP on a PIC microcontroller, it might be nice to process the secret in smaller bites. (No pun intended.) But I get this feeling that you're only pushing me away from the present incarnation of my proposal because you think it's too similar (but not quite similar enough) to a threshold ECDSA key scheme. > > It lets you efficiently scale to any size data being encoded without > extra overhead or having additional primes. It can be compactly > implemented in Javascript (there are several implementations you can > find if you google), it shouldn't be burdensome to implement on a > device like a trezor (much less a real microcontroller). Those are fair points. > And yea, sure, it's distinct from the implementation you'd use for > threshold signing. A threshold singing one would lack the size agility > or the easy of implementation on limited devices. So I do think that > if there is to be two it would be good to gain the advantages that > can't be achieved in an threshold ECDSA compatible approach. I agree. I'll look into secret sharing in GF(2^8), but it may take me a few days. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 13:51 ` Nikita Schmidt 2014-04-04 14:14 ` Gregory Maxwell @ 2014-04-04 16:03 ` Matt Whitlock 2014-04-08 0:33 ` Nikita Schmidt 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-04 16:03 UTC (permalink / raw) To: Nikita Schmidt; +Cc: bitcoin-development On Friday, 4 April 2014, at 5:51 pm, Nikita Schmidt wrote: > On 4 April 2014 01:42, Matt Whitlock <bip@mattwhitlock•name> wrote: > > The fingerprint field, Hash16(K), is presently specified as a 16-bit field. Rationale: There is no need to consume 4 bytes just to allow shares to be grouped together. And if someone has more than 100 different secrets, they probably have a good system for managing their shares and won't need the hash anyway. > > Right, of course. Sorry, I didn't notice there was an update. Two > bytes are plenty. > > I'm worried however about the dependency on SHA-512, which may be > stretching it for a tiny embedded application. The other uses of > HashL can be avoided. We are balancing here between consistency with > the rest of this proposal, where everything is done via HashL, and > consistency with the general practice of generating fingerprints with > SHA-256, like in Base58Check. I'd be fine with changing the key fingerprint algorithm to something else. Do you like CRC16? > >> Speaking of encoding, is it not wasteful to allocate three different > >> application/version bytes just for the sake of always starting with > >> 'SS'? It would be OK if it were accepted as a BIP, but merely as a > >> de-facto standard it should aim at minimising future chances of > >> collision. > > > > I agree on principle, however I think the more user-acceptable behavior is for all base58-encoded Shamir shares to begin with a common prefix, such as "SS". Users are accustomed to relying on the prefix of the base58 encoding to understand what the object is: "1" for mainnet pubkey hash, "3" for mainnet script hash, "5" for uncompressed private key, "P" for passphrase-protected private key, etc. > > Yes, "5" for uncompressed private key and "K" or "L" for compressed > private key. One A/VB and three prefixes in base58. Am I the only > one to see this as a counter-example? > > However, thinking about this, I can find logic in wanting to stabilise > text prefixes at a cost of six A/V bytes (as per the latest spec). > There are only 58 first characters versus 256 AVBs, so we should > rather be saving the former. The type of a base58-encoded object is determined not only by the application/version byte but by the payload length as well. For example, a base58-encoded object with an application/version byte of 0x80 but a payload length of 16 bytes would not be mistakable for a Bitcoin private key, even though AVB 0x80 does denote a Bitcoin private key when the payload length is 32 or 33 bytes. So it's not as simple as saying that this proposal costs 6 AVBs. It really costs one AVB for 18-byte payloads, one AVB for 21-byte payloads, one AVB for 34-byte payloads, one AVB fo 37-byte payloads, one AVB for 66-byte payloads, and one AVB for 69-byte payloads. > >> What about using the same P256 prime as for the elliptic curve? Just > >> for consistency's sake. > > > > The initial draft of this BIP used the cyclic order (n) of the generator point on the secp256k1 elliptic curve as the modulus. The change to the present scheme was actually done for consistency's sake, so all sizes of secret can use a consistently defined modulus. > > Fair enough. Although I would have chosen the field order (p) simply > because that's how all arithmetic already works in bitcoin. One field > for everybody. It's also very close to 2^256, although still smaller > than your maximum prime. Now of course with different bit lengths we > have to pick one consistency over others. As Gregory Maxwell pointed out, you can't use p when you're dealing with private keys, as that is the order of the finite field over which the elliptic curve is defined, but private keys are not points on that curve; a private key is a scalar number of times to multiply the generator point. That means you have to use the order of the generator point as the modulus when working with private keys. > >> Also, I'm somewhat inclined towards using the actual x instead of j in > >> the encoding. I find it more direct and straightforward to encode the > >> pair (x, y). And x=0 can denote a special case for future extensions. > >> There is no technical reason behind this, it's just for (subjective) > >> clarity and consistency. > > > > There is a technical reason for encoding j rather than x[j]: it allows for the first 256 shares to be encoded, rather than only the first 255 shares. > > Wow, big deal. It's hard to imagine anyone needing exactly 256 > shares, but who knows. And with j = x (starting from 1) we'd get > user-friendly share numbering and simpler formulas in the spec and > possibly in the implementation, with no off-by-one stuff. And M > instead of M-2... It's common for implementation limits to be powers of two. I don't foresee any off-by-one errors, as the spec is clear on the value of each byte in the encoding. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-04 16:03 ` Matt Whitlock @ 2014-04-08 0:33 ` Nikita Schmidt 2014-04-08 0:38 ` Gregory Maxwell 0 siblings, 1 reply; 90+ messages in thread From: Nikita Schmidt @ 2014-04-08 0:33 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development > > I'd be fine with changing the key fingerprint algorithm to something else. Do you like CRC16? > I like CRC16. Do you intend to use it in conjunction with a cryptographic hash? Regarding the choice of fields, any implementation of this BIP will need big integer arithmetic to do base-58 anyway. The operations required for SSS are nearly the same as for base-58 and can probably be done by the same subset of the chosen bignum library. So in fact using GF(2^8) will add complexity to both the BIP and its implementations. However, the maths in GF(2^8) is so simple that this additional complexity can be considered negligible. As a co-author of a bitcoin application running on a real microcontroller (not the sort of big-iron thing Trezor runs on), I was also going to implement my SSS over a 256-bit prime field. (I am not going into 512-bit master seeds at this time.) Uniform processing of secrets of any size (instead of using different primes for different cases) is a valid argument in favour of GF(2^8), though. I have no preference one way or another. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-08 0:33 ` Nikita Schmidt @ 2014-04-08 0:38 ` Gregory Maxwell 2014-04-08 1:46 ` Matt Whitlock 0 siblings, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-08 0:38 UTC (permalink / raw) To: Nikita Schmidt; +Cc: bitcoin-development, Matt Whitlock On Mon, Apr 7, 2014 at 5:33 PM, Nikita Schmidt <nikita@megiontechnologies•com> wrote: > Regarding the choice of fields, any implementation of this BIP will > need big integer arithmetic to do base-58 anyway. Nah, it doesn't. E.g. https://gitorious.org/bitcoin/libblkmaker/source/eb33f9c8e441ffef457a79d76ceed1ea20ab3059:base58.c > However, the maths in GF(2^8) is so simple that this > additional complexity can be considered negligible. [...] > Uniform processing of secrets of any size (instead of using different > primes for different cases) is a valid argument in favour of GF(2^8), > though. I have no preference one way or another. I think this is really one of the bigger selling points. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-08 0:38 ` Gregory Maxwell @ 2014-04-08 1:46 ` Matt Whitlock 2014-04-08 2:07 ` Gregory Maxwell 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-08 1:46 UTC (permalink / raw) To: Gregory Maxwell; +Cc: bitcoin-development On Monday, 7 April 2014, at 5:38 pm, Gregory Maxwell wrote: > On Mon, Apr 7, 2014 at 5:33 PM, Nikita Schmidt > <nikita@megiontechnologies•com> wrote: > > Regarding the choice of fields, any implementation of this BIP will > > need big integer arithmetic to do base-58 anyway. > > Nah, it doesn't. E.g. > https://gitorious.org/bitcoin/libblkmaker/source/eb33f9c8e441ffef457a79d76ceed1ea20ab3059:base58.c That only *decodes* Base58Check. It has no encode function, which would require biginteger division. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-08 1:46 ` Matt Whitlock @ 2014-04-08 2:07 ` Gregory Maxwell 2014-04-08 11:52 ` Matt Whitlock 0 siblings, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-08 2:07 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development On Mon, Apr 7, 2014 at 6:46 PM, Matt Whitlock <bip@mattwhitlock•name> wrote: > On Monday, 7 April 2014, at 5:38 pm, Gregory Maxwell wrote: >> On Mon, Apr 7, 2014 at 5:33 PM, Nikita Schmidt >> <nikita@megiontechnologies•com> wrote: >> > Regarding the choice of fields, any implementation of this BIP will >> > need big integer arithmetic to do base-58 anyway. >> Nah, it doesn't. E.g. >> https://gitorious.org/bitcoin/libblkmaker/source/eb33f9c8e441ffef457a79d76ceed1ea20ab3059:base58.c > That only *decodes* Base58Check. It has no encode function, which would require biginteger division. Yes thats only a decode but the same process (long division with manual carries) works just fine the other way. There is absolutely no need to use big integers for this. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-08 2:07 ` Gregory Maxwell @ 2014-04-08 11:52 ` Matt Whitlock 2014-04-10 22:31 ` Nikita Schmidt 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-08 11:52 UTC (permalink / raw) To: Gregory Maxwell; +Cc: bitcoin-development On Monday, 7 April 2014, at 7:07 pm, Gregory Maxwell wrote: > On Mon, Apr 7, 2014 at 6:46 PM, Matt Whitlock <bip@mattwhitlock•name> wrote: > > On Monday, 7 April 2014, at 5:38 pm, Gregory Maxwell wrote: > >> On Mon, Apr 7, 2014 at 5:33 PM, Nikita Schmidt > >> <nikita@megiontechnologies•com> wrote: > >> > Regarding the choice of fields, any implementation of this BIP will > >> > need big integer arithmetic to do base-58 anyway. > >> Nah, it doesn't. E.g. > >> https://gitorious.org/bitcoin/libblkmaker/source/eb33f9c8e441ffef457a79d76ceed1ea20ab3059:base58.c > > That only *decodes* Base58Check. It has no encode function, which would require biginteger division. > > Yes thats only a decode but the same process (long division with > manual carries) works just fine the other way. There is absolutely no > need to use big integers for this. What do you think a big-integer division by a word-sized divisor *is*? Obviously rolling your own is always an option. Are you just saying that Base58 encoding and decoding is easier than Shamir's Secret Sharing because the divisors are small? ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-08 11:52 ` Matt Whitlock @ 2014-04-10 22:31 ` Nikita Schmidt 2014-04-22 8:06 ` Jan Møller 0 siblings, 1 reply; 90+ messages in thread From: Nikita Schmidt @ 2014-04-10 22:31 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development > What do you think a big-integer division by a word-sized divisor *is*? Obviously rolling your own is always an option. Are you just saying that Base58 encoding and decoding is easier than Shamir's Secret Sharing because the divisors are small? Well, yes, to be fair, in fact it is. The small divisor and lack of modulo arithmetic make base-58 encoding and decoding noticeably smaller and easier than Shamir's Secret Sharing over GF(P256). ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-10 22:31 ` Nikita Schmidt @ 2014-04-22 8:06 ` Jan Møller 2014-04-22 8:11 ` Matt Whitlock 2014-04-22 8:15 ` Gregory Maxwell 0 siblings, 2 replies; 90+ messages in thread From: Jan Møller @ 2014-04-22 8:06 UTC (permalink / raw) To: Nikita Schmidt; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 2072 bytes --] This is a very useful BIP, and I am very much looking forward to implementing it in Mycelium, in particular for bip32 wallets. To me this is not about whether to use SSS instead of multisig transactions. In the end you want to protect a secret (be it a HD master seed or a private key) in such a way that you can recover it in case of partial theft/loss. Whether I'll use the master seed to generate keys that are going to be used for multisig transactions is another discussion IMO. A few suggestions: - I think it is very useful to define different prefixes for testnet keys/seeds. As a developer I use the testnet every day, and many of our users use it for trying out new functionality. Mixing up keys meant for testnet and mainnet is bad. - Please allow M=1. From a usability point of view it makes sense to allow the user to select 1 share if that is what he wants. I have no strong opinions of whether to use GF(2^8) over Shamir's Secret Sharing, but the simplicity of GF(2^8) is appealing. - Jan On Fri, Apr 11, 2014 at 12:31 AM, Nikita Schmidt < nikita@megiontechnologies•com> wrote: > > What do you think a big-integer division by a word-sized divisor *is*? > Obviously rolling your own is always an option. Are you just saying that > Base58 encoding and decoding is easier than Shamir's Secret Sharing because > the divisors are small? > > Well, yes, to be fair, in fact it is. The small divisor and lack of > modulo arithmetic make base-58 encoding and decoding noticeably > smaller and easier than Shamir's Secret Sharing over GF(P256). > > > ------------------------------------------------------------------------------ > Put Bad Developers to Shame > Dominate Development with Jenkins Continuous Integration > Continuously Automate Build, Test & Deployment > Start a new project now. Try Jenkins in the cloud. > http://p.sf.net/sfu/13600_Cloudbees > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 2855 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:06 ` Jan Møller @ 2014-04-22 8:11 ` Matt Whitlock 2014-04-22 8:27 ` Jan Møller ` (2 more replies) 2014-04-22 8:15 ` Gregory Maxwell 1 sibling, 3 replies; 90+ messages in thread From: Matt Whitlock @ 2014-04-22 8:11 UTC (permalink / raw) To: jan.moller, bitcoin-development On Tuesday, 22 April 2014, at 10:06 am, Jan Møller wrote: > This is a very useful BIP, and I am very much looking forward to > implementing it in Mycelium, in particular for bip32 wallets. > To me this is not about whether to use SSS instead of multisig > transactions. In the end you want to protect a secret (be it a HD master > seed or a private key) in such a way that you can recover it in case of > partial theft/loss. Whether I'll use the master seed to generate keys that > are going to be used for multisig transactions is another discussion IMO. > > A few suggestions: > - I think it is very useful to define different prefixes for testnet > keys/seeds. As a developer I use the testnet every day, and many of our > users use it for trying out new functionality. Mixing up keys meant for > testnet and mainnet is bad. A fair point. I'll add some prefixes for testnet. > - Please allow M=1. From a usability point of view it makes sense to allow > the user to select 1 share if that is what he wants. How does that make sense? Decomposing a key/seed into 1 share is functionally equivalent to dispensing with the secret sharing scheme entirely. > I have no strong opinions of whether to use GF(2^8) over Shamir's Secret > Sharing, but the simplicity of GF(2^8) is appealing. I'll welcome forks of my draft BIP. I don't really have the inclination to research GF(2^8) secret sharing schemes and write an implementation at the present time, but if someone wants to take my BIP in that direction, then okay. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:11 ` Matt Whitlock @ 2014-04-22 8:27 ` Jan Møller 2014-04-22 8:29 ` Matt Whitlock 2014-04-22 8:35 ` Matt Whitlock 2014-04-22 13:37 ` Nikita Schmidt 2 siblings, 1 reply; 90+ messages in thread From: Jan Møller @ 2014-04-22 8:27 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 762 bytes --] > > > > - Please allow M=1. From a usability point of view it makes sense to > allow > > the user to select 1 share if that is what he wants. > > How does that make sense? Decomposing a key/seed into 1 share is > functionally equivalent to dispensing with the secret sharing scheme > entirely. > > I agree that it may look silly to have just one-of-one share from a technical point of view, but from an end-user point of view there could be reasons for just having one piece of paper to manage. If M can be 1 then the software/hardware doesn't have to support multiple formats, import/export paths + UI (one for SIPA keys in one share, one for HD seeds in one share, one for SIPA keys + HD seeds in multiple shares). Less complexity & more freedom of choice. [-- Attachment #2: Type: text/html, Size: 1093 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:27 ` Jan Møller @ 2014-04-22 8:29 ` Matt Whitlock 2014-04-22 8:39 ` Jan Møller 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-22 8:29 UTC (permalink / raw) To: jan.moller; +Cc: bitcoin-development On Tuesday, 22 April 2014, at 10:27 am, Jan Møller wrote: > > > - Please allow M=1. From a usability point of view it makes sense to > > allow > > > the user to select 1 share if that is what he wants. > > > > How does that make sense? Decomposing a key/seed into 1 share is > > functionally equivalent to dispensing with the secret sharing scheme > > entirely. > > > > > I agree that it may look silly to have just one-of-one share from a > technical point of view, but from an end-user point of view there could be > reasons for just having one piece of paper to manage. If M can be 1 then > the software/hardware doesn't have to support multiple formats, > import/export paths + UI (one for SIPA keys in one share, one for HD seeds > in one share, one for SIPA keys + HD seeds in multiple shares). > > Less complexity & more freedom of choice. Alright. It's a fair argument. Do you agree with encoding M using a bias of -1 so that M up to and including 256 can be encoded in one byte? ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:29 ` Matt Whitlock @ 2014-04-22 8:39 ` Jan Møller 2014-04-22 8:43 ` Matt Whitlock 2014-04-22 9:13 ` Matt Whitlock 0 siblings, 2 replies; 90+ messages in thread From: Jan Møller @ 2014-04-22 8:39 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 1324 bytes --] Necessary Shares = M+1, not a problem I would probably encode N-of-M in 1 byte as I don't see good use cases with more than 17 shares. Anyway, I am fine with it as it is. On Tue, Apr 22, 2014 at 10:29 AM, Matt Whitlock <bip@mattwhitlock•name>wrote: > On Tuesday, 22 April 2014, at 10:27 am, Jan Møller wrote: > > > > - Please allow M=1. From a usability point of view it makes sense to > > > allow > > > > the user to select 1 share if that is what he wants. > > > > > > How does that make sense? Decomposing a key/seed into 1 share is > > > functionally equivalent to dispensing with the secret sharing scheme > > > entirely. > > > > > > > > I agree that it may look silly to have just one-of-one share from a > > technical point of view, but from an end-user point of view there could > be > > reasons for just having one piece of paper to manage. If M can be 1 then > > the software/hardware doesn't have to support multiple formats, > > import/export paths + UI (one for SIPA keys in one share, one for HD > seeds > > in one share, one for SIPA keys + HD seeds in multiple shares). > > > > Less complexity & more freedom of choice. > > Alright. It's a fair argument. Do you agree with encoding M using a bias > of -1 so that M up to and including 256 can be encoded in one byte? > [-- Attachment #2: Type: text/html, Size: 1829 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:39 ` Jan Møller @ 2014-04-22 8:43 ` Matt Whitlock 2014-04-22 8:51 ` Jan Møller 2014-04-22 9:13 ` Matt Whitlock 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-22 8:43 UTC (permalink / raw) To: jan.moller; +Cc: bitcoin-development On Tuesday, 22 April 2014, at 10:39 am, Jan Møller wrote: > Necessary Shares = M+1, not a problem > > I would probably encode N-of-M in 1 byte as I don't see good use cases with > more than 17 shares. Anyway, I am fine with it as it is. I agree that M > 16 is probably not a viable use case for human beings, but machines would probably be able to make use of it. I, for one, welcome our new robot overlords. Also, the byte that encodes M−1 is optional, so if you're concerned about space, you can omit it (and the checksum). ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:43 ` Matt Whitlock @ 2014-04-22 8:51 ` Jan Møller 0 siblings, 0 replies; 90+ messages in thread From: Jan Møller @ 2014-04-22 8:51 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 761 bytes --] I am concerned about space, but more about usability :-) I'll definitely use both M and the checksum. On Tue, Apr 22, 2014 at 10:43 AM, Matt Whitlock <bip@mattwhitlock•name>wrote: > On Tuesday, 22 April 2014, at 10:39 am, Jan Møller wrote: > > Necessary Shares = M+1, not a problem > > > > I would probably encode N-of-M in 1 byte as I don't see good use cases > with > > more than 17 shares. Anyway, I am fine with it as it is. > > I agree that M > 16 is probably not a viable use case for human beings, > but machines would probably be able to make use of it. I, for one, welcome > our new robot overlords. > > Also, the byte that encodes M−1 is optional, so if you're concerned about > space, you can omit it (and the checksum). > [-- Attachment #2: Type: text/html, Size: 1120 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:39 ` Jan Møller 2014-04-22 8:43 ` Matt Whitlock @ 2014-04-22 9:13 ` Matt Whitlock 2014-04-22 11:50 ` Justin A 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-22 9:13 UTC (permalink / raw) To: jan.moller; +Cc: bitcoin-development On Tuesday, 22 April 2014, at 10:39 am, Jan Møller wrote: > On Tue, Apr 22, 2014 at 10:29 AM, Matt Whitlock <bip@mattwhitlock•name>wrote: > > On Tuesday, 22 April 2014, at 10:27 am, Jan Møller wrote: > > > > > - Please allow M=1. From a usability point of view it makes sense to allow > > > > > the user to select 1 share if that is what he wants. > > > > > > > > How does that make sense? Decomposing a key/seed into 1 share is > > > > functionally equivalent to dispensing with the secret sharing scheme > > > > entirely. > > > > > > > I agree that it may look silly to have just one-of-one share from a > > > technical point of view, but from an end-user point of view there could be > > > reasons for just having one piece of paper to manage. If M can be 1 then > > > the software/hardware doesn't have to support multiple formats, > > > import/export paths + UI (one for SIPA keys in one share, one for HD seeds > > > in one share, one for SIPA keys + HD seeds in multiple shares). > > > > > > Less complexity & more freedom of choice. > > > > Alright. It's a fair argument. Do you agree with encoding M using a bias > > of -1 so that M up to and including 256 can be encoded in one byte? > > Necessary Shares = M+1, not a problem > > I would probably encode N-of-M in 1 byte as I don't see good use cases with > more than 17 shares. Anyway, I am fine with it as it is. Encoding bias of M changed to -1, and test vectors updated: https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 9:13 ` Matt Whitlock @ 2014-04-22 11:50 ` Justin A 0 siblings, 0 replies; 90+ messages in thread From: Justin A @ 2014-04-22 11:50 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Development [-- Attachment #1: Type: text/plain, Size: 3366 bytes --] Is there a reason you prefer doing the M-1 offset as opposed to limiting the range to 255 instead? Seems like something that will certainly confuse some developers in exchange for adding one more value at the high end of a range. I don't gather there's much difference between 255 and 256 here is there? Also requires the small bit of explanation to hang around as a rider in all future documentation, and the name of the field may not be self-documenting anymore. By way of predicting how I'm wrong, perhaps it is better to have a field where all possible values are legitimate (by not biasing you would have to check it's not zero), or perhaps it's important that powers of 2 be represented here? Perhaps there's some use case at 256 that 255 just won't do for? I'm mostly just curious, as I find problems and funnies crop up when people get clever with optimization of things like message bit-packing etc.. If it's not necessary then maybe better to keep to what's intuitive (i.e. the girls name is clear and self-documenting) Anyway enough of my bike shedding! On Apr 22, 2014 5:38 AM, "Matt Whitlock" <bip@mattwhitlock•name> wrote: > On Tuesday, 22 April 2014, at 10:39 am, Jan Møller wrote: > > On Tue, Apr 22, 2014 at 10:29 AM, Matt Whitlock <bip@mattwhitlock•name > >wrote: > > > On Tuesday, 22 April 2014, at 10:27 am, Jan Møller wrote: > > > > > > - Please allow M=1. From a usability point of view it makes > sense to allow > > > > > > the user to select 1 share if that is what he wants. > > > > > > > > > > How does that make sense? Decomposing a key/seed into 1 share is > > > > > functionally equivalent to dispensing with the secret sharing > scheme > > > > > entirely. > > > > > > > > > I agree that it may look silly to have just one-of-one share from a > > > > technical point of view, but from an end-user point of view there > could be > > > > reasons for just having one piece of paper to manage. If M can be 1 > then > > > > the software/hardware doesn't have to support multiple formats, > > > > import/export paths + UI (one for SIPA keys in one share, one for > HD seeds > > > > in one share, one for SIPA keys + HD seeds in multiple shares). > > > > > > > > Less complexity & more freedom of choice. > > > > > > Alright. It's a fair argument. Do you agree with encoding M using a > bias > > > of -1 so that M up to and including 256 can be encoded in one byte? > > > > Necessary Shares = M+1, not a problem > > > > I would probably encode N-of-M in 1 byte as I don't see good use cases > with > > more than 17 shares. Anyway, I am fine with it as it is. > > Encoding bias of M changed to -1, and test vectors updated: > https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > > ------------------------------------------------------------------------------ > Start Your Social Network Today - Download eXo Platform > Build your Enterprise Intranet with eXo Platform Software > Java Based Open Source Intranet - Social, Extensible, Cloud Ready > Get Started Now And Turn Your Intranet Into A Collaboration Platform > http://p.sf.net/sfu/ExoPlatform > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 4326 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:11 ` Matt Whitlock 2014-04-22 8:27 ` Jan Møller @ 2014-04-22 8:35 ` Matt Whitlock 2014-04-22 8:39 ` Tamas Blummer 2014-04-22 13:37 ` Nikita Schmidt 2 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-22 8:35 UTC (permalink / raw) To: jan.moller; +Cc: bitcoin-development On Tuesday, 22 April 2014, at 4:11 am, Matt Whitlock wrote: > On Tuesday, 22 April 2014, at 10:06 am, Jan Møller wrote: > > - I think it is very useful to define different prefixes for testnet > > keys/seeds. As a developer I use the testnet every day, and many of our > > users use it for trying out new functionality. Mixing up keys meant for > > testnet and mainnet is bad. > > A fair point. I'll add some prefixes for testnet. Testnet encodings are added: https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:35 ` Matt Whitlock @ 2014-04-22 8:39 ` Tamas Blummer 2014-04-22 8:40 ` Matt Whitlock 2014-04-22 15:32 ` Mark Friedenbach 0 siblings, 2 replies; 90+ messages in thread From: Tamas Blummer @ 2014-04-22 8:39 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 1378 bytes --] Extra encoding for testnet is quite useless complexity in face of many alt chains. BIPS should be chain agnostic. Regards, Tamas Blummer http://bitsofproof.com On 22.04.2014, at 10:35, Matt Whitlock <bip@mattwhitlock•name> wrote: > On Tuesday, 22 April 2014, at 4:11 am, Matt Whitlock wrote: >> On Tuesday, 22 April 2014, at 10:06 am, Jan Møller wrote: >>> - I think it is very useful to define different prefixes for testnet >>> keys/seeds. As a developer I use the testnet every day, and many of our >>> users use it for trying out new functionality. Mixing up keys meant for >>> testnet and mainnet is bad. >> >> A fair point. I'll add some prefixes for testnet. > > Testnet encodings are added: https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > ------------------------------------------------------------------------------ > Start Your Social Network Today - Download eXo Platform > Build your Enterprise Intranet with eXo Platform Software > Java Based Open Source Intranet - Social, Extensible, Cloud Ready > Get Started Now And Turn Your Intranet Into A Collaboration Platform > http://p.sf.net/sfu/ExoPlatform > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #1.2: Type: text/html, Size: 4913 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:39 ` Tamas Blummer @ 2014-04-22 8:40 ` Matt Whitlock 2014-04-22 8:43 ` Tamas Blummer 2014-04-22 15:32 ` Mark Friedenbach 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-22 8:40 UTC (permalink / raw) To: Tamas Blummer; +Cc: bitcoin-development On Tuesday, 22 April 2014, at 10:39 am, Tamas Blummer wrote: > Extra encoding for testnet is quite useless complexity in face of many alt chains. > BIPS should be chain agnostic. I would argue that Bitcoin should be altcoin-agnostic. :) I have no interest in catering to altcoins. But that's just me. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:40 ` Matt Whitlock @ 2014-04-22 8:43 ` Tamas Blummer 2014-04-22 8:47 ` Matt Whitlock 0 siblings, 1 reply; 90+ messages in thread From: Tamas Blummer @ 2014-04-22 8:43 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 266 bytes --] It is not about taste, but the fact that BIPs are used by many chains. Alts are useful for at least for experiments, and I think that the notion of main and testnet is superseeded by a wide choice of chains. Regards, Tamas Blummer http://bitsofproof.com [-- Attachment #1.2: Type: text/html, Size: 3493 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:43 ` Tamas Blummer @ 2014-04-22 8:47 ` Matt Whitlock 2014-04-22 8:50 ` Tamas Blummer 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-04-22 8:47 UTC (permalink / raw) To: Tamas Blummer; +Cc: bitcoin-development On Tuesday, 22 April 2014, at 10:43 am, Tamas Blummer wrote: > It is not about taste, but the fact that BIPs are used by many chains. > Alts are useful for at least for experiments, and I think that the notion of main and testnet is superseeded by a wide choice of chains. There aren't enough distinct bytes to allow for every altcoin. I believe what they do is their own business and is outside the scope of a Bitcoin Improvement Proposal. If your argument were valid, then we would also have to apply it to private keys. Why do we bother specifying a separate encoding for Bitcoin testnet private keys? There are so many altcoins, after all. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:47 ` Matt Whitlock @ 2014-04-22 8:50 ` Tamas Blummer 0 siblings, 0 replies; 90+ messages in thread From: Tamas Blummer @ 2014-04-22 8:50 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 260 bytes --] I do not suggest to encode the chain, in contrary. I consider the encoding of main and testnet in WIF and BIP32 as legacy, that I ignore, and suggest that new BIPs should no longer carry this forward. Regards, Tamas Blummer http://bitsofproof.com [-- Attachment #1.2: Type: text/html, Size: 3484 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:39 ` Tamas Blummer 2014-04-22 8:40 ` Matt Whitlock @ 2014-04-22 15:32 ` Mark Friedenbach 2014-04-22 15:49 ` Tamas Blummer 1 sibling, 1 reply; 90+ messages in thread From: Mark Friedenbach @ 2014-04-22 15:32 UTC (permalink / raw) To: bitcoin-development Testnet vs mainnet is quite a separate issue than bitcoin vs altcoin. Unfortunately few of the alts ever figured this out. On 04/22/2014 01:39 AM, Tamas Blummer wrote: > Extra encoding for testnet is quite useless complexity in face of many > alt chains. > BIPS should be chain agnostic. > > Regards, > > Tamas Blummer > http://bitsofproof.com ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 15:32 ` Mark Friedenbach @ 2014-04-22 15:49 ` Tamas Blummer 2014-04-22 17:03 ` Mark Friedenbach 2014-04-22 17:07 ` Jan Møller 0 siblings, 2 replies; 90+ messages in thread From: Tamas Blummer @ 2014-04-22 15:49 UTC (permalink / raw) To: Mark Friedenbach; +Cc: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 616 bytes --] I use several test chains while testing my software, the official test net, a standalone net in house and even chains only created on the fly for unit tests. I found no use of distinguishing serialization of keys while using any of them. If you have some deep insights about why this is needed share it, as I am not goint to guess your valuable thoughts. Regards, Tamas Blummer http://bitsofproof.com On 22.04.2014, at 17:32, Mark Friedenbach <mark@monetize•io> wrote: > Testnet vs mainnet is quite a separate issue than bitcoin vs altcoin. > Unfortunately few of the alts ever figured this out. [-- Attachment #1.2: Type: text/html, Size: 3727 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 15:49 ` Tamas Blummer @ 2014-04-22 17:03 ` Mark Friedenbach 2014-04-22 17:07 ` Jan Møller 1 sibling, 0 replies; 90+ messages in thread From: Mark Friedenbach @ 2014-04-22 17:03 UTC (permalink / raw) To: Tamas Blummer; +Cc: bitcoin-development What I was saying is that while it may or may not make sense to have separate prefixes for testnet, it makes no sense to have per-alt prefixes. On 04/22/2014 08:49 AM, Tamas Blummer wrote: > I use several test chains while testing my software, the official test > net, a standalone net in house and even chains only created on the fly > for unit tests. I found no use of distinguishing serialization of keys > while using any of them. > > If you have some deep insights about why this is needed share it, as I > am not goint to guess your valuable thoughts. > > Regards, > > Tamas Blummer > http://bitsofproof.com > > On 22.04.2014, at 17:32, Mark Friedenbach <mark@monetize•io > <mailto:mark@monetize•io>> wrote: > >> Testnet vs mainnet is quite a separate issue than bitcoin vs altcoin. >> Unfortunately few of the alts ever figured this out. > ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 15:49 ` Tamas Blummer 2014-04-22 17:03 ` Mark Friedenbach @ 2014-04-22 17:07 ` Jan Møller 2014-04-22 18:29 ` Tamas Blummer 1 sibling, 1 reply; 90+ messages in thread From: Jan Møller @ 2014-04-22 17:07 UTC (permalink / raw) To: Tamas Blummer; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1512 bytes --] Treating testnet differently is quite the norm, we have that in BIP 32, 38, 70, SIPA private keys (no BIP for that I guess), bitcoin addresses etc. At the same time none of them define values for alt coins as far as I recall. On Tue, Apr 22, 2014 at 5:49 PM, Tamas Blummer <tamas@bitsofproof•com>wrote: > I use several test chains while testing my software, the official test > net, a standalone net in house and even chains only created on the fly for > unit tests. I found no use of distinguishing serialization of keys while > using any of them. > > If you have some deep insights about why this is needed share it, as I am > not goint to guess your valuable thoughts. > > Regards, > > Tamas Blummer > http://bitsofproof.com > > On 22.04.2014, at 17:32, Mark Friedenbach <mark@monetize•io> wrote: > > Testnet vs mainnet is quite a separate issue than bitcoin vs altcoin. > Unfortunately few of the alts ever figured this out. > > > > > ------------------------------------------------------------------------------ > Start Your Social Network Today - Download eXo Platform > Build your Enterprise Intranet with eXo Platform Software > Java Based Open Source Intranet - Social, Extensible, Cloud Ready > Get Started Now And Turn Your Intranet Into A Collaboration Platform > http://p.sf.net/sfu/ExoPlatform > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > [-- Attachment #2: Type: text/html, Size: 4281 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 17:07 ` Jan Møller @ 2014-04-22 18:29 ` Tamas Blummer 2014-04-22 18:46 ` Gregory Maxwell 0 siblings, 1 reply; 90+ messages in thread From: Tamas Blummer @ 2014-04-22 18:29 UTC (permalink / raw) To: jan.moller; +Cc: Bitcoin Dev [-- Attachment #1.1: Type: text/plain, Size: 1334 bytes --] Yes, it is current norm. I am questioning if we should hang on to it in BIPs. I see testnet as a tool for a certain type of testing. Its existence is likely a consequence of Satoshi not writing unit tests and having automated integration tests, but creating a shadow chain to try things out, mostly manually. I do not say testnet (as we know) would not be useful for certain tests. E.g. as we developed myTREZOR with slush it was useful to have a shared chain with worthless tokens and transactions we can both refer to. However for our automated tests chains-in-a-box are better as we can easily create and exactly re-create wierd situations on-the-fly. While talking about BIP32 hierarchy use, several people argued to use a level of the hierarchy to identify the chain the key is used on. That level could identify testnet but as well an alt coin chain. Above leads me thinking that testnet is far less important than to be addressed in every future BIP. Regards, Tamas Blummer http://bitsofproof.com On 22.04.2014, at 19:07, Jan Møller <jan.moller@gmail•com> wrote: > Treating testnet differently is quite the norm, we have that in BIP 32, 38, 70, SIPA private keys (no BIP for that I guess), bitcoin addresses etc. At the same time none of them define values for alt coins as far as I recall. > > [-- Attachment #1.2: Type: text/html, Size: 4806 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 18:29 ` Tamas Blummer @ 2014-04-22 18:46 ` Gregory Maxwell 2014-04-23 5:33 ` Tamas Blummer 0 siblings, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-22 18:46 UTC (permalink / raw) To: Tamas Blummer; +Cc: Bitcoin Dev On Tue, Apr 22, 2014 at 11:29 AM, Tamas Blummer <tamas@bitsofproof•com> wrote: > Yes, it is current norm. I am questioning if we should hang on to it in > BIPs. > > I see testnet as a tool for a certain type of testing. Its existence is > likely a consequence of Satoshi not writing unit tests and having automated > integration tests, but creating a shadow chain to try things out, mostly > manually. Satoshi didn't create testnet. Testnet exists so you can do public tests involving multiple people and services, so you can have shadow versions of sites and services interacting with each other and trading worthless tokens. Importantly, testnet also creates a public live fire environment where grey hats can try out their attacks while minimizing damage (and it's been very successful at this). Testnet is not an alternative to the unit and integration tests that exist in Bitcoin core but exists for more or less completely different reasons. > Above leads me thinking that testnet is far less important than to be > addressed in every future BIP. Testnet is not normally addressed in BIPs at all, except for soft fork bips that had compressed deployment schedules on testnet. For address like specification we have always used a version byte and there is a common encoding for version bytes that flags the network ID in the byte. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 18:46 ` Gregory Maxwell @ 2014-04-23 5:33 ` Tamas Blummer 2014-04-23 6:16 ` Gregory Maxwell 0 siblings, 1 reply; 90+ messages in thread From: Tamas Blummer @ 2014-04-23 5:33 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev [-- Attachment #1.1: Type: text/plain, Size: 587 bytes --] So you agree, that SSS should not contain specific flag for testnet? Or for that matter not even BIP32 needs them since it is not an address to send to. Regards, Tamas Blummer http://bitsofproof.com On 22.04.2014, at 20:46, Gregory Maxwell <gmaxwell@gmail•com> wrote: > Testnet is not normally addressed in BIPs at all, except for soft fork > bips that had compressed deployment schedules on testnet. For address > like specification we have always used a version byte and there is a > common encoding for version bytes that flags the network ID in the > byte. > [-- Attachment #1.2: Type: text/html, Size: 3906 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-23 5:33 ` Tamas Blummer @ 2014-04-23 6:16 ` Gregory Maxwell 2014-05-05 19:36 ` Nikita Schmidt 0 siblings, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-23 6:16 UTC (permalink / raw) To: Tamas Blummer; +Cc: Bitcoin Dev On Tue, Apr 22, 2014 at 10:33 PM, Tamas Blummer <tamas@bitsofproof•com> wrote: > So you agree, that SSS should not contain specific flag for testnet? > > Or for that matter not even BIP32 needs them since it is not an address to > send to. I think the convention we have so far is that addresses and address relate thing we share normally contain an opaque 'version' identifier which we use to identify the purpose for the data (E.g. network meaning, etc.) and I think its a generally reasonable custom. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-23 6:16 ` Gregory Maxwell @ 2014-05-05 19:36 ` Nikita Schmidt 2014-05-12 12:09 ` Jan Møller 0 siblings, 1 reply; 90+ messages in thread From: Nikita Schmidt @ 2014-05-05 19:36 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev A fork of Matt's proposal converted to GF(2^8) is here: https://github.com/cetuscetus/btctool/blob/bip/bip-xxxx.mediawiki Other changes include: - only six application/version bytes are allocated, which is the minimum to ensure that the encoded form starts with S in all cases; - encoded prefixes are SK/SL for a shared private key (mainnet/testnet) and SS/ST for a shared BIP32 seed; - the only hash function in use is SHA-256, which is the all-purpose hash function in the Bitcoin protocol; - double SHA is used for similarity with Bitcoin, although Jan and I believe single SHA is enough in this application; - bias-less encoding of M and x, because there can't be more than 255 shares over GF(2^8). On 23 April 2014 09:16, Gregory Maxwell <gmaxwell@gmail•com> wrote: > On Tue, Apr 22, 2014 at 10:33 PM, Tamas Blummer <tamas@bitsofproof•com> wrote: >> So you agree, that SSS should not contain specific flag for testnet? >> >> Or for that matter not even BIP32 needs them since it is not an address to >> send to. > > I think the convention we have so far is that addresses and address > relate thing we share normally contain an opaque 'version' identifier > which we use to identify the purpose for the data (E.g. network > meaning, etc.) and I think its a generally reasonable custom. > > ------------------------------------------------------------------------------ > Start Your Social Network Today - Download eXo Platform > Build your Enterprise Intranet with eXo Platform Software > Java Based Open Source Intranet - Social, Extensible, Cloud Ready > Get Started Now And Turn Your Intranet Into A Collaboration Platform > http://p.sf.net/sfu/ExoPlatform > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-05-05 19:36 ` Nikita Schmidt @ 2014-05-12 12:09 ` Jan Møller 2014-08-14 19:23 ` Nikita Schmidt 0 siblings, 1 reply; 90+ messages in thread From: Jan Møller @ 2014-05-12 12:09 UTC (permalink / raw) To: Nikita Schmidt, Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 3268 bytes --] A Java implementation of what is called BIPSS in lack of an official number can be found here: https://github.com/mycelium-com/wallet/blob/master/public/bitlib/src/main/java/com/mrd/bitlib/crypto/BipSs.java (passing all test vectors) Which is based on a GF2^8 implementation here: https://github.com/mycelium-com/wallet/blob/master/public/bitlib/src/main/java/com/mrd/bitlib/crypto/Gf256.java I think having 3 encoding formats (long/short/compact) is over engineered, and basically only makes implementing the standard a pain in the rear. From a user experience point of view only the long format makes sense, and it is only a few bytes longer than the short version. On Mon, May 5, 2014 at 9:36 PM, Nikita Schmidt < nikita@megiontechnologies•com> wrote: > A fork of Matt's proposal converted to GF(2^8) is here: > https://github.com/cetuscetus/btctool/blob/bip/bip-xxxx.mediawiki > > Other changes include: > - only six application/version bytes are allocated, which is the > minimum to ensure that the encoded form starts with S in all cases; > - encoded prefixes are SK/SL for a shared private key > (mainnet/testnet) and SS/ST for a shared BIP32 seed; > - the only hash function in use is SHA-256, which is the all-purpose > hash function in the Bitcoin protocol; > - double SHA is used for similarity with Bitcoin, although Jan and I > believe single SHA is enough in this application; > - bias-less encoding of M and x, because there can't be more than 255 > shares over GF(2^8). > > > On 23 April 2014 09:16, Gregory Maxwell <gmaxwell@gmail•com> wrote: > > On Tue, Apr 22, 2014 at 10:33 PM, Tamas Blummer <tamas@bitsofproof•com> > wrote: > >> So you agree, that SSS should not contain specific flag for testnet? > >> > >> Or for that matter not even BIP32 needs them since it is not an address > to > >> send to. > > > > I think the convention we have so far is that addresses and address > > relate thing we share normally contain an opaque 'version' identifier > > which we use to identify the purpose for the data (E.g. network > > meaning, etc.) and I think its a generally reasonable custom. > > > > > ------------------------------------------------------------------------------ > > Start Your Social Network Today - Download eXo Platform > > Build your Enterprise Intranet with eXo Platform Software > > Java Based Open Source Intranet - Social, Extensible, Cloud Ready > > Get Started Now And Turn Your Intranet Into A Collaboration Platform > > http://p.sf.net/sfu/ExoPlatform > > _______________________________________________ > > Bitcoin-development mailing list > > Bitcoin-development@lists•sourceforge.net > > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > > ------------------------------------------------------------------------------ > Is your legacy SCM system holding you back? Join Perforce May 7 to find > out: > • 3 signs your SCM is hindering your productivity > • Requirements for releasing software faster > • Expert tips and advice for migrating your SCM now > http://p.sf.net/sfu/perforce > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 4919 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-05-12 12:09 ` Jan Møller @ 2014-08-14 19:23 ` Nikita Schmidt 0 siblings, 0 replies; 90+ messages in thread From: Nikita Schmidt @ 2014-08-14 19:23 UTC (permalink / raw) To: Jan Møller; +Cc: Bitcoin Dev On 12 May 2014 15:09, Jan Møller <jan.moller@gmail•com> wrote: > > I think having 3 encoding formats (long/short/compact) is over engineered, > and basically only makes implementing the standard a pain in the rear. From > a user experience point of view only the long format makes sense, and it is > only a few bytes longer than the short version. > True. Since nobody has objected, the draft has been reworked and is much leaner now: https://github.com/cetuscetus/btctool/blob/bip/bip-xxxx.mediawiki . The reasons for not making M and checksum fields optional are added to the Rationale section. The main difference is that the shared secret can be in encoded form, e.g. SIPA or BIP38 instead of a plain private key. This makes SSS a general purpose container for any kind of secret data. The benefits are: - no need to change the spec to carry another type of content; - testnet and altcoins do not need any treatment in this spec; - content-specific metadata, such as compressed/uncompressed, encrypted/non-encrypted, key inception time point etc., are encoded together with the secret, rather than provided for separately and individually in this spec. As we are now dealing with secrets of arbitrary length, GF(256) as the underlying field becomes much more advantageous than GF(large prime). An inconvenience of variable length is that we have no control of the Base58 prefix. This was solved by moving the magic prefix outside of the Base58 encoded content: SSS-abcdefgh. 'SSS-' acts as the application identifier both to humans and machines, and abcdefgh is the Base58 encoding of the share without any application/magic bytes. (This may seem mildly controversial, but is there a better way?) ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:11 ` Matt Whitlock 2014-04-22 8:27 ` Jan Møller 2014-04-22 8:35 ` Matt Whitlock @ 2014-04-22 13:37 ` Nikita Schmidt 2 siblings, 0 replies; 90+ messages in thread From: Nikita Schmidt @ 2014-04-22 13:37 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development > > A fair point. I'll add some prefixes for testnet. > I've looked at the latest draft and am worried about the increased AVB namespace usage. Would it make sense to differentiate main/testnet in the prefix byte instead of the AVB? Perhaps aiming for ST rather than TS. > I'll welcome forks of my draft BIP. I don't really have the inclination to research GF(2^8) secret sharing schemes and write an implementation at the present time, but if someone wants to take my BIP in that direction, then okay. I'm willing to fork it. The maximum number of shares possible over GF(2^8) is 255. That would make M and x biases unnecessary. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:06 ` Jan Møller 2014-04-22 8:11 ` Matt Whitlock @ 2014-04-22 8:15 ` Gregory Maxwell 2014-04-22 8:49 ` Jan Møller 1 sibling, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-04-22 8:15 UTC (permalink / raw) To: jan.moller; +Cc: bitcoin-development On Tue, Apr 22, 2014 at 1:06 AM, Jan Møller <jan.moller@gmail•com> wrote: > This is a very useful BIP, and I am very much looking forward to > implementing it in Mycelium, in particular for bip32 wallets. I haven't seen commentary from you on the Kogelman draft, it would be helpful there: https://bitcointalk.org/index.php?topic=258678.0 ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-04-22 8:15 ` Gregory Maxwell @ 2014-04-22 8:49 ` Jan Møller 0 siblings, 0 replies; 90+ messages in thread From: Jan Møller @ 2014-04-22 8:49 UTC (permalink / raw) To: Gregory Maxwell; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 977 bytes --] I did comment on it back in october ( https://bitcointalk.org/index.php?topic=258678.msg3298089#msg3298089) :-) But I must admit that I haven't been tracking it since then. I have never been a proponent of BIP 38 (which this BIP is derived from) and generally think that encrypting a secret with a human generated password is silly for many reasons (Let me know if I should repeat my list of concerns). As far as I remember we are pretty much on the same page here. Using SSS is superior in every way that I can think of. On Tue, Apr 22, 2014 at 10:15 AM, Gregory Maxwell <gmaxwell@gmail•com>wrote: > On Tue, Apr 22, 2014 at 1:06 AM, Jan Møller <jan.moller@gmail•com> wrote: > > This is a very useful BIP, and I am very much looking forward to > > implementing it in Mycelium, in particular for bip32 wallets. > > I haven't seen commentary from you on the Kogelman draft, it would be > helpful there: https://bitcointalk.org/index.php?topic=258678.0 > [-- Attachment #2: Type: text/html, Size: 1566 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
[parent not found: <CACsn0ckScTWG4YxNCscxvtdsmcUkxtR2Gi-rdBs2HCkirPz5rA@mail.gmail.com>]
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys [not found] <CACsn0ckScTWG4YxNCscxvtdsmcUkxtR2Gi-rdBs2HCkirPz5rA@mail.gmail.com> @ 2014-03-29 15:44 ` Matt Whitlock 2014-03-29 16:59 ` Alan Reiner ` (2 more replies) 0 siblings, 3 replies; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 15:44 UTC (permalink / raw) To: Watson Ladd; +Cc: Bitcoin Dev On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote: > https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/ Thanks. This is great, although it makes some critical references to an ACM paper for which no URL is provided, and thus I cannot implement it. A distributed ECDSA notwithstanding, we still need a way to decompose a BIP32 master seed into shares. I am envisioning a scenario in which I might meet my sudden and untimely demise, and I wish to allow my beneficiaries to reconstruct my wallet's master seed after my death. I would like to distribute seed shares to each of my beneficiaries and some close friends, such that some subset of the shares must be joined together to reconstitute my master seed. Shamir's Secret Sharing Scheme is perfect for this use case. I am presently working on extending my draft BIP so that it also applies to BIP32 master seeds of various sizes. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 15:44 ` Matt Whitlock @ 2014-03-29 16:59 ` Alan Reiner 2014-03-29 17:19 ` Matt Whitlock 2014-03-29 17:28 ` Roy Badami 2014-03-29 17:28 ` devrandom [not found] ` <1396113933.8809.91.camel@mimiz> 2 siblings, 2 replies; 90+ messages in thread From: Alan Reiner @ 2014-03-29 16:59 UTC (permalink / raw) To: bitcoin-development Armory has had "Fragmented Backups" for over a year, now. Advanced users love it. Though, I would say it's kind of difficult to standardize the way I did it since I was able to implement all the finite field math with recursion, list comprehensions and python arbitrary-big-integers in about 100 lines. I'm not sure how "portable" it is to other languages. There's obviously better ways to do it, but I didn't need a better way, because I don't need to support fragmentation above M=8 and this was 100% sufficient for it. And I was the only one doing it, so there was no one to be compatible with. I won't lie, there's a lot of work that goes into making an interface that makes this feature "usable." The user needs clear ways to identify which fragments are associated with which wallet, and which fragments are compatible with each other. They need a way to save some fragments to file, print them, or simply write them down. They need a way to re-enter fragment, reject duplicates, identify errors, etc. Without it, the math fails silently, and you end up restoring a different wallet. And they need a way to test that it all works. Armory did all this, but it was no trivial task. Including an interface that will test up to 50 subsets of make sure the math produces the same values every time (which still is not sufficient for some users, who won't be satisified til they see they're wallet actually restored from fragments. Also I put the secret in the highest-order coefficient of the polynomial, and made sure that the other coefficients were deterministic. This meant that if print out an M-of-N wallet, I can later print out an M-of-(N+1) wallet and the first N fragments will be the same. I'm not sure how many users would trust this, but we felt it was important in case a user needs to export some fragments, even if they don't increase N. You might consider loading Armory in offline mode, create a wallet, and then do a fragmented backup to see how we did it. I am extremely satisfied with the interface, but it's most definitely an "advanced" tool. But so is Armory ... which made it a good fit. But it might not be for everyone. -Alan On 03/29/2014 11:44 AM, Matt Whitlock wrote: > On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote: >> https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/ > Thanks. This is great, although it makes some critical references to an ACM paper for which no URL is provided, and thus I cannot implement it. > > A distributed ECDSA notwithstanding, we still need a way to decompose a BIP32 master seed into shares. I am envisioning a scenario in which I might meet my sudden and untimely demise, and I wish to allow my beneficiaries to reconstruct my wallet's master seed after my death. I would like to distribute seed shares to each of my beneficiaries and some close friends, such that some subset of the shares must be joined together to reconstitute my master seed. Shamir's Secret Sharing Scheme is perfect for this use case. I am presently working on extending my draft BIP so that it also applies to BIP32 master seeds of various sizes. > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 16:59 ` Alan Reiner @ 2014-03-29 17:19 ` Matt Whitlock 2014-03-29 17:52 ` Alan Reiner 2014-03-29 17:28 ` Roy Badami 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 17:19 UTC (permalink / raw) To: Alan Reiner; +Cc: bitcoin-development On Saturday, 29 March 2014, at 12:59 pm, Alan Reiner wrote: > I won't lie, there's a lot of work that goes into making an interface > that makes this feature "usable." The user needs clear ways to identify > which fragments are associated with which wallet, and which fragments > are compatible with each other. The same is true of the multiple private keys involved in a multi-signature addresses. > They need a way to save some fragments > to file, print them, or simply write them down. I proposed a share encoding scheme for exactly this purpose. > They need a way to > re-enter fragment, reject duplicates, identify errors, etc. Without it, > the math fails silently, and you end up restoring a different wallet. I intentionally omitted the parameter M (minimum subset size) from the shares because including it would give an adversary a vital piece of information. Likewise, including any kind of information that would allow a determination of whether the secret has been correctly reconstituted would give an adversary too much information. Failing silently when given incorrect shares or an insufficient number of shares is intentional. > Also I put the secret in the highest-order coefficient of the > polynomial, Does it make any difference which coefficient holds the secret? It's convenient to put it in the lowest-order coefficient to simply the recovery code. > and made sure that the other coefficients were > deterministic. This meant that if print out an M-of-N wallet, I can > later print out an M-of-(N+1) wallet and the first N fragments will be > the same. I'm not sure how many users would trust this, but we felt it > was important in case a user needs to export some fragments, even if > they don't increase N. My BIP likewise deterministically chooses the coefficients so that the shares of a secret are consistent across all runs of the algorithm having the same M. As I'm sure you're aware, N (the number of shares to output) plays no part in the calculation and merely controls how many times the outermost loop is executed. My BIP doesn't even mention this parameter. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:19 ` Matt Whitlock @ 2014-03-29 17:52 ` Alan Reiner 2014-03-29 18:00 ` Matt Whitlock 2014-03-29 18:16 ` Tamas Blummer 0 siblings, 2 replies; 90+ messages in thread From: Alan Reiner @ 2014-03-29 17:52 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development On 03/29/2014 01:19 PM, Matt Whitlock wrote: > I intentionally omitted the parameter M (minimum subset size) from the shares because including it would give an adversary a vital piece of information. Likewise, including any kind of information that would allow a determination of whether the secret has been correctly reconstituted would give an adversary too much information. Failing silently when given incorrect shares or an insufficient number of shares is intentional. I do not believe this is a good tradeoff. It's basically obfuscation of something that is already considered secure at the expense of usability. It's much more important to me that the user understands what is in their hands (or their family members after they get hit by a bus), than to obfuscate the parameters of the secret sharing to provide a tiny disadvantage to an adversary who gets ahold of one. The fact that it fails silently is really all downside, not a benefit. If I have enough fragments, I can reconstruct the seed and see that it produces addresses with money. If not, I know I need more fragments. I'm much more concerned about my family having all the info they need to recover the money, than an attacker knowing that he needs two more fragments instead of which are well-secured anyway. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:52 ` Alan Reiner @ 2014-03-29 18:00 ` Matt Whitlock 2014-03-29 18:08 ` Alan Reiner 2014-03-29 18:16 ` Tamas Blummer 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 18:00 UTC (permalink / raw) To: Alan Reiner; +Cc: bitcoin-development On Saturday, 29 March 2014, at 1:52 pm, Alan Reiner wrote: > On 03/29/2014 01:19 PM, Matt Whitlock wrote: > > I intentionally omitted the parameter M (minimum subset size) from the shares because including it would give an adversary a vital piece of information. Likewise, including any kind of information that would allow a determination of whether the secret has been correctly reconstituted would give an adversary too much information. Failing silently when given incorrect shares or an insufficient number of shares is intentional. > > I do not believe this is a good tradeoff. It's basically obfuscation of > something that is already considered secure at the expense of > usability. It's much more important to me that the user understands > what is in their hands (or their family members after they get hit by a > bus), than to obfuscate the parameters of the secret sharing to provide > a tiny disadvantage to an adversary who gets ahold of one. > > The fact that it fails silently is really all downside, not a benefit. > If I have enough fragments, I can reconstruct the seed and see that it > produces addresses with money. If not, I know I need more fragments. > I'm much more concerned about my family having all the info they need to > recover the money, than an attacker knowing that he needs two more > fragments instead of which are well-secured anyway. For what it's worth, ssss also omits from the shares any information about the threshold. It will happily return a garbage secret if too few shares are combined. (And actually, it will happily return a garbage secret if too *many* shares are combined, too. My implementation does not have that problem.) ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 18:00 ` Matt Whitlock @ 2014-03-29 18:08 ` Alan Reiner 2014-03-29 18:10 ` Matt Whitlock 0 siblings, 1 reply; 90+ messages in thread From: Alan Reiner @ 2014-03-29 18:08 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development On 03/29/2014 02:00 PM, Matt Whitlock wrote: > On Saturday, 29 March 2014, at 1:52 pm, Alan Reiner wrote: >> On 03/29/2014 01:19 PM, Matt Whitlock wrote: >>> I intentionally omitted the parameter M (minimum subset size) from the shares because including it would give an adversary a vital piece of information. Likewise, including any kind of information that would allow a determination of whether the secret has been correctly reconstituted would give an adversary too much information. Failing silently when given incorrect shares or an insufficient number of shares is intentional. >> I do not believe this is a good tradeoff. It's basically obfuscation of >> something that is already considered secure at the expense of >> usability. It's much more important to me that the user understands >> what is in their hands (or their family members after they get hit by a >> bus), than to obfuscate the parameters of the secret sharing to provide >> a tiny disadvantage to an adversary who gets ahold of one. >> >> The fact that it fails silently is really all downside, not a benefit. >> If I have enough fragments, I can reconstruct the seed and see that it >> produces addresses with money. If not, I know I need more fragments. >> I'm much more concerned about my family having all the info they need to >> recover the money, than an attacker knowing that he needs two more >> fragments instead of which are well-secured anyway. > For what it's worth, ssss also omits from the shares any information about the threshold. It will happily return a garbage secret if too few shares are combined. (And actually, it will happily return a garbage secret if too *many* shares are combined, too. My implementation does not have that problem.) Regardless of how SSSS does it, I believe that obfuscating that information is bad news from a usability perspective. Undoubtedly, users will make lots of backups of lots of wallets and think they remember the M-parameter but don't. They will accidentally mix in some 3-of-5 fragments with their 2-of-4 not realizing they are incompatible, or not able to distinguish them. Or they'll distribute too many thinking the threshold is higher and end up insecure, or possibly not have enough fragments to restore their wallet thinking the M-value was lower than it actually was. I just don't see the value in adding such complexity for the benefit of obfuscating information an attacker might be able to figure out anyway (most backups will be 2-of-N or 3-of-N) and can't act on anyway (because he doesn't know where the other frags are and they are actually in safe-deposit boxes) ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 18:08 ` Alan Reiner @ 2014-03-29 18:10 ` Matt Whitlock [not found] ` <CAAt2M18j7bGDsKouVw+e4j+FMiJ4vK6-sx+nrkwHyiKLqiH7Jg@mail.gmail.com> 2014-04-04 2:38 ` Jeff Garzik 0 siblings, 2 replies; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 18:10 UTC (permalink / raw) To: Alan Reiner; +Cc: bitcoin-development On Saturday, 29 March 2014, at 2:08 pm, Alan Reiner wrote: > Regardless of how SSSS does it, I believe that obfuscating that > information is bad news from a usability perspective. Undoubtedly, > users will make lots of backups of lots of wallets and think they > remember the M-parameter but don't. They will accidentally mix in some > 3-of-5 fragments with their 2-of-4 not realizing they are incompatible, > or not able to distinguish them. Or they'll distribute too many > thinking the threshold is higher and end up insecure, or possibly not > have enough fragments to restore their wallet thinking the M-value was > lower than it actually was. > > I just don't see the value in adding such complexity for the benefit of > obfuscating information an attacker might be able to figure out anyway > (most backups will be 2-of-N or 3-of-N) and can't act on anyway (because > he doesn't know where the other frags are and they are actually in > safe-deposit boxes) Okay, you've convinced me. However, it looks like the consensus here is that my BIP is unneeded, so I'm not sure it would be worth the effort for me to improve it with your suggestions. ^ permalink raw reply [flat|nested] 90+ messages in thread
[parent not found: <CAAt2M18j7bGDsKouVw+e4j+FMiJ4vK6-sx+nrkwHyiKLqiH7Jg@mail.gmail.com>]
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys [not found] ` <CAAt2M18j7bGDsKouVw+e4j+FMiJ4vK6-sx+nrkwHyiKLqiH7Jg@mail.gmail.com> @ 2014-03-29 19:34 ` Natanael 0 siblings, 0 replies; 90+ messages in thread From: Natanael @ 2014-03-29 19:34 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 1847 bytes --] Den 29 mar 2014 19:15 skrev "Matt Whitlock" <bip@mattwhitlock•name>: > > On Saturday, 29 March 2014, at 2:08 pm, Alan Reiner wrote: > > Regardless of how SSSS does it, I believe that obfuscating that > > information is bad news from a usability perspective. Undoubtedly, > > users will make lots of backups of lots of wallets and think they > > remember the M-parameter but don't. They will accidentally mix in some > > 3-of-5 fragments with their 2-of-4 not realizing they are incompatible, > > or not able to distinguish them. Or they'll distribute too many > > thinking the threshold is higher and end up insecure, or possibly not > > have enough fragments to restore their wallet thinking the M-value was > > lower than it actually was. > > > > I just don't see the value in adding such complexity for the benefit of > > obfuscating information an attacker might be able to figure out anyway > > (most backups will be 2-of-N or 3-of-N) and can't act on anyway (because > > he doesn't know where the other frags are and they are actually in > > safe-deposit boxes) > > Okay, you've convinced me. However, it looks like the consensus here is that my BIP is unneeded, so I'm not sure it would be worth the effort for me to improve it with your suggestions. I think it should be made an option (with the default being that the threshold is given and verification is applied. There could certainly be a few cases where the threshold is set high, you maybe don't have access to a great enough variety of hiding spots or secure enough hiding spots, and you want deter an attempt to find all the shares (with the idea being that the risk of detection would be too high, in particular when you use tamper evident seals). But for the majority it would be better to find a few different safeboxes to put the shares in and rely on physical security. [-- Attachment #2: Type: text/html, Size: 2176 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 18:10 ` Matt Whitlock [not found] ` <CAAt2M18j7bGDsKouVw+e4j+FMiJ4vK6-sx+nrkwHyiKLqiH7Jg@mail.gmail.com> @ 2014-04-04 2:38 ` Jeff Garzik 1 sibling, 0 replies; 90+ messages in thread From: Jeff Garzik @ 2014-04-04 2:38 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Dev On Sat, Mar 29, 2014 at 2:10 PM, Matt Whitlock <bip@mattwhitlock•name> wrote: > Okay, you've convinced me. However, it looks like the consensus here is that my BIP is unneeded, so I'm not sure it would be worth the effort for me to improve it with your suggestions. Discussion of whether you should or should not use SSS is separate from whether you should or should not write a BIP. If people are using SSS in the field, it is better to write a BIP than not. Informational BIPs describing existing practice can be useful. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:52 ` Alan Reiner 2014-03-29 18:00 ` Matt Whitlock @ 2014-03-29 18:16 ` Tamas Blummer 2014-03-29 18:41 ` Alan Reiner 1 sibling, 1 reply; 90+ messages in thread From: Tamas Blummer @ 2014-03-29 18:16 UTC (permalink / raw) To: Alan Reiner; +Cc: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 2296 bytes --] I also think that we can add usability features if the underlying secret remains well protected. I do not think there is any reason to assume that the knowledge of the degree of the polynomial, would aid an attacker. Similarly a fingerprint of the secret if it is unrelated to the hash used in the polinomyal should leak no useful information, The length of such fingerpring (say 4 bytes) and the degree (1 byte) does not seem a big overhead for me. Remember that the biggest obstacle of Bitcoin is usability not security. Regards, Tamas Blummer http://bitsofproof.com On 29.03.2014, at 18:52, Alan Reiner <etotheipi@gmail•com> wrote: > On 03/29/2014 01:19 PM, Matt Whitlock wrote: >> I intentionally omitted the parameter M (minimum subset size) from the shares because including it would give an adversary a vital piece of information. Likewise, including any kind of information that would allow a determination of whether the secret has been correctly reconstituted would give an adversary too much information. Failing silently when given incorrect shares or an insufficient number of shares is intentional. > > I do not believe this is a good tradeoff. It's basically obfuscation of > something that is already considered secure at the expense of > usability. It's much more important to me that the user understands > what is in their hands (or their family members after they get hit by a > bus), than to obfuscate the parameters of the secret sharing to provide > a tiny disadvantage to an adversary who gets ahold of one. > > The fact that it fails silently is really all downside, not a benefit. > If I have enough fragments, I can reconstruct the seed and see that it > produces addresses with money. If not, I know I need more fragments. > I'm much more concerned about my family having all the info they need to > recover the money, than an attacker knowing that he needs two more > fragments instead of which are well-secured anyway. > > > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #1.2: Type: text/html, Size: 5709 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 18:16 ` Tamas Blummer @ 2014-03-29 18:41 ` Alan Reiner 0 siblings, 0 replies; 90+ messages in thread From: Alan Reiner @ 2014-03-29 18:41 UTC (permalink / raw) To: Tamas Blummer; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 2995 bytes --] Armory does exactly this: it defines the "Fragment ID" as the first few bytes of the hash of the root pubKey + M-parameter, converted to base58. Then it explains to the user "All fragments with the same fragment ID are compatible" (which only works if you use deterministic coefficients). Each fragment is then labeled with "[FragID]-#1", "[FragID]-#2", etc. It became quite useful for organizing the fragments and documenting how I was distributing them, especially if I had printed or saved the same fragment twice by accident. On 03/29/2014 02:16 PM, Tamas Blummer wrote: > I also think that we can add usability features if the underlying > secret remains well protected. > I do not think there is any reason to assume that the knowledge of the > degree of the polynomial, would aid an attacker. > > Similarly a fingerprint of the secret if it is unrelated to the hash > used in the polinomyal should leak no useful information, > > The length of such fingerpring (say 4 bytes) and the degree (1 byte) > does not seem a big overhead for me. > > Remember that the biggest obstacle of Bitcoin is usability not security. > > Regards, > > Tamas Blummer > http://bitsofproof.com > > On 29.03.2014, at 18:52, Alan Reiner <etotheipi@gmail•com > <mailto:etotheipi@gmail•com>> wrote: > >> On 03/29/2014 01:19 PM, Matt Whitlock wrote: >>> I intentionally omitted the parameter M (minimum subset size) from >>> the shares because including it would give an adversary a vital >>> piece of information. Likewise, including any kind of information >>> that would allow a determination of whether the secret has been >>> correctly reconstituted would give an adversary too much >>> information. Failing silently when given incorrect shares or an >>> insufficient number of shares is intentional. >> >> I do not believe this is a good tradeoff. It's basically obfuscation of >> something that is already considered secure at the expense of >> usability. It's much more important to me that the user understands >> what is in their hands (or their family members after they get hit by a >> bus), than to obfuscate the parameters of the secret sharing to provide >> a tiny disadvantage to an adversary who gets ahold of one. >> >> The fact that it fails silently is really all downside, not a benefit. >> If I have enough fragments, I can reconstruct the seed and see that it >> produces addresses with money. If not, I know I need more fragments. >> I'm much more concerned about my family having all the info they need to >> recover the money, than an attacker knowing that he needs two more >> fragments instead of which are well-secured anyway. >> >> >> >> ------------------------------------------------------------------------------ >> _______________________________________________ >> Bitcoin-development mailing list >> Bitcoin-development@lists•sourceforge.net >> <mailto:Bitcoin-development@lists•sourceforge.net> >> https://lists.sourceforge.net/lists/listinfo/bitcoin-development >> > [-- Attachment #2: Type: text/html, Size: 8228 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 16:59 ` Alan Reiner 2014-03-29 17:19 ` Matt Whitlock @ 2014-03-29 17:28 ` Roy Badami 2014-03-29 17:42 ` Matt Whitlock 1 sibling, 1 reply; 90+ messages in thread From: Roy Badami @ 2014-03-29 17:28 UTC (permalink / raw) To: Alan Reiner; +Cc: bitcoin-development Right now there are also people simply taking base58-encoded private keys and running them through ssss-split. It has a lot going for it, since it can easily be reassembled on any Linux machine without special software (B Poettering's Linux command line SSSS implementation[1] seems to be included in most Linux distros). roy [1] http://point-at-infinity.org/ssss/ On Sat, Mar 29, 2014 at 12:59:19PM -0400, Alan Reiner wrote: > > Armory has had "Fragmented Backups" for over a year, now. Advanced > users love it. Though, I would say it's kind of difficult to > standardize the way I did it since I was able to implement all the > finite field math with recursion, list comprehensions and python > arbitrary-big-integers in about 100 lines. I'm not sure how "portable" > it is to other languages. There's obviously better ways to do it, but I > didn't need a better way, because I don't need to support fragmentation > above M=8 and this was 100% sufficient for it. And I was the only one > doing it, so there was no one to be compatible with. > > I won't lie, there's a lot of work that goes into making an interface > that makes this feature "usable." The user needs clear ways to identify > which fragments are associated with which wallet, and which fragments > are compatible with each other. They need a way to save some fragments > to file, print them, or simply write them down. They need a way to > re-enter fragment, reject duplicates, identify errors, etc. Without it, > the math fails silently, and you end up restoring a different wallet. > And they need a way to test that it all works. Armory did all this, > but it was no trivial task. Including an interface that will test up to > 50 subsets of make sure the math produces the same values every time > (which still is not sufficient for some users, who won't be satisified > til they see they're wallet actually restored from fragments. > > Also I put the secret in the highest-order coefficient of the > polynomial, and made sure that the other coefficients were > deterministic. This meant that if print out an M-of-N wallet, I can > later print out an M-of-(N+1) wallet and the first N fragments will be > the same. I'm not sure how many users would trust this, but we felt it > was important in case a user needs to export some fragments, even if > they don't increase N. > > You might consider loading Armory in offline mode, create a wallet, and > then do a fragmented backup to see how we did it. I am extremely > satisfied with the interface, but it's most definitely an "advanced" > tool. But so is Armory ... which made it a good fit. But it might not > be for everyone. > > -Alan > > > > On 03/29/2014 11:44 AM, Matt Whitlock wrote: > > On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote: > >> https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/ > > Thanks. This is great, although it makes some critical references to an ACM paper for which no URL is provided, and thus I cannot implement it. > > > > A distributed ECDSA notwithstanding, we still need a way to decompose a BIP32 master seed into shares. I am envisioning a scenario in which I might meet my sudden and untimely demise, and I wish to allow my beneficiaries to reconstruct my wallet's master seed after my death. I would like to distribute seed shares to each of my beneficiaries and some close friends, such that some subset of the shares must be joined together to reconstitute my master seed. Shamir's Secret Sharing Scheme is perfect for this use case. I am presently working on extending my draft BIP so that it also applies to BIP32 master seeds of various sizes. > > > > ------------------------------------------------------------------------------ > > _______________________________________________ > > Bitcoin-development mailing list > > Bitcoin-development@lists•sourceforge.net > > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:28 ` Roy Badami @ 2014-03-29 17:42 ` Matt Whitlock 2014-03-29 17:51 ` Roy Badami 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 17:42 UTC (permalink / raw) To: Roy Badami; +Cc: bitcoin-development On Saturday, 29 March 2014, at 5:28 pm, Roy Badami wrote: > Right now there are also people simply taking base58-encoded private > keys and running them through ssss-split. > > It has a lot going for it, since it can easily be reassembled on any > Linux machine without special software (B Poettering's Linux command > line SSSS implementation[1] seems to be included in most Linux distros). > > roy > > [1] http://point-at-infinity.org/ssss/ Respectfully, it's also possible to take a base58-encoded private key and run it through GPG, which is included in most Linux distros. But yet we have BIP38. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:42 ` Matt Whitlock @ 2014-03-29 17:51 ` Roy Badami 0 siblings, 0 replies; 90+ messages in thread From: Roy Badami @ 2014-03-29 17:51 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development On Sat, Mar 29, 2014 at 01:42:01PM -0400, Matt Whitlock wrote: > On Saturday, 29 March 2014, at 5:28 pm, Roy Badami wrote: > > Right now there are also people simply taking base58-encoded private > > keys and running them through ssss-split. > > > > It has a lot going for it, since it can easily be reassembled on any > > Linux machine without special software (B Poettering's Linux command > > line SSSS implementation[1] seems to be included in most Linux distros). > > > > roy > > > > [1] http://point-at-infinity.org/ssss/ > > Respectfully, it's also possible to take a base58-encoded private key and run it through GPG, which is included in most Linux distros. But yet we have BIP38. And yet, how many wallets can import BIP38 keys? If someone gave me one I would have no idea what software (if any) can understand it (nor would I have any idea how to generate one in the first place). Anyway, I'm not arguing against standardising these things - if people are going to implement this then of course it's beneficial that they implement it compatibly. It was just a simple observation - make of it what you will. roy ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 15:44 ` Matt Whitlock 2014-03-29 16:59 ` Alan Reiner @ 2014-03-29 17:28 ` devrandom [not found] ` <1396113933.8809.91.camel@mimiz> 2 siblings, 0 replies; 90+ messages in thread From: devrandom @ 2014-03-29 17:28 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Dev On Sat, 2014-03-29 at 11:44 -0400, Matt Whitlock wrote: > On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote: > > https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/ > > Thanks. This is great, although it makes some critical references to an > ACM paper for which no URL is provided, and thus I cannot implement it. > > A distributed ECDSA notwithstanding, we still need a way to decompose a > BIP32 master seed into shares. I am envisioning a scenario in which I It would seem that threshold ECDSA with keys derived from separate seeds has better security properties than one seed that is then split up. The main thing is that there is no single point of attack in the generation or signing. > might meet my sudden and untimely demise, and I wish to allow my > beneficiaries to reconstruct my wallet's master seed after my death. I > would like to distribute seed shares to each of my beneficiaries and > some close friends, such that some subset of the shares must be joined > together to reconstitute my master seed. Shamir's Secret Sharing Scheme > is perfect for this use case. I am presently working on extending my > draft BIP so that it also applies to BIP32 master seeds of various > sizes. > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- -- Miron / devrandom -- -- Miron / devrandom ^ permalink raw reply [flat|nested] 90+ messages in thread
[parent not found: <1396113933.8809.91.camel@mimiz>]
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys [not found] ` <1396113933.8809.91.camel@mimiz> @ 2014-03-29 17:38 ` Matt Whitlock 2014-03-29 17:46 ` Gregory Maxwell 2014-03-29 17:48 ` devrandom 0 siblings, 2 replies; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 17:38 UTC (permalink / raw) To: Dev Random; +Cc: Bitcoin Dev On Saturday, 29 March 2014, at 10:25 am, Dev Random wrote: > On Sat, 2014-03-29 at 11:44 -0400, Matt Whitlock wrote: > > On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote: > > > https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/ > > > > Thanks. This is great, although it makes some critical references to an > > ACM paper for which no URL is provided, and thus I cannot implement it. > > > > A distributed ECDSA notwithstanding, we still need a way to decompose a > > BIP32 master seed into shares. I am envisioning a scenario in which I > > It would seem that threshold ECDSA with keys derived from separate seeds > has better security properties than one seed that is then split up. The > main thing is that there is no single point of attack in the generation > or signing. No contest here. But can threshold ECDSA work with BIP32? In other words, can a threshold ECDSA public key be generated from separate, precomputed private keys, or can it only be generated interactively? Maybe the BIP32 master seeds have to be generated interactively, and then all sets of corresponding derived keys are valid signing groups? Threshold ECDSA certainly sounds nice, but is anyone working on a BIP for it? I would take it on myself, but I don't understand it well enough yet, and publicly available information on it seems lacking. I proposed this Shamir Secret Sharing BIP as an easily understood, easily implemented measure that we can use today, with no changes to existing Bitcoin software. It's low-hanging fruit. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:38 ` Matt Whitlock @ 2014-03-29 17:46 ` Gregory Maxwell 2014-03-29 19:49 ` Tamas Blummer 2014-03-29 17:48 ` devrandom 1 sibling, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-03-29 17:46 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Dev, Dev Random On Sat, Mar 29, 2014 at 10:38 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > But can threshold ECDSA work with BIP32? Yes. >In other words, can a threshold ECDSA public key be generated from separate, precomputed private keys, No. > can it only be generated interactively? Yes. But see the first question. Basically you can do an interactive step to generate a master pubkey and then use BIP32 non-hardened derivation to build thresholded children. On Sat, Mar 29, 2014 at 10:42 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > Respectfully, it's also possible to take a base58-encoded private key and run it through GPG, which is included in most Linux distros. But yet we have BIP38. BIP38 is a bad example (because it was created without public discussion due to a technical snafu). In this case I don't see anything wrong with specifying secret sharing, but I think— if possible— it should be carefully constructed so that the same polynomials and interpolation code can be used for threshold signatures (when encoding compatible data). If it requires entirely different code than the code for threshold signing it might as well be a file generic tool like SSSS. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:46 ` Gregory Maxwell @ 2014-03-29 19:49 ` Tamas Blummer 0 siblings, 0 replies; 90+ messages in thread From: Tamas Blummer @ 2014-03-29 19:49 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev, Dev Random [-- Attachment #1.1: Type: text/plain, Size: 666 bytes --] On 29.03.2014, at 18:46, Gregory Maxwell <gmaxwell@gmail•com> wrote: > In this case I don't see anything wrong with specifying secret > sharing, but I think— if possible— it should be carefully constructed > so that the same polynomials and interpolation code can be used for > threshold signatures (when encoding compatible data). The paper http://www.cs.princeton.edu/~stevenag/bitcoin_threshold_signatures.pdf does not mention anything special about the polynomial to use other than: "random polynomial f of degree t - 1 such that d = f(0)" Do you have reasons to assume that there is more to this? Since this is compatible with Matt's proposal. [-- Attachment #1.2: Type: text/html, Size: 1146 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:38 ` Matt Whitlock 2014-03-29 17:46 ` Gregory Maxwell @ 2014-03-29 17:48 ` devrandom 2014-03-29 17:51 ` Matt Whitlock 1 sibling, 1 reply; 90+ messages in thread From: devrandom @ 2014-03-29 17:48 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Dev On Sat, 2014-03-29 at 13:38 -0400, Matt Whitlock wrote: > On Saturday, 29 March 2014, at 10:25 am, Dev Random wrote: > > On Sat, 2014-03-29 at 11:44 -0400, Matt Whitlock wrote: > > > On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote: > > > > https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/ > > > > > > Thanks. This is great, although it makes some critical references to an > > > ACM paper for which no URL is provided, and thus I cannot implement it. > > > > > > A distributed ECDSA notwithstanding, we still need a way to decompose a > > > BIP32 master seed into shares. I am envisioning a scenario in which I > > > > It would seem that threshold ECDSA with keys derived from separate seeds > > has better security properties than one seed that is then split up. The > > main thing is that there is no single point of attack in the generation > > or signing. > > No contest here. But can threshold ECDSA work with BIP32? In other > words, can a threshold ECDSA public key be generated from separate, > precomputed private keys, or can it only be generated interactively? > Maybe the BIP32 master seeds have to be generated interactively, and > then all sets of corresponding derived keys are valid signing groups? That's a good point. In the paper, they have a deterministic wallet scheme in section 3.3. It is non-interactive, so that's good. On the other hand, it's not BIP32, so that adds complexity. > > Threshold ECDSA certainly sounds nice, but is anyone working on a BIP > for it? I would take it on myself, but I don't understand it well > enough yet, and publicly available information on it seems lacking. I > proposed this Shamir Secret Sharing BIP as an easily understood, easily > implemented measure that we can use today, with no changes to existing > Bitcoin software. It's low-hanging fruit. Good points, although multisig is catching on quickly in the ecosystem. AFAIK, all production wallets can send to p2sh addresses. -- Miron / devrandom ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:48 ` devrandom @ 2014-03-29 17:51 ` Matt Whitlock 2014-03-29 17:56 ` devrandom 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 17:51 UTC (permalink / raw) To: devrandom; +Cc: Bitcoin Dev On Saturday, 29 March 2014, at 10:48 am, devrandom wrote: > On Sat, 2014-03-29 at 13:38 -0400, Matt Whitlock wrote: > > Threshold ECDSA certainly sounds nice, but is anyone working on a BIP > > for it? I would take it on myself, but I don't understand it well > > enough yet, and publicly available information on it seems lacking. I > > proposed this Shamir Secret Sharing BIP as an easily understood, easily > > implemented measure that we can use today, with no changes to existing > > Bitcoin software. It's low-hanging fruit. > > Good points, although multisig is catching on quickly in the ecosystem. > AFAIK, all production wallets can send to p2sh addresses. As far as I know, Blockchain.info wallets still can't send to P2SH addresses. This was a *major* roadblock in the Bitcoin project that I've been working on for the past several months, and it was the impetus for my creating this Shamir Secret Sharing implementation in the first place. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 17:51 ` Matt Whitlock @ 2014-03-29 17:56 ` devrandom 0 siblings, 0 replies; 90+ messages in thread From: devrandom @ 2014-03-29 17:56 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Dev On Sat, 2014-03-29 at 13:51 -0400, Matt Whitlock wrote: > On Saturday, 29 March 2014, at 10:48 am, devrandom wrote: > > On Sat, 2014-03-29 at 13:38 -0400, Matt Whitlock wrote: > > > Threshold ECDSA certainly sounds nice, but is anyone working on a BIP > > > for it? I would take it on myself, but I don't understand it well > > > enough yet, and publicly available information on it seems lacking. I > > > proposed this Shamir Secret Sharing BIP as an easily understood, easily > > > implemented measure that we can use today, with no changes to existing > > > Bitcoin software. It's low-hanging fruit. > > > > Good points, although multisig is catching on quickly in the ecosystem. > > AFAIK, all production wallets can send to p2sh addresses. > > As far as I know, Blockchain.info wallets still can't send to P2SH > addresses. This was a *major* roadblock in the Bitcoin project that > I've been working on for the past several months, and it was the > impetus for my creating this Shamir Secret Sharing implementation in > the first place. That was true until they merged in my pull request a month ago ;) https://github.com/blockchain/My-Wallet/pull/59 -- Miron / devrandom ^ permalink raw reply [flat|nested] 90+ messages in thread
* [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
@ 2014-03-29 8:05 Matt Whitlock
2014-03-29 8:34 ` Tamas Blummer
` (3 more replies)
0 siblings, 4 replies; 90+ messages in thread
From: Matt Whitlock @ 2014-03-29 8:05 UTC (permalink / raw)
To: bitcoin-development
Abstract: A method is described for dividing a Bitcoin private key into shares in a manner such that the key can be reconstituted from any sufficiently large subset of the shares but such that individually the shares do not reveal any information about the key. This method is commonly known as Shamir's Secret Sharing Scheme. Additionally, an encoding methodology is proposed to standardize transmission and storage of shares.
Complete BIP: https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki
I am looking to have this BIP assigned a number and added to the bitcoin/bips repository. I invite any comments, questions, or suggestions.
^ permalink raw reply [flat|nested] 90+ messages in thread* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 8:05 Matt Whitlock @ 2014-03-29 8:34 ` Tamas Blummer 2014-03-29 8:44 ` Tamas Blummer ` (2 subsequent siblings) 3 siblings, 0 replies; 90+ messages in thread From: Tamas Blummer @ 2014-03-29 8:34 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 1460 bytes --] Great stuff Matt! I have an implementation of Shamir's Secret Sharing here: https://github.com/bitsofproof/bop-bitcoin-client-misc/blob/master/src/main/java/com/bitsofproof/supernode/misc/ShamirsSecretSharing.java What was missing was nice serialization. Thanks a lot for defining and starting the process. I will shortly adapt my code and check your test vectors. Regards, Tamas Blummer http://bitsofproof.com On 29.03.2014, at 09:05, Matt Whitlock <bip@mattwhitlock•name> wrote: > Abstract: A method is described for dividing a Bitcoin private key into shares in a manner such that the key can be reconstituted from any sufficiently large subset of the shares but such that individually the shares do not reveal any information about the key. This method is commonly known as Shamir's Secret Sharing Scheme. Additionally, an encoding methodology is proposed to standardize transmission and storage of shares. > > Complete BIP: https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > I am looking to have this BIP assigned a number and added to the bitcoin/bips repository. I invite any comments, questions, or suggestions. > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #1.2: Type: text/html, Size: 5155 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 8:05 Matt Whitlock 2014-03-29 8:34 ` Tamas Blummer @ 2014-03-29 8:44 ` Tamas Blummer 2014-03-29 8:51 ` Matt Whitlock 2014-03-29 16:54 ` Matt Whitlock 2014-03-29 9:08 ` Chris Beams 2014-03-29 9:21 ` Chris Beams 3 siblings, 2 replies; 90+ messages in thread From: Tamas Blummer @ 2014-03-29 8:44 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 1372 bytes --] Hi Matt, I used Shamir's Secret Sharing to decompose a seed for a BIP32 master key, that is I think more future relevant than a single key. Therefore suggest to adapt the BIP for a length used there typically 16 or 32 bytes and have a magic code to indicate its use as key vs. seed. Regards, Tamas Blummer http://bitsofproof.com On 29.03.2014, at 09:05, Matt Whitlock <bip@mattwhitlock•name> wrote: > Abstract: A method is described for dividing a Bitcoin private key into shares in a manner such that the key can be reconstituted from any sufficiently large subset of the shares but such that individually the shares do not reveal any information about the key. This method is commonly known as Shamir's Secret Sharing Scheme. Additionally, an encoding methodology is proposed to standardize transmission and storage of shares. > > Complete BIP: https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > I am looking to have this BIP assigned a number and added to the bitcoin/bips repository. I invite any comments, questions, or suggestions. > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #1.2: Type: text/html, Size: 5150 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 8:44 ` Tamas Blummer @ 2014-03-29 8:51 ` Matt Whitlock 2014-03-29 8:54 ` Matt Whitlock 2014-03-29 16:54 ` Matt Whitlock 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 8:51 UTC (permalink / raw) To: Tamas Blummer; +Cc: bitcoin-development On Saturday, 29 March 2014, at 9:44 am, Tamas Blummer wrote: > I used Shamir's Secret Sharing to decompose a seed for a BIP32 master key, that is I think more future relevant than a single key. > Therefore suggest to adapt the BIP for a length used there typically 16 or 32 bytes and have a magic code to indicate its use as key vs. seed. Master keys of 32 bytes would work as-is, as ordinary private keys are also 32 bytes. Secrets of other lengths could be supported if the function that generates a[i] from a[i-1] (which is presently SHA-256) were replaced with a function having parameterized output length, such as scrypt. Base58Check encodings of shares for secrets of lengths other than 32 bytes would have prefixes other than "SS", but that's not a huge concern. I suspect 32 bytes would be the most common secret length anyway, wouldn't you? ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 8:51 ` Matt Whitlock @ 2014-03-29 8:54 ` Matt Whitlock 0 siblings, 0 replies; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 8:54 UTC (permalink / raw) To: Tamas Blummer; +Cc: bitcoin-development On Saturday, 29 March 2014, at 4:51 am, Matt Whitlock wrote: > On Saturday, 29 March 2014, at 9:44 am, Tamas Blummer wrote: > > I used Shamir's Secret Sharing to decompose a seed for a BIP32 master key, that is I think more future relevant than a single key. > > Therefore suggest to adapt the BIP for a length used there typically 16 or 32 bytes and have a magic code to indicate its use as key vs. seed. > > Master keys of 32 bytes would work as-is, as ordinary private keys are also 32 bytes. Secrets of other lengths could be supported if the function that generates a[i] from a[i-1] (which is presently SHA-256) were replaced with a function having parameterized output length, such as scrypt. Actually, secrets with value greater than secp256k1_N cannot be supported because the modular arithmetic would destroy them. But any secret smaller than 256 bits would be fine. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 8:44 ` Tamas Blummer 2014-03-29 8:51 ` Matt Whitlock @ 2014-03-29 16:54 ` Matt Whitlock 2014-03-29 17:37 ` Tamas Blummer 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 16:54 UTC (permalink / raw) To: Tamas Blummer, bitcoin-development On Saturday, 29 March 2014, at 9:44 am, Tamas Blummer wrote: > I used Shamir's Secret Sharing to decompose a seed for a BIP32 master key, that is I think more future relevant than a single key. > Therefore suggest to adapt the BIP for a length used there typically 16 or 32 bytes and have a magic code to indicate its use as key vs. seed. I have expanded the BIP so that it additionally applies to BIP32 master seeds of sizes 128, 256, and 512 bits. https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki The most significant change versus the previous version is how the coefficients of the polynomials are constructed. Previously they were SHA-256 digests. Now they are SHA-512 digests, modulo a prime number that is selected depending on the size of the secret. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 16:54 ` Matt Whitlock @ 2014-03-29 17:37 ` Tamas Blummer 0 siblings, 0 replies; 90+ messages in thread From: Tamas Blummer @ 2014-03-29 17:37 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1.1: Type: text/plain, Size: 1951 bytes --] I had Matt's answer already, see below, but then I recognized that the group was not cc:-d, so I repeat: It would help on the user interface to include into individual shares: 1. Number of shares needed 2. A few bytes fingerprint of the secret so shares that likely belong together can be identified. I wonder how others weight security vs. usability in these questions. Regards, Tamas Blummer http://bitsofproof.com On Saturday, 29 March 2014, at 6:22 pm, Tamas Blummer wrote: > It might make sense to store the number of shares needed. I know it is not needed by math, but could help on user interface to say, > you need x more shares.. I intentionally omitted that information because it's a security risk. If an adversary gains control of one share and can see exactly how many more shares he needs, he may be able to plan a better attack. If he is clueless about how many shares he needs, then he may not be able to execute an attack at all because he may not know whether his information about what shares exist and where is complete. On 29.03.2014, at 17:54, Matt Whitlock <bip@mattwhitlock•name> wrote: > On Saturday, 29 March 2014, at 9:44 am, Tamas Blummer wrote: >> I used Shamir's Secret Sharing to decompose a seed for a BIP32 master key, that is I think more future relevant than a single key. >> Therefore suggest to adapt the BIP for a length used there typically 16 or 32 bytes and have a magic code to indicate its use as key vs. seed. > > I have expanded the BIP so that it additionally applies to BIP32 master seeds of sizes 128, 256, and 512 bits. > > https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > The most significant change versus the previous version is how the coefficients of the polynomials are constructed. Previously they were SHA-256 digests. Now they are SHA-512 digests, modulo a prime number that is selected depending on the size of the secret. > [-- Attachment #1.2: Type: text/html, Size: 5070 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 8:05 Matt Whitlock 2014-03-29 8:34 ` Tamas Blummer 2014-03-29 8:44 ` Tamas Blummer @ 2014-03-29 9:08 ` Chris Beams 2014-03-29 9:31 ` Matt Whitlock 2014-03-29 11:16 ` Matt Whitlock 2014-03-29 9:21 ` Chris Beams 3 siblings, 2 replies; 90+ messages in thread From: Chris Beams @ 2014-03-29 9:08 UTC (permalink / raw) To: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 1443 bytes --] Matt, could you expand on use cases for which you see Shamir's Secret Sharing Scheme as the best tool for the job? In particular, when do you see that it would be superior to simply going with multisig in the first place? Perhaps you see these as complimentary approaches, toward defense-in-depth? In any case, the Motivation and Rationale sections of the BIP in its current form are silent on these questions. On Mar 29, 2014, at 9:05 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > Abstract: A method is described for dividing a Bitcoin private key into shares in a manner such that the key can be reconstituted from any sufficiently large subset of the shares but such that individually the shares do not reveal any information about the key. This method is commonly known as Shamir's Secret Sharing Scheme. Additionally, an encoding methodology is proposed to standardize transmission and storage of shares. > > Complete BIP: https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > I am looking to have this BIP assigned a number and added to the bitcoin/bips repository. I invite any comments, questions, or suggestions. > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 841 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 9:08 ` Chris Beams @ 2014-03-29 9:31 ` Matt Whitlock 2014-03-29 11:16 ` Matt Whitlock 1 sibling, 0 replies; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 9:31 UTC (permalink / raw) To: Chris Beams; +Cc: bitcoin-development On Saturday, 29 March 2014, at 10:08 am, Chris Beams wrote: > Matt, could you expand on use cases for which you see Shamir's Secret Sharing Scheme as the best tool for the job? In particular, when do you see that it would be superior to simply going with multisig in the first place? Perhaps you see these as complimentary approaches, toward defense-in-depth? In any case, the Motivation and Rationale sections of the BIP in its current form are silent on these questions. Okay, yes, I will address these questions. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 9:08 ` Chris Beams 2014-03-29 9:31 ` Matt Whitlock @ 2014-03-29 11:16 ` Matt Whitlock 2014-03-29 11:54 ` Chris Beams 1 sibling, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 11:16 UTC (permalink / raw) To: Chris Beams; +Cc: bitcoin-development On Saturday, 29 March 2014, at 10:08 am, Chris Beams wrote: > Matt, could you expand on use cases for which you see Shamir's Secret Sharing Scheme as the best tool for the job? In particular, when do you see that it would be superior to simply going with multisig in the first place? Perhaps you see these as complimentary approaches, toward defense-in-depth? In any case, the Motivation and Rationale sections of the BIP in its current form are silent on these questions. I have added two new sections to address your questions. https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 11:16 ` Matt Whitlock @ 2014-03-29 11:54 ` Chris Beams 2014-03-29 13:27 ` Jeff Garzik 0 siblings, 1 reply; 90+ messages in thread From: Chris Beams @ 2014-03-29 11:54 UTC (permalink / raw) To: Matt Whitlock; +Cc: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 791 bytes --] Enlightening; thanks, Matt. And apologies to the list for my earlier inadvertent double-post. On Mar 29, 2014, at 12:16 PM, Matt Whitlock <bip@mattwhitlock•name> wrote: > On Saturday, 29 March 2014, at 10:08 am, Chris Beams wrote: >> Matt, could you expand on use cases for which you see Shamir's Secret Sharing Scheme as the best tool for the job? In particular, when do you see that it would be superior to simply going with multisig in the first place? Perhaps you see these as complimentary approaches, toward defense-in-depth? In any case, the Motivation and Rationale sections of the BIP in its current form are silent on these questions. > > I have added two new sections to address your questions. > > https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 841 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 11:54 ` Chris Beams @ 2014-03-29 13:27 ` Jeff Garzik 2014-03-29 13:36 ` Mike Hearn 0 siblings, 1 reply; 90+ messages in thread From: Jeff Garzik @ 2014-03-29 13:27 UTC (permalink / raw) To: Chris Beams; +Cc: Bitcoin Dev The comparison with multisig fails to mention that multi-signature transactions explicitly define security at the transaction level. This permits fine-grained specificity of what a key holder may approve. Shamir is much more coarse-grained. You reconstitute a private key, which may then be used to control anything that key controls. Thus, in addition to Shamir itself, you need policies such as "no key reuse." My first impression of Shamir many moons ago was "cool!" but that's since been tempered by thinking through the use cases. Shamir has a higher D.I.Y. factor, with a correspondingly larger surface of things-that-could-go-wrong, IMO. (None of this implies making an informational BIP lacks value; I'm all for an informational BIP) On Sat, Mar 29, 2014 at 7:54 AM, Chris Beams <chris@beams•io> wrote: > Enlightening; thanks, Matt. And apologies to the list for my earlier inadvertent double-post. > > On Mar 29, 2014, at 12:16 PM, Matt Whitlock <bip@mattwhitlock•name> wrote: > >> On Saturday, 29 March 2014, at 10:08 am, Chris Beams wrote: >>> Matt, could you expand on use cases for which you see Shamir's Secret Sharing Scheme as the best tool for the job? In particular, when do you see that it would be superior to simply going with multisig in the first place? Perhaps you see these as complimentary approaches, toward defense-in-depth? In any case, the Motivation and Rationale sections of the BIP in its current form are silent on these questions. >> >> I have added two new sections to address your questions. >> >> https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > > ------------------------------------------------------------------------------ > > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 13:27 ` Jeff Garzik @ 2014-03-29 13:36 ` Mike Hearn 2014-03-29 13:38 ` Tamas Blummer 2014-03-29 14:10 ` Matt Whitlock 0 siblings, 2 replies; 90+ messages in thread From: Mike Hearn @ 2014-03-29 13:36 UTC (permalink / raw) To: Jeff Garzik; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 3054 bytes --] Right - the explanation in the BIP about the board of directors is IMO a little misleading. The problem is with splitting a private key is that at some point, *someone* has to get the full private key back and they can then just remember the private key to undo the system. CHECKMULTISIG avoids this. I can imagine that there may be occasional uses for splitting a wallet seed like this, like for higher security cold wallets, but I suspect an ongoing shared account like a corporate account is still best off using CHECKMULTISIG or the n-of-m ECDSA threshold scheme proposed by Ali et al. On Sat, Mar 29, 2014 at 2:27 PM, Jeff Garzik <jgarzik@bitpay•com> wrote: > The comparison with multisig fails to mention that multi-signature > transactions explicitly define security at the transaction level. > This permits fine-grained specificity of what a key holder may > approve. > > Shamir is much more coarse-grained. You reconstitute a private key, > which may then be used to control anything that key controls. Thus, > in addition to Shamir itself, you need policies such as "no key > reuse." > > My first impression of Shamir many moons ago was "cool!" but that's > since been tempered by thinking through the use cases. Shamir has a > higher D.I.Y. factor, with a correspondingly larger surface of > things-that-could-go-wrong, IMO. > > (None of this implies making an informational BIP lacks value; I'm all > for an informational BIP) > > > > > On Sat, Mar 29, 2014 at 7:54 AM, Chris Beams <chris@beams•io> wrote: > > Enlightening; thanks, Matt. And apologies to the list for my earlier > inadvertent double-post. > > > > On Mar 29, 2014, at 12:16 PM, Matt Whitlock <bip@mattwhitlock•name> > wrote: > > > >> On Saturday, 29 March 2014, at 10:08 am, Chris Beams wrote: > >>> Matt, could you expand on use cases for which you see Shamir's Secret > Sharing Scheme as the best tool for the job? In particular, when do you see > that it would be superior to simply going with multisig in the first place? > Perhaps you see these as complimentary approaches, toward defense-in-depth? > In any case, the Motivation and Rationale sections of the BIP in its > current form are silent on these questions. > >> > >> I have added two new sections to address your questions. > >> > >> https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > > > > > > ------------------------------------------------------------------------------ > > > > _______________________________________________ > > Bitcoin-development mailing list > > Bitcoin-development@lists•sourceforge.net > > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > > > > > -- > Jeff Garzik > Bitcoin core developer and open source evangelist > BitPay, Inc. https://bitpay.com/ > > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > [-- Attachment #2: Type: text/html, Size: 4392 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 13:36 ` Mike Hearn @ 2014-03-29 13:38 ` Tamas Blummer 2014-03-29 14:10 ` Matt Whitlock 1 sibling, 0 replies; 90+ messages in thread From: Tamas Blummer @ 2014-03-29 13:38 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Dev [-- Attachment #1.1: Type: text/plain, Size: 3617 bytes --] This is why my motivation is rather secure backup, not multisig. Instead of storing encrypted seed in one location and the passphrase for it in an other location, one can just store two shares in two places. > Right - the explanation in the BIP about the board of directors is IMO a little misleading. The problem is with splitting a private key is that at some point, someone has to get the full private key back and they can then just remember the private key to undo the system. CHECKMULTISIG avoids this. > > I can imagine that there may be occasional uses for splitting a wallet seed like this, like for higher security cold wallets, but I suspect an ongoing shared account like a corporate account is still best off using CHECKMULTISIG or the n-of-m ECDSA threshold scheme proposed by Ali et al. > > > On Sat, Mar 29, 2014 at 2:27 PM, Jeff Garzik <jgarzik@bitpay•com> wrote: > The comparison with multisig fails to mention that multi-signature > transactions explicitly define security at the transaction level. > This permits fine-grained specificity of what a key holder may > approve. > > Shamir is much more coarse-grained. You reconstitute a private key, > which may then be used to control anything that key controls. Thus, > in addition to Shamir itself, you need policies such as "no key > reuse." > > My first impression of Shamir many moons ago was "cool!" but that's > since been tempered by thinking through the use cases. Shamir has a > higher D.I.Y. factor, with a correspondingly larger surface of > things-that-could-go-wrong, IMO. > > (None of this implies making an informational BIP lacks value; I'm all > for an informational BIP) > > > > > On Sat, Mar 29, 2014 at 7:54 AM, Chris Beams <chris@beams•io> wrote: > > Enlightening; thanks, Matt. And apologies to the list for my earlier inadvertent double-post. > > > > On Mar 29, 2014, at 12:16 PM, Matt Whitlock <bip@mattwhitlock•name> wrote: > > > >> On Saturday, 29 March 2014, at 10:08 am, Chris Beams wrote: > >>> Matt, could you expand on use cases for which you see Shamir's Secret Sharing Scheme as the best tool for the job? In particular, when do you see that it would be superior to simply going with multisig in the first place? Perhaps you see these as complimentary approaches, toward defense-in-depth? In any case, the Motivation and Rationale sections of the BIP in its current form are silent on these questions. > >> > >> I have added two new sections to address your questions. > >> > >> https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > > > > > ------------------------------------------------------------------------------ > > > > _______________________________________________ > > Bitcoin-development mailing list > > Bitcoin-development@lists•sourceforge.net > > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > > > > > -- > Jeff Garzik > Bitcoin core developer and open source evangelist > BitPay, Inc. https://bitpay.com/ > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development [-- Attachment #1.2: Type: text/html, Size: 5219 bytes --] [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 495 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 13:36 ` Mike Hearn 2014-03-29 13:38 ` Tamas Blummer @ 2014-03-29 14:10 ` Matt Whitlock 2014-03-29 14:19 ` Jeff Garzik 2014-03-29 14:28 ` Watson Ladd 1 sibling, 2 replies; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 14:10 UTC (permalink / raw) To: bitcoin-development On Saturday, 29 March 2014, at 2:36 pm, Mike Hearn wrote: > Right - the explanation in the BIP about the board of directors is IMO a > little misleading. The problem is with splitting a private key is that at > some point, *someone* has to get the full private key back and they can > then just remember the private key to undo the system. CHECKMULTISIG avoids > this. The implication is that every director would want to retain the board's private key for himself but also would want to prevent every other director from successfully retaining the private key for himself, leading to a perpetual stalemate in which no director ever gets to retain the private key. > I can imagine that there may be occasional uses for splitting a wallet seed > like this, like for higher security cold wallets, but I suspect an ongoing > shared account like a corporate account is still best off using > CHECKMULTISIG or the n-of-m ECDSA threshold scheme proposed by Ali et al. Multisig does not allow for the topology I described. Say the board has seven directors, meaning the majority threshold is four. This means the organization needs the consent of six individuals in order to sign a transaction: the president, the CFO, and any four of the board members. A 6-of-9 multisig would not accomplish the same policy, as then any six board members could successfully sign a transaction without the consent of the president or CFO. Of course the multi-signature scheme could be expanded to allow for hierarchical threshold topologies, or Shamir's Secret Sharing can be used to distribute keys at the second level (and further, if desired). ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 14:10 ` Matt Whitlock @ 2014-03-29 14:19 ` Jeff Garzik 2014-03-29 14:55 ` Matt Whitlock 2014-03-29 14:28 ` Watson Ladd 1 sibling, 1 reply; 90+ messages in thread From: Jeff Garzik @ 2014-03-29 14:19 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Dev On Sat, Mar 29, 2014 at 10:10 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > Multisig does not allow for the topology I described. Say the board has seven directors, meaning the majority threshold is four. This means the organization needs the consent of six individuals in order to sign a transaction: the president, the CFO, and any four of the board members. A 6-of-9 multisig would not accomplish the same policy, as then any six board members could successfully sign a transaction without the consent of the president or CFO. Of course the multi-signature scheme could be expanded to allow for hierarchical threshold topologies, or Shamir's Secret Sharing can be used to distribute keys at the second level (and further, if desired). Disagree with "does not allow" Review bitcoin's script language. Bitcoin script can handle the use case you describe. Add conditionals to the bitcoin script, OP_IF etc. You can do 'multisig AND multisig' type boolean logic entirely in script, and be far more flexible than a single CHECKMULTISIG affords. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 14:19 ` Jeff Garzik @ 2014-03-29 14:55 ` Matt Whitlock 2014-03-29 15:04 ` Mike Hearn 0 siblings, 1 reply; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 14:55 UTC (permalink / raw) To: Jeff Garzik; +Cc: Bitcoin Dev On Saturday, 29 March 2014, at 10:19 am, Jeff Garzik wrote: > On Sat, Mar 29, 2014 at 10:10 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > > Multisig does not allow for the topology I described. Say the board has seven directors, meaning the majority threshold is four. This means the organization needs the consent of six individuals in order to sign a transaction: the president, the CFO, and any four of the board members. A 6-of-9 multisig would not accomplish the same policy, as then any six board members could successfully sign a transaction without the consent of the president or CFO. Of course the multi-signature scheme could be expanded to allow for hierarchical threshold topologies, or Shamir's Secret Sharing can be used to distribute keys at the second level (and further, if desired). > > Disagree with "does not allow" Review bitcoin's script language. > > Bitcoin script can handle the use case you describe. Add conditionals > to the bitcoin script, OP_IF etc. You can do 'multisig AND multisig' > type boolean logic entirely in script, and be far more flexible than a > single CHECKMULTISIG affords. Depends on your definition of "can." Bitcoin's scripting language is awesome, but it's mostly useless due to the requirement that scripts match one of a select few "standard" templates in order to be allowed to propagate across the network and be mined into blocks. I really hate IsStandard and wish it would die. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 14:55 ` Matt Whitlock @ 2014-03-29 15:04 ` Mike Hearn 0 siblings, 0 replies; 90+ messages in thread From: Mike Hearn @ 2014-03-29 15:04 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 1972 bytes --] Nobody is exactly thrilled by IsStandard, but it's not a deal-killer. If you have a use for a new type of script it can be added, and people do upgrade: http://getaddr.bitnodes.io/dashboard/chart/?days=30 As you can see the 0.9 rollout is going OK. If a new script type had been made standard for 0.9 like OP_RETURN was, I'm guessing it'll only be another month or so and it'll be quite usable. On Sat, Mar 29, 2014 at 3:55 PM, Matt Whitlock <bip@mattwhitlock•name>wrote: > On Saturday, 29 March 2014, at 10:19 am, Jeff Garzik wrote: > > On Sat, Mar 29, 2014 at 10:10 AM, Matt Whitlock <bip@mattwhitlock•name> > wrote: > > > Multisig does not allow for the topology I described. Say the board > has seven directors, meaning the majority threshold is four. This means the > organization needs the consent of six individuals in order to sign a > transaction: the president, the CFO, and any four of the board members. A > 6-of-9 multisig would not accomplish the same policy, as then any six board > members could successfully sign a transaction without the consent of the > president or CFO. Of course the multi-signature scheme could be expanded to > allow for hierarchical threshold topologies, or Shamir's Secret Sharing can > be used to distribute keys at the second level (and further, if desired). > > > > Disagree with "does not allow" Review bitcoin's script language. > > > > Bitcoin script can handle the use case you describe. Add conditionals > > to the bitcoin script, OP_IF etc. You can do 'multisig AND multisig' > > type boolean logic entirely in script, and be far more flexible than a > > single CHECKMULTISIG affords. > > Depends on your definition of "can." Bitcoin's scripting language is > awesome, but it's mostly useless due to the requirement that scripts match > one of a select few "standard" templates in order to be allowed to > propagate across the network and be mined into blocks. I really hate > IsStandard and wish it would die. > [-- Attachment #2: Type: text/html, Size: 2609 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 14:10 ` Matt Whitlock 2014-03-29 14:19 ` Jeff Garzik @ 2014-03-29 14:28 ` Watson Ladd 2014-03-29 14:36 ` Gregory Maxwell 1 sibling, 1 reply; 90+ messages in thread From: Watson Ladd @ 2014-03-29 14:28 UTC (permalink / raw) To: Matt Whitlock; +Cc: Bitcoin Dev On Sat, Mar 29, 2014 at 10:10 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > On Saturday, 29 March 2014, at 2:36 pm, Mike Hearn wrote: >> Right - the explanation in the BIP about the board of directors is IMO a >> little misleading. The problem is with splitting a private key is that at >> some point, *someone* has to get the full private key back and they can >> then just remember the private key to undo the system. CHECKMULTISIG avoids >> this. > > The implication is that every director would want to retain the board's private key for himself but also would want to prevent every other director from successfully retaining the private key for himself, leading to a perpetual stalemate in which no director ever gets to retain the private key. This is not the case: one can use MPC techniques to compute a signature from shares without reconstructing the private key. There is a paper on this for bitcoin, but I don't know where it is. > >> I can imagine that there may be occasional uses for splitting a wallet seed >> like this, like for higher security cold wallets, but I suspect an ongoing >> shared account like a corporate account is still best off using >> CHECKMULTISIG or the n-of-m ECDSA threshold scheme proposed by Ali et al. > > Multisig does not allow for the topology I described. Say the board has seven directors, meaning the majority threshold is four. This means the organization needs the consent of six individuals in order to sign a transaction: the president, the CFO, and any four of the board members. A 6-of-9 multisig would not accomplish the same policy, as then any six board members could successfully sign a transaction without the consent of the president or CFO. Of course the multi-signature scheme could be expanded to allow for hierarchical threshold topologies, or Shamir's Secret Sharing can be used to distribute keys at the second level (and further, if desired). > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 14:28 ` Watson Ladd @ 2014-03-29 14:36 ` Gregory Maxwell 2014-03-29 15:01 ` Matt Whitlock 0 siblings, 1 reply; 90+ messages in thread From: Gregory Maxwell @ 2014-03-29 14:36 UTC (permalink / raw) To: Watson Ladd; +Cc: Bitcoin Dev On Sat, Mar 29, 2014 at 7:28 AM, Watson Ladd <wbl@uchicago•edu> wrote: > This is not the case: one can use MPC techniques to compute a > signature from shares without reconstructing the private key. There is > a paper on this for bitcoin, but I don't know where it is. Practically speaking you cannot unless the technique used is one carefully selected to make it possible. This proposal isn't such a scheme I beleieve, however, and I think I'd strongly prefer that we BIP standardize a formulation which also has this property. The paper you want is http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.9913 There will soon be a paper coming out from some princeton folks about refining that and applying it to Bitcoin. You can use the secret sharing from threshold ecdsa in the not-super-useful way where you just recombine the private key and sign... but you can also use it to compute a secret shared signature and then interpolate back the signature... avoiding the need for any trusted device in holding the signature. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 14:36 ` Gregory Maxwell @ 2014-03-29 15:01 ` Matt Whitlock 0 siblings, 0 replies; 90+ messages in thread From: Matt Whitlock @ 2014-03-29 15:01 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev On Saturday, 29 March 2014, at 7:36 am, Gregory Maxwell wrote: > On Sat, Mar 29, 2014 at 7:28 AM, Watson Ladd <wbl@uchicago•edu> wrote: > > This is not the case: one can use MPC techniques to compute a > > signature from shares without reconstructing the private key. There is > > a paper on this for bitcoin, but I don't know where it is. > > Practically speaking you cannot unless the technique used is one > carefully selected to make it possible. This proposal isn't such a > scheme I beleieve, however, and I think I'd strongly prefer that we > BIP standardize a formulation which also has this property. I too would prefer that, but I do not believe there exists a method for computing a traditional signature from decomposed private key shares. Unless I'm mistaken, the composed signature has a different formula and requires a different verification algorithm from the ECDSA signatures we're using today. Thus, such a scheme would require a change to the Bitcoin scripting language. I specifically did not want to address that in my BIP because changes like that take too long. I am aiming to be useful in the present. ^ permalink raw reply [flat|nested] 90+ messages in thread
* Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys 2014-03-29 8:05 Matt Whitlock ` (2 preceding siblings ...) 2014-03-29 9:08 ` Chris Beams @ 2014-03-29 9:21 ` Chris Beams 3 siblings, 0 replies; 90+ messages in thread From: Chris Beams @ 2014-03-29 9:21 UTC (permalink / raw) To: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 1436 bytes --] Matt, could you expand on use cases for which you see Shamir's Secret Sharing as the best tool for the job? In particular, when do you see that it would be superior to simply going with multisig in the first place? Perhaps you see these as complimentary approaches, toward defense in depth? In any case, the Motivation and Rationale sections of the BIP in its current form are silent on these questions. On Mar 29, 2014, at 9:05 AM, Matt Whitlock <bip@mattwhitlock•name> wrote: > Abstract: A method is described for dividing a Bitcoin private key into shares in a manner such that the key can be reconstituted from any sufficiently large subset of the shares but such that individually the shares do not reveal any information about the key. This method is commonly known as Shamir's Secret Sharing Scheme. Additionally, an encoding methodology is proposed to standardize transmission and storage of shares. > > Complete BIP: https://github.com/whitslack/btctool/blob/bip/bip-xxxx.mediawiki > > I am looking to have this BIP assigned a number and added to the bitcoin/bips repository. I invite any comments, questions, or suggestions. > > ------------------------------------------------------------------------------ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development [-- Attachment #2: Message signed with OpenPGP using GPGMail --] [-- Type: application/pgp-signature, Size: 841 bytes --] ^ permalink raw reply [flat|nested] 90+ messages in thread
end of thread, other threads:[~2014-08-14 19:54 UTC | newest]
Thread overview: 90+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-04-03 12:41 [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys Nikita Schmidt
2014-04-03 21:42 ` Matt Whitlock
2014-04-04 13:51 ` Nikita Schmidt
2014-04-04 14:14 ` Gregory Maxwell
2014-04-04 16:05 ` Matt Whitlock
2014-04-04 16:25 ` Gregory Maxwell
2014-04-04 16:36 ` Matt Whitlock
2014-04-04 17:08 ` Gregory Maxwell
2014-04-04 17:16 ` Matt Whitlock
2014-04-04 17:51 ` Gregory Maxwell
2014-04-04 18:53 ` Matt Whitlock
2014-04-04 16:03 ` Matt Whitlock
2014-04-08 0:33 ` Nikita Schmidt
2014-04-08 0:38 ` Gregory Maxwell
2014-04-08 1:46 ` Matt Whitlock
2014-04-08 2:07 ` Gregory Maxwell
2014-04-08 11:52 ` Matt Whitlock
2014-04-10 22:31 ` Nikita Schmidt
2014-04-22 8:06 ` Jan Møller
2014-04-22 8:11 ` Matt Whitlock
2014-04-22 8:27 ` Jan Møller
2014-04-22 8:29 ` Matt Whitlock
2014-04-22 8:39 ` Jan Møller
2014-04-22 8:43 ` Matt Whitlock
2014-04-22 8:51 ` Jan Møller
2014-04-22 9:13 ` Matt Whitlock
2014-04-22 11:50 ` Justin A
2014-04-22 8:35 ` Matt Whitlock
2014-04-22 8:39 ` Tamas Blummer
2014-04-22 8:40 ` Matt Whitlock
2014-04-22 8:43 ` Tamas Blummer
2014-04-22 8:47 ` Matt Whitlock
2014-04-22 8:50 ` Tamas Blummer
2014-04-22 15:32 ` Mark Friedenbach
2014-04-22 15:49 ` Tamas Blummer
2014-04-22 17:03 ` Mark Friedenbach
2014-04-22 17:07 ` Jan Møller
2014-04-22 18:29 ` Tamas Blummer
2014-04-22 18:46 ` Gregory Maxwell
2014-04-23 5:33 ` Tamas Blummer
2014-04-23 6:16 ` Gregory Maxwell
2014-05-05 19:36 ` Nikita Schmidt
2014-05-12 12:09 ` Jan Møller
2014-08-14 19:23 ` Nikita Schmidt
2014-04-22 13:37 ` Nikita Schmidt
2014-04-22 8:15 ` Gregory Maxwell
2014-04-22 8:49 ` Jan Møller
[not found] <CACsn0ckScTWG4YxNCscxvtdsmcUkxtR2Gi-rdBs2HCkirPz5rA@mail.gmail.com>
2014-03-29 15:44 ` Matt Whitlock
2014-03-29 16:59 ` Alan Reiner
2014-03-29 17:19 ` Matt Whitlock
2014-03-29 17:52 ` Alan Reiner
2014-03-29 18:00 ` Matt Whitlock
2014-03-29 18:08 ` Alan Reiner
2014-03-29 18:10 ` Matt Whitlock
[not found] ` <CAAt2M18j7bGDsKouVw+e4j+FMiJ4vK6-sx+nrkwHyiKLqiH7Jg@mail.gmail.com>
2014-03-29 19:34 ` Natanael
2014-04-04 2:38 ` Jeff Garzik
2014-03-29 18:16 ` Tamas Blummer
2014-03-29 18:41 ` Alan Reiner
2014-03-29 17:28 ` Roy Badami
2014-03-29 17:42 ` Matt Whitlock
2014-03-29 17:51 ` Roy Badami
2014-03-29 17:28 ` devrandom
[not found] ` <1396113933.8809.91.camel@mimiz>
2014-03-29 17:38 ` Matt Whitlock
2014-03-29 17:46 ` Gregory Maxwell
2014-03-29 19:49 ` Tamas Blummer
2014-03-29 17:48 ` devrandom
2014-03-29 17:51 ` Matt Whitlock
2014-03-29 17:56 ` devrandom
-- strict thread matches above, loose matches on Subject: below --
2014-03-29 8:05 Matt Whitlock
2014-03-29 8:34 ` Tamas Blummer
2014-03-29 8:44 ` Tamas Blummer
2014-03-29 8:51 ` Matt Whitlock
2014-03-29 8:54 ` Matt Whitlock
2014-03-29 16:54 ` Matt Whitlock
2014-03-29 17:37 ` Tamas Blummer
2014-03-29 9:08 ` Chris Beams
2014-03-29 9:31 ` Matt Whitlock
2014-03-29 11:16 ` Matt Whitlock
2014-03-29 11:54 ` Chris Beams
2014-03-29 13:27 ` Jeff Garzik
2014-03-29 13:36 ` Mike Hearn
2014-03-29 13:38 ` Tamas Blummer
2014-03-29 14:10 ` Matt Whitlock
2014-03-29 14:19 ` Jeff Garzik
2014-03-29 14:55 ` Matt Whitlock
2014-03-29 15:04 ` Mike Hearn
2014-03-29 14:28 ` Watson Ladd
2014-03-29 14:36 ` Gregory Maxwell
2014-03-29 15:01 ` Matt Whitlock
2014-03-29 9:21 ` Chris Beams
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox