coin mixing using Chaum's blind signatures

[killerstorm]

Fairly easy to implement, if I'm not missing something:

Suppose there is a mixer service.

First of all, user needs to prepare outpoints for mixing: they should have exactly the bitcoin amount service requests, say, 1 BTC.

User submits a pair: outpoint he wants to mix and a blinded hash of receiving address. He also needs to pay a small fee. Server responds with a blind signature of an address. (I'm sorry if I'm using terminology incorrectly: I've just read blind signature algo description.)

Some time later user submits his address together with unblinded signature. Service can confirm validity of signature, thus it knows that this address is linked to some outpoint, but it cannot know with which one.

After enough users have submitted their outpoints for mixing, service will create a mixing transaction: it will include all outpoints and all addresses. Since addresses appear in a different order, it isn't possible to tell which outpoints are linked to which addresses.

Users then sign their outpoints after confirming that their addresses are included in transaction's outputs.

There are two possible problems:

1. User refuses to sign his input. It's easy to deal with it: asshole's outpoint is banned, everybody else re-submits their blinded and non-blinded addresses. Thus this DoS attack costs asshole money. Also service might require minimal age of 1 day for outpoints. It would mean that to sabotage signing 100 times per day asshole needs at least 100 BTC.

2. NSA submits their own outpoints for mixing, subtracts them from transaction and thus reduces mixing entropy. I don't see it is a big problem because mixing entropy is always log2 N where N is number of honest participants who will never reveal their (outpoint, address) pairs. So NSA can only instill a sense of false security if number of honest participants is low. And it will cost NSA some money...

In an ideal case commonly used Bitcoin clients should do mixing from time to time, even if users doesn't really need it. This will make sure that number of honest participants is quite large. Then Bitcoin will be statistically anonymous.

EDIT: Oh, the third possible problem: mixer service is run by NSA and they will make sure that your coins are not mixed with coins of honest people. This problem needs to be addressed, but I think solution is fairly simple: it is possible to check quality of mixing externally. Say, if have some sort of web of trust, WoT members can sign messages like "my coins were mixed in transaction xxx". If you see that enough WoT members sign certain transaction you can make sure that some mixing entropy exists. (As long as you trust WoT, that is.)

[Ari]

There's a limit to RSA blind signatures - if someone signs a bunch of small prime numbers, then multiplying these together yeilds a valid signature on the product.  Collect enough factors and you can sign anything.  So, if too many blind signatures are made, it effectively leaks the signing key.  Thus, the signing key needs to be changed each time, and you can only mix a limited number per batch.

[killerstorm]

Doing it in small batches is OK, it's probably even preferable for other reasons: faster and less disruptions.

It is possible to do mixing in a p2p fashion without blind signatures: by mixing coins of two users at once. But if some users are compromised (e.g. are NSA agents), entropy gain per round is small, and so large number of rounds is required. Blockchain bloat will be too large...

Doing it in batches where more than two users are involved would drastically speed up entropy gain. Even, say, 32 inputs per transaction is very good.

You still probably want many rounds (ideally on different services), but not thousands of rounds. If rounds are fast, it's not a problem.

For the sake of completeness, I previously considered two-party mixing rounds with subsequent compaction: i.e. these two party transactions won't be submitted into blockchain, but instead somebody would make a large transaction out of all of them and people will then sign this large transaction. It is possible and can compress thousands of small mixing rounds into one tx, but is very vulnerable to DoS attack: if there is an asshole who refuses to sign, people will have to re-do mixing pretty much from scratch.

[behindtext]

Fairly easy to implement, if I'm not missing something:

this is an interesting improvement on the usual mixing service. might be instructive to put together some example code.

There are two possible problems:

1. User refuses to sign his input. It's easy to deal with it: asshole's outpoint is banned, everybody else re-submits their blinded and non-blinded addresses. Thus this DoS attack costs asshole money. Also service might require minimal age of 1 day for outpoints. It would mean that to sabotage signing 100 times per day asshole needs at least 100 BTC.

2. NSA submits their own outpoints for mixing, subtracts them from transaction and thus reduces mixing entropy. I don't see it is a big problem because mixing entropy is always log2 N where N is number of honest participants who will never reveal their (outpoint, address) pairs. So NSA can only instill a sense of false security if number of honest participants is low. And it will cost NSA some money...

In an ideal case commonly used Bitcoin clients should do mixing from time to time, even if users doesn't really need it. This will make sure that number of honest participants is quite large. Then Bitcoin will be statistically anonymous.

EDIT: Oh, the third possible problem: mixer service is run by NSA and they will make sure that your coins are not mixed with coins of honest people. This problem needs to be addressed, but I think solution is fairly simple: it is possible to check quality of mixing externally. Say, if have some sort of web of trust, WoT members can sign messages like "my coins were mixed in transaction xxx". If you see that enough WoT members sign certain transaction you can make sure that some mixing entropy exists. (As long as you trust WoT, that is.)

the blind signature trick is helpful. per your own comments the issue is again reduced to "do you trust the mixer you're using?".

establishing some kind of trust metric, e.g. mix quality, for each mixing service doesn't sound like a bad idea.

[killerstorm]

the blind signature trick is helpful. per your own comments the issue is again reduced to "do you trust the mixer you're using?".

I wouldn't formulate it like that. A simple mixer service can trivially run away with your money, or it can log everything and sell it to interested parties. So it is 100% honor based, and quite likely you rely on service being altruistic.

On the other hand, it is kinda hard for a blind signature-based mixer to attack someone. Moreover, such attack can be easily detected by users.

So it isn't about trust. It is like "does somebody want to pull off a sophisticated attack at his own expense to reveal my identity?"

We should try to improve it further, but even as is it is way ahead of simple mixers in terms of security.

[behindtext]

There's a limit to RSA blind signatures - if someone signs a bunch of small prime numbers, then multiplying these together yeilds a valid signature on the product.  Collect enough factors and you can sign anything.  So, if too many blind signatures are made, it effectively leaks the signing key.  Thus, the signing key needs to be changed each time, and you can only mix a limited number per batch.

bitcoind uses (256-bit) ecdsa keys, so i would expect the bleeding of signing key via prime factors, which is specific to rsa, to be irrelevant.

i could, of course, be wrong

[killerstorm]

bitcoind uses (256-bit) ecdsa keys, so i would expect the bleeding of signing key via prime factors, which is specific to rsa, to be irrelevant.

Blind signatures used by mixing service are entirely orthogonal to Bitcoin cryptography.

From what I see RSA should be used for blind signatures, but perhaps there is a way to make other digital signature protocols to work with it too.

[gmaxwell]

Blind signatures used by mixing service are entirely orthogonal to Bitcoin cryptography.

From what I see RSA should be used for blind signatures, but perhaps there is a way to make other digital signature protocols to work with it too.

It's pretty easy to implement blind signing with ECC. http://ojs.academypublisher.com/index.php/jnw/article/viewFile/0508921928/2053


Edit: See also this post from a few months ago where I describe the same idea as this thread: parties use blind signatures to collaborate to choose a set of inputs and outputs for a single transaction.  In that thread users of the forum actually generated joint transactions with me (though without the blind-signature privacy parts) -- the idea is older still but that thread couldn't be created until Bitcoin-QT released raw transaction support so that people could participate.

[proff]

Since your scheme is separate from Bitcoin, it seems that it would be cumbersome for users: they would need to run a special client and keep it online for a long time. Also, how is the resulting mixing more secure than the server simply selling people Chaumian cash? It could be interesting to set up a mix-net rather than a single server, though.

If you simply want to experiment with blinding, for every 1.05 bitcoins you send me plus a blinded address, I would be more than happy to sign the blinded message, and for every fresh Bitcoin address you give me with my signature on it, I will send 1 coin to that address

[killerstorm]

Since your scheme is separate from Bitcoin, it seems that it would be cumbersome for users: they would need to run a special client

Well, it might be sort of a plugin for one of clients...

and keep it online for a long time.

Not necessary. If a lot of people use mixing, one round can be done in less than a minute.

Also, how is the resulting mixing more secure than the server simply selling people Chaumian cash?

Isn't it obvious? You can keep your bitcoins securely in your wallet. Service simply helps to negotiate a transaction which sends Bitcoins from your wallet to your wallet. There is no risk whatsoever.

"Simply selling people Chaumian cash" would require people to trust that server, develop a way to pay with them etc.

In which sense it is simpler than running a "mix my coins" plugin for your wallet?

It could be interesting to set up a mix-net rather than a single server, though.

Sure, there is no reason to have just one server.

If you simply want to experiment with blinding, for every 1.05 bitcoins you send me plus a blinded address, I would be more than happy to sign the blinded message, and for every fresh Bitcoin address you give me with my signature on it, I will send 1 coin to that address

I would need to trust you to not run away with my money. Also I cannot estimate mixing quality you provide.

[Ari]

bitcoind uses (256-bit) ecdsa keys, so i would expect the bleeding of signing key via prime factors, which is specific to rsa, to be irrelevant.

i could, of course, be wrong

Blind signatures, as described by David Chaum, are based on RSA.

Anyway, the basic idea is that someone buys a blind signature from the mixer, then some time later uses that signature to get money back, but the mixer can't connect the two.  The blind signature is not used to directly sign bitcoin transactions.

[killerstorm]

Well, it might be sort of a plugin for one of clients...

To elaborate on this... I was involved in development of ArmoryX, an Armory modification which can do colored coins.

What I noticed is that it is fairly easy to implement plugins for Armory in Python. Perhaps etotheipi will add this to Armory mainline...

Anyway, it can look like this: you grab normal Armory binaries, then install some plugin in form of Python code (of course, you need to check that it doesn't steal your coins =) ), then you basically have "mix my coins" button.

It is fairly easy to implement this. p2ptrade I've implemented for ArmoryX does something very similar, so-called atomic coin swapping between two parties. (I.e. two parties construct a transaction and sign their parts of it after they check that transaction is right.)

It is probably possible to implement an add-on for bitcoind which would use RPC API.

Finally if somebody uses a client which doesn't have this plugin/add-on, he might run a standalone mixer program. Basically this program will give you an address, you send coins to that address, and some time later get them back.

So feasibility isn't a problem at all. I wonder whether this scheme is secure, and whether there is interest in mixing like this.

[proff]

Since your scheme is separate from Bitcoin, it seems that it would be cumbersome for users: they would need to run a special client

Well, it might be sort of a plugin for one of clients...

There are different clients, though, and many people use online wallets. Just something to keep in mind (eg you would not want the online wallet to know which addresses are yours and therefore link them!) That said, an easy-to-use plugin or standalone application is probably the way to go, sure.

Not necessary. If a lot of people use mixing, one round can be done in less than a minute.

not sure if that fast, don't forget that the batches will be queued up and broadcast in some random order. And it will take time before "a lot of people" are using the service on a regular basis!

Also, how is the resulting mixing more secure than the server simply selling people Chaumian cash?

Isn't it obvious? You can keep your bitcoins securely in your wallet. Service simply helps to negotiate a transaction which sends Bitcoins from your wallet to your wallet. There is no risk whatsoever.

I meant secure as in indistinguishability of outputs. You are right, of course.

"Simply selling people Chaumian cash" would require people to trust that server, develop a way to pay with them etc.

In which sense it is simpler than running a "mix my coins" plugin for your wallet?

Not simpler, but having some of the mixing bypass the Bitcoin network completely is potentially more secure.

[behindtext]

bitcoind uses (256-bit) ecdsa keys, so i would expect the bleeding of signing key via prime factors, which is specific to rsa, to be irrelevant.

i could, of course, be wrong

Blind signatures, as described by David Chaum, are based on RSA.

Anyway, the basic idea is that someone buys a blind signature from the mixer, then some time later uses that signature to get money back, but the mixer can't connect the two.  The blind signature is not used to directly sign bitcoin transactions.

sorry ari, i was trollin you a bit

[killerstorm]

There are different clients, though, and many people use online wallets. Just something to keep in mind (eg you would not want the online wallet to know which addresses are yours and therefore link them!)

Well, one should send coins to a different wallet after mixing, ideally on a different online wallet service.

not sure if that fast, don't forget that the batches will be queued up and broadcast in some random order.

Once server have queued up enough tickets it will send a message "broadcast within a minute starting from T".

Participant picks a point in time within that minute at random and broadcasts his unblinded ticket at that point.

There are some difficulties in this, for example, user needs to be able to switch to an unrelated IP address between time he obtained ticket and redeemed it. But otherwise speed is limited by demand for such service, i.e. time it takes to queue up enough participants.

And it will take time before "a lot of people" are using the service on a regular basis!

Not if it is integrated with some popular wallet software

Not simpler, but having some of the mixing bypass the Bitcoin network completely is potentially more secure.

I don't see how, properly executed mixing is exactly as untraceable as Chaumian cash.

Basically, the only difference is who signs the transaction, and I don't think it is substantial.

[proff]

Let's agree that, no matter what goes on inside the mixer, coins go in and later coins come out; what achieves anonymity is the inability to connect inputs with outputs. Therefore small batches and a small latency window will reduce anonymity. Consider the case of a coin sent to the mixer and a coin that comes out 36h later, or a couple of weeks later - could they be connected? Seems better not to set short time limits.

Also do not forget that an attacker will be spamming the server with their transactions, both for DoS and to fill up any small batches. Of course for each "real" input there will be a probability that the mixer adds a dummy input and output. (And of course all communication with the server is encrypted and dummy traffic generated.)

[BlindMixerDR]

There's a limit to RSA blind signatures - if someone signs a bunch of small prime numbers, then multiplying these together yeilds a valid signature on the product.  Collect enough factors and you can sign anything.  So, if too many blind signatures are made, it effectively leaks the signing key.  Thus, the signing key needs to be changed each time, and you can only mix a limited number per batch.

I am currently finishing to build a mixer which functions on this principle, with RSA. This point by Ari is the only insecure thing to be resolved. But every blind signature requires the user to send some bitcoins first. And these bitcoins are not redeemable if the user asks for blind signature on a small prime number.
Therefore, only issue is how many unredeemed blind signatures is safe to leave. When this number is reached, the mixer must change the blindsigning key.

Alternative is to make a pool of blindsigning keys, and select at random for each blind signature. This adds complexity.

[Tom Scholl]

I'm building a p2p trustless Bitcoin privacy solution that operates like this - many thanks for the description, killerstorm!

Current status is testnet only, as there are various privacy-breaking attacks that I haven't countered yet. But it seems to work, and I was really happy to find this algorithm as implementing secure multi-party sorting didn't look easy.

Here's the thread, with source etc: https://bitcointalk.org/index.php?topic=200952

[Etlase2]

In the context of Decrits, I have come up with a blind-mixing system that has several good properties:

1) You can't lose your money, no matter what
2) No extra p2p network is required to find other people to mix with, it is managed by the network
3) In regards to your point 1, asshole will simply lose his money

