Topic: RFC: Bitcoin Mixnet (Read 11789 times)

I'd like to mention that the following scheme provides perfect anonymity without extra transactions.

https://bitcointalksearch.org/topic/untraceable-transactions-which-can-contain-a-secure-message-are-inevitable-5965

One would also not need to generate and distribute new receiving addresses for each transaction.

ByteCoin

In case anyone is interested, here's what I have so far: http://www.flamewars.org/~phil/btcexchanger.git

This is incomplete. I'd hoped to finish the reference implementation and set up a test node before making this available but I've run out of time/energy for now. In fact I haven't worked on this since mid March.

The RPC mechanism and a basic web interface are working, but the backend which actually causes the Bitcoin transactions to take place is missing. I was thinking about using two separate bitcoin daemons with independent wallets for each transaction, to guarantee that the transaction history for the sent coins is isolated from that of the received coins. There should be a way to do that within a single daemon but I doubt that functionality is implemented currently.

Thoughts (and patches ) are welcome.

There's a difference between currencies and legal tender. The USG doesn't care whether or not you can pay your taxes with a particular currency. See:

http://www.securityfocus.com/news/11528

Yes, I'm not really objecting to anything in your paper per se, just saying that I don't think there'll be many independent mixing services and that it'd be better, at least in the short/medium term, to have one big node than a network of smaller nodes. It'd allow you to anonymize more coins and that one big node would be easier to trust, either because of an investment in remote attestation technology, or because of reputation, or both.

But I'm not gonna do the work and it sounds like you are, so go for it.

In that case, in my language a 'mixer' is a node. Based on what you've said in earlier posts, the difference seems to be that people trust mixers but not nodes (and that mixers are more 'sophisticated'). Or is there more to it?


If I try to pay my taxes in bitcoins I'll get about the same reaction as if I tried to pay them in Monopoly money. Would you suggest that the government will prosecute me for creating a Monopoly money laundry?

The (important) difference between one and the other (for this discussion) is that people seem to think Bitcoins have more value than Monopoly money. Neither is a currency in the same sense that bank notes issued by a national government are currency.

I say again that node operators will have do their own homework regarding their local jurisdiction before they start.

This is all getting a little off point. The original purpose of this thread was to solicit comments regarding the general technical architecture and operating process of a Bitcoin mixnet. Since no one has commented on those aspects I will proceed towards a more detailed technical specification and reference implementation.

By mixer I mean a service that has coins and will send coins from its wallet when it receives coins, ensuring they are not the same.

On AML laws, are you seriously going to go in front of a judge and try to argue that Bitcoin is not a currency and users of a mixer/mixnet are not "customers" in some way? I would be interested to see the reaction to such an argument given that the system is called BitCoin and the front page title is "Bitcoin P2P Virtual Currency".

For the obfuscation yes, I think I didn't explain it well. The columns are not clear text. Instead of a key you store a hash and instead of the value, you store the value XORd with a different hash of the key. It means you can't see what keys are in the table, and you can only read the value when you present a key that is in there.

