Almost sure one-endedness of a random graph model of distributed ledgers

Ken R. Duffy, Jiewei Feng, Christopher King

Published 2023-09-14Version 1

Blockchain and other decentralized databases, known as distributed ledgers, are designed to store information online where all trusted network members can update the data with transparency. The dynamics of ledger's development can be mathematically represented by a directed acyclic graph (DAG). One essential property of a properly functioning shared ledger is that all network members holding a copy of the ledger agree on a sequence of information added to the ledger, which is referred to as consensus and is known to be related to a structural property of DAG called one-endedness. In this paper, we consider a model of distributed ledger with sequential stochastic arrivals that mimic attachment rules from the IOTA cryptocurrency. We first prove that the number of leaves in the random DAG is bounded by a constant infinitely often through the identification of a suitable martingale, and then prove that a sequence of specific events happens infinitely often. Combining those results we establish that, as time goes to infinity, the IOTA DAG is almost surely one-ended.