Hash-Based Signature Schemes for Post-Quantum Bitcoin

In my personal opinion, the most dangerous and unpredictable challenge facing Bitcoin is not political pressure, practical usability, scaling, or economic incentive… It is the threat of quantum computers.

Large and powerful organizations - both political and corporate - have been pouring billions of dollars into developing quantum computers for decades. Ever since Peter Shor published his (in)famous namesake algorithm in 1994, cryptographers have been preparing for “Q-Day” - the day a large, practically usable quantum computer becomes available.

If you’re reading my blog, I can assume you are at least roughly familiar with elliptic curve public/private keys. I’ll simply tell you that a quantum computer of sufficient power would be able to flip an EC public key backwards into its private key - a feat thought to be implausible with ordinary classical computers. You can see how this might be a problem. If you’d like to learn how this can be done in detail, check out Shor’s original paper.

This article won’t dissect the mechanics of how quantum computers break Bitcoin public keys, nor is it intended as a doom-and-gloom FUD-piece about how we should all be digging graves, stocking bunkers, and prepping for day zero of the post-quantum meltdown. I won’t bother to conjecture how long it will take for a powerful quantum computer to be invented - Estimates of when this will occur vary widely even between professional analysts. I will simply assume it will happen, one day, eventually. When it does, we must deal with it.

My hope is that this article will show you the landscape of the quantum threats facing the Bitcoin community. Then I’ll explore various hash-based signature schemes and analyze their potential to diffuse these threats, and the tradeoffs which inevitably come with them. Finally, I’ll propose a novel upgrade path for Bitcoin clients which uses hash-based cryptography as a fallback option to insure bitcoin users against future quantum adversaries, without the need for any near-term consensus changes.

_{All safe roads once were wild.}

The Quantum Threat

In this section I’ll dive into the mechanics of how exactly a selfish quantum adversary could attack Bitcoin for financial gain. Understanding the fundamental threat of quantum computers in more detail will lead us to clues as to how we can improve our defenses.

Almost every Bitcoin transaction mined from the genesis block to today has authenticated itself using one or more asymmetric signatures. Sometimes public keys are hashed. Sometimes we use Bitcoin script opcodes to encumber coins with additional validation steps (e.g. time delays). But eventually, to spend a Bitcoin UTXO safely, one must be required to supply an asymmetric signature matching some public key committed to by the UTXO itself. The signature must commit to the spending transaction in some way so that it can’t be applied to a different transaction.

If one were to encumber a transaction output with only a hashlock, or only a timelock, etc, with no asymmetric signature requirement, then that UTXO can be spent by anyone who observes it being spent (including the miners who must see the transaction to validate it).

OP_SHA256 <hash> OP_EQUAL

_{A simple hash-lock Bitcoin script pubkey. This script is unspendable until someone reveals the preimage of <hash>. After that, the script could be easily unlocked by anyone.}

Bitcoin transactions use signatures on the secp256k1 elliptic curve to achieve this asymmetric authentication dynamic. ECDSA is the older and more well-known signing algorithm, and Schnorr is a cleaner, faster, more secure and more flexible signing algorithm which was adopted several years ago as part of Bitcoin’s Taproot upgrade. Bitcoin’s Schnorr and ECDSA signing protocols both use the same secp256k1 elliptic curve.

ECDSA and Schnorr signing protocols are equally vulnerable to a quantum adversary (QA) who knows a victim’s secp256k1 public key, because the QA can simply invert the public key into the private key, and sign any message they desire.

However, the same QA will have a much harder time computing the preimage (i.e. input) of a hash function given its output. The currently-known best-case-scenario for a QA brute-forcing a hash preimage is a quadratic speed boost, given by Grover’s algorithm. Quadratic in this context means that if a classical computer requires operations to do something, then the QA can do it in operations. The smallest hash used in Bitcoin output scripts is RMD160 which has a security level of , so a quantum computer could crack a preimage to RMD160 in at most operations. Not great, but still implausibly difficult according to current theory.

So not all one-way functions are dead in the water, and cryptographic hashes aren’t the only ones still kicking.

Let’s examine the different address (output script) types in more detail.

Hashed Output Types

_{(AKA P2PKH/P2SH/P2WPKH/P2WSH)}

The most commonly used type of Bitcoin address today is a pay-to-(witness)-public-key-hash address (P2PKH/P2WPKH), in which the public key is first hashed before being given to the payer. When spending this output, the owner signs the transaction and provides the raw public key so that verifiers (Bitcoin nodes) may re-hash it and compare the hash against the output script being spent.

OP_DUP OP_HASH160 <hash> OP_EQUALVERIFY OP_CHECKSIG

_{The classic P2PKH locking-script.}

In P2SH and P2WSH, the address instead is the hash of a Bitcoin locking script which itself almost always contains at least one ECDSA pubkey, whose signature is required for spending. For the purposes of assessing post-quantum security, script-hash type outputs have effectively the same properties as key-hash type outputs, with the exception that P2WSH outputs are encoded as SHA256 hashes whereas all others are encoded as RMD160 hashes.

OP_HASH160 <hash> OP_EQUAL

