Skip to content

Instantly share code, notes, and snippets.

@stoichammer
stoichammer / imperative pseudo-code.md
Last active December 20, 2019 04:49
Imperative style pseudo-code for the Transpose Merkle Tree construction.

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;
@stoichammer
stoichammer / Transpose-Merkle-Tree.md
Last active February 9, 2020 12:54
Introducing the Transpose Merkle Tree

Introducing the Transpose Merkle Tree

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,

  • a highly efficient algorithm to compute the TMT with only O(3 log n) space complexity (primary memory).
  • a compact pre-ready data-structure, that can be persisted in a graph database(Neo4j), and can readily serve Merkle branch/paths trivially, traversal (by DB engine) of only 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

@stoichammer
stoichammer / Allegory & AllPay.md
Last active March 2, 2020 05:53
Allegory & AllPay protocol suite
@stoichammer
stoichammer / Bitcoin-paymail-protocol-and-beyond.md
Last active December 23, 2020 01:30
Bitcoin user-friendly identity, the paymail protocol and beyond!

Bitcoin user-friendly identity, the paymail protocol and beyond!

The article spans across multiple areas, the agenda outline is below:

  • Philosophical underpinnings of online identity. High level view of the evolution of digital identity centralized → federated → self-sovereign (user autonomy).
  • A critique of the paymail protocol, its strengths and limitations
  • Establish the need for a new naming protocol suite with a fundamental focus on user autonomy.
  • An attempt to present dispassionate arguments without social bias
@stoichammer
stoichammer / Digital-communications-Bitcoin-era.md
Last active May 29, 2019 05:25
Digital communications in the Bitcoin era.

How Bitcoin will disrupt digital communication

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

@stoichammer
stoichammer / Mangrove.md
Last active June 18, 2019 15:40
Mangrove - Bitcoin node distributed system architecture

Mangrove - Bitcoin node distributed system architecture

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.

Preface

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

@stoichammer
stoichammer / Bitcoin-block-propagation-Ultra-compression.md
Last active August 13, 2019 18:39
Bitcoin block propagation - Ultra compression

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.

Abstract:

  • A node, alongside its mempool, now maintains a 'stateful' index of unconfirmed transactions exchanged with each of its peers. So each node maintains a map of seqNo<->transactionIDs for every active peer connection.
  • Currently when a miner succeeds in the mining attempt, i.e. the nonce that produces the hash less than the network difficulty it transmits the entire contents of the block (legacy or Compact blocks BIP-152) to its peers.
  • In this proposal the miner can efficiently (in space & time) transmit a packed block containing the sequence of indices to its peer.
  • The peer unpacks the block, effectively reconstructing