Trustless Bridges via Random Sampling Light Clients

We formalize our setting, where the objective of an on-chain light client $ℒ𝒞$ on destination chain $𝔻$ is to follow the finality of a source PoS blockchain $𝕊$. For brevity, we model the light client as a smart contract, however, our results hold for other computation models for updating state on $𝔻$. Our setting comprises of three actors: Validators on the source chain $𝕊$, trustless relayer $ℝ$, and a light-client $ℒ𝒞$ deployed on $𝔻$. We make some standard assumptions on the PoS model of $𝕊$, satisfied by most PoS networks like Cosmos, Ethereum, Polkadot:

1. 1.

   Consensus: The blockchain $𝕊$ runs a consensus mechanism with deterministic finality, e.g., Byzantine Fault Tolerant algorithms like CasperFFG, GRANDPA, Tendermint, PBFT, etc. [15, 54, 11, 17].

2. 2.

   Payloads: Each block $B$ in $𝕊$ contains a payload ${𝒫}_B$ capturing the state of $𝕊$ after executing block $B$. Typically, the payload is the hash of a crypto accumulator (e.g., Merkle Tree or Merkle Mountain Range Root [56]) where its leaves are the state of $𝕊$.

3. 3.

   Justifications: Oblivious of the underlying consensus mechanism, once a block $B$ is finalised in $𝕊$, the payload ${𝒫}_B$ is signed by all honest validators in the associated validator set ${𝒱}_B$ of size $n$. We assume at most $f$ validators are malicious, such that . The validator use an unforgeable signature scheme $\sigma$ to attest the payloads. Let ${\sigma }_i$ be the signature of $V_i$ on ${𝒫}_B$, which can be verified against its public-key $p{k}_i$. We often identify the validator $V_i$ by its public-key. A block $B$ is considered justified (or finalised when context is clear) if its payload ${𝒫}_B$ has been signed by at least $2n/3+1$ validators in ${𝒱}_B$. The set of such valid signatures are called justifications, denoted ${𝒥}_B=\{{\sigma }_i|i\in [1,..,n]\}$. We say a justification is valid iff $|{𝒥}_B|\ge 2n/3+1$ and ${\sigma }_i$’s are valid signatures from validators in ${𝒱}_B$. Assuming the underlying consensus mechanism is safe, note that for a particular block-height $h$, only a unique block $B$ can have valid justifications.

4. 4.

   Stakes: Validator $V_i$ has a stake $s_i$ locked on $𝕊$. Any malicious behavior by $V_i$ results in partial or full slash of validator’s stake. We assume the delay in detecting an offense and enforcing the slash and is bounded by $\mathrm{\Delta }$, the slashing delay.

5. 5.

   Epochs: The blockchain $S$ is divided into consecutive set of blocks called epochs, denoted $ℰ=\{{ℰ}_0,\mathrm{\cdots },{ℰ}_i,\mathrm{\cdots }\}$. For any $i$, the validator set ${𝒱}_{{ℰ}_i}$ remains unchanged for all blocks within an epoch ${ℰ}_i$.

6. 6.

   Epoch Transitions: A commitment (e.g. Merkle Root) to the next validator set ${𝒱}_{{ℰ}_{i+1}}$ is included in the payload of ${ℰ}_i$’s last block. PoS networks provide this functionality to facilitate light-clients to sync-up efficiently to the head of the chain by tracking only blocks with validator set changes.

Note: Justifications are succinct proofs of finality designed to simplify the light-client’s process for following the chain head. We require honest validators to justify a payload only if the payload has already been finalized by the underlying finality gadget. Unlike consensus mechanism where an honest validator may sign a non-finalized block, an honest validator never signs justification for a block that has not already been finalized. Hence, the justification of a block guarantees stronger properties than being finalized by the underlying finality gadget like Grandpa or Casper-FFG. We show it is straightforward to construct a justification layer on top of any finality gadget in Section 5.1.

