The Lightning Network aims to solve Bitcoin's scalability problem by providing a way to transact with minimal use of the blockchain. Instead, payments are routed over payment channel networks. This routing is done by LN clients, which use cost functions to compute the optimal transaction path. With the use of onion routing, LN tries to hide the identity of transaction participants from each other. However, the cost functions of these routing protocols are currently too deterministic, making it possible for curious transaction participants to comprise the identity of sender and receiver by computing the optimal path themselves.
Here we show that we can increase the anonymity of this network by adding randomness to these routing algorithms. More specifically, during path computation we will randomly deviate from the optimal path by hopping to a random node and continue by computing a new optimal path from there. The unpredictability of this process improves the anonymity of the network, such that malicious nodes can identify the sender and recipient of transactions with negligible probability in most cases.