New Implementation For Bitcoin Mixing Service CoinJoin Improves Sybil Resistance

This week’s Bitcoin Optech newsletter details a JoinMarket implementation improvement for CoinJoin bitcoin mixing and more.

The Bitcoin Optech newsletter provides readers with a top-level summary of the most important technical news happening in Bitcoin, along with resources that help them learn more. To help our readers stay up-to-date with Bitcoin, we’re republishing the latest issue of this newsletter below. Remember to subscribe to receive this content straight to your inbox.

This week’s newsletter follows up on a previous description about fidelity bonds in JoinMarket and includes our regular sections with the summary of a Bitcoin Core PR Review Club meeting, suggestions for preparing for taproot, announcements of releases and release candidates, and descriptions of notable changes to popular infrastructure projects.

News

Implementation of fidelity bonds: the JoinMarket 0.9.0 implementation of coinjoin includes support for fidelity bonds. As previously described in Newsletter #57, the bonds improve the sybil resistance of the JoinMarket system, increasing the ability for coinjoin initiators (“takers”) to choose unique liquidity providers (“makers”). Within days of release, over 50 BTC (currently valued at over $2 million USD) had been placed in timelocked fidelity bonds.
Although the specific implementation is unique to JoinMarket, the overall design may be useful in other decentralized protocols built on top of Bitcoin.

Bitcoin Core PR Review Club

In this monthly section, we summarize a recent Bitcoin Core PR Review Club meeting, highlighting some of the important questions and answers. Click on a question below to see a summary of the answer from the meeting.

Prefer to use txindex if available for GetTransaction is a PR by Jameson Lopp which improves the performance of GetTransaction (and, by extension, the getrawtransaction RPC for users) by utilizing the transaction index (txindex) when possible. This change fixes an unexpected performance loss in which a call to getrawtransaction on a txindex-enabled node is significantly slower when called with the hash of the block that includes the transaction. The review club evaluated the cause of this performance issue by comparing the steps to retrieve a transaction with and without txindex.

What are the different ways GetTransaction can retrieve a transaction from disk?
The transaction can be retrieved from the mempool (if unconfirmed), by retrieving the entire block from disk and searching for the transaction, or by using txindex to fetch the transaction from disk by itself.
Why do you think that performance is worse when the block hash is provided (when txindex is enabled)?
Participants guessed that the bottleneck was in the deserialization of the block. Another process unique to fetching the entire block – albeit less time-consuming – is a linear search through the entire list of transactions.
If we are looking up the transaction by block hash, what are the steps? How much data is deserialized?
We first use the block index to find the file and byte offset necessary for accessing the block. We then fetch and deserialize the entire block and scan through the list of transactions until we find a match. This involves deserializing about 1-2MB of data.
If we are looking up the transaction using the txindex, what are the steps? How much data is deserialized?
The txindex maps from transaction id to the file, block position (similar to the block index), and the offset within the blk*.dat file where the transaction starts. We fetch and deserialize the block header and transaction. The header is 80B and allows us to return the block hash to the user (which is information not stored in the txindex). The transaction can be any size but is typically thousands of times smaller than the block.
The first version of this PR included a behavior change: when an incorrect block_index is provided to GetTransaction, find and return the tx anyway using the txindex. Do you think this change is an improvement, and should it be included in this PR?
Participants agreed that it could be helpful but misleading, and that notifying the user of the incorrect block hash input would be better. They also noted that a performance improvement and behavior change would be best split into separate PRs.

Preparing For Taproot #8: Multisignature Nonces

A weekly series about how developers and service providers can prepare for the upcoming activation of taproot at block height 709,632.

In last week’s column, we wrote about multisignatures and gave an example using MuSig2. Our description appears to have been technically correct, but several cryptographers who contributed to MuSig2 worried that the way we suggested using it was dangerous. We updated our description to address their immediate concerns and then began researching the issue more thoroughly. In this post, we’ll look at what we learned may be the greatest challenge for safely implementing multisignatures: avoiding nonce reuse.

To validate a signature in Bitcoin, you fill out a publicly known equation with the signature, the message that was signed (e.g. a transaction), your public key, and a public nonce. It’s only possible for you to balance that equation if you know your private key and the private form of the nonce. Thus anyone seeing such a balanced equation considers the signature for that message and public key to be valid.

The motivation for including the signature and the message in the equation is obvious. The public key is a stand-in for your private key. What’s the public nonce for? If it wasn’t there, every other value in the equation except for your private key would be known, meaning we could use basic algebra to solve for that single unknown value. But algebra can’t solve for two unknown values, so the private form of the nonce serves to keep your private key secret. And, just as your public key is a stand-in for your private key in the signature equation, the public form of the nonce stands in for its private form.

Nonces in this context are not only numbers used once but numbers that must only ever be used once. If you reuse the same nonce with two different signatures, the two signature equations can be combined, the nonce can be canceled out, and someone can again solve for the only remaining unknown value—your private key. If you use BIP32 standard derivation (non-hardened derivation), which likely nearly all multisignature wallets will do, then the revelation of one private key means the reveal of every other private key in the same BIP32 path (and possibly in other paths as well). That means a multisignature wallet which has received bitcoins to a hundred different addresses will have every one of those addresses compromised for the signer who reuses even a single nonce.

