[Back]

D. Lobmaier:
"Routing Algorithms in Blockchain-based Payment Channel Networks";
Supervisor: S. Schulte; Institute of Information Systems Engineering, Distributed Systems Group, 2019; final examination: 2020-01-21.

Payment Channel Networks (PCNs) are a technology that has been developed to overcome the scalability problems of blockchains like Bitcoin or Ethereum. Payments are not immediately settled on the blockchain but stored in a so-called payment channel which connects payer and payee. Hence, interactions with the blockchain are minimized and only necessary on opening and closing a channel. If we combine many of such payment channels, we obtain a PCN that enables users to reach further away destinations by using foreign channels for a fee. The problem that needs to be solved is finding a path of payment channels that reaches the destination and meets several additional requirements. The core is a routing algorithm which has to scale well and has to fit the individual objectives of PCN users. Recent contributions to this topic are promising but lack a profound evaluation in a realistic setting. Therefore, we collect multiple requirements for routing in PCNs and compare them to protocols originating from the field of Wireless Sensor Networks (WSNs) which have to overcome similar challenges regarding scalability. Based on this analysis, the WSN routing algorithms E-TORA, M-DART and TERP promise the highest compatibility. To evaluate these routing algorithms under realistic conditions, we use a novel simulation approach incorporating PCN users with rational behavior. For this, we substantially rework an existing simulation approach and extend it with a formally described behavior model. Then, we analyze the algorithms in different simulated scenarios that are based on our behavior model and receive the following results: E-TORA finds the shortest payment paths, M-DART ensures the lowest fees and TERP reaches the highest success ratio. In general, TERP corresponds most closely to the requirements for routing algorithms in PCNs.

Payment Channel Networks (PCNs) sind eine Technologie, die entwickelt worden ist, um die Skalierungsprobleme von Blockchains wie Bitcoin oder Ethereum zu lösen. Dabei werden Zahlungen nicht mehr wie gewohnt über die Blockchain abgewickelt, sondern in Bezahlkanälen (engl. "Payment Channels") zwischen zwei Partnern gespeichert. Interaktionen mit der Blockchain sind nur dann notwendig, wenn ein Kanal geöffnet oder geschlossen wird. Betrachtet man nun eine Vielzahl von Kanälen, dann spricht man von einem PCN. Innerhalb eines solchen Netzwerkes können auch fremde Kanäle gegen eine Gebühr genutzt werden, um ferne Empfänger zu erreichen. Das Problem, das sich hierbei ergibt ist das Finden einer Abfolge von Kanälen, die zum Ziel führt und gleichzeitig noch weitere Anforderungen erfüllt. Das Herzstück bildet dabei ein Routing Algorithmus, der sowohl gut skalieren muss, als auch auf die individuellen Bedürfnisse des Benutzers abgestimmt werden sollte. Bisherige Lösungsansätze wirken zwar vielversprechend, jedoch wurde noch keiner unter realitätsnahen Bedingungen getestet. Deswegen haben wir in dieser Arbeit zuerst Anforderungen für Routing Algorithmen in PCNs gesammelt und diese dann mit Protokollen aus dem Forschungsfeld der Sensornetze (engl. "Wireless Sensor Networks") verglichen, da besonders im Bereich Skalierbarkeit Gemeinsamkeiten bestehen. Die drei Algorithmen E-TORA, M-DART und TERP haben sich dabei als die geeignetsten Protokolle herausgestellt. Um diese Algorithmen zu evaluieren, haben wir uns eines neuartigen Simulationsansatzes bedient, bei dem die einzelnen Teilnehmer eines PCN über rationales Verhalten verfügen, um eine möglichst hohe Realitätsnähe zu gewährleisten. Dazu ist ein bestehender Simulator für PCNs grundlegend überarbeitet und um ein formal definiertes Verhaltensmodell erweitert worden. Wir haben die Algorithmen in verschiedenen Szenarien, basierend auf unserem Verhaltensmodell, simuliert und bei der Auswertung der Daten das folgende Ergebnis erhalten: E-TORA findet die kürzesten Routen, M-DART garantiert die niedrigsten Kosten und TERP hat im Mittel die höchste Erfolgsrate. Generell überzeugt das Protokoll TERP am meisten, da es die größte Übereinstimmung mit den definierten Anforderungen aufweist.

Blockchain / Payment Channel Networks / Simulation / Routing