The timetable for the development of cryptographically relevant quantum computers has been significantly shortened as a result of recent developments in quantum hardware, such as Google’s Willow processor. In the context of blockchain technology, where addresses and key derivation standards like BIP32, BIP44, and SLIP-10 are the predominant infrastructure for wallet management, a quantum computer that is running Shor’s algorithm has the ability to recover any elliptic-curve private key from the corresponding public key. This poses a threat to every wallet that is currently in production. In order to migrate to post-quantum signature schemes, the public key format must be changed, and address migration must be forced across all participating networks. This presents a substantial challenge for individuals and groups involved in blockchain technology.
Keeping the existing address format completely unchanged and replacing the classical signing step with an NIZK proof of knowledge of the seed underlying the existing address is the orthogonal approach that we present. This approach reduces the security against quantum adversaries to the conjectured quantum hardness of the underlying hash functions and the soundness of the NIZK against quantum adversaries. Additionally, this approach does not require address migration or key registration. The recent report has been authored by Vincenzo Botta, Michal Pospieszalski, Emanuele Ragnoli and Justus Ranvier.
We elaborate on the finding made by Baldimtsi et al., which states that the seed is a valid zero-knowledge witness for the public key due to EdDSA’s deterministic seed-to-key mapping. Furthermore, we extend their single-level conclusion to the whole hierarchical deterministic wallet setup. Starting from BIP32-Ed25519, we replace the classical signing step with an NIZK proof that certifies knowledge of the root seed and the full derivation chain. We then prove EUF-CMA security for the scheme that is produced as a result of this. It is hypothesized that post-quantum security will be maintained because all underlying primitives are dependent solely on the difficulty of hash functions and the robustness of the NIZK against quantum adversaries.
The current systems each derive their quantum-safe witness as an accidental byproduct of a curve-specific key format, and none of them give a single derivation standard that is applicable across curves in the same way. As a result, we provide QBIP32, a novel key derivation strategy that is based on a keyed function HASH768 (instantiated using KMAC256). This approach generates the signing scalar, an explicit quantum-safe witness, and the chain code all inside a single call. QBIP32 is designed for any elliptic curve group of prime order with a fixed generator. It does not need any structural changes to be made to the derivation or proof system between curves. The same architecture is utilized for secp256k1, Ed25519, and any future curve that will be used in blockchain infrastructure. The BIP32-Ed25519 technique, on the other hand, is dependent on the Ed25519 extended key format and does not have any analogues for other curves. This universality stands in contrast to the previously mentioned approach.
After that, we tackle the efficiency issue, which is that the cost of a monolithic proof of the whole derivation chain increases in a linear fashion with the depth of the derivation. Our most important contribution is a signature scheme called ZKPoSP, which stands for Zero-Knowledge Proof of Seed Provenance. This scheme is thought to be secure against quantum adversaries because it divides the proof into two parts: a derivation proof that is generated once for each key pair and a signing proof that is generated once for each message. This reduces the cost of proving each message to a constant that is independent of the depth of the derivation. To further characterize the precise circumstances under which the derivation proof itself can be shortened to cover only the final step of the derivation rather than the entire chain beginning with the root seed, we identify the existence of a private value that is bound to the seed by a one-way function and cannot be recovered from the public key as the precise criterion. This criterion is satisfied by hardened keys, but it is not satisfied by non-hardened keys. This is a structural distinction that is shared by all schemes: BIP32 secp256k1, SLIP-10/Ed25519, BIP32-Ed25519, and QBIP32 all allow a last-step derivation proof for hardened keys, whereas non-hardened keys require a proof that reaches back to the last hardened ancestor. By taking advantage of this, we are able to demonstrate that just one hardened step and the non-hardened suffix may be shown in a single proof for BIP44 routes. This allows for the safe deletion of the root seed.
When the proofs of derivation and signature are separated, the cost of each transaction is already reduced to a constant that is independent of the depth of the derivation. This is before Q-day. Following Q-day, once all non-post-quantum signatures have been rejected by networks, the leaf scalar may be transferred to the public statement. This will eliminate all elliptic-curve scalar multiplications from the proof circuit, which will result in a significant reduction in the amount of time required for derivation proofing.
In addition to instantiating HASH768 with KMAC256 and implementing all constructions in Rust with RISC Zero serving as the NIZK backend, we also give benchmarks for monolithic proofs, ZKPoSP over entire BIP44 routes, and the post-Q-day version. The time required for signing and proving is consistent at around 12-13 seconds, while the time required for verification is consistent at approximately 9-10 milliseconds, regardless of the variation or depth.
