  Path-based transaction (PBT) networks, which settle payments from one user to
another via a path of intermediaries, are a growing area of research. They
overcome the scalability and privacy issues in cryptocurrencies like Bitcoin
and Ethereum by replacing expensive and slow on-chain blockchain operations
with inexpensive and fast off-chain transfers. In the form of credit networks
such as Ripple and Stellar, they also enable low-price real-time gross
settlements across different currencies. For example, SilentWhsipers is a
recently proposed fully distributed credit network relying on path-based
transactions for secure and in particular private payments without a public
ledger. At the core of a decentralized PBT network is a routing algorithm that
discovers transaction paths between payer and payee. During the last year, a
number of routing algorithms have been proposed. However, the existing ad hoc
efforts lack either efficiency or privacy. In this work, we first identify
several efficiency concerns in SilentWhsipers. Armed with this knowledge, we
design and evaluate SpeedyMurmurs, a novel routing algorithm for decentralized
PBT networks using efficient and flexible embedding-based path discovery and
on-demand efficient stabilization to handle the dynamics of a PBT network. Our
simulation study, based on real-world data from the currently deployed Ripple
credit network, indicates that SpeedyMurmurs reduces the overhead of
stabilization by up to two orders of magnitude and the overhead of routing a
transaction by more than a factor of two. Furthermore, using SpeedyMurmurs
maintains at least the same success ratio as decentralized landmark routing,
while providing lower delays. Finally, SpeedyMurmurs achieves key privacy goals
for routing in PBT networks.
