How to linearize your cluster

In the realm of optimizing transaction efficiency and computational resources, the debate between using 64-bit versus 128-bit arithmetic in blockchain technology garners attention. The precision required for separating transaction chunks by feerate—specifically those only $0.004$ sat/vB apart—can be adequately managed with 64-bit arithmetic. This approach is validated by calculating that a multiplier of $M = 461$ allows for this level of differentiation even when cluster sizes are capped at 4 MWU and feerates peak at approximately 10000 sat/vB.

The comparison between the costs associated with 64-bit and 128-bit arithmetic reveals a minimal difference, suggesting that the choice of bit-level may not significantly impact overall performance. The primary computational efforts involve a single division per chunk and several multiplications per transaction for each chunk, whereas the majority of the process—comprising comparisons, additions, and subtractions—is less affected by the choice of arithmetic bit-level. Furthermore, the intensive part of the computation is likely attributed to iterating over nodes and edges and managing the underlying data structures rather than the arithmetic operations themselves.

Additionally, insights from a published paper introduce a theoretical framework for the max-height push-relabel algorithm, indicating an $\mathcal{O}(n^2 \sqrt{m})$ complexity bound. This paper provides methodologies for constructing worst-case scenarios to reach such complexity levels, offering a valuable resource for benchmarking and stress-testing systems under extreme conditions. Such research could inform future decisions on computational strategies, including the optimal use of arithmetic bit-levels in transaction processing and network optimization efforts within blockchain technologies.