Towards sustainable blockchains
Professor Krzysztof Pietrzak from IST Austria and BitTorrent inventor/Chia Network CEO Bram Cohen receive EUROCRYPT 2018’s Best Paper Award for research on sustainable blockchains. Disk space could be used to secure blockchains rather than computational work, but one crucial property is still missing.
As blockchains become ever more popular and widespread, a growing concern is their sustainability: current designs, most notably the blockchain underlying the Bitcoin cryptocurrency, are secured using so-called “proofs of work”, which results in the consumption of huge amounts of computational power. This is an ecological problem and brings into question the long-term viability of such cryptocurrencies. In an ongoing collaboration, Institute of Science and Technology Austria (IST Austria) Professor Krzysztof Pietrzak and BitTorrent inventor/Chia Network CEO Bram Cohen seek to address this problem by making use of disk space rather than computational work. Research into one of the two key components of this approach—“proofs of sequential work”, also known as “verifiable delay algorithms”—received this year’s Best Paper Award at EUROCRYPT, one of the world’s top two cryptography conferences. This is the second year in a row the IST Austria cryptography group has received this award.
Bitcoin is by far the most successful digital currency in history. It owes its success to one property that distinguishes it from all previously proposed digital currencies: it is decentralized. Instead of having a central entity, all Bitcoin transactions are recorded in a public sequence of blocks known as a “blockchain”. To add a block to the blockchain, a user (or “miner”) needs to provide a “proof of work”, that is, they must solve a kind of cryptographic puzzle or challenge. As long as more than half of the computational power dedicated towards solving these puzzles is contributed by honest parties, the blockchain acts as robust, non-tamperable ledger that keeps track of all the Bitcoin transactions. Miners are incentivized by the promise of receiving Bitcoins as a reward for adding blocks, currently worth about USD 100 000 (about EUR 80 000) for every block found. This leads to a massive use of energy—by some estimates around the energy consumption of Denmark. But the problem is not only ecological, it is also economical. The high rewards required to incentivize miners will in the long run lead to either inflation or high transaction costs.
Researchers have been looking into alternatives to proofs of work for securing blockchains. “We believe the most promising approach is to use disk space” says Krzysztof Pietrzak. “There exist massive amounts of unused disk space—in data centers, but also personal laptops and the like—which could be used for mining at almost no marginal cost.”
Designing blockchains that use disk-space instead of proofs of work is a challenging problem. A recent proposal, the Chia network (chia.net), will replace proofs of work with two key components.
The first of these is “proofs of space”, which are used by miners to prove they dedicate disk-space. As those proofs are extremely cheap to generate once the dedicated space has been initialized, another component is required to enforce a dynamic, similar to what occurs in Bitcoin, where new blocks only appear every few minutes. This second component uses what is called a “proof of sequential work” or “verifiable delay algorithm”. Essentially, this is a protocol where the user can show that they have done a long sequential computation upon receiving some sort of challenge. Being sequential means that—unlike “normal” proofs of work—having enormous amounts of computational power available does not make the computation any faster. Therefore, it serves as proof that a given amount of time has elapsed since the challenge has been received.
In their award-winning paper, Cohen and Pietrzak construct the first practical and publicly verifiable proof of sequential work. Previous constructions either require the verifier to hold a secret trapdoor to verify a proof, or the prover to dedicate a massive amount of disk space to generate a proof.
Existing algorithms were extremely complicated, or the proofs could only be verified by a party that had some kind of secret trapdoor, or the prover required a massive amount of disk-space to generate a proof. Unfortunately, the new construction cannot be readily used for the main application the authors were interested in—blockchain designs—as it lacks one crucial property: “uniqueness”. In particular, a valid proof can be adapted into a different valid proof without having to repeat the sequential computation. This is a problem since the process to add a new block is like a lottery, and without the uniqueness property, an adversary could generate many different proofs of sequential work, and only announce the one that gives him the best chance of also winning this lottery in the next round. “Coming up with a design where proofs have a canonical representation without using heavy cryptographic machinery is an exciting open question”, says Pietrzak.
About IST Austria – www.ist.ac.at
The Institute of Science and Technology (IST Austria) is a PhD-granting research institution located in Klosterneuburg, 18 km from the center of Vienna, Austria. Inaugurated in 2009, the Institute is dedicated to basic research in the natural and mathematical sciences. IST Austria employs professors on a tenure-track system, postdoctoral fellows, and doctoral students. While dedicated to the principle of curiosity-driven research, the Institute owns the rights to all scientific discoveries and is committed to promote their use. The first president of IST Austria is Thomas A. Henzinger, a leading computer scientist and former professor at the University of California in Berkeley, USA, and the EPFL in Lausanne, Switzerland. The graduate school of IST Austria offers fully-funded PhD positions to highly qualified candidates with a bachelor’s or master’s degree in biology, neuroscience, mathematics, computer science, physics, and related areas.
Bram Cohen and Krzysztof Pietrzak: “Simple Proofs of Sequential Work”