---
eip: 7812
title: ZK Identity Registry
description: Singleton registry system for storing abstract private provable statements.
author: Artem Chystiakov (@arvolear) <artem@rarilabs.com>, Oleksandr Kurbatov <oleksandr@rarilabs.com>, Yaroslav Panasenko <yaroslav@rarilabs.com>, Michael Elliot (@michaelelliot) <mike@zkpassport.id>, Vitalik Buterin (@vbuterin)
discussions-to: https://ethereum-magicians.org/t/erc-7812-zk-identity-registry/21624
status: Review
type: Standards Track
category: ERC
created: 2024-11-08
---

## Abstract

This EIP introduces an on-chain registry system for storing and proving abstract statements. Users may utilize the system to store commitments to their private data to later prove its validity and authenticity via zero knowledge, without disclosing anything about the data itself. Moreover, developers may use the singleton `EvidenceRegistry` contract available at `0x781246D2256dc0C1d8357c9dDc1eEe926a9c7812` to integrate custom business-specific registrars for managing and processing particular statements.

## Motivation

This EIP stemmed from the need to localize and unravel the storage and issuance of provable statements so that future protocols can anchor to the standardized singleton on-chain registry and benefit from cross-reuse.

The aggregation of provable statements significantly improves reusability, portability, and security of the abundance of zero knowledge privacy-oriented solutions. The abstract specification of the registry allows custom indentity-based, reputation-based, proof-of-attendance-based, etc., protocols to be implemented with little to minimal constraints.

The given proposal lays the important foundation for specific solution to build upon. The more concrete specifications of statements and commitments structures are expected to emerge as separate, standalone EIPs. 

## Specification

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.

### Definitions

- A "Sparse Merkle Tree (SMT)" is a special Merkle tree that works by deterministically and idempotently storing key/value pairs in the given locations leveraging a hash function. The Poseidon hash function is often used to optimize the compatibility with ZK.
- A "statement" is an accepted structured representation of some abstract evidence. A statement can range from a simple `string` to a Merkle root of some SMT.
- A "commitment" is a special public value resulting from blinding a statement to conceal it. Commitments allow the authenticity of a statement to be proven in ZK without disclosing the statement itself.
- A "commitment key" is a private salt mixed with the statement to obtain a commitment to that statement. The commitment key must be kept private to maintain the confidentiality of statements.

### General

The on-chain registry system consists of two subsystems: the `EvidenceRegistry` with `EvidenceDB` and `Registrar` components. This EIP will focus on describing and standardizing the former, while the `Registrar` specification may be amended as the separate proposals.

![The on-chain evidence registry system entities diagram.](../assets/eip-7812/images/diagram.png)

The on-chain evidence registry system entities diagram.

The `EvidenceRegistry` acts as the entrypoint to a protocol-wide provable database `EvidenceDB` where arbitrary `32-byte` data can be written to and later proven on demand. The `Registrar` entities implement specific business use cases, structure the provable data, and utilize `EvidenceRegistry` to put this data in the `EvidenceDB`.

In order to prove that certain data is or is not present in the `EvidenceDB` Merkle proofs may be used. Understanding how a specific `Registrar` has structured and put data into the `EvidenceDB`, one may implement an on-chain ZK verifier (using Circom or any other stack) and prove the inclusion (or exclusion) of the data in the database.

The Circom implementation of a general-purpose SMT-driven `EvidenceDB` verifier circuit together with the Solidity implementation of `EvidenceRegistry` and `EvidenceDB` smart contracts may be found in the "Reference Implementation" section.

### Evidence DB

The `EvidenceDB` smart contract MAY implement an arbitrary provable key/value data structure, however it MUST support the `addition`, `update`, and `removal` of elements. All of the supported write operations MUST maintain the property of idempotence (e.i. `addition` followed by `removal` should not change the state of the database). The data structure of choice MUST be capable of providing both element inclusion and exclusion proofs. The functions that modify the `EvidenceDB` state MUST be callable only by the `EvidenceRegistry`.

