Iceberg: Nested Threshold Signatures for Lightning

Since the Taproot softfork, Bitcoin has allowed Schnorr digital signatures to be used when spending on-chain coins. Recently, the BOLTs (Lightning specification) have introduced support for “Taproot channels” which are Lightning channels that use BIP 327 MuSig to aggregate the two channel participant’s keys into a single key so that on-chain channel activity is normally indistinguishable from simple single-party bitcoin payments. This transition makes it more difficult for one channel party to use threshold custody schemes using Script (OP_CHECKMULTISIG/OP_CHECKSIGADD) but is still compatible with interactive off-chain threshold signature schemes. The scheme FROST is the most well-known Schnorr threshold signature, but it is ill-suited for being nested inside of MuSig in most contexts.

In this post we unpack our proposal, Iceberg, for how to sign in a threshold custody Lightning Network channel. This was a joint work with Paul Gerhart and Jesse Posner, and Matias Furszyfer wrote an implementation and performed benchmarking.

Paper Link!

Threshold Key Management in Multi-Party Bitcoin

In multi-party Bitcoin contracts such as Lightning channels (or Discreet Log Contracts or Ark or many others), funds are put into shared custody “funding transactions” which are locked by \(n\)-of-\(n\) (\(n=2\) for Lightning) multi-signatures made up of all involved parties. Before sending funds to a funding transaction, all parties generate and sign all possible transactions that may spend this funding transaction. This ensures that there are an enumerated set of ways any party can unilaterally spend the funding transaction (since they already have all the necessary signatures) and no new spending conditions can be added without everyone’s approval. With the introduction of the Taproot soft fork, Schnorr signatures became available to Bitcoin protocols and thus it is becoming standard practice to use protocols such as BIP 327 MuSig to replace script-enforced \(n\)-of-\(n\) contracts with a single aggregate key that enforces the same \(n\)-of-\(n\) constraint via key aggregation and signature aggregation. This provides the benefit of a smaller and less distinct on-chain footprint, and thus better privacy and lower fees. However, it complicates key management as it is now harder to use a threshold \(t\)-of-\(n\) key sharing setup within these key aggregation protocols, and threshold key management is the standard practice for serious custodians of Bitcoin to protect themselves from attacks and from losses of secrets.

In the Lightning Network, node operators are required to keep their private key online and ready to sign, but this means they have a single point of failure and a single vulnerability that holds all of their channel funds. It would be preferable for large channel operators to be able to have some offline backup keys as well as to be able to tolerate the corruption of some bounded number of online keys as is standard with threshold key management. This is what nested threshold signatures provide: One participant in a BIP 327 MuSig-based contract can use a nested threshold signature protocol to construct a single aggregate MuSig participant key for themselves that actually consists of many secrets. Furthermore, some of these secrets can be air-gapped and offline cold storage secrets and some subset of secrets may be corrupted without losing channel funds.

Nested Thresholds via RSS

Background

Iceberg only functions under certain assumptions that were chosen specifically with the Lightning Network in mind.

Lightning functions by having a commitment transaction that spends the \(2\)-of-\(2\) funding transaction, giving each party their portion of the funds back. But when a Lightning payment is made, a new commitment transaction is constructed and signed that has the updated balances of the two parties. This transaction isn’t final until it is no longer possible to use the previous commitment transaction anymore, as doing so would revert the balances back to the previous state. There is no simple way to invalidate a Bitcoin transaction once it has been signed and made valid, so what Lightning channels do is they include a poison pill clause to the commitment transaction that allows one party to take all of the funds in the funding transaction if they know a secret for that commitment called the revocation secret. Each party then shares the previous commitment transaction’s revocation secrets with each other so that if either party publishes that old commitment transaction, the other party then gains the ability to sweep all of the funds. Thus, only the most recent commitment transaction can then be used without risking all of your funds being taken by the other party of the channel.

With this background in mind, there are a couple complications when trying to thresholdize a Lightning node. First, it is very important that the honest (i.e., non-corrupted) signing devices agree on the current channel state so that they only sign transactions that they should be signing and never sign old commitment transactions. Even if honest parties do not have their keys compromised they should not be willing to sign arbitrary Lightning transactions as this can lead to a complete loss of funds through signing an already-revoked commitment transaction. Operationally, this means that we need Byzantine fault tolerant (BFT) state agreement, which requires an honest online majority of signing devices to ensure that honest offline devices can learn the correct channel state upon coming online. Second, it is not safe to have a single device know the revocation secrets for your side of the channel, as that is again a single point of failure that an attacker could compromise to sweep all channel funds just as if you had revoked the current commitment transaction without knowing you had. This requires a threshold multi-party computation (MPC) in order to compute revocation secret hashes without having any party learn the revocation secret until it is time to revoke an old commitment transaction. This is similar to how we have multiple online signing devices that collectively compute an aggregate signature, but instead they need to compute an aggregate hash of a secret without individually knowing that secret.

