No "wallet protection services" without (A and B) or C transactions

[ByteCoin]

As mentioned in BIP0011, implementing multisignature transactions is expected to facilitate the development of "wallet protection services" which are meant to ensure that someone can't steal your bitcoins even if they hack your computer.

To do this, you would request that people paying you send the bitcoins to an address which requires two signatures to spend. One signature is supplied by your bitcoin client and the other by the wallet protection service after appropriate checks have been completed.

Unfortunately, if the wallet protection service goes out of business or equivalently, if you lose your wallet.dat then you effectively lose the associated coins. Losing your wallet.dat is a risk we have with the current system and the fact that bitcoin is used nevertheless means that it is deemed to be tolerable. It's doubtful that users will tolerate being vulnerable to the wallet protection service losing their wallet and to mitigate this risk, it is suggested that the WPS will send the user a copy of their private keys in some secure fashion to be used to recover the coins in the event that the WPS disappears.

There are several problems with this:

• It's inconvenient and a security vulnerability to have to manipulate and mail out the secret keys.
• The recipients of the secret keys should ideally have a way to verify the keys are correct without revealing them to their possibly hacked computer.
• The wallet protection service has to maintain different keys for each of their clients.
• Once clients have the wallet protection service's secret keys, they can do anything the WPS can. This means that it's difficult for a WPS to maintain a good reputation against the efforts of a malicious client. Similarly, a malicious WPS can say that fraud it has facilitated is the action of a malicious client trying to ruin its reputation.

Let's look at that last point more closely.
There will likely be multiple wallet protection services and each one could sign up as a client with the rival WPSes. It's in each WPS's interest to use the mailed private keys to "steal coins" from themselves and claim that the rival WPS is not doing its job correctly.
Alternatively, hackers who have stolen a user's wallet.dat can offer to split the bitcoins with the WPS if the WPS supplies the keys and the WPS can claim that the user must have divulged the mailed private keys or be attempting to defame the WPS.

So we can see that mailing out private keys is likely to result in acrimony and fraud. Not mailing out private keys is likely to result in lost bitcoins.

The solution to this is the use of an (A and B) or C transaction which is an instance of a "recovery key" transaction. It is important that the bitcoins should be spendable even if all information about keys A and/or B are lost. This post outlines how to achieve this in a practical fashion.

ByteCoin

[finway]

Yes,
this (A lost or B lost or A duplicated )
 is a problem.

[Gavin Andresen]

Can we come up with a scheme that uses 2-of-3 that solves the problem?


Key 1 is the Wallet Protection Service Key. Your wallet only knows the public half of that key.

Create two random keys, Key 2 and Key 3, offline.  Save them, they're needed for backup.
Transfer the private part of Key 2 and just the public half of Key 3 to the online wallet.

The wallet can generate the 2-of-3 required bitcoin payment address (it has all 3 public keys), but can only sign for Key 2.

Normally, it will ask the wallet protection service to sign for Key 1.

If the WPS goes out of business, the private key for Key3 can be imported and the wallet will be able to spend without the WPS.
If the online wallet gets lost AND the WPS goes out of business, then Key2 and Key3 can be restored from the offline backup.


If you care about privacy and want to make it harder for people to track your transactions, then you could implement a deterministic key scheme on top of all of that-- start with keys 1, 2 and 3 and ECC multiply them by some random number to get derived keys. The random number would need to be stored with the backup, in the online wallet, and sent to the wallet protection service, but that's OK because you need the random number plus 2 of the 3 secret keys to spend the coins.

[finway]

Yes, backup is bad idea,

(2 in 3) or (A&B or C) are all good choice,

the key point is kept "recovering" action different from "usual spending",

and still,

you should trust your WPS that he won't "redeem" by stealth,
or your WPS should trust you that you won't abuse your backup key.

[casascius]

A wallet protection service could be implemented in a smartphone.

It could hold half of what's needed to sign a transaction.  A PC could display a QR code on its screen to initiate a transaction, and then the smartphone app could read the QR code, confirm the transaction with the user, complete the transaction, and send it to a service that gets it into the P2P network.

[ByteCoin]

Can we come up with a scheme that uses 2-of-3 that solves the problem?

The two advantages of the "2-of-3" solution over my "or C" solution are:
1) It's simpler.
2) It's soon to become standard.

However, I'm concerned about how well the "2-of-3" solution will integrate into the existing workflow.

