Topic: coin mixing using Chaum's blind signatures (Read 5394 times)

It was mentioned above that you indeed can get better anonymity if you trust the mixer... That's just plain Chaumian cash.

Maybe mixing scheme I proposed for account ledger system can be adapted to use with bitcoin. It will surely be more complicated, but you know, it's just like everything else in bitcoin

https://bitcointalksearch.org/topic/m.2289285

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. 

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.

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://bitcointalksearch.org/topic/ann-bitprivacy-decentralized-trustless-privacy-200952

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.

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.)

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


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.


Not if it is integrated with some popular wallet software


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.

sorry ari, i was trollin you a bit

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 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!

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

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

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.

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.

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


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


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?


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


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

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

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.

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.

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

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.

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



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.

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.