Introduction
It’s 2034 and mid-day on a Thursday. Your mom just called, she needs some urgent help paying a ransom to get access to her emails and bank passwords — someone’s locked her computer. You go to find your hardware wallet only to discover that your dog just destroyed your ‘primary’ signing device. Luckily, you moved your funds back in 2028 to a new key format that Blockstream Research launched in 2026, SHRIMPS, which will let you use your backup key to sign for your funds without a problem and without spending all the available balance for fees.
Backing up wallet state is a big issue for post-quantum hash-based signatures. Blockstream Research’s latest update is a push in the direction of better, stateless backups without giving up gains in conserving blockspace.
The previous Blockstream Research post-quantum signature scheme was reported on by Insider Edition. Our deep dive on SHRINCS, a quantum-resistant scheme combining both stateful and stateless hash-based signatures shows how stateful and stateless schemes can be combined in a single signature. Stateful schemes allow for smaller signatures, at the cost of needing to keep track of which signatures have been already used (this is the ‘state’ you’re tracking).
If the record of what signatures have already been made is lost, like in our opening horror story, you can no longer use the keys without risking compromising their security, which would allow someone else to move your funds.
On the other hand, we have stateless signing schemes. These can be easily restored from a static backup such as a seed phrase, but the signatures they produce are quite large — you trade cheap onchain signatures for a guarantee of being able to use it if lose your device.
SHRINCS, Blockstream Research’s first post-quantum (PQ) signature proposal, fuses a stateful and stateless scheme to give you the best of both worlds. The combined signature scheme uses the stateful scheme which produces smaller signatures for ordinary operations, but falls back to the stateless, more expensive signatures, if your signing history is lost. SHRINCS’s stateless signing mode removes the risk of producing weak or forgeable signatures from lost state, while allowing you to benefit from smaller, stateful signatures in the default case.
On March 27th, Director of Blockstream Research Jonas Nick introduced a new scheme called SHRIMPS on the popular technical forum, Delving Bitcoin. SHRIMPS is another PQ signature scheme proposal. As a product of one of Bitcoin’s most experienced research labs, it aims to improve on the earlier SHRINCS proposal.
By default, a SHRINCS backup signing device would default to using the stateless signing mechanism. In this case, your keys lose the ability to produce smaller signatures, moving from 324 bytes per signature to up to 8KB, a 25x increase in on-chain weight. This is problematic, given that you pay for every byte used in a bitcoin transaction. Backup signing devices, if used, would produce 25x more expensive transactions.
SHRIMPS, the latest proposal, aims to optimize the fallback option of SHRINCS. Instead of having a single fallback option, SHRIMPS would allow user’s backup devices to sign in a compact form until a threshold number of signatures is reached, and only once the limit on smaller signatures is reached, falling back to the more expensive, larger signature signing option.
Basics of SHRIMPS
The construction of SHRIMPS combines two instances of SPHINCS+, a stateless hash-based PQ signature scheme. SPHINCS+ is complex. It’s constructed using several WOTS+ and XMSS nested trees to produce a single quantum safe key-pair. A SPHINCS+ key-pair can be used to sign many messages safely.
The depth of navigating the SPHINCS+ hash tree to locate the public/private key is what contributes to the large size of SPHINCS+ stateless signatures. The statelessness comes from the low probability of ever picking the same path in the tree again, at random. However, there is an upper bound to how many signatures can be produced in a SPHINCS+ tree before the odds of picking the same path again goes above what is considered ‘safe’.
In the SPHINCS+ literature, q_sis this upper limit. It’s the bound on the number of signatures that can be securely produced under a single SPHINCS+ key tree. q_s also governs the depth of the nested SPHINCS+ trees. So a smaller q_s means smaller resulting signatures, as it takes less data to describe the path through the SPHINCS+ forest. A smaller tree means less signatures that can be safely produced, but also less data per signature.
SHRIMPS uses this q_s to create two different SPHINCS+ key trees, and then binds them together into a single key, which can sign using either of the two SPHINCS+ trees. The trees only differ on the value of their q_s parameter: The first instance, referred to as compact path, uses a low q_s, which allows for smaller, but very limited number of signatures; the second instance uses a larger q_s. It produces much larger signatures, but can sign an almost infinite number of times.
Since both options are using SPHINCS+, both tree options are independently stateless. Unlike in SHRINCS where on one path you must remember what you’ve signed, SHRIMPS’ paths only need to remember how many times the lower-bound SPHINCS+ tree has been used.
According to Nick, for the compact instance q_s = 2^10 would be a good, conservative bound — providing around 1024 signatures —, while the fallback instance should be implemented with a sufficiently large parameter, such as q_s = 2^40 or q_s = 2^64 — an upper bound of around 1.85 x 10^19 signatures.
The SHRIMPS public key p_k is the hash of the public keys of each of the two SPHINCS+ treesets. A signature consists of a SPHINCS+ signature under the chosen instance s_k1 and the public key of the other p_k2. The verifier reconstructs the signing instance’s public key p_k1 from the SPHINCS+ signature, hashes p_k1 and p_k2 to reconstruct the combined public key, and compares it to the known SHRIMPS public key, p_k.
When initializing a new device by providing a seed, it will deterministically derive keys for each of the two SPHINCS+ instances. Each device will have its own, independent, persistent state to check whether the compact path has already been used or not.
How Many Signatures?
Assuming that the compact signature can be used to sign at most once for every device, q_s basically becomes the upper limit to the number of devices that could be initialized, n_dev. Setting q_s = n_dev = 2^10 means giving the user the possibility to initialize more than one thousand devices, which seems a lot, even in the most pessimistic cases. Hopefully, no one would lose access or break a device more than one thousand times!
The “budget” could also be expanded to provide each device with more than one compact-path signature to be used. For example, setting n_devsigs = 2^4 would provide the possibility to sign 16 times with the compact instance with each device, nevertheless resulting in a signature smaller than 3KB. In this case, the parameter would be set to q_s = n_dev x n_devsigs .
As we said, each device needs to store an independent counter to decide whether to use the compact signature or not. The counter will be log2(n_devsigs + 1) bits in size, depending on the number of signatures available for each device.
In the simplest case — one device, one compact signature — the signing flow would require to check whether the independent, single-bit counter is 0 or 1. In the first case, the device will sign using the compact SPHINCS+, resulting in a 2.5KB signature at 128bit security. Otherwise, it falls back to the larger instance. In case n_devsigs > 1 , the device will be able to use the compact signatures several time until exhaustion — 16, in case n_devsigs = 2^4.
If the number of compact-path signatures exceeds the q_s budget, security does not break down immediately. Instead, it degrades gradually, as the the table provided by Nick clearly shows. With a budget set to q_s = 2 ^10 , the security of the scheme is 128.0 bits. Using 2^11 signatures doesn’t degrade security, which only start to drop tp 125.1 bits when signing with the compact scheme 2^12 times (i.e. 4 times the available budget).
Putting it all together
As previously said, the aim of SHRIMPS is to improve on the stateful scheme side of SHRINCS to provide a safe path towards funds recovery. When using SHRINCS, if a single signing device is lost, the scheme allows the user to recover its keys using a static backup. However, it will default to use the heavy stateless scheme as soon as the state for the smaller signature scheme is lost.
SHRIMPS provides an intermediate step between the lean stateful signatures (324 bytes) and the huge stateless ones (~8KB), by allowing for a series of devices, each which can track their state independently and produce smaller SPHINCS+ signatures until the counter expires.
Putting together SHRINCS and SHRIMPS would result in the following workflow:
The first device is initialized, and the stateful scheme is used to sign any transaction. The stateful scheme is used until the state is known, to avoid breaking the cryptographic assumptions of the scheme. Each signature is 324bytes in size.
Once the state is lost (i.e. first device is no more usable), a new device is initialized. The compact SPHINCS+ instance is used to sign until the budget
n_devsigfor the device is reached. Each signature is ~2.5KB in size.When the whole budget has been drained, the SPHINCS+ with the larger
q_sparameter, and thus larger signatures, is used. Each signature would be between ~4KB and ~8KB depending on the exact parameters chosen, but the number of signatures available is high enough to allow for practically unlimited signing.
In the following table, we can see the size of the signatures produces by the different algorithms:
Post-quantum Bitcoin is Moving
Brink recently announced that they had hired quantum cryptography researcher Conduition, to focus on making Bitcoin quantum-secure. His main area of focus will be to make SHRINCS a reality, providing a usable protocol and draft BIP for the signature scheme. This seems to point to the fact that SHRINCS could be a viable solution in a post-quantum future. Building upon this protocol, thus, follows a natural course. SHRIMPS is another clever solution to improve the UX of post-quantum signatures even more.
And earlier this month, following the rash of LLM powered attacks on existing Bitcoin infrastructure, Jonas Nick announced a preliminary C library — libshrincs. It is a handwritten C library implementing WOTS+C, the one-time signature used by SHRINCS for the stateful signing path.
On August 27th Jonas Nick also announced the publication of BIP SHRINCS, the draft proposal specifying all the underlying cryptography needed for the scheme to work. While using SHRINCS in Bitcoin Script would require a separate BIP, this proposal defines the design choices, new parameter set, and improvement on top of the original proposal. The BIP is up for debate and the SHRINCS working group — composed by Conduition, Mike Casey, Ethan Heilman, Remix, Boris Nagaev, Mikhail Kudinov, Oleksandr Kurbatov, and Nick himself— is waiting for feedback on the proposal.
Research on post-quantum signature for scarce resource environments is still at the beginning, but the ball is already moving. Improving on the small signatures, and fallback in case of state loss is another step towards a better experience using Bitcoin securely and cheaply in a post-quantum world.