Skip to content

Merkle–Patricia Inclusion

A full description of our most important M3 instance

In this section, we describe in detail our M3-based arithmetization of Merkle–Patricia inclusion, a task of critical real-life importance in Ethereum. This arithmetization showcases the full power of M3, and demonstrates its capacity to solve real problems.

Subsection Directory

This subsection has the following pages:

  • Review of MPT Task. Here, we sketch a few preliminaries. We explain how Merkle–Patricia proofs work, and why they stand to make Ethereum's state more efficiently verifiable.
  • Informal Explanation. Since our construction is so involved, we break up our treatment by dropping first an informal sketch. That sketch appears in this page, and explains our main idea on an intuitive level.
  • Our MPT Construction. Here, we thoroughly explain a slightly simplified—but nonetheless representative—variant of our construction, in which aggressive deduplication is not performed.
  • State Forking. Here, we describe state forking, an advanced deduplication technique. Using this technique, we secure efficiency gains whenever many key–value pairs are getting proved at once.