Analysis of the Stacks blockchain VRF

The Stacks blockchain uses its VRF implementation for two different random processes: first, it uses the VRF value to perform miner selection using miner’s commitments to weight the selection, and secondly, in PoX, the value is used to permute over the PoX reward addresses during the rewards phase. Both of these uses require that the VRF be unbiased and indistinguishable from a uniform random function.

To check this process, node operators can add a log line to their stacks-node instances which outputs the VRF (this requires adding a new rust line and compiling from source). At Hiro Systems, we did this and performed some analysis on the first ~9300 sortitions in the Stacks blockchains.

To determine whether or not the VRF values matched a uniform random function, we bucketed the measured values into 40 buckets in the VRF’s range, and performed a Chi^2 test between the observed bucket counts and the expected bucket counts – the measured Chi^2 value was:

0.5256827539

This is a test statistic where the null hypothesis is that the observed counts are drawn from the same distribution as the expected counts, meaning that if we wanted to conclude that the measured counts were not uniform at 95% certainty, this statistic would need to be < 5%. It is far higher than that, indicating that the measured counts are not statistically differentiable from a uniform random distribution.

For reference, this is a histogram of the bucket counts:

vrf-analysis

Of course, the behavior of the VRF function does not tell the whole story of miner performance: miner selection is weighted by miner’s relative commitment scores in a given block, this score is computed by miner’s commitments over a window of blocks, and different blocks have different rewards – because of transaction fees and because if a previous bitcoin block’s sortition was skipped, because there were no valid miners in that block, then that blocks rewards are paid to the next miner. More analysis would be required to confirm and detail how all those factors ultimately impact miner selection and expected miner rewards.

6 Likes

Good to see that the VRF is operating as expected. It’d be great to see any further analysis on miner selection!

1 Like

I believe I have found one possible reason why a miner that has 100% uptime may not be getting duly considered by the sortition algorithm. This is because the miner must always consolidate their UTXOs when they refill their address. If they don’t, then the miner code will flip-flop between two or more UTXOs that have similar amounts of BTC on them, because the miner chooses whichever UTXO(s) are the biggest when creating a block-commit transaction.

If you are a miner, you should always re-consolidate your UTXOs when you re-fill your miner. The sortition algorithm isn’t biased; it’s instead penalizing miners who don’t UTXO-chain their block-commits.