The BEEFY light client posts regular updates to the Polkadot validator set stored on Ethereum. Since these regular updates are expensive, Snowfork, Polytope Labs, Parity, and W3F have been researching & testing optimisations for this update scheme.
While BEEFY’s subsampling scheme already provides a significant optimisation against a naive scheme checking all signatures, (original PoW ETH protocol, updated PoS ETH scheme, WIP overview), there are still possible optimisations to how this subsample is being checked.
This post migrates the discussion #12800 here to encourage participation from other teams/community members. A brief overview of the current state:
- The BEEFY light client posts regular updates to the Polkadot validator set stored on Ethereum. Since these regular updates are expensive, Snowfork, Polytope Labs, Parity, and W3F have been researching & testing optimisations for this update scheme.
- While BEEFY’s subsampling scheme already provides a significant optimisation against a naive scheme checking all signatures, (original PoW ETH protocol, updated PoS ETH scheme), there are still possible optimisations to how this subsample is being checked.
- A lexical hash ordering optimisation was first introduced to cut gas cost by ~30% (#12857), which infers the order of hash inputs from their lexical ordering rather than their positions in the tree
- Snowfork later realised that this also breaks the commitment to the subsample of validators used in BEEFY, so the lexical hash ordering optimisation was reverted for now (#14176)
To cut down the cost of the BEEFY updates again, we currently have four alternatives to explore: multiproofs such as those from Polytope Labs, or the three options from here. Welcoming other suggestions or benchmarks / PoCs for improvements.