The current client seems to use new addresses (public keys) at every possible opportunity. In the "2-of-3" solution this means that there's potentially quite a lot of data transferred from the "offline device" to the online wallet. Similarly, unless a deterministic wallet is used on the offline device, the secure storage requirements for the offline device are significant. If a deterministic wallet is used then the computation and software complexity/trustworthyness requirements are significant.
With the "or C" solution, the offline device can be a small piece of paper which has no computational requirements, has perfect computation integrity and is a storage medium of long standing with well understood properties.

There's also the question of key management for the WPS. Would they issue one key for all their customers, one key per customer or one key per transaction? Every different WPS key either needs to be securely stored separately or else sent to the offline device to be logged. If stored separately there's another secure storage problem and there may be a problem matching up the WPS key with the user's keys if the WPS disappears. If sent to the offline device then that's another infection vector, storage and key matching problem.

I agree that the problems can be somewhat mitigated through the use of deterministic wallets but unless deterministic wallet operation is standardized before "2-of-3" solutions go online then it's going to be chaos when people try setting up and using WPSs with various behaviours. It will be difficult to ensure that the standard client can interoperate with different WPSs if they distribute keys or implement deterministic wallets in different ways.

You might imagine that similar concerns operate with the "or C" solution. The situation is considerably better as the standard client can always ensure that the transactions are recoverable irrespective of the operation of the WPS. This means that the issue of recovering transactions is orthogonal to the WPS implementation whereas in the "2-of-3" solution, they are intimately bound together.

ByteCoin

[Gavin Andresen]

.... If a deterministic wallet is used then the computation and software complexity/trustworthyness requirements are significant.

I only half-paid-attention to all the previous deterministic wallet discussions, but isn't it pretty simple?

Start with a random private key and a random nonce.
ECC multiply the key by SHA256(nonce+n) to get the n'th derived key.

(I think you could even get away with using the private key as the nonce) (and, of course, I defer to the expertise of people who know way more about ECC crypto than I do)

There's also the question of key management for the WPS. Would they issue one key for all their customers, one key per customer or one key per transaction? Every different WPS key either needs to be securely stored separately or else sent to the offline device to be logged. If stored separately there's another secure storage problem and there may be a problem matching up the WPS key with the user's keys if the WPS disappears. If sent to the offline device then that's another infection vector, storage and key matching problem.

It seems to me these issues will be the same no matter what solution is implemented.

I agree that the problems can be somewhat mitigated through the use of deterministic wallets but unless deterministic wallet operation is standardized before "2-of-3" solutions go online then it's going to be chaos when people try setting up and using WPSs with various behaviours.

I think the next step is starting to prototype and standardize a protocol for communicating with WPS or escrow services to request new public keys, get keys signed, etc.

Supporting deterministic wallet schemes at the same time makes sense, in my humble opinion.

I imagine an API call that is something like "I'm customer gavin@acm.org.  Please use whatever private key you're storing for me and this 256-bit number to derive a new public key, and send it back to me."

(details to be worked out, but note that the WPS wouldn't necessarily have to store that new keypair if the "Please sign" request included the same (gavin@acm.org,256-bit-number) ....)

It will be difficult to ensure that the standard client can interoperate with different WPSs if they distribute keys or implement deterministic wallets in different ways.

As long as the API is consistent, I don't think the details of the deterministic wallet matter.

You might imagine that similar concerns operate with the "or C" solution. The situation is considerably better as the standard client can always ensure that the transactions are recoverable irrespective of the operation of the WPS. This means that the issue of recovering transactions is orthogonal to the WPS implementation whereas in the "2-of-3" solution, they are intimately bound together.

I don't see the difference: if the WPS becomes unavailable, then either solution requires that the "C" key be transferred from paper (or wherever) to the online client.

[jojkaart]

I think the biggest problem is that we don't really have a crypto expert deeply involved who'd take the responsibility of working these things out. I wonder if making a public invitation for people well versed with cryptography to become involved would work.

P.S. If we do have one, that person needs more visiblity as the go-to person when dealing with crypto design. So if there's anyone reading this with the right skills and willingness to help, please make yourself known.

[etotheipi]

I have the solution for most of the concerns presented here and it's not terribly difficult in concept, but one does need the infrastructure in place in order to impelment it.

Luckily, I'm going to have 90% of this problem solved with my first release of Armory next month, and hopefully the full solution implemented by v2.0... whenever that is.  There are three key things that make this possible:

(1) Deterministic wallets that can be extended by someone without the private keys

• The determinism of the wallet comes from the public key, not the private key.  In the case of Armory, a chain code xor'd with the 32-byte hash of the public key is used as the chain to the next address:  multiply the private key by this number mod N (order of the group) and you have a new private key.  The benefit is that someone holding just the public keys can still predict/generate the address chain, but can't spend the money (they EC multiply the public key by this number which they can compute if they have the chaincode)
• This allows someone who has only the chaincode and the public key, to produce the next public key/address in the chain.  This means that my computer can generate addresses for my phone wallet, without actually having access to the phone wallet keys.  If my computer is compromised, my phone isn't.  

(2) BIP 0010 or some variant thereof.

• BIP 0010 solves a lot of problems in this area of BTC.  It is targeted at multi-sig transactions but actually works for any kind of transaction.  The critical benefit of BIP 0010 is that the other parties signing the TxDP do not need the blockchain.  
• In this case, it would be your phone.  Your phone only needs the private keys/wallet, an ECDSA module and the TxDP, and it has the capability to present the tx to the user, ask for confirmation, sign the TxDP, convert it to a completed transaction and broadcast.  This enables key-storage on just about any kind of device that can do ECDSA, which is a significantly broader subset than the one that can store and process the blockchain.
• This works just as well for offline wallet transactions as well, which is why Armory generates all transactions by going through a TxDP:  if it's got the key to sign it, it does... if not, it presents it to the user who can copy the TxDP to the correct computer/phone/email of someone who does have the private keys.
• I really hope to see BIP 0010 expanded and implemented (in some form) because of its extreme versatility.  There's nothing stopping someone else from making an Android app that implements BIP 0010, and then can use their app to sign TxDPs from Armory.  (in fact, I hope someone will, so I can avoid making the app myself -- this is the 10% I'll be missing in my first release).
  