Relayers (denoted $ℝ$) are entities that collect justifications ${𝒥}_B$ from $𝕊$ and interact with the light-client $ℒ𝒞$ to convince it of the newly finalised blocks. In the process, they may collect fees for their efforts. Relayers are completely permissionless, i.e, they do not deposit any stakes either on $𝕊$ or $𝔻$ nor there is any registration. Relayers can communicate with $𝔻$ by calling transactions of the smart contract $ℒ𝒞$. The only requirement on $𝔻$ is:

1. 1.

   Randomness: $𝔻$ provides a source of randomness $ℛ$ accessible to $ℒ𝒞$. Ideally, $ℛ$ is unbiasable by the relayers, and for that matter, even by $𝔻$’s validators. We model the source of randomness as a random function $ℛ:Block{s}_{𝔻}\to \mathbb{N}$, where $ℛ(B^{𝔻})\in \mathbb{N}$ is the randomness generated at block $B^{𝔻}$.

We model the attackers as rational agents, ie., an attack is launched only if the expected outcome of an attack is positive. Our attacker model allows collusion between the relayers and validators on $𝕊$, as well as validators on $𝔻$. We tolerate adversarial faction up to the limit determined by the underlying consensus mechanism on both $𝕊$ and $𝔻$, without adding new trust assumption for safety of the bridge. In particular, relayers are completely permissionless and trustless. The relayer have no stake attached on either $𝕊$ nor $𝔻$. The relayer also can arbitrarily initiate and break an interactive session with the light client. This also means relayer can spawn multiple session concurrently. However, we assume the existence of at least one honest relayers for liveness of the bridge.

We tackle the problem of building trustless bridges using light clients [63]. Typically, a light client synchronizing block headers of the source chain is implemented as a smart contract on the destination chain. This ensures the destination chain can verify information about the state of $𝕊$ without relying on external parties. Moreover, it allows anyone to prove the existence of transactions on $𝕊$ for smart contracts on $𝔻$ (using Merkle proofs), paving the way for generic applications. We formally lay out the desired properties of a light client protocol between verifier $ℒ𝒞$ and prover $ℝ$, with an objective to update $ℒ𝒞$’s view of the latest finalised block on $𝕊$. The $ℝ$ (prover) wants to convince the $ℒ𝒞$ (verifier) that at least one honest validator on $𝕊$ signed the payload ${𝒫}_B$ of a recently finalised block $B$. We introduce the notion of crypto-economic soundness for light-client protocols which lets us trade-off negligible soundness guarantees for efficiency.

Our attacker model does not make any honesty assumptions on relayers. Any safety violation in our approach is traced back to the validators signing malicious payloads. We require the light client protocol to be accountable, i.e, malicious validators on $𝕊$ can be identified and slashed. Our goal is to design a light client protocol that is crypto-economically sound, as defined below:

The prover $ℝ$ initiates the protocol claiming to have valid justification ${𝒥}_B=\{{\sigma }_i|V_i\in {𝒱}_B\}$ for the finality of block $B$, where ${\sigma }_i$’s are signatures of $V_i$ on payload ${𝒫}_B$. Instead of sharing the whole justification (super-majority of signatures), the relayer shares its $\mathrm{𝐶𝑙𝑎𝑖𝑚𝑠}$, a bitfield of length $|V|$ (validator-set size) which represents the validator signatures claimed to be possessed by $ℝ$. For accountability reasons, the tuple in the commit phase also includes a validator signature ${\sigma }_j$ along with the claims, which we term as the backing validator of the current claim. Note that Backing Validators is only an expository term we use to describe the protocol and prove its security. As such, backing validators are not special actors in the protocol. We assume the verifier knows the Merkle Root $𝒞$ of the set of validators (identified by their public keys) for the epoch in which $B$ is finalised. As outlined in section 2.1, the epoch transition mechanism on source chain comprises of a hand-over process, where the Merkle Root of the validator set responsible for next epoch is included in the state by the last block of the current epoch. Such hand-overs are mandatorily enforced as part of the protocol. In unforeseen circumstances when such handovers are unsuccessful, fall-backs mechanism can designed using on-chain governance. To bootstrap the protocol, either the genesis block or a trusted snapshot can be used. The verifier has access to public randomness $ℛ:Block{s}_{𝔻}\to \mathbb{N}$ which it can query at a particular block on $𝔻$. In the challenge phase, it uses $ℛ$ to query a random subset of the signatures. The prover responds by sending the signatures and openings of the randomly sampled signatures in the response phase. The verifier maintains two variables in its state: $latestSyncedBlockHeight$ and $latestSyncedPayload$, denoting the block-height and payload of the latest know block finalised on $𝕊$. If the signatures and opening submitted in the response phase verifies, the payload (${𝒫}_B$) is accepted the state is accordingly updated.