_{The classic P2SH locking-script.}

These four types of addresses currently protect the bulk of the mined and circulating Bitcoin supply.

The threat of a quantum adversary (QA) is in its ability to invert public keys into private keys. If a key-hash or script-hash address has received but not spent any of its coins, then the preimage of that hash (the key or the script) hasn’t been revealed yet. Barring out-of-band exposure (e.g. via BIP32 xpubs leaked to servers or peers), the QA generally won’t be able to attack such addresses practically.

This protection ends the moment the owner of the key/script-hash address tries to spend any of their coins. To validate a transaction spending a pay-to-*-hash output, the Bitcoin network peers must be given the key/script preimage. A quantum adversary could easily monitor these transactions and see that preimage, which always contains a public key the QA can invert. After inverting, the QA can try to double-spend the coins with a new higher-fee transaction.

Gracefully, the QA will have a limited time in which to mount this attack. A typical Bitcoin TX spends only 5 to 60 minutes of its public existence in the mempool before it is mined, at which point the coins will have moved permanently to a new address. If that new address is protected by a hash whose preimage the QA does not know, then the coins will be out of reach for the QA.

However, a significant fraction of key-hash and script-hash addresses are being reused on mainnet today. A reused address is one which receives one or more UTXOs, spends them, and having revealed their public key or spending-script, is still being used to custody additional Bitcoin UTXOs. Some estimate the amount of bitcoin held on such reused addresses was at least 5 million BTC as recently as 2019. A quantum adversary has much more time to compute the public keys exposed by these addresses. Time is on the side of the QA here; The burden of action is squarely on the shoulders of the owner to move their coins to a fresh unused address.

There is also the possibility of a large mining pool becoming a quantum adversary. Such a pool could delay mining certain transactions intentionally, to give themselves more time to crack a newly discovered public key.

Summary

P2PKH/P2SH/P2WPKH/P2WSH output script types can be reasonably secure against a QA if used properly, provided the QA needs a decent amount of processing time (more than an hour) to invert a secp256k1 public key.

The problem is that proper usage is hard. Ava Chow describes the numerous pitfalls which plague key-hashing as a countermeasure against a quantum adversary.

P2TR Outputs

In P2TR addresses, an internal public key is tweaked with a given hash to produce an output public key (where is the secp256k1 generator point). The output pubkey is then encoded directly (unhashed) in the P2TR address which receivers distribute.

When spending, the bearer can either authenticate directly by signing as the output pubkey (“key-path” spend), or they can provide the internal public key , a Bitcoin locking script, unlocking witness stack, and a proof that the locking script was committed as a merkle tree leaf of . If the script evaluation succeeds, the spender is deemed authentic (“script-path” spend). See BIP341 for more information.

The critical distinction between P2TR and the legacy pay-to-*-hash output script types is that taproot encodes a secp256k1 point directly in the output script. This means a quantum adversary (QA) can invert any P2TR output pubkey to get its secret key, and claim the P2TR UTXO using a “key-path spend”, even if the address has not been spent from before.

This is not a new observation, there has been much discourse and controversy surrounding this property of the taproot upgrade.

• https://freicoin.substack.com/p/why-im-against-taproot
• https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-March/018641.html
• https://bitcoinops.org/en/newsletters/2021/03/24/#discussion-of-quantum-computer-attacks-on-taproot

Summary

Against a quantum adversary, P2TR addresses are comparable in security to an already-reused key-hash address. The QA has unlimited time to invert the output pubkey and can start attacking any P2TR output from the moment they learn of its output public key . The burden of action is on the address owner to move funds to a quantum-safe address - or to avoid using the P2TR output script type - as soon as they realize the QA exists (or could exist soon).

Note on Multisig

P2SH or P2WSH addresses which use OP_CHECKMULTISIG cause a linear increase in the processing time needed for a QA to fully compromise the address. For an -of- multisig address composed of distinct pubkeys, the QA must invert at least of the constituent public keys to wield spending power over the address.

This slowdown will probably be offset by parallel-processing across multiple quantum processors, or with parallelized quantum algorithms which invert multiple public keys at once.

P2TR multisig addresses which use key aggregation do not have this property, because the taproot output pubkey can always be inverted. Possessing the secret key of is always sufficient to spend the P2TR output under current consensus rules.

Note on BIP32

Most consumer wallets derive their addresses using BIP32 hierarchical-deterministic (HD) wallet schemes. This allows a single seed to derive basically unlimited secret keys and corresponding public addresses for any script type. Wallets will sometimes share their extended public keys to avoid the need to communicate many individual child addresses.

To a quantum adversary, a BIP32 extended public key (xpub) is equivalent to its counterpart extended private key (xpriv) given enough time to invert the xpub. Once inverted, the QA can quickly derive all child addresses, and can thereafter monitor the blockchain to steal any funds paid to them.

To comply with BIP44 standards, most wallets derive one xpub/xpriv pair at specific BIP32 paths for each Bitcoin address type.

• m/44'/0'/n' for P2PKH
• m/49'/0'/n' for P2SH-wrapped P2WPKH
• m/84'/0'/n' for native P2WPKH
• m/86'/0'/n' for P2TR

