Settling Payments Fast and Private: Efficient Decentralized Routing for\n Path-Based Transactions

Abstract

Path-based transaction (PBT) networks, which settle payments from one user to\nanother via a path of intermediaries, are a growing area of research. They\novercome the scalability and privacy issues in cryptocurrencies like Bitcoin\nand Ethereum by replacing expensive and slow on-chain blockchain operations\nwith inexpensive and fast off-chain transfers. In the form of credit networks\nsuch as Ripple and Stellar, they also enable low-price real-time gross\nsettlements across different currencies. For example, SilentWhsipers is a\nrecently proposed fully distributed credit network relying on path-based\ntransactions for secure and in particular private payments without a public\nledger. At the core of a decentralized PBT network is a routing algorithm that\ndiscovers transaction paths between payer and payee. During the last year, a\nnumber of routing algorithms have been proposed. However, the existing ad hoc\nefforts lack either efficiency or privacy. In this work, we first identify\nseveral efficiency concerns in SilentWhsipers. Armed with this knowledge, we\ndesign and evaluate SpeedyMurmurs, a novel routing algorithm for decentralized\nPBT networks using efficient and flexible embedding-based path discovery and\non-demand efficient stabilization to handle the dynamics of a PBT network. Our\nsimulation study, based on real-world data from the currently deployed Ripple\ncredit network, indicates that SpeedyMurmurs reduces the overhead of\nstabilization by up to two orders of magnitude and the overhead of routing a\ntransaction by more than a factor of two. Furthermore, using SpeedyMurmurs\nmaintains at least the same success ratio as decentralized landmark routing,\nwhile providing lower delays. Finally, SpeedyMurmurs achieves key privacy goals\nfor routing in PBT networks.\n