JoinMarket has a problem where it assumes different nicknames have different bitcoin wallets. This can be exploited by people running multiple yield generator bots from the same wallet, so they get a higher rate of profit at the expense of de-legitimizing the system for privacy.
A merkle tree is a way of producing a commitment to a set, which can later can prove that elements are contained within the set using only O(logN) data, and only revealing one other element in the set.
For example here is a merkle tree commiting to a set of numbers {6, 3, 9, 0, 8, 4, 7, 2}
R
/ \
N N
/ \ / \
N N N N
/ \ / \ / \ / \
6 3 9 0 8 4 7 2
N are the nodes in tree, each node is the hash of the two lower node hashes concatenated together with N = hash(N_left | N_right). And R is the root hash, which is published as a commitment along with the total number of elements.
To prove that a certain element is a member of the set, it is only required to reveal some hashes. For example proving the membership of element 0.
R
/ \
N N
/ \
N N
/ \
9 0
The challenger can then concatenate and hash all those elements and show that they recreate the root hash R. Only one other element in the set needs to be revealed. Also note that these proofs are transferable to other entities.
Merkle trees are used in bitcoin, each block must have the merkle root of all the transaction hashes which can be used by lightweight wallets to prove that a certain transaction did indeed get mined into a block.
For better diagrams, the wikipedia page has a good one, also google images and this page from the bitcoin.org developer guide which has a cute gif animation.
By sorting the elements in set, a merkle tree can be used to prove the non-membership of certain elements. Take the same set {6, 3, 9, 0, 8, 4, 7, 2} but sort the elements.
R
/ \
N N
/ \ / \
N N N N
/ \ / \ / \ / \
0 2 3 4 6 7 8 9
To prove that a certain element 1 is NOT in the set, reveal elements either side.
R
/ \
N N
/ \
N N
/ \
0 2
Hence 1 is not in the set because 0 < 1 < 2, but 0 and 2 are next to each other.
In this best case, only one branch and two leaf nodes must be revealed. In the worst case another branch of the tree must be revealed, revealing four leaf nodes. For proving 5 is not in the set:
R
/ \
N N
/ \ / \
N N N N
/ \ / \
3 4 6 7
JoinMarket's issue693 problem could be solved using sorted merkle trees and proofs of non-membership.
Along with their offers, makers must publish a sorted merkle root of all the coins (UTXOs) in their wallet. Later in the protocol, when makers send their coinjoin transaction signatures they also send a proof that other UTXOs are not included in their own wallets. If the maker fails at any of these proofs then the taker won't go ahead with broadcasting the coinjoin, which is a opportunity loss for the maker.
Because merkle tree proofs of non-membership don't need to reveal many other leafs, the taker does not learn many other of the maker's UTXOs, which is important or else a malicious taker could unmix the maker's future coinjoins. (See joinmarket issue #156)
Also the log scaling of merkle trees is helpful to keep the amount of data transmitted low. Although makers anyway have an incentive to not have too many UTXOs in their wallet because it will eventually cost them miner fees to combine together. So it's likely the UTXO merkle trees won't be very big (I estimate less than 50 UTXOs, from asking some people)
Obviously the above scheme doesn't work if it's not proved that the maker's merkle root hash is indeed a real commitment of their wallet. A maker could swap two UTXOs to get a new merkle root hash, then run a new bot with that hash which would roughly double their income.
Along with the other proofs of non-membership described above, the taker should also demand a proof of set-membership for the UTXOs the maker sends that are intended to be spent in the coinjoin.
All the proofs the taker receives must also be checked to make sure that the UTXOs are sorted correctly.
The taker could also send a few random integers to the maker, and the maker must reply with the UTXOs at those indecies, the taker will check they are sorted.
Finally, if the taker detects any fraud they can publish to the messaging channel a proof of wrong-sorting, in this case 2 comes before 0:
R
/ \
N N
/ \
N N
/ \
2 0
Other takers can see this proof and know not to create coinjoins with the maker which has wallet merkle root of R.
Also other honest makers could re-send the proof whenever a new taker appears and asks for the orderbook. Then the new taker knows not to create coinjoins with the fraudulent makers. To save bandwidth, the honest makers should only send 'inventory' messages first, the taker then chooses a single maker to download the actual proofs from. This is the same idea as in the bitcoin p2p protocol with the 'inv' command.
A serious problem with the 'honest makers rebroadcasting fraud proofs' idea is the fraud maker knows when they have been found out, and could simply swap two UTXOs in their wallet to get a new merkle root and carry on.
No problems with privacy for the maker as far as I know. But we should be mindful, especially in light of issue #156.
It might be possible to do this with another data structure apart from sorted merkle trees which also supports proofs of non-membership.
Please direct any comments to the github issue: JoinMarket-Org/joinmarket#693
In point 2 in sorted merkle tree why can't you prove membership just like you are checking non membership by comparing data? I think this is not the way to prove nonmembership, you are missing something.