zk-smps v1.0.0

About ZK-SMPS

This repository contains a proving scheme made for the Sismo Protocol and used in ZK-SMPS attester. This proving scheme was built agnostic to our protocol. We invite other teams to reuse it for other use cases.

A proving scheme is composed by a prover and a verifier. The prover generates a ZK proof depending on inputs and the verifier verify if a proof is correct or not.

This proving scheme allows a user to prove that he is in a Merkle Tree with one Ethereum account (his source) and link this information to another Ethereum account (his destination). The Merkle tree also allows to associate a value to each address which allows to bring more informations on the source address to the destination.

How does it work ?

Data source

Ethereum accounts and their value are stored in a Merkle Tree, here labeled as AccountMerkleTree. Each AccountMerkleTree has its root located inside the WorldMerkleTree at a specific leaf position. The position of the Account in the World Merkle Tree defines if the value is a score or an information. If the position is even, it's an information, if it's not it's a score.

A score can be downgraded, for example if it's the Ether balance the user must choose what he reveel about himself. An information can not be downgraded, for example if we want to store a nationality in the value, we do not want that a user downgrade his value and change his nationality.

If a leaf of an AccountMerkleTree is update the WorldMerkleTree must be update too.

Zero-Knowledge

In order to have no link between the source and the destination account we use zkSNARK circuits made by CIRCOM which allow us to create ZK proofs. More informations

Commitment Mapper

The commitment Mapper ensure : 1. Ethereum address ownership 2. Only one nullifier can be used by Ethereum address

The commitment mapper is a trusted sever which store in a map all commitments related to an address.

The user sends his Ethereum address, a signature and his commitment which is hash(secret) to the commitment mapper. When the user send his commitment he verify if the address is already stored in the map. If it's already stored and if the commitment stored is not equal to the commitment it's throw an error, the user is trying to use a different nullifier than before. If not, the server send back to the user a receipt to validate the commitment in his map.

This is an alternative to the Semaphore commitment step. With the third party commitment mapper, the anonimity set constituted by users commitments is hidden.

Here you can find a comparison of tradeoff between them:

Check commitment receipt in circuits

This receipt emit by the commitment mapper is a signature of poseidonHash(EthAddress, commitment). In the circuit the user send in private input his secret which allow us to re-create the message and verrify if the signature is valid with the commitment mapper public key which is provided in public inputs.

In practice, verifiing signatures of Ethereum addresses (ECDSA) with a zkSNARK circuit takes too much time to compute (circom-ecdsa 1.5M constraint and 1Go proving key). To solve this issue, we use the EdDSA digital signature scheme verification inside the zkSNARK circuit, which is much more faster (5k constraint).

Getting Started

Prover

Javascript/Typescript (docs)

yarn add @sismo-core/zksmps-prover-js

Verifier

Javascript/Typescript (docs)

yarn add @sismo-core/zksmps-verifier-js

Solidity (docs)

yarn add @sismo-core/zksmps-verifier-contracts

Commitment Mapper Tester

Javascript/Typescript (docs)

yarn add @sismo-core/zksmps-commitment-mapper-tester-js

Contributing

Contributions are welcome, do not hesitate to open a PR or to contact us.

The best way to contact us is to join our discord.

Installation

Circom2

install circom2 (rust version)

Build

yarn build

This command will execute theses commands :

yarn clean // Remove all generated files
yarn install // Install dependencies mandatory to compile circuits
yarn compile-circuits 
yarn bootstrap // Run yarn install + yarn prepare in all packages
yarn build:all // Run yarn build in all packages

Test

yarn test
yarn test:prover
yarn test:verifier

Deployed Contract Address

Sismo deployed the verifier contract of the ZK-SMPS at:

• Mainnet: 0x1
• Polygon: 0x2

The link between the ZK-SMPS and the Sismo Protocol is made through attesters. Deployed and live attesters can be found on the sismo-protocol repository.

Cryptography

Poseidon Hash

Famously known Hash functions as keccak256 require a huge number of constraint in zk-snark. (for example keccak256-circom require 151k constraint).
Poseidon hash is a ZK-friendly Hashing that use only 400 constraints to execute inside a snark circuits.

AccountMerkleTree

An AccountMerkleTree is a merkleTree implementation created for this proving scheme that is defined as below:

• Hash function: Poseidon
• Leaf encoding: EthereumAddress | balance(or arbitrary value) .
• Height: variable, can vary between 0 and 32 levels.

WorldMerkleTree

A WorldMerkleTree is a merkleTree implementation that encode the root of each AccountMerkleTree in its leafs.

• Hash function: Poseidon
• Leaf encoding: AccountMerkleRoot | AccountMerkleHeight
• Height: hardcoded to 13 levels, which corresponds to 8192 leafs or 8192 different AccountMerkleTrees. This is an optimisation that allows to update all AccountMerkleTrees root in one transaction by simply updating the WorlMerkleTree root onchain.

EdDSA

Edward-curve Digital Signature Algorithm is a digital signature scheme which has the particularity of beeing easily verified inside a Snark circuit. This digitail signature has been implemented inside the circomlib library using Poseidon hash function and the BabyJubJub elliptic curve. This digital signature along its implementation allows to verify a signature for a small number of constraint (~ 5k)

NullifierHash

This proving scheme implements the concept of NullifierHash for beeing able to generate a deterministic trace from the ethereum source account, without being bruteforcable. A secret is used as the sourceIdNullifier. An externalNullifier is easily customizable.
NullifierHash = Hash(sourceIdNullifier, externalNullifier)

License

Distributed under the MIT License. See LICENSE.txt for more information.

Contact

Prefer Discord or Twitter

Project Link: https://github.com/sismo-core/ZK-SMPS