# Effects of using the leader VRF as the tiebreak VRF

## Background and Status Quo

### Basics of the Cardano leader schedule

> See [these docs](https://ouroboros-consensus.cardano.intersectmbo.org/docs/for-developers/PreflightGuide#dynamics-of-the-leader-schedule) for more details. In particular, we are ignoring [*grinding*](https://cips.cardano.org/cps/CPS-0021) for the purpose of this discussion.

In Cardano, the probability of a pool with stake $\sigma$ to be elected in a given slot is $$ \phi(\sigma) = 1 - (1-f)^\sigma $$ where $f$ is the active slot coefficient (the probability that at least one pool is elected per slot), with $f = 1/20$ on mainnet. For different slots, the probabilities to be elected are independent.

This is implemented by evaluating a VRF for every slot (depending on a private key, the epoch nonce and the slot number), which results in a (of course only almost) uniformly distributed number rational number $o$ with $0\le o\le 1$, and we then check if $o < \phi(\sigma)$.

### Multi-leader slots

We say that a slot is a *multi-leader slot* if there is more than one pool elected in that slot.
Usually, such a slot will give rise to a *slot battle*, meaning that there are at least two blocks in that slot with the same parent, such that all but at most one block will be orphaned (i.e. not end up on the historical chain).

The exact probability for a slot to be a multi-leader slot can be calculated from the stake distribution of a particular epoch. For example, for epoch 562, the probability is $\approx 0.126878\,\%$. An analytical tight upper bound, independent of the stake distribution (basically assuming that the stake is evenly distributed across infinitely many pools) is given by $f + (1-f) \log(1-f) \approx 0.127137\,\%$.

Concretely, on Cardano mainnet, this means that we expect multi-leader slots to happen roughly every 13 minutes, which means 550 multi-leader slots per epoch. Pooltool is tracking slot battles on mainnet on https://pooltool.io/networkhealth. On average, from epoch 553 to 561, it recorded 416 slot battles per epoch. It is very likely that there actually were more multi-leader slots that Pooltool didn't notice (e.g. because the pools forging the orphaned blocks diffused their block a bit late, and do not report to Pooltool directly).

### Height battles

Apart from slot battles, two honest well-configured nodes can also forge blocks in different slots with the same parent if the pool elected in the later slot did not select the block from the earlier slot in time, e.g. because the block had to go through more hops than usual, or the block is expensive to validate, or diffusion pipelining being ineffective etc.

Currently, with chain load being relatively low and diffusion pipelining working well, this seems to happen quite rarely. Pooltool reported only 14 height battles per epoch from epoch 553 to 561 on average. Based on the leader schedule, we expect $\approx 1050$ pairs of consecutive active slots, so in most cases, even in these cases, no height battle takes place.

Of course, in general, assuming any combination of very high load, adversarial activity and/or bugs, much more complicated forks that are several blocks deep might be diffused. As this has never happened so far, and such periods are (hopefully) temporary, we do not analyze them here.

### Tiebreakers[^tiebreaker-details] in the chain order

When deciding whether to adopt a new chain, we primarily consider chain length. If the chain is of equal length, we apply two *tiebreakers*. The first one is related to opcert issue numbers and is not relevant for this discussions. If that one is inconclusive (which is almost always the case), we apply the VRF tiebreaker:

> If the tip slots of the two chains differ by at most $5$[^vrf-arm], we adopt the candidate chain if its tip's header's *non-range extended* VRF value is smaller than the one of the current selection.

The non-range extended VRF value[^range-extension] (used since Praos/Babbage, in contrast to TPraos) is uncorrelated to the (range-extended) leader VRF value. Assuming the tip slot assumption is satisfied, which should be the case if both pools are honest and well-configured, this means that the decision is uniformly random.

In particular, slot/height battles are decided randomly, with any pool (no matter its size) winning half of the battles it is involved in (ignoring adversarial activity such as withholding blocks if they have a poor/strong tiebreaker).

## Proposed change

The change proposed in https://github.com/IntersectMBO/ouroboros-consensus/pull/1548 is to use a different VRF value for the VRF tiebreaker, namely, the leader VRF. This was also the case historically, namely in TPraos before Babbage.

The motivation is to improve the situation of small pools in block battles, as small pools are now more likely to win battles based on the VRF tiebreaker (as being a leader in a slot as a small pool with stake $\sigma$ already implies that the leader VRF was rather small based as it must have been smaller than the threshold $\phi(\sigma)$).

## Effect on battles

Consider two pools $P_1,P_2$ with relative stakes $\sigma_1 \le \sigma_2$.

With the current VRF tiebreaker (which is uncorrelated to the leader VRF), the probability that $P_1$ wins a battle (by having a lower tiebreaker) than $P_2$ is always $1/2$, completely independent of $\sigma_1$ and $\sigma_2$.

However, the situation changes when using the leader VRF as the VRF tiebreaker. As mentioned above, the VRF outputs for a particular slot can be modeled as independent and identically distributed random variables $O_1,O_2$ on the interval $[0,1]$. A pool $i \in \{0,1\}$ is elected if $O_i < \phi(\sigma_i)$. Now one can calculate the conditional probability (in the TPraos case) that $P_1$ has a better tiebreaker than $P_2$ if both are elected is
$$
\alpha = \operatorname{Pr}(O_1 <O_2 \mid O_1 < \phi(\sigma_1) \wedge O_2 < \phi(\sigma_2)) = 1 - \frac 12 \frac{\phi(\sigma_1)}{\phi(\sigma_2)} \approx 1 - \frac 12 \frac{\sigma_1}{\sigma_2}
$$
as $\phi(\sigma) \approx f \sigma$ for small $\sigma$.

- When $\sigma_1 = \sigma_2$, then $\alpha = 1/2$ as expected, so no advantage for either party.
- If $P_1$ has half the stake of $P_2$, then $\alpha \approx 75\,\%$.
- If $P_1$ has only a tenth of the stake of $P_2$, then $\alpha \approx 95\,\%$, so $P_1$ usually wins slot/height battles against $P_2$.

Slightly more generally, we write $$ \alpha(\sigma_1,\sigma_2) = \begin{cases} 1 - \frac{1}{2} \frac{\phi(\sigma_1)}{\phi(\sigma_2)} & \sigma_1 \le \sigma_2 \\ \frac{1}{2} \frac{\phi(\sigma_2)}{\phi(\sigma_1)} & \sigma_1 \ge \sigma_2 \end{cases} $$ for the probability that a pool with $\sigma_1$ stake wins the VRF tiebreaker battle against a pool with $\sigma_2$ stake.

## Effect on rewards

The total rewards of a pool are linear in the number of blocks produced by that pool in an epoch that ended up on the historical chain (in particular, blocks orphaned in battles are *not* counted).

### Considering only slot battles

Let us first ignore height battles, focusing on how the number of non-orphaned blocks of pools of different stakes changes under the proposed tiebreaker.

Suppose that the set of all stake pools is $\mathcal{P}$ with relative stake $\sigma_P$ for $P\in\mathcal{P}$. Let $w(P,Q)$ be the probability that the pool $P$ wins the VRF tiebreaker against the pool $Q$.

- With the currently deployed tiebreaker, we have $w(P,Q) = 1/2$ for all $P,Q$.
- With the proposed tiebreaker, we have $w(P,Q) = \alpha(\sigma_P,\sigma_Q)$ as defined above.

Consider a party $P\in\mathcal{P}$ as well as a particular slot. Then there are the following possibilities:

- $P$ is not elected. Probability $1-\phi(\sigma_P)$.
- $P$ is elected. Probability $\phi(\sigma_P)$.
- No other pool is elected. Probability $1-\phi(1-\sigma_P)$.
- At least one other pool is elected. Probability $\phi(1-\sigma_P)$.
- $P$ wins the tiebreaker battle against all other elected pools. Probability $$ \rho_P(w) = \prod_{Q\in\mathcal{P}\setminus\{P\}} \underbrace{1-\phi(\sigma_Q)}_{\text{$Q$ is not elected}} + \underbrace{\phi(\sigma_Q)}_{\text{$Q$ is elected}}\cdot \underbrace{w(P,Q)}_{\text{$P$ wins against $Q$}} \;. $$
- Otherwise, $P$ loses the tiebreaker to at least one other elected pool.

Therefore, the expected number of non-orphaned blocks for $P$, and hence, its total rewards (again, ignoring height battles) change by a factor of
$$
\begin{align*}
r_P = \frac{\rho_P(\alpha)}{\rho_P(1/2)} &= \frac{\prod_{Q\in\mathcal{P}\setminus\{P\}} 1-\phi(\sigma_Q) + \phi(\sigma_Q)\cdot \alpha(\sigma_P,\sigma_Q)}{\prod_{Q\in\mathcal{P}\setminus\{P\}} 1-\phi(\sigma_Q) + \phi(\sigma_Q)\cdot \frac12} \\
&= \prod_{Q\in\mathcal{P}\setminus\{P\}} \frac{1-(1-\alpha(\sigma_P,\sigma_Q))\phi(\sigma_Q)}{1-\frac 12\phi(\sigma_Q)}
\end{align*}
$$
compared to the status quo if we were to adopt the proposed tiebreaker.

We can get generic bounds on $r_P$ considering the extreme change from $w^{\bot}(P,Q) = 0$ to $w^{\top}(P,Q) = 1$ for all $Q$ (intuitively: $P$ previously somehow magically always lost all VRF tiebreaker battles, but is now winning all of them) and vice versa. Thus, we have
$$ r_P = \frac{\rho_P(w^\top)}{\rho_P(w^\bot)} \le \frac{\prod_{Q\in\mathcal{P}\setminus\{P\}} 1-\phi(\sigma_Q) + \phi(\sigma_Q)\cdot 1}{\prod_{Q\in\mathcal{P}\setminus\{P\}} 1-\phi(\sigma_Q) + \phi(\sigma_Q)\cdot 0} = \frac{1}{1-\phi(1-\sigma)} \le \frac{1}{1-f} $$
and dually $r_p \ge 1-f$, so $95\,\% \le r_P \le 105.263 \%$.

In reality, the changes are expected to be smaller in both directions. We plot the empirical values for the stake distribution (ignoring pools with no stake) from epoch 562 (using [this script](https://gist.github.com/amesgen/d654f8d72e8c3c28e17910d644094753)):


As expected, smaller pools benefit more from this, increasing their mean rewards. Some key numbers:

- The smallest 2560 pools (with $43\,\%$ combined stake) benefit from this change.
- The largest 205 pools (with $57\,\%$ combined stake) lose out from this change.
- The smallest pool that loses out from this change has $0.185\,\%$ stake.
- Largest relative benefit from this change: $+2.6\,\%$
- Largest relative loss from this change: $-1.4\,\%$

### Considering height battles

TODO: This requires ad-hoc assumptions on how often height battles happen, see above. In any case, height battles are *empirically* much more rare than slot battles, so the situation shouldn't change too much.

[^tiebreaker-details]: [All the low-level details](https://ouroboros-consensus.cardano.intersectmbo.org/haddocks/ouroboros-consensus-protocol/Ouroboros-Consensus-Protocol-Praos-Common.html#t:PraosChainSelectView) about the current tiebreakers, including motivation.

[^vrf-arm]: This is the usual value for the $\Delta$ network parameter, i.e. the maximum time it should take for a block to diffuse from its producer to (almost) all other pools.

[^range-extension]: See [this paper](https://eprint.iacr.org/2022/1045.pdf) for background on range extension. Briefly, it means that one can derive multiple independent VRF outputs from a single VRF output via hashing and domain separation.