In my model I have two things: nodes and mixnets. Each node belongs to (is operated and controlled by) a single entity (individual/organization). A mixnet is made up of any number of nodes greater than 1. (I also have clients and transactions (chained and not) but let's keep this simple.)

What is a 'mixer'? Is it a node or a mixnet or something else? Is it controlled by a single entity or by more than one?


I will read more about that once I get the chance, but here's the thing: I don't think any of those regulations apply because Bitcoin isn't a currency and mixnet nodes don't have customers, in the commonly understood definitions of those words. That's not a legal opinion and obviously node operators will have do their homework regarding their local jurisdiction before they start. I just expect that in many cases it won't be a problem until the law begins to recognize Bitcoin as a currency.


I may have misunderstood, but it looks like your DB has two garbage columns but then the two bitcoin addresses, in order and in plaintext. An attacker who seizes the DB will not have to compute keys or values and do lookups, he'll just dump the entire DB, discard the first two columns, and use column A as his key and B as his value.

I mean one "pro" mixer rather than several mixers. I mean, sure, if there are several mixing services around why not join them together, but I doubt that'll happen for a while.

Running a mixer is risky because various government regulations in US/EU require you to know who your customer is once you're doing transactions of above a certain level, I think. See here:

http://en.wikipedia.org/wiki/Anti-money_laundering

In other parts of the world it's less likely to be an issue, but given that AML is quite tied up with the "war on terror" it's worth pondering the risks before setting one up.

For the database it's possible to obfuscate such that it cannot be read but as the entries should be transitory that won't provide too much value. Consider this scheme

Columns: KEY, VALUE, A, B

A and B are large random numbers. You want to insert (foo, bar).

KEY = hash(concat(a, foo))
VALUE = hash(concat(b, foo)) ^ bar

Now key and value are both obfuscated. You can read the value only if you present the key. If the keys and values are BitCoin keys they will be difficult to brute force.

That said I'm not sure that pattern can easily be applied in this case.

That's not quite true. Since the client preparing a transaction knows what size transaction each mixnet node can accept, it can choose nodes with larger maximum transaction sizes. For example, for a 3-node chain, the largest possible transaction will be as large as the third largest node in the pool (ignoring the problem of trust for the moment).

Also, one of the suggested extensions in the document allows single transactions to be broken into smaller pieces and sent along different paths. That increases the largest possible transaction size to the sum of all node sizes (assuming that a 1-node chain is sufficient for that transaction).


I'm not sure I see why. People in Western countries run Tor nodes all the time, which carries similar risks. They are sometimes harassed by poorly-informed authorities but to my knowledge none of them have ever been fined or jailed.

Maybe it's different because Bitcoins are a carrier of value. Still, they are not a recognized currency. I think the political climate will have to change a lot before we begin to worry about government intervention.


Just to make sure I've understood you, you're talking about a single entity that runs many internal coin exchangers, essentially an entire mixnet controlled by one individual/organization? Wouldn't that organization be extremely vulnerable to subpoena/search and seizure? They'd have full knowledge of the sender and receiver of every transaction, so it would be easy for an authority to trace an individual they've taken an interest in, or to trace every single user of the mixnet.


How do you mean? If the database is seized by some authority? In that case it's not going to matter what obfuscation you use, the attacker will be able to decode it. That's the whole reason behind multiparty mixnets: no individual has enough information to trace the entire path, and the path can be chosen to cross many jurisdictions to make traces that much harder.

I'm not sure having lots of small mixers then joining them together is necessarily the best way to build an anonymization service.

One problem is the maximum amount you can mix is the min(all pool sizes), which is probably not that huge assuming reasonable fees.

Another problem is that - let's face it - running a mixer is going to be seriously risky for anyone who lives in the USA or Europe, so there aren't likely to be lots of people queuing up to do it. I would expect such a service would have to at minimum run as a Tor hidden service, as the legal risk involved with being what is effectively a dedicated money laundering service is large.

And yet another problem is that - as you point out in your paper - trust is essential for a mixer service. Building trust takes time and effort, also many people probably aren't that interested in mixing services which further slows down the trust building process.

So I think it's worth exploring not only a "mixnet" model of many co-operating coin mixers, but also a model in which a small number of sophisticated mixers with large coin pools and possibly special hardware can provide this service, whilst still providing the same kinds of privacy guarantees a large mixnet would provide.

This approach has a big advantage, namely that if big miners trusted the mixnet owner, they could set up deals to send large quantities of coins through the mixer 24/7, providing plenty of cover to make timing attacks harder and a big liquid pool.

For clients trusting the mixer on more than reputation alone, a secure platform that supports remote attestation would be ideal. Unfortunately there aren't many of them out there. Hal has practical experience with the IBM 4758 but sadly they aren't being sold anymore. Their replacement requires a contract with IBM to run arbitrary code, it seems.

The final weak point in zipslacks scheme is the mapping of local address -> destination address. This could be solved using an obfuscated table algorithm but it's probably not worth it as the delay between setting up the mix and actually sending the coins shouldn't be all that big.

Yes, after posting I realized that self-mixing creates a mostly-self-connected sub-graph.  You really need to start with multiple transactions in, ideally randomly occuring during the mixing process, and not spend all your bitcoins at once.

Somebody who knows a lot more about graph theory, statistics, and probability than I do should chime in and tell me how I'm wrong or come up with a good metric for the ideal amount of mixing (I bet too much is just as bad as too little).  Analyzing the connectedness of the existing bitcoin transaction graph might be a good place to start.

That system is probably very secure against an attacking fourth party (meaning someone other than the sender, recipient, or mix node) but I think it's more complicated than it really needs to be, for most use cases. It also has a weakness: M knows every detail about the transaction, including the sender and final recipient (and in my opinion the biggest challenge for this type of mixnet is untrustworthy mix nodes). However most of what you describe could be done within the framework I described in the PDF, if the user wanted to be that paranoid. M would not randomize anything, rather A_x's client would specify each transaction to be made, including sizes and delays, and could choose to route the transactions through multiple mix nodes. (Technically it's not a mixnet if there's only a single intermediate node. )


That's a very interesting suggestion. I think I need to learn more about exactly how coins are represented in the block chain, because I was under the impression this wouldn't work because no matter how many accounts a coin passed through, it would always be traceable through the chain back to every account it ever 'belonged' to.

So if I get a payment for 100 bitcoins composed of 20 smaller balances from 20 different accounts, and I trace those coins back and find that 1 week ago they all belonged to a single account, it's likely that the coins were passed through a "send to self" mix and the account from 1 week ago belongs to the same user who just sent me this payment. (Another way to say that would be, it's very unlikely that a user received a payment for (at least) 100 coins, then paid it out in 20 separate transactions to 20 different individuals who passed those coins through another series of transactions that coincidentally finally ended with accounts controlled by a single individual who made a payment of those coins to me. That's a slightly oversimplified example but still a realistic one I think.)

I see the allure of that, and no need to trust a server

With a server though handling many simultaneous mixes then it'd be impossible to analyse.

By channeling it through a central source, the noise from all other people obfuscates the channel. Information is permanently lost.

If the threat model is as zipslack describes, then I think a "send to self" mixnet would work.

Patch bitcoin so it generates, a random transaction every, oh, I dunno, eight hours or so, sending, oh, I dunno, 1/10'th or so of your bitcoins back to yourself via a newly generated address.

And to erase your trail in case your wallet gets seized, remove the source transactions and their (spent) keys from your wallet.

After a week of doing that you'll have put 21 extra transactions on the network and, on average, four extra transactions on the coins in your wallet (four because every send typically generates a change transaction).  Do it constantly and you'll have an ever-churning wallet that aught to foil any attempt to connect incoming <-> outgoing transactions.

That is all assuming that you don't start with zero bitcoins in your wallet, get exactly 111.11 bitcoins from somebody, spend a couple weeks mixing them, and then pay exactly 111.11 bitcoins to somebody else.  That transaction network graph is easy to analyze, and it would be insanely unlikely that you "just happened" to receive exactly those same 111.11-worth of coins that were given out.

Hmm, I wonder if the patch could detect a bad mix and warn you if you tried to do something stupid like that...

Somebody who knows a lot more about mixnets than I do can probably work out the math to know how much, and what type, of randomness to add to the eight hours and 1/10th to make statistical analysis as difficult as possible.

Me and MagicalTux were discussing this. The concept we came up with to provide anonymity was:

A_x wants to send to B_x

A_1 sends 40 BTC to M
A_2 sends 10 BTC to M
A_3 sends 30 BTC to M

Spread over 1 week M does:

M sends 10 BTC to B_1
M sends 3 BTC to B_2
M sends 5 BTC to B_1
M sends 6 BTC to B_2
M sends 10 BTC to B_3
M sends 15 BTC to B_1
M sends 5 BTC to B_1
M sends 22 BTC to B_3

- The sums the mixnet sends never total the sums received. Its +/- a random amount (biased slightly towards - as the fee).
- Plausible deniability by spreading the funds over time.
- A_x provides several addresses for the B_x destination. M cycles through this list randomly then restarts once it's finished.

The only method to reverse engineer payments using this mixnet is through statistical analysis. If the payments are broken down enough, and many different users channel their payments through the system then it's very hard to rationalise what happened from the block-chain.

I am assuming that traffic between senders and nodes will be tunneled through an anonymizing network and I'm assuming that such network is secure. I'm really only trying to address the problem of transferring your coins (assumed to be tainted with your identity) to a recipient whose address you have, without allowing that recipient (or others) to learn your identity by examining the block chain. Problems of secure and anonymous communication are outside the scope.


I'm assuming not. The objective is to prevent the attacker from obtaining the sender's addresses.


Again I am assuming not, since the attacker doesn't know the sender's addresses.

I think you should begin by defining the threat model.

Can the attacker see all unencrypted IP traffic to/from the sender's node, or is the traffic tunneled through an anonymizing network like i2p or tor?

Does the attacker know any of the sender's receiving bitcoin addresses?  Is the attacker willing and/or able to send 'marked bitcoins' to the sender?  Lots of them?

http://www.flamewars.org/~phil/Bitcoin%20mixnet.pdf

From the linked document:
This idea or one like it has very likely been discussed before. I've certainly seen people suggesting using Bitcoin exchanges as single-stage coin exchangers to limit the traceability of a transaction. This is mainly a suggestion for how to standardize that concept to allow for a scalable mixnet. It's a very rough and general document at the moment, but I think it's a good starting point for discussion.