# BEEFY

This document presents a description of the BEEFY protocol. BEEFY's aim is to efficiently follow a chain that has GRANDPA finality, a finality gadget created for Substrate/Polkadot ecosystem. This is useful for bridges (e.g., Polkadot->Ethereum), where a chain can follow another chain and light clients suitable for low storage devices such as mobile phones.

## Why not just use GRANDPA?

A client could just follow GRANDPA using GRANDPA justifications, sets of signatures from validators. This is used for the substrate-substrate bridge and in light clients such as the Substrate connect browser extension. The main issue with this is that GRANDPA justifications are large and that they are expensive to verify on other chains like Ethereum that do not use the same cryptography.

It is not easy to modify GRANDPA to make it better for this. Certain design decisions, like validators voting for different blocks in a justification make this hard. We also don't want to use slower cryptography in GRANDPA.

Thus we are adding an extra protocol, BEEFY, that will allow lighter bridges and light clients of Polkadot.

## Protocol Overview
BEEFY consists of two parts
1. **Consensus Extension** on GRANDPA finalisation that is a voting round

The consensus extension serves to have smaller consensus justification than GRANDPA and alternative cryptography this helps the second part of BEEFY, the light client protocol described below.

2. **Light client** protocol for convincing the other chain/device efficiently about this vote.

In the BEEFY light client, a prover, a full node or bridge relayer, wants to convince a verifier, a light client that may be on-chain, of the outcome of a BEEFY vote. The prover has access to all voting data from the BEEFY voting round. In the light client part, the prover may generate a proof and send it to the verifier or they may engage in an interactive protocol with several rounds of communication.

Since BEEFY runs on top of GRANDPA, similarly to how GRANDPA is lagging behind the best produced (non-finalized) block, BEEFY is going to lag behind the best GRANDPA (finalised) block. The following simplifications for its setup make sense.

- BEEFY validator set is the same as GRANDPA's, however they might be identified by different keys from their session keys
- From a single validator perspective, BEEFY has at most one active voting round.
- Since GRANDPA validators are reaching finality, we assume they are online and well-connected and have a similar view of the state of the blockchain.

## Consensus Extension: Voting Round
In this part of BEEFY all validators need to produce and broadcast votes on GRANDPA finalised block.

A vote is the validator's signatures over a Commitment that consists of a payload and a block number from which the payload originates. The payload is a blob extracted from a block or state at that block, and is expected to be a crypto accumulator, e.g., Merkle Tree Hash or Merkle Mountain Range Root Hash. Additionally Commitment contains BEEFY validator set id at that particular block.

Note the block is finalised, so there is no ambiguity despite using block number instead of a hash. A collection of votes, or rather a Commitment and a collection of signatures is going to be called Signed Commitment. A valid Signed Commitment is also called a BEEFY Justification or BEEFY Finality Proof.

A round is an attempt by BEEFY validators to produce BEEFY Justification. Round number is simply defined as a block number the validators are voting for, or to be more precise, the Commitment for that block number. Round ends when the next round is started, which may happen when one of the events occur:

1. Either collect 2/3rd + 1 valid votes for that round.
2. Or have received a BEEFY Justification for a block greater than the current best BEEFY block.

The new round number is determined locally based on what is believed to be the current round number.

The choice is based on knowledge of:

- Best GRANDPA finalised block number
- Best BEEFY finalised block number
- Starting block of current session
A session means a period of time or rather number of blocks where validator set (keys) do not change.

For more details please see [here](https://github.com/paritytech/grandpa-bridge-gadget/blob/master/docs/beefy.md).

## Implementation alternatives for the BEEFY Light Client

BEEFY will support multiple ways of doing light client protocol and in turn they need different signature schemes too, which is also applied to the voting round. There will be two versions of the light client protocol, a) one using random sampling and secp256k1 signatures (cite) and b) one using SNARKs and BLS signatures (cite).
The voting round will use both secp256k1 and BLS signatures to support both types of light clients.

For efficiency, the verifier doesn't need to know the public keys of the validator set, instead they just have a commitment to the list of keys. The nature of this commitment will be different for the schemes. Since Polkadot's validator set changes over time, when it does, the current validator set will need to sign in a BEEFY message, the commitment to the next validator set and the verifier can update the commitment when it is convinced that the current validator set agreed on it.

### a) Random Sampling
The aim is to have an interactive protocol with a prover that has access to all the votes who voted for that outcome and a verifier who wants to know if an outcome is true.

The prover claims that a particular subset of validators signed the outcome and sends the signature of one of the validators. See [here](https://hackmd.io/wsVcL0tZQA-Ks3b5KJilFQ) for the restristctions on this one signature. The verifier asks the prover for signatures from a randomly selected sample of validators who the prover claimed voted for this outcome. Then the prover provides these signatures and if they verify, the verifier accepts.

Our aim is to be efficient and have this interaction to be a minimal number of signatures that have to be inquired by the verifier to be convinced of the outcome with a certain probability.

#### Form of the votes and light client communication

(TODO details: how does the prover message look like)

*Vote*: The validators sign messages with secp256k1 keys. The message is a Polkadot relay chain block number and Merkle Mountain Range (MMR) (cite) root, where the leafs refer to Polkadot relay chain blocks. The leafs also include information about the bridge parachain blocks of that relay chain block.

*Commitment*: The commitment to the list of the validator's public keys is a Merkle tree.

The prover indicates the subset of keys that signed a message by sending a *bitvector*, whose $k$th bit is 1 if the $k$th key in the list committed to by the Merkle tree signed the message. It also inlcludes the signature of one of the validators, this is important to be able to slash anyone if the claim is wrong, since provers often dont have much stake themselves to be slashed for a wrong claim.

To prove that the $k$th key signed the message when asked, the prover provides the copath of the $k$th public key in the Merkle tree, as well as the signature on the outcome that verifies with this public key.

#### Protocol Parameters and Analysis

We will be more formal about this than here in https://hackmd.io/c6STzrvfQGyN2P2rVmTmoA .

There are $n$ validators. We assume that up to $f=\lfloor (n-1)/3 \rfloor$ of these may be dishonest, which gives that $n > 3f$, consistent with GRANDPA's assumptions.

The verifier requires that the prover's bitvector contains at least $n-f$ 1s. The verifier then asks for $m$ signatures, sampling these uniformly at random from the bits which are 1. $m$ depends on the certainty that the verifier wants to have of the outcome, where for overwhelming certainty it needs $m=f+1$ samples.

Consider an honest prover having $n-f$ signatures on a message. If the validators the prover claims signed the outcome, then the prover should always be able to provide the signatures the verifier asked for and convince the verifier.

Now suppose the prover is lying and the outcome did not happen. Then no honest validator would have signed the message. The prover needs to claim that $n-f$ validators signed the message but they can only obtain signatures from $f$ validators, the dishonest ones. So at least $n-2f$ of the claimed validators are honest and did not sign. For each signature the validator asks for, there is at least $(n-2f)/(n-f) \geq 1-f/(n-f) > 1-f/2f = 1/2$ chance that the validator is honest and then the prover cannot provide the signature. The verifier is only convinced when all samples are dishonest. Since each sample is independent, this happens with probability at most $(f/(n-f))^m < 2^{-m}$.

*Example*: let us assume we have 100 total voters that are validators of a chain. The chain has agreed to outcome X, where 67 honest voters have voted for it and 33 dishonest voters have abstained from voting. The prover wants to convince the verifier that X has been agreed upon with probability 1/1000 . The verifier needs to inquire about the signatures of these 67 honest voters to be convinced that X has indeed been agreed upon. If the verifier inquires about $m=34$ signatures, it can be sure with overwhelming probability that at least one of these signatures is from an honest voter since dishonest voters are at most 33 voters. Now to be sure with probability 1/1000, the verifier only needs to inquire about $m=10$ signatures, because every time successful inquiry reduces the probability that the claim that X has been agreed upon being false by a factor of 1/2.

#### How to do this on-chain?

Here the verifier is on another chain. The prover will post their messages on-chain and chain logic or a smart contract will do the verification. This logic will need randomness for the samples, obtained from the consensus of the chain.

We need this randomness to be random enough, even conditioned on what the prover knows when they make their claim. There will be a delay between the prover's message claiming that certain validators signed and the randomness for the challenge to ensure this.

For proof of work chains, we will be able to use the blockhash as a source of randomness.

Proof of stake chains generally have their own sources of randomness, as consensus often needs one. In Ethereum's case, this is called RANDAO randomness and is available to smart contracts.

### b) Aggregateable Signatures and SNARK

The main difference of this implementation alternative is that BLS signatures are used that make aggregating signatures possible. Note that the verification of these signatures is different too. Another difference is that the prover only needs to send a single aggregated signature and accompanying proofs once to the verifier, which means we don't need to do random sampling anymore and no further interaction is needed.

The prover obtains a single aggregate signature and a commitment to all the necessary public keys needed for verifying this signature. Normally, the verifier needs to compute an aggregate public key for verification from the signing public keys, however we avoid this by having the prover provide a commitment and SNARK that the aggregate public key is correct. Thus the verifier does not need the full list of public keys, just the commitment and a bitvector of who signed. It uses the commitment, the bitvector and the aggregate public key as inputs to the SNARK. If the SNARK verifies, it knows that the aggregate public key is correct which it then uses to verify the aggregate signature.

Note that this alternative is not probabilistic. Indeed it is **accountable**, i.e. a full node, who has the real list of validator public keys can determine which validators have misbehaved and can report this behaviour to the chain. The bitvector indicates who has signed, and the same aggregate public key can be computed directly from the public keys.

#### Cryptographic details

We use BLS signatures, probably on the BLS12-377 curve. The SNARK can be done most efficiently on the BW6-761 curve. This has subsecond proving time. We plan for the primitives necessary to verify this be added as host calls to substrate and be usable on a parachain: https://github.com/paritytech/substrate/pull/13031 .

This will only be efficient in on-chain light clients of chains that support primitives for these curves. As an alternative, we could prove the aggregation and BLS verification inside a SNARK that uses a completely different curve, like BLS12-381 or BN254. This requires using "non-native arithmetic" inside the SNARK resulting in slower proving times by a factor of several 100 so a few minutes proving time, but it will be usable on many chains like Ethereum.

These different curves require different commitments to the list of validator's public keys. So BEEFY will have to support multiple commitments.

## Comparison of the two light client alternatives

The subsampling protocol requires less cryptographic primitives. It is also ready to be using in Snowfork.

The SNARK based protocol does not rely on on-chain randomness and provides accountability. It also has no delay because it has less communication rounds and is more efficient in terms of data because we do not need to provide several Merkle proofs and signatures. It is therefore superior when it can be used, when we have the SNARK code ready and when the verifier can easily support the cryptography required.

Ultimately, we should aim to use the SNARK-based light client whenever possible because its simpler and more secure. However, on the short-term using the random sampling light client makes sense.

## Slashing for BEEFY misbehaviour

It is necessary to slash validators who vote on a chain that is not finalised. It is not directly possible to prove this because we dont know what is finalized on chain.

It should be slashable to vote in BEEFY for a block that is not in the current chain. This includes blocks with a smaller or equal block number to the head of the current chain but are not in the chain, and blocks with a higher block number.

As long as GRANDPA is safe, no validator will be slashed in a finalised chain if they vote for only finalised blocks.

Except for the case of higher block numbers, the slashing report would need to show that the signed message, which was for a block of a certain height, wasn't what the message should be for the block in the current chain of this height. The message, oddly called commitment in the code, is a tuple of (payload, Block Number, ValidatorSetID). We will ignore ValidatorSetID here as if it were wrong, it would at worst have the wrong validators signing the correct payload. So we want to slash for signing a message containing the wrong payload for a previous block number.

The payload is an MMR root. We should store recent MMR roots on chain. If the MMR root is for a block number older than those stored on-chain, it should be possible for the slash reporter to generate an MMR prefix proof which shows that an MMR with a particular root and block number was a prefix of an MMR with a later proof and block number. This latter has to correspond with a recent MMR root stored on-chain.

Sampling-based BEEFY light clients require that there is considerable slashing for the offense that is signing the wrong chain (there are no other types of slashable offenses in BEEFY), unlike in GRANDPA where a single equivocation offense is not slashed much unless there are many simultaneous offenses since a single equivocation in GRANDPA is less risky. Also note that in GRANDPA, it is easy to accidentally equivocate by running a second node with the same validator identity. However in BEEFY, as long as GRANDPA is safe, validators can only be slashed for voting for blocks they do not see as finalised by GRANDPA, which honest nodes will never do. So we can have significant slashing for one offense.

If BEEFY only supported SNARK based light clients, it could have small slashing for a first offense and increased slashing for more simultaneous offenses like GRANDPA. This is because such light clients are accountable i.e. if it is misled and the proof is made public, then we should be able to slash 1/3 of validators. So a few misbehaving validators are not so much of a threat.