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

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,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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:

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

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

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

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

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.

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

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

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

[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

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

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

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

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

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