Each layer of derivation in these key paths after the master key (m) is hardened, meaning that deriving that child key involves hashing the parent secret key.

Remember QAs cannot invert a hash function as efficiently as they invert elliptic curve public keys. This means that the BIP32 master key m, as well as the xprivs at any previously unused key path, are generally safe from the eyes of the QA provided the wallet has not exposed the BIP32 master public key. We will make use of this property in some of the options we discuss later.

Quantum-Safe Signatures

The critical question is: What cryptographic mechanism replaces elliptic curve digital signatures?

Whatever mechanism replaces EC signatures must be asymmetric, allowing a user to give payment instructions to a prospective sender, without surrendering control of their money to the sender. This way the receiver can claim that payment later without revealing their signing credentials to anybody (like one would with a password to a bank website). This rules out symmetric cryptographic schemes, such as HMAC, simple hashing, or symmetric encryption algorithms like AES or ChaCha.

We have numerous quantitative metrics by which to judge a replacement algorithm:

• Public key size
• Signature size
• Secret key size
• Key generation time
• Signature computation time
• Signature verification time

We also have qualitative statements we can make about a signing algorithm:

• Statefulness: Does a signer need to maintain state between each signature?
• Reusability: Can a signer reuse their secret key to sign multiple messages?

Today we’re going to explore one genre of signing algorithms which is almost certainly the safest and most conservative candidate, but which comes with some big practical issues: Hash-based signatures, or HBS for short.

Hash-based signature schemes are constructed from a simple one-way cryptographic hash function like SHA256. Secret keys are usually vectors of preimages. Public keys are usually hashes, or vectors of hashes. Signatures are usually vectors of preimages, paired with auxiliary data needed to verify the preimages correspond to a specific static public key. Unlike other candidates for post-quantum cryptography, hash-based signatures do not rely on new (possibly flawed) cryptographic assumptions - This is what makes them the conservative option.

I’ll now give a detailed description of several well-known hash-based signature algorithms, in increasing order of complexity. If I lose you in some of the math, don’t worry - Understanding the internals of the HBS schemes is not critical to understanding how they can be applied to Bitcoin.

Skip through to the final analysis section if you don’t care about the technical details of HBS schemes.

Before we begin, some notation:

Notation	Meaning
	The set of all possible bit strings of length
	Uniform random sampling of an element from the set

Let be a secure cryptographic hash function which outputs pseudorandom bit strings of length (For SHA256, ). All constructions below are typically based on this single cryptographic primitive.

Disclaimer

I began studying these hash-based signing protocols only a few weeks ago. Do not take my technical descriptions below as precise and safe for real-world use, because I have probably made typos or omitted stuff. The purpose of these descriptions is to illustrate and convey the essence of the algorithms, not to provide any concrete implementation instructions.

Roll your own crypto at your own peril.

If you are an expert in hash-based signatures and have noticed a typo, please email me or open a pull request to fix it.

Let’s start with the simplest and earliest-known example of an HBS scheme: Lamport Signatures.

Lamport Signatures

We want to sign a single bit of information - 0 or 1 - using our hash function .

We generate two random preimages of bits each:

The tuple is a one-time secret key.

Our public key is the tuple . We can safely give the public key to anybody, and later reveal either to sign the bit zero, or to sign the bit one. Any observer with the public key can easily verify for a given bit .

We may generalize this approach to sign message strings of arbitrary bit length by generating more preimages - one per message bit. Then our secret key would be:

Each is an array of random preimages .

Our public key is made of hashes of every preimage.

To produce a signature on the message bits , we reveal the appropriate preimages per bit:

To verify, simply check that the hashed preimages match the public key for every bit in the message.

Properties

Lamport Signatures are a one-time signature (OTS) protocol - once the signer reveals a signature for a given public key, they can never use the same signing key again for a different message. If they do, the signer gives observers the ability to forge signatures on new messages they never consented to sign.

For instance, if and a signer reveals two signatures for distinct messages and , they will have now revealed all four preimages in their secret key . Any observer can now sign the other messages and even though the key owner never approved those messages.

Signatures have bit length and public keys have bit length .

Signing is simple, as it consists only of revealing secrets. Verification requires evaluations of .

Modifications

We can modify lamport signatures to improve the amount of space consumed by keys and signatures at the cost of some computation time.

Deterministic key-gen: Instead of randomly sampling our secret key preimages, we can derive them from a root secret using .

This way we only need to store a single 256-bit secret preimage for each Lamport OTS key, instead of preimages, but we do need to compute hashes to derive our public key, and we must compute hashes to sign a message of bits.

Compact public keys: We can reduce the size of public keys from to simply bits, by representing the public key itself as a hash of the standard Lamport public key.

However, we must now adjust our signature algorithm to supply not only the preimages, but also the complementary hashes, which are needed to reconstruct the public key hash .

Signatures double in size to bits, whereas public keys shrink from bits to only bits.

Verifiers can verify against by hashing each of the preimages and then hashing those hashes to re-derive .

Comparisons

