Tag Archives: blockchain

New paper: Proof-of-work consensus by quantum sampling

Our new paper on using boson-sampling as a basis for distributed blockchain consensus algorithms is available here.

Abstract: Since its advent in 2011, boson-sampling has been a preferred candidate for demonstrating quantum advantage because of its simplicity and near-term requirements compared to other quantum algorithms. We propose to use a variant, called coarse-grained boson-sampling (CGBS), as a quantum Proof-of-Work (PoW) scheme for blockchain consensus. The users perform boson-sampling using input states that depend on the current block information, and commit their samples to the network. Afterward, CGBS strategies are determined which can be used to both validate samples and to reward successful miners. By combining rewards to miners committing honest samples together with penalties to miners committing dishonest samples, a Nash equilibrium is found that incentivizes honest nodes. The scheme works for both Fock state boson sampling and Gaussian boson sampling and provides dramatic speedup and energy savings relative to computation by classical hardware.

Blockchain finance in the quantum era

This post was originally published by BTQ, which builds post-quantum infrastructure to enable the next generation of energy-efficient blockchain networks, here.

Two emerging technologies currently gaining enormous attention are blockchain-based decentralised finance, and the rapidly developing field of quantum computing, both likely to be highly transformative ones that define the future technological landscape and structure of the global economy. While seemingly disparate there is a complex interplay between these technologies via the dependence of blockchain implementations on cryptographic techniques and the future potential for quantum computers to compromise them.

The technological capability for quantum computers to undermine present-day cryptography could reasonably be anticipated to eventuate within the next couple of decades. This timescale may seem distant as it poses no immediate threat for everyday cryptographic applications like securely accessing your email. However, from a financial perspective, where assets may be valued according to their discounted future value, and contracts valued according to whether they can be enforced, such timescales are incredibly meaningful — it is commonplace for economists to refer to the yield curves of assets over multi-decade timescales. Cryptographic assets such as cryptocurrencies or smart contracts must be viewed in a similar light. If I know my cryptographic assets are going to be worthless tomorrow they likely don’t have much value today, and a smart contract isn’t very smart if it’s likely to be invalidated before maturation.

Researchers working at the intersection of these fields have already provided estimates for the timescales and resources required to compromise current blockchain implementations (https://doi.org/10.5195/ledger.2018.127), while others have speculated that the yield curves on cryptographic assets could act as market predictors for when this is likely to take place, which could in principle be securitised into instruments for forecasting or betting upon developments in quantum technology (https://doi.org/10.2139/ssrn.3777706).

While the quantum threat to cryptography may seem rather pessimistic for the future of blockchain-based FinTech it isn’t by any means the end of the road. There is significant nuance and even greater misunderstanding of the threat quantum computers pose to cryptography. It is not uncommon to hear claims to the effect that “quantum computers will one day crack all cryptographic codes”, which is simply not true — not even in theory. Quantum computers could also dominate mining of cryptocurrencies, although there the quantum advantage is far smaller making this a less urgent threat.

There are many different cryptographic primitives that we rely on. Most notably there are ones for securely encrypting data so that it can’t be read by eavesdroppers, and the ones used for authentication and providing digital signatures. In the blockchain context, it is the latter that is of importance. Specifically, blockchains validate transactions via a ‘consensus algorithm’ in which a pool of witnesses attests to the legitimacy of transactions. When a sufficient number of independent witnesses digitally sign-off on the legitimacy of a transaction it becomes irrevocably transcribed to the ledger which forms the blockchain. 

The threat here lies in the fact that if someone could falsify digital signatures they could transcribe fraudulent transactions to the blockchain by unilaterally forming consensus. Crypto-assets are at risk because quantum computers can exploit known public keys and addresses to infer the associated private keys and spend the funds freely. Indeed it is estimated that up to a third of existing Bitcoin is vulnerable to such theft. While there are safeguards to avoid this such as always using new addresses, it is almost impossible to apply them to long-term, well-known addresses such as those of major exchanges or popular smart contracts. Also, always using new addresses increases key management overhead, which may have resulted in losing many private keys over time, effectively taking the associated coins out of circulation.

The only reliable way to curb the quantum threat is to substitute the underlying cryptographic protocols with quantum-safe ones using a so-called soft fork. 

Currently, the most widely used digital signature techniques are RSA (named after the inventors) and the more efficient elliptic-curve cryptography (ECC). Unfortunately, both of these can in principle be compromised by future quantum computers able to implement an algorithm known as Shor’s algorithm. However, despite recent major advances in quantum computing, including demonstration of so-called ‘quantum supremacy’ (quantum computers able to significantly outperform the best classical computers), implementing Shor’s algorithm at the required scale remains at least a decade away. 

In parallel to this, a major field of research in the field of cryptography is ‘post-quantum cryptography’, which as the name suggests is cryptography that even quantum computers cannot break. Currently, NIST (the United States National Institute of Standards & Technology) is in the third round of a major initiative to standardise a suite of post-quantum cryptographic protocols with recommendations expected by 2024 (https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization). 

Already several highly capitalised blockchain-based cryptocurrencies claim to be quantum-secure. Yet in the absence of standards like those being pursued by NIST, it’s unclear how much trust to place in these protocols. Once standards are settled we will see rapid advancement in next-generation blockchain protocols designed to survive the onset of the quantum era. But based on the forward-valuation mantra these considerations need to be taken into account today as they affect different blockchain implementations differently and consequently will impact investment strategies.

Furthermore, the conservative nature of standards bodies like NIST directs them to focus on basic crypto such as digital signatures, while the fast-growing crypto markets demand more advanced crypto; for example, zero-knowledge rollup techniques have been rapidly gaining momentum and popularity. Most of these advanced crypto such as the popular zero-knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARKs) would be compromised by quantum computers, just like RSA and ECC. Therefore, it is crucial that we examine as soon as possible all relevant crypto, both in use and under research and development, making sure that they can survive quantum attacks in the next decades to come. This will involve substantial research and engineering efforts, without which DeFi will be, unfortunately, just like castles built on sand.

Those with the deepest understanding of this technological interplay and the ability to navigate quantum threats will be the ones who dominate future financial markets. This highlights the importance of quantum education and awareness not just within companies’ cyber teams, but at the executive level where strategic decision-making takes place.

Dr Peter Rohde is senior lecturer and ARC Future Fellow in the Centre for Quantum Software & Information at the University of Technology Sydney, Australia.

Prof Gavin Brennen is professor of physics at Macquarie University, director of the Macquarie Centre for Quantum Engineering, a chief investigator in the ARC Centre of Excellence in Engineered Quantum Systems, Australia, and a quantum information advisor to BTQ AG.