Bitcoin block propagation - Ultra compression

This solution paper is a sequel to my earlier post on reddit Bitcoin-SV: are terabyte blocks feasible?, I recommend reading that article first as it deals with requirements scoping & feasibility before continuing this paper.

​

https://gist.github.com/stoichammer/b275228fa5583487955c8c2f91829b00

​

Would greatly appreciate feedback and criticism on the above from SV devs. I recently noticed a tweet from @shadders333where he announced a potential solution for block propagation will be announced in the CoinGeek scaling conference. It is purely co-incidental I was interested in this problem for the past few days, and I have no clue about the solution they intend to share. Would love to hear first-hand thoughts from you guys.

----------------------------

Edit: Added a new section to the paper on how it compares with Graphene. Copying the same here as well. 

​

Comparison with Graphene:

Graphene uses techniques such as Bloom filters and invertible bloom lookup tables (IBLTs) to compress blocks with better efficiency when compared to Compact Blocks (BIP-152). Graphene works on a probabilistic model for IBLT decoding, and there is a small chance of failure, in that event the sender must resend the IBLT with double the number of cells, the authors did some empirical testing and found this doubling was sufficient for the very few that actually failed. It seems the Graphene sizes are linearly proportional to the mempool sizes. But practically speaking, we need to take another factor "mempool divergence" into account, as network grows and mempools become larger the divergence increases, and in practice decoding failures will raise. One proposal to counter this is to request blocks from multiple (2/3) peers and merging them together, this decreases the probability of IBLT decoding errors at the cost of additional resources. There is also an open attack vector called the poison block attack where a malicious miner could mine a block with transactions that are held private, this will lead to a inevitable decode failure. Although this attack seems fatal to Graphene’s adoption, there is likely hope that game theoretical PoW underpinnings may come to the rescue.

Graphene distills the block propagation problem into the classical set reconciliation problem (Set theory; order of elements is irrelevant), it builds on the previous academic literature on Set reconciliation which also involved Bloom filters & IBLTs. It discards the concomitant time information of transactions and defaults to implicit ordering, typically canonical (ID sorting). But it supports supplemental order information to be included. If topological ordering of transactions is needed, additional ordering information has to be included at the cost of increasing the size of the block. It complements well with implicit ordering techniques like CTOR(Canonical Transaction ordering), although it deviates from Nakamoto style chronological ordering of transactions within a block.

Whereas Ultra compression (this paper) has a novel approach which leverages the concomitant time information of transactions to its advantage and achieves a much better compression factor. It does not approach the problem as merely that of Set reconciliation and instead by improves efficiency by encoding relative time sequence of transactions into a block.

The primary advantages are as below:

• High compression factor, considerably smaller blocks compared to Graphene.
• Not a probabilistic algorithm, and hence no decoding failures and hence no need for complex recovery mechanisms.
• Mempool divergences are pre-addressed and hence corresponding problems do not arise, the efficiency of packing/unpacking does not get worse as network and mempools grow.
• No serious attack vectors like the poison block attack (at-least not known yet)
• Allows highly concurrent packing and unpacking
• Allows Merkle sub-tree computations concurrently while unpacking
• Highly scalable due to above, Tera-byte blocks & beyond.

Notable disadvantages:

• Places a higher memory load on the system, needed for maintaining additional data structures like maps of seqNo<->transactionIDs
• Packing & Unpacking needed at every hop, passive relaying is not possible. Although the high parallelism ensures very low latency.

In my subsequent post, I will cover a more comprehensive distributed system architecture for a Node that covers the following:

• Parallel Transaction Verification
• Parallel Block processing (under topological ordering)
• Mempool sharding(Intra node)
• UTxO set sharding
• Parallel Merkle subtree computation