Xthinner is a new block propagation protocol which I have been working on. It takes advantage of LTOR to give about 99.6% compression for blocks, as long as all of the transactions in the block were previously transmitted. That’s about 13 bits (1.6 bytes) per transaction. Xthinner is designed to be fault-tolerant, and to handle situations in which the sender and receiver’s mempools are not well synchronized with gracefully degrading performance — missing transactions or other decoding errors can be detected and corrected with one or (rarely) two additional round trips of communication. My expectation is that when it is finished, it will perform about 4x to 6x better than Compact Blocks and Xthin for block propagation. Relative to Graphene, I expect Xthinner to perform similarly under ideal circumstances (better than Graphene v1, slightly worse than Graphene v2), but much better under strenuous conditions (i.e. mempool desynchrony).
The current development status of Xthinner is as follows:
- Python proof-of-concept encoder/decoder — done 2018-09-15
- Detailed informal writeup of the encoding scheme — done 2018-09-29
- Modify TxMemPool to allow iterating on a view sorted by TxId — done 2018-11-26
- Basic C++ segment encoder — done 2018-11-26
- Basic c++ segment decoder — done 2018-11-26
- Checksums for error detection — done 2018-12-09
- Serialization/deserialization — done 2018-12-09
- Prefilled transactions, coinbase handling, and non-mempool transactions — done 2018-12-25
- Missing/extra transactions, re-requests, and handling mempool desynchrony for segment decoding — done 2019-01-12
- Block transmission coupling the block header with one or more Xthinner segments — 50% 2019-01-12
- Missing/extra transactions, re-requests, and handling mempool desynchrony for block decoding
- Integration with Bitcoin ABC networking code
- Networking testing on regtest/testnet/mainnet with real blocks
- Write BIP/BUIP and formal spec
- Bitcoin ABC pull request and begin of code review
- Unit tests, performance tests, benchmarks — started
- Bitcoin Unlimited pull request and begin of code review
- Alpha release of binaries for testing or low-security block relay networks
- Merging code into ABC/BU, disabled-by-default
- Complete security review
- Enable by default in ABC and/or BU
- (Optional) parallelize encoding/decoding of blocks
Following is the debugging output from a test run done with coherent sender/recipient mempools with a 1.25 million tx block, edited for readability:
Testing Xthinner on a block with 1250003 transactions with sender mempool size 2500000 and recipient mempool size 2500000 Tx/Block creation took 262 sec, 104853 ns/tx (mempool) CTOR block sorting took 2467 ms, 987 ns/tx (mempool) Encoding is 1444761 pushBytes, 2889520 1-bit commands, 103770 checksum bytes total 1910345 bytes, 12.23 bits/tx Single-threaded encoding took 2924 ms, 1169 ns/tx (mempool) Serialization/deserialization took 1089 ms, 435 ns/tx (mempool) Single-threaded decoding took 1912314 usec, 764 ns/tx (mempool) Filling missing slots and handling checksum errors took 0 rounds and 12 usec, 0 ns/tx (mempool) Blocks match! *** No errors detected
If each transaction were 400 bytes on average, this block would be 500 MB, and it was encoded in 1.9 MB of data, a 99.618% reduction in size. Real-world performance is likely to be somewhat worse than this, as it’s not likely that 100% of the block’s transactions will always be in the recipient’s mempool, but the performance reduction from mempool desychrony is smooth and predictable. If the recipient is missing 10% of the sender’s transactions, and has another 10% that the sender does not have, the transaction list is still able to be successfully transmitted and decoded, although in that case it usually takes 2.5 round trips to do so, and the overall compression ratio ends up being around 68% instead of 99.6%.
Anybody who wishes can view the WIP Xthinner code here.
Once Xthinner is finished, I intend to start working on Blocktorrent. Blocktorrent is a method for breaking a block into small independently verifiable chunks for transmission, where each chunk is about one IP packet (a bit less than 1500 bytes) in size. In the same way that Bittorrent was faster than Napster, Blocktorrent should be faster than Xthin(ner). Currently, one of the big limitations on block propagation performance is that a node cannot forward the first byte of a block until the last byte of the block has been received and completely validated. Blocktorrent will change that, and allow nodes to forward each IP packet shortly after that packet was received, regardless of whether any other packets have also been received and regardless of the order in which the packets are received. This should dramatically improve the bandwidth utilization efficiency of nodes during block propagation, and should reduce the block propagation latency for reaching the full network quite a lot — my current estimate is about 10x improvement over Xthinner. Blocktorrent achieves this partial validation of small chunks by taking advantage of Bitcoin blocks’ Merkle tree structure. Chunks of transactions are transmitted in a packet along with enough data from the rest of the Merkle tree’s internal nodes to allow for that chunk of transactions to be validated back to the Merkle root, the block header, and the mining PoW, thereby ensuring that packet being forwarded is not invalid spam data used solely for a DoS attack. (Forwarding DoS attacks to other nodes is bad.) Each chunk will contain an Xthinner segment to encode TXIDs. My performance target with Blocktorrent is to be able to propagate a 1 GB block in about 5-10 seconds to all nodes in the network that have 100 Mbps connectivity and quad core CPUs.