# Number of Signatures needed for Sampling Light client of BEEFY

This document considers the number of random validators's signatures that must be included in the final step of the random sampling light client of BEEFY, the protocol described [here](https://hackmd.io/UsPqx0IATX6yFSxcBLIhHQ), to be secure.

[This analysis](https://hackmd.io/c6STzrvfQGyN2P2rVmTmoA) shows using $k$ random validator's signatures gives a probability of at most $2^{-k}$ of an adversary convincing the verifier of a false claim. However this considers a one-shot protocol with unbiased randomness.

The goal is to make an attack on the BEEFY client of Polkadot more expensive than all DOT tokens. Note that this many tokens can be used for other attacks on Polkadot, such as attacking GRANDPA or BEEFY directly by choosing 1/3 of the validators or attacking parachains. For the latter, we only obtain that attacks are expensive in expectation, and we will aim for something similar here. Then we can argue that any bridge using BEEFY is not a weak point. This also holds if BEEFY is used for many bridges, since an attack on Polkadot or a bridge hub parachain could be used to attack several bridges.

The first BEEFY transaction contains a signature by one validator. When slashing for BEEFY is appropriately implemented, it should be possible to report and slash any validator whose signature appears on another chain. Ideally relayers for the bridge would automatically make such a report in a timely fashion.

If the protocol was one-shot and unbiased, we could set

$$k = \lceil \log_2 \frac{\text{total DOT supply}}{\text{minimum amount slashed}} \rceil $$

However, there are a number of things that can bias the number of needed signatures and when we need to increase the number of checkers to stay safe.

1. The concurrency [issue](https://hackmd.io/wsVcL0tZQA-Ks3b5KJilFQ). The problem is that a single validator's signature may be used many times before they are slashed.
2. If an Randao attack happens which will impact which validators signature they ask for. The Randao attack works as follows. The adversary waits until it has the possiblity to create or not, many blocks at the end of an epoch. This will give it a chance to bias epoch+2 and consequently epoch+4.
We want the waiting time to be as long as possible to make the attack expensive. The number of signatures needed since they impact the cost of the Randao attack:

All these factors gives a formula for an upper bound for $k$ which is secure that looks something like:

\begin{align*}
k = \lceil \log_2 & \frac{\text{total DOT supply}}{\text{minimum amount slashed}} \times \\
& \text{number of slots the RanDAO value could come form} \times \\
& \text{expected number of choices under a RanDAO attack per slot} \times \\
& \text{the number of times a validators signature can be reused in claims}
\rceil
\end{align*}

We will look at these parameters in the following sections. For the last number, we will aim for a variable probability and add $1+2\lceil \log_2 (\text{no. of initial claims this session signed by the same validator}) \rceil$.

Let's assume 1000 validators as on Kusama and 25% slashing. Then using recommendations from below, we obtain:

\begin{align*}
k = \lceil \log_2 & 2.5 \times 1000 \times 4 \times \\
& 78 \times \\
& 172.8 \rceil\\
& + 1+2\lceil \log_2 (\text{no. of initial claims this session signed by the same validator}) \rceil \\
&= 29+2\lceil \log_2 (\text{no. of initial claims this session signed by the same validator}) \rceil
\end{align*}

## Estimating the ratio of the total DOTs to what could be slashed

We need to estimate
$\frac{\text{Total issuance}}{\text{Dots that can be slashed for backing of the least backed validator}}$

At the current time, we have:

| Network | Total issuance | Stake backing least backed validator | Ratio | Number of validators | Ratio per validator|
| -------------------------------| ------------------------ | ------------------------------------ | ------ | ------------ |--|
| Kusama (block no. 19,422,555) | 13.9492 MKSM | 6,750 KSM | $2066.54$ | 1000 | 2.066 |
| Polkadot (block no. 17,033,647) | $1.3496\times 10^9$ DOT | $1.9567\times 10^6$ DOT | $689.73$ | 297 |2.3198|

Based on this numbers we would suggest to include a factor of 2.5 times the number of validators in the formula above to be safe, assuming that we slash 100% for signing the wrong payload in BEEFY. We expect the number of validators in Kusama/Polkadot to change in the future, but expect the *ratio per validator* to remain the same. Hence we suggest using *ratio per validator* $\times$ *Validator Set*, keeping it parametric to the validator set size which the light client is aware of. If we wanted to slash e.g. 3%, then we'd need to increase this by $1/0.03$ to get the correct value for $\frac{\text{total DOT supply}}{\text{minimum amount slashed}}$. We also suggest keeping the number of checks paramteric w.r.t the slashing rate.

## The concurrency issue

In https://hackmd.io/wsVcL0tZQA-Ks3b5KJilFQ , we reccommended adding $1+2\lceil \log_2 (\text{no. of relayers this session}) \rceil$ checkers, assuming we can make each relayer not use the same validator signature. Alternatives include adding $1+2\lceil \log_2 (\text{no. of initial claims this session}) \rceil$, which requires only counting the number of initial claims. Or we can keep track of the number of times each validator has a signature used in the inital claim, and then increase by $1+2\lceil \log_2 (\text{no. of initial claims this session signed by the same validator}) \rceil$.

Currently it appears that only having a static increase in the number of validators, not tracking anything in the session, would require not only a decent increase, but also new security assumptions.

## Randao Biasability

We did some analysis in https://github.com/w3f/consensus/blob/master/random/randao_analysis.ipynb .

Our analysis of Randao builds on the one the one in [this paper](https://drops.dagstuhl.de/storage/00lipics/lipics-vol316-aft2024/LIPIcs.AFT.2024.10/LIPIcs.AFT.2024.10.pdf), which in turn bult on that in [this chapter](https://eth2book.info/capella/part2/building_blocks/randomness/#randao-biasability). Our analysis will need to reflect our specific objective. While the analysis in [the paper] considered an attacker who wants to maximise their share of rewards, our attacker wants to bias an interactive protocol that uses on-chain randomness.

We can interpret the protocol in [figure 1] as a 3 round interactive proof protocol , so the prover sends an initial commit message, the verifier responds with a challenge, and the prover responds to that challenge. Abstracting, for this section, we consider any such protocl. The protocol would work as a public coin protocol where the verfier challenge is chosen uniformly at random from some challenge set $S_{challenge}$, however in our protocol instantiated on a blockchain, the verifier is a complicated interactive protocol, in which some participants are adversarial, which produces biasable randomness. We can quantify this bias as follows

**Definition**: We say that a verifier protocol $V$ for a 3 round interactive proof protocol is $\mu$-biasable if for any adversary, for any challenge $c \in S_{challenge}$, $\Pr[\text{V produces challenge }c] \leq \mu/|S_{challenge}|$.

We consider implementing the interactive protocol on Ethereum as follows. The prover sends a transaction including the commit message to a smart contract which stores the message and the block number $n_{initial}$ in which the transaction in included. Then the verifier challenge is defined as the chain's RANDAO randomness from some block with number $n_{challenge}$ in the range $n_{initial}+b_{delay} \leq n_{challenge} \leq n_{initial}+b_{delay}+b_{sample choice}$ for some parameters $b_{delay},b_{sample choice}$. A smart contract call made by the prover included in block $n_{challenge}+1$ records this challenge. Then the prover can send a final transaction including the response to the smart contract, which verifies accoring to the interactive protocol. We note that smart contracts on Ethereum have access to the RANDAO randomness from the previous block as well as the block number, but unfortunately have no access to the slot number of the block [maybe cite for definition of slot number].

We assume that more than $2/3$ of validators are honest, and that the remainder are adversarial. We assume that the adverary cannot forge signatures or predict honest validator's randomness controbutions (for Ethereum, these are both covered by the unforgability of BLS signatures). Now the question that the rest of this section answers is which $\mu$ can we show that the interactive protcol outlined above has a $\mu$-biasable verifier protocol under these assumptions.

As the previous analyses[cn], though they don't make it explicit, we assume that an attacker is unable to prevent an honest block producer's block from being included in the chain. They might feasibly be able to do so by using the attack on LMD Casper outlined in https://arxiv.org/pdf/2102.02247.pdf and https://arxiv.org/pdf/2110.10086.pdf or by Dos attacking the block producers whose identity is public.

1. The attacks on LMD Casper considered in https://arxiv.org/pdf/2102.02247.pdf and https://arxiv.org/pdf/2110.10086.pdf . In particular the one block private fork attack allows a malicious block producer to skip an honest block producer in the next slot. This really complicates the analysis, making it much more combinatoric.
2. The fact that Ethereum block producers are publicly known well in advance makes them a target for DoS attacks, potentially causing them to miss their slot. If this is consistently possible, then Ethereum is censorable, the randao randomness is arbitrarily biasable and the sync committee is useless.

These issues will eventually be solved: 2 will be fixed by some form of mostly secret leader election. 1 would be solved by adopting the Goldfish or RLMD protocols. We ignore these attacks.

As the previous analyses, the key quantity is the tail length, the number $T$ of slots with adversarial block producers in sequence before the randao value is used at the end of the epoch or the challenge block for BEEFY. The last honest block producer before this point produces a block that must be included, whose contribution to the randomness is random and unknown in advance. The adversarial contributions the randomness are fixed by this point, so the adversary has the choice of publishing a block or not. This gives them $2^m$ choices of randomness.

The randao randomness at the end of epoch $n$ is used to determine the block producers of epoch $n+2$. We can imagine that the adversary wants to maximise the numnber of adversarial slots at the end of epoch $n+2$ to get control over the randonness in epoch $n+4$ etc. If they choose to do this, we can construct a Markov chain, where each state is the number of adversarial blocks at the end of this epoch. The next state is the number of adversarial blocks at the end of the epoch after next. (So odd and even numbered epochs are mostly indepedent.) In terms used by [paper], this is the Markov chain obtained by using the strategy TAIL-MAX(TODO: font) into the MDP $M_G'$.

If the adversray controls $1/3$ of the validator set and controls $m$ slots at the end of the current epoch then under this attack, the distribution of the number of slots they control at the end of the next epoch is the maximum of $2^m$ geometric distributions (the kind that start at 0) with parameter $2/3$.

The stationary distribution of this Markov chain is the distribution of the number of adversarial slots at the end of the peoch under continous attack where the adversary tries to maximise this.

We want to consider sampling randomness 4 epochs after some trigger happens. Now an attacker could wasit until the current epoch has many adversarial validators at the end, before causing the trigger to happen. Then 4 epochs, later, the current epoch may still be somewhate biasable, allowing the adversary to have a more than usual chance to get many adversarial blocks before the trigger block.

How many slots at the end of an epoch is it reasonable to wait for? Well from https://github.com/w3f/consensus/blob/master/random/randao_analysis.ipynb , we obtained that, under the stationary distribution, i.e. under the continuous attack above, tail lengths of 15,16,17 occur in expectation once in every 8.03,24.1 and 72.3 years respectively. It seems rather expensive in terms of missed block rewards to carry out the attack for that long. Without the continuous attack, tail lengths 15,16,17 only occur in expectation every 26.2,78.6,235.8 years respectively. So we went with 16 as the maximum feasible tail length for the adversary. Hopefully this is conservative enough for 1. not to be a problem.

If there is a tail length of 16 in the current epoch $n$ and the adversary makes the initial transaction now, then the distribution of the number of slots before a slot in epoch $n+4$ is given by the distribution of the Markov chain two transitions from the state correspoding to tail length 16. The expectation of $2^X$ with $X$ sampled from this distribution is the expected number of choices the adversary will have. We obtained an expected number of 172.8 choices from this.

We therefore advise adding $\lceil \log_2 172.8 \rceil = 8$ samples to deal with the RanDAO biasability.

## How many choices of slot number does the adversary have?

In the BEEFY protocol as implemented, when the block number which is the initial block number + 128 is reached, the relayer needs to send a transaction that samples the previous RANDAO random number. They have a certain number of blocks $m$ to include this transaction. The adversary can then choose from $m$ block numbers.

However, if the protocol works using block numbers, the number of choices of slot number can be much bigger. Block producers are assigned to slot numbers, not block numbers, in an epoch. Some slot numbers will have more adversarial slots before them and so more choices for the randomness. By choosing whether or not to produce blocks in earlier slots, which do not affect the number of choices for the randomness, the adversary may be able to ensure that the sampling block occurs at their choice of slot number.
This attack is not useful before the adversary knows the randomness for the epoch in question.

However, there is not much point them doing this until 2 epochs before, because then they don't know which slot to aim for until they know the block producers. After that, they need at most 64 blocks until the RanDAO randomness can be sampled. Then they have an additional few blocks depending on a parameter `RandaoCommitExpiration`. Let's assume that this is 3, though we can tolerate much larger numbers.

Just how many choices of slots do they have, starting at 67 blocks before? Again we assume that honest blocks always end up in the chain. Though now the LMD attacks where they don't are not so useful as they end up with some adversarial block in the chain instead.

If all block producers produce blocks, then the can be a minium of 64 slots. The maximum number of slots before 67 blocks is 67 plus the number of adversarial slots before there are 67 honest slots. If the slots assignments were random, and of course they can be biased as above, this is a sample from a negative binomial distribution with parameters r=67. p=2/3.

As calculated at the end of https://github.com/w3f/consensus/blob/master/random/randao_analysis.ipynb , there could be 74 adversarial slots before 67 honest ones. except with probability $1/(172.8 \times 3738.7)$. Thus the slots taken for 64 to 67 blocks could be in the range $64$ to $67+74$, giving $78$ choices.

Using linearity of expectation, we can naively bound the expected number of choices of RanDAO as $172.8 \times 78$ with $\lceil \log_2 172.8 \times 78 \rceil = 14$. But I suspect that we can do better.

### Strenghtening Security Assumption on Ethereum Validators

We played around with the honesty assumption on ethereum validators ot see how much of a difference it makes on the number of signatures required to negate Randao Biasability. Summarised in the table below:

| p| Last-Revealer choices | Block# vs Slot# choices | Extra signatures |
| -------- | -------- | -------- | --- |
| 2/3rd | 131.1 | 77 | 14 |
| 3/4th | 10.61 | 53 | 10 |
| 9/10th | 1.43 | 27 | 6 |

**p**: ratio of honest validators assumed on Ethereum
**Last-Revealer Choices**: Expected number of choices due to last-revealer attack obtained from markov chain analysis. Here we assume the expected wait time to achieve the max tail of malicious blockc producers is >=100yrs
**Block# vs Slot# choices**: choices due to Randomness being queried after a fixed number of blockcs and not slots. probability of adversarial slots before 67 honest slots is extremely high (>= 0.999857)
**signatures**: Extra signature checks required to negate the RANDAO bias by malicious ETH validators. signatures = $\lceil log2 (LastRevealerChoices * BlockVsSlotChoices) \rceil$

## Tighter bounds to reduce signature checks

[This analysis](https://hackmd.io/c6STzrvfQGyN2P2rVmTmoA) shows using $k$ random validator's signatures gives a probability of at most $2^{-k}$ of an adversary convincing the verifier of a false claim. However, if $k$ unique signatures are chosen (i.e., there are no duplicates), this bound can be improved. Snowbridge already implements this optimisation, as the subsample routine that randomly selects signatures also ensures that the chosen signatures are all unique. Assuming $n$ as the number of signatures sent by the relayer ($\geq$ 2/3* (ValidatorSet)+1), and $f$ malicious signatures ($\leq$ 1/3 *(ValidatorSet)), and $m'$ signatures chosen randomly uniquely, the winning probability is :

$$ \frac{f!}{(f-m')!}* \frac{(n-m')!}{n!}
$$

Using the analysis above, for the case of Polkadot, assuming $n=201$, $f=100$, chosing $m=30$ signatures randomly gives the same security guarantees as chosing $m'=27$ signatures randomly uniquely (this optimisation already exists in implementation).