At first glance, computing our shachain of revocation secrets inside of an MPC appears prohibitively expensive. SHA-256 does not have the algebraic structure that makes threshold Schnorr signing efficient, so it must instead be evaluated as a Boolean circuit. In our implementation and benchmarks, one shachain hash operation required 1,614 sequential communication rounds and took 65.5 seconds between machines in four cloud regions across the United States and Europe, running maliciously secure three-party computation tolerating one corrupted device.

Fortunately, future secrets can be pre-computed in parallel and placed into a lookahead buffer before they are needed. Refilling a buffer of 1,024 secrets takes about 12.6 minutes over the same wide-area network, but buys enough secrets to sustain one commitment revocation every 0.74 seconds for a channel. The computation itself takes only 1.09 seconds of CPU time per signing device; almost all of the elapsed time is spent waiting for network round trips.

Once a secret has been prepared, revealing it requires no MPC computation at all. We store a public masked value together with a replicated sharing of the mask, so an authorized quorum can send its shares, verify the replicated copies, and reconstruct the secret in a single communication round. The reconstructed secret is then checked against the elliptic curve point published for that commitment. This took 139 milliseconds in our experiment. Prepared secrets use the same replicated sharing structure as the long-term seed, so changing which signing devices form the online quorum does not require rebuilding the buffer.

It is also possible that we decide to drop the SHA-chains that Lightning uses for revocation secrets in the future, as they aren’t particularly important.

These are the two main threshold but non-signature structures that need to be implemented to safely use a threshold within a lightning node. That said, both of these can be done “out-of-the-box” with existing cryptographic primitives, and our contribution is solving the nested threshold signature mechanism for a Lightning channel.

Replicated Secret Sharing

As I discuss in a previous blog post, Replicated Secret Sharing (RSS) is the practice of creating a threshold shared secret by having each party store a list of secrets, where the same secrets are known among many parties (hence replicated), such that any \(t-1\) parties are missing at least one secret and any \(t\) parties know all of the secrets. The aggregate secret is then a de-duplicated sum of all of the secrets involved. For example, if Alice and Bob and Carol want to use RSS to have a \(2\)-of-\(3\) shared secret, they could do a DKG in which Alice learns \(x_1\) and \(x_2\), Bob learns \(x_2\) and \(x_3\), and Carol learns \(x_3\) and \(x_1\), and the aggregate secret key is \(x = x_1 + x_2 + x_3\). This way, any one party is missing one of the three secret summands and any two parties collectively know all three. This is not a widely-used practice as it does not scale well to large signing sets, but for standard key management use-cases, it is perfectly practical.

In my previous work I have proven that it is secure to nest MuSig within MuSig in a similar fashion to what is necessary for nested threshold signatures, but MuSig does not support thresholds (only \(n\)-of-\(n\)). So the idea behind Iceberg is to do an \(N\)-of-\(N\) nested MuSig but where the \(N\) secrets are not participant private keys, but rather RSS secret summands (of which there are significantly more than the number of parties, \(N >> n\), but still practical for key management use cases). This way, any \(t-1\) parties will be missing at least one of the \(N\) secrets and cannot satisfy the \(N\)-of-\(N\) nested MuSig spending conditions, while any \(t\) parties will collectively know all \(N\) secrets that can be combined to generate a nested MuSig aggregate partial signature. In essence, RSS lets us transform an \(N\)-of-\(N\) mechanism into a \(t\)-of-\(n\) mechanism (where \(N = \binom{n}{t-1}\) is the number of \((t-1)\)-sized subsets of \(n\) signers).

However, the scheme I’ve just described is insecure in general when applied to secret nonce values, which cannot be re-used for signing different messages without leaking the (aggregate) private key. Consider the following attack: We have a \(3\)-of-\(3\) MuSig using the secret keys \(x_1\), \(x_2\), and \(x_3\), as distributed among Alice, Bob, and Carol earlier, that functions as a \(2\)-of-\(3\) aggregate secret key \(x = x_1 + x_2 + x_3\). If Alice is malicious, she could go to Bob asking to sign one message (and claiming that Carol is offline) and then she could go to Carol asking to sign another message (claiming that Bob is offline). If Bob and Carol each sign their given (different) messages, then the same aggregate (replicated) nonce was effectively used twice for different messages and Alice learns this value and can then learn the aggregate private key from the signature as a result. This is why state agreement is not only important for Lightning channel functions, but also for enabling this relatively naive RSS transformation from \(N\)-of-\(N\) to \(t\)-of-\(n\). With state agreement we can guarantee that all honest parties collectively only ever agree to sign a single message for any given aggregate nonce.

