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

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

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

2014-03-29 Thread Matt Whitlock
On Saturday, 29 March 2014, at 4:51 am, Matt Whitlock wrote:
 On Saturday, 29 March 2014, at 9:44 am, Tamas Blummer wrote:
  I used Shamir's Secret Sharing to decompose a seed for a BIP32 master key, 
  that is I think more future relevant than a single key.
  Therefore suggest to adapt the BIP for a length used there typically 16 or 
  32 bytes and have a magic code to indicate its use as key vs. seed.
 
 Master keys of 32 bytes would work as-is, as ordinary private keys are also 
 32 bytes. Secrets of other lengths could be supported if the function that 
 generates a[i] from a[i-1] (which is presently SHA-256) were replaced with a 
 function having parameterized output length, such as scrypt.

Actually, secrets with value greater than secp256k1_N cannot be supported 
because the modular arithmetic would destroy them. But any secret smaller than 
256 bits would be fine.

--
___
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 Matt Whitlock
On Saturday, 29 March 2014, at 9:44 am, Tamas Blummer wrote:
 I used Shamir's Secret Sharing to decompose a seed for a BIP32 master key, 
 that is I think more future relevant than a single key.
 Therefore suggest to adapt the BIP for a length used there typically 16 or 32 
 bytes and have a magic code to indicate its use as key vs. seed.

Master keys of 32 bytes would work as-is, as ordinary private keys are also 32 
bytes. Secrets of other lengths could be supported if the function that 
generates a[i] from a[i-1] (which is presently SHA-256) were replaced with a 
function having parameterized output length, such as scrypt.

Base58Check encodings of shares for secrets of lengths other than 32 bytes 
would have prefixes other than SS, but that's not a huge concern. I suspect 
32 bytes would be the most common secret length anyway, wouldn't you?

--
___
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] BIP 70 refund field

2014-03-29 Thread Roy Badami
On Fri, Mar 28, 2014 at 09:56:57PM +0100, Andreas Schildbach wrote:
 On 03/28/2014 07:19 PM, Mike Hearn wrote:
 
  Ok, why don't fix this in the spec for now, by defining a fixed expiry
  time. In the EU, most products are covered by a 2 years warranty, so it
  seems appropriate to pick 2.5 years (30 months) -- allowing for some
  time to ship the product back and forth.
 
  Yeah I was thinking something like that on the walk home. But 2 years is
  a long time. Do we have enough RAM for that?
 
 It depends on usage stats, script size, etc...
 
  Plus warranties usually
  result in the defective goods being replaced rather than a monetary
  refund, right?
 
 Usually yes. The next smaller unit of time in Germany would be two
 weeks, the so-called Fernabsatzgesetz. It allows you to send back
 mail-orders and usually you want the money back. Don't know if that made
 it into EU law or how it applies to other countries.

It's EU law, but the Distance Selling Directive only says at least
seven days, so the exact period probably varies by country (in the UK
it is 7 days).

