Paper 2024/961

Efficient Execution Auditing for Blockchains under Byzantine Assumptions

Jeff Burdges, Web3 Foundation
Alfonso Cevallos
Handan Kılınç Alper
Chen-Da Liu-Zhang, Web3 Foundation
Fatemeh Shirazi, Web3 Foundation
Alistair Stewart, Web3 Foundation
Rob Habermeier
Robert Klotzner, Parity Technologies
Andronik Ordian, Parity Technologies

Security of blockchain technologies primarily relies on decentralization making them resilient against a subset of entities being taken down or corrupt. Blockchain scaling, crucial to decentralisation, has been addressed by architectural changes: i.e., the load of the nodes is reduced by parallelisation, called sharding or by taking computation load off the main blockchain via rollups. Both sharding and rollups have limitations in terms of decentralization and security. A crucial component in these architectures is a layer that allows to efficiently check the validity of incoming blocks in the system. We provide the first formalization and analysis of ELVES, the auditing layer that is currently deployed in the Polkadot and Kusama blockchains. In this layer, “auditing committees” are formed independently for each block, and security relies on the fact that it is prohibitively expensive in expectation for an adversary to make ELVES to accept a block that is not valid. In addition, ELVES has the following characteristics: 1) Auditing committees wind up orders of magnitude smaller than pre-assigned committees. In fact, the size of the committees adapts automatically to network conditions but remains a low constant in expectation, in the order of tens or low hundreds; 2) Although synchronous per se, ELVES tolerates instant adaptive crashes, mirroring realistic network capabilities. Surprisingly, the committee-size analysis of our protocol is ’all but simple’ and involves a novel strengthening of Cantelli’s inequality, which may be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
Contact author(s)
jeff @ web3 foundation
alfonsoc @ gmail com
handankilinc1 @ gmail com
chendaliu @ gmail com
fateme shirazi @ gmail com
stewart al @ gmail com
rphmeier @ gmail com
robert klotzner @ parity io
andronik @ parity io
2024-06-17: approved
2024-06-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jeff Burdges and Alfonso Cevallos and Handan Kılınç Alper and Chen-Da Liu-Zhang and Fatemeh Shirazi and Alistair Stewart and Rob Habermeier and Robert Klotzner and Andronik Ordian},
      title = {Efficient Execution Auditing for Blockchains under Byzantine Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/961},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.