zk identity registry proposal

When working with cryptographic systems, determinism is critical - the same input must always produce the same output. However, a hiccup emerges with Ethereum signatures.

ECDSA signatures include an arbitrary nonce - a number used once or very infrequently. The signer can alter this nonce to generate different signatures from the same payload. The result? Non-determinism - different outputs from the same input.

This non-determinism becomes a hurdle when calculating a nullifier, an essential tool in preventing double voting. A nullifier is a unique identifier for each vote. When a vote is cast, the nullifier is logged in a public list on the blockchain.

Generating a deterministic nullifier requires a deterministic signature scheme. And because ECDSA signatures are non-deterministic, they don’t play nice with nullifier generation. So, we hit a roadblock when trying to stop double votes in an anonymous binding voting system on Ethereum.

The global identity zk-registry

We introduce the concept of the global identity zk-registry, a sophisticated Ethereum Smart Contract devised to manage a list of secret identity keys (SIKs), each intricately linked to its respective Ethereum address. The SIK is forged through the hashing of two concatenated fields: ethereum_address + user_secret. The secret can manifest as a password, a hashed ECDSA signature, or a potent amalgamation of both, offering a versatile foundation for secure identity management.

The key-address compilation resides in a Snark-Friendly Merkle tree, a choice grounded in its ability to foster a tamper-resistant and efficient environment for storing and verifying substantial data volumes — a pivotal requirement in our endeavor.

In this Merkle tree, the user's Ethereum address delineates the path to a specific leaf, a journey orchestrated through a systematic index. At the end of this path lies the leaf value, a hashed representation of the SIK, encapsulating the user's secret in a cryptographic embrace. Below, we illustrate a prototype showcasing the meticulous architecture of this data structure:

To facilitate a cost-effective and scalable smart contract execution, we retain solely the current root hash of the tree. The caller is tasked with constructing a zkSnark proof, authenticated by the contract, substantiating the following:

1. The transition from the old-root to the new-root is valid, ensuring a legitimate evolution of the tree with the incorporation of new data.
2. The sole alteration executed on the tree is the addition of N addresses, maintaining the integrity of the existing data.
3. None of the N addresses previously housed a valid leaf, averting duplications and preserving the uniqueness of each entry.
4. The N addresses and their corresponding SIKs are delineated as public inputs of the circuit and appended to the smart contract call data, facilitating transparency and verification.
5. Each of the N addresses bears a signature over the respective SIK, affirming the authenticity of the data introduced.

Note that the Signature provided to the circuit must be salted with a specific text, such as "I understand this signature validates the creation of my SIK into the identity zk-registry" to ensure the user is aware of its action when signing.

Concurrent Transactions Issue

In the current zk-registry setup, simultaneous transactions pose a significant problem. If two users attempt to add their SIKs to the Merkle tree at the same time, the transaction initiated by the second user will fail. This failure occurs because the root of the tree would have already altered due to the first transaction, resulting in a mismatch of the old-root value for the second transaction. This scenario highlights a concurrency issue that needs to be addressed to allow for seamless simultaneous transactions.

Solution: zkRollup Service

To remedy the concurrency issue, we propose the implementation of a zkRollup service. This service will act as an intermediary, accumulating the input data for the circuit from various users. It will then aggregate these multiple root transitions into a single transition by incorporating several addresses and SIKs within the same zkSnark proof. Consequently, this facilitates a batch processing of transactions, ensuring efficiency and avoiding conflicts arising from simultaneous submissions.

Data availability and reproducibility

To ensure the enduring availability and reproducibility of the data, the full Merkle tree data can be hosted on IPFS by the zkRollup service, with the option for it to be pinned by various actors, enhancing its accessibility and permanence.

In the event of a service disruption or failure in the IPFS service, any entity can initiate a recovery process by aggregating all transactions dispatched to the Smart Contract from its inception. Leveraging the call data — which records the addresses and SIKs involved in each root transition — one can reconstruct the most recent state of the Merkle tree, thereby ensuring the continuity and integrity of the zkRegistry.

---

Secret Identity Key (SIK) registry
When working with cryptographic systems, determinism is critical—the same input must always produce the same output. However, a hiccup emerges with Ethereum signatures.

ECDSA signatures include an arbitrary nonce—a number used once. The signer can alter this nonce to generate different signatures from the same payload.

Generating a deterministic nullifier requires a deterministic signature scheme. Because ECDSA signatures are non-deterministic, they don’t align with nullifier generation.

We introduce the concept of a SIK Registry, an Ethereum smart contract devised to manage a list of Secret Identity Keys (SIKs), each intricately linked to its respective Ethereum address. The SIK is forged by hashing two concatenated fields: ethereum_address + user_secret (the secret can be a password).

The key-address compilation resides in a SNARK-friendly Merkle tree, where the user's Ethereum address delineates the path to a specific leaf. The leaf value is a hashed representation of the SIK.

Process
To securely and efficiently update the SIK Merkle tree while ensuring data availability and integrity, we utilize:
EIP-4844 Blobs: Store new addresses and SIKs off-chain in blobs, reducing on-chain data costs.
zkSNARKs: Prove the validity of Merkle tree updates without revealing sensitive data on-chain.

1. Data Submission
   New addresses and SIKs are stored in a blob (EIP-4844).
   A KZG commitment of the blob is included in the transaction.
2. zkSNARK Proof Generation
   Proves the following:
   Valid Tree Transition: The transition from the old Merkle root to the new root is valid.
   Single Operation Addition: Only the addition or update of SIKs has occurred.
   Signature Authenticity: Each address has signed its corresponding SIK.

Public inputs:
old_root: Current Merkle tree root.
new_root: Updated Merkle tree root.
blob_commitment: KZG commitment of the blob containing new data.

Private Inputs
addresses: List of new Ethereum addresses.
SIKs: Corresponding Secret Identity Keys.
signatures: Signatures from each address over its SIK.
3. Smart Contract Verification
Verifies the zkSNARK proof.
Ensures the blob_commitment matches the commitment in the transaction.
Updates the Merkle root if verification succeeds.

4. Data Availability
   Participants retrieve blob data using the blob_commitment.
   Store data off-chain for future updates.