SHRINCS: an efficient hash-based signature scheme for Bitcoin (first draft)

[conduition]

Hi everyone, it's me again.

On behalf of the SHRINCS Working Group, I am excited to announce a first draft of a cryptographic BIP that fully specifies SHRINCS: A semi-stateful hash-based signature scheme for Bitcoin.

https://github.com/SHRINCS/shrincs-bip/blob/main/SHRINCS.md

Disclaimer: Do NOT use in production. SHRINCS is prototype cryptography, still in need of peer review. Formal security proofs are WIP.

Features

SHRINCS offers:

• Compactness. SHRINCS public keys are 48 bytes. Stateful signatures are 548 bytes at the smallest, with a stateless fallback component built into every key pair by default that produces larger 5777-byte signatures.
• NIST-I security (~128-bit classical and ~64-bit post-quantum). SHRINCS' security depends only on properties of the (truncated) SHA256 hash function which are believed to be post-quantum-secure.
• Fast verification performance. Amortized on a per-byte basis, SHRINCS signatures are 4x-16x faster to verify than BIP340 Schnorr depending on whether SHA256 hardware acceleration is available. At worst, verification costs 2792 SHA256 compressions with a 5777 byte stateless signature.
• Flexibility. SHRINCS allows signers to control the shape and size of their stateful keypair to best suit their use-case, while SHRINCS' stateful verifier is agnostic to signer-side choices and contains only a single code path to be scrutinized and optimized.
• Good incentives. SHRINCS with UXMSS provides the most compact signatures possible within the scheme, and the signatures grow as a key is reused. If SHRINCS comes into common use, users will be economically incentivized not to reuse addresses. Address reuse would still be possible, either via stateful BXMSS keys, or via the stateless component.

Drawbacks

SHRINCS has drawbacks:

• The efficient stateful component requires software that can manage an incrementing state counter (essentially the number of signatures issued) for each keypair. If wallet software accidentally reuses the same state counter on two distinct signatures under a key, any adversary who observed both signatures can forge a new one.
• The key generation and signing algorithms are computationally expensive - Though this can be mitigated using SIMD, parallism, or hardware acceleration techniques.
• SHRINCS lacks any algebraic structure allowing for public key rerandomization (to admit BIP32-style xpubs), multisignature schemes (like MuSig), etc, in contrast to feature-rich cryptosystems like Schnorr.

Changes

This new specification is the evolution and formalization of ideas originally put forward by Jonas Nick and Mikhail Kudinov in this Delving thread and in their joint paper referenced therein. Also see this related mailing list thread.

Notable changes since the original proposals 8+ months ago include:

• Black-box compatibility with SLH-DSA (FIPS-205) algorithms. This encourages interoperability with non-Bitcoin systems, and leans into established security proofs.
  
• Flexible XMSS (FXMSS). Prior descriptions of SHRINCS implied only unbalanced stateful trees were allowed. We now allow stateful trees of any structure.
• New parameter sets. The stateless component now uses a parameter set allowing at most 2^40 stateless signatures, rather than 2^20. This allows SHRINCS to be useful for protocols that require high-frequency signing, such as Lightning. The stateful component now uses parameters which offer much faster performance (at the cost of larger signatures) compared to the original proposal.

Status

This initial draft specification contains only the cryptography of the SHRINCS scheme, decoupled from consensus validation rules. Further BIPs would be required to deploy the SHRINCS signature scheme on Bitcoin. Notably, we cannot safely deploy SHRINCS without introducing at least one new output type, which we do not define in this BIP.

The draft BIP-SHRINCS is not ready to be submitted to the BIPs repository yet. We still have much work to do. Notably absent from this draft are:

• Test vectors
• Unit tests

• A security proof

• An optimized implementation
• Mediawiki or Markdown format compliance

We are posting here to seek review of SHRINCS' design, parameters, cryptography, and reference code, primarily for security, correctness, compatibility, consistency, and clarity, in that order. Insightful reviews will be highly appreciated and met with positive vibes and beers at the next conference :)

We also hope that seeing a concrete specification will spur further discussion of related problems, such as how PQ HD wallets will work, and how to handle user experience of a semi-stateful signing scheme.

We note that SHRINCS' parameters offer a complex multi-dimensional trade-off space between performance and signature size. The choice of parameter set therefore seems ripe for bikeshedding. We provide a forum for parameter set discussion here, but we encourage prospective cyclists to first read the relevant sections of the design rationale, and invite readers to also play with our interactive stateless and stateful parameter set exploration tools.

Those who prefer video format may be interested in this interview discussing the internals of SHRINCS: https://youtu.be/n-jGPICZMR0?si=NpfyTRB88-sUxtlh

Related Work

We are building libshrincs, an attempt at a formally verified C implementation. One machine-checked Rocq theorem covers WOTS+C, the one-time signature in FXMSS: honest signatures verify, the linked C implements its four public contracts under CompCert's semantics (VST), and forging costs breaking truncated SHA256 (SSProve). Still a prototype, more detail on Delving.

Acknowledgements

The SHRINCS specification is the result of several months' collaboration between contributors across multiple organizations. The SHRINCS Working Group is, in alphabetical order:

- Mike Casey (OpenChain)
- Conduition (Brink)
- Ethan Heilman (Cloudflare)
- Mikhail Kudinov (Blockstream)
- Oleksandr Kurbatov (Blockstream)
- Boris Nagaev (Independent)
- Jonas Nick (Blockstream)
- remix7531 (OpenSats)


regards,
conduition