Deterministic wallets

[simondlr]

Yep. Cool isn't it The best part is that no one can spend your coins if they get access to the master public key. All they can do is predict the future set of generated addresses. This is not a problem if you use a dedicated wallet for each purpose. You can easily create a new wallet using the -w command line switch when starting up electrum:

electrum -w /path/to/mynewwallet.dat

There are quite a few projects out there that take advantage of this. There is an ecommerce plugin for woocommerce:

http://wordpress.org/plugins/bitcoin-payments-for-woocommerce/

Then this concise PHP script by @stick:

https://github.com/prusnak/addrgen

Very very cool! As Bitcoin for Woocommerce shows, it removes third-parties from transactions. Thanks for the links. Amped!

[Abdussamad]

Very very cool! As Bitcoin for Woocommerce shows, it removes third-parties from transactions. Thanks for the links. Amped!

To be fair you still need a way to verify transactions. Bitcoin for woocommerce uses blockexplorer.com with fall back to blockchain.info.

There is a way to get both master public key based address generation and transaction confirmation without relying on third parties. There is an example script called merchant.py in the electrum repository that shows you how to do this:

https://github.com/spesmilo/electrum/blob/master/scripts/merchant.readme

It runs as a daemon and you can configure it to callback your script each time a transaction hits one of your addresses.

But I don't know python so I haven't succeeded in getting it to work.

[piotr_n]

So if someone gives me an extended public key, I can generate public keys to addresses that the other person can unlock (by generating the appropriate private key on their side). Is this correct?

Not quite.
You need to give him your public key and the secret.
From these two, one can "guess" further private keys.

The bolded part is incorrect. It might be a typo. You can never derive private keys from public keys. If you could do that it would shake the very foundation of bitcoin and public key cryptography.

piotr_n must have meant public key.

Yeah, sorry guys - I indeed meant public keys.
Thanks for correcting

[piotr_n]

This topic is 15 pages long, so please forgive me it it was discussed already.

Having in mind the recent same K-value problems in the signatures, I have been thinking about a deterministic wallet solution where exposing one private key does not expose all the others, that come after it.

So in my solution (which I call type-3), I do something like this:

Code:

seed_key = SHA256(seed_password)
for (n=0; n<KEY_CNT; n++) {
  priv_key[n] = SHA256(seed_key)
  seed_key = seed_key || (byte)n
}

Where SHA256 is actually the double sha256 and my wallet is a brain wallet (based on the seed_password).

Could you please give me any feedback on whether you see any security risks with such an approach?

[TierNolan]

So in my solution (which I call type-3), I do something like this:

Code:

seed_key = SHA256(seed_password)
for (n=0; n<KEY_CNT; n++) {
  priv_key[n] = SHA256(seed_key)
  seed_key = seed_key || (byte)n
}

What do you mean by || ?  If that is the OR operator, then you are going to set the least significant byte to all 1's, since after 256 values n will have 1 in every possible bit position.

Could you please give me any feedback on whether you see any security risks with such an approach?

One of the big benefits of deterministic wallets is that a public server can generate the public keys without compromising the private keys.

The OP in this thread has a way to do it with safety (I think).

Root private key: k
Root public key: K = kG

You can then generate a public key by picking an offset n.

Private key(n): k(n) = k + X(n)
Public key(n): K(n) = (k + X(n))*G = kG + X(n)*G = K + X(n)*G

However, you need to keep the X(n) function secret.

If some obtains

- the X(n) function (available by hacking the server)
- the private key k(n) for a public key K(n) (ECDSA break/implementation error)

They can compute k from

k(n) - X(n) = k + X(n) - X(n) = k

It seems to me that deterministic wallets are inherently less secure than normal wallets. 

If a normal address is only used once, then it is protected by both the RIPEMD160 hash and the ECDSA system.

Deterministic wallets are only protected by the ECDSA.

[piotr_n]

What do you mean by || ?  If that is the OR operator, then you are going to set the least significant byte to all 1's, since after 256 values n will have 1 in every possible bit position.

