Post Quantum

Overcollateralized Jonny asked this:

Which is something I've been thinking about for a while!

Quantum safe blockchains will be needed sooner than many think, so we probably need to ask: wen quantum?

Armageddon!

OK, OK, so not armageddon. But more serious than the whole Y2K thing, and that caused quite a stir.

Our on-line life relies heavily on cryptography. From the methods used to keep our internet traffic private to the signing algorithms used on blockchains. Blockchains use asymmetric cryptography, aka public-key cryptography. If you do anything on a blockchain you will be familiar with this. You have a public key (sometimes called your wallet address), and a private key (the thing the scammers ask for when posing as metamask support).

If you have the private key you can prove you control the public key. And for someone else to brute force your private key they would need to build a Dyson sphere around the sun and harvest all it's energy for a million years.

Or something like that.

That is, until we get quantum computers with enough qubits to do the job in a few days, or hours, or minutes.

Oh my.

What do we use for signatures atm?

We use ECDSA (Elliptic Curve Digital Signature Algorithm). Bitcoin and Ethereum use slightly different flavours.

An advanced Quantum computer will eat them for breakfast. . .

The Standards

But don't worry! The NIST (The National Institute of Standards and Technology) from the US Department of Commerce is here to save us all! I am reliably informed these heroes do indeed wear capes to work every day. Which is possibly not what you would expect from an organisation devoted to the generation of new technical standards.

In July 2022 NIST announced four Post-Quantum Cryptography candidates for standardisation.

Of these four, three are standards for digital signatures, so of relevance for blockchains:

• CRYSTALS-Dilithium
• FALCON
• SPHINCS⁺

First of all: yes, they all sound very geeky. And no, apparently SPHINCS isn't an acronym for anything (it was chosen as it sounds like Sphinx).

So will one of these be what we use in 2030 to mint an NFT showing a lizard with the head of a cat wearing sunglasses with a tattoo of the number eight on its left bicep?

This bird won't fly (imo)

There are pros and cons for any of these approaches. But I am going to go wild and eliminate FALCON right out of the gate!

FALCON is particularly vulnerable to side-channel attacks, where information about it's operation (timings, power consumption etc) could be used to inform an attacker's approach.

Maybe not the best for a public blockchain with distributed nodes then. (IMO).

CRYSTALS-Dilithium vs SPHINCS+

So, it's the Star Trek warp core vs an enormous Egyptian statue!

Somehow I always knew it would come to this...

And here's the thing, neither is ideal for crypto. If we look simply at the 256 bit implementations of each we need to consider (among other things) the size of the keys, the size of the signatures, and the effort required to sign and verify.

Key Size

Round one goes to SPHINCS+. The public key (your wallet address) will be 64 bytes long with SPINCS+. On Ethereum it's currently 20 bytes long. So yeah, a bit of a pain, but you go from this:

0xf50b18912b717dc35ed064ce4b5e73710bdf4db2

To this:

0xf50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8

I mean, that's clearly a lot longer, but not outrageous (it's twice the length of a transaction hash).

With Dilithium your wallet address is, um, 2,592 bytes long. So:

0xf50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8f50b18912b717dc35ed064ce4b5e73710bdf4db27fb96922409e3b4b3b8771d8

Now, this might not matter (maybe). I could see services like ENS becoming very important. Or indeed some other more embedded public key to wallet address abstraction getting baked in.

But I am calling this round for SPHINCS+

Signature Size

The Star Trek crew immediately strike back! They detonate that warp core at just the right moment and the SPHINCS is left reeling.

Your current signature on Ethereum is 65 bytes long.

Using Dilithium it would be 4,595 bytes long (a cool 70x, uponly!).

Using SPHINCS+ it would be 29,792 bytes long, using the space saving implementation. So that's over 458 times as big...

I don't know how signatures are costed by the EVM, but if they take 16 gas units per byte like calldata that signature costs 476,672 gas.

Round 2 to Dilithium.

Tie-Break: Effort to Process

I found a brilliant graphic with the processing time for each method. It was amazing, so easy to compare all the approaches.

And now I can't find it.

But, TLDR, this is a win for Dilithium. By quite a margin.

The Future

As is so often in life, when it comes to the future it's too early to call. But from a practical perspective it looks like CRYSTALS-Dilithium has the edge. Sending 29,792 byte signatures (with SPHINCS+) just feels like a problem that can't be overcome.

On the other hand, I can see us needing an abstraction over the enormous public key that is needed with CRYSTALS-Dilithium. So maybe you have a public key, but everyone interacts with some other identifier (let's be all cute and call it your "cryptoname"), that is much shorter.

But then how do we avoid collisions, other than using an on-chain registry? Or can we just make a 32 byte hash of your 2,592 byte public address and use that, somehow? But if we do that, are we forever hashing the 2,592 byte public address to ensure it matches the 32 byte "cryptoname"?

One thing is for sure: there is more work to be done here.

Disclaimer

All and any inaccuracies in the above are my own error. Feel free to point them out, would love to talk with you.

If you enjoyed this, please say (@0mnus).