We assume the signature scheme $\sigma$ is unforgeable and the commitment scheme $𝒞$ is binding. We ignore the negligible probability that the prover can find a signature that verifies against the public key of an honest validator that did not sign the message or that they can find an opening of $𝒞$ at position $i$ to a value other than $p{k}_i$ that verifies. To ensure randomness is unpredictable to the prover at commit phase, verifier uses the randomness $ℛ(d)$ only revealed after the commit phase as concluded. Equipped with the above assumptions, we now present the soundness and completeness results for ${\mathrm{\Pi }}_{\text{Int}}$.

Observe that the verifier samples $m$ indices in the Challenge phase in Protocol 1, where indices are chosen uniformly at random from the positions of bits in $\mathrm{𝐶𝑙𝑎𝑖𝑚𝑠}$ set to $1$s. This sampling is done with replacement, i.e., the same index can be sampled multiple times. However, the soundness error can be improved by sampling without replacement, i.e., all the sampled indices are unique. Assuming the validator set size is $n$ of which at most $n/3$ are malicious, and $m^{\prime }$ signatures chosen uniquely at random by the verifier, the soundness error is bounded by:

The soundness error bounds for sampling with and without replacement converge asymptotically with respect to $n$, but for practical validator set sizes $\le {10}^6$, the difference is significant. More importantly, one can get away sampling fewer signatures without replacement for the same soundness error. For example, sampling $41$ signatures without replacement provides the same soundness error as sampling 128 signatures with replacement to achieve a soundness error of $2^{-128}$.

${\mathrm{\Pi }}_{\text{Int}}$ guarantees probabilistic $ϵ$-Soundness with the soundness error $1/2^m$, solely dependent on $m$, the number of signatures sampled in the challenge phase. This leads to a natural question: how to set the security parameter $m$? We provide a crypto-economic framework for deriving the security parameter, striking a balance between efficiency and security.

If a relayer initiates the Commit phase for a canonical block but does not respond to the Challenges by the verifier (either due to genuine or malicious reasons), there is no necessity to slash the backing validator revealed in the commit phase. Slashing any validator that signs a non-canonical block (i.e. with no valid justifications) suffices for the $ϵ$-soundness of ${\mathrm{\Pi }}_{\text{Int}}$. A soundness attack (i.e. relaying a malicious block) is public already at the Commit phase and eventually the backing validator who signed a malicious payload gets slashed, guaranteeing $ϵ$-soundness without any honesty assumptions on the relayers.

We assume there is one honest relayer who relays at least one block per epoch for liveness of the bridge, i.e., the verifier is in sync with the latest finalised blocks on the source chain. Presence of at least one honest relayer per epoch ensures that the verifier can track the validator set changes. A subtle corner case impacting soundness arises when there is no honest relayer for a time-period greater than the unbonding period, i.e, time allowed for an active validator to unbond their stake and exit the network (usually 20-30 days). If no blocks are relayed and updated by the light client over such a long period, then there is a possibility that validators on source chain unbond their stake and hence there is no stake to slash for ${\mathrm{\Pi }}_{\text{Int}}$ attempts after the unbonding period. However, we feel this is unlikely for bridge applications with a clear monetary incentive to stay live. Moreover, the lengthy unbonding period provides ample time to detect and rectify the situation. The problem of bootstrapping efficiently from genesis [1] is more of a concern for light clients that are frequently offline (e.g. light clients embedded in user wallets) unlike bridge applications.