The following table shows some concrete examples of time/space tradeoffs for Lamport signatures. In these examples, I’ll set , to emulate the results using the well-known hash function SHA256. All sizes are in bits.

Algorithm	Signature size	Public key size	Secret key size
Vanilla Lamport
Compact Lamport

Below I note the time complexity of Lamport signatures in terms of the number of invocations of the hash function .

Algorithm	Keygen time	Signing time	Verification time
Vanilla Lamport
Compact Lamport

Viability for Bitcoin

I expect the Compact Lamport signature approach would be the most practical flavor of Lamport Signatures, as public keys would be the same size or possibly smaller than a P2TR pubkey is today.

However, even the most space-efficient Lamport signatures with the lowest viable security levels () would require at least 6400 bytes of witness space per signature before compression. That’s 100x larger than a Schnorr signature.

There’s also the matter of key reuse. Lamport signatures are a one-time signature scheme. If a Bitcoin user spends from a hypothetical “pay-to-lamport-public-key” address, they’ll never be able to spend from that address again without giving observers some power to forge signatures.

Power users would not be affected greatly, as the best-practice touted by most experienced Bitcoiners is to use addresses only once, for a single receive/spend cycle. Yet, as we’ve seen earlier, a huge fraction of bitcoiners by volume have either never heard this advice, or have disregarded it. It will be difficult to convey to these users that address reuse with Lamport signatures will be more than just a privacy no-no - It could seriously compromise their security. This would make life especially difficult for cold-storage hardware signing devices, which rely on a semi-trusted host machine to prompt them with transactions to sign.

Lamport signatures are stateful, in that a signer should know if he has used his private key to sign a message before to know whether signing again could be dangerous.

Lamport signatures are not backwards compatible with Bitcoin’s consensus protocol as it exists today, although an outlandish scheme has been proposed by Ethan Heilman which make use of OP_SIZE to Lamport-sign the size of an ECDSA signature. Whether this approach is secure is still up for debate. But even with such creative invention, the size of such a signature would prohibit its usage in P2WSH addresses. At least with current knowledge, a soft-fork would be needed to add Lamport signature support.

Even after such a soft fork, existing addresses with exposed public keys would still be vulnerable to a quantum adversary. Users would need to actively migrate coins to a hypothetical pay-to-lamport-public-key address format.

Winternitz One-Time Signatures (WOTS)

Winternitz signatures rely on a chain of hashes starting from a set of secret preimages. By revealing certain intermediate hashes in that chain, the signer can sign a specific message.

In comparison to the Lamport scheme, WOTS shoulders a higher computational burden in exchange for much shorter signatures. Let’s see how they work.

First, let’s re-establish some parameters:

• Let be the bit-length of the message we want to sign.
• Let be the “Winternitz parameter” (used for time/space tradeoffs).
• Let be the bit-group width into which we parse the message.
• Let be the length of the message in digits of base .
• Let be the checksum length in digits of base .
• Let be the overall length of the message plus the checksum in digits of base .

As WOTS relies on hash-chains, we need a hash-chaining function which uses our primitive hash function internally.

So for instance, would hash twice.

Now we’re ready to generate our keys. We start by sampling random preimages of bits each.

To compute the Winternitz public key , we iteratively hash each preimage times.

To sign a message of bit-length , we break up into digits of base (I think of them as groups of bits).

We compute a checksum of the message:

Because , the binary representation of is at most bits long. This means we can always represent as an array of digits in base . In fact that’s exactly what we’ll do.

We append this checksum array to the message , to get the final message to sign, which is just an array of digits of base (I think of them as groups of bits).

To sign the checksummed-message , we go digit-by-digit through , and for each digit , we recursively hash the preimage , for iterations. This array of “intermediate hashes” in each hash-chain is the Winternitz signature.

A verifier given the plain message and public key must first reconstruct the checksummed message just like the signer should’ve. Then the verifier simply follows each hash chain in the signature to its expected terminal hash, and compares these terminal hashes against the public key .

If this holds for all , then the signature is valid.

Properties

Security. Note the special role played by the checksum. Without it, revealing one set of intermediate hashes should allow an observer to forge signatures on any message in a “higher” position in the hash chain.

For instance, consider the following diagramed example.

If we don’t add a checksum to the two-digit message , the signature would simply be the two intermediate hashes . But then anybody who learns this signature could forge a signature on any message “higher” in the chain, like or .

Because of the checksum construction, increasing any message digit implies decreasing at least one checksum digit . To forge the signature on the checksum as well, the observer would need to invert the hash function (implausible). So an observer cannot forge any other valid signature for as long as the signer uses their signing key only once.

Size. Signatures, public keys, and secret keys all have bit length

In case that equation seems unintuitive to you, you’re not alone. I plotted the relationship between the time/space tradeoff parameter on the X axis and the final WOTS signature size on the Y axis (in bits). I set to generate this particular graph.

Higher values of result in much smaller signatures and keys at first, but we get diminishing returns. In the limit as , it seems the shortest we can make our signatures is .

Approaching anywhere near that limit would be wildly impractical though, because by increasing we also exponentially increase the amount of work we need to do to generate public keys, sign messages, and verify signatures.

