About SPHINCS+

09-26

This article is machine translated

Show original

Author: NIFTY
Source: https://insider.btcpp.dev/p/sphincs

Presido Bitcoin, a Bitcoin-only coworking space in San Francisco, hosted an industry conference last week on Bitcoin and quantum computing. @roasbeef , lead maintainer of btcd and lnd clients and CTO of Lightning Labs , presented a proposal for adding a quantum-safe signature scheme, SPHINCS+, to Bitcoin. In today's report, Insider's protocol expert @niftynei explains the proposal.

Quantum security issues

Most funds on the Bitcoin blockchain are protected by private keys. In order for your Bitcoin transaction (fund transfer) to be confirmed on the blockchain, you need to prove your authority to spend those funds by providing a signature. A valid signature can only be generated by someone with access to the correct private key.

In a sense, Bitcoin also achieves "security through obfuscation." The "obfuscation" here refers to the difficulty of guessing your private key. The number of possible numbers that could be a private key is astronomical. Guessing a single private key would require so much time and energy that it is beyond the reach of any human within a reasonable timeframe (e.g., hundreds of years).

However, current Bitcoin keys rely on mathematical equations based on elliptic curves. Elliptic curves are a good choice for creating public and private keys because they are generally more secure than prime number factorization (another "mathematical system" that serves as the basis for public and private key cryptography), and the public and private keys are also smaller.

However, elliptic curve cryptography also has a problem. The Shor algorithm, invented by Peter Shor in 1994, is based on Fourier transforms and means that a quantum computer with enough quantum bits (qubits) can quickly calculate the private key of any public key.

Shor's algorithm means we know how to break elliptic curve cryptography, but the tools to do so don't yet exist. Whether and when such tools will appear is a hotly debated topic, not only within the Bitcoin community but also within the broader cryptography community. The security of every private key used to store Bitcoin depends on the fact that no one will ever have access to a tool capable of executing Shor's algorithm for the indefinite future.

The general consensus is that at some point in the future, Bitcoin will need to migrate to a post -quantum public-private key cryptography system. @roasbeef's proposal at the Presidio last week was based on the "SPHINCS+" hash signature scheme. Let's take a quick look at how it works and why it might be a good choice for securing Bitcoin.

Quantum secure, but data heavy

SPHINCS+ is a hash-based signature construction. At its core, it relies on cryptographic hash functions (rather than elegant elliptic curve equations or secret prime factorization) to construct public keys and verify signatures. Hash-based cryptographic schemes are immune to Shor's algorithm because they don't use functional mathematical systems behind their one-way functions. Instead, hash functions rely on brute-force preimage stacking. Brute-force methods don't contain mathematical relationships (or shortcuts) that are vulnerable to quantum Fourier transforms, making them vulnerable to Shor's algorithm.

Stacking data, or hashing functions, has a drawback: its public keys and signatures require significantly more data to share. Satoshi Nakamoto chose elliptic curves for Bitcoin precisely because elliptic curve-based cryptography requires less data to share when verifying a signature and locking funds to a public key. I like to say that Bitcoin is the killer app for elliptic curve cryptography; before Satoshi Nakamoto implemented secp256k1 (a specific elliptic curve) in the Bitcoin protocol, most cryptographic systems used RSA (or prime factorization) as the underlying mathematical system. According to the SEC 2 parameter paper, to achieve 128-bit signature security, RSA public keys need to be 3072 bits long, while elliptic curve public keys only require 256 bits.

Small size is crucial for blockchain systems, as any data added to the blockchain must be sent to and stored by every peer in the network. Compact signature and public key sizes mean that more transactions can be packed into the same data space. This reduction in size is arguably the reason Satoshi Nakamoto chose elliptic curve cryptography over RSA for Bitcoin.

By comparison, both public keys and signatures in post-quantum cryptographic systems are incredibly large. Public keys in the SPHINCS+ system are the same size as those in Bitcoin's current key system, but signatures are several thousand bytes long. Schnorr signatures in Segregated Witness v1 (also known as Taproot) are 64 bytes long; benchmark SPHINCS+ signatures are 3 to 7 kilobytes.

