COMP90088: Cryptocurrencies and decentralised ledgers Semester 1 2022
Tutorial Sheet, Week 12 Week of May 23, 2022
1. Off-chain payment networks. In class we discussed the use of payment channel networks to improve Bitcoin scaling. Consider two possible network scenarios for a group of N users. In a distributed model, all users have a channel with all other users. In a hub-and-spoke model, all users have one channel with a central hub.
Assume all payment channels are bidirectional. Each has an initial capacity, the maximum the balance can deviate from zero in either direction. If a payment is executed which increases the channel balance to capacity, the channel is reset. We¡¯ll consider a simple model where every second, a random user sends 1 unit to a different random user. Assume there are N users total and each user is willing to put M total coins on deposit.
Copyright By PowCoder代写 加微信 powcoder
a. For each scenario, how many channels will be required for N users? Hub-and-spoke: N total channels
Distributed: (N choose 2) = N(N-1)/2
b. For each scenario, what will the bidirectional capacity of each channel be assuming users divide their total coins M equally? Note: remember that to open a channel with bidirectional capacity X, 2X coins must be put on deposit.
Hub-and-spoke: M/2 bidirectional capacity per channel
Distributed: (M/(N-1)/2)/2 = M/(N-1) bidirectional capacity per channel
c. For each scenario, for what fraction of random payments will a given channel be used?
Hub-and-spoke: There are (N choose 2) = N(N-1)/2 possible payments, and each channel
is used for exactly (N-1) of them, so each channel is for a 2/N fraction of possible payments.
Distributed: There are (N choose 2) = N(N-1)/2 possible payments, and each channel is used for exactly 1 of them, so each channel is for a 2/(N(N-1)) fraction of possible payments.
d. For each scenario, compute the long-run scalability improvement over processing all payments on-chain. That is, compute the ratio of the number of on-chain transactions
required if all payments appeared on-chain to that required in the payment channel scenario. Remember that resetting a channel requires two transactions.
Hint: A useful fact from the theory of random walks is that the ¡°time to complete¡± (starting from 0) with upper and lower boundaries (n, -m) is nm. For example, in a single channel of capacity n with random payments back and forth, an average of n2 payments can be made before one will push the balance to ¡Àn, requiring a channel reset.
Note that it doesn¡¯t matter how many total channels there are here (in either case) since random channels are chosen for each payment. In the steady state, each of those is at some random point in its lifespan and processing one extra payment introduces a constant probability (over time) of requiring a reset. This probability is 1/the answer to part (c).
Hub-and-spoke: Given initial channel capacity M/2, on expectation a channel will be reset after M2/4 payments have been made on that channel. Since each payment requires two channels, an expected 8/M2 resets are required for a random payment, or 16/M2 transactions per payment (because a reset requires 2 transactions). 1 transaction per payment is traditionally required, so the scalability improvement is M2/16.
Distributed: Given initial channel capacity M/(N-1), on expectation a channel will be reset after M2/(N-1)2 payments have been made on that channel. Since each reset requires two transactions, an expected 2(N-1)2/M2 transactions are required per payment. 1 transaction per payment is traditionally required, so the scalability improvement is M2/(2(N-1)2)
e. What are some disadvantages of the hub-and-spoke model?
Generally, the hub has too powerful of a position and this model is highly centralized. The hub is on the path for every payment. If they crash, no payments can be processed so reliability is poor. They also learn everybody¡¯s channel usage pattern. They would be in a position to censor or charge high fees since no payment is possible without them.
f. Why is the random payment model in this question unrealistic? Briefly describe how you might improve efficiency by taking advantage of a more realistic distribution of payments.
Most users will never pay most other users. Indeed the space of all users might not even be known. It is more realistic that users only open a channel on the first payment to another user rather than pre-emptively opening channels with all users. Users might also allocate capacity non-uniformly, placing more capacity on their most frequently used channels.
2. Ethereum micropayments. In class we saw a protocol for serial micropayments in Bitcoin: Alice wants to send a series of payments to Bob, so she puts n units of currency into an escrow account which is a multisig account shared by Alice and Bob. She then repeatedly signs transactions, the first paying 1 unit to Bob and returning n-1 to Alice, the second paying 2 units to Bob and returning n-2 units to Alice, and so on. Alice stops sending transactions whenever she wishes, and Bob can sign and publish the last transaction received. A time-locked refund transaction is used to ensure Alice can recover her money if Bob goes offline.
Let¡¯s consider solving this problem in Ethereum. It is very easy to implement the above logic. We can actually add a cool feature: each micropayment need only require hashing, rather than signatures. This is perfect for lightweight clients (although initialization will require a signed message). The scheme works as follows: Alice picks a random X and computes Y = Hn(X) [that is, iterate the function H n times starting at X, e,g., for n=2 we have Y = H(H(X))]. She then creates a contract with n units of currency and embeds the value Y in the contract (and sends Y to Bob). To pay Bob k units (for k