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.
Topic: coin mixing using Chaum's blind signatures - page 2. (Read 5394 times)
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.)
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.)
Jump to: