Aurora: a probabilistic algorithm for distributed ledgers enabling trustless synchronization and transaction inclusion verification

08/09/2021
by   Federico Matteo Benčić, et al.
0

A new node joining a blockchain network first synchronizes with the network to verify ledger state by downloading the entire ledger history. We present Aurora, a probabilistic algorithm that identifies honest nodes for transient or persistent communication in the presence of malicious nodes in a blockchain network, or ceases operation if it is unable to do so. The algorithm allows a node joining the network to make an informed decision about its next synchronization step or to verify that a transaction is contained in a valid ledger block without downloading the entire ledger or even the header chain. The algorithm constructs a Directed Acyclic Graph on the network topology to select a subset of nodes including a predefined number of honest nodes with a given probability. It is evaluated on a Bitcoin-like network topology using an open-source blockchain simulator. We investigate algorithm performance and analyze its communication complexity. Our results show that the algorithm facilitates trustless interactions of resource-constrained nodes with a blockchain network containing malicious nodes to enable a leaner initial blockchain download or an efficient and trustless transaction inclusion verification. Moreover, the algorithm can be implemented without any changes to the existing consensus protocol.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset