How Can a Blockchain Bridge Trust Just 10 Signatures?

Imagine a blockchain with 1,000 validators. Its finality rules require agreement from more than two-thirds of them. Now imagine another blockchain trying to verify that finality.

The obvious solution is to check hundreds of validator signatures. It works, but every check consumes computation—and on a chain like Ethereum, computation costs gas.

What if the receiving chain checked only 10 or 20 signatures instead?

It sounds reckless. Surely a handful of signatures cannot prove that hundreds of validators agreed.

Here’s the trick: the bridge isn’t trying to prove that a supermajority signed by checking every member of that supermajority. It’s trying to establish that at least one honest validator signed a very particular kind of message.

That distinction is the key to random-sampling light clients, an approach described by Web3 Foundation researchers in Trustless Bridges via Random Sampling Light Clients and used in the design of Polkadot’s connection to Ethereum.

Let’s unpack why it works—and where its guarantees end.

Why bridges face this problem

A blockchain knows which of its own blocks are finalized because its nodes participate in the consensus process. Another blockchain doesn’t have that luxury.

Suppose someone tells an Ethereum smart contract, “This state was finalized on Polkadot.”

The contract can’t simply take their word for it. If it did, that person would effectively become a trusted bridge operator.

Instead, Ethereum needs evidence it can check independently. One way is to verify the signatures of Polkadot validators on a finalized-state commitment. But if the validator set is large, verifying enough signatures becomes expensive. The cost rises with the number of validators, even if the actual cross-chain message is tiny.

This is the trade-off: we want the destination chain to verify finality without trusting relayers, but we don’t want each update to require a huge amount of on-chain work.

Random sampling attacks the verification cost. It doesn’t change how the source chain reaches consensus.

The part that makes everything possible: one honest signature

First, a crucial caveat. One honest validator’s ordinary consensus vote does not necessarily prove a block is finalized. Honest validators can vote during consensus before finality is achieved.

The approach needs an additional rule:

Honest validators sign the bridge’s state commitment only after the underlying consensus protocol has finalized that state.

With this rule, a signature means something stronger than “I voted for this block.” It means “I’ve observed that this state is finalized.”

If a commitment really contains the signature of one honest validator, and honest validators follow that rule, the commitment refers to finalized state. The bridge doesn’t need to rerun the source chain’s consensus process.

Polkadot has a natural setup for this. GRANDPA establishes finality; BEEFY provides an additional, bridge-friendly way for validators to attest to already-finalized state. BEEFY signatures are relatively easy for an Ethereum contract to check.

The problem is that a smart contract cannot look at a validator’s public key and tell whether its owner is honest. A malicious validator can produce a perfectly valid signature on a false commitment.

So how can the bridge be reasonably sure it has found an honest signer?

Make the relayer claim a crowd, then spot-check the crowd

Assume a validator set has 100 members, with at most 33 malicious. That’s the familiar BFT assumption: fewer than one-third are Byzantine.

A relayer presents a state commitment and claims to have signatures from at least 67 validators. Rather than posting every signature, it submits a bitfield—a compact list of which validator positions supposedly signed.

Now consider a dishonest relayer trying to sneak through a false commitment.

No honest validator would have signed it, because honest validators only sign already-finalized state. So the attacker can produce at most 33 genuine signatures, all from malicious validators.

Yet the relayer must claim at least 67 signatures.

That means at least 34 of the claimed signatures don’t actually exist.

The relayer has to bluff about more than half of its claimed signers.

The receiving contract now picks 10 claimed positions at random and demands the corresponding signatures. If even one position belongs to an honest validator whose signature was fabricated in the claim, the relayer fails the challenge.

For the attacker to pass, every random pick must land among the at-most-33 positions for which it has genuine signatures.

In the worst case, each independent pick has less than a 50% chance of landing on a position the attacker controls. Therefore:

\[ P(\text{fake commitment passes}) < (1/2)^m \]