Runtime. Given a secret key containing preimages, to derive its public key we must compute hashes to derive our public key.

Public key generation uses the same hash-chaining procedure as signing/verifying. To sign or verify a signature, we must compute at worst hashes (on average, only half that).

To avoid this exponential blowup in computation time, most real-world WOTS instantiations keep quite low, usually at most 16, which would mean computing on the order of hashes for a signature operation, per bits in the message. As you can see, beyond performance will become a big issue.

_{X-axis is , Y-axis is the number of iterations of needed to generate a public key.}

For reference, my weedy little computer can generate a WOTS public key with in around 0.4 seconds. Verification and signing will each require about the same in sum, as the signer starts the hash-chain which the verifier finishes.

Curiously, due to the zero-sum nature of the hash-chain signature construction, signers and verifiers who are able to select the message they’re signing can also influence the amount of work they and their counterparty must perform. By selecting a message digit significantly lower than the base , the signer needs to do less work to compute , while the verifier must do more work to compute . This could be a hinderance for a blockchain application like Bitcoin, because one signer could disproportionately emburden thousands of verifiers (nodes).

Modifications

Compact public keys: WOTS lends itself well to compacting public keys via hashing. A Winternitz signature gives the verifier everything they need to reconstruct the signer’s public key , and so we can represent a WOTS key succinctly with its hash, in exchange for an one additional unit of work for the verifier.

This decreases the public key size from bits to merely bits.

Deterministic key-gen: Like with Lamport signatures, WOTS secret keys can be generated from a seed with only invocations of .

Smaller and more secure signatures: To improve performance and security, one should consider using WOTS+, a variant of WOTS which adjusts the hash-chain construction to XOR each of the intermediary hashes in every hash chain with a randomization vector. This odd choice allows the security proof to reduce forgeries to second preimage extraction: If someone can forge a WOTS+ signature, they can also break the second-preimage resistance of . The security of WOTS+ thus relies on weaker assumptions than standard WOTS, which assumes a forging adversary cannot break collision resistance of (easier to do than finding a second-preimage). Broadly speaking, weaker assumptions lead to better security.

This means we can get away with using WOTS+ with smaller, faster hash functions which have broken collision resistance but are still believed to be second-preimage resistant, as long as one can accept the lower security level implied by their shorter output. Or WOTS+ can be instantiated with larger hash functions, and for only a modest increase in signature size and verification complexity, we gain the added security of weaker assumptions.

WOTS+ relies on a set of -bit randomization elements and an HMAC key which can all be generated pseudorandomly with and a seed, just like the vanilla WOTS secret key .

Instead of computing the intermediate values of the hash-chains as , WOTS+ uses a keyed hash function (think of it as an HMAC). The chaining function XORs the output of each keyed-hash on with a randomization element before proceeding with the next iteration.

For instance, would be:

WOTS+ appends the tuple to the public key, so that verifiers may also compute . To improve space-efficiency for public and secret keys, we can instead derive from a public seed (which is itself probably derived from a secret seed). The signer distributes as part of their signature.

The compact WOTS+ public key can then be defined as a simple -bit hash.

More efficient signatures using brute-force compression: This paper suggests modifying the WOTS signing algorithm so that the signer repeatedly hashes the input message along with an incrementing 32-bit salt/counter , until the resulting WOTS message checksum equals some fixed static value, e.g. zero. The signer appends the salt to the signature and the verifier confirms the resulting checksum is zero.

This allows the signer to omit the checksum portion of the WOTS signature, because the checksum is verified to always work out to a fixed static value. Messages without this fixed checksum are not valid, and so the checksum itself does not need to be signed. This approach is called “WOTS with Compression” (WOTS+C).

The effect of this compression is to reduce the overall runtime of the scheme on average across keygen, verification, and signing, while also reducing signature size by removing the checksum hash chains from the construction completely. One would think signing WOTS+C would take more time, due to the signer’s brute-force search for the salt . But the signer now needs to compute only intermediate hashes for the signature, instead of . These effects offset each other. At least, it does according to the paper authors, I have not yet validated this myself.

The authors of WOTS+C even propose ways for the signer to further reduce the size of their signature by removing additional chains from their signature, at the cost of additional work to find an appropriate message salt.

Comparisons

The following table shows some concrete examples of time/space tradeoffs for various kinds of Winternitz signatures. In these examples, I’ll set , to emulate the results using the well-known hash function SHA256. All sizes are in bits.

Algorithm	Signature size	Public key size	Secret key size
Vanilla WOTS
Compact WOTS
Compact WOTS
Compact WOTS
Compact WOTS
…
Vanilla WOTS+
Compact WOTS+
Compact WOTS+
Compact WOTS+
Compact WOTS+
…
Compact WOTS+C
Compact WOTS+C
Compact WOTS+C
Compact WOTS+C

Below I note the worst-case time complexity of each flavor of Winternitz signatures in terms of the number of invocations of the hash function (or for WOTS+).

For the sake of brevity, let be the total number of hashes in each chain.

