Single key wallets with privacy

[ffe]

This may have been described elsewhere but I haven't seen it.

It is possible have wallets with only one key yet have all transactions sending coins to that wallet be private in the sense that they are not traceable to that wallet (other than the sender knowing he sent coins to that wallet of course).  This involves no changes to the protocol or the block chain. The client would change however.

The idea is that the sender recognizes the public key as a wallet key, not a vanilla receiving key.  When this happens, the sender generates a new, unique, public key from the receiver's wallet's master public key.  He sends to that new public key when creating the transaction for sending coins.  The sender cannot, however, generate the corresponding private key.  Only the receiver can generate the private key (it is derived from the wallet secret master key as described below).  So only the receiver can later spend those coins.  Furthermore, no one but the sender and receiver know that the transaction belongs to the receiver.

With single key wallets backing up becomes much simpler since you don't have to make sure you back up all the keys generated by the client for the purpose of receiving. Only the master key is backed up.

Having the same wallet on multiple clients is much simpler as well since none of the clients have to "generate new blocks of keys" to receive (for receiving change for example) the way the current clients do, so coordination is just not an issue.

This is how you implement a single key wallet:

Assume Alice owns a single key wallet. This wallet has a key that cannot be used in a normal fashion by other clients to send to. (Let's say this new key has a new key type in the key block for example). Let "a" be the wallet private key.  The wallet public key is "A" (A = aQ where Q is the basis point in the curve).  A is published by Alice.  Also, let Bob have a wallet and it has coins under a public key "Y" so the bitcoin block chain has a transaction transferring coins to "Y" and Bob has the private key, "y", corresponding to "Y".

Bob wants to send some coins to Alice. He looks up "A" and and his client notices it cannot send directly to "A" (because of the key type). The current client would just stop here. If Bob's client knows about single key wallets, it instead generates a public key "X" from "A", "y", and "m" ("m" is randomness derived from parts of the transaction that transfers the coins).  "X" has the property that only Alice can derive the private key "x" and only Bob knows that Alice owns "X". Alice can spend the coins in "X" by generating "x" and using it to sign a transaction spending the coins at some future time.

Bob generates "X" as follows:  s = Hash(m,yA);  X = sA  (note yA and sA are cryptographic multiplies in ECC)
Note, only Bob and Alice can generate "s".  Also, Bob cannot generate the private part of "X" but he can transfer coins to "X".

Alice generates "x", the private part of "X", as follows:  She obtains m and Y from the transaction; then  s = Hash(m,aY);  x = sa (modulo a large prime determined by the ECC);  She can check that X = xQ.
Note, yA = aY and only Bob and Alice can calculate them. Also, "X" is derived from "A" but no one can prove Alice is the owner of "X" since only Alice and Bob know "s".

"m" is chosen so that no two transactions produce the same "s". Hence "X" will always be unique to that transaction. "m" would be a few bytes from the transaction that are unique to the transaction but are not dependent on "X", the receiving key in the transaction.

A client holding wallet "A" would have to check every new transaction for the property that s = Hash(m,aY) and X = sA to know to add the coins to the balance in the wallet. This is expensive. We could save time by leaving a few bytes from Hash(s) in an available field of the transaction. That would save one of the two required ECC multiplies. The client would still have to calculate an "s" for each transaction but after that the Hash(s) is relatively cheap.

Finally, Deterministic Wallets:
Wallet "A" could be generated deterministically by generating "a" from a hardened password and salt as described elsewhere for deterministic wallets. Having this wallet on multiple clients would be much simpler since the clients don’t have to coordinate generating receive keys.

[ffe]

Some deterministic wallet implementations have “light” clients talking to (untrusted) servers that handle the heavy work of scanning the bitcoin block chain and linking to multiple peers.

In that scenario the server should be able to check the ownership of a new transaction without being able to spend the coins in the transaction. Allowing this conflicts with the stated property of privacy when using single key wallets.

This note is to show how you allow a server of your choosing to verify that you own a transaction without allowing the server to spend your coins or allowing the whole world to know which transactions are yours. It’s an intermediate level of trust that may not make sense to people who value strict privacy but is useful to people who value the single key property (for ease of multiple light client deployment, for example).

It’s done this way:

The wallet master key is really a key doublet. The private key is “a”. Generate a verifier private part “b”.  b = Hash(a). Let the public part of “a” be “A” and the public part of “b” be “B”.   A = aQ and B = bQ. The doublet “A,B” is published as the wallet master public key. “A,B” and the private verifier “b” are given to the service(s) you are using to manage the block chain for you. With “b” the server can verify transaction ownership but not spend.

A sender would recognize “A,B” as a wallet key. The sender then generates "X" as follows:  s = Hash(m,yB);  X = sA. The sender sends coin to “X”.

A server holding verifier "b" would have to check every new transaction for the property that s = Hash(m,bY) and X = sA to know to add the coins to the balance in the wallet. (Note yB = bY). As I mentioned in the previous post, this is expensive. We could save time by leaving a few bytes from Hash(s) in an available field of the transaction. The server would still have to calculate an "s" for each transaction but after that the Hash(s) is relatively cheap.

Note the server can verify “X” but cannot generate the private part of “X”.

The thin client generates "x", the private part of "X", as follows:  She is given m and Y from the transaction; then  s = Hash(m,bY);  x = sa (modulo a large prime determined by the ECC);  She can check that X = xQ.

The thin client can now sign a prepared transaction using “x” and return the signed transaction to the server when spending.

[gmaxwell]

This may have been described elsewhere but I haven't seen it.

Type-2 deterministic wallets: https://bitcointalk.org/index.php?topic=19137.0

[ffe]

This may have been described elsewhere but I haven't seen it.

Type-2 deterministic wallets: https://bitcointalk.org/index.php?topic=19137.0

Nice. I guess mine isn't the first single key wallet.

One difference is with Type-2 deterministic wallets the receiver has to generate the extra keys and distribute them whereas here the sender can generate a new key for the receiver whenever he is ready to send. It's easier to backup this wallet or have multiple clients carry the same wallet here since there is no need to coordinate the generating of new keys.

[ByteCoin]

I came up with a scheme which looks like it's functionally equivalent in the thread called Protecting privacy without generating and distributing new addresses.

It wasn't popular then but I still think it's a good scheme.

I imagine it's possible to come up with variants to allow untrusted third parties to recognize your transactions and send them to you if you don't want to scan all transactions.

ByteCoin

[ffe]

I came up with a scheme which looks like it's functionally equivalent in the thread called Protecting privacy without generating and distributing new addresses.

It wasn't popular then but I still think it's a good scheme.

I imagine it's possible to come up with variants to allow untrusted third parties to recognize your transactions and send them to you if you don't want to scan all transactions.

ByteCoin

Yes. This is an equivalent scheme as well. Hard to tread where no man has gone before, it seems.
You even point out the ease of backup with this scheme...

It means that one can make one backup of one's wallet and then it's safe forever. In the existing situation you need to back up your wallet every time a new "block" of addresses are generated.
ByteCoin

Maybe with new light clients coming out this will find a more receptive audience.

[etotheipi]

You even point out the ease of backup with this scheme...
...
Maybe with new light clients coming out this will find a more receptive audience.

Keep an eye out for Armory which is a client I've spent 6 months developing, and should be released (alpha) within the next month.  Among the plethora of fantastic features is that it uses Type-2 deterministic wallets for everything, and it gives you an option to print a paper backup of the wallet when it is created.  And because it's type-2, it also supports watching-only wallets, so that you can create your offline wallet, make a no-private-key copy of it, and use it to generate addresses and monitor transactions from an online computer.

Teaser:  below is a screenshot of Armory's paper-backup dialog -- yes, it only needs to be backed up once (unless you manually import addresses)


At the moment, it's about as far from lightweight as it can get.  But the current goal is proof-of-concept of the features, and I have a development plan to scale-down/fork a "lightweight" version, and eventually release a sister Android/iPhone app. 

P.S. - It will be open-source (AGPL v3) and the code can be found here.  (trying to drum up some hype for it before the first release)

[btc_artist]

Very nice etotheipi.  BTW, I'm assuming this is the project you wanted the logo design for a while back in that other thread?