Open Problems

2023

ZK-(SNARKS) Applications in Bitcoin

Author: Jonas Nick - Blockstream ( jonasdnick@gmail.com )

Prove properties of a blind signed transaction

There are often situations where for improved privacy you want a cosigner to be blind. However, a fully blind cosigner is as useful as having no cosigner at all. Therefore, we want that the cosigner can verify in zero-knowledge that the transaction fulfills certain properties, for example that the output amount does not exceed a threshold of that it goes to a specific receiver.

This may be also interesting to build a better “smart contracts unchained.” Instead of showing that you have the inputs to satisfy a certain smart contract, you just prove that those inputs exist.

UTXO-set commitments

Idea: Use a µcash-style accumulator instead of a Merkle tree (utreexo). But that application doesn’t need zero-knowledge.

HTLC<->PTLC bridge

Given hash h and point P, prove that h = hash(x) and P = x*G. This may be useful when adding PTLC to the existing network of HTLC nodes.

Other Applications

• Deterministic musig (similar to MuSig-DN)
• Proof of reserves
• Add OP_ZKP opcode to script
• Replace all witness data in block with succinct proof that the witness data exists.
• In Bitcoin this doesn’t save that much space (compared to ETH) since there isn’t all that much witness data and it’s already discounted.
• Prove that a UTXO set was generated by a list of valid blocks (aka ZeroSync)
• This reduces resources for IBD and keeping up with the chain and may allow full node in browser or phone.
• It’s even better with utreexo because then the client doesn’t need to receive the entire UTXO set

Schnorr signatures

Author: Tim Ruffing - Blockstream ( crypto@timruffing.de )

Blind Schnorr multi-party signatures

Blind Schnorr multisignatures and threshold signature schemes (i.e., some cosigners are blind) have great potential to enhance user’s privacy in semi-custodial applications with a semi-trusted cosigner, e.g., a server that cosigns transactions of a user only if the user presents a second authentication factor.

Due to the fact that reuse of public keys is discouraged for privacy reasons, schemes will need to hide the signed message and the aggregate public key from blind cosigners.

While there have been ad-hoc proposals in that direction¹², they lack a formal security analysis, including a proper security definition.

Practical deterministic Schnorr multi-party signatures

Implementations of DL-based signature schemes such as ECDSA and Schnorr signatures typically de-randomize the signing algorithm to avoid catastrophic accidents caused by bad random sources.

However, the same de-randomization techniques do not apply to multi-party signatures, and thus all “natural” constructions of Schnorr multi-signature and Schnorr threshold signature schemes critically rely on the availability of good randomness during signing.

While it is possible³⁴⁵ to de-randomize multi-party signing protocols, all known protocols suffer from a lack of efficiency and in particular a high implementation complexity.

More research is necessary to obtain practical protocols for which, in typical scenarios, the additional risk stemming from the implementation complexity is lower than the risk of relying on randomness.

1. Schnorr Blinded Custody (ref) ↩

2. Private Collaborative Custody with FROST (ref) ↩

3. MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces. Jonas Nick, Tim Ruffing, Yannick Seurin, and Pieter Wuille. ACM CCS 2020 ↩

4. Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions. François Garillot, Yashvanth Kondi, Payman Mohassel, and Valeria Nikolaenko CRYPTO 2021 ↩

5. Two-Round Stateless Deterministic Two-Party Schnorr Signatures From Pseudorandom Correlation Functions. Yashvanth Kondi, Claudio Orlandi, Lawrence Roy. Preprint ↩

Post-Quantum

Author: Tim Ruffing - Blockstream ( crypto@timruffing.de )

Advanced post-quantum signatures

Signatures in Bitcoin have, already for a long time, supported advanced key derivation, e.g. BIP32 wallets with hierarchical derivation.