To counter the concurrency issue described above, we propose ${\mathrm{\Pi }}_{\text{Dyn}}$, an extension of ${\mathrm{\Pi }}_{\text{Int}}$. In ${\mathrm{\Pi }}_{\text{Dyn}}$, the security parameter (signatures sampled) dynamically increases based on the number of relay instance backed by the same backing validator. The light client (verifier) now keeps a counter $u_{e,v}$ for each backing validator $v$ in epoch $e$ that increments by 1 whenever there is an initial claim made by a relayer. For any further relay instances by a relayer (or a set of relayer) using the same backing validator $v$, the number of signatures sampled during challenge phase is increased by $1+2\ast \lceil lo{g}_2(u_{e,v})\rceil$. If $c$ instances of ${\mathrm{\Pi }}_{\text{Dyn}}$ are initiated concurrently using the same backing validator, the probability of attack succeeding is bounded by summation over all the $c$ instances using union bounds:

This dynamic increase in the number of signature checks ensures that the probability of successful attack is bounded irrespective of the number of concurrent ${\mathrm{\Pi }}_{\text{Dyn}}$ initiated, and the advantage gained by using the same backing validator multiple times is neutralized.

The setup for ${\mathrm{\Pi }}_{\text{Dyn}}$ is very similar to ${\mathrm{\Pi }}_{\text{Int}}$ except that the verifier ($ℒ𝒞$) maintains an additional mapping $u:(\mathrm{𝙴𝚙𝚘𝚌𝚑},P{K}_{{𝒱}_B})\to \mathbb{N}$, where $u(e,v)$ captures the number of time a validator has been used for the backing signature in the commit-phase. Here, the backing validator is identified by its public-key. We do not keep track of relayers as they are permissionless and any attempt to keep track is not sybil resistant. Intuitively, the dynamic random sampling described in Protocol 2 ensures the adversary does not increase probability of successful attack without increasing its slashing exposure. Importantly, note that the security parameter remains unchanged if no concurrency attack is launched.

Since initiating ${\mathrm{\Pi }}_{\text{Dyn}}$ is permissionless, an adversary can attempt to grief honest relayers by intentionally inflating the dynamic security parameter. This results in increased network workload and added costs, however, we show such griefing attacks are expensive and hence impractical for a rational adversary. Assuming the mapping $u(e,v)$ on the destination chain is publicly observable, an honest relayer in the commit phase can always pick a validator with the least usage, i.e., ${argmin}_{v}u(e,v)$ in the epoch $e$. Thus, an adversary with objective of griefing honest relayers has to uniformly increase the usage counter ($u$) across all possible backing validators for the epoch. Let $C_{\text{init}}$ be the cost for a relayer to initiate ${\mathrm{\Pi }}_{\text{Dyn}}$ and $C_{\text{ver}}$ be the cost of checking each additional signature in the verify phase. $𝒪(2^{x-1}\cdot |V|)$ need to be initiated by the adversary for increasing the security parameter by only $x$. Recall that the security parameter grows by $2\lceil lo{g}_{2}u(e,v)\rceil$. We compute the griefing factor $GF$ [14] (ratio of additional costs on victims to cost incurred by the attacker) for the above optimal strategy.

Therefore, the griefing factor asymptotically drops exponentially for as the attack prolongs. In most practical scenarios, $C_{\text{ver}}\approx C_{\text{init}}$ if not $C_{\text{ver}}\ll C_{\text{init}}$, resulting in low griefing factor for even small values of $x$. Moreover, the griefing attacks do not extend beyond the epoch in which they are launched, as the usage counter $u$ is reset every epoch.

