[INFO - DISCUSSION] SHRINCS - draft BIP for a post-quantum signature scheme

[cygan]

today, the following Bitcoin improvement proposal (bip) was published for his experimental SHRINCS signature scheme.
the proposal targets a major future threat posed by sufficiently powerful quantum computers.
according to Jonas Nick from Blockstream research, SHRINCS is not intended to be the final signature scheme for Bitcoin.

draft-bip: https://github.com/SHRINCS/shrincs-bip/blob/main/SHRINCS.md
bitcoin-dev post: https://groups.google.com/g/bitcoindev/c/HbVboXIFiG8?pli=1

https://cointelegraph.com/magazine/shrincs-bip-is-published-quantum-secure-bitcoin-comes-with-a-catch

[Antidote47k]

From my understanding, the stateful part uses one-time signing keys, which means the signer has to keep track of the ones that have already been used. Essentially reusing an old signing state could compromise the security of the scheme, so protecting that state is an important part of the implementation.
SHRINCS also provided a stateless fallback for cases where state can’t be safely recovered so this shouldn’t be problem in general but I’m curious how it works in practice.

With a normal seed back up, you can loose the device and still restore the seed and continue using the wallet, with a stateful scheme, an additional piece of signing state has to be managed correctly, so in this case would the wallet normally use the stateful scheme if the state is available, then switch to a stateless scheme if t isn’t? And how would this be communicated to the user with complicating the backup/recovery process?

[d5000]

I think SHRINCS could be an excellent option for Tadge Dryja's proposed recovery mechanism [1] or other recovery schemes like [2].

For now (and probably several years), people can use P2WPKH as normal - as long as the public key is not known, i.e. you don't re-use the address (or publish your key somewhere accidentally), your funds are not at risk even with advanced quantum computers.

Now if QCs become powerful enough, Dryja proposed roughly the following scheme:

1) confirm a transaction with a proof that you know the private key (e.g. a transaction ID) on the blockchain
2) reference this proof in a second transaction where you effectively move the coins.
3) transactions which move ECDSA coins that don't contain this proof are invalid after a deadline (which requires a soft fork).

For step 1 and 2, a quantum safe mehtod is needed, but this wallet is no necessarily meant to be a permanent storage, it can be an intermediate or short time wallet. So the "stateful" problem isn't really relevant because ideally you would use it only once (or a few times), that problem appears mostly when you want to use the wallet for "daily" usage, i.e. to transact every now and then. But in Tadge Dryja's mechanism, it is needed only for an "emergency".

Implementing SHRINCS on the Bitcoin protocol in the mid term (e.g. before 2028 or so) would give us the option to use Dryja's recovery method as soon as the problem materializes. This means: If really this Google study is correct and in 2029 a quantum threat is already realistic, then we have already a safety net and Bitcoin could be continued to be used without major disruptions. But the developers have then more time to develop a better solution for the 2030s.

Of course this does not protect re-used addresses and/or P2PK and similar vulnerable coins.


[1] see mailing list post: https://mailing-list.bitcoindevs.xyz/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n@googlegroups.com/
[2] Bitcointalk thread: https://bitcointalk.org/index.php?topic=5571348.0