Blind signatures for bitcoin transaction anonymity, by Watson Ladd

[EhVedadoOAnonimato]

Recently I found this paper: http://wbl.github.com/bitcoinanon.pdf

I read it once, and realize it's just too much to me. Satoshi's paper I could grasp, this one talks about things I've never heard of.
I imagine I could spend days or weeks trying to dig through the references, studying them and finally understand what Mr. Ladd is proposing. But well, I'm not a cryptographer, I have my ordinary job to watch for, and I guess I'm just too lazy for that.

Has anyone here with deep cryptography knowledge understood the paper? Could you eventually explain what is he proposing and how could that eliminate traceability in bitcoin transactions, with simple analogies that a mere mortal like me would understand?

I mean, I do understand the principles of symmetric and asymmetric cryptography, and I believe I do understand the basic of blinded signature (you sign an encrypted piece of data and in the same shot you also sign its unencrypted form, without knowing it). But I just can't understand what the hell Alice is doing with all those B-named men in the paper.....

[Ente]

/watching

Ente

[DeathAndTaxes]

My attempt at a layman's explanation/analogy.  The first thing to understand is it improves anonymity it doesn't create perfect anonymity.

Explanation:
Alice wants to pay 5 BTC to 10 people.  The people she is paying don't want their identities to be linked to their addresses.  A special script is created (not possible under current Bitcoin "rules") which pays in 50 BTC and allows 10 "withdrawals" by pushing an address to the blockchain.  The address isn't recorded in the script so Alice doesn't know what the eventual payment addresses will be or which address corresponds to which person.  

So Alice can only set this SET of 10 addresses corresponds to this set of 10 people.  While the paper doesn't cover it there likely are few instances where Alice and B-named men are direct entities.  Rather the most likely implementation is that Alice is a coin washing service.  It combines multiple inputs and issues same sized outputs thus preventing double spends or coin generation but at the same time breaking the link between a distinct input and a distinct output.

A Real World Analogy:
Alice owes 10 people $20 each.  The people don't want to be paid directly because Alice could link the serial # on the $20 bill to their identity.  The 10 creditors have Alice create a set of instructions for a bank and 10 hashes of secret keys.  Alice deposits the $200 and instructions with the bank. The bank destroys the $200 and has $200 in new bills minted. Individually and anonymously the 10 creditors each go to the bank provide their secret key (which bank verifies) and they get their $20 bill.  The bank records the serial # of the new bills given to the 10 creditors and Alice likely will learn this she can however never know which creditor got which bill.  She only knows "this set of 10 serials #s collectively was given to this set of 10 creditors".

[EhVedadoOAnonimato]

A special script is created (not possible under current Bitcoin "rules") which pays in 50 BTC and allows 10 "withdrawals" by pushing an address to the blockchain.
....
The bank destroys the $200 and has $200 in new bills minted. Individually and anonymously the 10 creditors each go to the bank provide their secret key (which bank verifies) and they get their $20 bill.  The bank records the serial # of the new bills given to the 10 creditors and Alice likely will learn this she can however never know which creditor got which bill.  She only knows "this set of 10 serials #s collectively was given to this set of 10 creditors".

Thank you Death&Taxes.

But, if during the withdraw an address is pushed, won't this address get publicly linked to Alice's address?

I don't understand how the "the bank destroys the $200 and has $200 in new bills minted" part works in bitcoin. Who's the bank? How can this data be destroyed while still preserving the blockchain integrity? Wouldn't the verification the bank does on the secret keys in your example had to be done publicly in the chain?

[DeathAndTaxes]

Looks like my analogy hurt more than it helped.
The bank is the blockchain.
The secret key is the signature of the address of the recipient.
There is nothing "destroyed" but the blockchain won't be linking a specific input to a specific output so for all intents and purposes it is like the old bills being destroyed and new bills being created.  The blockchain is merely making sure 200 input matches 200 output just like the bank would make sure $200 in new bills matches $200 in old bills.

To answer your larger question the entire tx WILL be linked to Alice input address that is why I said it isn't perfect anonymity but it does improve on the current implementation.

Currently: this specific and distinct input is linked to this specific and distinct output

As proposed: this set of inputs are loosely and collectively linked to this set of outputs.

So while you can say Alice paid this 10 addresses, even Alice doesn't know which address belongs to which person paid.  So if say the Police questioned Alice she could say "oh in that tx I paid Bob, Bill, Buddy ... 7 other people" but she couldn't say Address 1234 belongs to Bob.  

