# History Verification¶

Once a client has received a history proof, they need to be able to correctly check the proof’s validity. This page describes the process for applying each individual proof element and determining the overal validity of the proof.

## Proof Structure¶

A HistoryProof consists of a series of “proof elements”. Each of these elements is either a **Deposit Proof Element**, an **Exclusion Proof Element**, or a **State Update Proof Element**. Elements of each different element type must be handled differently as they convey different information.

## Applying Proof Elements¶

Proof elements each correspond to some action that took place within a specific plasma block. Proof elements **MUST** be applied in ascending block order. Otherwise, a client may not have the necessary information to verify a specific state transition.

### Deposit Proof Elements¶

Deposit Proof Elements consist of a **deposit ID**. Deposit IDs correspond to a deposit on Ethereum, which contains a state update. Whenever the client encounters a Deposit Proof Element, the client **MUST** download the deposit with the given ID by querying for the checkpoint with the same ID.

For efficiency, the client **SHOULD** check their local database for the deposit before querying Ethereum. It’s possible that the client already downloaded while verifying another history proof.

If the deposit is not found, the client **MUST** either throw an error or skip the element.

Once the client has downloaded the corresponding deposit, the client **MUST** insert the deposit’s state update into their local state. The client does **not** need to verify anything about this state update since it came directly from a deposit.

### Exclusion Proof Elements¶

Elements of our Merkle Interval Tree have both an explicit range and an implicit range. A valid inclusion proof for an element of the tree also conveys the fact that no other elements intersect with the included element’s implicit range.

Exclusion Proof Elements simply consist of a state update and an inclusion proof. These elements make no statements about the validity of the state update, but prove that there were no valid transactions on the update’s implicit range.

The client **MUST** verify the inclusion proof for each Exclusion Proof Element. If the inclusion proof fails, the client **MUST** either throw an error or skip to the next proof element.

The client **MUST** then find all state updates that intersect with the implicit range of the proof element where `update.verifiedBlockNumber`

is equal to `element.block - 1`

. We’re only interested in these state updates because the implicit proof only applies to the `element.block`

but not any previous blocks.

Next, for each found state update, the client **MUST** split any elements where the implicit range only partially covers the intersected update. For example, if the implicit range is `(50, 100)`

but the found update is over `(0, 100)`

, the client will split the update into two elements that cover `(0, 50)`

and `(50, 100)`

. This process will leave the client with a set of state updates that are entirely covered by the implicit range and a set that no longer intersect at all.

Next, for each element that is **entirely** covered by the implicit range, the client **MUST** set `update.verifiedBlockNumber`

to `element.block`

. This process effectively finds any state updates covered by the implicit range and “bumps up” the block to which they’re considered valid.

### State Update Proof Elements¶

State Update Proof Elements prove that a given state update has transitioned to a newer one. Despite the name, State Update Proof Elements actually consist of transactions and not state updates. The provided transactions are used to compute the newer state update. These elements also include a block number in which the computed state update was included and an inclusion proof that the state update was actually included in the given block.

For simplicity, we require that all of the transactions within a single State Update Proof Element refer to the same range. If any of the transactions do not refer to the same range, the client **MUST** either throw an error or skip to the next element.

Next, the client **MUST** find all previously verified state updates that intersect with the range on the transations **and** where `update.verifiedBlockNumber`

is equal to `element.block - 1`

.

For each update found in the previous step, the client then **MUST** execute each transaction against the update. Each transaction execution will generate a resulting state update.

After executing the transactions against all updates, the client **MUST** verify that the resulting state updates are all equivalent. If any state update is not equivalent, the client **MUST** either throw an error or skip to the next proof element. The resulting update **MUST** have a block number equal to `element.block`

.

The client then **MUST** verify the inclusion proof provided as part of the proof element. If the inclusion proof is invalid, the client **MUST** either throw an error or skip to the next proof element.

Finally, the client **MUST** insert the resulting state update into the local state. This process **MUST** split or overwrite any existing state updates over the same range. For example, if the local state contains an update that covers `(0, 100)`

and the computed update covers `(50, 100)`

, the client will modify the first update such that it only covers `(0, 50)`

.