Bitcoin Optech Newsletter #86

This week’s newsletter announces the 2020 Chaincode Residency program, describes two proposed routing improvements for LN, summarizes three interesting talks from the Stanford Blockchain Conference, links to popular questions and answers from the Bitcoin StackExchange, and lists several notable changes to popular Bitcoin infrastructure software.

Action items

  • Apply to the Chaincode Residency: Chaincode Labs announced its fifth residency program to be held in New York this June. The program consists of two seminar and discussion series covering Bitcoin and Lightning protocol development. Developers interested in contributing to open source projects may apply for either the Bitcoin series, the LN series, or both. Applicants from all backgrounds are welcomed, and Chaincode will cover travel and accommodation costs as needed.

Note: the list of releases and release candidates has been moved to its own section.

News

  • Reverse up-front payments: as described in Newsletter #72, LN developers have been looking for a way to charge a small fee for routing an LN payment (HTLC) even if the payment is rejected. This can discourage payments that are designed to consume bandwidth and liquidity before ultimately failing at no cost. This week, Joost Jager proposed a new scheme where up-front fees are paid from the receiver of an HTLC back towards the sender of the payment. For example, if a payment is being sent from Alice to Bob to Carol, then Alice receives a small fee from Bob and Bob receives a small fee from Carol. The fee would be proportional to the amount of time the HTLC remained pending, which would incentivize quickly routing or rejecting HTLCs and would ensure users of hold invoices (for example, Carol) paid the routing nodes (such as Bob) for tying up their routing capital.

    Several responders seemed to like the idea and began discussing how it might be implemented as well as what technical challenges it would need to overcome.

  • LN direct messages: Rusty Russell proposed allowing LN nodes to route encrypted messages between peers without using the LN payments mechanism. This could replace current uses of messages-over-payments, such as Whatsat, with a simpler protocol that might be easier to build upon (such as for the offers idea described in Newsletter #72). Russell’s proposal originally specified using the same there-and-back onion routing used for LN payments (HTLCs), but developer ZmnSCPxj proposed having the message sender specify the full path from their node to the message recipient and back to the sender. For example, if Alice wants to communicate with Carol, she might choose the following path:

      Alice → Bob → Carol → Dan → Alice
    

    This type of circle routing would make surveillance more difficult and would eliminate the overhead for routing nodes of having to store the return path, making the protocol stateless for routing nodes. Discussion remains ongoing as of this writing, with a focus on enhancing privacy and preventing the mechanism from being abused for spam.

Notable talks from the 2020 Stanford Blockchain Conference

The Stanford Center for Blockchain Research hosted its annual Stanford Blockchain Conference last week. The conference included over 30 presentations across three days. We’ve summarized three talks that we think will be of particular interest to Optech newsletter readers.

We thank the conference organizers for putting together the program and making videos of the talks available online (day 1, day 2, day 3), and Bryan Bishop for providing transcripts.

  • An Axiomatic Approach to Block Rewards: Tim Roughgarden presented his work with Xi Chen and Christos Papadimitriou analyzing Bitcoin’s block reward allocation rule from a mechanism design theory perspective. (transcript, video, paper).

    Roughgarden began his talk by introducing mechanism design as the inverse of the better-known game theory. Game theory describes the rules of a game and then reasons about what equilibria and behavior are the result of those rules. By contrast, mechanism design starts with an intended outcome and tries to design game rules that will result in that desired outcome. Roughgarden asks “Wouldn’t it be nice if we had a mathematical description of the space of block chain protocols […] and we could [… pick our] favorite objective function and […] find a protocol that is optimal?” Roughgarden then gives three ‘axioms’ for desired behavior when designing the reward mechanism for a block chain:

    1. sybil resistance: no miner should be able to increase their reward by splitting their public identity into multiple parts.

    2. collusion resistance: no group of miners should be able to increase their reward by joining their independent identities into a single joined identity.

    3. anonymity: the reward distribution should not depend on the miners’ public identities, and if the miners’ hashrates are permuted, then the reward should be permuted in the same ways.

    The paper then gives a formal proof that the unique reward mechanism that satisfies these axioms is a proportional mechanism (i.e. that each miner receives rewards proportional to their hashrate). The paper only deals with the theory around the creation of a single block, and so does not consider longer-term strategies like selfish mining.

    The result may appear to be self-evident to people familiar with Bitcoin, but the formal treatment seems novel and may be a good basis for exploring more complex behavior for miners (eg long-term strategies and pooling behavior).

  • Boomerang: Redundancy Improves Latency and Throughput in Payment-Channel Networks: Joachim Neu presented his work with Vivek Bagaria and David Tse on reducing latency and preventing liquidity lock-up when using atomic multipath payments in payment channel networks such as Bitcoin’s Lightning Network. (transcript, video, paper).

    Multipath payments suffer from the “everyone-waits-for-the-last” straggler problem. This concept from distributed computing describes how, if a goal depends on n tasks, then the goal must wait for the slowest of all n of those tasks to complete. In the context of a multipath payment, this means that if a payer wants to pay 0.05 BTC split into five parts of 0.01 BTC, the payment will only complete when all of those constituent parts complete. This leads to high latency for payments and reduced routing liquidity, particularly if one or more of the parts fails and needs to be retried.

    A common approach to fixing the straggler problem is to introduce redundancy. In our example above, this would involve the payer making seven partial payments of 0.01 BTC, and the receiver claiming the first five of those payments that successfully route. The problem then becomes how to prevent the receiver from claiming all seven parts resulting in an overpayment of 0.02 BTC.

    Neu et al. present a novel scheme called a boomerang contract. The receiver selects the pre-images for the payment parts as shares in a publicly verifiable secret sharing scheme. In our example above, the secret can be reconstructed from six of the seven payment pre-images. The payer then constructs the seven payment parts, but each payment part is associated with a reverse (boomerang) condition that pays the payer back the full amount if the payer knows the full secret. If the receiver claims five or fewer of the payment parts, the payer never learns the full secret, and the boomerang clause cannot be invoked, but if the receiver cheats and claims six or more of the parts, then the payer is able to invoke the boomerang clause of the contract and none of the payment parts can be redeemed by the receiver.

    The paper goes on to describe an implementation of boomerang contracts in Bitcoin using adaptor signatures based on a schnorr signature scheme. Neu also noted that it is possible to create adaptor signatures over ECDSA, so boomerang contracts could theoretically be implemented in Bitcoin today.

  • Remote Side-Channel Attacks on Anonymous Transactions: Florian Tramer presented his work with Dan Boneh and Kenneth G. Paterson on timing side-channel and traffic-analysis attacks on user privacy in Monero and Zcash. (transcript, video, paper).

    Monero and Zcash are privacy-focused cryptocurrencies which use cryptographic techniques (ring signatures and bulletproofs for Monero and zk-SNARKs for Zcash) to hide the sender’s identity, receiver’s identity, and amounts in a transaction from the public ledger. Tramer et al. show that even if these cryptographic constructions are correct, implementation details can allow information about the identities and amounts to be leaked to adversaries on the network.

    When a Monero or Zcash node receives a transaction from the peer-to-peer network, that transaction is passed to the node’s wallet to determine if the transaction belongs to the wallet. If the transaction does belong to the wallet, then the wallet must do additional computation to decrypt the data and amounts from the transaction, and if the wallet pauses its node’s peer-to-peer activity while it is doing this additional computational work, then an adversary can use a timing attack to discover which transactions are associated with which node. The authors demonstrate that these timing attacks can be carried out remotely (across a WAN connection from London to Zurich) and that it may also be possible to use similar timing attacks to reveal the amounts in Zcash transactions.

    The attacks in the paper do not apply to Bitcoin Core, since the difference in computation that the Bitcoin Core wallet does for its own transactions and other transactions is minimal (no advanced cryptography is involved), and since v0.16, wallet operations have been processed asynchronously from peer-to-peer behavior (see Bitcoin Core #10286). However, the observations in the paper are sufficiently general to be interesting to anyone implementing systems on Bitcoin, namely that allowing wallet or application processing to affect peer-to-peer behavior can leak information.

Related: the Optech newsletter summarized a selection of talks from last year’s Stanford Blockchain Conference in Newsletter #32.

Selected Q&A from Bitcoin StackExchange

Bitcoin StackExchange is one of the first places Optech contributors look for answers to their questions—or when we have a few spare moments to help curious or confused users. In this monthly feature, we highlight some of the top-voted questions and answers posted since our last update.

Releases and release candidates

New releases and release candidates for popular Bitcoin infrastructure. Please consider upgrading to new releases or helping to test release candidates.

Notable code and documentation changes

Notable changes this week in Bitcoin Core, C-Lightning, Eclair, LND, libsecp256k1, Bitcoin Improvement Proposals (BIPs), and Lightning BOLTs.

  • Bitcoin Core #13339 allows the wallet name to be passed as an argument to a user-provided walletnotify transaction notification script. Previously only the txid was passed to the walletnotify script, which made it difficult for users running in multi-wallet mode to determine which wallet received the incoming transaction. This change is part of an ongoing effort to enhance multi-wallet support. The change is not currently supported on Windows.

  • Eclair #1325 allows the SendToRoute endpoint to accept routing hints that can help the spending node find a path to the receiving node.

  • BOLTs #682 allows the init message to include a networks field with the identifier (chain hash) for the networks the node is interested in, which may help prevent nodes on one network (e.g. testnet) from connecting to nodes on another network (e.g. mainnet).

  • BOLTs #596 updates BOLT2 to allow LN nodes to advertise that they’ll accept channel opens over the previous maximum value limit of about 0.17 BTC. This is one of the features of the “wumbo” proposal, the other feature being the ability to send larger payments in a channel. See Newsletter #22 for details.

Acknowledgements

We thank Joachim Neu and Tim Roughgarden for their review of a draft of this newsletter’s Stanford Blockchain Conference talk summaries. Any remaining errors are the fault of the newsletter author.