Topic: CoinJoin: Bitcoin privacy for the real world - page 37. (Read 294649 times)

Wow, that was unexpectedly fast.

Hi,

I am claiming the bounty.

More info: https://bitcointalksearch.org/topic/anonymous-bitcoin-transactions-with-coinjoin-282086

Source code: https://github.com/calafou/coinjoin

The risk of DoS in many of these cases could make the entire scheme unusable for as long as it's decentralized, as you can't really effectively ban the attacker. If the attacker can run 20x as many fake nodes as there are real nodes and abuse the scheme to only spend a trivial amount of computing power and bandwidth, while making the real users waste lots of it, then the system is trivially rendered unusable. Just throw a botnet at it and it's dead.

That's why I'm thinking hard on DoS prevention.

Edit: Also, regarding change addresses: You should split up your change in several parts. If everybody does that and thus generally also refers to multiple inputs for the transaction as a result, then correlation based on the BTC sums is much harder.

Edit: https://bitcointalksearch.org/topic/m.315793 - So somebody else had the same basic idea over 2 years ago. Although my version (who originally was almost identical to his) now accounts for various types of possible attacks.

Dos attacks on systems which don't require flag day updates are categorically different from cryptographic breaks. I fear the approach you are advocating would result in us getting nothing at all. (but, I certainly would welcome it if someone wanted to actually work on it!)

It isn't certain that you'd be able to tell WHICH input that the attacker used, at least not with my scheme where you hide who's using what input. Revealing who's using what input might not be optimal if a user want to use inputs already tied to himself AND some inputs that aren't already, and doesn't want the unlinked ones to become linked to him.

Also, it's hard to convince other that the attacker maliciously broke the scheme where none of the participants has any long-term pseudonym, thus it's hard to blacklist that one input. Also, a single input can STILL be used many times simultaneously, even if not many times in a row.

I don't have enough experience with programming, and absolutely not of crypto implementations, to be able to make a proper proof-of-concept of this, sorry. I'm hoping that somebody else *who does* will find this interesting enough to implement.

