by Alex Biryukov (University of Luxembourg)
Customisable proofs of work and memory hard functions are investigated by the SnT&CSC/CryptoLUX team at University of Luxembourg.
Proofs-of-work (PoW) are at the core of most of the present day blockchains and cryptocurrencies. These are the tools that make large public distributed ledgers possible, since they replace the difficult to quantify and manage trust by hard to forge mathematical computations.
Proofs-of-work have been first proposed as a way to mitigate the spam problem and were later used by Nakamoto in the Bitcoin protocol. First blockchain proofs of work were often based on iteration of cryptographic functions (double SHA-256 in Bitcoin) until the result shows a special lucky number. Due to cryptographic properties of the function this is similar to winning a lottery and the lucky “miner” is rewarded with cryptocurrency. One of the smart decisions in Bitcoin was to make this winning chance adjustable depending on the available market of miners. However after the first cryptocurrencies started to gain popularity and value, the mining process entered into an arms race of mining hardware: from desktop computer mining, to GPU, FPGA and finally to ASIC mining.
Today Bitcoin mining is concentrated in the hands of about a dozen mining farm operators, who have access to optimised ASICs, cheap electricity (for example in China) and environments that facilitate cooling (in Scandinavia, for example). Bitcoin miners serve as validators of the transactions in the Bitcoin public ledger and it is miners who decide what will be included in the ledger. Thus mining centralisation goes against the democratic principles declared in the original Bitcoin whitepaper. Moreover current blocksize/SegWit debate demonstrates that Bitcoin is hostage to its mining conglomerates, who have made huge investments into Bitcoin “printing” hardware.
This situation is due to high parallelisation of the Bitcoin mining process: an ASIC full of SHA-256 cores is more than 30,000 times more energy efficient in Bitcoin mining than the general purpose CPU. In order to remedy this problem, memory-hard functions were proposed. Our CryptoLUX team [L1] has been working on a project to design democratic proofs of work and we have come up with two different designs. One is based on our team's memory-hard password hashing design called Argon2, which won the 2015 international password hashing competition (PHC). In [1] we propose building memory-hard, but easy to verify PoW, using Merkle hash tree on top of the Argon2 hash chain (Figure 1). Then we compute the hash of the tree root together with a nonce and apply Fiat-Shamir's method to produce queries about random locations in the Argon2 hash chain.
Figure 1: Merkle-tree based Proof-of-Work with light verification.
If attackers try to cheat and store only a fraction of the Argon2 chain, they are very likely to be caught as they will not be able to demonstrate the knowledge of the proper Argon2 chain elements with their correct paths in the Merkle tree. This scheme is called MTP and can be instantiated with any memory-hard hash function. In another work [2] we followed a completely different pass, using the well-studied generalised birthday problem. In this problem given k lists of n-bit numbers one is asked to find a set of elements, one per list, such that the XOR of all the numbers is zero. The best currently known algorithm was developed by D. Wagner, and in order to find the solution it needs to store the numbers in the lists and to constantly sort the new resulting lists (which is memory-hard). An improvement in Wagner’s algorithm would be an important breakthrough for cryptography. On the other hand, once the solution is found, its correctness is very easy to verify. We use this problem (with some important hardening modifications, e.g., algorithm binding) to build a new memory-hard proof of work function that we call Equihash. This function is now being used in one of the popular cryptocurrencies - Zcash. So far it holds the ASIC resistance promise and is mined on CPUs and GPUs.
One of the main concerns with proof-of-work based cryptocurrencies is their waste of energy. Indeed the amount of electricity being burned just for Bitcoin is approaching the energy consumption of a country like Denmark. It is a valid question whether this is a justified price to pay for the running of a trustless public ledger. While electricity can be very cheap in some places (e.g., an old hydroelectric power plant in the middle of a rural area) and green forms of energy might make electricity cheap in the future, many researchers have been wondering if it is possible to avoid the energy waste. In our team we have started to explore “greener” alternatives, such as proofs-of-stake consensus protocols, which involve economic and game-theoretic reasoning or distributed ledgers based on Byzantine fault tolerance (BFT), which have high throughput in terms of transactions but require permissioned blockchains due to trust and scalability issues.
Link:
[L1] https://www.cryptolux.org
References:
[1] Alex Biryukov, Dmitry Khovratovich: Egalitarian Computing. USENIX Security Symposium 2016: 315-326.
[2] Alex Biryukov, Dmitry Khovratovich: Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem. NDSS 2016.
Please contact:
Alex Biryukov
University of Luxembourg
+352 46 66 44 6793
