Cryptography from Space

One grant from the European Research Council can fully sustain a research team in theoretical computer science for five years. But what exactly has the group of Krzysztof Pietrzak at the Institute of Science and Technology (IST) Austria explored with it? Now, after the five-year funding period, they review their scientific achievements: developing an ecologically sustainable blockchain, proving key properties of several cryptographic functions, and implementing their theoretical insights into applications.

What would you do with 1,882,244 euros? For many, this question is a mere lottery dream, but in the case of Krzysztof Pietrzak, computer science professor for cryptography at the Institute of Science and Technology Austria (IST Austria), the answer was clear. It was convincing enough for the European Research Council (ERC) to give him the money in form of a research grant. When he received the grant in 2015, he set out to mathematically prove security properties of existing algorithms and thereby broaden the basics of cryptography. “We made progress on all projects in the proposal”, Pietrzak says, “but the most exciting research appeared during the project. Especially for theoreticians, the result of an ERC funding can be quite different from what they set out to achieve at first.”

The curiosity-driven research at IST Austria has been successful in attracting the immensely competitive ERC grants, with 43 professors having been awarded 52 of them and a total of 86.5 million euros. In addition to the world-class researchers, IST Austria has a Grant Office that offers extensive support in applying for grants.The European Union’s funding program enables excellent basic research across all disciplines, and in the case of Pietrzak it financed interns, PhDs, and post-doctoral researchers to work on alternative ways to construct cryptocurrencies and on investigating other cryptographic questions.

Proof of Space

Bitcoin and other famous cryptocurrencies operate with blockchains based on proofs of work. Blocks are basically ledgers of transactions, which are then concatenated to a chain – the blockchain. It contains the full history of transactions and cannot be altered. To stop a potential adversary, adding blocks to the chain is made computationally very laborious. An honest participant is incentivized to contribute computing power by being rewarded with “coins” of the cryptocurrency for every block they add. This means that abusing the system to your advantage is prohibited by the practical impossibility that you singularly cannot own more processing power than all the honest participants together. Despite the success of bitcoin, already in 2011 Pietrzak and colleagues identified major shortcomings.

First, specialized hardware can be used to mine much more efficiently than with general processors like CPUs. This designated hardware is deployed by large players. This loophole undermines the decentralized, democratic aspiration, which assumed everyone contributes with their own small computational power.

What is more, processing consumes energy and depending on the location of the hardware, this energy is produced unsustainably causing CO₂ emissions. With currently 75 million tons of annual CO₂ emissions Bitcoin alone has almost reached a carbon footprint equal to Austria’s exacerbating the climate crisis. “And for the protocol to work, honest parties must burn constantly more energy than dishonest ones to keep up the Bitcoin system”, Pietrzak criticizes this unsustainability.

Therefore, he and his colleagues proposed an alternative proof system. It is not based on non-stop energy-intensive processing work but on free disk space. A “proof of space” leverages unused disk-space rather than computation to secure the blockchain. The space needs to be initialized once, but afterwards the creation of new cryptocoins – the so-called mining – is free, thus resulting in a much more energy-efficient cryptocurrency.

Advancing Computational Methods

Apart from applied topics like sustainable blockchains, the ERC-funded research also tackled more foundational and theoretical questions. For example, verifiable delay functions, which are functions whose computation is inherently sequential, and thus cannot be sped up using parallel computing. They have recently found utilization in randomness beacons, proofs of replication, and computational timestamping.

Another research focus were memory hard functions. These are functions which cannot be evaluated on application-specific hardware at significantly lower energy or hardware cost than on your laptop. Such functions are required to prevent brute-force attacks that decrypt and recover passwords. “Most of the projects in our group are either theoretical or aim at using theoretical results to construct new applications”, Pietrzak explains. “The sustainable cryptocurrency Chia is a prime example: It’s based on proof of space and verifiable delay functions, both developed in our group.”

From here onwards, the group aims to continue their cutting-edge research on sustainable cryptocurrencies and wants to dive into the field of security for group messaging applications. The researchers also want to revisit leakage-resilient crypto, meaning cryptographic schemes that remain secure despite tampering of the underlying hardware. “This was the topic of my first ERC”, Pietrzak remembers, “and I’m coming back to it frequently. Only very recently we found some meaningful theoretical countermeasures. Making progress on a problem you’ve been thinking on and off for over a decade, is pure scientific satisfaction.”

—

Funding information

The IST Austria projects were supported by funding from the European Research Council, ERC consolidator grant 682815 (TOCNeT).

Link to Interactive Pebbling Game: https://www.pebbling-game.at/