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.

7 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.

1 Like

Hi, @jude
thank you for recommendation
could you please explain in more details how the penalty occurs if a certain UTXO was selected for every block-commit
“flip-flop between two or more UTXOs that have similar amounts of BTC on them” seems to happen before commit…
is this still actual or fixed in latest release?

This was fixed a while ago, but if you notice that your miner’s block-commits aren’t spending each other’s UTXOs (i.e. if you notice that commit N+1 does NOT spend the miner change output from commit N as its first input), then the immediate fix will be for you to consolidate your miner UTXOs manually. You should be able to do this with most Bitcoin wallets.

i see, thank you
does it mean that every time when miner changes UTXOs it involves some sort of penalty? it will certanly happen with every re-fill as new UTXO comes in.
Do you have any recommendations how to avoid penalty at all?

@jude could you please also clarify RBF function goal. It updates tx fee almost immediately after tx was created. And is there any penalty if RBF limit reached and fee cannot be updated anymore?

Yes. This is by design – the system rewards miners who consistently try to mine over miners that only sporadically mine. The system enforces this by requiring miners to link block-commits together by UTXO chaining. However, the system currently penalizes miners whose block-commits are not mined on-time (see Reliability improvements: UTXO chaining breaks after miner commitments miss intended burnchain block · Issue #2358 · blockstack/stacks-blockchain · GitHub). This will be fixed in Stacks 2.1.

When you refill the miner, create a UTXO that is bigger than the miner’s current balance.

When create a new UTXO to refill your miner, the node will automatically consolidate the new UTXO and the currently-used UTXO on the next block-commit it produces. The validation code requires only requires that the first spent TXO in the block-commit correspond to the change address in the previous block-commit, but it makes no assumptions about subsequent spent TXOs. The mining code accommodates this by creating block-commits that consume UTXOs in newest-first, smallest-first order, so that the first UTXO spent on a refill will likely be the UTXO the block-commit validation code expects.

Your node will RBF its block-commit if the Stacks block it produces changes, which can happen as the miner discovers more and more microblocks produced by the previous miner (since confirming a longer stream will change the block hash). There’s no penalty if the RBF limit is reached. The only penalty that gets applied is if the UTXO chain between block-commits gets interrupted.

@jude thank you for taking time to explain with such a details!
probably last thing to clarify is what kind of penalty occurs in case if UTXO chaining got interrupted? it slashes the whole history of block commits and miner continue from median_burn=1, or it slashes history for 1 block-commit only so it doesn’t effect the median_burn?