For reference, the `EvidenceDB` smart contract MAY implement the following interface:

```solidity
pragma solidity ^0.8.0;

/**
 * @notice Evidence DB interface for Sparse Merkle Tree based statements database.
 */
interface IEvidenceDB {
    /**
     * @notice Represents the proof of a node's inclusion/exclusion in the tree.
     * @param root The root hash of the Merkle tree.
     * @param siblings An array of sibling hashes can be used to get the Merkle Root.
     * @param existence Indicates the presence (true) or absence (false) of the node.
     * @param key The key associated with the node.
     * @param value The value associated with the node.
     * @param auxExistence Indicates the presence (true) or absence (false) of an auxiliary node.
     * @param auxKey The key of the auxiliary node.
     * @param auxValue The value of the auxiliary node.
     */
    struct Proof {
        bytes32 root;
        bytes32[] siblings;
        bool existence;
        bytes32 key;
        bytes32 value;
        bool auxExistence;
        bytes32 auxKey;
        bytes32 auxValue;
    }
    
    /**
     * @notice Adds the new element to the tree.
     */
    function add(bytes32 key, bytes32 value) external;

    /**
     * @notice Removes the element from the tree.
     */
    function remove(bytes32 key) external;

    /**
     * @notice Updates the element in the tree.
     */
    function update(bytes32 key, bytes32 newValue) external;

    /**
     * @notice Gets the SMT root.
     * SHOULD NOT be used on-chain due to roots frontrunning.
     */
    function getRoot() external view returns (bytes32);

    /**
     * @notice Gets the number of nodes in the tree.
     */
    function getSize() external view returns (uint256);
    
    /**
     * @notice Gets the max tree height (number of branches in the Merkle proof)
     */
    function getMaxHeight() external view returns (uint256);

    /**
     * @notice Gets Merkle inclusion/exclusion proof of the element.
     */
    function getProof(bytes32 key) external view returns (Proof memory);

    /**
     * @notice Gets the element value by its key.
     */
    function getValue(bytes32 key) external view returns (bytes32);
}
```

### Evidence Registry

The `EvidenceRegistry` smart contract is the central piece of this EIP. The `EvidenceRegistry` MUST implement the following interface, however, it MAY be extended:

```solidity
pragma solidity ^0.8.0;

/**
 * @notice Common Evidence Registry interface.
 */
interface IEvidenceRegistry {
    /**
     * @notice MUST be emitted whenever the Merkle root is updated.
     */
    event RootUpdated(bytes32 indexed prev, bytes32 indexed curr);

    /**
     * @notice Adds the new statement to the DB.
     */
    function addStatement(bytes32 key, bytes32 value) external;

    /**
     * @notice Removes the statement from the DB.
     */
    function removeStatement(bytes32 key) external;

    /**
     * @notice Updates the statement in the DB.
     */
    function updateStatement(bytes32 key, bytes32 newValue) external;

    /**
     * @notice Retrieves historical DB roots creation timestamps.
     * Latest root MUST return `block.timestamp`.
     * Non-existent root MUST return `0`.
     */
    function getRootTimestamp(bytes32 root) external view returns (uint256);

    /**
     * @notice Builds and returns the isolated key for `source` and given `key`.
     */
    function getIsolatedKey(address source, bytes32 key) external view returns (bytes32);
}
```

The `addStatement`, `removeStatement`, and `updateStatement` methods MUST isolate the statement `key` in order for the database to allocate a specific namespace for a caller. These methods MUST revert in case the isolated key being added already exists in the `EvidenceDB` or the isolated key being removed or updated does not.

The `EvidenceRegistry` MUST maintain the linear history of `EvidenceDB` roots. The `getRootTimestamp` method MUST NOT revert. Instead, it MUST return `0` in case the queried `root` does not exist. The method MUST return `block.timestamp` in case the latest root is requested.

Before communicating with the `EvidenceDB`, the `key` MUST be isolated in the following way:

```solidity
bytes32 isolatedKey = hash(msg.sender, key)
```

