Monday, May 21, 2018

SoK Cryptocurrencies and the Bitcoin Lightning Network

We wrapped up the distributed systems seminar with two more papers discussed last month.

The "SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies" paper appeared in 2015. Although the cryptocurrency scene has seen a lot of action recently, this survey paper did not age and it is still a very good introduction to learning about the technical aspects and challenges  of cryptocurrencies. The paper starts with a technical overview of the cryptocurrency concept. Then it delves more into incentives and stability issues. It observes that it is unclear "how stability will be affected either in the end state of no mining rewards or in intermediate states as transaction fees become a non-negligible source of revenue". It talks about possible attacks, including Goldfinger attack and feather-forking, and also about stability of mining pools and the peer-to-peer layer. Finally it also covers some security and privacy issues.

"The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments" whitepaper is from 2016. Bitcoin has a very high latency, poor scalability, and high transaction fees, and the lightning network provides an overlay solution to ease off these pains. To this end, the paper describes a secure off-chain solution for instant payments and microtransactions with low transaction fee.  This video by Jackson Palmer describes the lightning network ideas very nicely. (I strongly prefer reading to watching/listening, but recently I am finding a lot of useful content on YouTube.)

The protocol builds on the basic concept of a pairwise payment channel. Two parties put aside an initial amount of Bitcoin into a multi signature transaction. Subsequently many updates to the allocation of the current balance can be made off-the-chain just with the cooperation of both parties using a new timelocked transaction, without broadcasting this to the chain. This is analogous to buying a Starbucks card and transacting with Starbucks pairwise with that card. A broadcast to the chain can be done to redeem funds on the chain and to close the channel. If either party tries to cheat by broadcasting an old transaction state from the pairwise payment channel, the counterparty may take all the funds in the channel as penalty after it provides the latest multisig agreed state to the chain (within the on-chain dispute mediation window).

The lightning overlay network is then formed by multihop routing over these pairwise payment channels. Even when A and Z does not have a direct pairwise payment channel, it may be possible to construct a multihop route from A to Z to use intermediaries, traversing through several pairwise payment channels. While pairwise channels could be without a fee, the multihop intermediaries need a small transaction fee to have the incentive to participate.

The pairwise payment channels need to be extend with hashlocks to achieve multihop transactions. Here is how this is done as explained in the Bitcoin wiki:

  1. Alice opens a payment channel to Bob, and Bob opens a payment channel to Charlie.
  2. Alice wants to buy something from Charlie for 1000 satoshis.
  3. Charlie generates a random number and generates its SHA256 hash. Charlie gives that hash to Alice.
  4. Alice uses her payment channel to Bob to pay him 1,000 satoshis, but she adds the hash Charlie gave her to the payment along with an extra condition: in order for Bob to claim the payment, he has to provide the data which was used to produce that hash.
  5. Bob uses his payment channel to Charlie to pay Charlie 1,000 satoshis, and Bob adds a copy of the same condition that Alice put on the payment she gave Bob.
  6. Charlie has the original data that was used to produce the hash (called a pre-image), so Charlie can use it to finalize his payment and fully receive the payment from Bob. By doing so, Charlie necessarily makes the pre-image available to Bob.
  7. Bob uses the pre-image to finalize his payment from Alice

In order for the multihop routes to work there should be enough cooperative participants online, each of which with enough balance to pass the bucket from hand to hand. The rest is a path-finding exercise. With viable paths present, similar to a source-side routing decision, you can start the lightning transaction. There has been a lot of work on MANETs under the names of intermittently connected networks and delay tolerant routing. I wonder if some of them can find applications here (even though they were mostly geometrical and this is a non-geometrical network.) In practice though, the multihop network often converges to a hub and spokes model, with a well-connected fat wallet intermediary.

The lightning network is also useful for transacting securely across different blockchains, as long as all edges in the route support the same hash function to use for the hash lock and can create timed locks.

MAD questions

1. How can we improve the way we run the seminar?
The students liked how we run the seminars. They said they were more actively engaged and learned a greater deal due to this format. But I think we can improve. It would be nice to get experts video-conference and answer some questions. I think many experts would be generous to spare 20 minutes to spare to answer some questions from smart well-prepared students. 

The students also mentioned that it would have been nice to have some hands-on projects to accompany the seminars. We started a blockchain channel so the interested students can figure out some small projects they can work on and collaborate.

2. What did I learn?
I didn't think much of blockchains but I am fascinated to learn that there are many challenging questions here and many good ideas/techniques. This is an area very suitable for doing distributed algorithms/protocols work, which I love. There is a need for developing more principled approaches and well-reasoned and verified algorithms/protocols.

I still think the best ideas from these work will get borrowed and used in more centralized (could be hierarchical or federated) systems for the sake of efficiency/economy and scalability. That may be how these systems will go mainstream to millions and even billions.

No comments:

Two-phase commit and beyond

In this post, we model and explore the two-phase commit protocol using TLA+. The two-phase commit protocol is practical and is used in man...