Topic: Protecting privacy without generating and distributing new addresses. (Read 1608 times)

Since I like making pictures, here's one that should clear up everything I've said so far.  The "DHSS Key Gen" is your proposed solution that I have already declared is brilliant.  It represents the way to create "friends" that can generate new keys for each other after a handshake.

Everything else is the full puzzle I was trying to convey.  If you re-read my previous posts, you'll see this is what I was trying to communicate, but did so very poorly.



Full-sized image is at:  http://dl.dropbox.com/u/1139081/BitcoinImg/overflow/Unified_DHSS_Solution.png

Keep in mind that this only shows other people sending me money.  The handshake would also enable me to send them money without requesting a new address.

Whoa, I missed something here.  I wasn't proposing an alternative to your idea.  Your idea is absolutely elegant & brilliant, but I don't see how it solves the problem of one-time wallet backup and privacy-preserving key generation,  it's simply one (critical) piece of the puzzle.  This isn't off-topic, I was trying to fill in what else would be needed to complete this puzzle.  I think you misunderstood.  Or I misunderstood the puzzle.

EDIT:  look at the picture in my next post before continuing

Take the example:  you run a small business.  You have 100 customers every week paying you with one-time addresses who will never engage in your solution because it's not necessary.  But you have relationships with banks, distributors, maybe frequent customers that do benefit from your solution.  So you set up your client to use your (ByteCoin's) solution.  
  
The problem is your client is checking all those one-time addresses for DHSS-based addresses and at some point it just can't keep up anymore because your wallet is so huge.  Should your client check every key in every global transaction going forward forever?  I argue that it's not only best, but actually necessary to encode this into the blockchain via some kind of handshake -- if we want this solution to accommodate all use cases.

• If you don't do some kind of filtering/revocation, the computation required for a large wallet will become prohibitive.  The CPU will be calculating DHSS's for thousands of your own keys in every transaction that goes by just to see if money was received (even though 99% of your keys will never have your proposed address scheme applied to them).    
• You can't rely on the user to tell the client what to search for, it needs to be evident to your BTC client.  If the user doesn't do it right, they could end up missing transactions that they should've been searching for, or make their computer unusable while it searches everything.
• Even if you could trust the user, the wallet was only backed up once, which means in the event of recovery all this information is lost forever.  There's no way to recover it and thus you run into the problem above.
• By encoding the rules into two transactions, once, you enable your client to automatically apply your solution with minimum, bounded computation.
• Your solution is likely to be used by parties who expect to execute many transactions over the course of their financial relationship.  Two tx's exchanged once to initiate this agreement is noise.
• Maybe I don't want people assuming I accept these chained address transactions unless there's an explicit agreement
• This handshake allows you to encode the start of the agreement and the revocation into the blockchain with the same degree of anonymity that your solution provides for actually generating addresses