Caveats:

1) A set amount of time must pass after enough transactions have been corralled and blind signed, to give everyone an opportunity to claim the unblinded txes. This must be on the order of several days.

Basically, the shareholders in the decrits system will be the blind signers. Say someone initiates a blind tx pool for 50 coins and 100 inputs. This info is public and everyone on the network can see that they can add to this pool. Once 100 inputs are received, users have 7 days (or whatever) to unblind and send the transaction to receive payment. After 7 days, the shareholder will retain any uncollected transactions. This doesn't hurt the viability any more than the NSA injecting txes. If any time prior to the 7 day mark more txes are received than the shareholder has ability to pay, he will lose his deposit, and all inputs will be refunded to their original accounts.

If blind signatures are vulnerable to attack (I was not fully aware of this), it is simple to add one-shot use public keys for each pool that can only be associated with the shareholder in question. Because this will require 2 txes and 3 signatures, the fee for these transactions will be more, and indeed NSA will lose money when the very paranoid people will do this multiple times across many different pools. It will be a mostly fruitless affair.

[townf]

This is all kind of over my head here and possibly off topic, but to aid in anonymity in any mixer no matter the number of inputs/outputs and no matter who inputs the coins, what about the possibility of instead of immediately crediting the outputs, the mixer could issue a "receipt" that could be cryptographically printed on a smartchip or something. This "receipt" can be used just like physical cash and passed around in transactions with no record in the blockchain until it is redeemed to the mixer later, which adds anonymity and the convenience of physical cash.