So far I'm thinking that my two-round version SMPC scheme with initial PoW before starting SMPC would be pretty decent, where you'd remember which pseudonyms that mixing has worked with in the past. Participants that don't supply PoW is ignored, and to stop a sybil attack where many nodes don't do PoW to try to make you calculate PoW for nothing you'd connect to multiple dozens of random nodes at once.
Edit: If the SMPC was given bad inputs, it would also reveal who it was that gave it the bad inputs (if it were to finish, but giving bad inputs + interupting the SMPC is just wasteful from an attacker's point of view).

And by the way, I'm one of those who wants the system to be as solid as possible in advance. Nobody deploys bad encryption algorithms and try to patch the algorithm as flaws is found. Not that I think that the other suggestions is bad, but I don't want people to get screwed over because somebody forgot to consider a simple attack that a little bit more analysis would have revealed and maybe shown how to stop.

You're missing my point.  If you detect them disrupting the protocol the participants blacklist that input and never participate with it again (ideally the protocol would be such that they got proof of the disruption that they could show to others). But since success consumes the input you don't have a problem with long term identity linking. Yes, simultaneous is a possible but even in the worst case a given input could only be used to jam each group of users once. If recovering from a jamming is just a few packet round trip times and signature operations to redo the mix, this isn't so bad.

In any case, I've probably given you enough of my thoughts on this. Go out and code. Practice trumps theory.  As I said in my initial post, I suspect that it might be better to just start out with very weak dos protection and then adapt to the actual threats rather than trying to predict all possible threats in advance. Unlike a global consensus system there is no great harm in evolving this technology.

Ok, so coin age would be your DoS countermeasure?

Note that attackers don't actually have to spend that input if they disrupt the protocol. They can use the same one over and over, even many times simultaneously.

PoW could be an option where participants can set a minimum PoW accepted and a maximum PoW they're themselves willing to perform. So for example if 10 people all have 2^15 work within their range of acceptable PoW (one has 2^15 as their lowest, another as their highest, they'll all generate a common input for PoW and start working on it. Then they start this scheme with the SMPC. That would indeed make the attack costly for somebody trying to break the scheme for as many as possible (DoS) and would make Sybil very costly.

You don't reuse your inputs if the transaction completes successfully. Basically having an available (potentially aged) input of sufficient size that has not been used to jam the mix is a scarce resource that would limit attackers. The network already rate-limits people's ability to create new outputs as part of its own dos protection. This isn't the greatest anti-DoS possible, though you could add PoW to it too if you wanted, but in the lightweight schemes the harm of jamming the mix is very low, so the protection doesn't have to be especially great.

I don't see how that would help countering DoS, you won't likely be reusing inputs so there can't be reputation tracking.


It was a bit more than that IIRC. It was highest bid wins, with winner paying the price set by the second highest bid, and it was NOT just two or three participants, it was a LARGE auction. A very large amount of offered goods and bids.

Besides for risk of sybil+correlation attacks (which can be partially countered through reputation tracking), I like my SMPC scheme.

Ah okay, yes the anti-dos pseudonym tracking is why I had suggested the method of using the input coin itself as the identity.

A specialized for doing a meet in the middle auction (e.g. a few comparison operations and an arithmetic average) is a whole other of magnitude less complex than running a complete transaction processing program in it. Going and figuring out where the state of the art is in that space has been on my todo list.

Every participants has a key for a homomorphic encryption scheme (which can be decrypted or encrypted in arbitrary order). Each party encrypts their signature with everyones key, the signatures are grouped up and passed around, with each peer permuting their order and applying a re-encryption operation. At the end they all decrypt in sequence and you get a mixed output. The downside is that people can silently jam the mix by replacing or corrupting data during reencryption. To prevent this you need to do cut and choose (e.g. mix 10000 times, commit to all of them, one gets picked as the real mix output and you reveal the rest) and that takes a lot of bandwidth.

As an aside— I hope the cryptowizardy for the decenteralized versions of this aren't scaring people off. Part of the merit of CoinJoin as an idea is that there are braindead simple ways of using these ideas that don't require cryptomagic and are only somewhat compromised compared to what you can do with maximal magic.  I personally find the magic very exciting, but I find actual systems that people can use even _more_ exciting.  I hope people will work at this space from both ends.

gmaxwell: Yes, in the last part of that comment, that's what I suggested.

If a pseudonym is reused often, then correlation could be used to link all inputs with the pseudonym that provided them. This could the be further used to see if outputs from mixed transactions that the pseudonym in question has been part in often has some outputs in common, thus deanonymizing users who use this frequently for the same outputs (assuming the recipient has repeating or non-individual payment/donation addresses, which is common).

I've read that SMPC has been used IRL successfully for auctions for farms selling their goods. Can't remember the source. SMPC should be possible to run on most hardware. There's multiple implementations of it, some in Java and some in C.

How would a homomorphic mix work?

Two-round SMPC could certainly work, where the inputs simply are the individual signatures plus the previously unsigned transaction, creating a properly signed transaction.

Edit: SMPC implementations:
FairplayMP: http://www.cs.huji.ac.il/project/Fairplay/
Sepia: http://www.sepia.ee.ethz.ch/
Viff: http://viff.dk/
SIMAP (nothing available for download?): http://ny.alexandra.dk/uk/labs/Security-lab/Pages/Secure-Multiparty-Computation.aspx

I don't see any reason to hand your private key over to the SMPC, the point of this thread is that our transaction design is already such that users can separately sign a transaction. You could use SMPC to build the transaction to sign, and then everyone signs.  This would be less brittle, e.g. sybils don't get your private key they can only jam the process or get a user unfairly banned. OH you say that at the end.

I don't follow why you think you need signature privacy at the end? You could use a homorphic mix, or just use SMPC to do the combine (e.g. two phases)... but the signatures only show ownership of an input, and the input side is normally not considered as private.

I'm not aware of any general production scale implementations of SMPC, it would be very exciting for a lot of things— are you aware of any system that could be realistically tasked with signing bitcoin transactions with commodity hardware separated by consumer internet connections?

What about putting it somewhere on the OP top and adding a tldr?

CoinJoin - Improving Bitcoin Privacy using Shared Transactions

Will spin it on http://blockchained.com

I have one suggestion that among others uses Secure Multiparty Computation (SMPC). https://en.wikipedia.org/wiki/Secure_multi-party_computation

Step one: Peer finding is done using a DHT network. This can be done inside I2P or Tor if you want to for increased anonymity. You might want to do reputation tracking where nodes uses public-key based pseudonyms (if you reuse a pseudonym, you must make sure to not spend inputs that can be tied to you personally more than just once (or rather not more often than the average, some identifiable inputs might by chance be involved with the same 3rd party multiple times) with that pseudonym since it otherwise can be directly correlated with your pseudonym).

To make verification of inputs simple and quick, each client keeps an updated Merkle tree hash of all currently valid spendable outputs in the blockchain (basically those that not have been spent yet) in this form: [Address]-[Transaction ID]-[Amount of BTC].

The SMPC uses cryptography to emulate a trusted 3rd party computer, running code all participants have agreed on. Unless a majority of the participants collude (Sybil attacks are a potential issue, be careful about who you run this with), no participant can get any other information out of it than they are *supposed* to get out of it.

Now, everybody puts in their transactions and their private keys for them. The SMPC checks if all participants really have the correct private keys for the (valid) previous outputs they claim as inputs through checking what addresses they correspond to, what transaction ID was claimed and how many bitcoins are claimed, and checks this data against the Merkle hash tree.

It then checks that the outputs aren't larger than the inputs. A transaction is then generated with all the user provided inputs and outputs, and signs it with all the private keys.

The signed transaction is given as an output to all the participants, and any one of them can publish it (or all of them at once).

Nobody can know which transactions came from whom, other than that they know their own. Out comes a signed Bitcoin transaction that includes them all in one. Either everything gets signed properly or it exits with an error. The protocol doesn't allow the generated transaction to be created in any other way than the correct way. All user specified outputs will be included, all user specified inputs will be included, no user can specify larger outputs than inputs (unless everybody agrees), etc...

The only major risk here is that of a Sybil attack (a large number of colluding nodes), and the major risk in here is private-key disclosure, the second is identifying which pseudonym spent what input. I hope that we can get around that somehow. One possible way is to not have the private keys provided to the SMPC, but to use simply prove you have the private key through signing a challenge of some sort, where the challenge can be a random number that is a checksum of all random numbers provided as inputs by the participants, so you only need one signature per participant. The SMPC would then only output an unsigned transaction, where all participants needs to sign it. The question then is how they all share their signatures with the other participants, ideally they should be able to hide that it came from them. Chaumian blinding could maybe be used in this step.

If you decide to not use blinding (to just pass on your signature), and not use any permanent pseudonym of any kind, then you'll have a risk of DoS attempts through both doublespend attempts (making the generated transaction invalid) and through canceled SMPC runs at the last step (thus wasting CPU power).

My intent is to make the system as automatable and fast as possible while maintaining full security.

It has the nice feature as a leading application that it would be harder to shut down as it is charitable.

Another potentially useful idea I had in this space is CoinJoin software for doing matching charitable contributions.

E.g. you announce "I'll pay ~1 BTC to the EFF if 10 other people do too" and form a joint transaction with a single output. This may be fun, socially beneficial, and improve user privacy because even 1 TX output transactions couldn't be assumed to reveal common ownership of the input keys. Likewise, common donation outputs could be used to receive jagged change ediges in other kinds of join transactions which would otherwise be data revealing.

The bounty address is now up and already has 12.19262795 BTC assigned to it.

That is if there is no cost to having multiplexed transactions, unlimited number of public keys, and the delays and limited time windows of CoinJoin or the blockchain + hash check bloat of Zerocoin. I am also thinking of a Visa-scalable block chain. Your naive users will never be using Bitcoin any way, because the blockchain can't scale. By making CoinJoin popular, you will have further cemented Bitcoin's inability to modify the block chain design in this respect (although there may be a way to scale the block chain with multiplexed transactions and unlimited public keys, I am still studying this).

If there is no cost, I am not against it. I am arguing it is lower priority, not that it isn't worth considering if it fits into the big picture goals.

If we aren't concerned about the bogeyman who can see everyone's IP address or deposit viruses on our machine, then employing a high-latency Chaum mix-net with a standalone machine (e.g. Rasberry PI running L4 Linux) isn't that crucial. Then the only way users reveal their identity is by:

1. Explicitly giving it to the recipient.

2. Using the same browser for both entering their spending public key and browsing the internet, e.g. Google's cookies.

3. Use Windows 8

Did I miss any?

If we are concerned about more sophisticated harvesting of identity (which I am, because of Anonymity or Regulation and more), then with a high-latency Chaum mix-net built in for all incoming transactions, the above two pitfalls still apply.

And even with CoinJoin or Zerocoin, the above three pitfalls still apply.

I still don't see how CoinJoin or Zerocoin practically gain the naive user anything. Either the user stops giving up their identity by not doing the above three items, or they don't.

I understand the concept that IF users only give up their identity by mistake infrequently, thus delinking the block chain can in theory recover from such user error. However, I think users do what they do habitually.

P.S. CoinWitness is interesting because it can move the multiplexing of transactions off the blockchain, so then people employing decentralized mixing don't burden the block chain design. However, if a future design limits public keys, still need to support in the blockchain some way to retire and regenerate public keys for those coming out the other side of the offline mixer. (EDIT: note that last sentence might not be true, if the output can pay to existing key which is not yourself.)


So why not have a separate individual BTC pool of capital for those purposes where you explicitly want to be public? Else send him a paypal to his email address. (Personally I wouldn't be announcing publicly my ownership of Bitcoin, because I think the governments are going to demand capital gains taxes in arrears, when they declare it isn't money rather a good like gold).

You are conflating use cases of BTC, just because you want it to be more convenient in one way, yet you potentially make it less capable in another way (for someone who is considering any possible blockchain design for the future) by choosing that convenience over other considerations.

We have to be sophisticated in our analysis of tradeoffs.

Edit: donating more

I may be jumping the gun a bit, but please accept this 10.11BTC donation to the fund:


-----BEGIN PGP MESSAGE-----
Version: GnuPG v1.4.11 (GNU/Linux)

hQIOAwAAAAAAAAAAEAgAhYb+uVMQsS/LBxtWH3PKcfQkpBhbygfrRLtaZn4DSPGP
F12rmQQ8QRJOiRyKgrXrwXWoLZ4cFA9q2VabhyiYLWo/NO+pdP+h/XnHteTmjvTI
rRwZjMtXntGZO2Awh+BpsKlUyfnDpCuPbkZGT82/iubUWhTrbQAPseEISVArP9Jd
SvPVnw2cHQnvBu9aU6+qzf7rmYox2dMYPHkAtRLtAYO5WU087dhGWoNW0S7E6pNG
P8NkYYg18YJA7wHZ9raBf6QzhhEJY4ppuIIe6P60CzxsU+acswPA3yFKjzPXaMQv
ZeglXsOC/jWX36s/f7Q03ICPg2wEguJiMrKPDew9fwf/eX+or4F1QLJWX7e2bPbS
hMsI+H/EjV9iuNoRmYmWQq+Q+aP6RZC6SwESXEgp0lqr3poLO0za7mYuxiiZg2IQ
1255u2yVz0ikdGv1VKr2tyEZLitARID3YVetEWdTIm/rlHsKV7stF6zh+fnVIHjx
jkmaKa4G8dGGOhDt2xLsgfB6oJ9iuDJHSDL9nXU3aanTPc7E8NFhUHrxBW+CWu6E
wo7xlnfjYrSYFTjrhVqm0ywbWmpyTdhb54w7AroOjeTU7axgcbNV4b59v0H8HSx2
EGlDnSf4wKWPX28c9r/aXevd5Jt2GQtwI48noqKNC4ryPVgZF65FpaRy7Z0E9s21
CIUBDAMAAAAAAAAAAAEH/0QxCBCEp8x+QwA1WwvyD4/f4OW8LAjKO2idR9NNJFx0
yLK0ohtX5nGryZujvAwvZmG1Haanj9QFQ26Xxpe4NINGee3EZ/kBMIxDWQ7vqXmx
yvU+g6W8lhwWO4Fs9mX5yrt/KnYL2AS5e4A3ZKXiJzLvd+fQ26NuuO9UTeHvB4fv
DaivRxV+Jytfym875cob+q4BvjklqjW4QSKMLMZbHXUgYlqmEWbVdIqOMoa/11nA
c9vYWzMBv4+dzX1QNILtAjH57zac2axowKDanZ0zCmp0WyZu3ZzDRP3/SIIilCKr
TrKxTeRzgJssOacxahH9qSFxYlWbtZ61mZJmU8Ny7HaFAQwDAAAAAAAAAAABB/9D
krpjhcyVrDTq/6b8QiCxznCiv8GvMLQEs4amVStGXYY8YnwuTqcOpzrMno0/FQp/
atkMc8mR1LoeWd182YRvnRRDqBM3Iz8OsEPOM2Pnjgi/ZTrKkncWMOiZALjH2vLT
JKCJa62ou08cDL6Y+sX9SHQOpxG3kG1/QcKaaqwpbQLLm6lz4TxF1+c/Mjd9Zukq
3qq9h2v7gwbc6KJXsq3ZbXp5prNgAhtoJPRIv+kcxnfEwO0hpGnyoJ1xb16YsqMN
L6JmmHKJhi60B6t4S8TWvth7piVfce1d6izDpXQJ2gmkNS/mah3rw/jpeCdHgeQd
PnqaSkj5Nmqa98rbYQyo0ukBYW9cHSZONbFqT994oSU/7C+8GVFPXet+gxbja9nB
kaWwi1PL7ngSSrYbchzrREmLxNY3RALVwcjWyPrc7Dax+G+vfVw+dANzxQtt0a22
J6hFVBAp70XvNM9YCg1CkAIqnyd+Y8bYmgAcAkNOovg2KZh0wWmziAEP/FizNbZm
xpWd4TXzTKNae3usoJxjBGUS6DAk26fZFkvczqEDJBW3GCPHYcupIa9k9FECnIaF
Wp/YodreY3bzFWidJpFZtpvt4qLz/PovxhZoR/9nqBjwsCJSEXtx7VcuPjKKWCRx
7miDE/xzKS8QIKV8/BZjcNf0S6H/BwxnGyzLTVSpukPvqy8B/RxUO+nf4RFSNpNT
jp+0tlILpncwzTDL2h6FF/jtj+nl4cTT23ZazbkuYAlxnwMxU+GU6jtQZLHAoYdo
n9TjMNDZZCRN5spMWu1UWnKqQ1Gc43q0vUJ+s5KWj2T3lOoYoSsNYrAQmPoilsLH
3Lh0Lg4sPVoG1DwwKXOVrkJF34utSlCFl63h/PMFXmjRgcueb0Ta6POU4njGg8VY
sEKc0bux7+lK0bMgoQA3O/quxHsK0Q3uQVWmNtTjqU2uf/sE3mz5twTGU8bDOWYu
88PuGBANtQHkNR1Cz1yHnPug5tI8NXYsC3PNKnu9DmI9y4TBK6qFSfJm8cZVbfLS
AcD7vvQgizaMTNi8FW4/NfKi0tNLE8foZgV1m6pXgYr4pzfWhWdcJUZ7ClV41Vzl
RDayvveBOWy/w68eUc8/5nWmH6+phmwtpjFWuht/OIGY1Oo91LoO0h+CgMKf5kur
zCBa72DTZfVpaDzwaRcr8tcP60u77PYrL8NMw6LP9q7760bbij+DJ274tWlmJnsM
9q/ZhVXm7bW5m1gXIGO7Hl4Dce9S3ImxxzCogcwP0VaZP4IZPNCmmK8xkmIiAKDV
Rr8mKh00KtaP0tby06IOuRr5bo2XbMo0knEwsdVHyM/yocAfPMbfPlJlao5ZI/XA
xV5db7pETa08sjKoYGHyjvJnclQ9P0yFy8jK/b8LoFAej/bVGQwdckIsBIEUg28F
C1tOskPkd7B4fiL4tGqfEkI7msvGYgH366kI63osglOcaYTj4BzvufkqSO4LwgLK
yzZlmyVfx+PaJzoL1F+IGUAmD9E4Fz5dporFHGW2elAtIh8MEywyZyPWvr1kJ5Q8
iEe3CHLM0X834PwLQ7snKzuoCulRvQnuiwfqVqASTwwjR05XpzhcalWAkhSPgRG/
rj1GXIngmSEO/hiFSOE=
=AaHO
-----END PGP MESSAGE-----

What I most like about this concept is its simple engineering pragmatism. You know, ZeroCoin solves exactly one problem really well, but it solves it so well because they pushed the envelope so far in one particular direction. From an academic point of view it makes for great papers and clever theory, but the history of cryptography is littered with empty and disused ivory towers, and in any case often those towers lack railings.

I have to wonder how many of the people pushing ZeroCoin so hard even recognize that it needs a mix net or a standard way of getting your transactions to those you are paying to be useful?

AnonyMint: You come so close to being pragmatic in how you recognize the need for mixers for communication. But then you miss so badly, like it or not, normal users will make mistakes that reveal their identity, and CoinJoin can help make those mistakes less devastating. In any case it is usually not the boogeyman of three-letter-agencies who the users of CoinJoin would be trying to protect themselves from, but individuals and businesses who simply want to use Bitcoin with the same level of financial privacy they enjoy in with the convention banking system.

Look at the above. I am happy to have the world know I am giving 5BTC to this effort, and I am happy for Gregory Maxwell to know that it is me where the money is coming from. But why should I give the whole world insight into my finances? With CoinJoin I won't have to use something as convoluted as encrypting an access key, and the proposals above share a common thread of being such that all the actual complexity can be hidden away in software with a sufficiently sophisticated implementation.

Check my logic. I don't see the point.

As I understand the problem-to-solve is that if someone reveals your identity for any transaction then any other spends from the same public key are associated with your identity and any spends (inputs) from other public keys to the same transactions as the identified public key are with high-likelihood associated with your identity.

The CoinJoin solution is dual pronged in that if a greater percentage of blockchain transactions are inputs from multiple parties, then the high-likelihood case is reduced in likelihood for all users of the blockchain that don't use CoinJoin. The second prong is the mixing of parties for a transaction using CoinJoin protects the identity of the public keys for the parties spending using CoinJoin.

Note the first prong is an improvement even when someone reveals your identity for all the input public keys of a transaction, because you may use one of those public keys later with other uncompromised public keys in other transactions that were not revealed.

However, CoinJoin is unnecessary if no one ever knows your identity.

If you must provide your identity, then why are you using Bitcoin and not your credit card, cash, money order, paypal, etc?

I suppose there are rare cases where you want to give your identity to someone trusted but not the identity of the merchant to your bank. But that hardly seems like a compelling use case to justify such convoluted systems as proposed for CoinJoin. Credit card numbers can be stolen but in the relatively rare event, most of the time your issuer will remove any unauthorized charges. If identity theft is your concern, then again why are you providing your identity.

And against the NSA and the government, plausible deniability is not a defense (btw jim is James A Donald, first person ever publicly recorded as interacting with Satoshi). So if they know your IP then they can compel you to unmix all the mixing stages.

Thus, I view zerocoin and CoinJoin as a lower priority than a high-latency Chaum mix-net (or dc-net), which we don't have available today.

If you are littering your identity all over the web, then nothing is going to help you.