On State Transition Probability and Performance of Direct Acyclic Graph Based Ledgers

Direct acyclic graph (DAG) based ledgers with multi-chain structures aim to solve the technical bottlenecks associated with classical blockchain technologies in the Internet of Things (IoT). The basic working principle of DAG-based ledgers is to validate new transactions by previous transactions in order to be added to the system. During the tip selection process in the unsteady regime, the state transition probability refers to the probability of a transaction changing from the initial state to an arbitrary state. The state transition probability plays an indispensable role in the performance and security analysis of the IoT relying on DAG-based ledgers. In this paper, we derive the exact expression and an approximate expression of the state transition probability, which both are in closed form. In addition, we propose and analyze three performance metrics, i.e., the expected cumulative weight, the expected number of steps, and the confirmation failure probability, which are derived from the state transition probability and greatly enrich the performance analysis and evaluation of the IoT. Markov chain Monte Carlo (MCMC) simulations are carried out to verify the derived analytical results and provide insight into the IoT using DAG-based ledgers.