But the clock only starts ticking when you receive the goods, and the
Distance Selling Directive allows the supplier 30 days to execute the
order (I *think* the 30 days always has to include shipping, because
for consumer contracts title doesn't pass until the goods are
delivered, so the order wouldn't be considered complete until then).

So I think latest possible deadline for returning the goods for refund
could be up to 30 days to execute the order plus at least 7 days
(with some countries allowing more).  Plus, conceivably, shipping
time, if some member states have chosen to interpret the 30 day
execution differently.

So I think this adds up to a couple of months, give or take.  In
practice, though, even a couple of months is a bit on the short time.
What if the goods are delayed.  How many people have had miner orders
outstanding for the best part of a year?

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

2014-03-29 Thread Matt Whitlock
On Saturday, 29 March 2014, at 10:08 am, Chris Beams wrote:
 Matt, could you expand on use cases for which you see Shamir's Secret Sharing 
 Scheme as the best tool for the job? In particular, when do you see that it 
 would be superior to simply going with multisig in the first place? Perhaps 
 you see these as complimentary approaches, toward defense-in-depth? In any 
 case, the Motivation and Rationale sections of the BIP in its current form 
 are silent on these questions.

Okay, yes, I will address these questions.

--
___
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 Matt Whitlock
On Saturday, 29 March 2014, at 10:08 am, Chris Beams wrote:
 Matt, could you expand on use cases for which you see Shamir's Secret Sharing 
 Scheme as the best tool for the job? In particular, when do you see that it 
 would be superior to simply going with multisig in the first place? Perhaps 
 you see these as complimentary approaches, toward defense-in-depth? In any 
 case, the Motivation and Rationale sections of the BIP in its current form 
 are silent on these questions.

I have added two new sections to address your questions.

https://github.com/whitslack/btctool/blob/bip/bip-.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 Jeff Garzik
The comparison with multisig fails to mention that multi-signature
transactions explicitly define security at the transaction level.
This permits fine-grained specificity of what a key holder may
approve.

Shamir is much more coarse-grained.  You reconstitute a private key,
which may then be used to control anything that key controls.  Thus,
in addition to Shamir itself, you need policies such as no key
reuse.

My first impression of Shamir many moons ago was cool! but that's
since been tempered by thinking through the use cases.  Shamir has a
higher D.I.Y. factor, with a correspondingly larger surface of
things-that-could-go-wrong, IMO.

(None of this implies making an informational BIP lacks value; I'm all
for an informational BIP)




On Sat, Mar 29, 2014 at 7:54 AM, Chris Beams 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


Re: [Bitcoin-development] BIP 70 refund field

2014-03-29 Thread Mike Hearn
So how about we say two months? That way it's easy for merchants to comply
with the EU DSD and we keep RAM usage in check until we come up with a more
sophisticated refund scheme.

There's another issue with BIP 70 and refunds that I noticed. The
PaymentRequest doesn't specify whether refunds are possible. So wallets
have to either never submit refund data, or always submit it even if it
makes no sense. Because setting things up to get refunds has a non-zero
cost for the sender, it'd help if we could optimise it away for merchants
that simply refuse to issue refunds for whatever reason.



On Sat, Mar 29, 2014 at 10:27 AM, Roy Badami r...@gnomon.org.uk wrote:

 On Fri, Mar 28, 2014 at 09:56:57PM +0100, Andreas Schildbach wrote:
  On 03/28/2014 07:19 PM, Mike Hearn wrote:
 
   Ok, why don't fix this in the spec for now, by defining a fixed expiry
   time. In the EU, most products are covered by a 2 years warranty, so
 it
   seems appropriate to pick 2.5 years (30 months) -- allowing for some
   time to ship the product back and forth.
  
   Yeah I was thinking something like that on the walk home. But 2 years
 is
   a long time. Do we have enough RAM for that?
 
  It depends on usage stats, script size, etc...
 
   Plus warranties usually
   result in the defective goods being replaced rather than a monetary
   refund, right?
 
  Usually yes. The next smaller unit of time in Germany would be two
  weeks, the so-called Fernabsatzgesetz. It allows you to send back
  mail-orders and usually you want the money back. Don't know if that made
  it into EU law or how it applies to other countries.

 It's EU law, but the Distance Selling Directive only says at least
 seven days, so the exact period probably varies by country (in the UK
 it is 7 days).

 But the clock only starts ticking when you receive the goods, and the
 Distance Selling Directive allows the supplier 30 days to execute the
 order (I *think* the 30 days always has to include shipping, because
 for consumer contracts title doesn't pass until the goods are
 delivered, so the order wouldn't be considered complete until then).

 So I think latest possible deadline for returning the goods for refund
 could be up to 30 days to execute the order plus at least 7 days
 (with some countries allowing more).  Plus, conceivably, shipping
 time, if some member states have chosen to interpret the 30 day
 execution differently.

 So I think this adds up to a couple of months, give or take.  In
 practice, though, even a couple of months is a bit on the short time.
 What if the goods are delayed.  How many people have had miner orders
 outstanding for the best part of a year?

 roy



 --
 ___
 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] BIP 70 and OP_RETURN

2014-03-29 Thread Mike Hearn
They would just encode the OP_RETURN script into an Output structure. I'm
not sure about the question - you seem to give the answer yourself in the
first 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-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

2014-03-29 Thread Matt Whitlock
On Saturday, 29 March 2014, at 2:36 pm, Mike Hearn wrote:
 Right - the explanation in the BIP about the board of  directors is IMO a
 little misleading. The problem is with splitting a private key is that at
 some point, *someone* has to get the full private key back and they can
 then just remember the private key to undo the system. CHECKMULTISIG avoids
 this.

The implication is that every director would want to retain the board's private 
key for himself but also would want to prevent every other director from 
successfully retaining the private key for himself, leading to a perpetual 
stalemate in which no director ever gets to retain the private key.

 I can imagine that there may be occasional uses for splitting a wallet seed
 like this, like for higher security cold wallets, but I suspect an ongoing
 shared account like a corporate account is still best off using
 CHECKMULTISIG or the n-of-m ECDSA threshold scheme proposed by Ali et al.

Multisig does not allow for the topology I described. Say the board has seven 
directors, meaning the majority threshold is four. This means the organization 
needs the consent of six individuals in order to sign a transaction: the 
president, the CFO, and any four of the board members. A 6-of-9 multisig would 
not accomplish the same policy, as then any six board members could 
successfully sign a transaction without the consent of the president or CFO. Of 
course the multi-signature scheme could be expanded to allow for hierarchical 
threshold topologies, or Shamir's Secret Sharing can be used to distribute keys 
at the second level (and further, if desired).

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

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

2014-03-29 Thread Matt Whitlock
On Saturday, 29 March 2014, at 7:36 am, Gregory Maxwell wrote:
 On Sat, Mar 29, 2014 at 7:28 AM, Watson Ladd 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] BIP 70 and OP_RETURN

