Almost Sure One-Endedness of a Random Graph Model of Distributed Ledgers

Distributed ledgers (DLs) are modern decentralized databases where trusted network members can transparently update data while maintaining security. IOTA is an exemplar alternative to the well-known Bitcoin protocol, and such alternatives, which aim to overcome shortcomings, have gained increasing attention recently. These systems warrant deeper theoretical analysis using directed acyclic graph (DAG) models. One essential property of a properly functioning DL is that all network members holding a copy of the database agree on the sequence of information added, which is referred to as consensus and is known to be related to a structural property of DAGs called one-endedness. In this paper, we consider a model of a DL with sequential stochastic arrivals that mimic IOTA’s attachment rules. Although the resulting DAG model is more complex than Bitcoin, we demonstrate that as time goes to infinity, the IOTA DAG almost surely achieves one-endedness.