# VRF-based mining
This idea is co-developed by Runchao Han (runchao.han@monash.edu) and Haoyu Lin (chris.haoyul@gmail.com).
We introduce VRF-based mining, a surprisingly simple and effective way of making pooled mining impossible. Instead of using hash functions, we use Verifiable Random Functions (VRFs) for proof-of-work-based consensus. As VRF binds the authorship with hashes, a pool operator should reveal his private key to outsource the mining process to miners, and miners can easily steal cryptocurrency in the pool operator’s wallet anonymously.
## Verifiable Random Functions
We start from recalling the definition of VRFs. A VRF is a tuple of functions $(\mathsf{VRFKeyGen}, \mathsf{VRFHash}, \mathsf{VRFProve}, \mathsf{VRFVerify})$:
- $(sk, pk) \gets \mathsf{VRFKeyGen}(1^{\lambda})$: On input a security parameter $1^\lambda$, outputs the secret/public key pair $(sk, pk)$.
- $\beta \gets \mathsf{VRFHash}(sk, \alpha)$: On input $sk$ and an arbitrary-length string $\alpha$, outputs a fixed-length hash $\beta$.
- $\pi \gets \mathsf{VRFProve}(sk, \alpha)$: On input $sk$ and $\alpha$, outputs the proof $\pi$ for $\beta$.
- $\{0, 1\} \gets \mathsf{VRFVerify}(pk, \alpha, \beta, \pi)$: On input $pk$, $\alpha$, $\beta$, $\pi$, outputs the verification result 0 or 1.
Please find the standardised Elliptic-curve-based VRF (EC-VRF) construction in Appendix.
## VRF-based mining
Instead of using a hash function, VRF-based mining uses a VRF to produce hashes that satisfy the difficulty requirement. Different from hash functions, VRF takes both an input and a secret key to produce a hash. In addition, the owner of this secret key can produce a proof proving that the hash is generated by himself. Thus, to outsource the mining process, the pool operator should show his secret key to miners. However, with the secret key, any miner in the mining pool can steal all coins of the pool operator.
Cryptocurrency mining consists of two components, namely mining blocks and verifying blocks. We call the process of mining a block $\mathsf{Work}$, and the process of verifying a block $\mathsf{Verify}$.
### Work
Miners run $\mathsf{Work}$ to mine new blocks. More specifically, a miner - with his private key $sk$ the block template (a complete block without nonce) $t$ - keeps searching for a nonce $n$ that can make the (VRF) hash $h$ of the block $blk$ to meet the difficulty requirement $Target$. Once finding a valid $n$, the miner produces the proof $\pi$ of $h$, and appends $blk$ (with $n$), $h$ and $\pi$ to the blockchain.
Note that the protocol should enforce the bindding between the mining reward and $sk$. In particular, the address in the coinbase transaction in $t$ should be the one associated with $sk$.
![](https://i.imgur.com/R2WEbz7.png)
### Verify
Upon incoming blocks, miners run $\mathsf{Verify}$ to verify their validity. While other verifications are the same as in hash-based mining, $\mathsf{Verify}$ in VRF-based mining should additionally run $\mathsf{VRFVerify}(\cdot)$ to verify 1) whether $h$ is produced by the owner of $sk$, and 2) whether $h$ is a valid output of $\mathsf{VRFHash}(sk, blk)$.
![](https://i.imgur.com/5LiLRQ5.png)
### Block structure
Different from hash-based mining, in VRF-based mining a block should additionally attach $h$ and $\pi$, but does not need the signature of a block. Other miners without knowing $sk$ cannot produce $h$, but can use $\pi$ to verify $h$ is generated by someone knowing $sk$. Through proving the authorship of $h$, $\pi$ also proves the authorship of the block. Thus, miners only need to sign $h$, but do not need to sign blocks.
## Non-outsourceability analysis
[Miller et al.](http://soc1024.ece.illinois.edu/nonoutsourceable_full.pdf) first formalises cryptocurrency mining as non-outsourceable scratch-off puzzles, and formally defines non-outsourceability.
In particular, they define two levels of non-outsourceability, namely **Weak non-outsourceability** and **Strong non-outsourceability**. Informally, the weak one means that "If the pool operator outsources the mining process, miners can always steal the reward of mining". The strong one means that, in addition to the weak one, the pool operator cannot link the stolen mining reward with the miner who steals it.
VRF-based mining achieves **Strong non-outsourceability**. Once the miner has the knowledge of the pool operator's private key, he can steal all coins held by that private key. The stealing can be anonymised by lots of tools, such as coin mixer and stealth address.
## Instantiating VRF
In order to implement VRF-based mining, one needs to first instantiate the VRF. EC-VRF in [draft-goldbe-vrf](https://tools.ietf.org/id/draft-goldbe-vrf-01.html) has four configurable components, including the elliptic curve and three hash functions. Three hash functions are:
- $H_{1}(\cdot)$ mapping an arbitrary-length string into an elliptic curve element
- $H_{2}(\cdot)$ mapping an elliptic curve element into a fixed-length string
- $H_{3}(\cdot)$ mapping an arbitrary-length string into a fixed-length string
### Elliptic curve
As neither blockchains and VRF limits the choice of elliptic curves, any elliptic curve can be adapted. Among prominent elliptic curves, Ed25519 can be a promising choice. First, Ed25519 works on a prime field with the prime number $2^{255} - 19$, which provides sufficient enumeration space for VRF. Second, Ed25519 supports EdDSA, a fast and secure digital signature algorithm. Last, Ed25519 is compatible with existing blockchains: numerous blockchains and projects using VRF adapt Curve25519 as their underlying elliptic curve.
### Hashing a string to an elliptic curve point $H_{1}(\cdot)$
$H_{1}(\cdot)$ is a hash-to-curve function, which should prevent distinguishing behaviours: adversaries cannot learn any pattern of the input from its hash. In addition, the hash-to-curve function used in VRF should be deterministic, otherwise the hash will be unreproducible.
[Hashing to Elliptic Curves](https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-01) specifies several hash-to-curve functions that fit into different elliptic curves and satisfy our requirements: Icart Method, Shallue-Woestijne-Ulas Method, Simplified SWU Method and Elligator2. Within these hash-to-curve functions, Elligator2 is the recommended one for Curve25519.
### Hashing an elliptic curve point to a string $H_{2}(\cdot)$
$H_{2}(\cdot)$ hashes an elliptic curve point to a fixed-length string. It can be divided to two steps: 1) encoding an elliptic curve point to a string, and 2) hashing the string using a normal hash function. The encoding step can be bidirectional and unencrypted, so can be done simply by converting a big integer to a string. The hashing step should be cryptographically secure, so can adapt any existing cryptographically secure hash functions.
### Normal hash function $H_{3}(\cdot)$
$H_{3}(\cdot)$ is only used in $\mathsf{VRFProve}$ (proving the authorship of hashes) and $\mathsf{VRFVerify}$ (verifying the authorship of hashes). The overhead of proving and verification should be minimised, so cryptographically secure hash functions that are designed to be fast (such as Keccak and BLAKE) are suitable for $H_{3}(\cdot)$.
### Memory-hard mining
For ASIC-resistant cryptocurrencies using memory-hard hash functions (e.g., Ethereum and Monero), we can make $H_1(\cdot)$ or hash functions in $H_{2}(\cdot)$ memory-hard. This can be achieved by coupling them with one or multiple sequential memory-hard hash functions (such as Ethash and CryptoNight).
### Preventing partial outsourcing
The pool operator may have opportunity to outsource a part of mining. The non-outsourceability is from $\gamma = h^{sk}$, which requires the knowledge of the pool operator's secret key $sk$. The pool operator can outsource the pre-processing ($h = H_1(\alpha)$) by distributing different $\alpha$s to miners, and can also outsource the post-processing $\beta = H_2(\gamma)$ by distributing different $\gamma$ to miners.
However, this can be extremely I/O intensive for both the pool operator and miners. For each different block template the pool operator should have a round-trip communication with a miner.
In order to make outsourcing even I/O intensive, we recommend to make $H_1(\alpha)$ more time-consuming than $H_2(\gamma)$. This is because outsourcing the post-processing is less I/O intensive than outsourcing the pre-processing for the pool operator. Once having $\beta$ (the result of $H_2(\gamma)$), the miner can know whether $\beta$ satisfies the difficulty or not, and can only send valid $\beta$s to the pool operator. But, if we make pre-processing more computationally intensive than post-processing, outsourcing the post-processing will no longer be profitable. This can be achieved by making $H_1(\alpha)$ more time-consuming than $H_2(\gamma)$.
## Possible problems and solutions
While eliminating mining pools can contribute to decentralisation, it will also introduce three problems, namely the high reward variance, the high orphan rate, and the potential secret key leakage in memory.
### High reward variance
There are several proposals on minimising the reward variance. [Miller et al.](http://soc1024.ece.illinois.edu/nonoutsourceable_full.pdf) proposes the Multi-tier reward scheme, where the mining difficulty is divided into different levels, and miners can mine blocks satisfying different difficulty levels arbitrarily. The multi-tier reward scheme distributes the mining reward in a fine-grained way so lowers the reward variance. [StrongChain](https://www.usenix.org/system/files/sec19-szalachowski.pdf) introduces the notion of Collaborative PoW, where miners are incentivised to mine blocks together and the mining reward is distributed in proportion to miners' contributions. [Prism](https://eprint.iacr.org/2018/992.pdf) decouples the block to core blocks and transaction blocks. Core blocks construct the blockchain and only contain metadata, while transaction blocks are anchored on core blocks and contain confirmed transactions. Mining core blocks and transaction blocks is different in terms of difficulty, and miners can mine core blocks and transaction blocks simultaneously. In this way, miners are also rewarded more stably.
Another approach is to increase the speed of mining blocks.With more blocks mined in a time unit, the mining reward can also be more stable. For example, proposals on blockchain scalability such as sharding (e.g., [Monoxide](https://www.usenix.org/system/files/nsdi19-wang-jiaping.pdf)) and DAG (e.g., [Conflux](https://arxiv.org/abs/1805.03870)) can stabilise the mining reward variance, although they are not designed for it.
### High orphan rate
There are two approaches to minimise the orphan rate. The first is to reward orphan blocks instead of discarding them. For example, ETH's GHOST protocol. The second is to accelerate the block propagation to let miners know the latest block as soon as possible. [BIP-152](https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki) introduces the block relay protocol. Following BIP-152, several proposals on accelerating the block propagation have been proposed, such as [Grephene](https://people.cs.umass.edu/~gbiss/graphene.sigcomm.pdf), [Bloxroute](https://bloxroute.com/wp-content/uploads/2018/03/bloXroute-whitepaper.pdf) and [Erlay](https://arxiv.org/abs/1905.10518).
### Secret key leakage in memory
Different from hash-based mining, in VRF-based mining the secret key is kept in plaintext in memory all the time, as mining requires the secret key. This gives opportunity for adversaries to steal the secret key from the memory. For instance, the mining software has a bug, and the hacker can exploit this bug (even without logging in to the mining machine) to access the memory space of the mining software. In this way, the hacker can easily steal the secret key.
Unfortunately, keeping the secret key in memory is inevitable for achieving the non-outsourceability guarantee that outsourcing leads to secret key leakage. To achieve such non-outsourceability guarantee, the secret key should be combined to the mining process. As long as the mining is continuous and endless, the process should keep the plaintext secret key in memory. Not only VRF-based mining, but also all protocols combining the secret key to mining suffer from this issue.
To protect secret keys in memory, Oblivious RAM (ORAM) is a promising primitive. ORAM allows CPUs to access data in memory while the data in memory is encrypted and the access pattern is hidden. In addition, one can load secret keys into software or hardware encalves so that reading secret keys is protected. Note that the encalves are unnecessary to be general-purpose. Moreover, the process of the mining software can proactively destroy itself once detecting anomalous memory access attempts.
## Related work
We briefly review related research on preventing mining pools, and compare them with VRF-based mining.
### Mining protocols
A simple approach of preventing pooled mining is to apply the difficulty parameter to blocks' signatures rather than their hashes. However, this requires deterministic signature algorithms, while commonly used digital signatures (e.g., ECDSA, EdDSA) rely on randomisation. If the signature is non-deterministic, the miner can search for a randomisation parameter (e.g., $k$ in ECDSA) rather than a nonce to meet the difficulty parameter. If the mining algorithm in PoW is slower than signing blocks (especially for memory-hard mining algorithms), the mining algorithm will be rendered useless.
There are [some techniques](https://tools.ietf.org/html/rfc6979) to make DSA and ECDSA deterministic. However, these techniques suffer from several attacks, such as [Fault Attacks](https://eprint.iacr.org/2017/1014.pdf) and [Differential Attacks](https://eprint.iacr.org/2017/975.pdf).
[2P-PoW](http://hackingdistributed.com/2014/06/18/how-to-disincentivize-large-bitcoin-mining-pools/) is a mining protocol that discourages pooled mining. In 2P-PoW, there are two phases, and each phase has a difficulty parameter. A miner should find a nonce that makes the block to pass two phases: 1) the Sha256d hash of the block meets the first difficulty, 2) the Sha256 hash of the signature of the block meets the second difficulty. As the second requirement requires the private key, pool operators cannot outsource the second phase.
The first phase of 2P-PoW is outsourceable. In addition, 2P-PoW also requires deterministic signature algorithms. If the signature is non-deterministic, given a nonce meeting the first difficulty, the pool operator can search for a randomisation parameter to meet the second difficulty. Moreover, how to adjust two difficulties still remains unknown and requires some simulations.
[Miller et al.](http://soc1024.ece.illinois.edu/nonoutsourceable_full.pdf) first formalises cryptocurrency mining as non-outsourceable scratch-off puzzles, and formally defines non-outsourceability. In their construction, the block template is not binded with the coinbase tx, so miners can first find a valid nonce then bind the nonce with his address and take the reward. Compared to the non-outsourceable scratch-off puzzle, our VRF-based mining achieves stronger non-outsourceability (as the miner can steal **all** coins rather than just mining reward), and is more efficient and simpler to implement.
### Decentralised mining pools
Decentralised mining pool is a type of mining pool that works in a decentralised way. More specifically, miners mine in the name of themselves rather than the pool operator, but they share reward in a fine-grained way. In this way, miners are rewarded stably while mining power is not aggregated to pool operators.
[P2Pool](http://p2pool.in/) is a decentralised mining pool for Bitcoin. P2Pool runs a share-chain among all miners in the pool, and the share-chain includes shares submitted to the pool in sequence. During mining, the coinbase transaction records the number of shares submitted by each miner, and distributes the mining reward according to miners’ contribution. In this way, once mining a Bitcoin block, the coinbase transaction will become valid, and miners will be rewarded according to their contribution. However, P2Pool suffers from several challenges. First, handling the difficulty of mining shares in P2Pool is hard. If the difficulty is high, a miner’s reward will still be volatile. If the difficulty is low, there will be numerous low-difficulty shares, which introduces huge overhead on broadcasting shares or even spamming attacks. Second, frequent share submissions amplifies the influence of network latency which leads to high orphan share rate. Last, P2Pool is vulnerable to temporary dishonest majority.
[SmartPool](https://loiluu.com/papers/smartpool.pdf) is another decentralised mining pool, which uses a smart contract to replace the centralised pool operator. As relying on smart contracts, SmartPool cannot work on blockchains without smart contracts. In addition, as blockchains achieve limited throughput, transaction processing might be congested and mining reward might be delayed, especially when a large number of miners participate in the SmartPool. Moreover, as the SmartPool smart contract should verify the validity of blocks, miners should submit the whole block (with transactions) to the SmartPool. Verifying blocks introduces significant overhead on computing (so expensive transaction fees), and storing blocks in the SmartPool smart contract also introduces significant overhead on storing the blockchain.
[BetterHash](https://www.betterhash.net/) is another decentralised mining protocol, which has been integrated into [Stratum V2](https://stratumprotocol.org/), the next generation of the Stratum pooled mining protocol. In BetterHash, the block operator allows miners to choose transactions and construct blocks in his name, rather than constructing block templates by himself. Thus, BetterHash only contributes to the decentralisation of constructing blocks, but does not contribute to the decentralisation of mining power.
## Acknowledgement
We thank Cheng Wang, Omer Shlomovits and Jiangshan Yu and John Trump for their valuable feedback.
## Appendix
Here is the Elliptic-curve-based VRF (EC-VRF) construction standardised in [draft-goldbe-vrf](https://tools.ietf.org/id/draft-goldbe-vrf-01.html)
- Preliminaries
- $G$ is a cyclic group of prime order $q$ with generator $g$.
- $H_1(\cdot)$ hashes an arbitrary-length string into an element in $G$.
- $H_2(\cdot)$ hashes an element in $G$ into a fixed-length string.
- $H_3(\cdot)$ hashes an arbitrary-length string into a fixed-length string.
- $\mathsf{random}([x, y])$ uniformly and randomly picks a number in $[x, y]$.
- $(sk, pk) \gets \mathsf{VRFKeyGen}(1^{\lambda})$
- $sk = \mathsf{random}([0, q-1])$
- $pk = g^{sk}$
- Return $(sk, pk)$
- $\beta \gets \mathsf{VRFHash}(sk, \alpha)$
- $h = H_{1}(\alpha)$
- $\gamma = h^{sk}$
- $\beta = H_{2}(\gamma)$
- Return $\beta$
- $\pi \gets \mathsf{VRFProve}(sk, \alpha)$
- $h = H_{1}(\alpha)$
- $\gamma = h^{sk}$
- $k = \mathsf{random}([0, q-1])$
- $c = H_{3}(g, h, pk, h^{sk}, g^{k}, h^{k})$
- $s = k - c \cdot sk \pmod{q}$
- $\pi = (\gamma, c, s)$
- Return $\pi$
- $\{0, 1\} \gets \mathsf{VRFVerify}(pk, \alpha, \beta, \pi)$
- $u = pk^{c} \cdot g^{s}$
- $h = H_{1}(\alpha)$
- Return 0 if $\gamma \notin G$
- $v = \gamma^{c} \cdot h^{s}$
- Return 0 if $c \neq H_{3}(g, h, pk, \gamma, u, v)$
- Return 1