# Communication complexity of comparing sets, for Bitcoin

In Bitcoin, when one node wants to tell another node about a block, it sends the block header, then all the transactions it contains. This is inefficient, because the receiving node might already have some or all of those transactions.

The sending node needs to tell the receiving node

• the transactions that the receiving node does not have
• which transactions are in the block
• what order those transactions are in

What would be more efficient than sending all of the transactions? (Each transaction is about 160 bytes)

You could send a list of hashes of the transactions. That would reduce the overhead for each transaction to 20 bytes (if you used SHA1). The receiving node could ask for the transactions that it was missing. This is the most efficient method that I can think of - but I think there’s probably something better.

• To pre-empt anyone suggesting that this should be on Bitcoin SE, note that the asker is a high-rep user there so presumably has a better feeling than we do about whether this question belongs there. :-) – David Richerby Sep 2 '14 at 20:04
• Do you have any domain knowledge on the probability distribution on which transactions the recipient is likely to already have, and which it might be missing? For instance, is it likely that there is a long common prefix of transactions that both nodes are likely to have, and most of the differences are right near the end? If so, that might enable some optimizations (e.g., by choosing the structure of a Merkle tree cleverly). – D.W. Sep 3 '14 at 7:25
• @D.W. Doing an unscientific test, my Bitcoin client already knows about 50-90% of the transactions. – Nick ODell Sep 3 '14 at 18:45

One possibly better approach would be to use a Merkle tree, or some other hierarchical data structure like that. If there's a large set of transactions that the sender can identify as probably already known to the recipient, then this might save a significant amount of data transfer.

Build a binary tree, where each leaf corresponds to a single transaction, and where each internal node has two children. Now each leaf node will be labelled with 20 bytes, namely, the hash of the transaction. Each internal node will be labelled with 20 bytes, namely, the hash of the concatenation of the labels on its two children. For example, for each $i$, we might have an internal node at height $i$ that covers the first $2^i$ leaves, with a complete binary tree hanging underneath it (along with a bunch of other internal nodes).

The two parties can then compare their Merkle trees via some interactive protocol. Note that if Alice and Bob established that they both have the same label for some node of their tree, they don't need to examine anything under that node; they know the subtree rooted at that node is the same for both of them. If they have a different label for some node of their trees, then they can recurse and compare their children.

You can probably choose the structure of Merkle tree to take advantage of the probability distribution on where differences are most likely to appear. You can also vary the branching factor. This gives you a space of possible trees, with a range of tradeoffs between the typical number of rounds of interaction vs the typical amount of data that must be communicated. You might be able to choose a parameter setting that is optimal in your setting.

Also, as another optimization, Alice can start by sending Bob the value of some fixed set of her nodes. Notice that your example of sending a list of hashes corresponds to Alice proactively sending the value of all of the leaves. However we might be able to do better by taking advantage of interaction: e.g., if Alice expects that one of her subtrees is probably shared by Bob, she can send just the label on the root of that subtree, and not send anything under that node (e.g., not the hashes of any of the transactions). If she is right and Bob does have that transaction, neither has to do any other work. If she is wrong, then some further interaction and additional data must be exchanged.

Many variations on this basic idea are probably possible.

• Remember, the receiving node doesn't know the order that the transactions are in. If you have the same transaction in the tree, but in a different order, you'll get a different merkle tree hash. Though, now that I think about it, you could sort the transactions, then put them back in correct order when you're done. That would only take about a byte or two per transaction. – Nick ODell Sep 3 '14 at 18:44
• You can also use weaker hashes for the tree, since you just need to get high enough probability to be useful. 20 bytes seems like overkill. Another thing consider is trying to compress the number of rounds, since you'd really want $o(log n)$ rounds in the protocol and have a lot of space in each packet. – Louis Sep 4 '14 at 7:59
• @Louis, I agree the hashes could be shorter; 10-byte hashes would probably suffice, if we used a universal one-way hash (i.e., if we use $H(r,x)$ instead of $H(x)$, where $r$ is a random nonce). A possible risk with going shorter than that is that Alice and Bob might think Bob has all the transactions, when actually Bob is missing one due to a hash collision; I don't know whether that matters in Bitcoin, or whether there's a better solution for that problem. – D.W. Sep 4 '14 at 17:23
• Practically, you can just have Bob send back a long hash of all the blocks he knows after running the protocol. If it's the wrong thing, they can repeat with a new random hash function to get the missing ones – Louis Sep 4 '14 at 19:56