#
EIP-7545: Verkle proof verification precompile

### Add a precompile to help dapps verify verkle proofs

Authors | Guillaume Ballet (@gballet), Diederik Loerakker (@protolambda) |
---|---|

Created | 2023-10-13 |

Discussion Link | https://ethereum-magicians.org/t/verkle-proof-verification-precompile/16274 |

## Table of Contents

## Abstract

This EIP proposes the addition of a precompiled contract to provide up-to-date state proof verification capabilities to smart contracts in a stateless Ethereum context.

## Motivation

The proposed proof systems for stateless Ethereum require an upgrade to many tools and applications, that need a simple path to keep their proving systems up-to-date, without having to develop and deploy new proving libraries each time another proof format must be supported.

## Specification

The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “NOT RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in RFC 2119 and RFC 8174.

A precompiled contract is added at address `0x21`

, wrapping the stateless ethereum proof verification function.

The precompile’s `input`

is the tightly packed concatenation of the following fields:

`version`

(1 byte) specifies which version of the stateless proof verification function should be used. Version 0 is used for an MPT and version 1 is used for the polynomial commitment scheme multiproof used in EIP-6800.`state_root`

(32 bytes) specifies the state root that the proof is proving against.`proof_data`

(arbitrary long) is the proof data.

Pseudo-code behavior of the precompile:

```
def proof_verification_precompile(input):
version = input[0]
state_root = input[1:33]
proof_data = input[33:33+proof_data_size]
if version == 0:
proof = deserialize_proof(state_root, proof_data)
return verify_mpt_multiproof(proof)
if version == 1:
proof = deserialize_proof(state_root, proof_data)
return verify_pcs_multiproof(proof)
return 0
```

If `version`

is `0`

then the proof is expected to follow the SSZ format described in “the verge” proposal in the consensus spec.

The precompile returns `1`

if it was able to verify the proof, and `0`

otherwise.

### Gas costs

Constant name | cost |
---|---|

`POINT_COST` |
TBD |

`POLY_EVAL_COST` |
TBD |

The precompile cost is:

`cost = (POINT_COST + 1)*len(get_commitments(input)) + POLY_EVAL_COST * [leaf_depth(key, get_tree(input)) for key in get_keys(input))]`

where:

`get_commitments`

extracts the list of commitments in the proof, as encoded in`input`

`get_keys`

extracts the list of keys in the proof, as encoded in`input`

`leaf_depth`

returns the depth of the leaf in the tree`get tree`

reconstruct a stateless view of the tree from`input`

## Rationale

Stateless Ethereum relies on proofs using advanced mathematical concepts and tools from a fast-moving area of cryptography. As a result, a soft-fork approach is currently favored in the choice of the proof format: proofs are going to be distributed outside of consensus, and in the future, stateless clients will be able to chose their favorite proof format.

This introduces a burden on several application, e.g. bridges, as they will potentially need to support proof formats designed after the release of the bridge contract.

Delegating the proof verification burden to a version-aware precompile will ensure that these applications can support newer proving primitives without having to upgrade their contracts.

## Backwards Compatibility

No backward compatibility issues found.

## Test Cases

TODO

## Reference Implementation

WIP

- First implementation in Optimism, pull request #192 of ethereum-optimism/op-geth by @protolambda

## Security Considerations

Needs discussion.

## Copyright

Copyright and related rights waived via CC0.

## Citation

Please cite this document as:

Guillaume Ballet (@gballet), Diederik Loerakker (@protolambda), "EIP-7545: Verkle proof verification precompile [DRAFT]," *Ethereum Improvement Proposals*, no. 7545, October 2023. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-7545.