Distributed Ledger Witness Selection in Bounded Width Directed Acyclic Graphs

Abstract

This work explores a new low-latency distributed ledger structure based on bounded width directed acyclic graphs (DAGs). In this design, each user has their own blockchain traceable back to a common root. These individual chains mutually witness each other to confirm transactions and form a global partially ordered set of events. The number of witness hashes required to establish new blocks is defined as the “DAG width”. This width has an upper bound which of the total number of users in the system, though the actual number of witnesses required is usually far less. In this paper we mathematically model the expected DAG width using analytical techniques from the near miss birthday problem and simulate expected widths for expected network latency and user activity.