(3) Paper backups

• This is exactly as it sounds.  Generate your wallet, print off a "paper backup" and scan it with your phone to absorb the private keys.
• This also means that for non-third-party WPS, you dont' actually need a C party... you simply backup A and B to paper
• The screenshot from Armory shows the ideal form of paper backup for my deterministic wallets:  allows you to recover your keys if the wallet is lost, or transfer to another device (especially easy if it reads QR codes).

Putting it all together:
(1)  Computer creates new wallets A and B.
(2)  Computer prints paper backups for both A and B
(3)  Computer deletes private keys for B
(4)  Phone scans QR code on paper backup for B to absorb the wallet.  Phone does not need blockchain
(5)  Paper backups are stored in a safe or safety-deposit box

Now, you make sure that all your money is encumbered by a 2-of-2 transaction using A and B.  To send money:
(1) Computer generates appropriate TxDP spending the 2-of-2 transaction.
(2) Computer signs for party A
(3) Computer converts partially-signed TxDP to QR code
(4) Phone scans the QR code, and displays the transaction to the the user
(5) The user accepts the transaction, and the phone signs and broadcasts the transaction.

If the computer HDD fails, or the phone is lost/stolen, you still have both A and B backed up on paper and can still access the funds.  So you get all the benefits of WPS, without a third party, and using only a 2-of-2 transaction, which will already be supported by the network in the near future.

QED



(P.S. - This is a testnet wallet, so don't get excited trying to recover the 2.35 BTC in it )

[ByteCoin]

The proposed etotheipi solution makes it quite feasible securely to operate a bitcoin node even if an attacker can see everything the node does, using only vanilla multisignature transactions.

Running a determinisitic wallet means that all the different public keys can be regenerated from relatively little secret information. It's easier to store and secure small amounts of static secret information. Also, if the devices are wiped, the information which enables redemption of payments can be regenerated completely.

The proposal does not involve frequent secure transfers of secret information between devices in order to operate correctly. This is desirable as such transfers are vulnerable to corruption or eavesdropping.

The workflow suggested by etotheipi has the computer generating new wallets A and B. I imagine that the phone could do this if the user was of the opinion that the phone is more secure. The private key is short enough to write down with some suitable error detection scheme. For instance, the phone could tell you what to write down and then make you re-enter what it told you to write before continuing.

In etotheipi's solution, the phone finally signs and broadcasts the transaction. I imagine it might be easier if the phone provides its signature for the transaction which the user then enters into their possibly compromised client to countersign and broadcast.

It's clear that the standard client does not support this scheme at the moment. I propose that as a medium-term goal  we add support for this scheme (and similar schemes) to the client. This means support for:
1) a deterministic wallet - importing root public keys.
2) exporting unsigned, partially signed or signed transactions.
3) importing signatures for partially signed or unsigned transactions

ByteCoin

[etotheipi]

