#
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.