- From the NIST SPHINCS+ Parameters Paper -

SPHINCS+

SPHINCS+ is a complex signature scheme developed using multiple layers of post-quantum signature "gadgets"; when combined, they create a quantum-safe public/private key pair that can securely sign many messages. Unlike its predecessor, "eXtended Merkle Signature Schemes (XMSS)" (also a hash-based post-quantum signature scheme), SPHINCS+ eliminates the need to remember signatures created for a key pair.

A SPHINCS+ "structure" can produce a public key that can sign multiple messages without revealing the private key.

A SPHINCS+ "structure" consists of three parts:

FORS stands for "Forest of Random Subsets." This is the underlying layer of the SPHINCS+ "structure," where messages are used to determine which preimages to reveal. The set of revealed preimages becomes the basis for the SPHINCS+ signature. In SPHINCS+, messages are actually "signed" using FORS. The next section will involve tying the FORS signature to the root public key of the SPHINCS+ "superstructure" (as I've chosen to call it).
WOTS+, or "Winternitz One-Time Signature Plus," is a post-quantum, hash-based signature algorithm that can securely sign a message. SPHINCS+ uses WOTS+ signatures to bind the preimage revealed in FORS to a hierarchical XMSS Merkle tree. The root of this hierarchical Merkle tree is the SPHINCS+ public key. (The only difference between WOTS and WOTS+ is that the "+" variant includes a random prefix in each hash operation, mitigating multi-target hash attacks. The "+" in "SPHINCS+" also means that each hash operation includes a randomly generated prefix.)
XMSS Merkle Tree. Each leaf of an XMSS Merkle Tree is a WOTS+ public key. SPHINCS+ uses layers of XMSS Merkle Trees to create a massive pyramid structure. Trees upon trees are often called "hypertrees." Each leaf of a parent tree is a WOTS+ public key, which signs the root of the tree below it, thus binding the trees together (forming a structure). The number of trees, and therefore the number of layers, can be varied, depending on the desired signature size for a SPHINCS+ "hyperstructure." The smaller the desired signature size, the more hashes are required to verify and generate the signature. Each leaf at the lowest level of all trees is a FORS. Many Merkle trees and many layers mean that there are many FORS at the base of the pyramid, which can be used to create secure signatures with a very low probability of reuse.
(Translator's note: The reason a SPHINCS+ structure is called a "pyramid" rather than "a whole tree" is because it is indeed not like a single Merkle tree, which starts from the leaves and merges layer by layer to form a root (so that a root commits to all the leaves at the bottom level); instead, each leaf of an XMSS Merkle tree in the top layer is a WOTS+ public key, and each WOTS+ public key signs the root of an XMSS Merkle tree in the second layer. These second-level XMSS Merkle trees are constructed in the same way: each leaf is a WOTS+ public key; and so on; therefore, the number of XMSS Merkle trees in the next layer is always a multiple of the number in the previous layer, that is, a pyramid. The bottom layer is not an XMSS Merkle tree, but a FORS Merkle tree (forest) - a FORS public key corresponds to many Merkle trees, which can be used to make signatures.)

- An oversimplified version of a supertree graph. The PK in the diagram above is actually a FORS signature in the context of SPHINCS+. The "root" is the SPHINCS+ public key. -

The basic process for generating a SPHINCS+ public key is to generate a WOTS+ public key at the root of a tree, then compute the Merkle root of these trees. The root of the topmost tree is the SPHINCS+ public key. The size of the Merkle tree root is determined by the hash function used to compute it. Typically, the SHA256 hash function is used, which has a 256-bit output. This means that the root of such a Merkle tree will be 32 bytes. This is how the SPHINCS+ public key comes about.

Generating a SPHINCS+ signature requires using a hash of the message to randomly select a FORS subtree to join to the SPHINCS+ supertree and generate the FORS signature. Once the FORS signature is generated, it's signed with the private key of a WOTS+ public key in the XMSS tree above it; this signature is then combined with the Merkle path (of the public key) up through the tree until it reaches the topmost SPHINCS+ public key. The combination of all the WOTS+ signatures, the FORS signatures, and the Merkle path leading from the FORS signature to the SPHINCS+ public key constitutes the signature of the message. As you can imagine, this is a lot of data, which is why SPHINCS+ signatures are orders of magnitude larger than elliptic curve signatures (64 bytes).

- Schematic diagram of the data contained in a SPHINCS+ signature; the "sign" on the right generates a FORS signature; while the "sign" in the middle generates a WOTS+ signature. -

Why use SPHINCS+?

SPHINCS+ is fully hierarchical, quite unwieldy, and relies on several different "tools" to generate signatures: Witnernitz signatures, FORS, and the XMSS subtree.

SPHINCS+'s complexity stems from its powerful feature set. It is a rigorous optimization of XMSS, also a post-quantum signature scheme that allows a single public key to sign multiple messages, but requires tracking which Merkle tree leaves have been used to sign. SPHINCS+ uses randomness generated from the digest of the signed message to deterministically select a subtree leaf within the supertree.

In Bitcoin, ideally, you should rotate a public key for every transaction, which means you generate a new SPHINCS+ superstructure for every public key used in Bitcoin.

At first, I was confused as to why such a strong multi-signature capability would be provided on a (ideally) one-time public key.

Jonas Nick from Blockstream Research pointed out that you would sign again when you want to add additional fees or the transaction is lost for some reason; Laolu (also known as roasbeef) pointed out that off-chain protocols such as the Lightning Network require multiple signatures (of the same public key) to track state transitions within private contracts.

In Bitcoin, you likely don't need unlimited re-signing functionality, allowing us to construct a smaller SPHINCS+ superstructure to generate public keys. A smaller superstructure means smaller signatures because fewer Merkle tree paths need to be carried. However, this also means that the number of signatures you can create before security begins to degrade is reduced. In elliptic curve cryptography, reuse of signature nonce immediately leaks the private key; in SPHINCS+, overuse of the public key (for signing) only gradually degrades security starting at 128 bits (as the lower-level FORS begins to reuse some of the key).

After digging deeper, I have to say I'm a real fan of roasbeef's proposal to use SPHINCS+ as a post-quantum signature scheme. There's still a lot of design work to be done to determine the exact parameters. I'm looking forward to a draft BIP (which he indicates is already in progress) that could help fill in some of the gaps surrounding the relationship between the number of layers in the superstructure and the number of secure re-signing attempts.

It's also worth pointing out that, as mentioned in roasbeef's talk, SPHINCS+ doesn't allow for seed/subkey derivation paths. This means BIP32 hierarchical wallets are dead. There are alternatives, but we'll lose the ability to use a hierarchical derivation path to describe the public keys that make up a wallet (as currently used by the industry with xpubs and subwallets).

Which way to go?

Bitcoin will migrate to a post-quantum signature scheme. When, which scheme to use, and with what parameters will be hot topics in the next few years.

Roasbeef's SPHINCS+ proposal is an attractive option, despite the complexity of the multi-layered tree superstructure. In my opinion, all post-quantum public key schemes based on hash functions are hideous. SPHINCS+ is also ugly, but that's because it offers the most features, especially statelessness when signing repeatedly.

As I better understood the role each part played in the protocol, I began to strongly appreciate the cleverness that went into designing this multi-layered structure.

Roasbeef still has much work to do on the BIP, particularly regarding the depth of each tree and the number of subtree levels, the size of Winternitz signatures, and the parameters for FORS. There's a dilemma between the size of the signature and the number of hashes required to generate it. Finding the right balance between computational effort and on-chain traceability is crucial before a formal BIP can be released.

So there is one last question left:

Does the move to SPHINCS+ mean that Bitcoin has become a pyramid-scheme? It’s hard to define, but it certainly seems to be the case.

(Translator's note: This is a pun, because "pyramid-scheme" can mean both "pyramid scheme" and the "pyramid structure" of SPHINCS+.)

Acknowledgements

Thanks to Jonas Nick and Olaoluwa Osuntokun for their help in explaining SPHINCS+ public key reuse and parameter tuning.