How does MimbleWimble avoid transaction graph leaks?

Question

Now, creating transactions in this manner supports OWAS already. To show this, suppose we have two transactions that have a surplus k1*G and k2*G, and the attached signatures with these. Then you can combine the lists of inputs and outputs of the two transactions, with both k1*G and k2*G to the mix, and voilá! is again a valid transaction. From the combination, it is impossible to say which outputs or inputs are from which original transaction.

Suppose that you observe these two transactions on the network, prior to them getting into a block. Can you separate them then? If you can get ahold of all of the transactions in a block before they get combined, can you produce a transaction graph like what we currently have, without amounts?

Answer 1

Yes -- although "without amounts or scripts" gives a clearer idea of what the transaction graph will look like: every output is a uniformly random curvepoint. This story is actually quite a bit better than Bitcoin where there are "addresses" which are often public and often reused.

In general, finding a p2p layer that hides the original, unmerged transactions, seems difficult. Initially I had thought it would be possible for "passive merging" where nodes would just aggregate all the transactions that they saw, taking in unmerged transactions and outputting merged ones. This appears to be very fragile: consider three nodes which each have a transaction, say A, B and C. The first node publishes A, then the second and third latch onto it simultaneously, outputting AB and AC respectively, and now only one of B or C can be confirmed. Observe that this happens even without any adversarial behaviour, and happens even if merging is only done by some special set of "masternodes".

The problem ultimately comes down to the fact that with OWAS, conflicting merges (transactions with intersecting input sets where neither is a subset of the other) look identical to conflicting transactions (double-spends). So "unifying" AB and AC to get ABC, which is the desired network behaviour, is just as hard as "unifying" a double-spend. Which, to be clear, is "doesn't even make sense" levels of difficult.

It may be possible to have a p2p layer that does interactive merging somehow, which in Mimblewimble could be made much simpler than Coinjoin in Bitcoin, so that transaction creators have control over what other transactions their transaction gets merged with on the wire. Miners would then drop the signatures or whatever was needed to enforce interaction at the p2p layer and just merge what they got. This might be sufficient to stop the creation of accidental conflicts, but you then have to worry about adversarial behaviour.

It would be possible for users to directly communicate transactions to miners; for a given transaction they'd give a different version to every miner so that nobody but the miner who created a block would be able to tell what the original transactions in the block were. Absent collusion this would erase a lot of the transaction graph from any specific adversary's view, although it would enforce miner centralization which I find very undesirable.