Here, m is the number of independent signature checks.

Random checks	Upper bound on success of one fraudulent attempt
5	About 1 in 32
10	About 1 in 1,024
20	About 1 in 1 million
30	About 1 in 1 billion

That’s the core idea. The source chain can have hundreds of validators, but the receiving contract may only need a few dozen random checks to make a single fraudulent claim very unlikely to pass.

Notice what this does not prove: the contract hasn’t established that 67 valid signatures exist. It has tested a relayer’s claim in a way that is difficult to fake. And if one of the verified signatures is honest, the separate post-finality signing rule does the rest.

The challenge must be a surprise

There’s an obvious loophole if the relayer knows which signers will be checked in advance. The attacker could place its real malicious signatures at those positions and invent the rest.

The protocol therefore works as a short interaction:

Commit: The relayer submits the state commitment, the bitfield of claimed signers, and a real signature identifying a backing validator.
Challenge: After the commitment is fixed, the receiving chain obtains fresh randomness and chooses which claimed signatures to inspect.
Respond: The relayer provides those specific signatures and proofs that their public keys belong to the correct validator set.
Verify: If every check passes, the light client accepts the commitment, subject to its other state-transition rules.

The randomness must be unknown when the claim is made. It also must not be too easy for the attacker to influence.

This is an interactive protocol rather than a certificate the relayer can fully prepare beforehand. The extra rounds add some latency, but they prevent the relayer from choosing its claims after seeing the test.

Why isn’t a one-in-a-thousand chance far too dangerous?

It would be dangerous if that probability were the whole security story.

Suppose someone stands to steal $100 million from a bridge. A one-in-a-thousand success rate still offers a tempting gamble if unsuccessful attempts cost almost nothing.

The paper’s next idea is economic accountability.

The relayer’s initial commitment includes one genuine signature from a backing validator. If that validator signed a fraudulent post-finality commitment, the signature provides evidence of misbehavior that can be reported to the source chain for slashing.

Now a failed attack isn’t merely an unsuccessful guess. It can put real validator stake at risk.

The protocol can choose how many signatures to sample by considering both the possible reward from cheating and the penalty an attacker actually stands to lose. Larger potential gains or smaller enforceable penalties call for more checks.

This is what cryptoeconomic security means here: the goal is to make cheating unattractive to a rational, financially motivated attacker, even though the mathematical probability of success is not literally zero.

There is an important catch: the penalty must be real and enforceable. Nominal stake is not enough if misbehavior cannot be proved, slashing is delayed indefinitely, or the responsible validator can withdraw before being penalized.

The nasty surprise: one small chance, repeated 1,000 times

There’s an even subtler problem.

If each attempt has a one-in-1,024 chance of passing, what happens when an attacker makes 1,000 independent attempts?

The chance of at least one successful attempt rises to about 62% under that illustrative per-attempt bound.

Permissionless relayers make this especially relevant. A malicious actor can spin up many identities and start multiple verification sessions. If all those sessions reuse the same backing validator before slashing takes effect, the attacker may get many tries while exposing roughly the same collateral.

The paper identifies this concurrency attack and proposes a neat defense: make repeated claims backed by the same validator progressively harder to pass.

The light client tracks how often each backing validator is used during an epoch. As that count rises, it asks for more random signatures. The increase is logarithmic, so normal usage stays relatively cheap while thousands of repeat attempts become significantly harder.

Why track the validator instead of the relayer? Because relayer addresses are free to create. Validators have authenticated identities and slashable stake.

This is one of the design’s most interesting lessons: a probability bound for one attempt is not a security guarantee for a protocol that lets attackers retry.

What if Ethereum’s randomness isn’t perfectly random?

Random sampling only works as advertised if the relayer cannot predict or substantially control the challenge.

Ethereum’s RANDAO-based randomness is useful, but it is not perfectly unbiasable. A malicious block proposer may choose to withhold a block, affecting whether its randomness contribution is included. Several cooperating proposers can gain more influence over the possible outcomes. Ethereum’s own EIP-4399 discusses this issue.

