header-langage
简体中文
English
Tiếng Việt
Scan to Download the APP
Partnered With:

Hardcore | A Comprehensive Study on Routing Problems in Payment Networks

Read this article in 15 Minutes
The payment network has become one of the most popular blockchain research and engineering practice directions.
Original source: Shor, Ph.D., Shanghai Jiaotong University


Blockchain is often criticized for the transaction throughput limit of Layer 1, offline payment network (off -chain payment channel network, PCN, hereinafter collectively referred to as "payment network") provides a solution of "offline payment + online settlement", which empowers payment in the blockchain world (and its generalized various interactions) almost unlimited transaction throughput. Therefore, the payment network has become one of the most popular blockchain research and engineering practice directions.


After years of development of international scholars and projects, there have been a large number of research papers and Engineering practice is no longer easy to read and understand in detail. However, for this important research direction at the current stage, although most people in the blockchain field have an understanding of its basic ideas, there are not many domestic geeks and scholars who have comprehensively tracked its latest developments.


This review series is aimed at geeks and academics interested in this field, dissecting several direction, summarize the latest research progress, and put forward the author's thinking. The author is a fellow of Nervos Shor who loves research and is now a Ph.D. student at Shanghai Jiaotong University.


In this article, we assume that readers have a basic understanding of off-chain payment networks. In part of the description, we will regard the payment network as a graph in the sense of graph theory (graph), each participant as a node (vertex), and each payment channel as an edge on the graph (edge) . Therefore, in the following, the author will unconsciously use "graph" to refer to a payment network, "node" to refer to a participant, and "edge" to refer to a payment channel.


Routing is a process in which the person who needs to send the transaction on the payment network and the transaction receiver interact with other nodes on the graph to determine the payment path. Of course, strictly speaking, this is not necessarily a path, but may be a directed acyclic graph (DAG) composed of a series of paths. Since other scholars do not seem to have adopted a new term for this category, the author will The sum of this series of paths is named transaction pattern.   


Routing protocol based on network flow  


Use a The network flow model has the following advantages in describing the overall state of the payment network: First, the network flow accurately describes the total amount and balance of each payment channel, and the maximum payment amount that can be achieved between two points can be found using the existing maximum flow algorithm , and efficiently find a set of feasible paths. Next, the author briefly introduces the network flow problem.


Hint: "Routing protocol based on network flow" is the name proposed by the author, and its corresponding phrase in most documents is Source Routing. The reason is that the routing process of this type has to be completed locally by the source node. During the process, the source node has mastered the topology of the entire payment network by default, and can dynamically detect (probe) the balance in any payment channel. However, all existing Source Routing schemes are based on the maximum flow algorithm, so the author boldly changed the name to facilitate readers' understanding (another reason is that the author will propose a method that is not in the category of source routing in the research prospect section. flow-based routing protocol).   


Introduction to network flow problems


We use one of the network flow models The residual network describes the overall state (configuration) of a payment network, and its essence is a quadruple ancestor , where V  is a collection of nodes, each node represents a participating node in a payment network, is an edge set, each edge represents a payment channel,  represents residual flux on each side. Combined with the application needs of the payment network, we are different from traditionally adding   The maximum throughput established when the channel was established.


19 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z" >