Algorithm	Keygen time	Signing time	Verification time
Vanilla WOTS
Compact WOTS
Vanilla WOTS+
Compact WOTS+
Compact WOTS+C		*

_{The additional operations in Compact WOTS+ keygen are caused by derivation of .}

* is the number of possible message hashes which result in a zero checksum. See page 6 of the SPHINCS+C paper.

Viability for Bitcoin

Winternitz signatures are significantly smaller than Lamport signatures. With compaction and deterministic key-generation, the public and private keys can be condensed down to the same constant size ( bits).

Compact WOTS+ with seem like the best compromise between speed and signature size. Assuming we use SHA256 as our hash function, WOTS+ with could be instantiated with signatures of size slightly more than 1KB, with 32-byte public and private keys. Verification would require at most 8670 hash invocations, which takes only a few milliseconds on most modern machines. WOTS+C could be used to compress signatures even further, and verification can be parallelized across hash chains since they are independent.

However, like Lamport signatures, WOTS is a stateful one-time signature scheme, so it inherits all the same security concerns as Lamport signatures regarding address reuse ergonomics.

Hash to Obtain Random Subsets (HORS)

HORS is a few-time signature protocol based on Lamport Signatures which relies on complexity theory to make signatures smaller and provably resilient to forgery.

To generate a HORS key, the signer samples some large number random preimages , and gives out the hashes of those preimages as their public key .

To sign a specific message, the signer reveals a specific subset of preimages. Which subset to reveal is dictated by the message to sign.

tells us the total number of preimages in the secret key, while is the number of selected preimages per signature. Notice there’s a space tradeoff between HORS signature and pubkey size. Increasing means larger signatures. Increasing means larger public and private keys.

These parameters also affect the security of the HORS scheme. With total preimages, we have possible unordered combinations of preimages - This is the number of possible signatures. If we have a message space bits wide, we should choose and so that ; otherwise there would be collisions where one signature is valid for more than one message.

The key ingredient of HORS is a subset selection algorithm . Given a message , this function returns a unique subset of random elements in the set

The HORS paper suggests two bijective functions which fulfill the subset-selection role of with perfect OTS security, ensuring that each message uniquely corresponds to a -element subset of .

However these bijective functions are not one-way functions, so if a signer provides two or more signatures from the same key it is trivial for an observer to forge new signatures by working backwards to determine which messages they can now sign using the signer’s revealed preimages.

To address this, HORS instead uses a one-way hashing function to select subsets - hence the name Hash-to-Obtain-Random-Subsets. Here’s how you might implement . The signer computes the hash of the input message , and then parses into -bit integers . The output of is an bit string, so this gives us at most bit groups per message hash, but we can extend the output of to arbitrary lengths (e.g. by chaining it) so this isn’t really a hard limit.

Because the output of is pseudorandom, it’s possible that the integer set we parse from it could contain duplicate elements. If this occurs, we simply discard the duplicates and allow for shorter signatures. So really HORS signatures contain at most preimages, but possibly fewer. The lower is, the more likely duplicates are to occur. This actually has been the subject of certain attacks in which the attacker intentionally tries to find messages for which the set is small, so that they don’t need as many preimages to forge a signature.

After computing , the HORS signer maps the integers to a subset of their secret key preimages. This forms the signature on message .

A HORS verifier with a public key can then verify the message by recomputing as the signer did, and checking for each preimage in .

Properties

Unlike previous signature schemes, using a HORS signing key to sign more than one message does not immediately compromise the key’s security, it merely reduces security. An attacker who sees two or more signatures from the same secret key will need to brute-force the hash function to figure out which alternative messages they can forge signatures on using the revealed preimages. This is why HORS is designated a “few-time” signature (FTS) scheme, instead of a one-time signature (OTS) scheme. The hash-to-subset approach is what enables the few-time property of HORS.

The signer still has to be cautious though, because as the attacker sees more signatures, their guess-and-check attack will get progressively easier. The HORS paper describes exactly how much easier. The following expression gives the bits of security for a HORS public key after an attacker has seen distinct message signatures.

Usually is small (less than 10 signatures) but can be increased relatively safely by also increasing either or . This quickly blows up the size of keys and signatures though.

Size. HORS signatures have bit size , while public and private keys have bit size .

If we fix (so ), and we fix a constant security level of bits, then we can plot the key size as a function of signature size .

_{X axis is the signature size . Y axis is the key size . Exercise to the reader: How would you use this information to deduce the smallest possible combined key + signature size which still achieves bits of security?}

Runtime. The HORS keygen procedure requires evaluations of the hash function . Signing is extremely fast, just a single evaluation of the subset selection algorithm , and then the signature elements are picked from a set of preimages the signer already knows. Verification is also fast, with just invocations of , and is usually much lower than .

Modifications

Deterministic key-gen: As with previous examples, we can derive the HORS secret key preimages from a single -bit seed. This reduces secret key size to bits but at the cost of additional hash invocations during key generation.

Compact public keys: A modified version of HORS called “HORS with Trees” (HORST) was proposed by the authors of the SPHINCS signature scheme. Instead of representing the public key plainly as hashes each of bits, the public key is defined as the merkle-tree root of those hashes. Signatures must be lengthened to supply merkle-tree membership proofs for each element of the signature , but this trade-off greatly decreases the public key length from bits to only bits.