Bytecoin asked me a question about why not use a deterministic chaincode in the wallet design.  I think it's worth discussing in the open, so I hope he doesn't take offense that I am replying to a PM, here.

One thing I noticed about your proposal is that the piece of paper you store has both the private key and the chain code on it. I recommend that the chain code should be derived from the private key in some fashion so that deterministic wallets can be restored with just the private key even if the chain code has been lost.

I had thought long and hard about using a deterministic chaincode, because it cuts in half the amount of information that is needed to restore a wallet.  But ultimately I decided against it for three reasons:

• (1.) Take the case of a determinstic chaincode based on public key or first address:  this is actually a non-starter, because it means that anyone who has access to your first public key can immediately link all your transactions/addresses together.  You completely lose anonymity/privacy.  So you say, well how about making the chaincode based on your private key?  
• (2.) In the near future I plan to support "brainwallets": where your private keys are uniquely generated by your passphrase (passed through a KDF).  This has the benefit that no private data, encrypted or not, ever touches your harddrive.  As such, your private key is actually kept "in your brain."  However, I cannot allow them to be based PURELY on the passphrase, or else you will have multiple users generating identical, way-too-simple passphrases, and end up "sharing" wallets.   Additionally, it allows someone with a lot of computing power to start generating millions of wallets based on simple passphrases and eventually "colliding" with other users' wallets.  Sure, my KDF is hardc0re and will help prevent this, but the attacker gets to attack all brainwallet users all at once by doing this, which is a profitable attack.  Thus, I need the extra entropy provided by the PRNG-generated chaincode.
• (3.) The solution I implemented is more versatile.  If you like the deterministic chaincode, then you can still use it... you just calculate the chaincode from the private key and plug it in instead of using a PRNG.  The real pain would be if I implemented the simpler solution, did not put chaincodes into my wallet format, calculations, etc, and then wanted to upgrade to use it later.  I'm saving myself a lot of trouble in the future if I ultimately decide I do need them to be part of my design (and I do want brainwallets).  This is also why I left plenty of space in my wallet format for extra flags, just like the BTC protocol has.

EDIT:  I suppose a 16-byte chaincode could've been a good compromise...

Although the chain code could just be a hash of the private key, I'm thinking that it should be perhaps set to be the ECDSA signature of some nonce with some fixed k value. The reasoning for this would be that in a highly constrained environment like a microcontroller or smartcard, there might not be enough memory or ROM to implement a hash algorithm but ECDSA (or similar) signing comes for free

This is actually a very good point.  It's not a situation I would normally consider, but one of the benefits of BIP 0010 is that extremely lightweight devices can be used for signing -- why not make that a little easier if it comes at no cost to security?  Most likely, this is another use for the spare flags in the wallet file.

In etotheipi's solution, the phone finally signs and broadcasts the transaction. I imagine it might be easier if the phone provides its signature for the transaction which the user then enters into their possibly compromised client to countersign and broadcast.

I think it's much easier to get data from the computer to the phone (via QR codes) than the other way around.  100% of phones that support Android/iPhone apps have a camera.  Not all computers do.  Manually typing in this data is tedious, even for 64-bytes.  I should know... I've done it quite a lot while testing wallet-restore in my client...  it would get quite a bit more cumbersome with TxDPs that are hundreds of bytes.

I had pondered ways that you might be able to exchange data by text message or email (I'm desperately trying to avoid third-parties).  The problem is, I don't want to get in the business of monitoring peoples' emails or personal data.  I just don't want to go there.  And no matter how you look at it, you're going to need a private key on both devices, so I don't see any benefit to switching the order of operations -- both devices have to be compromised in order to lose your wallet, and I'm not particularly concerned about the initial wallet creation being compromised, as the private keys for B never have to touch the hard-drive.

[makomk]

Although the chain code could just be a hash of the private key, I'm thinking that it should be perhaps set to be the ECDSA signature of some nonce with some fixed k value. The reasoning for this would be that in a highly constrained environment like a microcontroller or smartcard, there might not be enough memory or ROM to implement a hash algorithm but ECDSA (or similar) signing comes for free

This is probably a bad idea. I think it might allow the calculation of the private key from the chain code, which you presumably don't want. (If you have a signature, the value of k used to make that signature, and the data being signed you can compute the private key from them. That's why it's so important that k is both randomly generated and different for each signature.)

[etotheipi]

Although the chain code could just be a hash of the private key, I'm thinking that it should be perhaps set to be the ECDSA signature of some nonce with some fixed k value. The reasoning for this would be that in a highly constrained environment like a microcontroller or smartcard, there might not be enough memory or ROM to implement a hash algorithm but ECDSA (or similar) signing comes for free

This is probably a bad idea. I think it might allow the calculation of the private key from the chain code, which you presumably don't want. (If you have a signature, the value of k used to make that signature, and the data being signed you can compute the private key from them. That's why it's so important that k is both randomly generated and different for each signature.)

As I write out my arguments, I realize that this isn't really a feasible situation.  You still have to use hashing in order to convert public keys to address strings.  Additionally, sha256 is an extremely compact algorithm, both in terms of space to implement, and RAM to run (hence why it's so good on GPUs).  In reality, the ECDSA operations are quite heavy in implementation and computation... I can't imagine a device that could do ECDSA but not hashing...

