Celer Network 백서

Celer Network

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 8쪽 중 3쪽

channel from 3 to 1. This is achieved by using a dependency contract to store deposits for counterparties. The N 1 counterparties will just sign the authorization of withdrawal entirely o↵-chain and one counterparty can submit that on-chain to complete the channel opening process. • Direct Final State Claim When building generalized state channel applications, conditional state dependency is commonly used. When finalizing the GPC, one party may want to avoid the process of traversing the conditional dependency graph. This is to limit the griefing scenario of the counter-party, where the counterparty goes o↵-line and refuse to cooperatively convert some ConditionGroup to unconditional state update. To limit the work needed for the disputing party, we introduce the method of direct final state claim. It allows the online party to directly claim a final state without actually performing any additional traversal of dependency graph. No counterparty signatures are needed. To avoid abuse, a fraud-proof bond is also required for the claiming party. After a challenging period, the state will become final without needing to perform any additional operations. • Dynamic Deposit and Withdrawal. A common requirement for GPC is to enable seamless on-chain transactions when the counterparty is not con- nected to the network. For withdrawals of funds, we introduces a pair of func- tions IntendWithdraw and ConfirmWithdraw,t om e e tt h i sr e q u i r e m e n t . IntendToWithdraw changes the base state s0 with a challenge period. Counter- party can submit conflicting sp to dispute. If no dispute happens before the chal- lenge period defined by ⌧ , ConfirmToWithdraw is called to confirm and dis- tribute the withdrawal. These two functions work very much like IntendSettle and ConfirmSettle. Deposit is straightforward as it only changes the base state s0. • Boolean Circuit Condition Group. We expect that GPC’s most common use case would be Boolean circuit based conditional payment. For example, “A pays B if 18 function X or function Y return true”. To optimize for such payment, we tweak the interface of condition group and condition. In particular, we can specialize function ResolveGroup to release a pre-defined conditional payment if any of the condition resolving results (or any boolean circuit of condition results) holds true. This way, we saved the trouble of creating additional objects for ResolveGroup and the corresponding multi-party communication overhead. We also specify condition as Boolean condition so that we require the depending objects should have an interface with the e↵ect of “isSatisfied” that returns true or false based on the state queried. • F und Assignment Condition Group. Another more generalized use case for GPC is generalized state assignment. We implement this by introducing another di↵erent type of condition group, which only has one condition in it. QueryResult will directly return a state assignment map dictating an update for s. This enables a more general plug-in point for GPC. One can plugin an o↵-chain contract that was initialized with certain locked in liquidity. This contract can check not only who wins a game (Boolean) but how many steps the winner took to win the game, and then assign the liquidity by carrying out a certain computation. The involved parties can generate a Condition Group that references the check function of the o↵-chain contract address they mutually agree on. There can be many more common patterns defined for di↵erent patterns, but the above example illustrates the design principle for such optimization. 2.2. Alternative Channel Model with Sidechains Besides the above-mentioned generalized state channel model, cChannel also intro- duces an alternative state channel model that is facilitated by sidechains [1]. For example, consider the scenario where multiple users need to pay each other. Users can pool their deposits to a central contract, which acts like a sidechain contract with the o↵-chain service providers playing the role of block proposers (forming a “multi-party hub” with o↵-chain service providers being “hub operators”), and therefore enables one-to-many payment relationships within a hub. The integrity of the o↵-chain service providers is ensured by a certain level of fraud-proof bond acceptable by participants. Specifically, in Celer Network, each o↵-chain service provider can run a sidechain- 19 aided state channel: C = {s, p⇤,b ,⌧ }, (5) where s is the sidechain state, p⇤ is the single block proposer (the o↵-chain service provider), b is the fraud bond and ⌧ represents the finality timeout. Each node i can send sidechain transactions to every other node in the channel to update the latest state. Just like any sidechain transactions, node i will not only sign this transaction but also sign another transaction to prove that it has seen this transaction included in the block created by p⇤. The second signed transaction can be used as proof for node i. As long as participants have block data fully available, the finality of this sidechain transaction can be confirmed quickly as well. This sidechain-aided channel model comes with the following expected benefits [1] when compared to previously mentioned channel models. • No on-chain transaction and online presence needed for the receiver. This is a natural benefit inherited from sidechain properties. The reason is that the receiver can redeem their fund received on the sidechain-aided channel with- out actually performing any sidechain deposit themselves. • No per-party fund lock-up. This benefit is in the context of payment chan- nels. When side-chain based channels are used for multi-party payment, each party does not need to lock their deposit in advance before they pay each other (except for the block proposer who needs to deposit fraud-proof bond). However, the ecosystem should be clearly aware of the downsides of this channel model as the following: • F raud proof bond is still needed. In the case of sidechain based channels, the fraud-proof bond is still needed from either the block proposer p⇤ directly or whoever is providing auditing and insurance services. It should be clearly understood that the worst-case liquidity requirement for the block proposer (i.e., the o↵-chain service provider) is actually unbounded. The reason is that with enough colluding, malicious party can create unbounded repeated spending. • Data availability issue may complicate finality .Even if no malicious parties are involved, the inherent finality delay for sidechain model still haunts this 20 channel model, especially when data availability becomes an issue. When the block data is not always available among relevant parties, the sidechain faces inevitable re-organization and therefore finality will be delayed at the best and the entire sidechain will be abandoned in the worst case. These sidechain based channels can be further connected to each other via the common state channels. 3. cRoute: Provably-Optimal Value Transfer Routing 3.1. Challenges in State Channel Network Routing The need for state routing (or “payment routing” in the case of payment channel networks) is apparent: it is impractical to establish direct state channels between every pair of nodes due to channel opening costs and deposit liquidity lockup. Therefore, it is necessary to build a network consisting of state channels, where state transitions should be relayed in a trust-free manner. The design of state routing is crucial for the level of scalability that a state channel network can provide, i.e., how fast and how many transactions can flow on a given network. However, existing proposals all fall short to meet the fundamental challenges imposed by the unique properties of state channel networks. Landmark routing [16] has been proposed as one option for decentralized payment routing in several payment channel networks. For example, Lightning Network [9] adopts a landmark routing protocol called Flare [10]. A similar algorithm is also used in the decentralized IOU credit network SilentWhispers [4]. The key idea of landmark routing is to determine the shortest path from sender to receiver through an interme- diate node, called a landmark, usually a well-known node with high connectivity. Raiden Network [2] (a payment channel network) mentioned a few implementation alternatives for payment routing, such as A⇤ tree search which is a distributed im- plementation of shortest path routing. In addition, since route discovery is hard but crucial, nodes can provide pathfinding services for other nodes for some convenience fees in Raiden Network. Recently proposed SpeedyMurmurs [13] enhances the previous shortest path routing algorithms (as used in Lightning Network and Raiden Network) by accounting for the available balances in each payment channel. Specifically, SpeedyMurmurs is based on 21 A C B 100 100 100 100 100 100 A C B A C B 200 0 0 200 200 0 A C B A C B 0 200 200 0 0 200 A C B time slot 1 time slot 2 time slot 3 Figure 2. Shortest path routing leads to frequent topology changes due to channel imbalance. the embedding-based routing algorithms that are commonly used in P2P networks [12], which first constructs a prefix tree and then assigns a coordinate for each node. The forwarding of each payment is based on the distances between the coordinate known to that node and the coordinate of the destination. The prefix tree and the coordinate of each node will be adjusted if there is any link that needs to be removed (i.e., when a link runs out of balance) or added (i.e., when a depleted link receives new funding). It can be observed that all of the existing routing mechanisms boil down to “ short- est path routing with available balance consideration ”. In traditional data networks, shortest path routing does provide reasonably good throughput and delay perfor- mance, based on the assumption that network topology remains relatively stable and link capacity is “stateless” (i.e., the capacity of each link is not a↵ected by past trans- missions). Unfortunately, such an assumption no longer holds for an o↵-chain state channel network due to its “stateful” link model, i.e., the capacity (available balance) of each directed link keeps changing as payments go through that link. Note that shortest path routing does not account for channel balancing, and thus each link may quickly run out of its capacity, which further leads to frequent changes in network topology. Figure 2 illustrates a scenario in which shortest path routing leads to topol- ogy changes every time slot. Suppose that at the beginning of each time slot, node A,n o d e B and node C each initiates a payment of 100 tokens to node B,n o d e C and node A, respectively. Under the initial channel balance distribution (time slot 1), every pair of nodes are connected by a bi-directional link, and each node selects a direct route to its destination under shortest path routing. However, this results 22 in a uni-directional transfer over each channel, and thus the distribution of channel balances becomes highly skewed in time slot 2, where the underlying topology is a counter-clockwise cycle. In this new topology, shortest path routing continues to make uni-directional transfers (e.g., selects route A ! C ! B for payment A ! B), and channel balances are pushed to the other extreme, where the underlying topology is completely reversed to a clockwise cycle (time slot 3). The same pattern will repeat indefinitely. In contrast, if node C takes a longer route C ! B ! A, every channel will remain balanced all the time, and the network topology never changes. For any decentralized implementation of shortest path routing, such frequent topology changes could lead to poor performance since it takes time for the algorithm to converge on the new topology (e.g., to reconstruct the prefix tree as in SpeedyMurmurs [13]), dur- ing which sub-optimal routes may be taken. What’s even worse is that the network topology may change again before the algorithm converges, and thus the algorithm may never converge and achieve continually poor throughput performance. Note that the recent project Revive [3] proposes an explicit channel rebalancing scheme. However, Revive does not account for state routing, which means that its channel rebalancing procedure is not transparent to the underlying routing process and requires extra out-of-band coordination. Moreover, Revive only works in a restricted class of network topologies that contain cyclic structures, and it does not provide any guarantee that its channel rebalancing procedure is feasible in a general topology. In comparison, we propose a routing algorithm that achieves transparent and optimal channel balancing during the routing process. 3.2. Distributed Balanced Routing (DBR) We propose Distributed Balanced Routing (DBR) as an ecient routing protocol for value transfers in an o↵-chain state channel network. The DBR algorithm is inspired by the BackPressure routing algorithm [7, 15] that was originally used in wireless networks. It is based on a completely di↵erent design philosophy from the traditional shortest path routing. In particular, DBR does not perform any explicit path com- putation from source to destination. Instead, the routing direction is guided by the current network’s congestion gradients. Think of water flowing from the top of a hill to a destination at the foot of the hill. The water does not need to know the route to its destination; all it needs to do is to follow the direction of gravity. 23 The DBR algorithm uses a similar design philosophy but also accounts for the stateful link model in state channel networks. In particular, the DBR algorithm is augmented with a state channel balancing ability that transparently maintains bal- anced transfer flows for each state channel. Compared with existing routing algorithms, the proposed DBR algorithm has the following advantages: • Provably optimal throughput . In other words, for a given arrival rate of value transfer requests, if there exists any routing algorithm that “supports” the rate, DBR is also able to do that. The meaning of “support” will be specified in Section 3.2.3. • T ransparent channel balancing . In DBR, the channel rebalancing process is naturally embedded in the routing process without any additional coordina- tion. It automatically rebalances each state channel to maintain balanced value transfers in the long term. • F ully decentralized. The DBR algorithm is a fully decentralized algorithm where each node only needs to talk to its neighbors in the state channel network topology. DBR also has low messaging cost in the protocol. • F ailure resilience. The DBR algorithm is highly robust against failures: it can quickly detect and adapt to unresponsive nodes, supporting the maximum possible throughput over the remaining available nodes. • Privacy preserving . Due to its multi-path nature, the DBR algorithm nat- urally preserves the privacy regarding the amount of transferred values, with- out using any additional privacy-preserving techniques (e.g., ZKSNARK). More importantly, the DBR algorithm can be seamlessly integrated with onion rout- ing [11] to preserve anonymity for sources/destinations. In the following, we first introduce the state channel network model, then describe the DBR algorithm, and finally prove the performance of DBR. Note that for the ease of exposition, we restrict our attention to bi-party payment channels in this section, but the same ideas apply to any state channel network that has value transfer requirements. 3.2.1. System Model In our model, time is discretized into slots of a fixed length, where the length of each slot usually corresponds to the physical transmission delay over one hop. Suppose that 24 there are N nodes in the network. For each pair of nodes i and j, a pair of directed links i ! j and j ! i exit if there is a bi-directional payment channel i $ j between node i and node j. Let cij (t) be the capacity of link i ! j in slot t, which corresponds to the remaining balance in the payment channel that can be transferred from node i to node j at the beginning of that slot. There is a total deposit constraint for each bi-directional payment channel between node i and node j: cij (t)+ cji (t)= Bi$j (t), where Bi$j (t) is the total deposit of bi-directional payment channel i $ j at the beginning of slot t. Note that the total deposit Bi$j (t) may change over time due to dynamic on-chain fund deposit/withdrawal. During each slot t, each node i receives new payment requests from outside the network, where the total amount of tokens that should be delivered to node k is a(k)i (t) 0. Also denote by µ(k)ij (t) the amount of tokens (required to be delivered to node k)s e n to v e rl i n ki ! j in slot t, which is referred to as a routing variable . 3.2.2. Protocol Description Before the description of DBR, we first introduce several important notions: debt queue, channel imbalance and congestion-plus-imbalance (CPI) weight. (Debt Queue). In the operation of DBR, each node i needs to maintain a “debt queue” for payments destined to each node k, whose queue length Q(k)i (t) corresponds to the amount of tokens (with destination k) that should be relayed by node i to the next hop but have not been relayed yet at the beginning of slot t.I n t u i t i v e l y ,t h e length of the debt queue is an indicator of congestion over each link. The queue length evolution is as follows: Q(k)i (t + 1) = hQ(k)i (t)+ a(k)i (t)+ X j2Ni µ(k)ji (t) X j2Ni µ(k)ij (t)i+, (6) where [ x]+ = max {0,x } (since queue length cannot be negative) and Ni is the set of neighbor nodes of node i. The above equation simply means that in slot t, the change of queue length is caused by three components: (1) new token transfer requests from outside the network (i.e., a(k)i (t)), (2) tokens routed from neighbors to node i,i . e . , 25 P j2Ni µ(k)ji (t), and (3) tokens routed from node i to its neighbors, i.e., Pj2Ni µ(k)ij (t). It should be noted that the queue length at the destination node is always zero, i.e., Q(i)i (t) = 0 for each node i, which guarantees that every packet can be eventually delivered to its destination under the DBR algorithm. (Channel Imbalance). For each link i ! j, we define the channel imbalance as ij (t)= X ⌧< t X k ⇣ µ(k)ji (⌧ ) µ(k)ij (⌧ )⌘. (7) Intuitively, ij (t) is the di↵erence between the total amount of tokens received by node i from node j and the total amount of tokens sent from i to j over their payment channel up to the beginning of slot t. Note that if ij (t) < 0 then it means that node i sent more tokens to node j than what was received from node j. Clearly, ij (t)i s a natural measure of channel imbalance as perceived by node i. Our DBR algorithm tries to balance the payment channel such that lim t!1 ij (t)/t = 0 for each payment channel i $ j, which implies that the long-term sending rate from i to j equals the sending rate from j to i. (Congestion-Plus-Imbalance (CPI) W eight). Define the Congestion-Plus- Imbalance (CPI) weight for link i ! j and destination k as W (k)ij (t)= Q(k)i (t) Q(k)j (t)+ ij (t), (8) where > 0 is a parameter adjusting the importance of channel balancing. Intuitively, the above weight is the sum of the di↵erential backlog Q(k)i (t) Q(k)j (t) for payments destined to node k between node i and node j (i.e., congestion gradient) and the channel imbalance ij (t)b e t w e e nn o d ei and node j. The former is used to reduce network congestion and improve network throughput while the latter is used to balance payment channels. Distributed Balanced Routing (DBR) The following protocol is locally executed by each node i. In each time slot t,n o d e i first exchanges the queue length information with 26 its neighbors and calculates the CPI weights. Then for each link i ! j,n o d e i calculates the best payment flow to transmit over that link: k⇤ = arg max k W (k)ij (t). (9) If W (k⇤ )ij (t) > 0, then µ(k
프로젝트로 돌아가기