This week’s newsletter requests testing on RCs for both LND and C-Lightning, describes using ECDH for uncoordinated LN payments, summarizes a proposal to add information about delays to LN routing replies, and includes summaries of some interesting talks from the recent ‘Breaking Bitcoin’ conference in Amsterdam. Also included are our regular sections on bech32 sending support and notable changes in popular Bitcoin infrastructure projects.

Action items

• ● Help test C-Lightning and LND RCs: both C-Lightning and LND are in the process of testing Release Candidates (RC) for their next releases. Experienced users of either program are encouraged to help test the RCs so that any remaining bugs can be identified and fixed before final release.

News

• ● Using ECDH for uncoordinated LN payments: Stephan Snigirev sent two ideas to the LN development mailing list in a single post. The first idea involves reusing an existing part of the protocol to enable spontaneous payments, a payment that Alice sends to Bob without her needing to request an invoice from Bob. As described in Newsletter #30, these are currently proposed for LND by having Alice select a pre-image, encrypt it to Bob’s key, and put it into an otherwise-unused part of an LN routing packet when Alice pays the hash of the pre-image. When Bob receives the encrypted pre-image, he decrypts it and releases it to claim the payment.

  Snigirev’s idea eliminates the need to route the encrypted pre-image. He notes that the routing of a payment from Alice to Bob already requires them to have a common shared secret (derived using Elliptic Curve Diffie–Hellman (ECDH). This secret can be hashed once to produce a unique pre-image known to both of them, and that pre-image can be hashed again to be the payment hash. To use this system, whenever Bob receives a payment to a hash that he didn’t create an invoice for, he simply generates the double hash of that session’s shared secret and sees if it matches. If so, he generates the single hash and claims the payment. C-Lightning developer Christian Decker has written a proof of concept patch and plugin for C-Lightning that implements this.

  Snigirev’s second idea allows an offline device, such as a vending machine, to generate a unique LN invoice that can be paid by an online user to another online node that knows how to produce the pre-image and claim the payment on behalf of the offline device. This results in the payer receiving the pre-image as a proof of payment. The payer can then show this proof to the offline device to receive the promised good or service, such as food from a vending machine. Again, this uses a shared secret derived using ECDH—but in this case the secret is shared between the offline device that generates the invoice and the online node that ultimately receives the payment. See Snigirev’s post for the protocol details.

• ● Authenticating messages about LN delays: when a payment fails in LN, it’s often possible for the node attempting the payment to receive an authenticated message from one of the two nodes involved in the payment failure. This allows the paying node to mark the channel between those two nodes as unreliable and choose other channels for future payments. But LND developer Joost Jager notes on the LN development mailing list that “non-ideal payment attempts [can also be] successful payments for which it took a long time to receive the [success] message.” He proposes that each node relaying a message back to the paying node add two timestamps to the message, one timestamp when the node offered to route a payment and one timestamp when it learned either that the payment had failed or that it succeeded. This would allow the paying node to determine where delays occurred during the routing of the payment and avoid those channels in the future.

  To prevent some nodes along the path from lying about other nodes, he propose the error messages and timestamps be protected by a message authentication code. This could also prevent intermediate nodes from corrupting encrypted error messages from endpoint nodes.

  Jager’s proposal also discusses how this type of system could be implemented in the current routing protocol and how it could address concerns related to routing privacy. The proposal has received a moderate amount of positive discussion on the mailing list so far.

Breaking Bitcoin

Breaking Bitcoin was a Bitcoin technology conference that took place in Amsterdam last weekend. It was well attended by both Bitcoin protocol developers and applications engineers. Videos of the Saturday and Sunday are available, as are several transcripts by Bitcoin developer Bryan Bishop (kanzure).

The following talks may be of particular interest to readers of the Bitcoin Optech newsletter:

• ● Breaking Bitcoin Privacy - Chris Belcher, creator of coinjoin implementation Joinmarket, gave an overview of privacy in Bitcoin. Belcher has previously written a literature review on privacy, and this very accesible talk touched on many of the topics in that review. He started by explaining why privacy is important in Bitcoin, described some commonly-used heuristics used by chain analysis companies to link Bitcoin addresses and transactions, and demonstrated how coinjoins and payjoins can be used to break those heuristics and thwart chain analysis. He finished by talking about how layer 2 technologies such as LN have the potential to improve privacy since they remove privacy-leaking data from the blockchain. (transcript).

• ● Bitcoin Build System Security - Chaincode Labs engineer Carl Dong gave a pre-recorded presentation on build security in Bitcoin Core and then answered audience questions over video link. Dong’s talk addressed the question: “If I download a Bitcoin Core executable from bitcoincore.org, how can I know what code I’m running?” The Bitcoin Core project currently uses reproducible gitian builds to ensure that the built binary corresponds to the source code, but Dong explains that reproducibility is not enough—if the reproducible build toolchain uses precompiled binaries, then those toolchain binaries could be compromised and used to undetectably insert malicious code into the compiled binary. Dong went on to describe reproducible and bootstrappable builds, where the number of precompiled binaries used in the toolchain is reduced to a minimum, and he gave an update on his project to integrate guix (pronounced ‘geeks’) builds into Bitcoin Core to minimize trust in the build toolchain. (transcript).

• ● Secure Protocols on bip-taproot - Blockstream engineer Jonas Nick gave an update on some of the work he and his colleagues have been doing to build secure protocols using schnorr signatures and the taproot construction. He started by explaining how the proposed bip-taproot works (more background) and then explained some practical considerations when building protocols using schnorr/taproot: external signers that can’t leak private keys through nonce bias, key aggregation and threshold signatures using Musig, and blind schnorr signatures. As the schnorr/taproot proposal develops and (maybe) approaches activation, companies that wish to take advantage of the new functionality offered by the proposal need to consider these practical aspects of building secure products and protocols. (transcript).

• ● Extracting Seeds from Hardware Wallets - Ledger CSO Charles Guillemet gave an eye-opening talk about security issues with several hardware wallets on the market. He spoke about previously-revealed exploits that he and his team have discovered, as well as new exploits for which he didn’t give the method in order to protect users. The attacks described used a mixture of physical access, side-channels, and exploiting insecure cryptography implementations. This was a fascinating talk for anyone working with or using hardware wallets to protect their Bitcoin. (transcript).

• ● Cryptographic Vulnerabilities in Threshold Wallets - One of the most hotly-anticipated aspects of schnorr signatures is the ability to implement key aggregation and threshold signature schemes. Similar schemes are possible (although much more complex to implement) using the ECDSA signing algorithm which is currently used in Bitcoin. ZenGo co-founder Omer Shlomovits described some of those ECDSA key-aggregation and threshold signature schemes and showed how many of the implementations for those schemes contained bugs due to faulty assumptions when optimizing the algorithms. (no transcript available).

Bech32 sending support

Week 14 of 24 in a series about allowing the people you pay to access all of segwit’s benefits.

There’s a class of multisig users who not only save on fees by using bech32 addresses but who also receive improved security against a potential type of attack called a hash collision. This class of users includes many exchanges and other business users.

To provide some background, all common single-sig addresses on Bitcoin today are the result of a pubkey being turned into a 160-bit RIPEMD160 hash digest. It’s theoretically possible for an attacker to generate a second pubkey that they control, hash it, and produce the same address. However, if we assume that the hash function produces perfectly unpredictable output, then the chance of this happening with a 160-bit hash function like RIPEMD160 is 1-in-2¹⁶⁰ for each pubkey the attacker tries.

For comparison, Bitcoin miners perform 2⁸⁰ hashing operations roughly every 5 hours as of this writing. The SHA256d hashing operation miners perform isn’t the same as used in this RIPEMD160 collision attack, so their equipment can’t be repurposed for that use, but we can use this as a reference rate for the number of brute force operations a real-world system can perform today (at great expense). At that rate, an attack that performed the 2¹⁵⁹ operations necessary to have a 50% chance of succeess would take about 25 million times the estimated age of the universe so far.

However, when multisig addresses are being used, the attacker may be one of the parties involved in generation of the address and so may be able to manipulate what address is finally chosen. For example, Bob sends his pubkey to Mallory expecting that Mallory will send her pubkey back. Then he expects they’ll each put the pubkeys into a multisig script template, hash it into an address, and someone will deposit money into that address.

Mallory instead takes the script template and Bob’s pubkey, inserts one of her pubkeys without telling Bob about it, and hashes it into an address. This allows her to see the address Bob will accept before Mallory has committed to using that pubkey. Mallory can then compare this address to a database of addresses generated from scripts that pay only her. If there’s a match (collision) between two of the addresses, she sends the pubkey back to Bob, waits for money to be deposited into the address, and then uses the script from her database to steal the money. If there’s not a match, Mallory can try again with a different pubkey over and over until she succeeds (if we assume she has unlimited time and resources).

Although this seems like the same brute force attack described earlier with a 1-in-2¹⁶⁰ chance of success per attempt, we have to consider the size of Mallory’s database. If we imagine the database has 100 addresses, then each different pubkey she tries has a 100-in-2¹⁶⁰ chance of success because it succeeds if it matches any one of the addresses in Mallory’s database.

This type of attack is called a collision attack. There are several algorithms with different CPU/memory tradeoffs for collision attacks, but the general rule security researchers follow is that a collision attack against a perfect hash function reduces its security to the square root of its number of combinations, i.e. it halves its size in bits. That means we can roughly assume that RIPEMD160’s security is reduced to 80 bits—which is the same number of operations we mentioned Bitcoin miners perform every 5 hours today using currently-existing technology. Again Bitcoin mining equipment can’t be used for this attack, and for an attacker to design and build enough custom equipment to find a collision in five hours might cost them billions of dollars—but it’s a theoretically possible attack that should concern those storing large values in P2SH, especially as custom hardware gets faster and cheaper. It’s also possible that there are variations on the collision attack that are easier and cheaper to execute because of weaknesses in the RIPEMD160 function.

It is possible to design multisig setup protocols so that they don’t have this problem and so that their collision resistance remains at 160 bits. However, the developers of segwit believed it was better to use a slightly longer hash function for segwit’s P2SH analog—P2WSH—so that users didn’t need to worry about these cryptographic particulars. For that reason segwit P2WSH uses the same SHA256d function used elsewhere in Bitcoin that provides 256-bit security for single-party cases and 128-bit worst-case security in multi-party use cases. To to continue our rough comparison, if we consider 80 bits to be equivalent to five hours of Bitcoin mining, 128 bits is equivalent to 160 billion years of mining.

Before we conclude this section, we do want to ensure a few things are clear:

1. We think it’s unlikely that anyone today has the ability to execute the attack described (but we can’t rule it out as a risk).

2. The attack can only be used at the time addresses are being created (although the actual theft could occur a long time afterwards).

3. The attack only applies to multi-party multisig addresses. If you’re a single party using P2SH multisig with only your own trusted devices or you’re using P2SH-P2WPKH (single-sig addresses), there’s no risk to you from this attack.

4. The attack applies to P2SH-wrapped segwit P2WSH addresses as well as regular P2SH addresses. To eliminate the risk, you have to use native segwit (bech32) addresses or a secure key exchange protocol.

To summarize, users of multi-party multisig who want the utmost in security should be migrating to bech32 P2WSH addresses to take advantage of their extra collision resistance. As users make that migration, it’ll become even more important for services to ensure they implement bech32 sending support so that they can send payments to those security-conscious users.

Notable code and documentation changes

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

• ● Bitcoin Core #15024 allows the importmulti RPC to derive specific private keys using an output script descriptor and then import the resultant keys.

• ● Bitcoin Core #15834 fixes the transaction relay bug introduced in #14897 where a node would sometimes stop receiving any new mempool transactions despite having a good connection to other nodes (see Newsletter #43 for details and previous mitigations, or #15776 for an excellent description of the bug and an initially-proposed solution).

• ● LND #3133 adds support for “altruist” watchtowers and clients. Watchtowers send breach remedy transactions (justice transactions) on behalf of clients that are currently offline to ensure that those clients’ counterparties can’t steal any money. The ideal watchtower for general deployment is incentivized to do this by receiving a modest monetary reward for sending remedy transactions, but managing the incentive adds complexity—so this initial version of the complete system uses simpler altruist watchtowers that don’t receive any reward via the protocol but otherwise provide both the client and server components for complete enforcement. You can setup a watchtower for your own channels or you can use the watchtowers of reliable friends. All the configuration parameters necessary are documented in LND’s runtime help. Developer Will O’Beirne also has an example tutorial that helps you setup watchtowers, attempt to breach a test channel, and then observe the watchtower protect that channel’s funds.

• ● LND #3140 adds support for RBF and CPFP fee bumping when LND is sending sweep transactions using one or more of its onchain UTXOs.

• ● LND #3134 allows users to integrate LND with the Prometheus monitoring solution for collecting statistics and sending alerts.

• ● C-Lightning #2672 adds new RPCs that can be used to open a channel using funds from an external wallet. The fundchannel_start RPC starts opening a new channel with a specified node and returns a bech32 address that the external wallet should pay using only segwit inputs and without broadcasting the transaction. When that transaction has been created, its serialized form can be provided to the fundchannel_complete RPC to securely finish the channel negotiation and broadcast the transaction. Alternatively, the fundchannel_cancel RPC can be called to abort the channel setup before funds are sent. Because most external wallets will broadcast transactions automatically, these options need to be enabled explicitly using a configuration option—but they make it possible for external wallets to better integrate with C-Lightning directly.

• ● C-Lightning #2700 limits the amount of gossip requested by only requesting gossip from a subset of a node’s peers. This continues the work across all major LN implementations of trying to reduce the amount of data sent via gossip now that the network has grown to thousands of peers.

• ● C-Lightning #2699 extends the fundchannel RPC with a new utxo parameter that allows the user to specify which of the UTXOs from C-Lightning’s built-in wallet to use to fund a new channel.

• ● C-Lightning #2696 adds a new listtransactions RPC method that lists all the onchain transactions created by the program and what they were used for (setup, unilateral close, mutual close, or anti-cheat). Other changes in this PR ensure that all the necessary data to provide these results is stored in the database.

• ● Eclair #1009 allows Eclair to search through gossiped node announcements to find the IP address of channel peers by their pubkeys in case any peer gets disconnected and has its IP address change.

• ● BIPs #555 adds BIP136 for bech32-encoded transaction positions within the block chain. For example, the position identifier of the first transaction in the chain (the Genesis block’s generation transaction) is tx1:rqqq-qqqq-qmhu-qhp. This idea was first proposed to the Bitcoin-Dev mailing list over two years ago with suggested use cases including identifying which transactions contain information useful to third-party applications, such as timestamped decentralized identity references.