This is the detailed cost analysis behind the post-quantum transition: what it costs, what has been measured, and what follows from it. The overall path and how it fits the rest of the programme belong to PQ Migration for Logos Blockchain. Work that is still open is in the companion document:

Fix idea propositions

The short version

We use Groth16 today. A quantum computer would break it. So we have to replace it.

Only the proof system is exposed to a quantum adversary. The keys people hold are not. Nobody has to invent a new secret because their old one leaked.

Some vocabulary first, because the rest depends on it.

A public key is a hash of a secret key. Today that hash works over a large field, the one BN254 uses. The post-quantum prover works over a much smaller field (Goldilock for example for now but not settled), and computing the old hash inside it is very expensive. So we will start deriving public keys with a hash the new prover speaks natively. Old-style key means one derived the way we do it today (Poseidon2 over BN254). New-style key means one derived with the native hash (Rescue over Goldilock). Every note carries whichever kind it was created with, and there is a signature circuit for each.

With that:

Migration needs no coordination. Both signature circuits stay valid forever, so nobody is ever locked out of their money. A new-style key is much cheaper to spend, so wallets will default to sending to one, and every note moves over as a side effect of being spent normally. There is no migration step, no special operation, and no deadline for anybody's funds.

ZkSignature proofs grow from 128 bytes (Groth16 compressed) to between 12.8 and 35 KB (ZK-STARK), depending on how many public keys they prove. The other three proofs are separate and are not covered by those numbers. Four consequences follow (without optimization, just updating the proving scheme):

The change with the best return involves no cryptography: sizing each signature to the number of public keys it actually proves rather than fixing it at 32.

Only the proof system is at risk, not the keys

Groth16 does two separate jobs for us. Only one is in danger, and separating them is what makes this migration cheap.

The first job is soundness. Soundness means you cannot produce a proof that gets accepted unless you really know the secret. Groth16 gets this from elliptic curves, and more precisely from the discrete logarithm problem being hard. A quantum computer running Shor's algorithm solves that problem, so soundness breaks and a quantum attacker could manufacture a proof our nodes would accept.

The second job is the link between a secret key and its public key. For that to be safe we need one property: given the public key and the proof, nobody can work backwards to the secret (or another one with the same pk!). That is a property of the hash function, not of the elliptic curve, because the proofs themselves reveal nothing about what they prove, so a quantum attacker learns nothing from the history either.

Shor's algorithm does nothing to a hash. The best known quantum attack here is Grover's, and Grover only halves the effective security level. Our hash output is about 254 bits, so halving still leaves an attacker facing about 127 bits of work, which is far out of reach.