The Taproot softfork with support for Schnorr signature verification made it significantly easier to use further advanced signing functionality, e.g., Taproot itself, compatible Schnorr multi-signatures (using MuSig2), compatible Schnorr threshold signatures (using FROST), and adaptor signatures. (“Compatibility” here means that the resulting signatures can be verified like ordinary single-signer signatures and thus are understood by the Bitcoin network.)

This raises the question if the same or similar functionality is possible in a post-quantum world. That is, is it possible to construct a post-quantum signature scheme that supports (as many as possible) the following features?

• public hierarchical derivation
• Taproot (i.e., public keys can be commitments to additional data) - natural constructions of compatible multi-signatures
• natural constructions of compatible threshold signatures
• adaptor signatures

While there has been research achieving some of these features individually (hierarchical derivation¹², multi-signatures³⁴, threshold signatures⁵), the big picture remains unexplored.

1. Deterministic Wallets in a Quantum World. Nabil Alkeilani Alkadri, Poulami Das, Andreas Erwig, Sebastian Faust, Juliane Krämer, Siavash Riahi, Patrick Struck. ACM CCS 2020 ↩

2. Post-Quantum Secure Deterministic Wallet: Stateless, Hot/Cold Setting, and More Secure. Mingxing Hu. Preprint ↩

3. Two-round n-out-of-n and Multi-Signatures and Trapdoor Commitment from Lattices. Ivan Damgård, Claudio Orlandi, Akira Takahashi, and Mehdi Tibouchi. JoC 2022 ↩

4. DualMS: Efficient Lattice-Based Two-Round Multi-Signature with Trapdoor-Free Simulation. Yanbo Chen. CRYPTO 2023 ↩

5. Sharing the LUOV: Threshold Post-Quantum Signatures. Daniele Cozzo and Nigel P. Smart. IMA CC 2019 ↩

Integrating MuSig2 with FROST Signatures to Enhance Lightning Network Security

Author: Jesse Posner - Block ( jesse.posner@gmail.com )

Scope

One of the best methods of keeping bitcoin secure is to utilize multi-signatures scripts that require the signatures of multiple keys to unlock the coins. However, while the Lightning Network protocol utilizes 2-of-2 multi-signatures to require the signatures of both Lightning counterparties, it does not permit the use of multi-signatures to secure the keys for a single counterparty, making it difficult to secure these secrets.

With the advent of Taproot Lightning channels, we can now utilize Schnorr signatures and multi-party computation to distribute these secrets. However, there are a number of unsolved problems that must be addressed to make this possible.

Bringing distributed security to Lightning would revolutionize Lightning key management and significantly improve the security of Lightning wallets.

Problem definition

Taproot Lightning channels utilize MuSig2, a Schnorr multi-signature protocol, to build an aggregate key from 2 component keys, 1 for each counterparty. This aggregate key requires the signatures of both component keys to produce a valid signature for the aggregate key. Instead of relying on a script for the multi-signature, Taproot allows for Schnorr multi-signatures that can be used in the “key-spend path.”

For each counterparty to distribute the security of their component keys, a counterparty can generate their component key with FROST, another Schnorr multi-signature protocol. Whereas MuSig2 is limited to an n-of-n construction (e.g. 2-of-2), FROST generates aggregate keys that require t-of-n signatures. For example, Alice and Bob are counterparties in a Lightning channel. They have a MuSig2 aggregate key that secures the channel which consists of Alice’s component key and Bob’s component key. If Alice generates her component key using FROST,then t-of-n signatures are required for her to sign with her component key, thus providing for distributed security.

However, this requires nesting a FROST key as a component key within MuSig2, and we don’t yet have a security proof for this scheme. This is the first unsolved problem.

In addition, with Taproot Lightning channels, nonces are committed in advance of producing signatures. However, when using FROST, each subset of signers produces a different nonce, which is a problem because that would mean only the subset of signers that produces the nonce could sign for the state update in the channel. This is particularly problematic for offline signer:



State of the art