The maximum flow is at A family of linear programming problems on network flow models. From s  to the single-source single-sink maximum flow of t (problem is:   



This rigorous definition based on linear programming is not convenient for the audience to understand. The author drew the following picture to help readers understand the definition of the maximum flow problem. In the picture below,  s1 to t1 The maximum flow is 10 units .   



If s1 to t1 The quota of 10 units has all been used up, and there is not only one plan. One of the "augmented" plans is used as shown below.   


< p> Commonly used maximum flow algorithms include reserved push algorithm (HLPP) and a class of maximum flow algorithms based on augmented path theorem, including  Edmonds-Karp algorithm and its derivative algorithms such as ISAP algorithm and  Dinic algorithm.


These algorithms have extremely high theoretical complexity in the worst case, and considerable operating efficiency that is often much lower than the theoretical complexity. For example, consider a card with N nodes M  Flow diagram, the theoretical computational complexity of the Edmonds-Karp algorithm is as high as , and the theoretical computational complexity of the Dinic algorithm is as high as  , and their execution efficiency on normal sparse random graphs is very high, and ordinary CPUs can find the maximum flow of thousands of nodes within 100 milliseconds.


< p>

It is not difficult to find that for large payments, we can use the maximum flow algorithm to obtain the maximum possible payment amount between two nodes. If the payment amount is less than this amount, we have also established a payment scheme through the maximum flow algorithm.


2. Routing protocol based on lighthouse nodes 


Based on lighthouse (landmark) nodes The general idea of the routing protocol is as follows. First of all, each node is eligible to be a lighthouse node, and each node has the right to choose which lighthouse nodes to assist in routing. This major premise basically guarantees that the decentralization feature of the routing scheme will not be broken.


Then, in order to provide a certain amount of privacy and increase the probability of successful payment, the amount of each payment is divided into   copies, each of which is assisted by different lighthouse nodes to complete the transmission. For the case of non-fragmentation, we think  . The way the lighthouse assists in the transmission is to arrange a channel for the amount according to its own vision, and communicate with the nodes on these channels to obtain the maximum amount that can pass through the channel.   


Early method


Landmark-based The idea of routing protocols comes from research in the field of computer networks. The common components are as follows.


Two-way BFS to find the shortest path


Readers who are familiar with the algorithm understand that on a directed graph with no border weight, the breadth-first search (Breath-First Search, BFS) sequence property guarantee from a single source: Each node in the BFS tree The path to the source node, which is the shortest path or one of the shortest paths from this node to the source node. Each Landmark node maintains two BFS trees with itself as the source node, one T1 based on PCN graph, one T2 77 697 676T704 667Q704 661 687 553T668 444Q668 437 649 437Q640 437 637 437T631 442L629 445Q629 451 635 490T641 551Q641 586 628 604T573 629Q568 630 5 15 631Q469 631 457 630T439 622Q438 621 368 343T298 60Q298 48 386 46Q418 46 427 45T436 36Q436 31 433 22Q429 4 424 1L422 0Q41 9 0 415 0Q410 0 363 1T228 2Q99 2 64 0H49Q43 6 43 9T45 27Q49 40 55 46H83H94Q174 46 189 55Q190 56 191 56Q196 59 201 76T241 233Q258 301 269 344Q339 61 9 339 625Q339 630 310 630H279Q212 630 191 624Q146 614 121 583T67 467Q60 445 57 441T43 437H40Z"> Based on a PCN diagram with all lane directions reversed. Of course, for undirected graphs, these two trees are identical. Thus, for a path from u to  v's routing needs, first find u in T1  246T182 105Q182 62 196 45T238 27T291 44T328 78L339 95Q341 99 377 247Q407 367 413 387T427 416Q444 431 463 431Q480 431 488 421T496 402L420 84Q419 79 419 68Q419 43 426 35T447 26Q469 29 482 57T512 145Q514 153 532 153Q551 153 551 144Q550 139 549 130T540 98T523 55T498 17T462 -8Q454 -10 438 -10Q372 -10 347 46Q34 5 45 336 36T318 21T296 6T267 -6T233 -11Q189 -11 155 7Q103 38 103 113Q103 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Z">  to the landmark node The path of T2 Find the landmark node to v  path. These two paths are spliced together, and the result from u to v A shortest path.




Graph Embedding


Tree-based graph embedding allows each lighthouse node Treat all the nodes in the view as a tree, and each edge on the tree corresponds to a payment channel. In this way, each node can be numbered with the path from the root node to the node in a Trie-like manner. For example, in the figure below, < /path> D node label is (0,1), &n bsp;The label of the H node is (0,1,0) < path d="M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z ">, the label of the J  node is (1, 0,1) < /path>. Of course, we are just using a binary tree as an example. In reality, this is a multi-fork tree. At this time, the encoding range is no longer 0 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q1 53 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z" >  and 1  between. For a k  tree, the coding range becomes 0  to k-1.   


< /p>

Through this encoding method, a path between two nodes can be efficiently determined—that is, the only path spliced from the payment node to the nearest common ancestor (LCA) of the two nodes is spliced from The only path from LCA to the receiving node.   


SilentWhispers  and SpeedyMurmurs 


SilentWhisper The protocol itself does not consider the dynamics of the payment network, and the scheme in the article does not consider quota sharding, so one payment only uses 1 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52 T207 57T213 61V578Z">  lighthouse node L. Of course, this scheme can be extended to   Fragmented payment scheme, but the communication complexity of this scheme grows linearly with the square of the number of lighthouse nodes used for payment. Suppose you need to process a transaction from u  to v  payment, the total amount is c. The payer divides the payment amount into m , page   routing by  Assistance. For every  


< /p>

First, find u to   and  to v  The shortest path,


Then, through the Communication, determine the amount of payment amount that can pass on this path, that is, the minimum margin on this path. This step can be done by secure multiparty computation (MPC) to ensure privacy.


SpeedyMurmurs directly adopts the split payment scheme. In addition, a big difference from SilentWhispers is that the lighthouse nodes in SpeedyMurmurs use the tree-based graph embedding method to provide payment paths. The starting point of SilentWhispers is (1) the difficulty of maintaining a bidirectional BFS tree in a dynamic network environment, (2) Even the route between two nodes whose topological distance is very close must go through the Landmark node, (3) and the problem of extremely poor concurrency.  


Each Landmark is maintained according to the existing payment channel A tree with itself as the root node k Fork tree. And use this to maintain the number of nodes in each field of view. Suppose you need to process a transaction from u to v  payment, the total amount is c, use m  lighthouse nodes . The payer divides the payment amount into m copy  < path d="M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q 95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z">, page  routing Assisted by   For each  , find U to v on tree  The tree path to complete the corresponding payment.


3. Routing protocol based on data network method 


The above routing schemes do not fully consider the dynamics of the actual payment network. Therefore, some scholars from the background of computer network have proposed several schemes to directly apply the routing method in the data network to the payment network. Since the routing theory of data network has been very mature in the field of computer network, this kind of scheme has high reliability. Dynamicity also provides very considerable efficiencies for such schemes. The most classic of these is the  Spider  protocol.


Spider  compares the payment network to the data transmission layer, and uses the data network method for dynamic routing. In order to match the model of the data network, in this scheme, we still assume that all channels are bidirectional. Similar to the data packets in the data network, each transaction is split into several amount packets and routed through different paths. Each amount package is directly transmitted through the payment network channel and finally reaches the payee, and the nodes in the forwarding process lock the corresponding amount. After the pathfinding is completed, the final payment is completed according to the forwarding path of each amount packet.


However, A major difference between payment networks and data networks is the existence of throughput limitations. Therefore, each channel will correspond to a queue (pending list) to store all the amount packets that have not yet been transmitted with the current flux. Only when there is enough flux from the other side of the channel (equivalent to an increase in the headroom in this direction), the amount packets in this queue can continue to be transmitted. It is worth noting that although we use the transmission process of an amount packet to describe the dynamic routing process, its essence is a process of pathfinding and locking. If you do not pay attention, this routing process will be mistaken for a payment process.


4. Hybrid Routing Protocol  


A recent survey (in Flash's paper) through a practical analysis of  Ripple  and  Bitcoin  payment networks Findings:


· Payment networks need to support large transactions (this has been questioned);

p> · Large-amount transactions need to pay more attention to the payment success rate, and small-amount transactions should pay more attention to efficiency.



Based on this discovery, the Flash  protocol uses the routing scheme based on the maximum flow to complete the payment of large amounts, and uses the routing method based on the data network to pay for small amounts. As a result, the payment success rate of large-amount transactions and the efficiency of small-amount transactions can be balanced.


Comparison and analysis of various routing schemes


< p>In the above table  Tab.1 , the author lists the advantages and disadvantages of various non-hybrid routing protocols. Because it is difficult to quantify, it has a certain subjective color.


5. Future Research Outlook


Next, the author puts forward some research prospects, and at the end of the article puts forward the problems that may be encountered in this aspect of scientific research.


Familiar with the "Maximum Flow Algorithm Based on Augmented Path" should understand that this type of algorithm needs to be Equipped with a "reverse edge" to describe the backflow that needs to be used in an algorithm. And we can be surprised to find that this backflow corresponds to the offset of the amount from the other direction in the two-way payment channel. Therefore, the Augmenting Path Theorem guarantees that even if there is no regular "augmentation" on the payment network, any payment that does not exceed the maximum amount of flow will be completed in the end. In this way, we get a completely "dynamic" routing algorithm based on maximum flow. This point does not seem to be mentioned in the existing literature. Of course, for the vast majority of small transactions, using this algorithm is too overkill. But the author believes that this idea will be useful for the huge transactions encountered in the early payment network.


You can use "minimum cost maximum flow" to replace the underlying maximum flow, so that the algorithm can pick out a group when there are multiple options The path scheme with the shortest length and the least total toll. Friends who have learned a "minimum cost maximum flow" algorithm should be able to understand the meaning of the author at this time, so I won't expand it here.


Through the reconstruction of payment network-related smart contract codes, or through the establishment of alternative landmark nodes, "guidance" to participate Nodes build edges to systematically improve the topology of the network. The author has done a lot of imagination about the structure that may be led by each  landmark , including a balanced tree based on  hypercube, rooted at  landmark , and  link- cut-tree and so on.


If you want to do in-depth research in this direction (routing in the payment network), especially if you want to shorten the average number of hops ( hop) for the purpose, there may be two major problems:


The first question


Seek truth from facts Indeed, current payment schemes are already good enough at the scale of the current payment network. According to the experimental data in the paper of  SpeedyMurmurs , it can already reach the level of average  2  to  4  hops (hop) in the  Ripple  network in its heyday. How about optimizing on top of this? Algorithms that are more elegant and can achieve better results in the future payment network of tens of millions or hundreds of millions may not be able to achieve a better result in the current payment network because of the larger "constant". Of course, basic research is aimed at the future of large-scale payment networks in the future, but future-oriented research must be simulated on a large-scale network to be credible. Next, the author will explain how the simulation of the topological structure of a large-scale payment network is impossible.


The second question


< p>

It is difficult to carry out reasonable simulation experiments. First of all, to be honest, most of the participants in the real network at the current stage are still a small number of geek elites and capital, and its topology must be very different from the real network in the future. Secondly, the author believes that some models in the social network cannot truly reflect the future topology of the payment network. For example, the author does not think that the "Watts  graph" commonly used in social networks can describe the future network well, because most nodes Do not build many edges to make the  density of the graph reach the  threshold where the small-world phenomenon appears, and the major premise of the Watts graph will not hold. All in all, the author believes that a study on the topology of future payment networks is very important today, and it is a major premise for more research and development of several payment networks.


Original link


Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia

举报 Correction/Report
Choose Library
Add Library
Cancel
Finish
Add Library
Visible to myself only
Public
Save
Correction/Report
Submit