There is also an alternative approach to resisting this attack when state-agreement is not an option (such as when there is no honest super-majority as required for BFT), but it requires a small deviation from BIP 327 as stated, so it is a little out of scope and is the subject of my next paper which is still in preparation. Stay tuned!

Optimizing for Production: VPSS and Benchmarks

While the basic RSS approach provides the threshold we need, it comes with an exorbitant storage and communication cost. This is where using VPSS allows us to transform most of the storage and communication costs to mimic Shamir secret sharing based schemes.

Pseudo-random Secret Sharing was first proposed by Cramer et al., where their two key insights were that many RSS secrets can be generated with a single setup, and that RSS-distributed secret summands can be locally (without communication) converted into Shamir secret shares for the same secret. This process is known as share conversion.

Unlike Shamir secret shares, RSS shares are additive which means that we can use pseudo-random functions (PRFs) to turn a single RSS setup into an arbitrary number of secrets shared across the same setup. Namely, rather than taking the secrets from the one setup to be summands, you take them to be seeds to a PRF and then for each new secret, you generate a unique session identifier (\(sid\)) and use this as input to each seeded PRF to deterministically generate replicated secrets across the same structure. Hence, while Shamir secret sharing has a lighter-weight DKG (in terms of the size of over-the-wire communications), it has the cost of having to do a new DKG every time. Meanwhile with the process we just described, one verbose RSS DKG leads to arbitrarily many shared secrets “for free.”

However, RSS has another downside for repeated use: each party has a long list of secrets and must communicate partial signatures for many secret shares each time we want to use them. This is awful compared to Shamir secret sharing where each secret share is a single secret value requiring only a single partial signature. This is where share conversion comes to the rescue! We do a single RSS setup for seeding the PRFs, and then we locally perform share conversion to combine our list of secret summands into a single Shamir secret share of the same (aggregate) private value. This means that after the initial setup, all communications that use shared secrets do not require large messages over-the-wire and instead look like normal Shamir secret sharing-based partial signature messages. This process of using RSS to seed PRFs and then using share conversion to optimize communications and computations is known as Pseudo-random Secret Sharing (PSS).

Komlo and Goldberg introduced a verifiable variant of PSS, VPSS, in their Arctic paper, which only works in the honest majority setting (which we are already in due to the constraints of state agreement protocols). This is discussed in my previous post, but basically verifiability here refers to the ability of participants in an honest-majority PSS to detect bad behavior by only looking at aggregate values. This means that we can use an aggregator (as is done in MuSig) to optimize communication without having to introduce additional state for our state agreement mechanism to keep track of, since signers can verify that their signing inputs are correct and thus the same as every other honest signer’s inputs assuming they pass verification.

In all, using VPSS means that after a single RSS seed distribution, all new nonce shares are computed as a single secret share (just as in Shamir, but without communication required) with a corresponding single partial signature, making the communication complexity of Iceberg signing superior to the communication complexity of Shamir-based (and other interactive DKG-based) threshold signatures after setup. The primary downside is that each party must still store all of their RSS seeds (which is a number that scales poorly with the number of signers), and must do a local computation that scales with the number of seeds for each nonce generated. We think that the benefits far out-weigh the costs for key management use-cases, and there are also further benefits we haven’t discussed here that the aggregate nonce does not depend on the signing set (as it does in FROST), making PSS an ideal mechanism for nonce generation in a nested threshold scheme where the aggregate nonce must be known before the message to be signed or the signing set is known.

Benchmarks in a real Lightning node

To quantify the cost of using Iceberg, we implemented the whole stack, starting from an Iceberg module inside of secp256k1, Bitcoin’s main cryptographic library, then JVM bindings on top of it, and finally integration into the existing taproot channels in eclair. The only change we made is which functions are called to sign for the funding key. The rest runs unmodified. The counterparty is normal eclair, and the modified setup has its channel test suites pass without changes with signing reproducing the scheme’s reference implementation byte-for-byte. Since signing needs \(2t-1\) members online, a \(2\)-of-\(4\) group keeps signing with one member down, a \(3\)-of-\(7\) with two, and a \(4\)-of-\(10\) with three. Replacing a single key with these groups costs between \(4\) and \(18\) ms of CPU per payment, growing quadratically with the threshold \(t\) and only weakly with the group size \(n\):