Comparisons

The following table shows some concrete examples of time/space trade-offs for HORS signatures. In these examples, I’ll aim for a security level of approximately bits when (one signature). The hashed message size will vary to accommodate different parameters. All sizes are in bits.

Algorithm	Signature size	Public key size	Secret key size
Vanilla HORS ,
Vanilla HORS ,
Vanilla HORS ,
Vanilla HORS ,
Vanilla HORS ,
Vanilla HORS ,
Vanilla HORS ,
Compact HORST ,	*
Compact HORST ,	*
Compact HORST ,	*
Compact HORST ,	*
Compact HORST ,	*
Compact HORST ,	*
Compact HORST ,	*

Below I note the time complexity of HORS signatures in terms of the number of invocations of the hash function .

Algorithm	Keygen time	Signing time	Verification time
Vanilla HORS
Compact HORST			*

_{The exact amount of bits by which the HORST signature size grows (and thus verification time as well) is determined by the function (see page 9 of the SPHINCS paper for more info).}

Viability for Bitcoin

HORS is conceptually refreshing, because it demonstrates that hash-based signatures can be quantifiably secure even when secret keys are reused. Since Bitcoin signing keys are typically only used a few dozen times at most, a few-time signature scheme like HORS might be acceptable for the vast majority of Bitcoin use cases, especially if each signature decreases security by a predictable and incremental amount, rather than the all-or-nothing security risks of reusing an OTS secret key (like with WOTS or Lamport).

However Vanilla HORS compromises significantly on public key sizes, while the more compact HORST experiences huge increases in signature key sizes as a trade-off. By comparison, Compact WOTS provided public keys of the same size with signatures roughly a quarter of the signature size HORST has. Safely supporting additional signatures () would require even larger signatures.

HORS is not a stateful signature scheme, but the signer should know roughly how many times they have used a given key pair so that they can avoid over-exposing their key. On the coattails of this assumption ride the same security issues as WOTS and Lamport signatures regarding address reuse in a Bitcoin context. The problem with HORST is really that to make a key secure for reasonably large numbers of signatures, we must make our parameters very large which inflates either the keygen/signing runtime, or the signature size.

Forest of Random Subsets (FORS)

FORS is another few-time signature scheme based on HORST (discussed above). It was first introduced as a component within the SPHINCS+ paper in 2017, but it deserves a definition on its own as it improves on HORST to reduce signature sizes dramatically.

The primary distinction between HORST and FORS is that FORS public keys are represented as the hash of several merkle trees - hence the use of the term “forest”. Each leaf node of these trees is, like HORST, the hash of a secret preimage, and we sign data by revealing specific preimages along with their merkle tree membership proofs.

Let be the number of merkle trees and let be the number of preimages in each tree, for a total of preimages. The trees will all have height .

This construction gives us merkle tree root hashes . We hash these roots to derive the FORS public key .

To sign a message , we hash using a randomized subset-selection algorithm to obtain where each digit (as in HORST). But whereas HORST uses those digits as indexes into a single tree, FORS uses those digits as indexes into separate merkle trees - one index per tree - to select which preimage to reveal from each tree. This ensures that FORS signatures always have a constant size (unlike HORS or HORST).

FORS is designed to generate the secret preimages from a small seed, giving constant secret key size. Given a secret FORS seed we can compute the -th preimage as . After computing , we can group these preimages into sets of length , and then construct the merkle trees from them.

Safety Notice: FORS is designed to use tweaked hash functions which prevent multi-target attacks where an adversary can exploit precomputation to do a drag-net attack on multiple keys in parallel. Do not naively implement FORS without properly tweaking (namespacing) each hash invocation. This risk applies to HORS and other signature schemes as well, but was not well understood until recently.

Note especially that the subset selection algorithm must be tweaked with a secret value, to prevent adaptive chosen-message attackers from selecting messages which would trick the signer into revealing specific preimages desired by the attacker. Reference.

Properties

Security. Like its predecessors, FORS is a few-time scheme which means the signer can confidently quantify the security of their public key even after revealing some signatures. The bit security of a FORS public key against a signature forging attack (with attacker-chosen messages) after revealing signatures is:

_Source

By fixing a security level of bits given signatures, we can compute the required tree height as a function of the number of trees in the “forest”.

_{X axis is (number of trees). The Y axis is (height of each tree). This graph was computed with and (i.e. 128 bits of security after 128 signatures)}

For instance, with trees and signatures, we would need trees of height , for a total of preimages.

Size. Public and secret FORS keys are both a constant size of bits each.

A FORS signature consists of preimages, plus merkle tree proofs containing hashes each, for a total of bits per signature.

Runtime. Key generation requires deriving secret preimages, hashing preimages, and then computing merkle tree roots therefrom. With one final hash to compress the merkle roots into the public key, this gives a total key-gen runtime of:

