BUIP197: BIPs32-39-44 HD functions for Falcon PQC - Public Bounty
Submitted by Andrew Clifford
21 April 2023
Background
Nexa utilises Schnorr signatures. This elliptic curve cryptographic (ECC) signature scheme was first proposed by Claus-Peter Schnorr in 1989 and is considered to be one of the most efficient and secure known today. Schnorr signatures are both more efficient in space and computational overhead, thereby superior to secp256k1 used by earlier Satoshi-UTXO coins such as BTC and LTC. The implementation in Nexa uses 64 bytes per signature and the computation of a Schnorr signature in NexaPoW is intended to incentivize the deployment of mining hardware which may be re-used for block validation, enhancing scalability.
Originally, Bitcoin wallets contained disassociated private/public key-pairs, known as JBOK (Just Another Bunch of Keys). This has the major drawback that no single seed can enable a wallet to be rebuilt, and all individual keys have to be backed up. A major advance for cryptocurrency was the implementation of Hierarchical Deterministic (HD) wallets which improves backup and recovery and audit (via a public master key). It makes for a much simpler and better process for users, who use seed words or numbers. This also facilitate privacy as address re-use can be avoided without backup concerns over many more keys.
BIP39 for making mnemonics to create a wallet seed
BIP32 for deriving keys from the wallet seed
BIP44 for defining a logical hierarchy for HD wallets using BIP32 keys
Nexa uses HD wallets for Schnorr key-pairs which together are effectively the state of the art in current blockchain technology. This should be sufficient long-term security as brute-forcing a single 256-bit ECC private key is considered to require a computer as large as the sun, running for longer than the lifespan of the Universe. However, this is true for classical computing only.
Motivation
At the B.U. Venice meeting I provided an overview of the quantum computing landscape and showed how QC technology is advancing rapidly in many directions. There is a clear and present risk to Elliptic Curves based upon prime factors. This is through usage of Shor’s algorithm by a QC with enough qubits to demonstrate a speed-up beyond any theoretical classical computer.
The timescale of a QC cracking ECC is highly uncertain, but many experts in the field expect this to likely be achievable by around 2030.
Predictions made in 2021, from 47 quantum experts from academia and industry. (Credit globalriskinstitute.org) In the 2 years since, sentiment has moved towards a greater risk percentage.
Notably, these assessments are before the recent advances in AI, which may well accelerate the development and design of ever more powerful QCs.
The canary in the coal-mine for QC being used to crack private keys are the blocks mined on Bitcoin in 2009, which did not use double-hashing for addresses.
Nexa uses double-hashing which makes addresses safe, however, address re-use exposes them for subsequent analysis. Also, the 2-minute average window for mempool storage provides a very narrow attack period. Nevertheless , the world’s premier cryptocurrency will need to support Post-Quantum signatures. The two best are Falcon and Dilithium.
Objective
The B.U. team has selected the NIST finalist Falcon post-quantum signature scheme for its initial implementation of PQC security in Nexa. It is true that side-channel attacks are a risk to several of the current PQC signature schemes. However, such attacks require physical proximity to the signing device and thousands of iterations to detect the EM fingerprint of floating point operations. it is anticipated that future revisions to these schemes using techniques of masking and padding, will alleviate side-channel risks. BU will upgrade its PQC according to latest NIST specifications of the scheme(s) it uses.
A search of Internet sources does not reveal any implementation of HD wallets in a PQC signature scheme.
Public Bounty
This BUIP requests the B.U. membership to approve a sum up to US$25,000 for a bounty to be paid for software which implements HD wallets using the Falcon (512 and 1024) signature scheme, conforming to BIPs 32, 39 & 44 standards. The successful contributor will require working code in a merge request to the Nexa Gitlab repository,
The presence of test scripts and a mathematical proof will be an important advantage for winning the bounty, particularly if there are several candidates. The proof will need to show that Falcon keys recursively derived are as secure as individual non-deterministic keys.
This bounty will be in the style of the B.U. bounty for OpenCL GPU mining software. In November 2022, there was an urgent and exceptional situation at the CPU/GPU transition point, Mining decentralization was successfully regained with the result of a bounty.
In the event that the bounty is not successful, the B.U. team will continue with a JBOK key-management implementation of Falcon. Ideally, the QC threat to ECC does not materialise for many years, however, at minimum, Nexa will be prepared for this eventuality, ensuring user funds security long-term.
Any success with this initiative, may well put Nexa further in the spotlight as the cryptocurrency making the running on deploying the most viable PQC implementation.