Source-linked AI summary
Settling Payments Fast and Private: Efficient Decentralized Routing for Path-Based Transactions
Stefanie Roos, Pedro Moreno-Sanchez, Aniket Kate, Ian Goldberg
TL;DR
Routing algorithms are central to PBT effectiveness, efficiency, scalability, and privacy, but existing approaches have limitations for dynamic, weighted credit networks. SpeedyMurmurs addresses these constraints with embedding-based routing and on-demand stabilization, achieving strong performance while preserving key privacy goals.
Problem
PBT routing must support effectiveness, efficiency, scalability, and privacy, while existing approaches such as VOUTE and SilentWhispers have limitations for weighted, directed, and dynamically changing credit networks.
Method
SpeedyMurmurs combines privacy-preserving embedding-based routing with credit-aware path selection and on-demand stabilization for decentralized PBT networks.
Results
SpeedyMurmurs achieved higher performance than SilentWhispers across all considered metrics in the static scenario and maintained high success while reducing routing and stabilization overhead.
Takeaways & Limitations
SpeedyMurmurs provides an efficient decentralized routing approach that retains key value and sender/receiver privacy for credit, payment-channel, and inter-blockchain networks.
Takeaways & Limitations
VOUTE is not directly suitable for PBT networks because their links are directed, weighted, and frequently changed by successful transactions.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
PBT networks use off-chain paths to address blockchain scalability, efficiency, interoperability, and privacy concerns. The paper presents SpeedyMurmurs as a fully distributed routing algorithm designed to improve efficiency while preserving privacy.
- PBT networks use paths of intermediaries and off-chain transfers to settle payments between users.Credit networks such as Ripple and Stellar also support real-time gross settlements across currencies and assets.
- Routing is central to PBT effectiveness, efficiency, and scalability because it finds sufficiently funded paths before payment settlement.The paper additionally identifies privacy as essential because routing can reveal transaction values, participant identities, or debts.
- Existing PBT routing approaches lack at least one of privacy, efficiency, or scalability.Ripple and Stellar use a public blockchain, while Canal centralizes network and transaction information at one server.
- SpeedyMurmurs combines embedding-based path discovery with on-demand stabilization for decentralized PBT networks.It extends VOUTE to handle weighted links and link-weight changes arising from transfers.
- SpeedyMurmurs performs transactions at about twice SilentWhispers’ speed and reduces transaction communication overhead by at least a factor of two.The evaluation models Ripple transactions from 2013 to 2016 and reports similar or higher effectiveness.
- SpeedyMurmurs reduces link-change management overhead by 2–3 orders of magnitude except during rare rapid-growth phases.It also provides value privacy and sender/receiver privacy against the adversary model considered.
A. PBT Networks
PBT networks represent transferable funds as weighted links and require routing before secure path settlement. The section explains landmark routing and identifies SilentWhispers weaknesses in stabilization, path length, overhead, and concurrency.
- PBT payments traverse intermediate users who adjust pairwise links to settle funds between sender and receiver.Routing must first find a path on which each link can support the transfer amount.
- Landmark routing computes selected sender-to-receiver paths through well-connected intermediate landmarks instead of using cost-intensive max-flow computation.Multiple landmarks increase the number of computed paths.
- Landmarks periodically construct forward and reverse BFS spanning trees to support paths from senders through landmarks to receivers.Path discovery concatenates the sender-to-landmark reverse path with the landmark-to-receiver forward path.
- SilentWhispers uses landmark-centered routing, multiparty computation, and periodic BFSs to discover paths and determine transferred amounts.Its probe operation computes available path credit using secret sharing while padding hides path length.
- Periodic tree creation can both react too slowly to network changes and recompute unchanged network regions unnecessarily.These effects can produce outdated routing information and additional stabilization overhead.
- Landmark-centered paths can be unnecessarily long, increasing delay and the chance that one link lacks sufficient funds.This occurs when shorter direct links exist outside the spanning tree or when sender and receiver share a branch.
- SilentWhispers’ probe operation has transaction overhead quadratic in the number of landmarks and lacks a suitable concurrency solution.Its alternatives either risk later failures from overcommitted credit or block links that could support multiple transactions.
C. Embedding-based Routing
Embedding-based routing assigns node coordinates and forwards toward destinations using coordinate distance, allowing shortcuts beyond a spanning tree. VOUTE adds anonymous addressing and on-demand adaptation for dynamic route-restricted networks.
- Embedding-based routing assigns coordinates to nodes and forwards messages according to distances between node and destination coordinates.Greedy embeddings can use links outside the spanning tree after coordinates are assigned.
- Embedding-based routing has no guarantee that shortcut routes exist, so spanning-tree links remain necessary for routing guarantees.Without shortcuts, embedding-based routing is identical to tree-only routing.
- Prefix Embedding assigns vector coordinates by appending child indices along a landmark-rooted spanning tree.Its coordinate distance corresponds to shortest-path length in that tree.
- Nodes using Prefix Embedding select the neighbor closest to the receiver’s coordinate distance, and Figure 1 contrasts tree-based routing schemes.The figure also illustrates the coordinate assignment.
- VOUTE builds on Prefix Embedding for anonymous and efficient message delivery in dynamic route-restricted networks.It replaces receiver coordinates with anonymous return addresses and uses keyed hashes to support forwarding.
- VOUTE replaces low-entropy child-enumeration indices with random b-bit numbers, making unknown coordinates computationally infeasible to guess.The passage gives b = 128 as an example.
- VOUTE uses on-demand stabilization rather than periodic spanning-tree reconstruction and retains recent neighbor invitations to react quickly to dynamics.New links trigger invitations from nodes already in the spanning tree.
2) Limitations of VOUTE:
VOUTE cannot be directly applied to PBT networks because its link, dynamics, and concurrency assumptions differ from payment settings. PBT adaptations must handle directed weighted links, changing balances, and probe-payment interactions.
- 2) Limitations of VOUTE:: VOUTE’s application to PBT scenarios is not straightforward because its assumptions conflict with payment-channel topology and state changes.The section frames these differences as limitations that must be overcome before deployment in PBT routing.
- 2) Limitations of VOUTE:: VOUTE assumes undirected, unweighted links, whereas PBT networks use directed, weighted links whose funds may be insufficient for a payment.Applying VOUTE therefore requires algorithms that handle weighted links and transfers.
- 2) Limitations of VOUTE:: VOUTE models dynamics as nodes joining or leaving, but PBT networks primarily change through link-weight updates caused by successful transactions.Reacting to every such change would likely be inefficient, making adaptation timing important.
- 2) Limitations of VOUTE:: VOUTE does not address concurrency because message transmission does not change link capacity, unlike separated probe and payment operations in SilentWhispers.A PBT variant therefore requires a new concurrency algorithm.
1) Operations:
Routing in a PBT network is specified through route initialization, credit updates, and payment-path discovery, with correctness requiring funded paths and no overpayment. The framework also models distributed privacy threats and excludes denial-of-service handling from routing.
- Operations:: Routing comprises setRoutes, setCred, and routePay for initializing information, updating link credit, and returning funded payment paths.setRoutes uses landmarks; setCred changes w(u, v); routePay returns path-and-funding tuples.
- Operations:: Correctness requires routing no more than the requested value and selecting paths with sufficient funds.A transaction may be partially funded when network liquidity is insufficient, while remaining correct under the stated definition.
- Operations:: The adversary controls a subset of nodes but cannot freely choose which users to compromise, and primarily targets privacy rather than large-scale denial of service.Detection and expulsion of malicious nodes are outside this paper’s routing scope.
- Operations:: Privacy analysis also considers a stronger adversary with a global topology view, despite the limits of the overall adversary model.This stronger model is used to define value-privacy goals.
C. Privacy Goals
The paper treats transaction privacy as hiding payment values and the sender and receiver identities, alongside routing performance measured by success, delay, and overhead. These goals are evaluated under explicit assumptions about compromised users and network visibility.
- Privacy Goals: Transaction privacy combines value privacy with sender and receiver privacy.The paper uses transaction privacy for satisfying all three notions.
- Privacy Goals: Value privacy hides the total transaction value when non-compromised users transact without compromised intermediate nodes.A weaker form remains possible if at least one employed path has no compromised nodes.
- Privacy Goals: Sender privacy prevents identifying the sender unless the attacker has complete knowledge of the sender’s incoming links.Controlling all incoming neighbors does not by itself guarantee certainty when the attacker lacks a global view.
- Privacy Goals: Routing performance is characterized by success ratio, hop delay, transaction overhead, and stabilization overhead.Success ratio captures completed transactions; delay measures termination relative to initiation, while overhead relates to congestion and device load.
IV. OUR CONSTRUCTION
SpeedyMurmurs uses landmark-specific embeddings, adaptive credit updates, and constrained path discovery to route payments in a dynamic distributed PBT network. Its routing procedure splits payments across landmark paths while preserving correctness through guaranteed-credit checks.
- IV. OUR CONSTRUCTION: The construction assumes local neighbor-link information, authenticated confidential channels, and publicly known landmarks.It abstracts away payment and accountability details while retaining the network’s dynamic character.
- IV. OUR CONSTRUCTION: setRoutes builds one embedding per landmark, first using bidirectional links and then adding nodes through unidirectional links.The embedding process assigns landmark-based coordinates across the connected graph.
- IV. OUR CONSTRUCTION: setCred adapts embeddings when links are added or removed, replacing unsuitable parent relations to increase funded spanning-tree connections.Coordinate changes remove affected descendants’ coordinates before they choose new parents.
- IV. OUR CONSTRUCTION: routePay returns anonymous receiver addresses, randomly splits the value across landmark paths, and discovers routes restricted to links with sufficient guaranteed credit.The algorithm prefers paths with high funds and proactively reserves guaranteed available credit under concurrency.
- IV. OUR CONSTRUCTION: Algorithm 3 achieves correctness because the path shares sum to c and every selected link has guaranteed credit at least equal to its assigned share.The condition is expressed as w(e) ≥ wA(e) ≥ ci on each path.
D. Parameters
SpeedyMurmurs’ performance depends on the number of landmarks, repeated transaction attempts, retry timing, and landmark selection. These parameters jointly affect overhead, delay, and success ratio.
- D. Parameters: The number of landmarks controls returned paths and increases routing and stabilization overhead roughly linearly.Delay tends to increase with the longest route across embeddings, while success-ratio effects depend on the scenario.
- D. Parameters: Repeated attempts let a sender retry a transaction up to a times, with random intervals bounded by an interval of length tl.Each retry uses different path shares for the same sender, receiver, and value.
- D. Parameters: Landmark choice affects performance, with financially prominent nodes potentially producing shallower spanning trees and higher performance.The supplied passage identifies landmark degree and tree depth as relevant factors.
E. Privacy Analysis
SpeedyMurmurs adapts privacy-preserving routing techniques to decentralized credit networks and claims privacy under specified adversary conditions. Its guarantees cover value, sender, and receiver privacy, while partial path compromise can reveal information about transaction value.
- Value Privacy: Value privacy holds when an adversary compromises no user on the routing paths, because point-to-point communications conceal the routed value.The guarantee applies to transactions between non-compromised users under the stated adversary condition.
- Value Privacy: Partial compromise of routing paths can let an adversary estimate the transaction value from observed positive shares.Knowing one share establishes c ≥ c_i, while uniform positive splitting permits an estimate of |L| ∗ c_i.
- Sender Privacy: Sender privacy follows because an anonymous routing address does not reveal whether the sender is s or another user connected through uncompromised links.The argument relies on corresponding VOUTE proofs.
- Receiver Privacy: Receiver privacy follows because an anonymous return address does not reveal whether r is the actual receiver or another connected receiver.The adversary cannot fully determine the intended receiver through direct or uncompromised paths.
- Design: SpeedyMurmurs adapts VOUTE to credit networks through two-phase construction, on-demand maintenance, adaptive path discovery, and credit splitting before discovery.The design handles unidirectional links, selects links using available credit and node coordinates, and supports concurrency.
V. PERFORMANCE EVALUATION
The evaluation compares SpeedyMurmurs with SilentWhispers and other routing approaches using simulations of static and evolving credit networks. It measures transaction success, delay, routing overhead, and stabilization effects under varied network and landmark parameters.
- Research Questions: The evaluation compares SpeedyMurmurs with SilentWhispers’ landmark-centered routing on success ratio, delay, and overhead using real-world data.It also examines the effects of routing, credit assignment, dynamic stabilization, and other approach choices.
- Simulation Model: The simulation executes routing and payments to assess stabilization overhead from link changes, while omitting security measures that do not affect routing performance.Link setup and related cryptographic details are excluded from the performance evaluation.
- Simulation Model: The model simulates temporally ordered transactions, link changes, and periodic spanning-tree recomputations, without modeling concurrency because realistic latency and bandwidth models were unavailable.This event sequence is used to construct the simulated network evolution.
- Simulation Modes: Two modes evaluate static networks with post-transaction repair and dynamic networks with transactions, node churn, and changing extended credit.The dynamic mode changes both network structure and link weights over time.
- Parameters and Baselines: The study varies tree count, transaction attempts, retry intervals, and SilentWhispers’ tree-recomputation epoch, while comparing maximal-degree and random landmark selection.Additional baselines include distributed Ford-Fulkerson and tree-only routing.
B. Dataset
The evaluation uses cleaned Ripple data to compare routing schemes in static and evolving networks, examining performance, stabilization, configuration choices, and dynamics. Results favor SpeedyMurmurs on static metrics and show substantially lower on-demand stabilization overhead, while performance varies with network changes.
- Dataset and simulation: The evaluation derives static and evolving-network datasets from a complete November 2016 Ripple crawl plus historical link modifications and transactions.The evolving setup initializes links that appear later with zero weight and replays transactions and link changes over time.
- Dataset and simulation: The simulations compare Ford-Fulkerson, SilentWhispers, and SpeedyMurmurs using three landmarks, two attempts, and epochs of roughly one day.The dynamic evaluation starts from an initial network and applies the Ripple transaction and link-change sequence.
- Stabilization: On-demand stabilization required a few thousand messages per epoch, compared with more than half a million for periodic tree rebuilding in the static evaluation.The authors caution that this advantage is partly attributable to limited link-value changes and static-simulation dynamics.
- Configuration choices: Increasing the number of trees raised delays and could reduce SpeedyMurmurs’ success ratio, while additional attempts produced only a slight success increase with linear transaction overhead.The observed success decrease with more trees reflects the greater likelihood that at least one path lacks sufficient credit.
- Dynamic evaluation: In dynamic Ripple replay, stabilization overhead and success ratio varied with transaction and link-change frequency; SilentWhispers eventually achieved a higher success ratio than SpeedyMurmurs.SpeedyMurmurs’ stabilization was usually below 100 messages per epoch but reached about 10^9 during periods of frequent change.
- Static evaluation: SpeedyMurmurs outperformed SilentWhispers on all considered metrics in the static scenario, while greedy embeddings nearly halved path length and transaction overhead.Greedy embeddings also increased success ratio through shorter paths and a lower probability of encountering insufficient credit.
VI. RELATED WORK
Prior routing approaches trade off efficiency, decentralization, path selection, or privacy. SpeedyMurmurs is presented as a higher-performing distributed approach that retains the privacy notions of interest.
- Existing algorithms may not scale because their runtimes are O(V^3) or O(V^2 log(E)).
- Public ledgers enable efficient routing but expose credit relationships and transaction activity, motivating decentralized networks without public logs.
- Flare exposes all link weights within each node’s k-neighborhood and propagates credit updates across that neighborhood.For k ≥3, each credit change can generate possibly hundreds of messages, creating privacy and efficiency concerns.
- Canal uses a trusted central party to compute spanning-tree paths and recompute trees under network dynamics, limiting decentralization and scalability.
- PrivPay adds trusted hardware to Canal but remains centralized, leaving low scalability and a single point of failure; it also motivates value and sender/receiver privacy notions.
- SilentWhispers uses landmark rendezvous paths, so every route passes a landmark even when sender and receiver share a branch, potentially harming performance.
- SpeedyMurmurs is reported to provide higher overall performance than state-of-the-art routing approaches while achieving the privacy notions of interest.
VII. CONCLUSION AND FUTURE WORK
The paper presents SpeedyMurmurs as an efficient, private routing algorithm for completely decentralized PBT networks. It also identifies dynamic stabilization switching as a direction for future work.
- SpeedyMurmurs targets completely decentralized PBT networks with efficient routing, high success probability, and value plus sender/receiver privacy.
- On-demand and periodic stabilization suit different phases of a PBT network’s evolution, motivating future work on dynamically switching between them.