2014-03-29 Thread Justus Ranvier
On 03/29/2014 01:30 PM, Mike Hearn wrote:
 They would just encode the OP_RETURN script into an Output structure. I'm
 not sure about the question - you seem to give the answer yourself in the
 first paragraph?
 

I guess what I was asking is whether or not all BIP70 compatible clients
will support the creation of all standard output types, including
OP_RETURN outputs.

-- 
Support online privacy by using email encryption whenever possible.
Learn how here: http://www.youtube.com/watch?v=bakOKJFtB-k


0x1B438BF4.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] BIP 70 and OP_RETURN

2014-03-29 Thread Mike Hearn
They should do. If they don't they're not spec compliant. I'm not sure what
they actually do though. Currently only Bitcoin Core and Android Bitcoin
Wallet implement BIP 70 so you can just create such a request and then try
it out and see what happens.


On Sat, Mar 29, 2014 at 4:02 PM, Justus Ranvier justusranv...@gmail.comwrote:

 On 03/29/2014 01:30 PM, Mike Hearn wrote:
  They would just encode the OP_RETURN script into an Output structure. I'm
  not sure about the question - you seem to give the answer yourself in the
  first paragraph?
 

 I guess what I was asking is whether or not all BIP70 compatible clients
 will support the creation of all standard output types, including
 OP_RETURN outputs.

 --
 Support online privacy by using email encryption whenever possible.
 Learn how here: http://www.youtube.com/watch?v=bakOKJFtB-k

--
___
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 Matt Whitlock
On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote:
 https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/

Thanks. This is great, although it makes some critical references to an ACM 
paper for which no URL is provided, and thus I cannot implement it.

A distributed ECDSA notwithstanding, we still need a way to decompose a BIP32 
master seed into shares. I am envisioning a scenario in which I might meet my 
sudden and untimely demise, and I wish to allow my beneficiaries to reconstruct 
my wallet's master seed after my death. I would like to distribute seed shares 
to each of my beneficiaries and some close friends, such that some subset of 
the shares must be joined together to reconstitute my master seed. Shamir's 
Secret Sharing Scheme is perfect for this use case. I am presently working on 
extending my draft BIP so that it also applies to BIP32 master seeds of various 
sizes.

--
___
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 Matt Whitlock
On Saturday, 29 March 2014, at 9:44 am, Tamas Blummer wrote:
 I used Shamir's Secret Sharing to decompose a seed for a BIP32 master key, 
 that is I think more future relevant than a single key.
 Therefore suggest to adapt the BIP for a length used there typically 16 or 32 
 bytes and have a magic code to indicate its use as key vs. seed.

I have expanded the BIP so that it additionally applies to BIP32 master seeds 
of sizes 128, 256, and 512 bits.

https://github.com/whitslack/btctool/blob/bip/bip-.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

2014-03-29 Thread Alan Reiner

Armory has had Fragmented Backups for over a year, now.  Advanced
users love it.  Though, I would say it's kind of difficult to
standardize the way I did it since I was able to implement all the
finite field math with recursion, list comprehensions and python
arbitrary-big-integers in about 100 lines.  I'm not sure how portable
it is to other languages.  There's obviously better ways to do it, but I
didn't need a better way, because I don't need to support fragmentation
above M=8 and this was 100% sufficient for it.  And I was the only one
doing it, so there was no one to be compatible with.