Theorem 3 proves that ${\mathrm{\Pi }}_{\text{Int}}$ is $ϵ$-sound for a single interaction and theorem 6 shows that ${\mathrm{\Pi }}_{\text{Dyn}}$ is unconditionally safe with soundness error $ϵ$ within the same epoch. We do not make any trust assumptions on the relayer for the safety results. However, theorem 4 in conjunction with one honest relayer ensures liveness. Note that our soundness depends on validators being slashed for signing malicious payloads. Similar to ${\mathrm{\Pi }}_{\text{Int}}$, soundness of ${\mathrm{\Pi }}_{\text{Dyn}}$ is affected in the highly unlikely case where blocks relayed for a period longer than the unbonding period (described in Section 3.4). The overall requirements for dynamic sampling is similar to changes adopted in the interactive protocol

Polkadot [13] uses GRANDPA [54], a deterministic finality gadget, for finalising blocks. GRANDPA is designed for secure and fast finalisation for the network, but was not primarily designed for light clients. In particular, finality proofs for GRANDPA are large (votes on forks not blocks) and light clients are required to maintain forks to follow finality. We argue that optimising the on-chain verifier workload is a priority. Hence, adding a light-weight finality layer that requires all validators to sign on the source-chain is a fair trade-off if it facilitates more efficient on-chain verification using destination-chain randomness. We design BEEFY [7] as an additional light-weight finality layer on GRANDPA such that:

• $\mathrm{■}$

  BEEFY justifications satisfy the properties in Section 2.1

• $\mathrm{■}$

  BEEFY uses the ECDSA (secp256k1 [61]) signature scheme which is efficiently verifiable on-chain on Ethereum.

• $\mathrm{■}$

  The validator sets for BEEFY and GRANDPA are identical for each epoch.

In our current design, BEEFY finality lags GRANDPA finality by a few seconds. Note that it is not necessary for every Grandpa finalised block to be BEEFY finalised. The payload is root of an MMR (Merkle Mountain Range) capturing the state of Polkadot, allowing efficient append operations as the chain and state grow [56]. MMRs also allow more efficient block inclusion and ancestry checks on the verifier side [12].

We now describe at a high-level the BEEFY protocol in a partially synchronous setting. The protocol is designed to be modular and can be plugged into PoS chains with any deterministic finality gadget. We extend the consensus mechanism with an extra voting round. Each validator has a local belief of the following:

1. 1.

   Highest GRANDPA finalized block number ($𝖦$).

2. 2.

   Highest BEEFY finalized block number ($𝖡$).

3. 3.

   Last block of the previous epoch $n-1$ (${𝖤}^{n-1}$).

Initially, they are all set to the genesis block. GRANDPA is independently finalising blocks and BEEFY’s objective is to produce justifications for a subset of those blocks. Since GRANDPA does not allow forks, BEEFY validators are essentially voting on a single chain. Hence, the crucial part of the protocol is to determine the block height to vote on.

The protocol runs in rounds from the viewpoint of validators. A BEEFY round is an attempt by validators to produce a BEEFY Justification. Round number is defined as the block height of a GRANDPA finalised block that the validators vote on. The protocol expects honest validators to gossip their vote. From the local view of a validator, a round ends if either of the following events occur:

1. 1.

   Validator collects $2n/3+1$ valid votes for the current round, i.e. the block obtains BEEFY justifications.

2. 2.

   Validator receives a BEEFY Justification for a block higher than the currently known highest BEEFY block.

The validator proceeds to determine the new round number in both the cases. As a strawman approach, BEEFY validators could just pick the next GRANDPA finalised block. However, this would be inefficient as BEEFY finality is not required (due to MMRs) for every GRANDPA finalised block. Moreover, if for unknown reasons (e.g. network latency) the two mechanism drift apart, then there is a risk of BEEFY significantly lagging behind GRANDPA. To address this inefficiency, we introduce a more sophisticated round selection mechanism which ensures the gap between GRANDPA and BEEFY finalised blocks is bounded, even if the rate at which GRANDPA finalises block is exponentially more than the rate at which BEEFY finalises blocks.

