Much has been written on the Post-Quantum Problem (PQP). We won’t rehash it all. We encourage readers to review these writings if they are unfamiliar with the capabilities of a Cryptographically Relevant Quantum Computer (CRQC) and what risks such a device poses to the Bitcoin network. In short, a CRQC can break the fundamental assumptions on which Bitcoin’s key-security is based: with knowledge of only a public key, the corresponding private/secret key can be recovered.
Regardless of the speed at which a CRQC will be developed, we believe that the PQP deserves dedicated and deep research. Failure to prepare would leave the ecosystem exposed to network actors attempting to push incomplete or under-studied primitives into Bitcoin’s consensus engine when a CRQC emerges.
To that end, Localhost Research is excited to announce a new initiative. This initiative is in partnership with two world-class cryptographers: Benedikt Bünz and Dan Boneh. Together, we have established a Post Quantum Cryptography Group that will review, study, and design conservative cryptographic schemes that will help inform the direction and shape of Bitcoin’s response to the PQP.
In this post, we provide some context on how we think about this problem, what research areas we have identified as within scope of this initiative, and ultimately how we intend to allocate our resources.
The PQP space is expansive. Across the world, there are workflows, systems, protocols, and operational standards that need to be upgraded in anticipation of a CRQC. Fortunately, there is a global effort to study, design, and review cryptographic primitives that can address this growing threat.
Such primitives need to be selected based on the given use case. Bitcoin presents a particularly constrained and conservative environment. As a synchronous decentralized consensus protocol with highly replicated data, Bitcoin is extremely sensitive to signature/proof size, verification times, and ultimately, the underlying mathematical and game theoretic assumptions on which an adopted scheme is built. This makes the majority of results from the broader post-quantum cryptography effort inapplicable to Bitcoin.
Two primary research categories have been identified by the Bitcoin ecosystem:
- Reactive proposals are measures the network might adopt in response to a sudden, unexpected CRQC deployment. They are intended as temporary mechanisms that let users safely transition to a post-quantum signature scheme (PQSS).
- Proactive proposals, by contrast, introduce lasting new PQSSs and related primitives that willing users can migrate to before a CRQC is deployed.
Each of these categories require significant levels of research and development to be suitable for consensus building. As proposals from either category address a new challenge under Bitcoin’s unique constraints, we expect that a large number of proposals will need to be explored and vetted to produce a viable solution.
Both categories also have long deployment tails. Even after foundational proposals are specified, drawn up as BIPs and achieve rough consensus, wallets, businesses and end-users will have to implement and adopt these new standards and features across the ecosystem. There is a long road ahead.
As a non-profit organization that seeks to build teams around fundamental and critical issues within the Bitcoin ecosystem, we seek out problems that are well suited for our shape and are currently underfunded.
To that end, we believe that a subset of proactive cryptographic research problems are within scope of our new initiative. We also hope to contribute to the process of standardizing and developing reference implementations of post-quantum schemes as they achieve rough consensus.
Within this category, there is a broad spectrum of post-quantum primitives, each making different tradeoffs between conservatism, functionality, efficiency, and implementation risk. At the most conservative end are hash-based signature schemes which rely on assumptions about hash functions rather than newer algebraic hardness assumptions. They are often cumbersome in practice, with large signatures, limited signing models, or state-management constraints, but they offer an important baseline precisely because they introduce so little cryptographic novelty.
Moving along the spectrum are lattice-based signature schemes, which are significantly more flexible and promising from a systems-design perspective, and will eventually support features that are much closer to what Bitcoin users have come to expect from modern signing systems. At the same time, the signatures are quite large and depend on newer cryptographic assumptions and have not yet enjoyed the same operational history as ECDSA, Schnorr, or the hash functions already deeply embedded in Bitcoin.
Further out still are more exotic families, including isogeny-based constructions and other advanced approaches, which are attractive in theory because they may offer compactness or richer functionality, but which remain far less mature and, in some cases, have experienced major cryptanalytic setbacks. For Bitcoin, this suggests a roadmap that begins with the most conservative post-quantum signature tools, while still investing in research on more expressive schemes that could eventually recover important functionality without compromising long-term security.
Given this landscape, our initial research objective is to perform a formal review of the design, security assumptions, concrete parameterization, and Bitcoin-specific tradeoffs of the SHRINCS/SHRIMPS proposals, including signature size, verification cost, key-management constraints, and suitability for consensus-critical deployment.
Building on that foundation, we are investigating threshold constructions for hash-based signatures that preserve verification compatibility at the consensus layer, ideally yielding a single signature artifact verifiable by the same logic as the corresponding non-threshold scheme. We are designing this threshold scheme such that it enables the threshold t to remain secret. Beyond these properties, we are specifically interested in threshold signing protocols that shift coordination complexity off-chain while minimizing or eliminating additional on-chain verification complexity.
Over the longer term, we view this line of research not merely as a way to make hash-based signatures more usable, but as a path toward recovering functionality that conservative post-quantum schemes do not natively provide. In particular, Bitcoin today benefits from structural properties of elliptic curve systems that support things like watch-only wallets, adaptor signatures, and related constructions for multiparty coordination and conditional payments. Hash-based signatures are attractive precisely because they are conservative, but they do not naturally reproduce much of this functionality. We believe not all of it is lost, and are excited to explore mechanisms by which powerful thresholdization and watch only-wallet functionality can be restored in creative ways.
More broadly, this research is not only an exercise in making hash-based schemes deployable; it is also a way to motivate longer-term work on more expressivity. Not only will we research ways to extend the functionality of hash-based signatures to support features we have all become accustomed to, this initial research will serve as a bridge towards constructions that depend on cryptographic primitives that extend beyond that hash-based paradigm. While it’s unlikely Bitcoin will consider non-hash-based primitives in the immediacy, it’s important that they are investigated within the context of Bitcoin’s limitations and usability requirements. We believe the future is bright, and with enough time, research, and battle-hardening, lattice and SNARK-based cryptosystems may one day be adopted by the Bitcoin community.
As a group, we are excited to work together on this initiative. We look forward to sharing our work and participating in constructive dialogues around the PQP.