D-BTC: A Simply Connected Two-Dimensional Blockchain Protocol

This work deals with questions of enhancing the scalability and security of linear chain Bitcoin by introducing a D-BTC (Domino Bitcoin) protocol, supported by a simply connected two-dimensional structure. The paper seeks to answer the question: can the linear topology of Bitcoin be replaced by a richer geometric structure that simultaneously (i) enlarges the number of valid positions where parallel mining can occur, and (ii) strengthens the asymptotic decay of the double-spend reversal probability? In the D-BTC protocol, the blocks, called B-dominoes (Bitcoin dominoes) are organized as a finite connected region subset of Z2 without holes, also called a lattice. Simple connectivity plays a central role in D-BTC and to mine a (valid) B-domino, a miner has to compute four PoW (Proof of Work), corresponding to cardinal directions, allowing them to add it to the frontier of the lattice, under the constraint that the new lattice is simply connected. We introduce a new deterministic consensus based on maximization of the lattice surface. By using a simple version of the isoperimetric inequality, we see that the frontier size grows as Ω(n), where n is the lattice size. Following the Nakamoto’s heuristic, and under the honest majority assumption, a double-spending attack is successful with probability decaying exponentially in k2, where k is the minimum Manhattan distance of the concerned B-domino from the lattice frontier. Additionally, we set up implementations and experiments to demonstrate the practical viability of the protocol with authentic gossip-based message propagation and complete Merkle tree verification.