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프로젝트로 돌아가기