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



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

2014-04-22 Thread Tamas Blummer

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



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
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

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 b...@mattwhitlock.namewrote:

 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?

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

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 b...@mattwhitlock.namewrote:

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

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

2014-04-22 Thread Tamas Blummer

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



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
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

2014-04-22 Thread 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.

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

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 gmaxw...@gmail.comwrote:

 On Tue, Apr 22, 2014 at 1:06 AM, Jan Møller jan.mol...@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

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

2014-04-22 Thread 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 b...@mattwhitlock.namewrote:
  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-.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

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

2014-04-22 Thread Justin A

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

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

2014-04-22 Thread 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.

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

2014-04-22 Thread 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

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

2014-04-22 Thread Tamas Blummer

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



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
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

2014-04-10 Thread 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).

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

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

2014-04-08 Thread 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 b...@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
  nik...@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?

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

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

2014-04-07 Thread 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.

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

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

2014-04-07 Thread Gregory Maxwell

On Mon, Apr 7, 2014 at 5:33 PM, Nikita Schmidt
nik...@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.

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

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

2014-04-07 Thread 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
 nik...@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.

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

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

2014-04-07 Thread Gregory Maxwell

On Mon, Apr 7, 2014 at 6:46 PM, Matt Whitlock b...@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
 nik...@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.

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

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

2014-04-04 Thread Gregory Maxwell

On Fri, Apr 4, 2014 at 6:51 AM, Nikita Schmidt
nik...@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.

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

On Friday, 4 April 2014, at 5:51 pm, Nikita Schmidt wrote:
 On 4 April 2014 01:42, Matt Whitlock b...@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.

--
___
Bitcoin-development mailing list

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

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.

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

On Friday, 4 April 2014, at 9:25 am, Gregory Maxwell wrote:
 On Fri, Apr 4, 2014 at 9:05 AM, Matt Whitlock b...@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? :)

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

2014-04-04 Thread Gregory Maxwell

On Fri, Apr 4, 2014 at 9:36 AM, Matt Whitlock b...@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).

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

On Friday, 4 April 2014, at 10:08 am, Gregory Maxwell wrote:
 On Fri, Apr 4, 2014 at 9:36 AM, Matt Whitlock b...@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.

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

2014-04-04 Thread Gregory Maxwell

On Fri, Apr 4, 2014 at 10:16 AM, Matt Whitlock b...@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.

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

On Friday, 4 April 2014, at 10:51 am, Gregory Maxwell wrote:
 On Fri, Apr 4, 2014 at 10:16 AM, Matt Whitlock b...@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.

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

2014-04-03 Thread 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 0x 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 0x 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!)


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

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

signature.asc
Description: Message signed with OpenPGP using GPGMail
--
___
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

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



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
___
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

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?

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

2014-03-29 Thread Chris Beams

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



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
___
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

2014-03-29 Thread Chris Beams

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



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
___
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

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.

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

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

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

2014-03-29 Thread Chris Beams

Enlightening; thanks, Matt. And apologies to the list for my earlier 
inadvertent double-post.

On Mar 29, 2014, at 12:16 PM, Matt Whitlock b...@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-.mediawiki



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
___
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

2014-03-29 Thread Mike Hearn

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 jgar...@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 ch...@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 b...@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-.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

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

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

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

2014-03-29 Thread Jeff Garzik

On Sat, Mar 29, 2014 at 10:10 AM, Matt Whitlock b...@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/

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

On Saturday, 29 March 2014, at 10:19 am, Jeff Garzik wrote:
 On Sat, Mar 29, 2014 at 10:10 AM, Matt Whitlock b...@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.

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

On Saturday, 29 March 2014, at 7:36 am, Gregory Maxwell wrote:
 On Sat, Mar 29, 2014 at 7:28 AM, Watson Ladd w...@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.

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

2014-03-29 Thread Mike Hearn

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 b...@mattwhitlock.namewrote:

 On Saturday, 29 March 2014, at 10:19 am, Jeff Garzik wrote:
  On Sat, Mar 29, 2014 at 10:10 AM, Matt Whitlock b...@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.

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

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

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

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

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.

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

2014-03-29 Thread Roy Badami

Right now there are also people simply taking base58-encoded private
keys and running them through -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 implementation[1] seems to be included in most Linux distros).

roy

[1] http://point-at-infinity.org//

On Sat, Mar 29, 2014 at 12:59:19PM -0400, Alan Reiner wrote:

-Alan

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

2014-03-29 Thread 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

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

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



signature.asc
Description: Message signed with OpenPGP using GPGMail
--
___
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

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.

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

2014-03-29 Thread Gregory Maxwell

On Sat, Mar 29, 2014 at 10:38 AM, Matt Whitlock b...@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 b...@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 .

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

2014-03-29 Thread 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

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

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

2014-03-29 Thread 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 -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  implementation[1] seems to be included in most Linux distros).
  
  roy
  
  [1] http://point-at-infinity.org//
 
 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



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

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.

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

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

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


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




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

On Saturday, 29 March 2014, at 2:08 pm, Alan Reiner wrote:
 Regardless of how  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.

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

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 etothe...@gmail.com
 mailto:etothe...@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



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

2014-03-29 Thread Natanael

Den 29 mar 2014 19:15 skrev Matt Whitlock b...@mattwhitlock.name:

 On Saturday, 29 March 2014, at 2:08 pm, Alan Reiner wrote:
  Regardless of how  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.
--
___
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