Where the `hash` is secure protocol-wide hash function of choice.

### Hash Function

The same secure hash function MUST be employed in both `EvidenceRegistry` and `EvidenceDB`. It is RECOMMENDED to use ZK-friendly hash function such as `poseidon` to streamline the database proving.

In case ZK-friendly hash function is chosen, `EvidenceRegistry` MUST NOT accept `keys` or `values` beyond the underlying elliptic curve prime field size (`21888242871839275222246405745257275088548364400416034343698204186575808495617` for `BN128`). 

## Rationale

During the EIP specification we have considered two approaches: where every protocol has its own registry and where all protocols are united under a singleton registry. We have decided to go with the latter as this approach provides the following benefits:

1. Cross-chain portability. Only a single `bytes32` value (the SMT root) has to be sent cross-chain to be able to prove the state of the registry.
2. Centralization of trust. Users only need to trust a single, permissionaless, immutable smart contract.
3. Integration streamline. The singleton design formalizes the system interface, the hash function, and the overall proofs structure to simplify the integration.

The proposal is deliberately written as abstract as possible to not constrain the possible business use cases and allow `Registrars` to implement arbitrary provable solutions.

It is expected that based on this work future EIPs will describe concrete registrars with the exact procedures of generation of commitments, management of commitment keys, and proving of operated statements. For instance, there may be a registrar for on-chain accounting of national passports, a registrar with [EIP-4337](./eip-4337.md) confidential account identity management, a registrar for POAPs, etc.

The `EvidenceDB` namespacing is chosen to segregate the write access to the database cells, ensuring that no entity but issuer can alter their content. However, this decision delegates the access control management responsibility solely to registrars, an important aspect to be considered during their development.

The `EvidenceRegistry` maintains the minimal viable (gas-wise) history of roots on-chain for smooth registrars integration. In case more elaborate history is required, it is RECOMMENDED to implement off-chain services for parsing of `RootUpdated` events.

## Backwards Compatibility

This EIP is fully backwards compatible.

### Deployment Method

The `EvidenceRegistry` is a singleton contract available at `0x781246D2256dc0C1d8357c9dDc1eEe926a9c7812` deployed via the "deterministic deployment proxy" from `0x4e59b44847b379578588920ca78fbf26c0b4956c` with the salt `0x04834e077c463de76a20df3770a7b96a5e5eb826922d1514f943cd5b41ccaed0`. 

## Reference Implementation

The reference implementation of `EvidenceRegistry` and `EvidenceDB` Solidity smart contracts together with the evidence registry state verifier Circom circuit is provided in the proposal.

The low-level Solidity and Circom implementations of SMT can be found [here](../assets/eip-7812/contracts/SparseMerkleTree.sol) and [here](../assets/eip-7812/circuits/SparseMerkleTree.circom).

The height of the SMT is set to `80`.

> Please note that the reference implementation depends on the `@openzeppelin/contracts v5.1.0` and `circomlib v2.0.5`.

### EvidenceDB Implementation