It can be debated whether the fact that X and Y are handshaking needs to be concealed (per the last bullet point).  But my solution solves all the problems described above, and perfectly compliments your solution.  (it may not be a great/simple solution, but it does work, and we're here to discuss these things)

As for alternative clients, I don't think it's your place to tell me I shouldn't be working on alternative clients.  Not all ideas (like this one!) can un-controversially go into the main client.  The main client doesn't work on Android/iPhone.  Not everyone can program C++.  Not everyone wants the full blockchain on their computer.  No one will ever agree on all the features that should go into it.  What if I don't like the file formats, data structures and encryption schemes?  What if I wanted to do something different?  How many people can really understand Bitcoin without getting their hands dirty writing the protocol themselves?  I could go on, but I'm trying to stay on-topic...[/list]

You correctly identify that my proposal needs a way to revoke keys in the event that they are compromised. This is an implementation detail and is not cryptographically interesting. All that is required is the publication of some suitably signed message.

Your proposal, etotheipi, bears scant resemblance to the scheme I outlined in the thread.

Step 1 of your process involves both parties generating new keys. The rapid proliferation of unrelated keys is something that my scheme is designed to avoid.
Step 2 of your process involves the recipient of funds sending the funder a new public key for them by some authenticated channel. This is analogous to the current need to pass the funder the address to receive their bitcoins, hence your scheme is no better in this regard. My scheme on the other hand does not require any direct communication between parties.
Step 3 and 5 of your scheme involves dust spamming the network in order to pass information between the parties. This is not a feature of a promising scheme.

Your proposal seems to be intended to facilitate repeated interaction between two parties. I suggest you instead advocate hashcoin's fine "Instant TX for established business relationships" scheme which has the advantage that most transactions don't touch the network.

Also I recommend collaborating with the other developers to improve the mainstream client rather than writing a new one.

If you wish to suggest improvements and alterations to my scheme then I welcome your thoughts on this thread. If your ideas are at such variance then starting a different thread would be more appropriate. On-topic discussion please!

ByteCoin

Bytecoin,

I will PM you later, as I put together a more formal proposal relating to this idea. But I want to hear your thoughts on two other things:

(1) My current proposal will suggest a hash-based generation method for generating new keys for parties that you have never communicated with.  This means that you generate new addresses yourself with secure hashing methods, all based on your original 256-bits of entropy.  There is, of course, EC-related ways you could do this, but I believe hashing is "better" as you don't need reversible transformation.  In the end, it's probably moot since all of these techniques are extremely secure.  But if you see some reason to use the crypto methods to generate new keys for new parties, I'd like to hear them.

(2) One major drawback to your idea is the risk that if your base key was compromised, someone may send you money not realizing that it's no longer a secure address.  This could be a devastating problem, especially with parties that exchange money frequently.  I'd like to propose a HaltChain message based on the initial key exchange between parties A and B that will let the other party know to stop sending money to these addresses.   Here's the proposal and the CONOPS for it (concept-of-operations) for A and B to initiate a long-term financial relationship :

EDIT:  I have rewritten the following from the original post, to reflect a new, better handshake process than the original without diluting this thread any further.   Note that DHSS is "Diffie-Hellman shared secret."

• (1)  A and B both create new addresses specifically for establishing this relationship.  Use hash-generation to create these new keys.
• (2) A sends B a Base58 version of his public key -- this only has to be done once (and really not any more burdensome than sending the address alone).
• (3) B will fund his new address and from that address construct a Tx to the address provide by A's public key.  It's important to note that B is sending directly to the address, not some computed version of it . The Tx amount containse the relevant information: it is the DHSS value computed based on both public keys, modulo 1e6.  If the DHSS is 19284183992249101 the transaction value will be 0.00249101.
• (4) A will look for such transactions, but only has to look at his own transactions, not the entire blockchain since he knows that such handshake tx's will be sent directly to one of his own addresses (massive computation saver!).
• (5) A will construct a reply transaction for the exact same amount, to a new computed address for B, based on the Diffie-Hellman sender-generation technique.
• This completes the handshake.  A and B both flag these two addresses as "chain-bearing" addresses, and compute a shared haltcode:  DHSS^249101 mod N (where N is the size of the EC group).
• In the event that one party's keys are compromised, or one party just wishes to reset the chain for security reasons, they simply send a transaction for any amount to the address ripemd160(sha256(HaltCode)).
• Before either party generates a new address for the other one, they will search the blockchain for any tx sent to the halt-code (a small price to pay for security).  If the halt-code is observed, the sender knows that the chain has been canceled and they need to contact the recipient to obtain a new address

Now, let's say A and B both lose their wallets and need to reconstruct their transaction history.

A only needs to search through transactions that were sent to one of his hash-generated keys.  A can calculate the DHSS for each of those [limited number of] Tx's, and see if the value matches the computed DHSS value.  If it does, he should check if that address then signed an identical transaction to another address.  If so, that's a chained tx handshake.

B only needs to search for transactions from his own keys and check whether the value is a computed DHSS code.  If so, he can check for the reply transaction from that address and confirm that he actually owns that address.

Actually, both parties need to search for both, because they don't know whether the were the originator or responder, but neither of them have to search the entire blockchain.  And the only identifying information here is that one address sent a transaction to another unrelated address for its entire balance, which really isn't all that uncommon.

This process provides a lot of explicit benefits for both parties:

• Explicit agreement before parties start executing the Diffie-Hellman address generation.  For most transactions (one-time sales on ebay), you wouldn't want or need to establish this relationship.
• Dramatically reduces the number of your own public keys that you have to search the blockchain for, and thus reduce computation.  Most of your keys will not follow this protocol and you won't need to search for chained transactions on those addresses.
• A related benefit is that the HaltCode also lets you know when you can stop searching for transactions on that chain.  This means that you can remove public keys from the pool of keys you search for.
• It provides a way for parties to communicate that they wish to change their key generations chains for any reason.  Businesses may choose to do this a couple times a year to invalidate any key chains that might be compromised by malicious employees.

Perhaps this is completely overkill.  Let me know what you think.  Either way, I want to start combining all these ideas into a unified proposal for a specification like this.  Even if it wouldn't be included in the main client, I have my own lite-client I'm working on, and if we can create a "standard implementation" it allows client developers to support it so that different clients can still communicate in this fashion.

-Eto

Thanks! I'm glad you've taken the time to understand it.


Correct. If addresses are more like public keys instead of their hashes then schemes like this become possible. One can do almost no cryptographically useful operations on a hashed public key.

Yes. There is an obvious implementation detail that would discourage A from sending to the "wrong" address of B which would also shave a few bytes from the size of the public key. Similar concerns would also discourage users from holding too many different active public keys as they provide essentially no additional anonymity and the computational burden increases linearly.

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.

The two parties can agree on some easily identified, optional OP_DROP tag for the transactions. Alternatively, the identification of transactions can be handed off to a trusted third party. Remember that full nodes have to verify all transactions anyway and it may be possible to arrange this scheme that one's own transactions can be identified with insignificant extra work as a side-effect of this verification.

The "difficulty" of recognizing transactions is inevitable if you want anonymity. In the current system, to have the same anonymity, each time you want a payment, you have to distribute a new address to your payer. To do this securely you really have to have a public key of theirs already. Some interested party could observe the exchange to compromise the anonymity. They might not know what the consequence of the interaction was but they know that you and your payer were communicating securely for some reason.


We'd try and avoid this by having B start with one key and by making it difficult for A to send to anything but B's intended key. I'm having trouble thinking of a good justification for having more than one key in a wallet under my scheme.

ByteCoin

Ack, that was pretty stupid -- B always has A's public key because it's in the TxIn script.  Just ignore the second half of my previous post

So B doesn't need to know anything about A in advance, and A only needs a public key of B.  Even if A picked any transaction he knew belonged to B, he could send him such a transaction, and B would eventually be able to find it if he scanned every transaction, trying all of his keys on each one looking for ones that match.  A would be wise to request a specific key from B before doing this the first time, otherwise it's going to be a lot of EC calculations for B to find such transactions to himself.  But it's still possible either way.

I really like this idea.  This makes any key in your wallet a generator of keys/addresses, the next one is generated by whoever is sending you money.  And people who know your public key can't identify it as belonging to you.  

My main problem with using this as the primary source of communication is that EC multiplies are expensive, and when transaction volume increases, you're going to be spending a lot of CPU time just scanning new transactions for whether one of them is yours.  At some point, it will take an average of more than 10 minutes to scan incoming transactions.  Then what?  And we will certainly hit that threshold a lot sooner with devices like Android apps: they will be draining the users' batteries just to check all incoming transactions!

Similarly, if B loses his wallet and has to recover from an initial set of keys, that's going to be a very long scan.  It gets longer as you receive more transactions, as you accumulate more addresses from which someone could've based another tx to you.  Still better than losing all your coins, though!

Bytecoin, this is great stuff.   The general idea of executing Diffie-Hellman using the existing public keys is pretty smart, and only works because the EC public key calculation is already one side of a Diffie-Hellman exchange.  I don't see an analogous procedure if we were using some other asymmetric op, such as RSA.

First of all, what is the point of using the TxInSig_r after the Diffie-Hellman calculation?  You already have a shared secret established at this point, which is GenPt*PrivKeyA*PrivKeyB (I'm using A for sender, B for recipient).  Why do you need to add the TxInSigA_r?  And why addition and not multiplication?

Why not just use the x-coordinate as the session key, and use PubKeyB*DH_Session_X as the target public key? Then B can redeem the funds using PrivKeyB*DH_Session_X as the private key, and I don't see any loss of security.

EDIT:  remainder of post edited out for being stupid

Yes you're quite right. Not a good solution. I was hoping you'd respond to this thread.

Your method of including the encrypted address as an OP_DROP parameter to the transaction would work but would take up quite a bit of room but that's the only particularly ugly part. It's a bit hyperbolic to say that it's like reimplementing PGP!

I believe the following scheme should sort address the problems you mentioned as it is indistinguishable from a normal transaction and there is a negligible possibility of address collisions or reuse.

The funder prepares a transaction crediting the redeemer and returning change to some other address.
This transaction has one or more TxIns and the scriptsig for the TxIn contains an ECDSA signature and a public key point
The funder does a Diffie-Helman key agreement using the secret key from the first TxIn and the redeemer's public key.
The funder then takes the x coordinate of the agreed key added to the r value from the first TxIn's ECDSA signature and computes that multiple of the redeemer's public key to get a session key.
The funder constructs the transaction as normal, sending the funds to the address formed from the hash of the session key.

So the funder sends to hash160(redeemer_public_key*(TxIn0_signature_r+x_coordinate(recipient_public_key * TxIn0_privatekey)))

The redeemer has to do two point multiplications to identify a transaction he can redeem. But that's comparable to verifying an average transaction anyway. There's likely to be a Shamir's trick variant to reduce the cost somewhat.

It may even be possible to pass a secure message to the recipient using the subchannel using a sophistication of the above idea....

ByteCoin

I agree with hashcoin's assessment. An investigator could collect public keys by agreeing to buy from people or pay them for some reason and/or by gaining access to an exchange, pool, or other service that pays people. These people then become easily trackable.

Warning, brainstorm below:

Would it not be better to randomize t instead of incrementing it? Instead you send the coins to h = hash160(concat(c, t)) where t is a large (256-bit?) random number. That way, it seems to me that even someone with public key couldn't determine if a given h was generated from a given c without knowing the t used. Although then again, I don't see how such a transaction could be redeemed by the receiver without some out-of-band communication of t. Maybe you could encrypt t to that public key and insert that into the transaction as well? This would let the receiver be able to see when he received the coins, but in order to prove ownership when spending the transaction, it seems like he'd have to reveal t, giving up the privacy. Maybe some form of non-interactive zero-knowledge proof could be used?

Is that at all useful/realistic?  The whole point of a public key is that everyone can know it.  The fact you need to deal with this "two people using same h" means others can tell which transactions were for you.  Noone should know that but you.

The correct way to do this has been discussed before: just send coins to a fresh address and then send the private key for that address securely to the recipient Out-of-band (e.g. via PGP email).  You could do it in-band in the blockchain, by including an encryption of the fresh private key with the recipients public key (the TX would not say who the message was for, so all you can tell is if it's for you by if you can decrypt it or not), but that is just basically implementing PGP email ontop of the blockchain, which is pretty ugly.  Also if only few people use this scheme, the latter method will stand out, while the former is indistinguishable from any other TX.  In other words, if 8 people in the world use a special method like yours, you have just made an investigators life 1000x easier, rather than harder.  That is why these things are best done out-of-band using networks like mixminion and TOR that already have large user pools.

A privacy preserving solution could work as follows.

All funders wanting to make payments to you know your public key c.
People looking at the block chain wishing to determine which transactions can be redeemed by you (investigators) do not know the key.
When a funder constructs a transaction to you he generates hashes h=hash160(c*x_coordinate(c*t)) for t=0,1,2,3.... and checks all transactions to find the first h which has not been used before.
He then constructs the transaction with h being the address.

This is effectively a deterministic wallet that resides in the funder's client software.

One problem would be if two people sent a transaction at the same time with the same h. This is solvable with a high probability with an OP_DROP parameter to the transaction.

I believe that if this were implemented in the default client then there would be no need for deterministic wallets, key pools or the distribution of new addresses for each transaction.

ByteCoin