Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sorted merkle tree as solution to issue #693

The Problem

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.

Crypto primitive 1: Merkle Tree

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.

Crypto primitive 2: Sorted Merkle Tree

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 Proof of Unique Wallet

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)

Ensuring the Merkle Root is a True Commitment to the Maker's Wallets

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.

Privacy for the Maker

No problems with privacy for the maker as far as I know. But we should be mindful, especially in light of issue #156.

Other

It might be possible to do this with another data structure apart from sorted merkle trees which also supports proofs of non-membership.

Comments

Please direct any comments to the github issue: https://github.com/JoinMarket-Org/joinmarket/issues/693

@dheerajkhatri

This comment has been minimized.

Copy link

dheerajkhatri commented May 15, 2017

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.

@shangsony

This comment has been minimized.

Copy link

shangsony commented Dec 29, 2018

good idea

@kant111

This comment has been minimized.

Copy link

kant111 commented May 9, 2019

what if I want to prove 10 does not exist? should I reveal the entire tree?

@0xAshish

This comment has been minimized.

Copy link

0xAshish commented Nov 20, 2019

@kant111 you can have constant start, end in a tree. like null node, through which it can be proved that max value is 8 and the last value is null so you provide proof for (8,null).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.