Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Nikita Schmidt]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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!)

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Nikita Schmidt]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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? :)

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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).

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Nikita Schmidt]

>
> 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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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?

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Nikita Schmidt]

> 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).

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jan Møller]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jan Møller]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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?

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jan Møller]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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).

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jan Møller]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Justin A]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Mark Friedenbach]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Mark Friedenbach]

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.
> 

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jan Møller]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Nikita Schmidt]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jan Møller]

[-- 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:
> &#149; 3 signs your SCM is hindering your productivity
> &#149; Requirements for releasing software faster
> &#149; 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Nikita Schmidt]

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?)

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Nikita Schmidt]

>
> 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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jan Møller]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Alan Reiner]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Alan Reiner]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.)

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Alan Reiner]

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)

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Natanael]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jeff Garzik]

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/

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Alan Reiner]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Roy Badami]

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
> 

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Roy Badami]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[devrandom]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[devrandom]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[devrandom]

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

[Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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?

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Chris Beams]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Chris Beams]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jeff Garzik]

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/

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Mike Hearn]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Tamas Blummer]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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).

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Jeff Garzik]

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/

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Mike Hearn]

[-- 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 --]

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Watson Ladd]

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

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Matt Whitlock]

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.

Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys

[Chris Beams]

[-- 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 --]