Slashing on-chain for BEEFY participants signing is crucial for security guarantees of ${\mathrm{\Pi }}_{\text{Int}}$ and ${\mathrm{\Pi }}_{\text{Dyn}}$. To this end, we store recent payloads on-chain, however, a slash reporter can always generate an MMR ancestry proof [56] to show that a block (not stored on-chain) was the prefix of a recent block. The slashing conditions are straight-forward: validators in BEEFY are slashed for signing a block that is not in the current chain (GRANDPA finalised). This includes blocks with height less than or equal 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, validators can only be slashed for voting for blocks they do not see as finalised by GRANDPA, which honest validators will never do. In theory the full-stake can be slashed but the validator can go rogue until the slash is enforced. Hence, we settle on slashing only half the stake, keeping room for slashing misbehaviors in other subsystems of the Polkadot protocol.

We describe an implementation of a light-client verifier, specifically, the challenge phase in ${\mathrm{\Pi }}_{\text{Int}}$: The prover sends a transaction including the commit message to a smart contract which stores the message and the block number $n_{\text{init}}$ in which the transaction is included. The verifier’s challenge is derived from the RANDAO randomness from some block with number $n_{\text{challenge}}$ in the range $n_{\text{init}}+b_{\text{delay}}\le n_{\text{challenge}}\le n_{\text{init}}+b_{\text{delay}}+b_{\text{window}}$ for some parameters $b_{\text{delay}},b_{\text{window}}$. $b_{\text{delay}}$ represents the number of slots to be waited to ensure the RANDAO value is unpredictable, while $b_{\text{window}}$ represents the number of slots of opportunity provided to the relayer to respond to the challenge after the delay. 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 according 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, as well as the slot numbers since the merge of EIP-4788 [55] as part of Dencun upgrade [45] on Ethereum Mainnet ²²2The analysis is more involved if the smart contract has only access to block numbers. Block producers are assigned to slot numbers in an epoch, not block numbers. Some slot numbers will have more adversarial slots before them and hence 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..

We instantiate the random function $ℛ$ (used in the challenge-phase) in ${\mathrm{\Pi }}_{\text{Dyn}}$ with the RANDAO beacon on Ethereum. While we assumed $ℛ$ is uniformly random and unbiasable, it is well-known that RANDAO is biasable [27, 2]. We focus on quantifying the bias for our specific objective: an attacker who wants to bias an interactive protocol (e.g., ${\mathrm{\Pi }}_{\text{Dyn}}$) that uses RANDAO. We analyze the bias and how it affects our security parameter.

In this section, we consider public-coin protocols with Commit-Challenge-Response phases and abstract away from ${\mathrm{\Pi }}_{\text{Dyn}}$. In a public-coin protocol, the verifier challenge is chosen uniformly at random from some challenge set $S_c$, however if the verifier is implemented on a blockchain, adversarial participants can introduce bias in the randomness. We quantify this bias as follows:

Gas costs for verifying ECDSA signatures on Ethereum using the ecrecover precompile is $\approx 3500$ Gwei. We compare gas costs for verifying BEEFY finality justifications using 3 different approaches across validator set sizes (assuming Polkadot’s total stake rate of $\approx 50\%$, i.e., the ratio of tokens staked to total issuance):

1. 1.

   ${\mathrm{\Pi }}_{\text{Int}}$ with no concurrency attack, but including the extra signatures required for negating RANDAO bias.

2. 2.

   Naive approach of verifying all signatures.

3. 3.

   SNARK circuits for verifying ECDSA signatures using UltraPlonk [58].

As evident from the table, the costs for random sampling logarithmically increase with $|V|$ (explained in Section 3.3) and are an order of magnitude less than the SNARK verification even for $|V|={10}^6$. For $|V|\ge {10}^4$, the gas requirement for Naive approach already exceeds the gas limit per block in Ethereum mainnet, making it infeasible. Further, such bulk usage for verifying signatures drives up the price of gas. As of 27/11/2024, each BEEFY consensus update on Ethereum mainnet costs $0.014$ ETH ($50$USD).