Topic: Deterministic wallets (Read 48413 times)

I don't think that you want this organization to create the "seed" because it implies that this organization can also steal the user's coins.

Maybe what you want is that any user can generate a fresh seed (that derives privkey/pubkey pairs so that only the user knows the privkeys), where the master pubkey and master chaincode (that are derived from the seed that he generated) must be signed by this organization before this "user account" becomes valid on this network? This implies that new users are at the mercy of this organization, e.g., this organization may refuse to sign a new account unless it receives a bribe on the side. Also, if the signing key of this organization is compromised then all bets are off.

At it's core, this is an HD Wallet question: 

I'm looking into developing a special purpose alt-coin and would like keep it largely the same as bitcoin except for what follows.  I would appreciate if someone would help me by telling me if a new protocol could be developed to support these requirements:

1.  we need to be able to have an internal organization create the seeds on behalf of a user (at their request.)
2.  this internal org would securely and confidentially maintain the user-to-seed relationship (no one else would know and it's a key requirement
3.  the user would be able to create any number of private or public keys themselves but always maintain the connection back to the original seed

Users would send and receive coins as bitcoin works today, with a blockchain as the ledger.  Users would be awarded coins by the company and can spend them/trade them with anyone else who also has a PK.

With these requirements, I would essentially have an audit trail of everyones transactions but only the internal organization could tie the transactions to a real employee.

Public keys in bitcoin are calculated by multiplying a private key by the generator point of the secp256k1 curve. This is a trapdoor function, where there are a lot of possible private keys, and a lot of public keys, and the oeration

Similarly, you can add numbers to private keys to get a new number, which would yield a different point.
You can also add two points together, which is equivalent to adding two numbers together.

Since public keys are by definition public, no harm comes by revealing them besides a loss of privacy. Public keys can be used to generate deterministic offsets between points on the elliptic curve.

By hashing the 'master public key', and a sequence number for the public key, you have deterministic 'offset' from the master public key - which is just a 256bit integer.. Which like private keys, can also be converted to a point.

So for public derivations, you have the master public key (a point) and an offset (another point), and you add these two together.

The private derivation assumes you have the private key, and want to obtain a child private key. You take the private key (a number), generate the offset from the master public key (a number, but this time it's not converted to a point, you keep the number), and then you do modulo addition..

Lo and behold, it yields a number (the private key), which when multiplied by the generator, gives the same point as when you added two points together using purely public information. The private derivation works because the person has the master public key and could hash it also.

The reason you cannot share a master public key AND private key, is that someone can deduce it in this way (in a simple example)

// Attacker has Master Public Key, Address6/PublicKey6, PrivKey6
hash = hash('mpk'+'6')
offset = hash * G
Pub6 = PointMPK(x,y) + offset

Priv6 = k.

Main Priv Key = Priv6 - offset
Main Priv Key * G == mpk.

Now to calculate every private key in the chain:
PrivKey(n) = MainPrivKey + hash('mpk' + n)

Ah alright, thanks! That's interesting, I really didn't know that the master public key may actually be an attack vector when compromised (in combination with an according private key). But it makes sense if it isn't a hash after all.

I can only tell you how it works in Electrum:

The master public key is not a hash.  It's simply a hex-encoded
public key to the master private key, which is an elliptic curve
key based on the deterministic seed.

New addresses are generated from the master key by
generating new ECDSA coordinates, basically by
combining new sequence numbers with that master key
to create a new point.

As with a normal Bitcoin address, you can calculate
the public key from the private key, but not the
other way around.  This is no different.

One consequence of the master key scheme,
is that if a single address in your wallet is compromised
(the private key becomes known), and the
attacker knows the master public key,
they can crack the entire wallet, because
they could use the one private key together
with the master public key to discover the
master private key.

For that reason, the master public key should be
kept secret.  Its purpose (at least in Electrum)
is to create a watching-only wallet.

that's clear, I was just making sure that indeed the master public key is needed in order to generate subsequent addresses even though it's just a public key (is it still a hash, though? what is it compromised of?)

The master public key can generate addresses but not the private keys of those addresses.

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

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.

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

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

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.

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.

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. 

Thanks, you are so right.

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


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

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.

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?


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.

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.

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.

Oh, I see. Thanks for explaining.


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.