This is imperative style pseudo-code, written loosely on Java syntax. It uses mutable data-structures, and is a rough translation of the Haskell snippet (purely functional & hence immutable) provided at - https://gist.github.com/stoichammer/7735abcddec08614a0b46335fe94a65f
class MerkleNode {
String node;
String leftChild;
String rightChild;
A Transpose Merkle Tree (TMT) is a data structure wherein interim nodes are transposed such that the walk from the leaf node to the root node essentially contains the Merkle branch(proof). The leaf & root nodes remain in the same position/s as in a standard Merkle tree.
This post includes,
O(3 log n) space complexity (primary memory).O(log n) nodes.The algorithm needs to store only the node-id, left-child-id, right-child-id for each height of the Merkle tree, hence the 3 log n. And the recursive algorithm shown below simultaneously constructs the intermediate nodes & transposes them appropriately upto the final root node recursively, with this simple structure. The time complexity of TMT construction is comparable to the standar
The article spans across multiple areas, the agenda outline is below:
In the not so distant future, when Bitcoin is ubiquitous, the digital communication ecosystem would be completely reinvented. It is possible that Bitcoin economic model will breathe new life into decades old comm. technologies and protocols that never really took off or were stagnating. At the same time it will open up avenues for a plethora of new services and features that will streamline and simplify things for everyone involved.
Before we dive into the future of digital communications, lets review the current state of the blockchain ecosystem and weed out some possible misconceptions. In the last decade (half actually) we had a Cambrian-explosion of public blockchains/ consensus protocols/ crypto-currencies (coins/ tokens) how many of these will survive & thrive in the coming years? we have arguments at both extremes of the spectrum, some say (maximalists) eventually there will be a single winning blockchain "winner takes all" by comparing blockchains to
This document is part-3 of the series of articles on scaling Bitcoin, I recommend reading part-2 on block propagation before continuing with this paper.
This paper takes a simple yet practical approach to building scalable software; puts to use the Fundamental Theorem of Software Engineering i.e. "We can solve any problem by introducing an extra level of indirection" & other often used software design paradigms. It is an attempt to derive a robust & scalable distributed system architecture which devolves crucial responsibilities to appropriate components. Although the new distributed node architecture is a departure from the legacy monolithic one, it ensures there is no impact to any of the consensus rules of the original Bitcoin protocol (Bitcoin SV).
The design that follows attempts to solve a number of issues; Parallel Transaction Verification & mempool accep
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.