The researchers analyze how much that influence could help an attacker in their particular challenge setup. Their model produces a bias bound that can be offset by 10 additional signature checks.

The takeaway isn’t that every use of RANDAO needs exactly 10 extra checks. That number depends on the threat model and challenge timing.

The takeaway is that the receiving chain’s randomness source becomes part of the bridge’s security model. A protocol deployed elsewhere must analyze that chain’s randomness instead of assuming every random-looking value is fair.

Why this matters for Polkadot and Ethereum

The approach fits a practical interoperability problem.

Polkadot’s GRANDPA protocol establishes finality, but its native finality proofs are not ideal for inexpensive verification inside Ethereum. BEEFY adds a lightweight attestation layer, using ECDSA signatures that Ethereum can verify efficiently and MMR commitments that support inclusion and ancestry proofs.

Random sampling then reduces how many BEEFY signatures the Ethereum light client has to check. This is part of the design behind Snowbridge, the Polkadot–Ethereum bridge.

The original paper reports that, for a hypothetical validator set of one million, its sampled verification approach uses roughly a tenth of the gas of the evaluated UltraPLONK-based verifier—and dramatically less than verifying the full signature quorum. Those are historical, isolated benchmark figures, not current end-to-end bridge transaction costs.

The more important result is architectural: the destination chain can follow another chain’s finalized state without trusting a designated relayer and without verifying every validator signature.

Where the idea stops working

Random sampling is powerful, but it is not a shortcut around every security assumption.

1. The source chain still needs secure finality. The technique assumes fewer than one-third of the relevant validators are Byzantine and that honest validators issue the special signatures only after finality. Ordinary consensus votes are not interchangeable with these attestations.

2. The result is probabilistic. Even a very small chance is not zero. Economic deterrence makes attacks unattractive under certain assumptions; it does not turn the verifier into a deterministic full-quorum checker.

3. Slashing has to work in practice. The economic case weakens if the attacker can evade punishment, if only a small amount is slashed, or if stake is no longer locked when evidence appears.

4. A bridge can’t go stale forever. If updates stop for longer than the source chain’s unbonding period, an old validator set might no longer have slashable collateral. The paper calls out this edge case.

5. Someone still has to relay. Permissionless relaying removes the need to trust which relayer participates, but it doesn’t ensure somebody will always be available and willing to pay for updates. Liveness needs its own incentives.

6. Validator weights matter. The simple counting argument assumes that the one-third Byzantine limit applies to the validators being sampled. Stake-weighted consensus systems need a corresponding analysis of voting weight and sampling rules.

7. It doesn’t secure every part of a bridge. Accepting an authentic finalized-state commitment is only one layer. Incorrect token accounting, replay protection, message execution, or smart contracts can still cause losses.

8. Small validator sets might not benefit. Bitfields, membership proofs, storage, and multiple transactions have overhead. Sometimes ordinary verification is cheaper and simpler.

The bigger idea

What makes random-sampling light clients interesting isn’t merely that they use fewer signatures.

It’s that they change the question the verifier needs to answer.

Instead of asking, “Can I independently check every signature in the supermajority?”, the verifier asks, “Can this relayer survive a surprise test that would be extremely difficult to pass without honest signatures?”

And because honest validators sign these commitments only after finality, the verifier needs evidence of just one honest signer—not a complete reconstruction of consensus.

That is a substantial reduction in work. But the cleverness comes with responsibilities: unpredictable challenges, retry protection, enforceable penalties, fresh validator sets, and a precise understanding of what the signatures mean.

In short, random sampling turns an expensive deterministic check into a cheap probabilistic one—and cryptoeconomics helps make the remaining risk unattractive to exploit.

For readers who want to go deeper, the original paper develops the probability bounds, dynamic retry defense, economic parameter selection, and RANDAO-bias analysis in detail.