WEP 8: Adding VRF in Consensus

Abstract

We propose introducing a new way to calculate a block’s generation signature using VRF – Verified Random Functions.

Motivation and Purposes

We want to improve our PoS algorithm so that it can successfully resist “stake grinding” attacks that exploit the possibility of influencing block generation randomness. A possible way to use a “stake grinding” attack in our current PoS system is as follows: a pseudo-randomness that is used for choosing the next block’s generator, depends on the current block’s generator and is determined for each would-be generator. The generator can manipulate randomness by skipping their opportunity to create a block. This can be done in order to get the best next combination of block generators or generation blocks. An attacker can also reallocate their funds between accounts for the same reason.

Specification

In Waves, time for a miner (generator) to generate a block depends on values from the header of the block that was 100 blocks ago (the pseudo-randomness is calculated using the generation signature, the complexity of base target and timestamp), and the generation balance of the current miner. The formula is as follows:

Ti = Tmin + C1 log(1 - C2 log(Xn/Xmax) / (bi * Λn)),

where Ti is the block generation time for the i-th account, Tmin, C1, C2, Xmax are constants, Xn is the generation signature, bi is the proportion of generation (forging) power of the i-th account (depending on the account generation balance) and Λn is the base target value. More details with the explanation of our PoS formula can be found in the article Fair PoS.

Currently, a block’s generation signature is calculated deterministically: generationSignature(i+1) can be obtained by Blake2b256-hashing of the current block’s generation signature generationSignature(i) and the new block’s generator’s public key pk:

generationSignature(i+1) = Blake2b256(generationSignature(i), pk)

The first 8 bytes of the resulting 32 bytes hash is converted to a number, referred to as the account hit. The hit from i-th block affects how soon an (i+100)-th block’s generator (current miner) will be able to generate a block after (i+99)-th block.

We chose to implement ECVRF, which is currently undergoing standardization, by Sharon Goldberg, Moni Naor, Dimitris Papadopoulos, Leonid Reyzin, and Jan Včelák: draft-irtf-cfrg-vrf-05.

The VRF implementation contains calculateVRF function, which calculates proof for some message, and verifyVRF function, which verifies proof from calculateVRF function with a message and the public key of the signer and returns deterministic VRF value.

Thus, now we consider that a block’s generation signature is equal to calculateVRF output (a VRF proof, that takes 96 bytes) for a previous generation signature with account private key sk (of the generator of (i+1)-th block):

generationSignature(i+1) = VRFproof = calculateVRFsk(VRF(i))

The output of calculateVRF function is a VRF proof, which means that the validity of the signature can be checked. Before VRF implementation, generationSignature(i) was used in consensus for defining of a time delay between (i+99) and (i+100) blocks for concrete block generator. Now with VRF, we use the output of function verifyVRF(pki , generationSignature(i)) for defining time delay between (i+99) and (i+100) blocks for concrete block generator, this output takes 32 bytes, as old generationSignature(i+1) = Blake2b256(generationSignature(i), pk) itself.

Rationale

To avoid stake-grinding attacks we want to improve our generation signature formula. For this purpose, we want to implement VRF [A Verifiable Random Function with Short Proofs and Keys] (https://cs.nyu.edu/~dodis/ps/short-vrf.pdf) – a pseudo-random function that uses a message and the private key of an account to provide a non-interactively verifiable proof for the correctness of its output. The use of VRF makes signature generation unpredictable because of the need to know the private key for calculation. Only the holder of the private key can compute the hash, but anyone with the public key can verify the correctness of the hash.

Backward Compatibility

The transition to the new scheme will be implemented via activation height.

Before activation height, generation signature will be calculated using the old algorithm:

generationSignature(i+1)=Blake2b256(generationSignature(i), pk),

where pk – public key of (i+1) block’s generator and generationSignature(i+1) takes 32 bytes,

Starting from activation height, the generation signature will be calculated as follows:

generationSignature(i+1)=calculateVRFsk(VRF(i)),

where sk – private key of (i+1) block’s generator and a signature (VRF proof) takes 96 bytes.

After activation height generation signature will be calculated using the same pair of public + private keys as before.

val signature = if (height < = blockchainSettings.functionalitySettings.usegenerationVRFSignatureAfterHeight) {
        generationSignature(previousGeneratorSignature, account.publicKey)
} else {
        generationVRFSignature(previousVRF, account.privateKey)
}

For a definition of generation time for (i+100)-th block of concrete miner before the activation height, function hit of generationSignature(i) will be used; after activation height the result of the execution of hit for VRF will be used – verification function’s output verifyVRF(pk(i), generationSignature(i)). In the case, if verification of the signature will fail the program will throw an exception.

Examples and Implementation

We have a java implementation of C-library from signal. Our implementation can be found here.

6 Likes