CPU time of the channel logic. Each row averages 1,500 back-to-back comparisons of a bare MuSig2 payment and the same payment with the group, on a 10-core AMD EPYC 7543. Compute is priced at $0.04 per vCPU-hour, and payments per second is what one core sustains.

The additions are modest because signing is a minor part of a Lightning payment. A payment updates its commitment transaction twice, once to add the HTLC and once to settle it, and those two updates are roughly four fifths of its processing, with the sender’s onion construction making up most of the rest. The partial signature Iceberg replaces takes about 1.5 ms, under 3% of the total. The group’s added cost lands in those two updates and nowhere else:

At this scale, signing is not what limits a threshold Lightning node. The actual bounding costs are operational. A signing quorum has to be online for every payment, and once members run on separate machines, the time goes to network round trips rather than to computation. Both come with the setting, not with Iceberg. The full benchmarks, across all twenty configurations the scheme can express, are in the benchmark repository.

Future Work

Iceberg solves the problem of threshold signing within a Lightning context, but this utilizes some heavy assumptions that are satisfied in that setting and that don’t apply in other contexts.

Arctic2 is a new Schnorr threshold signature based on PSS that does not require an honest majority, so it supports any threshold and does not rely on state agreement for its security. Furthermore, it is designed to be perfect for nesting within a version of MuSig2 that is a slight variation of BIP 327. I have completed the security proofs for this new signature scheme (including in the nested setting) and am currently preparing a paper on this scheme.

Our recommendation for the Lightning use-case is Iceberg without Arctic2 because the downsides of Iceberg relative to nested Arctic2 (honest majority and state agreement) are already requirements for threshold lightning nodes, and Iceberg has the benefit of not modifying the outer BIP 327 MuSig at all.

However, there are other use-cases where threshold signatures nested within MuSig are desirable where there is no such state agreement or honest majority constraint, and in these settings nested Arctic2 supports threshold schemes that are not possible with Iceberg. We will be proposing creating a version of BIP 327 that has a single added parameter and will otherwise be unchanged. Implementations that use this variant will be able to have nested threshold participants appear indistinguishable from single keys as usual.

Security Argument Appendix

This appendix requires more background than the rest of this post. Check out cryptocamp as a resource if you want to learn more!

Security/unforgeability in the nested threshold setting is described in Figure 3 of the Iceberg paper, and essentially consists of an attack game where the adversary is allowed to corrupt up to t-1 signers, and they then perform key generation with the honest parties and then have access to the honest signers signing interfaces. After making as many signing queries under concurrent signing sessions as they like, the adversary must then produce a forgery, which is a signature that verifies under the aggregate public key for some message that was not partially signed by any honest party.

Similarly, security/unforgeability in the nested multisignature setting (as is the setting for Nested MuSig) consists of there being only a single honest party, and the adversary may interact with them in concurrent signing sessions in which they control as many of the other participants as they wish and then ultimately produce a forgery for an aggregate key involving the honest party’s key for a message that was not signed by the honest party for this aggregate key’s group.

The Iceberg security proof reduces the unforgeability of Iceberg to the unforgeability of Nested MuSig. It intuitively follows exactly the intuition that Iceberg is essentially performing VPSS on top of MuSig (\(N\)-of-\(N\)) keys in the presence of a state agreement mechanism. The first step is to show that the security of Iceberg is equivalent to the security of an un-optimized version of Iceberg where we directly use RSS (with lists of nonce secrets and partial signatures and no share conversion), this is a straightforward simulation where the reduction simply performs share conversion itself to make the interfaces match. Next, the un-optimized version has its security reduced to the security of Nested MuSig. First we embed the Nested MuSig challenge key as an RSS share not known to the adversary; at least one must exist due to the corruption threshold being larger than the number of corruptions. Next, every other share has all computations performed honestly and cached, which is possible since the state agreement mechanism ensures that no honest party will ever use a replicated secret in a computation that is distinct from any other honest party. Lastly, some Random Oracle programming is used to match interfaces so that we can compute partial signatures for the embedded challenge share using the Nested MuSig EUF-CMA signing oracle. And this is everything! There is no forking or rewinding, and the only loss of advantage is a tiny negligible amount due to the possible failure of the Random Oracle programming. Thus, this is a tight straight-line reduction of the security of Iceberg to the security of Nested MuSig.