With interest, I read the paper "Bandwidth-Efficient Transaction Relay in Bitcoin" (Erlay Project). It seems quite flawed, and I believe I can offer a better approach.
Let's reconsider full mempool reconciliation. We can train a reconciliation AI model on a CPU. The training times for an ordinary CPU are as follows:
0.147s for 100 transactions, 100 inner Merkle tree nodes
3.984s for 1,000 transactions, 1,000 inner Merkle tree nodes
Very long for 5,000 transactions, 5,000 inner Merkle tree nodes
Now, applying bucketing (sharding by the initial hash byte, which divides the problem into 256 "equal" subproblems) on the same CPU yields:
0.004s * 256 = 1.024s for 1,000 transactions, 1,000 inner Merkle tree nodes, training 256 models on 8 data points each [48 * 256 bytes model]
0.029s * 256 = 7.424s for 5,000 transactions, 5,000 inner Merkle tree nodes, training 256 models on 40 data points each [157 * 256 bytes model]
0.057s * 256 = 14.592s for 10,000 transactions, 10,000 inner Merkle tree nodes, training 256 models on 80 data points each [258 * 256 bytes model]
Surprisingly, it's faster? And it will benefit from future CPU advancements. Maybe mining farms won’t mind?
If Party A sends this 66KB (44KB more realistically) model to Party B, Party B will immediately be able to respond with only the transactions that Party A doesn't have. The best part: notice how the AI model is smaller than a simple vector of hashes? It's about 3x-4x smaller.
Our model (actually, 256 models) will be able to predict the following boolean values based on TX/tree internal node 256-bit hash:
reconcile(model, hash1) = true // I have this object, and it is a TX hash (Merkle tree leaf). It is NOT a root/inner node.
reconcile(model, hash2) = true or false // I don't have this object (false positive/false negative)
reconcile(model, hash3) = false // This object is NOT a TX HASH but a Merkle tree root/inner node hash
Here is the proposed protocol:
ProtocolPacketUnsolicitedData:
field: "block_header": raw_header ([80]byte) // Note: contains the Merkle root
field: "block_height": 814201
ProtocolPacketReconcileRequest:
field: "merkle_root": hash
field: "my_best_model_hash_or_hashes": {model_hash} // Multiple or none, used only by a proxy; otherwise, one
field: "block_height": 814201
ProtocolPacketReconcileModelRequest:
field: "requested_model": model_hash ([32]byte)
ProtocolPacketReconcileModelResponse:
field: "model_hash": model_hash ([32]byte)
field: "model_response": raw_model ([]byte)
ProtocolPacketReconcileResponse:
field: "block_height": 814201
field: "merkle_root": ([32]byte)
field: "model_hash_vector": {model1_hash, model2_hash} ([][32]byte) // Used only by a proxy; otherwise, empty
field: "transactions": raw_txs ([][]byte)
field: "merkle_nodes": raw_inodes_left_right_hashes ([][2][32]byte)
Full node protocol:
A block is mined by us/new TX signed, and added to the chain/mempool respectively.
If it’s a block, we send it to everyone using the unsolicited ProtocolPacketUnsolicitedData packet.
Initialize reconciliation for the just-mined block (height), and perform periodic reconciliation for the next candidate block (height+1).
When a new reconciliation model (based on Merkle root and nodes) is trained, we send it to all peers via ProtocolPacketReconcileRequest.
The other party may download it using ProtocolPacketReconcileModelRequest/ProtocolPacketReconcileModelResponse.
The other party will perform reconciliation and directly send us the objects that we don't have for that specific height/candidate block.
Full node protocol - Handling ProtocolPacketReconcileRequest from another node:
If the block_height is far in the past or future, ignore it.
If the known Merkle root is on the chain or known chain branch, ignore it; we already have this.
If the sender's my_best_model_hash is different, update the my_best_model_hash for this connection and attempt to download the full model using ProtocolPacketReconcileModelRequest.
Once we have the ProtocolPacketReconcileModelResponse (the full model), determine if this is a mempool reconciliation or a block reconciliation based on the block_height.
Perform inference on the model and our view of the mempool/on-chain block. For each mempool/on-chain block object:
For each Merkle internal node, check if the model says the other node thinks it is truly an internal node. If the model is wrong, send the inode object.
For each transaction hash leaf, check if the model says the other node thinks it is truly a transaction hash leaf. If the model is wrong, send the whole transaction.
Send the ProtocolPacketReconcileResponse.
Proxy/Relay/Non-reconciliating node protocol - Handling ProtocolPacketReconcileRequest:
If the block_height is far in the past or future, ignore it.
If the known Merkle root is on the chain or known chain branch, ignore it; we already have this.
When a ProtocolPacketReconcileRequest comes in, set the inbound hash for this connection and add the hash to the outbound bag for all other connections.
Proxy the ProtocolPacketReconcileRequest to all other connections, containing the same block_height, same merkle_root, but their own connection's outbound hash bag set into the my_best_model_hash_or_hashes.
Proxy/Relay/Non-reconciliating node protocol - Handling ProtocolPacketReconcileResponse:
Determine which objects some peers don't have based on their connection's latest available model for that block height/merkle root.
Construct a ProtocolPacketReconcileResponse if they made a request before.
Send the TX data/tree inode data to them.
Proxy/Relay/Non-reconciliating node protocol - Handling ProtocolPacketReconcileModelRequest:
Identify which connection has the inbound model hash.
Set up mapping to send the response based on the model hash to whoever requested it.
Proxy the request to the node that has the inbound model hash, then proxy its response back (and save the response to the connection; this is how the proxy discovers models).