Bitcoin researchers mull solutions to throughput issues potentially raised by 'post-quantum' signatures

Cloudflare researcher and MIT DCI fellow Ethan Heilman sparked a conversation on the future of Bitcoin’s cryptographic security and scalability and the need to integrate post-quantum (PQ) signatures on the Bitcoin Development Mailing List on Friday. Heilman, a prominent voice in Bitcoin’s technical community, argued that quantum computing represents a looming threat for the first and largest blockchain.

"I strongly believe Bitcoin will need to move to PQ signatures in the near future," Heilman wrote.

Despite the need for Bitcoin to adopt PQ signatures, Heilman notes the implementation could be a heavy lift due to their large size. According to BIP-360, a proposal for quantum-resistant cryptography, the smallest PQ signature and public key combination is approximately 1.5 kilobytes, which is substantially larger than current standards like ECDSA or Schnorr signatures.

In other words, implementing PQ signatures could drastically reduce Bitcoin’s transaction throughput. "Even if we discount PQ signatures and public keys so that the maximum number of transactions that can fit in a block is unchanged we still have the problem that these blocks and transactions will be an order of magnitude bigger," he writes. 

Further, Heilman raised concerns about the risk of encoding extraneous data, such as JPEGs, within discounted PQ signatures, which could undermine Bitcoin’s primary function as a payment system.

PQ signatures were initially proposed late last year in "BIP-360: QuBit - Pay to Quantum Resistant Hash," which suggested introducing a quantum-resistant payment scheme to protect Bitcoin against potential vulnerabilities posed by quantum computers.

To address these issues, Heilman proposed a cryptographic solution called Non-Interactive Transaction Compression (NTC), also known as Non-Interactive Witness Aggregation (NIWA), a system that leverages a type of post-quantum cryptographic proof using STARKs. This approach would introduce a new transaction type where miners aggregate PQ signatures into a single, compact STARK, reducing transaction sizes to as little as 76 bytes for a simple transaction.

There's an added advantage here in that utilizing STARKs could drive throughput up to 87 transactions per second, a significant boost to Bitcoin’s scalability.

The discussion comes amid a moment of reckoning for many Bitcoiners as they begin to think about the implications of quantum resistance. Microsoft’s unveiling of its Majorana 1 quantum chip in February marked a breakthrough in quantum computing while reigniting fears of "Q-Day," when quantum machines could break today’s encryption.

In a recent post, venture capitalist Nic Carter, for instance, argued that quantum represented the biggest structural risk to Bitcoin over the next five to 10 years.

Bitcoin creator Satoshi Nakamoto considered the implications of quantum computing breaking the SHA-256 encryption standard used to secure the network over a decade ago.

"I think we could come to some agreement about what the honest blockchain was before the trouble started, lock that in and continue from there with a new hash function," Satoshi wrote at the time. "If the hash breakdown came gradually, we could transition to a new hash in an orderly way," Satoshi added. "The software would be programmed to start using a new hash after a certain block number. Everyone would have to upgrade by that time. The software could save the new hash of all the old blocks to make sure a different block with the same old hash can't be used."