```solidity
// SPDX-License-Identifier: CC0-1.0
pragma solidity ^0.8.21;

import {Initializable} from "@openzeppelin/contracts/proxy/utils/Initializable.sol";

import {IEvidenceDB} from "./interfaces/IEvidenceDB.sol";

import {SparseMerkleTree} from "./libraries/SparseMerkleTree.sol";
import {PoseidonUnit2L, PoseidonUnit3L} from "./libraries/Poseidon.sol";

contract EvidenceDB is IEvidenceDB, Initializable {
    using SparseMerkleTree for SparseMerkleTree.SMT;

    address private _evidenceRegistry;

    SparseMerkleTree.SMT private _tree;

    modifier onlyEvidenceRegistry() {
        _requireEvidenceRegistry();
        _;
    }

    function __EvidenceDB_init(address evidenceRegistry_, uint32 maxDepth_) external initializer {
        _evidenceRegistry = evidenceRegistry_;

        _tree.initialize(maxDepth_);

        _tree.setHashers(_hash2, _hash3);
    }

    /**
     * @inheritdoc IEvidenceDB
     */
    function add(bytes32 key_, bytes32 value_) external onlyEvidenceRegistry {
        _tree.add(key_, value_);
    }

    /**
     * @inheritdoc IEvidenceDB
     */
    function remove(bytes32 key_) external onlyEvidenceRegistry {
        _tree.remove(key_);
    }

    /**
     * @inheritdoc IEvidenceDB
     */
    function update(bytes32 key_, bytes32 newValue_) external onlyEvidenceRegistry {
        _tree.update(key_, newValue_);
    }

    /**
     * @inheritdoc IEvidenceDB
     */
    function getRoot() external view returns (bytes32) {
        return _tree.getRoot();
    }

    /**
     * @inheritdoc IEvidenceDB
     */
    function getSize() external view returns (uint256) {
        return _tree.getNodesCount();
    }

    /**
     * @inheritdoc IEvidenceDB
     */
    function getMaxHeight() external view returns (uint256) {
        return _tree.getMaxDepth();
    }

    /**
     * @inheritdoc IEvidenceDB
     */
    function getProof(bytes32 key_) external view returns (Proof memory) {
        return _tree.getProof(key_);
    }

    /**
     * @inheritdoc IEvidenceDB
     */
    function getValue(bytes32 key_) external view returns (bytes32) {
        return _tree.getNodeByKey(key_).value;
    }

    /**
     * @notice Returns the address of the Evidence Registry.
     */
    function getEvidenceRegistry() external view returns (address) {
        return _evidenceRegistry;
    }

    function _requireEvidenceRegistry() private view {
        if (_evidenceRegistry != msg.sender) {
            revert NotFromEvidenceRegistry(msg.sender);
        }
    }

    function _hash2(bytes32 element1_, bytes32 element2_) private pure returns (bytes32) {
        return PoseidonUnit2L.poseidon([element1_, element2_]);
    }

    function _hash3(
        bytes32 element1_,
        bytes32 element2_,
        bytes32 element3_
    ) private pure returns (bytes32) {
        return PoseidonUnit3L.poseidon([element1_, element2_, element3_]);
    }
}
```

### EvidenceRegistry Implementation