Now if the Police gained access to Bob's wallet they could reverse engineer the tx and prove "beyond a reasonable doubt" that Alice paid bob (and 9 other people) as part of that tx.  So bob needs to keep his wallet secure and careful how/where he uses that output in future txs. Also if the other 9 conspired they could determine the identity of Bob.

[EhVedadoOAnonimato]

It WILL be linked to Alice input address that is why I said it isn't perfect anonymity.

 
So, traceability is still there. No major improvement on that area so far....

As proposed:
this set of inputs are loosely linked to this set of outputs.

Hum, doesn't that already happen when one makes a send-many transaction? I supposed you used the word "loosely" to mean something particular....

Alice could say "oh in that tx I paid Bob, Bill, Buddy ... 7 other people" but she couldn't say Address 1234 belongs to Bob.

Is that it? In a send-many, the sender normally knows the address of each receipt. That's the improvement to the current situation?

[DeathAndTaxes]

It WILL be linked to Alice input address that is why I said it isn't perfect anonymity.

 
So, traceability is still there. No major improvement on that area so far...

Well traceability is improved but it isn't untraceable.  Bitcoin simply can't be untraceable.  Preventing double spend requires identifying the prior tx and ensuring that no equivalent tx already exists.

That being said nothing is untraceable.  If the US govt wanted to could they could require ID with every cash tx and install serial # readers at every merchant.  With a swipe of the ID, and a scan of the bills (in and out) one could build a map of every dollar and exactly where it went, by whom, and when.

Making inputs and outputs loosely coupled makes using that tracing more difficult and makes coin laundry services more comprehensive.

As proposed:
this set of inputs are loosely linked to this set of outputs.

Hum, doesn't that already happen when one makes a send-many transaction? I supposed you used the word "loosely" to mean something particular....

Loosely in the fact that the ownership of the output is semi-unknown.  the address can still be traced though.

[DeathAndTaxes]

I put this in a separate post because it is semi off-topic.

