Project Eleven published a review of the SHRINCs proposal today. SHRINCs is a hash-based, stateful scheme for post-quantum signatures #1555802, #1546995, that relies on SHA256 and one-time use signatures.

Project Eleven's review points out a number of the benefits of the SHRINCs proposal:

• SHRINCS is instantiated entirely with SHA-256, so it introduces no new family of mathematical assumptions into Bitcoin.
• the best-known quantum attack on a hash function, Grover's algorithm, gives a far smaller speedup than Shor's algorithm gives against ECDSA
• SHA-256 is heavily optimized, hardware acceleration is widely available, and the verification cost per byte is low.

But, they ultimately come to the conclusion that SHRINC isn't quite right:

Even though SHRINCS is meant to be a solution to the problem of securing Bitcoin in the post-quantum era, a primary design goal of SHRINCS seems to be optimizing block space, a shared and currently abundant resource. In doing so, it introduces a potential failure mode that is silent, irreversible, and borne by individuals at the exact layer where their money lives.

They claim that the statefulness requirement of SHRINCs (you really, really don't want to use the same signature twice) puts a lot of burden on wallets to get the implementation correct:

The signer has to maintain a counter that only ever moves forward, to ensure that no signature is ever used twice. If the same state is used to sign two different messages, the same one-time key is reused, potentially breaking the security of the scheme and allowing an attacker to forge signatures and steal funds.

In the nightmare scenario, you restore your wallet from a backup and the backup doesn't include the fully up to date state with the result that you leak your private key when you spend because you accidentally reused a signature.

SHRINCs does have a stateless signing mode that can be used if you are worried that you are inaccurate in your state of the wallet, but it creates a much larger signature.

Project Eleven's review points out three cases where statefulness becomes a footgun:

Consider a hardware wallet. An attacker gets a copy of the device's encrypted SHRINCS state. The owner then signs a transaction, moving the counter forward. If the attacker can later restore the old state to the device, the wallet can reuse a WOTS+C leaf the next time it signs. The attacker does not need to extract the private key. All they need is the ability to roll back security-critical state.

Software wallets have a more mundane version of the same problem: backups. Let's consider a scenario where a wallet is backed up to iCloud. The user signs transactions and advances the SHRINCS state, later loses their phone, and restores an older backup. Unless the wallet has some independent rollback-resistant mechanism, its local state is now behind the actual signing history. No attacker required. Normal disaster recovery creates exactly the condition SHRINCS is trying to prevent.

Seed portability raises a similar issue. Bitcoin users expect to be able to restore a seed into another wallet. A seed can recover the SHRINCS secret material, but it cannot tell the new wallet which stateful WOTS+C leaves have already been used. The BIP handles this correctly by requiring stateless signing when the counter is unavailable or uncertain.

Ultimately, the Project Eleven people conclude:

In our view, SHRINCS is elegant engineering, and evidence that serious people in the Bitcoin community are taking Q-Day seriously. But the case for the additional benefits, and complexity, that statefulness brings is not primarily a security argument. It is largely an attempt to avoid a political one.

And that a blocksize increase should be on the table (because many quantum resistant signatures are much larger, proposals like SHRINCs have optimized for size and, Project Eleven claims, introduced trade-offs).

One of the SHRINCs authors, n1ckler, has already responded. While he agrees with a number of the things the Project Eleven guys are saying, n1ckler notes:

The review suggests that the stateful path lets the SHRINCS authors say the block-size concern has been addressed. The intent is rather that SHRINCS doesn't depend on a block-size increase, so that question can be discussed separately without holding up post-quantum signatures.

The review describes stateful signing as an optimization, which fits better than the BIP's "primary path" wording. It also made me realize that calling the stateless path a "fallback" is misleading, and we're considering changing the terminology in the BIP.

It's an interesting conversation and worth spending half an hour reading through if you want to stay up on the latest quantum readiness stuff.