Signing requires a call to (presumably a single hash invocation) to select which preimages to reveal, along with constructing merkle-tree membership proofs. If a signer can cache the internal nodes of the merkle trees in memory, they can compute a signature with only a single invocation of .

If on the other hand the signer starts from just the seed (pre-keygen), then to construct a merkle proof for a single tree, they must first derive the preimages for that tree. Then they recompute hashes on level 0 of a tree, then hashes on level 1, then hashes on level 2, and so on until level where they only need to compute a single hash, finally arriving at the merkle root of the tree. Expressed more generally, this would require invocations of per merkle proof. The signer must construct merkle proofs, so the total worst-case signer runtime is:

The verifier’s runtime is much smaller. The verifier must run to compute the selected preimage indexes. They must hash each of the preimages from the signature, and verify the merkle proofs with hash invocations each. With one final hash to compute the expected signer’s pubkey, this gives a total verifier runtime of:

Check out the following graph which compares the time/space performance of FORS signatures. For this visualization, I fixed the FORS security parameters and (i.e. 128 bits of security expected after 128 signatures), with a hash output size of .

Along the X axis is an input , for the number of FORS trees. The tree height is computed as before as a function of to achieve our desired security level.

• The orange curve is , representing the total number of preimages the signer must generate and hash into their public key. This curve is directly proportional to both key-generation runtime and signer runtime (or memory usage if caching is used), but it does not affect public/secret key size.
• The pink line is the signature bit-size , which grows linearly with .
• The blue line hugging the X axis is the verifier’s runtime . It grows linearly with , but for all reasonable choices of the verifier needs to evaluate at most a thousand hashes or so.

This suggests that for the and parameters we fixed here, we likely would want to set . Any lower, and signers would experience an exponential runtime blowup. Any higher and we get diminishing returns in signer runtime savings.

Playing around with the parameters a little, we can see that using fewer but larger trees (lower w/ higher ) gives signers another advantage besides small signatures. Like with HORS, lower means fewer preimages revealed per signature, which means the security bit-level decreases more slowly as signatures are revealed.

See the following visualization with as an input on the logarithmic-scale X axis.

On the Y axis is the expected security level after signatures. The different lines represent the declining security of different FORS parameter sets. FORS tree heights were computed with setting and (same as before), but this graph shows what happens before and after a signer has issued their 128 signatures.

• The pink line is FORS with , .
• The green line is FORS with , .
• The orange line is FORS with , .
• The blue line is FORS with , .
• The white dashed line is bits of security, which represents an approximate boundary below which forgery might be practically achievable for currently available hardware.

Note how the FORS signer (pink line) can create almost signatures before their key’s expected security drops below 80 bits. At the opposite extreme, the signer (blue line) can only create 214 signatures before crossing the same boundary. Even though the tree height was computed the same way for all four signers, the security of signers with fewer trees decreases much more slowly.

Modifications

Security against adaptive chosen-message attacks: The authors of this paper suggest modifying the FORS signing algorithm to make the subset-selection function dependent on the signature itself, using a chain. They call this algorithm “Dynamic FORS” (DFORS). But they also note that a simple pseudorandom salt as used in SPHINCS+ is sufficient for safety against adaptive chosen-message attacks. As such I have elected not to go into detail as the DFORS modification seems unnecessary.

More efficient signatures using brute-force compression: This paper suggests modifying the FORS signing algorithm so that the signer repeatedly hashes the input message along with an incrementing 32-bit salt/counter , until outputs a set of index digits with a trailing zero digit at the end (i.e. the last bits of the salted message hash are zero). The signer can then FORS-sign the set of digits , omitting , and including the salt in their signature. The verifier recomputes and checks the final digit matches the requirement .

Because is also enforced by the verifier, the signer can omit the last preimage and merkle proof on from the signature, as that digit of the message is presumed static (A message which never changes does not need to be signed). Indeed the signer doesn’t need to even have a final -th tree.

The effect of this modification is to reduce signatures size by approximately bits, and reduce signing/verifying runtime as well (though I have not verified the runtime-reduction claim). The authors call this modification “FORS with compression” (FORS+C).

The authors have also noted that if the signer wishes to further reduce signature size, they can perform additional work to reduce the size of the 2nd-to-last tree by forcing more trailing bits to hash to zero.

Intuitively, this compression mechanism has a larger impact when the trees are larger (when is larger), because pruning the last tree from the signature construction makes a comparatively larger impact. Of course the trade-off is that we must do more work to find a salt which produces a message hash with trailing zero bits. On average to find a hash with trailing zeros, we must compute hashes, with hash invocations at the very worst.

Smaller signatures using Winternitz chains: This paper suggests extending the leaves of each FORS tree with a chain of hashes, much like the Winternitz OTS scheme. This extra dimension gives a new parameter, the length of the Winternitz chains , with which to expand the space of possible signatures. Now signatures are composed of intermediate hashes within the chains hanging from the FORS tree leaves.

More possible signatures for the same size message means in theory that signatures should be more secure. This modified scheme is called “Forest of Random Chains” (FORC). One could think of standard FORS as a FORC instance with chains of length .

The authors demonstrate that this extension improves reduces probability of two signatures colliding within a tree from