Perfect anonymity is most likely impossible given the constraints of digital systems.  The only place perfect anonymity would exist is where the currency is perfectly fungible, can be accurately verified.  Only then is it possible to transact safely without records.   An example would be identical physical coins with no deviation (dates, variations, serial #s, etc) where all coins in circulation are in perfect condition and all can be accurately and instantly evaluated as authentic.   Such a system probably is impossible without nanotechnology and probably would involve exotic material.  You could use synthetic isotopes which can't be created without significant cost (think physical hashing) and which can be identified by unique (low level) radioactive signature.  


Outside of that anonymity can only be improved it can't ever be perfect.  Adding significant anonymity to the current protocol is hindered by the block chain design.  Futher anonymity likely requires a new design for recording txs.

For example imagine the blockchain separated "sends" from "redeems" in a double blind system.  Sends would go into one block and then they would be redeemed in another block.  This would have other useful implications.  Sends could have an expiration date in blocks.  If the coins were sent to an invalid address or the recipient has lost the private key it would never be redeemed and the tx would be canceled.  

Now if signing of blocks was done as it is now anonymity would be improved BUT there would be significant limits.  The boundary of the improved anonymity is the tx boundry.  While the outputs are double blind one can still link an input to a set of outputs.

Now imagine instead of sending tx directly to miners there was an interim party.  Entities on the network called aggregators.   One would be splitting the role of tx processing, collecting and block signing.  Major pools likely would also be their own aggregator but that wouldn't be a requirement.

Instead of sending the signed tx to an aggregator your node would send just the inputs and the double-blind outputs.  The aggregator would take your input and the inputs of dozens or hundreds of others and create a single mult-sig tx, send it back to all participants to sign and then broadcast the "unified tx" to the network.   Thus the rest of the network only sees the unified tx (imagine a block where all the tx are combined).

Even here we don't have perfect anonymity.  The aggegator knows the inidividual "pieces".  That entity could break your trust.  This is similar to a VPN provider.  While your ISP doesn't know what you are doing the VPN provider does and if they decide to break your trust they have a complete log of your activities.  Still if one chooses the aggregator wisely the # of entities which know the "secrets" is limited.


Summary:
Current Protocol - very distinct link between inputs, output, and identity
Paper's proposal - improvement because identity is obfuscated from output, scope is limited because it is a "special" (and thus likely not often used) tx.
Blockchain based on "double blind" - tx you are looking to "hide" blends in because all tx are double blind.  the ambiguity is limited to tx boundry
Adding aggregators - allows creation of unified txs (either by miner or by trusted third party).  Anonymity significantly improved because scope of those who know the "secret" it limited.
...
?
...
?
...
Perfect anonymity

can it be taken further?  maybe.  It might be possible to involve 2 or more aggregators so that neither one can reconstruct the tx on their own.  This would require collusion between multiple trusted parties.   Some might not like the idea of trusted parties but the trust would be optional.  The only thing you are trusting is they won't share the tx components.  If they did it would be no worse than now (when every node knows every component of every tx).  Parties who don't care could send tx to all nodes for aggregation.  Parties who do care could be selective in which nodes they communicate with.

[Ente]

Thank you DnT, very informative as always!

So, the current option to use a cointumbler (everyone sends bitcoin there, bitcoin are mixed, everyone gets random bitcoin back) isn't that far from the (bitcoin-possible) optimum, and the proposal in the paper would not add significant anonymity, if any..?
Basically, the part about aggregators reads almost the same as instawallet to me.

Ente

[DeathAndTaxes]

"cointumbler" type services are too limited IMHO to provide much real anonymity.  You also need to trust them.  You need to trust they won't steal your coins or give your info to law enforcement.  You need to hope they have enough "legit" volume to blend the tx (and who sends legit coins to a mixing service?) Multi-sig and double blind are part of the "solution".

As far as aggregators being like instawallet I think I was unclear.  With instawallet you have no control over your private key and most tx don't go through instawallet.  Instawallet still relies on the blockchain and current broadcast to all method of propogating txs.  Instawallet knows your inputs and output and broadcasts those details to the entire network.

When I am talking about aggregators I am talking about a fundamental change in how tx are processed.  All nodes would have the capability to aggregate tx (possibly for a fee), handle the multi-party signing and broadcast the unified tx for inclusion in a block.  Most likely wouldn't and instead would just pass tx components, unified tx, and blocks around the network.    Since all tx would be processed this way double-blind tx wouldn't show up as "special".  The tx one was looking to keep "secret" would be in a sea of other tx and "unified" with dozens of unrelated tx components.  You may ask why not just have the miner (and by extension pool) handle this.  They most likely would but some may want to have a different party handle the aggregation.

Psuedo communicaiton code would be something like this:

Sender 1 -> Aggregator (tx components:  list of inputs, double blind outputs, and fee designated for aggregator)
Sender 2 -> Aggregator (tx components:  list of inputs, double blind outputs, and fee designated for aggregator)
...
Sender n -> Aggregator (tx components:  list of inputs, double blind outputs, and fee designated for aggregator)

Aggregator combines all inputs and outputs, adds an output for its fee.

Aggregator -> Sender 1 (unsigned unified tx)
Sender 1 verifies and signs
Sender 1 -> Aggregator (signed unified tx)

Aggregator -> Sender 2 (unified tx signed by sender 1)
Sender 2 verifies and signs
Sender 2 -> Aggregator (unified tx signed by sender 1 & 2)

...
Sender n -> Aggregator (unified tx signed by all parties)

Aggegator -> Entire network (signed unified tx)

[DeathAndTaxes]

For the record I am not advocating building such a system.  I am just pointing out some ideas that could improve anonymity of crypto currencies in general.  Bitcoin likely can't be improved much because anonymity must be handled at a fundamental level.

Hopefully Bitcoin will remain viable despite its limits on fungibility and the the never ending ambitions of the taint zealouts to destroy that fungibility.

If it does fail then such discussions will be less academic as I would hope crypto 2.0 would seek to expand on Bitcoins limitations.

[Explodicle]

IIRC Open Transactions features anonymous digital cash using blinded signatures. The catch is that the blinded signing has to be performed by an entity (the server) trusted by all involved parties. However, this blind signer doesn't need to know who is sending what to whom - you can operate "cash only" without so much as a pseudonym.

Bitcoins COULD still be tracked based on the size of inputs/outputs (like any other mixing service) but you could manually control the mixing process yourself.

Don't take my word for it, though... Most of what I've discovered so far is how much I have left to learn.

[EhVedadoOAnonimato]

It seems I had accidentally locked this topic, sorry!

Death&Taxes, thanks again for the posts.

OT-cash-only system is already "perfect anonymity" to me... not even the server can trace the transaction. That's practically as anonymous as a physical cash transactions. But I have the impression such level of anonymity is impossible to be implemented in "full p2p". Maybe one day the geniality of a "new Satoshi" will surprise us...