Towards Post-Quantum Bitcoin Blockchain using Dilithium Signature

Bitcoin is one of the famous cryptocurrencies in the world. It is a permissionless blockchain, and all transactions are stored in a public decentralized ledger. In its security design, Bitcoin utilizes various cryptographic primitives, such as hash functions and signature schemes. In the current version of Bitcoin, the Elliptic Curve Digital Signature Algorithm (ECDSA) is employed, which is not considered post-quantum secure due to the Shor's algorithm. Since December 2016, the National Institute of Standards and Technology (NIST) initiated a process to standardize certain post-quantum cryptographic primitives, including key encapsulation mechanisms (KEMs), public key encryption (PKE), and digital signature schemes. Dilithium, a lattice-based digital signature scheme, emerged as one of the winners of this competition and is recently standardized as ML-DSA (FIPS 204). In this work, we analyze the potential replacement of the ECDSA signature, the current signature in Bitcoin, with Dilithium, which is a post-quantum digital signature. This replacement will have a significant impact on many protocols within the Bitcoin ecosystem. The ECDSA algorithms are not only utilized for transaction signing and verification but also in wallet management. Bitcoin operates on a pseudonymous system rather than complete anonymity. To enhance privacy protection, the Bitcoin community has adopted a special type of (hierarchical) deterministic wallet as outlined in Bitcoin Improvement Proposal 32 (BIP32). We have constructed deterministic wallets by first designing DilithiumRK, a signature scheme with rerandomizable keys from Dilithium. Subsequently, we conducted a thorough security analysis and successful implementation of DilithiumRK.