```solidity
// SPDX-License-Identifier: CC0-1.0
pragma solidity ^0.8.21;

import {Initializable} from "@openzeppelin/contracts/proxy/utils/Initializable.sol";

import {IEvidenceDB} from "./interfaces/IEvidenceDB.sol";
import {IEvidenceRegistry} from "./interfaces/IEvidenceRegistry.sol";

import {PoseidonUnit2L} from "./libraries/Poseidon.sol";

contract EvidenceRegistry is IEvidenceRegistry, Initializable {
    uint256 public constant BABY_JUB_JUB_PRIME_FIELD =
        21888242871839275222246405745257275088548364400416034343698204186575808495617;

    IEvidenceDB private _evidenceDB;

    mapping(bytes32 => uint256) private _rootTimestamps;

    modifier onlyInPrimeField(bytes32 key) {
        _requireInPrimeField(key);
        _;
    }

    modifier onRootUpdate() {
        bytes32 prevRoot_ = _evidenceDB.getRoot();
        _rootTimestamps[prevRoot_] = block.timestamp;
        _;
        emit RootUpdated(prevRoot_, _evidenceDB.getRoot());
    }

    function __EvidenceRegistry_init(address evidenceDB_) external initializer {
        _evidenceDB = IEvidenceDB(evidenceDB_);
    }

    /**
     * @inheritdoc IEvidenceRegistry
     */
    function addStatement(
        bytes32 key_,
        bytes32 value_
    ) external onlyInPrimeField(key_) onlyInPrimeField(value_) onRootUpdate {
        bytes32 isolatedKey_ = getIsolatedKey(msg.sender, key_);

        if (_evidenceDB.getValue(isolatedKey_) != bytes32(0)) {
            revert KeyAlreadyExists(key_);
        }

        _evidenceDB.add(isolatedKey_, value_);
    }

    /**
     * @inheritdoc IEvidenceRegistry
     */
    function removeStatement(bytes32 key_) external onlyInPrimeField(key_) onRootUpdate {
        bytes32 isolatedKey_ = getIsolatedKey(msg.sender, key_);

        if (_evidenceDB.getValue(isolatedKey_) == bytes32(0)) {
            revert KeyDoesNotExist(key_);
        }

        _evidenceDB.remove(isolatedKey_);
    }

    /**
     * @inheritdoc IEvidenceRegistry
     */
    function updateStatement(
        bytes32 key_,
        bytes32 newValue_
    ) external onlyInPrimeField(key_) onlyInPrimeField(newValue_) onRootUpdate {
        bytes32 isolatedKey_ = getIsolatedKey(msg.sender, key_);

        if (_evidenceDB.getValue(isolatedKey_) == bytes32(0)) {
            revert KeyDoesNotExist(key_);
        }

        _evidenceDB.update(isolatedKey_, newValue_);
    }

    /**
     * @inheritdoc IEvidenceRegistry
     */
    function getRootTimestamp(bytes32 root_) external view returns (uint256) {
        if (root_ == bytes32(0)) {
            return 0;
        }

        if (root_ == _evidenceDB.getRoot()) {
            return block.timestamp;
        }

        return _rootTimestamps[root_];
    }

    /**
     * @inheritdoc IEvidenceRegistry
     */
    function getIsolatedKey(address source_ bytes32 key_) public pure returns (bytes32) {
        return PoseidonUnit2L.poseidon([bytes32(uint256(uint160(source_))), key_]);
    }

    function getEvidenceDB() external view returns (address) {
        return address(_evidenceDB);
    }

    function _requireInPrimeField(bytes32 key_) private pure {
        if (uint256(key_) >= BABY_JUB_JUB_PRIME_FIELD) {
            revert NumberNotInPrimeField(key_);
        }
    }
}
```

### EvidenceRegistry Verifier Implementation

```solidity
// LICENSE: CC0-1.0
pragma circom 2.1.9;

include "SparseMerkleTree.circom";

template BuildIsolatedKey() {
    signal output isolatedKey;

    signal input address;
    signal input key;

    component hasher = Poseidon(2);
    hasher.inputs[0] <== address;
    hasher.inputs[1] <== key;

    hasher.out ==> isolatedKey;
}

template EvidenceRegistrySMT(levels) {
    // Public Inputs
    signal input root;

    // Private Inputs
    signal input address;
    signal input key;

    signal input value;

    signal input siblings[levels];

    signal input auxKey;
    signal input auxValue;
    signal input auxIsEmpty;

    signal input isExclusion;

    // Build isolated key
    component isolatedKey = BuildIsolatedKey();
    isolatedKey.address <== address;
    isolatedKey.key <== key;

    // Verify Sparse Merkle Tree Proof
    component smtVerifier = SparseMerkleTree(levels);
    smtVerifier.siblings <== siblings;

    smtVerifier.key <== isolatedKey.isolatedKey;
    smtVerifier.value <== value;

    smtVerifier.auxKey <== auxKey;
    smtVerifier.auxValue <== auxValue;
    smtVerifier.auxIsEmpty <== auxIsEmpty;

    smtVerifier.isExclusion <== isExclusion;

    smtVerifier.root <== root;
}

component main {public [root]} = EvidenceRegistrySMT(80);
```

## Security Considerations

From security standpoint there are several important aspects that must be highlighted. 

The individual registrars are expected to provide the functionality for both management and proving of statements. The proving will often be carried out by ZK proofs, which require trusted setup. Improperly setup ZK verifiers can be exploited to verify forged proofs.

The `getRoot` method of `EvidenceDB` SHOULD NOT be used on-chain by the integrating registrars to check the validity of the database state. Instead, the required `root` SHOULD be passed as a function parameter and checked via `getRootTimestamp` method to avoid being frontrun.

## Copyright

Copyright and related rights waived via [CC0](../LICENSE.md).