POPS-VRF implementation

[moshababo]

Proof of Work Protected Setup-Verifiable Random Function (POPS-VRF)

Replacing #146, #168, spacemeshos/go-spacemesh#3507

Motivation

Prevent miners from choosing any arbitrary VRF identity that they wish to use in the consensus protocol.

More info can be found here.

Solution

1. Impose cost on VRF identity generation (while keeping it amortised for honest users), so that a bounded adversary won't be able to "try" too many identities.

   This would help to prevent grinding on VRF identities to perform concentration attacks in Hare and ballots production. But it isn't sufficient for the beacon, where identity-grinding can be expended over a long period of time. And so:

2. Require VRF identities to be “positioned in time” by using a positioning element, providing an efficient way to be sorted according to the time it was generated after.

   This would allow to implement a mitigation of a DoS attack against the beacon, where in case of getting too many proposals (considering the total weight of ATXs), they can be sorted according to their identity's time positioning, so that oldest identities' proposals could be ignored.

   More info about the attack and the mitigation can be found here.

VRF identity workflow

1. Pick an arbitrary VRF key pair
2. Commit the VRF pub key + a positioning element to PoST initialisation
3. During PoST initialisation, check for every nonce whether it satisfies H( nonce ++ VRFpk ++ positioning ) < d
4. A successful nonce should be used in every VRF invocation

Implementation

• Add positioning ATX to commitment for PoST initialisation go-spacemesh#3556
• Amortize the cost of finding a nonce for POPS-VRF #175
• Apply VRF nonce as a prefix in every VRF invocation for a given identity. #201

Support increase of number of units

Extracted this feature into its own epic: #209

This feature is currently not supported in the ATX level. If/when it will, it should impact the VRF generation difficulty so that the probability of finding one nonce during the (now longer) PoST initialisation will remain. In the case, the previously found nonce might turn invalid, and a new nonce will need to be advertised in a non-initial ATX, which contains the updated number of units.

An implementation implication of a potential higher difficulty (and so a lower threshold) is that finding a successful nonce won't be enough, because a better/lower one might be skipped as a result of that and so:

• Verify number of PoST space units in ATXs of one identity is not increasing go-spacemesh#3759 : this circumvents the issue for genesis. An identity can only decrease its PoST size between epochs, but not increase it again (so it can keep the nonce initially advertised).
• Instead of returning the first Nonce below difficulty, return the absolute lowest post#90 : this would change the nonce finding algorithm to find the absolute lowest instead of the first below a threshold. When this is implemented a node could increase their PoST size possibly without advertising a new nonce (if the current one is already sufficient) or by only having to search the newly generated data, but not the previous.

The good news

Having the VRF identity to have an on-mesh positioning element makes the requirement to commit genesis ID to PoST initialisation (in order to prevent its re-use across different networks) redundant because the positioning element already includes the genesis ID in a path of collision-resistant hashes.

[lrettig]

This looks good to me, seems complete, and is in line with my recollection of our conversations last week. Thanks.

[tal-m]

Looks good to me.
Some minor comments:

1. The positioning ATX should be the one with the highest tick count, not the highest layer number.
2. I'm not sure which "increase in the number of units you're referring to". If it's just allowing ATXs that have more than one unit of spacetime, then this shouldn't affect the difficulty of the POPS-VRF nonce. If you mean increasing the minimum spacetime required for a valid ATX, then it should (but this is something that requires more complex handling in general, and we haven't fully worked it out).
3. Running the gpu-lib in the "PoW" mode (which also looks for nonces) has a computational cost compared to the non-PoW mode. So I don't think we want to refactor gpu-lib to always run in this mode (which would be necessary in order to find the best nonce, rather than the first).

Even more minor comments:

• The beacon already prevents grinding (or rather, makes it irrelevant) for the standard Hare and Tortoise. The POPS-VRF is used to make the beacon protocol itself resistant to concentration attacks.
• The positioning element is used to mitigate a specific kind of DoS attack on the beacon protocol.

[moshababo]

@tal-m

1. The positioning ATX should be the one with the highest tick count, not the highest layer number.

Fixed.

2. I'm not sure which "increase in the number of units you're referring to". If it's just allowing ATXs that have more than one unit of spacetime, then this shouldn't affect the difficulty of the POPS-VRF nonce. If you mean increasing the minimum spacetime required for a valid ATX, then it should (but this is something that requires more complex handling in general, and we haven't fully worked it out).

I was under the impression that higher number of spacetime units, leading to higher weight, should affect the difficulty in a way that the probability of finding one single nonce during PoST initialization would remain. Are you saying that it’s not the case, and the difficulty should be derived from the number of labels in one spacetime unit only?

3. Running the gpu-lib in the "PoW" mode (which also looks for nonces) has a computational cost compared to the non-PoW mode. So I don't think we want to refactor gpu-lib to always run in this mode (which would be necessary in order to find the best nonce, rather than the first).

Yes, finding the best nonce would require to run in this mode continuously, compared to running in it until the first nonce is found. I suggested it in order to support the possibility of needing a better nonce in the future (due to a higher number of spacetime units, if it’s to affect the difficulty, or other difficulty adjustments). Are you suggesting that it doesn't worth the computation overhead?

[tal-m]

I was under the impression that higher number of spacetime units, leading to higher weight, should affect the difficulty in a way that the probability of finding one single nonce during PoST initialization would remain. Are you saying that it’s not the case, and the difficulty should be derived from the number of labels in one spacetime unit only?

Sorry! You're totally right. The nonce difficulty does need to depend on the number of spacetime units, otherwise an adversary can amortize the grinding cost by creating a very heavy identity.

Yes, finding the best nonce would require to run in this mode continuously, compared to running in it until the first nonce is found. I suggested it in order to support the possibility of needing a better nonce in the future (due to a higher number of spacetime units, if it’s to affect the difficulty, or other difficulty adjustments). Are you suggesting that it doesn't worth the computation overhead?

If you know you're not going to need more spacetime units in the future, it's probably not worth the overhead. But it depends on how likely you think that is, and what the actual overhead of constantly running in PoW mode is (if it's tiny, it might be worth it to keep it always on).

[noamnelke]

LGTM 👌🏻