Single-sig wallets, or those using script-based multisig, can use a simple trick to avoid reusing nonces: they make their nonce dependent on the message they’re signing. If there’s any change to the message, the nonce changes, and so they never reuse a nonce.

Multisignatures can’t use this trick. They require each cosigner contribute not just a partial signature but also a partial public nonce. The partial public nonces are combined together to produce an aggregated public nonce which is included with the message to sign.

That means it’s not safe to use the same partial nonce more than once even if the transaction stays the same. If, the second time you sign, one of your cosigners changed their partial nonce (changing the aggregated nonce), your second partial signature will effectively be for a different message. That reveals your private key. Since it’s impossibly circular for every party to make their private nonce dependent on all the other party’s partial public nonces, there’s no simple trick to avoid nonce reuse in multisignatures.

At first glance, this doesn’t seem like a big problem. Just have signers generate a new random nonce each time they need to sign something. This is harder to get right than it sounds—since at least 2012, people have been finding bitcoin-losing bugs in wallets that depended on generating random nonces.

But even if a wallet does generate high-quality random nonces, it has to ensure each nonce is only used a maximum of a single time. That can be a real challenge. In the original version of our column last week, we described a MuSig2-compatible cold wallet or hardware signing device that would create a large number of nonces on its first run. The wallet or device would then need to ensure each of those nonces was never used with more than one partial signature. Although that sounds simple—just increment a counter each time a nonce is used—it can be a real challenge when dealing with all the ways software and hardware can fail by accident, not to mention how they can be affected by external and possibly malicious intervention.

Perhaps the easiest way for a wallet to reduce its risk of nonce reuse is to store nonces for as short a time as possible. Our example from last week suggested storing nonces for months or years, which not only creates a lot of opportunity for something to go wrong but also requires recording nonces to a persistent storage medium which may be backed up and restored or otherwise put into an unexpected state. An alternative way to use MuSig2 would be to only create nonces on demand, such as when a PSBT is received. The nonces could be kept in volatile memory for the short time they were needed and so be automatically destroyed (made unreusable) in several cases of the unexpected happening, such as a software crash or a loss of power.

Still, the cryptographers working on this problem seem very concerned about the lack of foolproof way to prevent nonce reuse in the original MuSig protocol (MuSig1) and MuSig2. MuSig-DN (deterministic nonce) does offer a solution, but it’s complex and slow (an alpha implementation takes almost a second to create a nonce proof on a 2.9 GHz Intel i7; it’s unknown to us how long that might take on a 16 MHz hardware signing device with a much less sophisticated processor).

Our advice to anyone implementing multisignature signing is to consider stopping by the #secp256k1 IRC room or another place where Bitcoin cryptographers congregate and describe your plans before you make any major investments of time or resources.

Releases And Release Candidates

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

C-Lightning 0.10.1 is a release that contains a number of new features, several bug fixes, and a few updates to developing protocols (including dual funding and offers).
Bitcoin Core 22.0rc2 is a release candidate for the next major version of this full node implementation and its associated wallet and other software. Major changes in this new version include support for I2P connections, removal of support for version 2 Tor connections, and enhanced support for hardware wallets.

Notable code and documentation changes

Notable changes this week in Bitcoin Core, C-Lightning, Eclair, LND, Rust-Lightning, libsecp256k1, Hardware Wallet Interface (HWI), Rust Bitcoin, BTCPay Server, Bitcoin Improvement Proposals (BIPs), and Lightning BOLTs.

Bitcoin Core #21528 aims to improve the p2p propagation of full node listening addresses. Exposure to a diverse set of addresses is important for nodes to be protected against network partitions such as eclipse attacks. When Bitcoin Core nodes receive an address message containing 10 or fewer addresses, they forward it to 1 or 2 peers. This is the primary technique used to self-advertise addresses, so sending to peers that would not relay these addresses would effectively stop or “black hole” the propagation through the network. Although propagation failures cannot be prevented in the malicious case, this patch improves address propagation for the honest cases, such as for block-relay-only connections or light clients.
This update identifies whether or not an inbound connection is a candidate for forwarding addresses based on whether it has sent an address related message over the connection, such as addr, addrv2, or getaddr. This behavior change could be problematic if there is software on the network that relies on receiving address messages but never initiates an address-related message. Therefore, the author took care to circulate this proposed change before it was merged, including posting it to the mailing list and researching other open source clients to confirm compatibility.
LND #5484 allows storing all data in a single external Etcd database. This improves high-availability deployments by making cluster leadership changes instantaneous. The corresponding LND clustering documentation was previously covered in Newsletter #157.
Rust-Lightning #1004 adds a new event for PaymentForwarded that allows tracking when a payment has been successfully forwarded. Since successful forwarding may earn fees for the node, this allows tracking that income for the user’s accounting records.
BTCPay Server #2730 makes the amount optional when generating invoices. This simplifies the payment flow in cases where the operator delegates the choice of the amount to the user, e.g. when topping up an account.