coindesk.com
Researchers at Blockstream, a bitcoin infrastructure firm whose engineers have contributed to the Bitcoin blockchain’s core software for more than a decade, published a proposal on Thursday for SHRINCS, a way of signing bitcoin transactions that could withstand quantum computers without sharply reducing the number of transactions that fit in a block.
Bitcoin proves ownership using digital signatures built on a branch of mathematics known as elliptic-curve cryptography. Those signatures allow someone to prove they hold the private key controlling their bitcoin without revealing the key itself.
But it is theorized that a sufficiently powerful quantum computer running Shor's algorithm — the 1994 method that lets a quantum machine unpick the maths ordinary computers would take millions of years to solve — could eventually break that protection.
Such a system could work backwards from a public key visible on the blockchain to calculate the private key, allowing an attacker to forge a signature and spend the coins.
Read more: How a quantum computer can be used to actually steal your bitcoin in '9 minutes'
A large amount of bitcoin already sits at addresses where public keys have been exposed, either because of how older addresses were constructed or because coins from them have previously been spent. This includes over 1.1 million bitcoin belonging to the network’s pseudonymous creator Satoshi Nakamoto, as CoinDesk reported in July.
Solution for the size problem
Replacing those signatures runs into a size problem. Post-quantum signatures standardized by the U.S. National Institute of Standards and Technology (NIST) can be dozens of times larger than the signatures Bitcoin uses today, and Bitcoin blocks have limited space, so larger signatures leave room for fewer transactions.
Blockstream estimated that Bitcoin could process around 6.5 transactions per second if every transaction used today's compact Schnorr signatures, falling to about 0.36 with SLH-DSA, the hash-based scheme NIST has standardized.
SHRINCS gets that back to roughly three transactions per second. Its signatures start at about 324 bytes, compared to 64 for Schnorr, growing by around 16 bytes each time a key is used, with the configuration reaching three transactions per second using 580-byte signatures.
As such, five times larger does not cost five times the space because SegWit, a 2017 upgrade, gives the part of a transaction that holds signatures a discount.
SHRINCS is built using SHA-256, the same hash function already used throughout Bitcoin, including its mining system. That means its security does not depend on introducing an entirely new underlying mathematical assumption.