Then of course, I don't have much experience with microcontrollers...

[etotheipi]

As for the argument about creating phone keys on the phone, I guess it's not actually that hard.  Most smartphones have a built-in share/email function:  I could use the phone to create the wallet, then email myself the watching-only wallet to get it onto my primary computer.  This would be less convenient, but it would prevent the private keys from ever being on the same system, and it would be a one-time thing.

But I also have no experience with Android/iPhone apps... I'll have to leave it to someone else (for now) to actually execute the phone-part of this idea.  If anyone is interested in developing a sister app to close the loop on this functionality, I'll be happy to give a tutorial on Armory wallet files, algorithms, BIP 0010 details, QR codes, etc.  My first release next month will have all the computer-side code needed... even the multi-sig support is implemented, it just needs some testing.

[ByteCoin]

ECDSA signature of some nonce with some fixed k value.

This is probably a bad idea.

Yes it was a stupid idea. I was trying to create a secure hash of the private key, the value of which you couldn't infer from the public key using little more than the code/hardware used to multiply the group generator point.
Something like taking the private key adding it to the public key x-coordinate and then multiplying the group generator by that value should do the trick.

As I write out my arguments, I realize that this isn't really a feasible situation.  You still have to use hashing in order to convert public keys to address strings.  

I don't see why a minimalist piece of secure hardware needs to deal with address strings. All it needs to do is key generation and ECDSA signatures.

I cannot allow them to be based PURELY on the passphrase, or else you will have multiple users generating identical, way-too-simple passphrases, and end up "sharing" wallets.

I believe that this is just a feature of "brainwallets" (yuck) which has to be managed. What's the point of having a passphrase you CAN remember if you also need an impossible-to-remember "chain code" in order to be able to use your "brainwallet"? Implemented this way, you're falling between two stools.

ByteCoin

[etotheipi]

I cannot allow them to be based PURELY on the passphrase, or else you will have multiple users generating identical, way-too-simple passphrases, and end up "sharing" wallets.

I believe that this is just a feature of "brainwallets" (yuck) which has to be managed. What's the point of having a passphrase you CAN remember if you also need an impossible-to-remember "chain code" in order to be able to use your "brainwallet"? Implemented this way, you're falling between two stools.

I don't quite agree about falling between two stools.  The benefit of this implementation is that private key data never touches your hard-drive, encrypted or not.  This is a nice benefit for the ultra-paranoid.  Honestly, it's not a feature I really want for myself, but I've seen enough people muttering about how they wanted it, so I decided I should support it.

But I suppose I could implement it with some extremely high requirement on entropy of their passphrase.  Or use a much shorter chaincode to help prevent collisions.  Or force a passphrase on the user that has the desired entropy, and they won't have a choice about it. 

As I said before, my codebase has the flexibility to use either deterministic, or PRNG chaincodes.  I can just revert to using a deterministic value in case the chaincode is not specified.  You're right I don't have great reasons for needing them to be random, but I built the code so I can go either way. 

[casascius]

I cannot allow them to be based PURELY on the passphrase, or else you will have multiple users generating identical, way-too-simple passphrases, and end up "sharing" wallets.

I believe that this is just a feature of "brainwallets" (yuck) which has to be managed. What's the point of having a passphrase you CAN remember if you also need an impossible-to-remember "chain code" in order to be able to use your "brainwallet"? Implemented this way, you're falling between two stools.

Someone else suggested, and I think it's a pretty good idea, that part of what could go into the key derivation is some piece of information that is specific to the individual, not likely to change, and not a secret.  For example, their name, or some number they would know, or perhaps their e-mail address.

This information would be used as salt, so attackers couldn't attack the entire "brainwallet" community all at once.  They would only be able to work on one wallet at a time.  Meanwhile, nobody is going to forget their own name, so the "impossible-to-remember" aspect is eliminated.