Authors: Jonald Fyookball, Dr. Mark B. Lundeberg, @ProtocolCash
CashShuffle works as designed, processing hundreds of transactions a day on Bitcoin Cash. However, users still need to consolidate their coins. (For instance, if you have 2 shuffled coins of ~1 BCH and you want to purchase something > 1 BCH.)
Consolidation of inputs (even shuffled inputs) is an issue because it leaks information -- namely, the linkages between inputs.
With a single input being spent, the origins of the coin are obfuscated via the preceeding shuffle transactions, thus providing several possible origins. But with each additional input being combined, more and more clues accumulate as to the real origins.
Here's why consolidation is challenging:
Normally in coinshuffle, the participants only have one input each, and if they fail to sign that input, everyone knows who to blame. This provides at least a basic level of DOS-protection.
But with multiple inputs, it won't be clear who to blame. In fact, finding the guilty party (who failed to sign the final transaction) is directly at odds with the goal of hiding one's input linkages from all other shuffle participants, as well as the server.
There is an IP-address component of the current blame mechanism in CashShuffle that would unable to be used for this reason. Blaming could still be done on a per input basis, but would be fairly weak DOS-protection without the IP component.
Besides the main idea being presented, we can compare and contrast to somesome other potential means of handling the situation.
1. Use multiple inputs in the coinshuffle message
Users could simply choose not to care about the fact that other players in the same shuffle would know their input linkages.
This is an obvious drawback but if that limitation was accepted, then the solution is easy: Just have everyone announce all their inputs to everyone. If any of those inputs aren't signed, everyone knows who to blame.
2. ZKP
We can imagine some "crypto magic" solution using a zero-knowledge proof. If we could somehow prove that Alice signed all her inputs without telling anyone what her inputs are, this would be the best solution.
This might turn out to be impossible, but if it is possible, requires advanced cryptographic knowledge.
3. Combinatorics
We can also imagine a "poor man's ZKP" where the players sign a commitment to a certain range of values. For example, if Alice's actual inputs total 1.00343455, then she could sign a commitment that says there is some subset of inputs in the total set of all players' inputs between 1.0034 and 1.0035.
The idea would be to have this range be not so wide as to be unuseful for banning, but not so narrow as to create a unique set of inputs. Tradeoffs here would include the inability to always blame someone and the inability to guarantee privacy. Very messy.
4. Self-consolidation via multiple shuffles
A "backdoor" approach to the whole problem is just let the users consolidate on their own, but make it less dangerous to do so by utilizing multiple shuffles and restrict the number of coins that could be consolidated. A special tool in the wallet menu could do this, perhaps with a privacy slider bar. More privacy would mean less coins could be consolidated at once, and those coins also need more multiple shuffles.
This is something that could be built rather easily. But it is not clear how user friendly the entire approach would be in practice, nor how much privacy leaks it really solves (without a more detailed analysis). And this puts all those consolidations on chain for analysis.
"Semi-trusted" refers to (optionally) trusting the server with the privacy of the linkages of a user's inputs.
The basic idea of this solution is to have shuffling participants tell the server which inputs are theirs. If not all of the inputs are signed, then the server knows who to blame. The advantage of this solution, over say the self consolidation strategy, is that none of the extra information is published to the blockchain.
We can utilize a multi-round process where the first round doesn't reveal the key information to the server, and assumes all participants are honest actors. Using this assumption all the time would naturally lead to DOS. But here, we can have the best of both worlds. We first try to build the transaction naively, leaking no information. If that fails, the next round relies on the server as a facillitator.
Wallets could be configurable so that the user has the option whether or not to participate in an "assisted" shuffle (whether or not they want to share the information with the server). Note that the only information the server would be trusted with is the linkages between the inputs, and NOT the linkages to the output.
Note that this type of consolidation shuffle would be completely separate from (and would not replace) the standard (v300) shuffle.
The protocol would roughly follows these steps:
-
Players join the pool and choose an output of a standard size (for example 1 BCH). They can use the coinshuffle layered encryption although this is a different context. In this case, the encryption is done to hide the ownership of outputs from the server.
-
Players covertly announce their inputs (which need to total at least the output plus fee) See further discussion below about this.
-
All players sign the transaction.
-
If all players sign, we are done. If not, proceed to next step.
-
The entire shuffle is attempted again: Players who are willing to share their inputs with the server rejoin.
-
Each player shares the inputs they intend to use with the server.
-
All players sign the transaction.
-
If all players sign, we are done. If not, proceed to next step.
-
If all inputs aren't signed for any given player, server will ban the player via his IP address.
-
If a player is banned, then there are several ways to implement how to continue: either the process can be repeated with the current players minus the offender (coinshuffle++ style) or there can be another new process (either trusted or untrusted).
One important question is how will participants will covertly announce their inputs to the server? In the second loop (which is trusting the server with input linkages), then the annnouncements will not be covert; the layered encryption nicely obfuscates the outputs.
In the first loop (which is trustless), participants need to hide their IP address from the server. This could be done via TOR with a separate TOR route for each input. It also may be recommended to use a time delay (depending on how much delay there is already switching TOR routes) so that the server cannot deduce the input linkages based on timing.
It also possible to build an "internal TOR" system that is self-contained, where participants use DH key exchange to securely trade UTXO to broadcast, combined with a public key encryption from the server; In this scheme the server wouldn't know that an input doesn't belong to a player, and the players wouldn't know which utxo is being traded.
The strongest and simplest means to avoid giving away the ownership of inputs due to their uniqueness is to require that all amounts are the same size. For example, 5 players with 10 inputs of 1 BCH can create a transaction with 5 outputs of 10 BCH. Additionally, each player can include one input with sufficient funds to pay the mining fee. In this scheme, there would be no change outputs.
Coins can be consolidated using standardized amaounts (10 coins of 0.01 BCH can meld into 1 coin of 0.1 BCH, etc). It would possible to start with inputs of the smallest standard size (for example 0.0001 BCH), which then would condense into a smaller number of the next standard size (0.001 BCH), and so on. However, this would require the number of starting inputs to be quite large.
Instead of building up amounts like a pyramid, a more practical method will be for users to accumulate 10 shuffled coins on the same tier, and then "shave" the change off the standardized amount. For example, if the user has 10 coins of at least 0.1 BCH, they can shave off the portion that is larger than .1 BCH. This will give them 10 coins of exactly 0.1 BCH and new change output.
Those coins of the standardized amount can then be used for consolidation. In CashShuffle, normally any spend of a shuffled coin results in unshuffled outputs. But in this case the round number amounts obtained from shaving should get a new status, which is neither really shuffled or unshuffled. They can be spent in a consolidation shuffle, and shouldn't be marked for reshuffling since that would disturb the process. The outputs of non-standard amount from the shaving transaction should be marked as unshuffled and subsequently shuffled normally.
It's neither practical nor possible to keep lowering the standard size down to a satoshi. At some point, you have to deal with dust and fees. 0.0001 BCH is the lowest amount currently implemented in CashShuffle (10,000 sats) and this seems good. Below this, we propose setting up a shuffle with the following parameters, chosen precisely: 10 players using 10 inputs each. Considering the fee for signing a transaction will be already 1500 sats, and the minimum spendable input is 540 sats, statistically the participants are unlinkable.
"Semi Trusted" isn't the best sounding name, so suggestions are welcome for a replacement. But it also may be better, marketing-wise to make less controversial claims and be conservative. Three marketing points are as follows:
- The trust is optional. Some users will choose not to share linkages at all.
- The only trust required is trusting the server with the input linkages (not the outputs)
- This requires far less trust than people already give to ElectronX servers (servers can see your whole wallet!)
Thinking Cash ______. CashShuffle and Cash ______. Cash Blend? Cash Meld? Cash Play? Cash Mash?