By research@web3.foundation
1. Introduction
This document lays the roadmap to making the Polkadot and JAM protocols Post Quantum-resistant (PQ-resistant).
While post-quantum attacks are not posing any practical threat to the security of Polkadot network currently, we want to stay ahead of any possible threat even if the risk lies in the future. We propose to secure Polkadot and JAM against potential post-quantum attacks by replacing cryptographic primitives used at the consensus layer and, in account, certification of these protocols with post-quantum ones. The central cryptographic primitives used at consensus layers are hashes, signatures, and VRFs. The hash functions currently used in Polkadot and JAM are deemed post-quantum secure and, therefore, could be used as they are. The signature and VRF primitives, however, need to be replaced or supplemented with a cryptographically secure one.
Organization: Section Signatures introduces the various signature schemes used by Post Quantum Polkadot and JAM. The post-quantum secure signature primitives we recommend are the lattice-based NIST standards ML-DSA, Falcon, and ML-KEM, with the former and latter formerly known as CRYSTALS Dilithium and Kyber.
Section VRF explains how to replace the current usage of Elliptic curve-based VRFs in Polkadot and JAM with post quantum secure solutions.
Additionally, to secure the transport layer, which makes communication possible between Polkadot nodes, the minimum primitives needed are signatures and the non-interactive key exchanges. As this problem is far from unique to Polkadot and JAM architecture, we could safely assume that post-quantum secure transport layer protocols will emerge and be standardized, and we can use them to secure the Polkadot transport layer. While this is out of the scope of this document, we will briefly examine this issue in the Section Transport Layer.
2. Signatures
The Falcon and Dilithium signatures are the two signature schemes approved by the National Institute of Standards and Technology as post-quantum secure signatures. We use both schemes in different parts of the Polkadot protocol to replace all signature schemes.
- Falcon: Falcon offers a faster signature scheme with a smaller size. However, this scheme does not have a constant implementation time. As explained in the General Account Signatures section, Polkadot will use this scheme to handle accounts stored in the Polkadot state.
- Dilithium: Dilithium offers a bigger and slower signature scheme. However, it has a constant-time implementation, which makes it suitable for a consensus protocol. The Validator Signatures section describes this in detail.
For the reference, we are listing various benchmarks comparing these schemes here:
- Dilithium vs. Falcon – wolfSSL
- https://csrc.nist.gov/csrc/media/Presentations/2022/benchmarking-and-analysing-nist-pqc-lattice-based/images-media/session4-howe-benchmarking-analysing-pqc2022.pdf
- Search | CSRC
2.1 Validator Signatures
We will use the Dilithium scheme as specified by NIST for all messages signed by a validator except for BEEFY messages. This includes GRANDPA signatures, for example. Note that this is different for the current situation in Polkadot, as some signatures are currently integrated with VRF schemes and so the signature scheme is chosen to facilitate that integration. As such, validator schemes are not harmonized. VRF primitives are handled differently in post-quantum secure Polkadot, making harmonizing all validator signature schemes possible.
We use the same scheme for block production, that is, we use this scheme to sign the block after generating it. However, the VRF aspect of Sassafras’s single leader election protocol, which dictates who is eligible to generate a block for a given slot, must be handled by a post-quantum secure protocol described in the Sassafras section.
2.2 Account Signatures
The Falcon signature scheme is going to be used to secure accounts in post-quantum Polkadot. The migration from the current account scheme to Falcon is explained in Account migration section.
2.3 Account Migration
A post-quantum secure FRI-based SNARK is used to prove that the account holder knows the seed that has been hashed to generate the elliptic curve private key without revealing the private key itself. The FRI proof of 100s of KB is a signature of knowledge of the seed used in HDKD, resulting in the private key corresponding to the account elliptic curve point. This exploits the fact that even though the secret key for elliptic curve signatures is not post-quantum secure, it is actually derived using hashes, which are post-quantum secure.
The user submits the relatively large FRI proof to demonstrate the secret seed’s knowledge and the association of the post-quantum secure public key to the same seed. The large proof size is not prohibitive, as this demonstration needs to be carried out once. Since most users already use standardized algorithms for deriving keys from the seed, many cold wallets can transition to post-quantum crypto without having each account set up PQ keys in advance.
This is based on a similar idea from this ETH Research post by Vitalik Buterin. However, Vitalik Buterin suggests using a proof of knowledge that also includes the correct derivation of the lattice public key from the seed. This leads to an unnecessarily larger circuit than one for a signature of knowledge.
Chiesa, Manohar, and Spooner show in their work that protocols with round-by-round soundness and knowledge are secure in the quantum random oracle model and Block et al. show in their work that this applies to FRI. A lot of post-quantum signature suggestions are based on NIZKs with far worse complexity in terms of circuit sizes than the hash based SNARKs that are now becoming very practical because they do not realize that it is known that this is secure.
3. Bridge Protocol: Post Quantum BEEFY
Validators will sign BEEFY finality messages using each post-quantum secure scheme supported by the networks of interest that we are aiming to bridge. This includes the post-quantum scheme supported natively by EVM.
Bridge implementors could then use the current random sampling BEEFY protocol to prove the Polkadot state on other networks using the corresponding native scheme. While a relayer could potentially use a post-quantum secure SNARK such as FRI to present proof of the Polkadot state to the bridged chain, we expect that random sampling protocol to be far more competitive against SNARK-based design due to the size of post-quantum SNARK proofs.
4. VRF
The use of VRF in the current Polkadot protocol is being replaced by various application of a post-quantum secure Randomness beacon, as introduced in the Randomness Beacon section.
4.1 Randomness Beacon
Polkadot offers an unbiasable hashed-based post-quantum secure randomness beacon, assuming the honesty and liveness of 1/3 of validators, using techniques similar to Shamir’s secret sharing.
The randomness beacon protocol is based on a multi-instance verifiable secret sharing (VSS) where every party will act as a dealer in one VSS instance and as a recipient for all VSSes initiated by other validators. A low-degree test makes it possible to recognize honest parties and to use their shares to reconstruct the randomness contribution using Reed Solomon error correction. Subsequently, the final random value will be a linear combination of secrets obtained from all VSSes. All stages of this protocol are post-quantum secure.
4.2 Elves
We plan to replace some usage of the VRF in Elves with a randomness beacon. To significantly speed up the current (pre-quantum) Elves protocol, we will use public randomness from the randomness beacon along side the VRF.
In the post-quantum case however, we no longer need VRFs for ELVES. We replace VRF usage entirely with a combination of the randomness beacon and commit/reveal using a Merkle tree. While we hide the randomness while commiting to it in the Merkle tree, while we know it is unbiasable based on the threshold of honest validators participating in generating the random beacon.
The following subsections explain each substage of the public randomness-based Elves protocol.
4.2.1 Pre-Elves signature
We assume that we might have multiple equivocations for an RC block.
All validators sign the first RC block they import but never sign a second one.
We choose that fork for Elves if two-thirds of validators sign on the same block. We abandon the fork entirely if we never reach two-thirds of the signatures. We also hash any validator who signs multiple equivocations here.
This already has a draft RFC.
4.2.2 Tranche zero reveals
After seeing a 2/3 pre-elves signatures on a block, each validator reveals their share for a random beacon for the block. When they say enough (over 1/3) shares, they construct the random beacon result $r$. This is used as a seed for a shuffle that assigns validators to cores in tranche zero so that each core has about the same number of auditors and each validator does about the same amount of audits.
4.2.3 Later tranche reveals
We have an incoming randomness $r$ from the random beacon we use for tranch 0.
All nodes commit a random type TrancheRand([u8;32])
for each core in each slot in the epoch, so a [[TrancheRand; CORES]; SLOTS]
. These commitments consist of a Merkle root of a tree indexed by slots, whose leaves are Merkle roots of a tree over cores.
We hash the final TrancheRand
with $r$ and some auth_id
to determine the tranche for that code in that slot. This scheme requires the 2/3 pre-elves consensus signatures to be verified previously, because TrancheRand
can only be used once.
A tranche reveal consists of (slot,auth_id,merkle_proof,tranche,TrancheRand)
. These messages self-authenticate using the on-chain commitments. Theoretically, the slot component of merkle_proof
could be optimized out, but then the messages assume other messages arrive, requiring politeness care.
(In the pre-quantum setting, using VRFs as we do now vs the above scheme is a computation/bandwidth trade-off.)
4.3 Sassafras
To generate the Sassafras ticket, we concatenate the validator’s secret key with the VRF input from the Randomness Beacon. Then, we double-hash it using SNARK-friendly Poseiden hash. We prove the secret key’s validity, its belonging to the ring of validators, and the correctness of double hashing in a post-quantum secure FRI-based SNARK. The double-hashed value dictates the block producer of each slot. Other validators will verify the validity of the SNARK proof and assign slots to each ticket.
The validator includes the result of the first hash (the preimage of the second hash) in the block they will produce to prove the ticket’s ownership without the need for another expensive SNARK proof.
4.3.1 Ring VRF
The input to the VRF is the same as the current Sassafras: the random beacon output is concatenated with the ticket index.
The public key is the hash of the secret key. We would compute the VRF Output as
VRF Ouput = Hash(Hash(secret key || VRF Input) || public key)
We then prove in an FRI based SNARK with input the VRF Input and ring commitment that:
- The public key is in the ring, probably with a Merkle proof,
- The public key is the hash of the secret key and
- The output is computed as above.
We claim the ticket by revealing the preimage of the VRF output, i.e., Hash(secret key || VRF Input) || public key
, and putting this in the block’s header. Then, we use the validator signature scheme to sign it. To verify this, we need to look up the validator’s validator signature public key from the Sassafras public key.
When registering a public key, the validator must sign the Sassafras hash-based public key with their validator key.
5. Transport Layer
To turn the transport layer post-quantum secure, we require hybrid post-quantum key exchanges and certificates using on-chain certificates. Then, we use the exchanged keys to communicate using secure, audited external libraries that implement post-quantum secure TLS.
What happens next?
We are fleshing out more details about some of points above that will be rolled out in the next couple of weeks/months.
We propose to apply post-quantum changes first to Kusama same as the Zero-Knowledge tech turning Kusama into the cooler twin of Polkadot . We are preparing RFCs that will be soon posted to put the roadmap above into action. Stay tuned!
THE END
For a detailed explanation of the randomness beacon protocol, please see: https://hackmd.io/psN4gEpPRJmCGN0sFq36Mg.