# Applying Fiat-Shamir to BEEFY Light-Client Protocol
Authors: Bhargav Bhatt and Alistair Stewart, @bhargavbhatt:matrix.org

This spec has been implemented by Snowfork as part of [PR-1462](https://github.com/Snowfork/snowbridge/pull/1462)

## Introduction

The Fiat-Shamir Transform is a method to make an interactive proof of knowledge non-interactive. It achieves this by replacing the verifier's random challenge with a hash of the prover's initial message. We spec the steps and requirements for implementing the Fiat-Shamir Transform on the current Random Sampling BEEFY Light Client protocol (referred to as $\Pi_{int}$). This doc elaborates on ideas discussed in the [BEEFY paper](https://eprint.iacr.org/2025/057.pdf).

In the current implementation, the light client in $\Pi_{int}$ samples 27 signatures (assuming the [dynamic sampling](https://eprint.iacr.org/2025/057.pdf#page=8.42) is not triggered). However, the interactive protocol has a latency of ~20 minutes for the consensus updates. It is necessary to wait two ethereum epochs before sampling, else the RANDAO randomness is predictable, resulting in violation of protocol's security. This latency is unavoidable in the interactive protocol.
Applying the Fiat-Shamir transform reduces the latency to the time required to get a heavy transaction (>2M gas) included on ethereum at the cost of 100 signature checks (instead of 27 currently). We do not have exact numbers but estimate the latency to be <20s. Snowfork will run an experiment to benchmark the gas costs and absolute cost in ETH to verify 100 signatures in the smart contract. If necessary, this can be split across multiple blocks, slightly increasing the latency. For instance, splitting the 100 checks across $m$ blocks would add $m\times 12$s latency.

We suggest a weaker security parameter (signature checks) for fiat-shamir derived by levaraging crypto-economic arguments. In this model, our security is relative to bitcoin mining and the analysis can be found in [Chapter 6](https://eprint.iacr.org/2025/057.pdf#page=16.42) of the BEEFY paper. For any rational adversary, using its hash power to mine bitcoin is in expectation more profitable than attacking the bridge.

## Transformation Spec

We refer to [Protocol-1](https://eprint.iacr.org/2025/057.pdf#page=6) for description of the current Commit-Challenge-Response-Verify protocol. In the context of applying Fiat-Shamir, it is sufficient to consider the non dynamic sampling version. Dynamic sampling was only introduced to counter the concurrnecy issues of interactiveness.

Applying Fiat-Shamir to protocol-1 reduces the 4-step Commit-Challenge-Response-Verify to just the two steps:
1. Prover collects the BEEFY signature and creates a proof using the hash function.
2. Verifier non-interactively verifies the proof and is convinced at least 1 honest valiadtor signed the block. We introduce a new transaction:

 submitFiatShamir(
    Commitment calldata commitment,
    uint256[] calldata bitfield,
    ValidatorProof[] calldata proofs,
    MMRLeaf calldata leaf,
    bytes32[] calldata leafProof,
    uint256 leafProofOrder
 )

which is in spirit very similar to `submitFinal` in the current implementation.

### Notations:

1. $\mathcal{P}_B$: The payload of the block $B$ to be relayed.
2. $\mathcal{C}$: Merkle root of a tree whose leaves are all the validators public keys for the epoch in which $B$ is finalised.
3. $Claims$: A bit-vector representing the validators signatures that prover claims to know.
4. $pk_i$ is the public key of validator with index $i$.
5. $\pi_i$ is opening of $pk_i$ w.r.t $\mathcal{C}$.
7. $R_\sigma$: Merkle root of a tree whose leaves are claimed signatures.
8. $n$: the number of signatures to be included in the non-interactive proof. Relying on "relative to bitcoin mining" security argument, this can be set to ~101.

### Prover's Algorithm (Run by Relayer)
1. Prover listens to the BEEFY channel and collects signatures for the block (with payload $\mathcal{P}_B$) to be relayed.
2. **Generate FSCommitment ($a$)**: The prover computes the fiat-shamir commitment $a := \mathcal{P}_B ++ \mathcal{C} ++ Claims$. Here $++$ denotes concatenation.
3. **Compute Challenge ($e$)**: The prover computes the challenge $e = H(a)$, where $H$ is a cryptographic hash function.
4. **Generate Response (z)**: The prover computes the response $z$ based on $a$ and $e$.
- The prover uses $e$ as the seed for a PRNG $r$ (currently Keccak256) to generate a list of $n$ **distinct** indices $[j_1,\ldots j_n]$ of the $Claims$ bitvector which are set to 1. This logic already exists in the current [subsample](https://github.com/Snowfork/snowbridge/blob/5aabf721a613e23dfe2ba414068e12de7dbe127b/contracts/src/utils/Bitfield.sol#L41) function.
- Generate the list $z = [(\sigma_{j_i},j_i,pk_{j_i},\pi_{j_i}) | j_i \leftarrow[j_1,\ldots,j_n]]$ where $\sigma_{j_i}$ is the signature of validator $j_i$, $pk_{j_i}$ is public key of $j_i$, and $\pi_{j_i}$ is the opening of $pk_{j_i}$ w.r.t $\mathcal{C}$.

### Verifier's Algorithm (On-chain Lightclient)

The number of signatures to be included in the non-interactive proof $n$ is a constant that is set to 101 (derived from relative security to bitcoin argument).

1. **Receive Proof (a, z)**: Relayer (prover) submits the proof $z$ to the light-client smart contract as call data of the transaction $SubmitFiatShamir(\mathcal{P}_B,Claims,z,$leaf,leafProof,leafProofOrder)$. The parameters leaf, leafProof, and leafProofOrder are only used at the boundaries of sessions when a new validatorSet is to be set. The logic for updating new validator set is exactly the same as current implementation.
2. **Computes Challenge ($e'$)**: The verifier computes the challenge $e' = H(\mathcal{P}_B++\mathcal{C}++Claims)$, using the same hash function $H$. It already knows $\mathcal{C}$ and receives the other two from the prover.
3. **Verify Response**: The verifier checks if $z$ is a valid response for $a$ and $e'$ as follows. Perform following checks (these already exist in [verifyCommitment](https://github.com/Snowfork/snowbridge/blob/5aabf721a613e23dfe2ba414068e12de7dbe127b/contracts/src/BeefyClient.sol#L374)):
a. check if $|z|= n$. If not, verifier outputs $False$.
b. Compute indices $[j'_1,\ldots, j'_n]$ with $e'$ as the seed and the same mechanism as the prover in `Generate Response`.
c. for each element $(\sigma, pk, i, \pi)$ in the list $z$:
- check if $i\in [j'_1,\ldots, j'_n]$, and $i$ did not appear before in $z$.
- we [verify](https://github.com/Snowfork/snowbridge/blob/5aabf721a613e23dfe2ba414068e12de7dbe127b/contracts/src/BeefyClient.sol#L533) the signature $\sigma_i$ against $pk_i$ and that $\pi_i$ [opens](https://github.com/Snowfork/snowbridge/blob/5aabf721a613e23dfe2ba414068e12de7dbe127b/contracts/src/BeefyClient.sol#L528) against $\mathcal{C}$ as the $i^{th}$ element. If any of the check fails, verifier outputs $False$.

d. if all previous checks pass, verifier outputs $True$.

4. **Update State**: If verifier outputs $True$, update the `latestMMRroot` and `latestBeefyBlock` with values from the payload.

### Cryptographic Hash Function
A cryptographically secure hash function $H$ is required. The hash function should have the following properties:

- Preimage Resistance: Given a hash $h$, it is computationally infeasible to find a message m such that $H(m) = h$.
- Second Preimage Resistance: Given a message $m1$, it is computationally infeasible to find a different message $m2$ such that $H(m1) = H(m2)$.
- Collision Resistance: It is computationally infeasible to find two different messages $m1$ and $m2$ such that $H(m1) = H(m2)$.

Suitable hash functions include:

- SHA-256
- Keccak-256

To rely on the security argument relative to bitcoin mining, we must use the same hash function as bitcoin mining.

## Additional Considerations

- It would be beneficial if Polkadot validators BEEFY-sign blocks even after the $2n/3 +1$ threshold is reached. This would further improve efficiency. The number of signature checks would be $m/log2(3x)$ where x is the fraction of validator's BEEFY-signatures that can be gathered by the relayer. Here $m$ is the number of signature checks required assuming 2/3 n +1 validators sign BEEFY. If all validators sign, then signature checks required is $100/1.54 = 64$.

- there are two points of latency in the current consensus update of the bridge (Polkadot -> Ethereum):
1. cadence of consensus updates. IIRC, this is set as 4hrs in current relayer implementation
2. ~20min from the time `initialSubmit` is called to timepoint where the MMR root is updated on the light client.

The fiat shamir approach only helps wrt (2), reducing that latency to hopefully < 1 min but does not help with (1). In fact, with fiat-shamir, reducing latency (1) costs even more as each update is costlier. For example, if we increase cadence to once per hour, then total costs is 16x (4x for fiat shamir and 4x for higher cadence).

- We can run both the fiat-shamir version and interactive random-sampling in parallel. Fiat-shamir could be used for on-demand consensus updates where the user is willing to pay the costs for lower latency. However, there are subtleties that need to be taken care of when combining the above stand-alone Fiat-shamir spec with the interactive random sampling. For example, there needs to be some logic which ensures the the $latestMMRroot$ value on the smart contract is not updated simultaneously by two fiat-shamir transaction and $SubmitFinal$ (of the interactive protocol) or does not go backwards. This seems to be already taken care by [validateTicket](https://github.com/Snowfork/snowbridge/blob/5aabf721a613e23dfe2ba414068e12de7dbe127b/contracts/src/BeefyClient.sol#L623), but this would now have to be directly part of `submitFiatShamir` as there is no notion of tickets in FiatShamir.

## Resources
- https://sigma.zkproof.org/
- https://eprint.iacr.org/2024/1565.pdf (Describes common pitfalls in implementing Fiat-Shamir)
- https://blog.openzeppelin.com/the-last-challenge-attack