A potential solution to the delay signing issue with respect to nonce commitments is to use the pre-FROST threshold Schnorr scheme from Stinson & Strobl for nonce generation. In that scheme, rather than using additive secret sharing for the nonces, we use polynomial secret sharing so that any subset of signers is able to sign for the nonce that is committed to in the channel.

A detailed description of the open problems and potential solutions can be found here. There’s also a matrix channel where these problems and solutions have been discussed further, and where cryptographers and Lightning developers are available to discuss and answer questions.

Lightning Gossip using ZKPs

Author: Sanket Kanjalkar - Block ( sanket1729@gmail.com )

Scope

The primary objective of this project is to enhance the privacy of Lightning Network’s gossip protocol through the incorporation of zero-knowledge proofs (ZKPs). The proposed solution will encompass several key components, including a well-defined problem statement, the application of ZKPs, an analysis of the chosen ZK system, and an evaluation of the performance overhead associated with the integration of privacy solutions. Optionally, this may involve the practical implementation of the proposed solution within an existing Lightning Network implementation.

Problem definition

The current routing of payments in the Lightning Network relies on complete knowledge of the network’s graph structure. Nodes, when creating new channels, broadcast messages in the form of “channel announcements.” These announcements serve a dual purpose: first, they signify the creation of a new edge within the Lightning graph, and second, they serve as a preventive measure against potential denial-of-service (DoS) attacks launched by nodes announcing spurious channel connections.

Presently, Lightning Network nodes include an additional signature (called “stake certificates”) that attests to their ownership of the UTXO that funded the channel. Unfortunately, this also exposes the transaction ID linking the Lightning channel to the Bitcoin blockchain transaction ledger. Even though newer taproot channels make UTXOs indistinguishable from other spend outputs, they still divulge the funding transaction as part of the channel announcement.

To address this, a solution is sought that enables network participants to prove that a channel opening UTXO is derived from a Taproot UTXO within the last N blocks. The Taproot upgrade is instrumental here, as it ensures that all taproot transaction outputs are represented as elliptic curve points, making them more amenable to ZK proofs.

The ideal ZK proof system for this context should introduce minimal operational overhead to existing Lightning Network processes. This implies that proof sizes should be compact, as the data is disseminated across the network. Verification speed is a consideration but not a primary bottleneck, as channel announcements can tolerate some delay. Pairing assumptions can be made use of for further efficiency gains. Optionally, if these proofs can be aggregated at the gossip layer it further improves efficiency.

State of the art

Most state-of-the-art work in the context of the Lightning Network predominantly focuses on privacy vulnerabilities. While this is essential, it doesn’t address the specific privacy concerns associated with channel announcement in the Lightning Network.

A lot of work has been investigated into the improvement of ZCash UTXO double spend protocol with Sapling, Orchard. Existing work has been put in set membership protocols that can be actively leveraged to obtain maximal efficiency.

The classic solution to this problem are linkable ring signatures of which the most modern instantiation is Triptych with O(log(N)) size and O(N) linear verification. See also waxwing’s post on this.

A different implementation may place the public keys into some sort of accumulator. The goal of this is that verification time is in O(log(N)) instead of O(N) as in linkable ring signatures. According to the curve tree paper, set inclusion proofs are size O(log(n)) and have verifier time O(D-th root of n) where D is the number of levels in the tree.

Challenges

The challenges presented by this project are analogous to those encountered in the prevention of double-spending, as observed in ZCash. However, the problem at hand presents unique challenges and opportunities:

• ZKPs: The first challenge revolves around the need to ensure that zero-knowledge proofs are employed only once per UTXO. If implemented without careful consideration, this may lead to the same UTXO being claimed by multiple channel openings, potentially triggering a Denial of Service (DoS) attack. To mitigate this, the introduction of a nullifier concept, akin to those used in Zcash, is required. However, traditional Zcash-style nullifiers present challenges due to the ever-growing list of nullifiers that need to be tracked. Given the relatively small set of outputs that require proof in this context, alternative techniques offering enhanced privacy should be explored
• Multi-Party Computation (MPC): The second challenge pertains to the necessity of implementing Multi-Party Computation (MPC) to generate the proof. Unlike traditional zero-knowledge settings, the prover in this scenario is shared between the two parties opening the channel. Neither party is willing to divulge their secrets to the other, necessitating the use of MPC to generate the proof while preserving privacy. This introduces complexity to the implementation and necessitates a thorough assessment of security implications. Exploring options to simplify or represent the ZK protocol/circuit in an MPC-friendly manner is essential

