# Lagrange State Committees
###### Ismael Hishon-Rezaizadeh & Charalampos Papamanthou

* Isolated k-of-n bridges, Ethereum light client bridges and ZK light client bridges face inherent security limitations at scale.
* Restaking ([via EigenLayer](https://www.eigenlayer.xyz/)) or staking of a liquid staking derivative ([via Rocket Pool](https://rocketpool.net/)) provides a power primitive to dynamically scale the underlying security of state proof generation.
* Lagrange Labs has built the first proof system that enables the creation of inductive zero-knowledge proofs of the state of any arbitrary chain or roll-up with *super-linear security*.

Lagrange Labs is working to build secure infrastructure for zero-knowledge cross-chain state and storage proofs. The Lagrange Labs shared state security zone allows cross-chain bridging, messaging, or indexing protocols to plug into consuming trust-minimized zero-knowledge proofs of cross-chain state, derived from a generalizable light client committee based on rehypothecated collateral.

## **Existing Cross-Chain Security Models:**

### **Limitations of Isolated Cross-Chain State Security:**

Current approaches to messaging and bridging between EVM chains rely on isolated economic guarantees. These guarantees typically are *k of n* assumptions, where proving that a state exists or a transaction occurred on a different chain requires a plurality, *k,* of a set of *n* nodes to agree and sign. Examples of these approaches include multi-signature wallets, threshold signatures schemes across attestation sets, Tendermint proof-of-stake consensus and proofs of Ethereum’s light client sync committee.

While each of these approaches have distinct advantages, they all share a central flaw: Each cross-chain protocol has a capped sized set of validators that can be attacked in isolation by compromising a plurality of its nodes. Empirically, we’ve seen *isolated* *k of n* security guarantees fail, including the well-publicized hacks of [Ronin Bridge ($650m)](https://cointelegraph.com/news/the-aftermath-of-axie-infinity-s-650m-ronin-bridge-hack), where 5 out of a set of 9 validators were compromised and [Harmony Horizon ($100m)](https://www.halborn.com/blog/post/explained-the-harmony-horizon-bridge-hack) , where 2 out of a set of 5 validators were compromised.

Security across *isolated* *k of n* protocols is either *constant* or *sublinear* with respect to staked collateral. In short, as the amount of available collateral increases, security increases at a diminishing rate as the validator set begins to cap out in size.

To improve on the limitations of *isolated* *k of n* security guarantees, newer cross-chain protocols, such as [zkBridge](https://rdi.berkeley.edu/zkp/zkBridge/zkBridge.html), [Polyhedra Network](https://polyhedra.network/) and [Succinct Labs](https://www.succinct.xyz/), have begun to generate proofs of the signatures by Ethereum's light client sync committee members. While Ethereum’s light client sync committee provides a rough proxy for Ethereum consensus, its security has inherent limitations when used for proving Ethereum state on other chains.

### Understanding Ethereum Sync Committee:

The sync committee of Ethereum is a group of 512 Ethereum validators that are chosen at random every 256 epochs (~27 hours). The sync committee is responsible for continually signing new block headers, so that Ethereum light clients can verify chain state, without having to know the entire validator set. Nodes are given 512 epochs (~54 hours) of prior notice before they become a sync committee member.

The security of light client bridges, ZK bridges and sync committee proofs are all based on verification of signatures from the Ethereum light client sync committee. As the size of the sync committee is fixed, the economic security that underpins it is also capped over a 27-hour window. Once slashing is eventually implemented for Ethereum sync committees, the economic security will be bounded as follows:

*Economic Security of Sync Committee = 512 nodes \* 32 Eth \* $1650 USD/ETH **= $27,033,600***

*Threshold to Compromise Sync Committee = $27,033,600 \* 2/3 = **$18,022,400***

### **Limitations of Ethereum’s Light Client and ZK Light Client Bridges:**

While light client bridges and ZK light client bridges are thought of as a gold standard for cross-chain interoperability, the amount of assets they can secure with randomized sync committees is severely limited. As previously shown, the amount of collateral that colluding nodes would have to burn to simultaneously compromise all Ethereum light client and ZK light client bridges is capped at ***$18m***.

Consider a situation, where the sum of the value of all assets secured by all light client and ZK light client bridges is of an amount *k*. When _k < **$18m**_**,** all assets secured across the bridges are safe, as an attack is not economically viable.

As *k* grows such that *k > $27m ,* it becomes profitable for a group of bad actors in the sync committee to attest to malicious block in order to compromise the secured assets. The only remaining security once this economic threshold is passed is the complexity of requiring 342 random nodes (2/3 of the sync committee) to communicate and coordinate an attack over an 81-hour window.

While collusion between randomly selected nodes over a ~3.5-day window is very difficult, it’s not impossible if the upside of the theft is high enough.

Despite the Ethereum light client sync committee having limited security, zkBridges lack a feasible alternative for proving correct Ethereum state. Generating a SNARK proof of the finality of an Ethereum block based on consensus (Casper-FFG) would require verifying an aggregated BLS signature and set inclusion proofs for at least ⅔ of the active set of validators for each block. Given that the public keys of all active validators are stored within a contract on Ethereum, each set inclusion proof requires proving with the Keccak hash function and the RLP prefix encodings native to Ethereum. In total a SNARK proof of Casper-FFG for a single block would require at least ~400,000 individual set inclusion proofs, containing a total of ~5,000,000 Keccak hashes and RLP serialization proofs.

Given the limitations of the Ethereum light client sync committee’s security and the infeasibility of proving Casper finality, an alternative design is needed for trustless cross-chain state proofs.

## Introducing Lagrange’s Shared Cross-Chain State Security:

### Cross-Chain State Proofs Through Shared Security

Lagrange Labs is developing the cross-chain state committee to provide a more secure alternative to both *randomized light client sync committees* and *isolated k of n bridges* for applications that require trustless cross-chain states. The security of the Lagrange cross-chain state committee is derived from an ever growing, dynamically sized set of nodes with leveraged *rehypothecated collateral*, either restaked with EigenLayer or staked with liquid staking derivatives, such as Rocket Pool.

The Lagrange cross-chain state committee is designed to be *extensible* to generate state proofs for any chain, irrespective of consensus mechanisms, sequencer or validator set specifications. At launch the cross-chain state committee will provide state proofs for Ethereum, Polygon, Arbitrum, Optimism & zkSync.

Nodes wishing to join the cross-chain state committee must either restake via EigenLayer or rETH into Lagrange’s Ethereum contracts. A node must provide at least 32 ETH worth of rehypothecated collateral to join the network and must indicate which chain or roll-up that they wish to provide attestations for.

Every node in the network must run a containerized validator or watcher of a relevant chain or roll-up. If multiple restaked Ethereum nodes are operated by the same actor, each node can instead maintain a secure** RPC connection to a single instance of that chain’s validator (ideally run locally by the node operator). Once in the network, a node must execute a BLS12-381 signature on every new block that reaches finality on the chain that they are attesting to.


The set of attestors for each chain are active for a duration of *n blocks,* otherwise called an *attestation* *period.* The length of the *attestation period* is variable for each chain based on the fraud proof time required to slash colluding nodes. As opposed to the Ethereum light client sync committee which has a cap of 512 nodes, the consensus mechanism that underpins the cross-chain state committee supports an **unbounded set of nodes**.

As such, the collateral behind each attestation can scale dynamically as is required to create secure proofs for each given chain. This property is what enables the Lagrange cross-chain state committee to be the first protocol to enable generalizable state proofs of any arbitrary chain with *super-linear* security.

### Joining the Cross-Chain State Committee:

During each *attestation period*, cross-chain state committee nodes can signal that they want to either join or leave the attestation set at the end of the period. Nodes wishing to join the cross-chain state committee must provide at least 32 ETH worth of rehypothecated collateral through either restaking with EigenLayer or rETH as collateral into Lagrange’s contract on L1 Ethereum.

Nodes that wish to leave the attestation set must submit a transaction to Ethereum requesting removal at the end of the attestation period. At the end of an attestation period* the active set of attestors is amended based on the attestors that have requested to leave or join for the next period.

Since a list of active peers is maintained via Ethereum contracts, verifying peer nodes can be done independently by every attestor. In order to easily prove inclusion of nodes in the active set of attestors, each node independently constructs and stores a Merkle tree of the public keys of all active committee members. This *committee root* is constructed with a SNARK friendly hash function, such as Poseidon, Pedersen or Reinforced Concrete.

### **Responsibilities of a Cross-Chain State Attestor:**

Each cross-chain state attestor is responsible for executing a signature with its BLS12-381 key on every finalized block during the *attestation periods* that it is active for. Each signature is executed on a tuple containing a block header, a Merkle root of the public keys of the current committee and a Merkle root of the public keys of the next committee.

struct block {
        var block_header,
        var current_committee,
        var next_committee,
}

Both of these signatures create slashable conditions for fraud proofs on malicious nodes. Each cross-chain state committee node therefore must independently check the state of both Ethereum and the attested chain before executing each signature. The three basic checks that every attestor performs before signing include:

1. The *block\_header* is correct and corresponds to a finalized block of the chain that is being attested to.
1. The *current\_committee* Merkle root was correctly derived from the public keys of the attestation set on Ethereum for a given block of the arbitrary chain.
1. The *next\_committee* Merkle root was correctly derived by altering the *current\_commitee* at the end of the attestation period with any nodes who opted to enter or leave the attestation set.
### **Deterministic Slashing of Malicious Attestors:**

If a cross-chain state attestor executes a signature on an incorrect header or state committee root for a given block, other network actors must be able to trigger slashing of that node’s collateral. For slashing to occur in a trustless fashion, there must be a deterministic set of conditions under which a signature can be considered incorrect. Verifying the object that a node signed with its BLS key is trivial to do on-chain with a cost of ~110,000 gas.

To prove that a node attested to an incorrect committee root, a proof must show that the root signed by a given node incorrectly includes or excludes a specific public key. As committees are stored in contracts on Ethereum, the required leaf nodes can easily be referenced on-chain as part of proving inclusion or exclusion within a committee root for slashing.

Proving that a signature on a given block header is invalid, requires that a correct block header can be settled on Ethereum in a trust minimized manner. As settlement on Ethereum is only required in the event of slashing, slow forms can be used without compromising the time required for proof generation.

The following forms of state settlement can be used as a source of truth to trigger trust minimized slashing on Ethereum:

* **Ethereum:** A block header at a given height that is accessible from the slashing contract via the *block.header* variable.
* **Polygon:** A settled Polygon PoS check point.
* **Solana:** [A =nil; Foundation’s Light-Client State Proof](https://github.com/NilFoundation/solana-state-proof)
* **Arbitrum & Optimism:** A finalized roll-up block that has cleared the fraud proof window on Ethereum.
* **zkSync, Polygon Hermez & Scroll:** A roll-up block that has been verified on Ethereum.

### Inductive Zero-Knowledge State Proofs:

For a state proof of a single block to be valid, the following recursive properties must hold:

1. At least 2/3 of the *n attestors* restaked for a given block *b* must have signed the block header. The public keys of these nodes are stored in the *current\_committee* Merkle tree.
1. The *current\_committee* of block *b* equals the *next\_committee* tree of block *b-1.*
1. Block *b-1* is either the genesis block or is valid with respect to these three conditions.

This recursive relationship allows any block to be proven as valid via an inductive proof, starting with the base case of an initial hardcoded genesis attestor set. To prove an arbitrary block, a contract requires an inductive zero-knowledge proof of the validity of the previous block with respect to genesis and an aggregated BLS signature of the *current\_commitee* of the present block:

struct block {
        var block_header,
        var current_committee,
        var next_committee,
}

struct block_attestation {
        var block,
        var signer_public_keys
        var bls_signature,
        var previous
}

def inductive_state_proof (block_attestation, genesis):

        verify_bls(block_attestation.block, block_attestation.bls_signature,
                            block_attestation.signer_public_keys)

        for attestor_key in block_attestation.signer_public_keys:
                verify_inclusion(attestor_key, block_attestation.block.current_committee)

        require(3 * block_attestation.signer_public_keys.length >= 2 *  
                       block_attestation.block.current_committee.length)

        require(block_attestation.previous.block.next_committee ==
                      block_attestation.block.current_committee)

        if block_attestation == genesis:
                return true

        else:
                inductive_state_proof(block_attestation.previous, genesis)

## Technical Overview

Our technical approach is inspired by the current implementation of the Ethereum sync committees that is used by Ethereum light clients to verify that an Ethereum block header d’ is valid, assuming a previous block header d is valid (without re-executing all transactions that lead from d to d’). In particular, given two Ethereum blocks headers d and d’, and assuming you trust d, an Ethereum light client can verify that block header d’ is valid by verifying an aggregate signature by a certain number of public keys that are contained in either the current committee or the next committee field of d. The individual signatures are computed by Ethereum nodes that actually check the validity of d’ by replaying all transactions.

**How can you verify a block header d' (from an arbitrary chain C) assuming you trust the previous block header d (from this arbitrary chain C):**

We observe that we cannot apply the same technique with the Ethereum sync-committees to implement the light client for an arbitrary chain C since we cannot guarantee that an arbitrary chain C uses committees for light clients. At the same time, we want to enable a larger number of nodes serving as validators and not be constrained by the fixed number of 512 nodes that Ethereum provides.

Therefore, to verify that a block header d’ of a chain C is valid assuming a previous blockheader d is valid we introduce the following approach.

1. We use a smart contract in Ethereum that registers a dynamic set of validators for chain C. In particular, for every block header d of C, this contract registers the current set of validators current\_d and the next set of validators next\_d. Importantly these sets of validators evolve over time and can be arbitrarily large.
1. We extend the block header of C to contain two digests, one corresponding to the current set of validators and one corresponding to the next set of validators, namely the block header now becomes [d,digest(current\_d),digest(next\_d)]. Therefore the goal now is to verify that [d’,digest(current\_d’),digest(next\_d’)] is a valid extended block header, assuming that [d,digest(current\_d),digest(next\_d)] is a previous valid extended block header.
1. Given two extended block headers headers [d,digest(current\_d),digest(next\_d)] and [d’,digest(current\_d’),digest(next\_d’)], and assuming you trust [d,digest(current\_d),digest(next\_d)], a chain C-light client can verify that block header [d’,digest(current\_d’),digest(next\_d’)] is valid by verifying an aggregate signature by a certain number of public keys that are contained either in current\_d or next\_d. The individual signatures are computed by C nodes that actually check the validity of [d’,digest(current\_d’),digest(next\_d’)] by replaying all transactions and by making sure that current\_d’ and next\_d’ are consistent with the smart contract that corresponds to block header d’.
1. In case the digest d’ is many epochs forward, this procedure will be run recursively and the succinct proof can be produced using a recursive SNARK.

**Call For Collaborators:**

If you are a cross-chain protocol or application layer DApp that is interested in collaborating with Lagrange Labs on building a *cross-chain state committee*, please reach out to [[e-mail]](https://mailto:[e-mail]) or [[e-mail]](https://https://mailto:[e-mail]).
****