Please consider these blockchain use cases for Post Quantum digital signature schemes

[Doge Protocol]

Blockchains require certain properties from digital signature schemes for their scalability and usability. Please consider blockchain use-cases as well when finalizing candidate(s) to be standardized for PQ digital signature schemes.

1) Signature and Public Key size
==================================
The more the size of the signature and the public key, the larger the storage and bandwidth requirements are. Especially in proof-of-stake blockchains, signature sizes become critical, because a large number of validators need to sign each block (once every few seconds). These need to be transmitted over the network and also persisted on the disk forever.

For example, a blockchain with a block time of 12 seconds (like Ethereum) and 128 validators per block, would need close to 600 MB of storge per day with Falcon-512 signature sizes. This would decrease the decentralization factor of blockchains; because validators will need bulkier machines with larger storage and bandwidth requirements, which fewer people can afford.


2) Speed of the Verify operation
=================================
For each block, in typical proof-of-stake blockchains, many tens if not hundreds of validators need to verify the signatures of every other validator. They would also need to verify the signature of each transaction. If the verify operation is slow, this would impact the transactions-per-second of the blockchain. The tradeoff would be to decrease the number of validators which would also mean lesser security and thus reduces the decentralization factor. The other tradeoff is reduced number of transactions per second. Thus, to enable higher TPS and also maintain a level of security, the speed of the Verify operation is critical for blockchains.

3) Signature Aggregation
=========================

https://en.wikipedia.org/wiki/BLS_digital_signature
https://eprint.iacr.org/2018/483.pdf
https://ethresear.ch/t/pragmatic-signature-aggregation-with-bls/2105

Current elliptic curve based schemes support signature aggregation which can be verified at scale. Without such a scheme, blockchains will have reduced transactions per second and have to tradeoff on heavier machine requirements (which reduces the decentralization factor).

Is such signature aggregation possible with any of the post quantum digital signature schemes?

We read about STARK based aggregation for quantum security, but worried that without standardization and getting scrutinized by the larger cryptography community, such schemes won't be properly reviewed for security loopholes (thus causing future security risks in blockchains like Ethereum that intends to adopt it).

4) Recovery Phrases
=====================

https://medium.com/geekculture/what-is-bitcoin-improvement-proposal-32-bip-32-586a3f36a95c

Recovery Phrases also known as Mnemonic Phrases provides a human-friendly way to store private keys. They are made possible by certain properties of ECC. While not secure as hardware wallets are, they do enable wider adoption of blockchains because of simplicity of use and their human friendliness.

Is such a scheme possible with any of the candidates for digital signature algorithms?


5) Key Recovery Mode
======================
Public key recovery from Signatures offer a way to reduce bandwidth, since such a signature will be fewer bytes than sending signature+public key over the wire. Consider a blockchain that does thousands of transactions per second (Solana blockchain does 60000 TPS); these small savings become significant in reducing bandwidth at this scale. Reduced bandwidth requirements also increase the decentralization factor.

Schemes like Falcon offer a key recovery mode but it doesn't seem to be part of the official standard. Can we consider evaluating the security of the key-recovery mode as well for post quantum candidate finalization, so that it becomes well scrutinized and vetted by this cryptography community.

[Bas Westerbaan]

Thus, to enable higher TPS and also maintain a level of security, the speed of the Verify operation is critical for blockchains.

You'll be happy to learn that many PQ signature schemes verify signatures faster than P-256.

 

Is such a scheme possible with any of the candidates for digital signature algorithms?

Yes, all of them.

[Yaroslav Pilshchikov]

Currently Tidecoin is using Falcon-512 as a signature scheme. The blockchain is in mainnet for over a year and works just fine.

I wonder, are there post-quantum secure signature aggregation schemes that can serve the function of BLS?

ZK-STARKS usage are covered by patents as far as I know and they are not NIST approved.

Kind regards, Yaroslav.