Channel Addresses

Author: Lloyd Fournier - Independent ( lloyd.fourn@gmail.com )

Scope

Why can’t you just send money to a Bitcoin address and have it create a payment channel? There is no reason why this couldn’t be possible in theory – the address just needs to be a 2-of-2 multisig and have some way for the owner of the address to get the initial coins back.

Channel establishment is one of the core interactive protocols involved in scaling Bitcoin. If we can turn it into an non-interactive protocol we have dramatically simplified Bitcoin’s future. Furthermore, if we can make it as simple as sending to an address we’ve created frictionlessly interoperable with every other Bitcoin protocol.

Other than simplification consider the following concrete implications:

• A user can withdraw directly from an exchange into a lightning channel
• Funding a lightning channel with an LSP by sending to an address would be non-custodial and happen in one transaction (currently you must trust them to credit you with a channel in another transaction)
• Lighting channels can be trivially established through coin-joins and other batch transaction systems

Problem definition

Channel addresses must meet the following requirements:

• They can be created without interacting with a channel counterparty. Knowing the public keys of both channel parties should be sufficient to derive (multiple) addresses
• The channel should be established regardless of how much money is sent to the address
• The distribution of the funds in the channel should be committed to in the channel. It is sufficient to achieve it with distribution of 100% on one side but being able to have other distributions is a bonus
• The funds need to be recoverable by one of the channel parties regardless of what amount is sent to the address and without assuming the other channel party is online
• If the channel uses revocation punishment then the mechanism in (4) obviously needs to be revocable

State of the art

1. The Swap-in-Potentiam is similar to channel addresses except it requires two on-chain transactions to finally establish the channel, however you can start using the channel after the first transaction is confirmed on-chain
2. Non-interactive channel establishment is possible with OP_CTV. Although it’s non-interactive the script pubkey commits to the value of the channel so it is not viable as an address (since if the wrong amount was sent it would be stuck)
3. It’s possible that OP_TXHASH would enable channel addresses

Generating optimal Blinded Paths in the Lightning Network

Author: Bastien Teinturier - ACINQ ( bastien@acinq.fr )

Scope

Source-routed payments in the lightning network require recipients to provide a destination for pathfinding. Blinded paths have recently been introduced to the specification to improve recipient privacy by providing the sender with an encrypted multi-hop path from a known, cleartext introduction node to themselves. This is similar to Tor’s rendez-vous onion routing protocol, but uses a different cryptographic protocol.

Problem definition

Blinded paths need to provide aggregate information about the fee and time lock required for the encrypted portion of the path so that senders can send payments that meet the routing policies of the nodes in the nodes in the blinded path. This information can be compared to the publicly known lightning graph to attempt to de-anonymize blinded paths.

Open questions for blinded path selection are:

• The length of a blinded route and its introduction point can be used to “triangulate” the recipient. How many distinct introduction nodes are safe for a node to use?
• How to manage the trade-off between reliability and privacy, as blinded paths limit the last-mile options for payments
• Blinded path creators can inflate the fees and expiry for the blinded section, and include dummy hops to prevent the aggregate values from being correlated with the public graph. What are best practices for this?

It is not trivial to compute a reliable score for each of the two trade-offs above. But it is important to figure out a way to do so, and a graph algorithm that selects good blinded paths based on that scoring.

State of the art

Close to none. While blinded payments are supported in most lightning implementations today (October 2023), all of them defer the selection of the blinded paths to the end user.