Fast Tip Selection for Burst Message Arrivals on A DAG-based Blockchain Processing Node at Edge

Abstract

With the rapid evolution of blockchain technology, a clear trend is that new blockchain systems (e.g., IOTA) tend to use a Directed Acyclic Graph (DAG) rather a chain structure to organize ledger records. Such a DAG-based blockchain system shows higher scalability as multiple locations are available in the ledger for new message attachment. To decide an attachment location, a popular type of tip selection algorithms follow an approach using weighted random walks on the DAG ledger. In a burst message arrival scenario, however, a processing node deployed at edge using such a method may become a bottleneck because sequentially repeating random walks significantly increases processing delay. In this paper, we propose a new tip selection algorithm for the burst message arrival scenario on an edge node. Our solution abandons the weighted random walk approach, instead, with similar efforts we transfer to calculate in advance the tip selection probability distribution of the DAG ledger. Such a new scheme reduces tip selection to a probability distribution sampling task, which can be done extremely fast. We implement our solution and demonstrate the benefits of our approach by comparing with the random walk approach. We believe our attempt can effectively mitigate the congestion at the edge node and inspire tip selection algorithm design with a new vision for DAG-based blockchain systems.