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 the 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 generator of the previous block and is determined for each possible 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.
In Waves, a block’s generation signature is calculated deterministically: generationSignature(n) can be obtained by Blake2b256 hashing of the n-th block’s generation signature generationSignature(n-1) and the public key pk(n) of the new block’s generator:
generationSignature(n) = Blake2b256(generationSignature(n-1) + pk(n))
The generation signature from (n-100)-th block affects how soon the (n+1)-th block’s generator (current miner) will be able to generate a block after n-th block. As a source of randomness, generationSignature(n-100) is concatenated with a possible miner’s public key and then Blacke2b256 hashed. The first 8 bytes of the resulting 32 bytes hash are reversed and then converted to a number, which is called the account hit:
hit(n) = X(n) = <reversed first 8 bytes of> Blake2b256(generationSignature(n-100) + pk(n)),
where pk(n) is the public key of the (n + 1)-th block generator.
The hit value is used as a source of pseudo-randomness though in fact it is predictable, because the generation signature and public keys of all possible generators are publicly known.
For hit calculation, height = (n-100) is used due to the ability of multi-branching attacks: an attacker controls stake distributed over N forging accounts. Every time an honest miner forges a new block based on the current best block (parent-block), the attacker generates N hidden chains based on the same parent block. Their goal is to make alternative forks win over the main one by overtaking it. In order to reduce the effectiveness of multi-branching attack we use a pseudo-random variable from block (n - 100), but not from n-th block. This will eliminate the combinatorial effect. All the miner’s blocks at the same height have the same delay no matter how many chains they try to extend. Also, the probability of overtaking the main chain by a fork decreases with the increasing height of the main chain, since the attacker has a smaller balance.
Currently, the time for a miner to generate a block depends on the values from the header of the block that was 100 blocks ago (pseudo-random variable generation signature) and the previous block (base target and timestamp), and the generating balance of the current miner. More specifically, the time delay (the time to wait before this miner can generate a new block after the n-th block) is calculated by the following formula:
T(i,n) = Tmin + C1 log(1 – C2 log(X(i,n) / Xmax) / (b(i,n) · Λ(n))),
where
T(i,n) is the time delay that the i-th account’s has to wait after the n-th block is generated, before she is able to generate the (n + 1)-th block,
Tmin = 5000 ms,
C1, C2, are constants,
X(i,n) is the hit of the n-th block for the i-th account,
Xmax = 2^64 - 1 is the maximum signature with the length of the hit (8 bytes),
b(i,n) is the generation (forging) balance of the i-th account (generation balance) in the n-th block,
Λ(n) is the base target value of the n-th block.
More details with the explanation of our PoS formula can be found in the article Fair PoS.
Rationale
To avoid stake-grinding attacks we want to improve our generation signature calculation formula. For this purpose, we want to implement VRF - 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 hit generation unpredictable because of the need to know the private key for calculation. Only the holder of the private key can compute the hit, but anyone with the public key can verify the correctness of it.
Specification
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 signVRF function, which calculates proof for some message with the private key of the signer:
proof = signVRF(message, private key),
and verifyVRF function, which verifies proof from signVRF function with a message and the public key of the signer and returns deterministic VRF value:
VRF = verifyVRF(proof, message, public key).
Thus, now we consider that a block’s generation signature is equal to signVRF output (a VRF proof, that takes 96 bytes) for a VRF 100 blocks before, with account private key sk(n) (of the generator of the n-th block):
generationSignature(n) = signVRF(VRF(n-100), sk(n)).
For the calculation of a time delay between n-th and (n + 1)-th blocks for concrete block generator, the hit is calculated with the use of verifyVRF function as follows:
VRF(n) = verifyVRF(generationSignature(n), VRF(n-100), pk(n)).
hit(n) = <reversed first 8 bytes of> VRF(n),
where sk(n) and pk(n) are the n-th block generator’s private and public keys, respectively.
The output of signVRF function is a VRF proof, which means that the validity of the hit calculation can be checked via verifyVRF function. At the same time, its calculation requires the generator’s private key, so hitn cannot be predicted before generationSignaturen is published.
Backward Compatibility
As with the implementation of any other features, there will be a certain activation parameter for the VRF feature for voting by miners. Accordingly, the transition to the new scheme will be implemented via activation height.
The generation signature is calculated using the following algorithm:
generationSignature(n)=Blake2b256(generationSignature(n-1), pk(n)),
where pk(n) is the public key of n-th block’s generator.
Starting from activation height, the generation signature will be calculated as follows:
generationSignature(n) = signVRF(VRF(n-100), sk(n)),
where s(k) is the n-th block’s generator’s private key and the signature (VRF proof) takes 96 bytes.
Before the activation height, the time delay (the time to wait until the n-th block can be generated by a concrete miner) depends on the hit, which is calculated as
hit(n) = <reversed first 8 bytes of> SHA256(generationSignature(n-100) + pk(n)).
After activation height, the output of functions signVRF and verifyVRF will be used for defining the hit (the signVRF output takes 96 bytes, and the verifyVRF output takes 32 bytes):
VRF(n) = verifyVRF(generationSignature(n), VRF(n-100), pk(n)),
hit(n) = <reversed first 8 bytes of> VRF(n),
where sk(n) and pk(n) are the n-th block generator’s private and public keys, respectively.
If VRF proof verification fails, the program will throw an exception.
After activation height, the generation signature and hit will be calculated using the same pair of keys (public + private) as before.
The following table is to illustrate the transition to VRF. Here height=0 denotes the VRF activation height.
| Height | What is put into the block header | Hit source | Hit |
|---|---|---|---|
| -100 | GS(-100) = h(GS(-101)+pk(-100)) | GS(-200) | hit(-100) = (h(GS(-200)+pk(-100))).take(8) |
| -99 | GS(-99) = h(GS(-100)+pk(-99)) | GS(-199) | hit(-99) = (h(GS(-199)+pk(-99))).take(8) |
| … | |||
| -2 | GS(-2) = h(GS(-3)+pk(-2)) | GS(-102) | hit(-2) = (h(GS(-102)+pk(-2))).take(8) |
| -1 | GS(-1) = h(GS(-2)+pk(-1)) | GS(-101) | hit(-1) = (h(GS(-101)+pk(-1))).take(8) |
| 0 | GS(0) = signVRF(GS(-100), sk(0)) | VRF(0) = verifyVRF(GS(0), GS(-100), pk(0)) | hit(0) = VRF(0).take(8) |
| 1 | GS(1) = signVRF(GS(-99), sk(1)) | VRF(1) = verifyVRF(GS(1), GS(-99), pk(1)) | hit(1) = VRF(1).take(8) |
| 2 | GS(2) = signVRF(GS(-98), sk(2)) | VRF(2) = verifyVRF(GS(2), GS(-98), pk(2)) | hit(2) = VRF(2).take(8) |
| … | |||
| 99 | GS(99) = signVRF(GS(-1), sk(99)) | VRF(99) = verifyVRF(GS(99), GS(-1), pk(99)) | hit(99) = VRF(99).take(8) |
| 100 | GS(100) = signVRF(VRF(0), sk(100)) | VRF(100) = verifyVRF(GS(100), VRF(0), pk(100)) | hit(100) = VRF(100).take(8) |
| 101 | GS(101) = signVRF(VRF(1), sk(101)) | VRF(101) = verifyVRF(GS(101), VRF(1), pk(101)) | hit(101) = VRF(101).take(8) |
| 102 | GS(102) = signVRF(VRF(2), sk(102)) | VRF(102) = verifyVRF(GS(102), VRF(2), pk(102)) | hit(102) = VRF(102).take(8) |
| … |
To summarise, the following things will change:
| Before | After |
|---|---|
| generationSignature(n)=Blake2b256(generationSignature(n-1), pk(n)) | generationSignature(n) = signVRF(VRF(n-100), sk(n)) |
| 32 bytes | 96 bytes |
| hit(n) = <reversed first 8 bytes of> SHA256(generationSignature(n-100) + pk(n)) | hit(n) = <reversed first 8 bytes of> VRF(n), where VRF(n) = verifyVRF (generationSignature(n) , VRF(n-100) , pk(n)) |
| Public key pk and private key sk. | The same pair of keys pk, sk. |
Examples and Implementation
We have a java implementation of C-library from signal. Our implementation can be found here.