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 80,000 euro) 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", stated Krzysztof Pietrzak. "There exist massive amounts of unused disk space - in data centres, 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, Bram Cohen and Krzysztof 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", stated Krzysztof Pietrzak.