I won't lie, there's a lot of work that goes into making an interface
that makes this feature usable.  The user needs clear ways to identify
which fragments are associated with which wallet, and which fragments
are compatible with each other.  They need a way to save some fragments
to file, print them, or simply write them down.  They need a way to
re-enter fragment, reject duplicates, identify errors, etc.  Without it,
the math fails silently, and you end up restoring a different wallet.   
And they need a way to test that it all works.   Armory did all this,
but it was no trivial task.  Including an interface that will test up to
50 subsets of make sure the math produces the same values every time
(which still is not sufficient for some users, who won't be satisified
til they see they're wallet actually restored from fragments.

Also I put the secret in the highest-order coefficient of the
polynomial, and made sure that the other coefficients were
deterministic.  This meant that if print out an M-of-N wallet, I can
later print out an M-of-(N+1) wallet and the first N fragments will be
the same.  I'm not sure how many users would trust this, but we felt it
was important in case a user needs to export some fragments, even if
they don't increase N.

You might consider loading Armory in offline mode, create a wallet, and
then do a fragmented backup to see how we did it.  I am extremely
satisfied with the interface, but it's most definitely an advanced
tool.  But so is Armory ... which made it a good fit.  But it might not
be for everyone.

-Alan



On 03/29/2014 11:44 AM, Matt Whitlock wrote:
 On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote:
 https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/
 Thanks. This is great, although it makes some critical references to an ACM 
 paper for which no URL is provided, and thus I cannot implement it.

 A distributed ECDSA notwithstanding, we still need a way to decompose a BIP32 
 master seed into shares. I am envisioning a scenario in which I might meet my 
 sudden and untimely demise, and I wish to allow my beneficiaries to 
 reconstruct my wallet's master seed after my death. I would like to 
 distribute seed shares to each of my beneficiaries and some close friends, 
 such that some subset of the shares must be joined together to reconstitute 
 my master seed. Shamir's Secret Sharing Scheme is perfect for this use case. 
 I am presently working on extending my draft BIP so that it also applies to 
 BIP32 master seeds of various sizes.

 --
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development


--
___
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 Matt Whitlock
On Saturday, 29 March 2014, at 12:59 pm, Alan Reiner wrote:
 I won't lie, there's a lot of work that goes into making an interface
 that makes this feature usable.  The user needs clear ways to identify
 which fragments are associated with which wallet, and which fragments
 are compatible with each other.

The same is true of the multiple private keys involved in a multi-signature 
addresses.

 They need a way to save some fragments
 to file, print them, or simply write them down.

I proposed a share encoding scheme for exactly this purpose.

 They need a way to
 re-enter fragment, reject duplicates, identify errors, etc.  Without it,
 the math fails silently, and you end up restoring a different wallet.

I intentionally omitted the parameter M (minimum subset size) from the shares 
because including it would give an adversary a vital piece of information. 
Likewise, including any kind of information that would allow a determination of 
whether the secret has been correctly reconstituted would give an adversary too 
much information. Failing silently when given incorrect shares or an 
insufficient number of shares is intentional.

 Also I put the secret in the highest-order coefficient of the
 polynomial,

Does it make any difference which coefficient holds the secret? It's convenient 
to put it in the lowest-order coefficient to simply the recovery code.

 and made sure that the other coefficients were
 deterministic.  This meant that if print out an M-of-N wallet, I can
 later print out an M-of-(N+1) wallet and the first N fragments will be
 the same.  I'm not sure how many users would trust this, but we felt it
 was important in case a user needs to export some fragments, even if
 they don't increase N.

My BIP likewise deterministically chooses the coefficients so that the shares 
of a secret are consistent across all runs of the algorithm having the same M. 
As I'm sure you're aware, N (the number of shares to output) plays no part in 
the calculation and merely controls how many times the outermost loop is 
executed. My BIP doesn't even mention this parameter.

--
___
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:
 
 Armory has had Fragmented Backups for over a year, now.  Advanced
 users love it.  Though, I would say it's kind of difficult to
 standardize the way I did it since I was able to implement all the
 finite field math with recursion, list comprehensions and python
 arbitrary-big-integers in about 100 lines.  I'm not sure how portable
 it is to other languages.  There's obviously better ways to do it, but I
 didn't need a better way, because I don't need to support fragmentation
 above M=8 and this was 100% sufficient for it.  And I was the only one
 doing it, so there was no one to be compatible with.
 
 I won't lie, there's a lot of work that goes into making an interface
 that makes this feature usable.  The user needs clear ways to identify
 which fragments are associated with which wallet, and which fragments
 are compatible with each other.  They need a way to save some fragments
 to file, print them, or simply write them down.  They need a way to
 re-enter fragment, reject duplicates, identify errors, etc.  Without it,
 the math fails silently, and you end up restoring a different wallet.   
 And they need a way to test that it all works.   Armory did all this,
 but it was no trivial task.  Including an interface that will test up to
 50 subsets of make sure the math produces the same values every time
 (which still is not sufficient for some users, who won't be satisified
 til they see they're wallet actually restored from fragments.
 
 Also I put the secret in the highest-order coefficient of the
 polynomial, and made sure that the other coefficients were
 deterministic.  This meant that if print out an M-of-N wallet, I can
 later print out an M-of-(N+1) wallet and the first N fragments will be
 the same.  I'm not sure how many users would trust this, but we felt it
 was important in case a user needs to export some fragments, even if
 they don't increase N.
 
 You might consider loading Armory in offline mode, create a wallet, and
 then do a fragmented backup to see how we did it.  I am extremely
 satisfied with the interface, but it's most definitely an advanced
 tool.  But so is Armory ... which made it a good fit.  But it might not
 be for everyone.
 
 -Alan
 
 
 
 On 03/29/2014 11:44 AM, Matt Whitlock wrote:
  On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote:
  https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/
  Thanks. This is great, although it makes some critical references to an ACM 
  paper for which no URL is provided, and thus I cannot implement it.
 
  A distributed ECDSA notwithstanding, we still need a way to decompose a 
  BIP32 master seed into shares. I am envisioning a scenario in which I might 
  meet my sudden and untimely demise, and I wish to allow my beneficiaries to 
  reconstruct my wallet's master seed after my death. I would like to 
  distribute seed shares to each of my beneficiaries and some close friends, 
  such that some subset of the shares must be joined together to reconstitute 
  my master seed. Shamir's Secret Sharing Scheme is perfect for this use 
  case. I am presently working on extending my draft BIP so that it also 
  applies to BIP32 master seeds of various sizes.
 
  --
  ___
  Bitcoin-development mailing list
  Bitcoin-development@lists.sourceforge.net
  https://lists.sourceforge.net/lists/listinfo/bitcoin-development
 
 
 --
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development
 

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



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

2014-03-29 Thread Matt Whitlock
On Saturday, 29 March 2014, at 10:25 am, Dev Random wrote:
 On Sat, 2014-03-29 at 11:44 -0400, Matt Whitlock wrote:
  On Saturday, 29 March 2014, at 11:08 am, Watson Ladd wrote:
   https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/
  
  Thanks. This is great, although it makes some critical references to an
  ACM paper for which no URL is provided, and thus I cannot implement it.
  
  A distributed ECDSA notwithstanding, we still need a way to decompose a
  BIP32 master seed into shares. I am envisioning a scenario in which I
 
 It would seem that threshold ECDSA with keys derived from separate seeds
 has better security properties than one seed that is then split up.  The
 main thing is that there is no single point of attack in the generation
 or signing.

No contest here. But can threshold ECDSA work with BIP32? In other words, can a 
threshold ECDSA public key be generated from separate, precomputed private 
keys, or can it only be generated interactively? Maybe the BIP32 master seeds 
have to be generated interactively, and then all sets of corresponding derived 
keys are valid signing groups?

Threshold ECDSA certainly sounds nice, but is anyone working on a BIP for it? I 
would take it on myself, but I don't understand it well enough yet, and 
publicly available information on it seems lacking. I proposed this Shamir 
Secret Sharing BIP as an easily understood, easily implemented measure that we 
can use today, with no changes to existing Bitcoin software. It's low-hanging 
fruit.

--
___
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
  
  It would seem that threshold ECDSA with keys derived from separate seeds
  has better security properties than one seed that is then split up.  The
  main thing is that there is no single point of attack in the generation
  or signing.
 
 No contest here. But can threshold ECDSA work with BIP32? In other
 words, can a threshold ECDSA public key be generated from separate,
 precomputed private keys, or can it only be generated interactively?
 Maybe the BIP32 master seeds have to be generated interactively, and
 then all sets of corresponding derived keys are valid signing groups?

That's a good point. In the paper, they have a deterministic wallet
scheme in section 3.3.  It is non-interactive, so that's good.  On the
other hand, it's not BIP32, so that adds complexity.

 
 Threshold ECDSA certainly sounds nice, but is anyone working on a BIP
 for it? I would take it on myself, but I don't understand it well
 enough yet, and publicly available information on it seems lacking. I
 proposed this Shamir Secret Sharing BIP as an easily understood, easily
 implemented measure that we can use today, with no changes to existing
 Bitcoin software. It's low-hanging fruit.

Good points, although multisig is catching on quickly in the ecosystem.
AFAIK, all production wallets can send to p2sh addresses.

-- 
Miron / devrandom




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

2014-03-29 Thread Matt Whitlock
On Saturday, 29 March 2014, at 10:48 am, devrandom wrote:
 On Sat, 2014-03-29 at 13:38 -0400, Matt Whitlock wrote:
  Threshold ECDSA certainly sounds nice, but is anyone working on a BIP
  for it? I would take it on myself, but I don't understand it well
  enough yet, and publicly available information on it seems lacking. I
  proposed this Shamir Secret Sharing BIP as an easily understood, easily
  implemented measure that we can use today, with no changes to existing
  Bitcoin software. It's low-hanging fruit.
 
 Good points, although multisig is catching on quickly in the ecosystem.
 AFAIK, all production wallets can send to p2sh addresses.

As far as I know, Blockchain.info wallets still can't send to P2SH addresses. 
This was a *major* roadblock in the Bitcoin project that I've been working on 
for the past several months, and it was the impetus for my creating this Shamir 
Secret Sharing implementation in the first place.

--
___
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 Alan Reiner
On 03/29/2014 01:19 PM, Matt Whitlock wrote:
 I intentionally omitted the parameter M (minimum subset size) from the shares 
 because including it would give an adversary a vital piece of information. 
 Likewise, including any kind of information that would allow a determination 
 of whether the secret has been correctly reconstituted would give an 
 adversary too much information. Failing silently when given incorrect shares 
 or an insufficient number of shares is intentional.

I do not believe this is a good tradeoff.  It's basically obfuscation of
something that is already considered secure at the expense of
usability.  It's much more important to me that the user understands
what is in their hands (or their family members after they get hit by a
bus), than to obfuscate the parameters of the secret sharing to provide
a tiny disadvantage to an adversary who gets ahold of one. 

The fact that it fails silently is really all downside, not a benefit. 
If I have enough fragments, I can reconstruct the seed and see that it
produces addresses with money.  If not, I know I need more fragments. 
I'm much more concerned about my family having all the info they need to
recover the money, than an attacker knowing that he needs two more
fragments instead of which are well-secured anyway.



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

On 03/29/2014 02:00 PM, Matt Whitlock wrote:
 On Saturday, 29 March 2014, at 1:52 pm, Alan Reiner wrote:
 On 03/29/2014 01:19 PM, Matt Whitlock wrote:
 I intentionally omitted the parameter M (minimum subset size) from the 
 shares because including it would give an adversary a vital piece of 
 information. Likewise, including any kind of information that would allow a 
 determination of whether the secret has been correctly reconstituted would 
 give an adversary too much information. Failing silently when given 
 incorrect shares or an insufficient number of shares is intentional.
 I do not believe this is a good tradeoff.  It's basically obfuscation of
 something that is already considered secure at the expense of
 usability.  It's much more important to me that the user understands
 what is in their hands (or their family members after they get hit by a
 bus), than to obfuscate the parameters of the secret sharing to provide
 a tiny disadvantage to an adversary who gets ahold of one. 

 The fact that it fails silently is really all downside, not a benefit. 
 If I have enough fragments, I can reconstruct the seed and see that it
 produces addresses with money.  If not, I know I need more fragments. 
 I'm much more concerned about my family having all the info they need to
 recover the money, than an attacker knowing that he needs two more
 fragments instead of which are well-secured anyway.
 For what it's worth,  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

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

2014-03-29 Thread Tamas Blummer
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 wrote:

 On 03/29/2014 01:19 PM, Matt Whitlock wrote:
 I intentionally omitted the parameter M (minimum subset size) from the 
 shares because including it would give an adversary a vital piece of 
 information. Likewise, including any kind of information that would allow a 
 determination of whether the secret has been correctly reconstituted would 
 give an adversary too much information. Failing silently when given 
 incorrect shares or an insufficient number of shares is intentional.
 
 I do not believe this is a good tradeoff.  It's basically obfuscation of
 something that is already considered secure at the expense of
 usability.  It's much more important to me that the user understands
 what is in their hands (or their family members after they get hit by a
 bus), than to obfuscate the parameters of the secret sharing to provide
 a tiny disadvantage to an adversary who gets ahold of one. 
 
 The fact that it fails silently is really all downside, not a benefit. 
 If I have enough fragments, I can reconstruct the seed and see that it
 produces addresses with money.  If not, I know I need more fragments. 
 I'm much more concerned about my family having all the info they need to
 recover the money, than an attacker knowing that he needs two more
 fragments instead of which are well-secured anyway.
 
 
 
 --
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development
 



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


[Bitcoin-development] Best practices for dust remining

2014-03-29 Thread Justus Ranvier
Suppose am m-of-n multisig wallet receives a bunch of dust deposits due
to somebody advertising the Olympics, or any other reason, and the users
of the wallet don't want the few satoshis involved.

What is the best way to allow all these dust outputs to be re-mined in
order to clean up the utxo set, keeping in mind the scripts may include
large values of n?

-- 
Support online privacy by using email encryption whenever possible.
Learn how here: http://www.youtube.com/watch?v=bakOKJFtB-k


0x1B438BF4.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
--
___
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 Tamas Blummer
On 29.03.2014, at 18:46, Gregory Maxwell gmaxw...@gmail.com wrote:
 In this case I don't see anything wrong with specifying secret
 sharing, but I think— if possible— it should be carefully constructed
 so that the same polynomials and interpolation code can be used for
 threshold signatures (when encoding compatible data).

The paper http://www.cs.princeton.edu/~stevenag/bitcoin_threshold_signatures.pdf
does not mention anything special about the polynomial to use other than:
 random polynomial f of degree t - 1 such that d = f(0)

Do you have reasons to assume that there is more to this? Since this is 
compatible
with Matt's proposal.



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] Dust recycling

2014-03-29 Thread Justus Ranvier
On 03/29/2014 07:55 PM, Goss, Brian C., M.D. wrote:
 Could you collect the dust into a transaction with no outputs (thus making it 
 all tx fees) or putting in to an anyone can spend tx?
 
 The large number of signatures (for large n) would make the tx size 
 large...but, if enough dust were out there, it might be worth propagating to 
 a pools hash power. 

What would make it easier is if there was a standard output type for
sending the entire transaction to miner fees, that would make even large
transactions propagate that would normally be dropped by fee/kB rules.

-- 
Support online privacy by using email encryption whenever possible.
Learn how here: http://www.youtube.com/watch?v=bakOKJFtB-k


0x1B438BF4.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Dust recycling

2014-03-29 Thread Gregory Maxwell
On Sat, Mar 29, 2014 at 12:59 PM, Justus Ranvier
justusranv...@gmail.com wrote:
 What would make it easier is if there was a standard output type for
 sending the entire transaction to miner fees,

Hm. maybe it could be called a return operator or something like that? :)

 that would make even large
 transactions propagate that would normally be dropped by fee/kB rules.

Use dust-b-gone and make it someone elses problem to get it relayed. :)

--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Dust recycling

2014-03-29 Thread Justus Ranvier
On 03/29/2014 08:05 PM, Gregory Maxwell wrote:
 Use dust-b-gone and make it someone elses problem to get it relayed. :)
 

That's a sub-optimal solution, as it introduces a third party. What if
his server goes down?

An universal solution is preferable.

-- 
Support online privacy by using email encryption whenever possible.
Learn how here: http://www.youtube.com/watch?v=bakOKJFtB-k


0x1B438BF4.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] Dust recycling

2014-03-29 Thread Gregory Maxwell
On Sat, Mar 29, 2014 at 1:20 PM, Justus Ranvier justusranv...@gmail.com wrote:
 On 03/29/2014 08:05 PM, Gregory Maxwell wrote:
 Use dust-b-gone and make it someone elses problem to get it relayed. :)
 That's a sub-optimal solution, as it introduces a third party. What if
 his server goes down?
 An universal solution is preferable.

Then start the server yourself. There is no replacement for
aggregating multiple bits of dust in single transactions. Other ways
are less efficient.

You can already OP_RETURN to include your dust, but miners aren't
going to automatically take that over transactions paying more in
terms of fee/byte.

--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development