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.
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).
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 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.
The maximum flow is at A family of linear programming problems on network flow models. From s
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,

If s1

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
, and the theoretical computational complexity of the Dinic algorithm is as high as
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.
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
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">

p>
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,
< /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.
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
routing by Assistance. For every
< /p>
First, find u
and
to v
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
. The payer divides the payment amount into m
routing Assisted by
For each
, find
U to v on tree
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.
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.

p>
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.
p>
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:
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.
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