By || I mean appending one byte at the end of the seed_key, that gets hashed later to get the next private key.
So next time you calc a private key, you are hashing what you had hashed before, plus one byte more...

I was worried that maybe this could be somehow exploited, especially when the attacker knows that I append the bytes always with the same sequence (0,1,2,3,...)?

One of the big benefits of deterministic wallets is that a public server can generate the public keys without compromising the private keys.

Yeah. That's type-2. I have it implemented in my app, but I personally don't use it, because it allows the "public server" to predict my further public keys and I see more cons than pros with this. It might make a lot of sense for e-commerce apps, but I don't really need such a feature for a private use.

[piotr_n]

So if someone gives me an extended public key, I can generate public keys to addresses that the other person can unlock (by generating the appropriate private key on their side). Is this correct?

Not quite.
You need to give him your public key and the secret.
From these two, one can "guess" further private keys.

The bolded part is incorrect. It might be a typo. You can never derive private keys from public keys. If you could do that it would shake the very foundation of bitcoin and public key cryptography.

piotr_n must have meant public key.

Yeah, sorry guys - I indeed meant public keys.
Thanks for correcting

BTW, I also had second thoughts about the anonymity issue, with the type-2 wallets.

Initially I had thought that keeping "B_secret" secret does prevent others from guessing further public keys... but then it came to my mind (though, please correct me if I'm wrong) that just by having two consecutive public keys that came from the same type-2 deterministic wallet, it should be rather simple to calculate the B_secret - shouldn't it?

I mean, if

Code:

B_public_key = A_public_key + B_secret * G

Then:

Code:

B_secret = ( B_public_key - A_public_key ) / G

Right?

Or isn't it possible to do the second math?

[TierNolan]

Initially I had thought that keeping "B_secret" secret does prevent others from guessing further public keys... but then it came to my mind (though, please correct me if I'm wrong) that just by having two consecutive public keys that came from the same type-2 deterministic wallet, it should be rather simple to calculate the B_secret - shouldn't it?

I mean, if

Code:

B_public_key = A_public_key + B_secret * G

Then:

Code:

B_secret = ( B_public_key - A_public_key ) / G

Right?

Or isn't it possible to do the second math?

Most system use hashing.

The Armory system is that you work out a multiplier based on the chaincode and the current public key.

Multiplier(n) = ChainCode XOR Hash256(PubKey(n))

Public Key(n+1) = multiplier(n) * public key(n)
Private Key(n+1) = multiplier(n) * private key(n)

So, if you have the nth private key, you can work out the nth multiplier and then compute the (n+1)th key pair and by iterating, you get all the later pairs.

It doesn't let you work out the keys from before n (since that would require reversing the hash function).

You need the chain code, which isn't suppose to be public info.

Under your scheme, the private keys are directly generated by the server, so that is the worse than just having the chain code and root public key on the server.  

An attacker with public key(0) and the chain-code can obtain all private keys after the first private key they obtain.  

If someone hacks a server using your system, they get all the private keys.

[piotr_n]

Initially I had thought that keeping "B_secret" secret does prevent others from guessing further public keys... but then it came to my mind (though, please correct me if I'm wrong) that just by having two consecutive public keys that came from the same type-2 deterministic wallet, it should be rather simple to calculate the B_secret - shouldn't it?

I mean, if

Code:

B_public_key = A_public_key + B_secret * G

Then:

Code:

B_secret = ( B_public_key - A_public_key ) / G

Right?

Or isn't it possible to do the second math?

Most system use hashing.

The Armory system is that you work out a multiplier based on the chaincode and the current public key.

Multiplier(n) = ChainCode XOR Hash256(PubKey(n))

Public Key(n+1) = multiplier(n) * public key(n)
Private Key(n+1) = multiplier(n) * private key(n)

So, if you have the nth private key, you can work out the nth multiplier and then compute the (n+1)th key pair and by iterating, you get all the later pairs.

It doesn't let you work out the keys from before n (since that would require reversing the hash function).

You need the chain code, which isn't suppose to be public info.

Oh, I see. Thanks for explaining.

Under your scheme, the private keys are directly generated by the server, so that is the worse than just having the chain code and root public key on the server.  

An attacker with public key(0) and the chain-code can obtain all private keys after the first private key they obtain.  

If someone hacks a server using your system, they get all the private keys.

It's not really my scheme, it comes from the OP, but I do not quite get your logic that under this scheme "the private keys are directly generated by the server".
From what I understand, the whole idea of Type-2 scheme (from OP) is about generating the private keys outside the server. And I even checked it - it surely works.

EDIT: unless here you were talking about the scheme I described in this post?
There I generate the public addresses in my offline wallet and them move them online, for balance tracing.

[TierNolan]

There I generate the public addresses in my offline wallet and them move them online, for balance tracing.

Ahh ok.  You would get the same thing by having the chaincode.  However, if the chaincode is not on the public server then it doesn't matter either way.  You are just generating a set of public keys one way or another.

[piotr_n]

There I generate the public addresses in my offline wallet and them move them online, for balance tracing.

Ahh ok.  You would get the same thing by having the chaincode.  However, if the chaincode is not on the public server then it doesn't matter either way.  You are just generating a set of public keys one way or another.

I sort of mixed up two different issues here.

One was my request for an audit of my deterministic wallet solution, which does generate public keys in the wallet, but is supposed to be "resistant" when one on the private keys gets compromised. I did not get much feedback here, but since nobody has stolen my coins yet, I'm guessing it's somehow secured enough

The second issue was the privacy of the deterministic wallets, as they are being implemented now, by other parties; the kind of solution where you can generate further public addresses without having an access to the actual wallet. My concern was: how easy it will be for the attacker to figure out the secret/chaincode, while already having a couple of public keys from such a deterministic solution... From what you said, it won't be possible to figure out the chaincode, even having millions of consecutive public keys, or in other words: as long as you keep the chaincode secret, nobody can just calculate it from your public addresses. That's good to know - thanks.

[iddo]

One was my request for an audit of my deterministic wallet solution, which does generate public keys in the wallet, but is supposed to be "resistant" when one on the private keys gets compromised. I did not get much feedback here, but since nobody has stolen my coins yet, I'm guessing it's somehow secured enough

Your type-3 appears to inferior to type-1: with type-1 there's one master secret, and in case that master secret leaks then all the other privkeys in your wallet also leak, but in the case that certain privkeys themselves leak the all the other privkeys don't leak. With your type-3, for efficiency the user's client may opt to store many seed[n] values, and if any of those seed[n] leak, then all the subsequent privkeys leak too. And just like with type-1, with your type-3 wallet if the master secret leaks then the entire wallet leaks. You haven't explicitly tried to claim what's the supposed advantage of type-3 over type-1, but maybe what you had in mind is that in order to generate the next privkey the user wouldn't need to access the most sensitive piece of data which is the master secret, and will only need to access the seed[n-1] data instead, We have discussed similar properties here before. If you think that your type-3 has any advantage over type-1, please describe with precise details how the client software is supposed to retrieve an arbitrary privkey[k] without access to the master secret. Do you propose to have multiple layers of encryption every time that a new seed is derived?

The second issue was the privacy of the deterministic wallets, as they are being implemented now, by other parties; the kind of solution where you can generate further public addresses without having an access to the actual wallet. My concern was: how easy it will be for the attacker to figure out the secret/chaincode, while already having a couple of public keys from such a deterministic solution... From what you said, it won't be possible to figure out the chaincode, even having millions of consecutive public keys, or in other words: as long as you keep the chaincode secret, nobody can just calculate it from your public addresses. That's good to know - thanks.

If SHA2 is pseudorandom then it's infeasible to figure out chaincodes from the pubkeys. The more tricky question is whether you could carry out a related-key attack after seeing many signatures, and the answer is "no".
In practical settings, the issue that concerned us is that if you're running a listening-only server that doesn't have access to the privkeys but does have access to chaincodes, and your server is compromised, so if an attacker could obtain a single privkey from another source (not from the listening-only server because that server doesn't even know the privkeys) then all the privkeys in your wallet will leak. Our solution is to use type-1 derivation for the root of the branch that the listening-server would be using, so that any leakage of privkeys will be confined only to that branch, and the user is advised to store privkeys that control high amounts of coins in different "cold storage" branches.

[piotr_n]

Your type-3 appears to inferior to type-1: with type-1 there's one master secret, and in case that master secret leaks then all the other privkeys in your wallet also leak, but in the case that certain privkeys themselves leak the all the other privkeys don't leak. With your type-3, for efficiency the user's client may opt to store many seed[n] values, and if any of those seed[n] leak, then all the subsequent privkeys leak too. And just like with type-1, with your type-3 wallet if the master secret leaks then the entire wallet leaks. You haven't explicitly tried to claim what's the supposed advantage of type-3 over type-1, but maybe what you had in mind is that in order to generate the next privkey the user wouldn't need to access the most sensitive piece of data which is the master secret, and will only need to access the seed[n-1] data instead, We have discussed similar properties here before. If you think that your type-3 has any advantage over type-1, please describe with precise details how the client software is supposed to retrieve an arbitrary privkey[k] without access to the master secret. Do you propose to have multiple layers of encryption every time that a new seed is derived?

Thanks, you are so right.

When I read it again now, it is actually doing quite the same, as my "just invented" type-3

The wallet stores a large random seed  S (which can be encrypted if the user uses wallet encryption)

Privatekey(type,n) is then simply set to H(n|S|type).

So honestly, I don't know where I got this idea from, when I was thinking that the type-1 was about:

Code:

Privatekey[0] = H(S)
Privatekey[n] = H(Privatekey[n-1])

But now I see it was a stupid idea, and it existed only in my head - so never mind... Sometimes it is worth to make an idiot of yourself, just to learn something

Cheers, guys.

[gatomalo]

noob question is how can I apply the HD wallet to a web environment with multiple users. Once the wallets are created I can store everything in a MYSQL or something. Wouldn't I be able to query the blockchain  and update the web wallets. I think we can give the world a safe BIP0032 HDwallet that can be used online and on devices at the same time as a paper backup. Any help would be welcome. 

[grau]

The point of HD Key Generation, that is BIP32, is to protect you against accidental loss of keys (not theft!). Once you have a backup of a master key you are able to recreate any key to any address that is derived from that. The master keys may form a hierarchy that is helpful in a larger or more complex setup such as a multi-user environment.

Querying the block chain in a performant manner is a non-trivial task for a large number of addresses. I claim that querying is not even feasible for a bigger implementation. You rather need an architecture of monitoring and persistent caching of the subset you care.

Security is an even bigger concern as storing the master keys on-line that are capable to spend multiple user's entire balances instantaneously, or creating backups that if fall into wrong hands give same level of access are sure recipes for disaster. Practically all wallet services that did so got compromised and lost all their customer's money.

You need to deploy a set of techniques if dealing with other people's money in a large installation, of which BIP32 is only one basic building block. Contact me for a complete solution.

[iddo]

Because of the (mod n) operation, it looks to me like any possible value of IL would be valid.

The issue isn't validity, it's uniformity, i.e. we wouldn't want some privkeys to be more likely than others.
Please see posts #220 and #226 of this thread.

[iddo]

Re: deniable encryption

The simple use-case for deniable encryption is an attacker who points a gun at you and demands that you decrypt your Bitcoin wallet so that he can take your coins, hence you decrypt by using a decoy secret key that only gives the attacker a smaller portion of your coins, and while you're in a safe environment you decrypt your wallet with another secret key to access the larger portion of your coins. The attacker might see your screen with your wallet before he approaches you, therefore for everyday use you should prefer to operate with the version of your wallet that only controls the smaller portion of your coins (i.e. the pubkeys that correspond to the larger amount of coins will also be encrypted). This can be done by separate wallet.dat files, but built-in support for BIP32 wallet can be nicer, by selecting some branch in the deterministic tree as your decoy wallet, so you can easily transfer coins to/from that branch (see also post #192 in this thread).

It is easy to see that symmetric deniable encryption implies that the ciphertext must be bigger than the plaintext, simply because ordinary symmetric encryption is highly efficient. Suppose that you have two incompressible files f1 and f2 (i.e. files with high entropy) of same size, and note that the size of AES(f1) is the same as the size of f1. If you could create a ciphertext c1 of same size as f1 that can be decrypted into f1 by using the secret key k1 and can be decrypted into f2 by using another secret key k2, then you effectively compressed (f1,f2) into (c1,k1,k2), which is impossible.

This implies that if the attacker controlled which symmetric encryption algorithm we must use then there's no hope to have deniable encryption, but fortunately we can choose to use by default a symmetric encryption algorithm that expands the size of the ciphertext. Since wallet.dat files are quite small, that isn't really a big deal for end-users.

The straightforward construction for symmetric deniable encryption is simply concatenation, meaning that if we have the real plaintext f1 and the decoy plaintext f2 then the ciphertext is c=(c_1,c_2)=(enc_AES_k_i1(f1),enc_AES_k_i2(f2)) and the decryption algorithm dec(c,k,idx) will invoke dec_AES_k(c_idx), meaning that for {i1,i2}={1,2} the real secret key is (k1,i1) and the decoy secret key is (k2,i2).

The reference Bitcoin client can have by default a checkbox that reads "Support for deniable encryption", and when a user (who doesn't care about deniable encryption) encrypts his wallet the client will simply create a ciphertext that's twice the size of the plaintext where one random half is random data. This checkbox should be on by default, and each user can turn it off if he wishes to have a smaller ciphertext. If the user does care about deniable encryption, he encrypts his wallet with real half and decoy half by using the simple concatenation construction. If an attacker points a gun at this user, he will decrypt with his decoy key, and the attacker cannot tell whether the other half is random data (which would be the case with an ordinary user who didn't specifically choose to use deniable encryption) or not.

To protect against scenarios where the attacker has a reason to suspect that the user did use deniable encryption, and therefore try to force the user to reveal his 2nd secret key, it might be preferable to concatenate some n<N ciphertexts of variable sizes, instead of two ciphertexts of equal size, where n is random and N is some fixed bound. This way, the attacker wouldn't even know how many decoy wallets are contained in the ciphertext.

Edit: actually it isn't completely clear whether AES can be obliviously generated, meaning that (for random k) enc_AES_k(random) could be distinguishable from random (thanks to Hong-Sheng Zhou for this info), but in the worst case we'd just need to invoke AES once to encrypt random plaintext with random key and throw away the key...

[leanne]

quick question: deterministic wallets like electrum that have a master public key from which the public addresses may be (re-)generated subsequently. does one really need the master public key in order to generate those addresses or would it be possible to generate the subsequent addresses from e.g. the first public key (address)?

[jonald_fyookball]

quick question: deterministic wallets like electrum that have a master public key from which the public addresses may be (re-)generated subsequently. does one really need the master public key in order to generate those addresses or would it be possible to generate the subsequent addresses from e.g. the first public key (address)?

Yes you do need the master key.

An address is just a hash, and even if you knew the public keys
of specific addresses, you would not be able to determine
the other elliptic curve points of other addresses without the
master key.

[leanne]

quick question: deterministic wallets like electrum that have a master public key from which the public addresses may be (re-)generated subsequently. does one really need the master public key in order to generate those addresses or would it be possible to generate the subsequent addresses from e.g. the first public key (address)?

Yes you do need the master key.

An address is just a hash, and even if you knew the public keys
of specific addresses, you would not be able to determine
the other elliptic curve points of other addresses without the
master key.

Ah, alright, thanks! But you would be able to do that with the master public key, even though thats also just a public key!?