_images/iden3-icon2.png

Iden3 Documentation Site

Iden3 is an open source project offering a complete decentralized identity management solution over the public blockchain. It is designed with four fundamental goals in mind:

Enable Self Sovereign Identities, whereby identities are created, owned and controlled by the user.

Accesibility, by promoting the development of open standards and ease of use.

Scalability, by minimizing the number of accesses to the blockchain that identity management and claim processing requires.

Privacy by design by using including zkSNARKs to prove claims whithout revealing any information other than the validity of the claim.

Note

Our team can always use your feedback and help to improve the tutorials and material included. If you don’t understand something, or cannot find what you are looking for, or have any suggestion, help us make the documentation better by letting us know!

Submit an issue or pull request on the GitHub repository

This documentation site includes the following sections:

  • Technology : provides a description of iden3’s technology.
  • Developers : guide on how to integrate iden3’s software for specific applications.
  • Repository Guide : centralizes documentation scattered across different iden3’s repos in a single place.
  • Publications : includes articles and papers authored by iden3.

During the comming months, we will be sorting, improving and extending the documentation, so don’t forget to come back. Thank you!!!

Terminology

Claims

Identity

Merkle Tree

Zero Knowledge

Services & Protocols

Login Protocol

Login protocol

The login protocol is based on the signature protocol, in which a user signs a packet using an authorized kSign key.

For the login case, the user desires to assert a particular identity (an ethereum address in this case) to a server so that they are allowed access into the service while being identified.

image0

Assumptions
  • Secure connection between Wallet and Server.
  • Secure connection between Web Client and Server.
  • Wallet authenticates the Server in the connection.
  • Web Client authenticates the Server in the connection.
What is needed
  • Server authenticates the Ethereum Address and Ethereum Name from the Wallet.
  • The user transfers the authentication from the Wallet to the Web Client.
Protocol flow

image1

Challenges contain a cryptographic nonce and have a timeout that indicates the validity of the nonce in the challenge. A signed challenge with a timed out nonce must be rejected by the server. The server must store a list of not timed out nonces that haven’t been signed yet to guarantee freshness.

A cryptographic nonce must be securely generated and long enough to avoid colisions (we use 256 bits).

Signature Protocol v0.1 spec

A signature may be requested as follows:

{
  header: {
    typ: iden3.sig.v0_1
  }
  body: {
    type: TYPE
    data: DATA
  }
}

The user will generate a packet following the signature protocol specification, that may contain data from a signature request, or may be made from scratch. The packet contains a header and a payload, and is serialized and signed following the JWS standard. Usually the form will be filled by the user, and data will be copied from a request.

The structure of the data and form in the payload are specified by the type (what is being signed) in the payload. The rest of the elements are specified by the typ (signature packet) in the header.

JWS_PAYLOAD = {
  type: TYPE
  data: DATA
  form: FORM
  ksign: str # ksing public key in compressed form
  proofKSing: proofClaim # Proof of authorize k sign claim (which contains the public key in compressed form)
}

JWS_HEADER = {
  typ: iden3.sig.v0_1
  iss: str # Ethereum Address
  iat: uint # issued at time, unix timestamp
  exp: uint # expiration time, unix timestamp
  alg: ? # algorithm
}

JWS_SIGN(JWS_HEADER, JWS_PAYLOAD)

Each Signature request type has a view representation for the user, where the data and form are presented. Some of the values may be hidden from the user when necessary, but only if doing so doesn’t compromise the security of the user. In the request view, the user has the ability to pick some elements of the form.

ksign is the compressed public key of a secp256k ECDSA key pair. The proofKSing contains a KSign Authorize Claim for a secp256k public key.

As JWS_HEADER.alg we will use a custom algorithm (not defined in the JWS standard): “EK256K1”, which is ECDSA with secp256k1 curve and keccak as hash function, the same signature algorithm configuration used in Ethereum.

Auxiliary data structures
proofClaim: {
    signature: signature # Relay root + date signed by relay
    date: uint
    leaf: claim
    proofs: proofClaimPartial[]
}

proofClaimPartial: {
    mtp0: mtp # merkle tree proof of leaf existence
    mtp1: mtp # merkle tree proof of leaf non-existence
    root: key # merkle tree root
    aux: nil | { ver: uint, era: uint, idAddr: str } # Necessary data to construct SetRootClaim from root
}

Usually the relay returns the proofClaim data structure to prove that a claim is valid and is in the merkle tree.

Identity Assertion v0.1 spec

payload:

type: iden3.iden_assert.v0_1
data: {
  challenge: nonce # 256 bits in base64
  timeout: uint # seconds
  origin: str # domain
}
form: {
  ethName: str # ethereumName
  proofAssignName: proofClaim # proof of claim Assign Name for ethName
}

A session id, if necessary, can be computed from the challenge. This session id can be used to link the communication between the web service and the wallet service.

view:

type: Identity Assertion
data: {
  origin: str # domain
}
form: {
  ethName: str # ethereum name
}
Algorithms

Here we show an overview of the algorithms steps used for verification of the proofs and signatures used in the login protocol. The following algorithms consider the case in which there is a only a single trusted entity (identified by relayPk) that acts as a relay and as a domain name server.

Signature verification algorithm
VerifySignedPacket(jwsHeader, jwsPayload, signature, relayPk):
1. Verify jwsHeader.typ is 'iden3.sig.v0_1'
2. Verify jwsHeader.alg is 'EK256K1'
3. Verify that jwsHeader.iat <= now() < jwsHeader.exp
4. Verify that jwsPayload.ksign is in jwsPayload.proofKSign.leaf
5. Verify that jwsHeader.iss is in jwsPayload.proofKSign
6. Verify that signature of JWS(jwsHeader, jwsPayload) by jwsPayload.ksign is signature
7. VerifyProofOfClaim(jwsPayload.proofKSign, relayPk)

In 4. we verify that the ksign used to sign the packet is authorized by the user, identified by jwsHeader.iss ethereum address.

Iden Assert verification algorithm
VerifyIdenAssertV01(nonceDB, origin, jwsHeader, jwsPayload, signature, relayPk):
1. Verify jwsPayload.type is 'iden3.iden_assert.v0_1'
2. Verify jwsPayload.data.origin is origin
3. Verify jwsPayload.data.challenge is in nonceDB and hasn't expired, delete it
4. Verify that jwsHeader.iss and jwsPayload.form.ethName are in jwsPayload.proofAssignName.leaf
5. VerifyProofOfClaim(jwsPayload.form.ethName, relayPk)
ProofOfClaim verification
VerifyProofOfClaim(p, relayPk):
1. Verify signature of p.proofs[-1].root by relayPk is p.signature
   let leaf = p.leaf
2. loop for each proof in p.proofs:
    2.1 Verify proof.mtp0 is existence proof
    2.2 Verify proof.mtp0 with leaf and proof.root
    2.3 Verify proof.mtp1 is non-existence proof
    2.4 Verify proof.mtp1 with ClaimIncrementVersion(leaf) and proof.root
        leaf = NewClaimSetRootClaim(p.root, p.aux.ver, p.aux.era, p.aux.ethAddr)
Rationale

See this document for the rationale of some decisions made in the design of this protocol.

iden3js - protocols

Login (Identity Assertion)
Wallet                                   Service
  +                                         +
  |           signatureRequest              |
  | <-------------------------------------+ |
  |                                         |
  | +---+                                   |
  |     |                                   |
  |     |sign packet                        |
  |     |                                   |
  | <---+                                   |
  |              signedPacket               |
  | +-------------------------------------> |
  |                                         |
  |                                  +---+  |
  |                      verify      |      |
  |                      signedPacket|      |
  |                                  |      |
  |                                  +--->  |
  |                                         |
  |                 ok                      |
  | <-------------------------------------+ |
  |                                         |
  |                                         |
  |                                         |
  +                                         +

Read the login protocol specification here.

Define new NonceDB
const nonceDB = new iden3.protocols.NonceDB();
Generate New Request of Identity Assert

  • input

    • nonceDB: NonceDB class object
    • origin: domain of the emitter of the request
    • timeout: unixtime format, valid until that date. We can use for example 2 minutes (2*60 seconds)

  • output

    • signatureRequest: Object
    const signatureRequest = iden3.protocols.login.newRequestIdenAssert(nonceDB, origin, 2*60);

The nonce of the signatureRequest can be getted from:

const nonce = signatureRequest.body.data.challenge;
// nonce is the string containing the nonce value

We can add auxiliar data to the nonce in the nonceDB only one time:

const added = nodeDB.addAuxToNonce(nonce, auxdata);
// added is a bool confirming if the aux data had been added
Sign Packet

  • input

    • signatureRequest: object generated in the newRequestIdenAssert function
    • userAddr: Eth Address of the user that signs the data packet
    • ethName: name assigned to the userAddr
    • proofOfEthName: proofOfClaim of the ethName
    • kc: iden3.KeyContainer object
    • ksign: KOperational authorized for the userAddr
    • proofOfKSign: proofOfClaim of the ksign
    • expirationTime: unixtime format, signature will be valid until that date

  • output

    • signedPacket: String
    const expirationTime = unixtime + (3600 * 60);
const signedPacket = iden3.protocols.login.signIdenAssertV01(signatureRequest, usrAddr, ethName, proofOfEthName, kc, ksign, proofOfKSign, expirationTime);
Verify Signed Packet

  • input

    • nonceDB: NonceDB class object
    • origin: domain of the emitter of the request
    • signedPacket: object generated in the signIdenAssertV01 function

  • output

    • nonce: nonce object of the signedPacket, that has been just deleted from the nonceDB when the signedPacket is verified. If the verification fails, the nonce will be undefined
    const verified = iden3.protocols.login.verifySignedPacket(nonceDB, origin, signedPacket);
Apendix

See the login specification document for information about the protocol design.

Rationale

The following document contains references to similar protocols on which our login protocol relies on or takes inspiration from.

Signature format

Use JSON to encode the object that will be signed.

JSON Signing formats

https://medium.facilelogin.com/json-message-signing-alternatives-897f90d411c

  • JSON Web Signature (JWS)
    • Doesn’t need canonicalization
    • Allows signing arbitrary data (not only JSON)
    • Widely used
  • JSON Cleartext Signature (JCS)
  • Concise Binary Object Representation (CBOR) Object Signing

https://matrix.org/docs/spec/appendices.html#signing-json

  • Matrix JSON Signing
    • Allows having multiple signatures with different protocols for a single JSON
Possible attacks

See WebAuth API, FIDO Threat analysis

Apendix
The FIDO protocols security goals:
[SG-1]

Strong User Authentication: Authenticate (i.e. recognize) a user and/or a device to a relying party with high (cryptographic) strength. #### [SG-2] Credential Guessing Resilience: Provide robust protection against eavesdroppers, e.g. be resilient to physical observation, resilient to targeted impersonation, resilient to throttled and unthrottled guessing. #### [SG-3] Credential Disclosure Resilience: Be resilient to phishing attacks and real-time phishing attack, including resilience to online attacks by adversaries able to actively manipulate network traffic. #### [SG-4] Unlinkablity: Protect the protocol conversation such that any two relying parties cannot link the conversation to one user (i.e. be unlinkable). #### [SG-5] Verifier Leak Resilience: Be resilient to leaks from other relying parties. I.e., nothing that a verifier could possibly leak can help an attacker impersonate the user to another relying party. #### [SG-6] Authenticator Leak Resilience: Be resilient to leaks from other FIDO Authenticators. I.e., nothing that a particular FIDO Authenticator could possibly leak can help an attacker to impersonate any other user to any relying party. #### [SG-7] User Consent: Notify the user before a relationship to a new relying party is being established (requiring explicit consent). #### [SG-8] Limited PII: Limit the amount of personal identifiable information (PII) exposed to the relying party to the absolute minimum. #### [SG-9] Attestable Properties: Relying Party must be able to verify FIDO Authenticator model/type (in order to calculate the associated risk). #### [SG-10] DoS Resistance: Be resilient to Denial of Service Attacks. I.e. prevent attackers from inserting invalid registration information for a legitimate user for the next login phase. Afterward, the legitimate user will not be able to login successfully anymore. #### [SG-11] Forgery Resistance: Be resilient to Forgery Attacks (Impersonation Attacks). I.e. prevent attackers from attempting to modify intercepted communications in order to masquerade as the legitimate user and login to the system. #### [SG-12] Parallel Session Resistance: Be resilient to Parallel Session Attacks. Without knowing a user’s authentication credential, an attacker can masquerade as the legitimate user by creating a valid authentication message out of some eavesdropped communication between the user and the server. #### [SG-13] Forwarding Resistance: Be resilient to Forwarding and Replay Attacks. Having intercepted previous communications, an attacker can impersonate the legal user to authenticate to the system. The attacker can replay or forward the intercepted messages. #### [SG-14] (not covered by U2F) Transaction Non-Repudiation: Provide strong cryptographic non-repudiation for secure transactions. #### [SG-15] Respect for Operating Environment Security Boundaries: Ensure that registrations and private key material as a shared system resource is appropriately protected according to the operating environment privilege boundaries in place on the FIDO user device. #### [SG-16] Assessable Level of Security: Ensure that the design and implementation of the Authenticator allows for the testing laboratory / FIDO Alliance to assess the level of security provided by the Authenticator.

Claim Server

Identity Management System

Name Server

Notification Server

Relayer

Wallet

Centralized Login Use Case

Overview

This document will guide you through the steps required to integrate iden3’s technology into your application’s login.

Date:2019-04-05

Introduction

Iden3 is a complete decentralized identity management solution that allows users to leverage their pre-existing validated identities to proof they are who they claim to be, saving them the hassle of having to individually register with each service that requires a validated identification. One of the direct applications of iden3’s technology is to allow web services to reuse these identities for login into their portals.

The diagram below shows the steps taken by your back-end to enable access to your application using iden3 identity system once the user requests to login.

alternate text

Iden3 provides the SDK to take care of requesting and verifying identity so that the user can be authenticated.

Pre-requirements

Minimum requirements for a functional centralized login include:

  1. iden3 wallet service has been deployed
  2. User attempting to login has at least one valid identity.

Integration

A JavaScript reference implementation of how a third party can integrate iden3’s solution to login into their application can be found at https://github.com/iden3/centralized-login-demo. In this example the external service includes a front-end and a back-end server. We will assume this front-end/back-end division during our integration overview.

Some examples on how the Go implementation is used can be found at https://github.com/iden3/go-iden3/blob/master/services/signedpacketsrv/signedpacket_test.go

Front-End

On the front-end side you will typically need to embed a button to start the login process, and a place to display a QR code that the user can scan to complete the authentication. After the button is pressed, the front-end makes a request to the back-end to start the identity authentication and waits for the response containing the QR code to be displayed and scanned by the user.

In the provided reference implementation this is achieved by JavaScript function getLoginData() found in frontend/index.js. This code shows how to :

  • Send a request for a new requestIdenAssert packet to the centralized application back-end
  • Open a websocket between front-end and back-end
  • Display QR code containing the requestIdenAssert packet to be signed by iden3’s wallet

Back-End

Generating requests of identity assertion

On the back-end side you will need to prepare a new API endpoint to handle the requestIdenAssert() petitions from the front-end. In the reference implementation we use GET/login by calling JavaScript function

const signatureRequest = iden3.protocols.login.newRequestIdenAssert(nonceDB, origin, timeout);

or Go function:

requestIdenAssert := NewRequestIdenAssert(nonceDb, origin, timeout)

where

  • nonceDB: is a NonceDB object generated by calling an API function and stored in a RAM database
  • origin: domain of the emitter of the request, for example ‘myweb.com’
  • timeout: timeout in seconds, for example 2 minutes (120).

nonceDB is obtained by calling the following JavaScript function:

const nonceDB = new iden3.protocols.NonceDB();

or Go function:

Once you have the signatureRequest object, you can return it back to the front-end so that it can be displayed.

Verifying signedPacket

On the back-end you will also need to prepare a new API endpoint to handle the responses from iden3 wallet containing the signedPacket. In the reference implementation we use POST /login to allow the walled to send the signed data.

To perform the verification in the newly added endpoint you just need to call iden3js library:

const verified = iden3.protocols.login.verifySignedPacket(nonceDB, origin, signedPacket);

or go-iden3 library:

verified, err := signedPacketVerifier.
        VerifySignedPacketIdenAssert(signedPacket, nonceDB, origin)

where

  • nonceDB: is the NonceDB object generated earlier.
  • origin: domain of the emitter of the request, for example ‘myweb.com’
  • signedPacket: signed packet sent by iden3’s wallet.
  • verified: is null if verification fails.

SDK installation

iden3js

Installation
npm install --save @iden3/iden3
Import
const iden3 = require('iden3');

go-iden3

Installation
go get github.com/iden3/go-iden3
Import
import { "github.com/iden3/go-iden3/services/signedpacketsrv" }

Services and Infrastructure

Basic services and infrastructure libraries.

Repo Description
iden3js Javascript client library
go-iden3 Go implemenation of the iden3 system
tx-forwarder Implementation of server that pays gas on behalf of user signed transactions for specified smart contracts in ethereum blockchain
discovery-node Decentralized discovery protocol implementation
notification-server Implementation of a notification server to push notifications to user identity wallets

Iden3js

Overview

iden3js

Javascript client library of the iden3 system.

Build Status

Install
npm install --save @iden3/iden3

https://www.npmjs.com/package/@iden3/iden3

Basic usage
// import iden3js
const iden3 = require('@iden3/iden3');

// Simulate local storage locally if no browser is used
// if (typeof localStorage === 'undefined' || localStorage === null) {
//   const LocalStorage = require('node-localstorage').LocalStorage;
//   localStorage = new LocalStorage('./tmp');
// }

// It should be noted that if no babel is installed on `package.json` dependencies,
// next dependencies should be add to `dependecies` section on `package.json`:
// "babel-plugin-transform-class-properties": "^6.24.1",
// "babel-plugin-transform-runtime": "^6.23.0",


// new database
const db = new iden3.Db();
// new key container using localStorage
const keyContainer = new iden3.KeyContainer('localStorage', db);

// unlock the KeyContainer for the next 30 seconds
let passphrase = 'pass';
keyContainer.unlock(passphrase);

// generate master seed
const mnemonic = 'enjoy alter satoshi squirrel special spend crop link race rally two eye';
keyContainer.generateMasterSeed(mnemonic);

// Generate keys for first identity
const keys  = keyContainer.createKeys();

/*
  keys: [
    '0xc7d89fe96acdb257b434bf580b8e6eb677d445a9',
    '0x03c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff57833',
    '0xf3c9f94e4eaffef676d4fd3b4fc2732044caea91',
    '0xb07079bd6238fa845dc77bbce3ec2edf98ffe735'
  ];
*/
// It should be noted that 'keys' are in form of ethereum addresses except
// key[1] that is a pubic key in its compressed form
let keyAddressOp = keys[0];
let keyPublicOp = keys[1];
let keyRecover = keys[2];
let keyRevoke = keys[3];

// For more info and details about mnemonic, see section Usage > KeyContainer

// create a new relay object
const relayAddr = '0xe0fbce58cfaa72812103f003adce3f284fe5fc7c';
const relayUrl = 'http://127.0.0.1:8000/api/unstable';
const relay = new iden3.Relay(relayUrl);

// create a new id object
let id = new iden3.Id(keyPublicOp, keyRecover, keyRevoke, relay, relayAddr, '', undefined, 0);

// generates the counterfactoual contract through the relay, get the identity address as response
let proofKsign = {};

console.log('Create Identity');
id.createID()
  .then((createIdRes) => {
    // Successfull create identity api call to relay
    console.log(createIdRes.idAddr); // Identity counterfactoual address
    proofKsign = createIdRes.proofClaim;
    console.log(proofKsign); // Proof of claim regarding authorization of key public operational

    console.log('Create and authorize new key for address');
    // generate new key from identity and issue a claim to relay in order to authorize new key
    const keyLabel = 'testKey';
    const newKey = id.createKey(keyContainer, keyLabel, true);
    id.authorizeKSignSecp256k1(keyContainer, id.keyOperationalPub, newKey)
      .then((authRes) => {
        proofKSign = authRes.data.proofClaim;
        console.log(proofKSign);
      })
    .catch((error) => {
      console.error(error.message);
    });

    console.log('Bind label to an identity');
    // bind the identity address to a label. It send required data to name-resolver service and name-resolver issue a claim 'assignName' binding identity address with label
    const name = 'testName';
    id.bindID(keyContainer, name)
      .then( (bindRes) => {
        console.log(bindRes.data);
        // request idenity address to name-resolver ( currently name-resolver service is inside relay) from a given label
        relay.resolveName(`${name}@iden3.io`)
          .then((resolveRes) => {
            const idAddr = resolveRes.data.idAddr;
            console.log(`${name}@iden3.io associated with addres: ` + idAddr);
          })
          .catch((error) => {
            console.error(error.message);
          });
      })
      .catch((error) => {
        console.error(error.message);
      });

    console.log('Deploy identity smart contract');
    // creates identity smart contract on the ethereum blockchain testnet
    id.deployID()
      .then((deployIdRes) => {
        // Successfull deploy identity api call to relay
        console.log(deployIdRes.status);
      })
      .catch(() => {
        // If identity is already deployed, throws an error
        console.log('Identity already deployed');
      });
  })
  .catch((error) => {
    console.error(error.message);
  });

Example can be found in `iden3-basic-usage.example.js <https://github.com/iden3/iden3js/blob/master/examples/iden3-basic-usage.example.js>`__

Centralized login

In the next links, one can be found an example of iden3 implementation as well as the login protocol explained in detail

Usage
Import 
const iden3 = require('iden3');
KeyContainer
  • new KeyContainer using localStorage
// new key container
// new database
const db = new iden3.Db();
let keyContainer = new iden3.KeyContainer('localStorage');
  • usage:
// unlock the KeyContainer for the next 30 seconds
let passphrase = 'pass';
keyContainer.unlock(passphrase);

// generate master seed
const mnemonic = 'enjoy alter satoshi squirrel special spend crop link race rally two eye';
keyContainer.generateMasterSeed(mnemonic);

// Also, master seed can be generated randomly if no mnemonic is specified
// keyContainer.generateMasterSeed();

// functions above stores seed mnemonic into local storage
// it can be retrieved through:
const mnemonicDb = keyContainer.getMasterSeed();

// Generate keys for first identity
const keys = keyContainer.createKeys();
/*
  keys: [
    '0xc7d89fe96acdb257b434bf580b8e6eb677d445a9',
    '0x03c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff57833',
    '0xf3c9f94e4eaffef676d4fd3b4fc2732044caea91',
    '0xb07079bd6238fa845dc77bbce3ec2edf98ffe735'
  ];
*/
// Each time 'keyContainer.createKeys()' is called, a new set of keys for an identity is created

// Retrieve key seed and its current derivation path
const { keySeed, pathKey } = keyContainer.getKeySeed();

// It should be noted that 'keys' are in form of ethereum addresses except
// key[1] that is a pubic key in its compressed form
const keyAddressOp = keys[0];
const keyPublicOp = keys[1];
const keyRecover = keys[2];
const keyRevoke = keys[3];
Identity 
const db = new iden3.Db();
const keyContainer = new iden3.KeyContainer('localStorage', db);
const passphrase = 'pass';
keyContainer.unlock(passphrase);

// new relay
const relay = new iden3.Relay('http://127.0.0.1:8000/api/unstable');
const relayAddr = '0xe0fbce58cfaa72812103f003adce3f284fe5fc7c';
const relay = new iden3.Relay(relayUrl);

// create identity object with a set of keys
const keyPath = 0;
const id = new iden3.Id(keyPublicOp, keyRecover, keyRevoke, relay, relayAddr, '', undefined, keyPath);
id.createID

Creates the counterfactual contract through the Relay, and gets the identity address When an identity is created, all its keys are automatically stored

id.createID().then(res => {
  console.log(res.idAddr);
  console.log(res.proofClaim);
});

// Return : - idAddr: Address identity identifier
//          - proofOfClam: Structure of the claim emitted by the relay authorizing its key public operational
idAddr = 0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22;
proofClaim = {
  date: 1549531663,
  leaf:'000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff50000000000000000000000000000000000007833000000000000000000000004',
  proofs: [{
    aux: {
      era: 0,
      idAddr: '0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22',
      version: 0
    }
    mtp0: '0000000000000000000000000000000000000000000000000000000000000000',
    mtp1: '030000000000000000000000000000000000000000000000000000000000000028f8267fb21e8ce0cdd9888a6e532764eb8d52dd6c1e354157c78b7ea281ce801541a6b5aa9bf7d9be3d5cb0bcc7cacbca26242016a0feebfc19c90f2224baed',
    root: '1d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c3922',
  } , {
    aux: null
    mtp0: '0000000000000000000000000000000000000000000000000000000000000000',
    mtp1: '0300000000000000000000000000000000000000000000000000000000000000182adc955c46e6629ac74027ded0c843c7c65e8c3c4f12f77add56500f9f402e25451237d9133b0f5c1386b7b822f382cb14c5fff612a913956ef5436fb6208a',
    root: '083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f8199',

  }],
  signature:'440ec709297ecb6a7f7a200719c29d96025a893aef7318cebdcec401e3c8b3b711358f5a3c14394dc120b067ade86d7eca0c79be580d35934cc36dc246be6ec000',
}
id.createKey 
// Create new key for this identity and bind it to a label
const labelKey = 'test key'
const loginKey = id.createKey(keyContainer, labelKey);
console.log(loginKey);

// Return : New key created
loginKey = '0xaac4ed37a11e6a9170cb19a6e558913dc3efa6a7';
id.getKeys 
// Retrieve all keys that have been created for this identity
const keysIdentity = id.getKeys();
console.log(keysIdentity);

// Return : Object containing all the keys associated with the identity
{
  operationalPub:"0x03c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff57833",
  recover:"0xf3c9f94e4eaffef676d4fd3b4fc2732044caea91",
  revoke:"0xb07079bd6238fa845dc77bbce3ec2edf98ffe735",
  test key:"0xaac4ed37a11e6a9170cb19a6e558913dc3efa6a7",
}
id.deployID

Deploys the counterfactual smart contract of identity to the blockchain.

id.deployID().then(res => {
  console.log(res.data);
});
// Return object: - idAddr: Address identity identifier
//                - tx: transaction identifier of the deploying identity smart contract on the blockchain
id.bindID

Vinculates a label to an identity. It sends required data to name-resolver service and name-resolver issue a claim ‘assignName’ binding identity address with a label

const name = 'testName';
id.bindID(kc, name).then(bindRes => {
  console.log(bindRes.data);
});
  • Output:
// Return object: - claimAssigName: hexadecimal representation of claim data
//                - idAddr: ethereum addres to bind to the label
//                - name: label binded to the ethereum address
//                - proofClaimAssignName: full proof of existance of the claim issued by the name-resolved
{
  claimAssigName: '0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000007b471a1bdbd3b8ac98f3715507449f3a8e1f3b22008c8efcda9e563cf153563941b60fc5ac88336fc58d361eb0888686fadb99760000000000000000000000000000000000000000000000000000000000000003',
  idAddr: '0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22',
  name: 'testName',
  proofClaimAssignName: {
    date:1549532610,
    leaf:'00000000000000000000000000000000000000000000000000000000000000000000000000000000000000007b471a1bdbd3b8ac98f3715507449f3a8e1f3b22008c8efcda9e563cf153563941b60fc5ac88336fc58d361eb0888686fadb99760000000000000000000000000000000000000000000000000000000000000003',
    proofs:[{
      aux: null,
      mtp0:'0001000000000000000000000000000000000000000000000000000000000001083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f8199',
      mtp1:'03010000000000000000000000000000000000000000000000000000000000010fef40cc16896de64be5a0f827799555344fd3d9aade9b65d95ecfbcac3e5a73182adc955c46e6629ac74027ded0c843c7c65e8c3c4f12f77add56500f9f402e25451237d9133b0f5c1386b7b822f382cb14c5fff612a913956ef5436fb6208a',
      root:'1b6feefde6e76c1e9d98d30fa0993a7a7b35f5b2580a757c9a57ee383dc50b96',
    }],
    signature:'1e6d15ef907000937577aa06437ee2a1230713be20ff09d7628ce4dc6c902c11274f34d4ae0f9e9fc2e67cf21abe5da7f11748fc243f4013faa42e53e9c81e3e01',
  }
}
id.authorizeKSignSecp256k1 
// generate new key from identity and add issue a claim to relay in order to authorize new key
const keyLabel = 'testKey';
const newKey = id.createKey(keyContainer, keyLabel, true);

// send claim to relay signed by operational key in order to authorize a second key 'newKey'
id.authorizeKSignSecp256k1(keyContainer, id.keyOperationalPub, loginKey)
  .then((res) => {
    console.error(res.data);
  });
  • Output:
// Return object: - proofClaim: full proof of existence of the claim issued by the relay
proofClaim = {
  date: 1549534168,
  leaf:'000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000aac4ed37a11e6a9170cb19a6e558913dc3ef000000000000000000000000000000000000a6a7000000000000000000000004',
  proofs: [{
    aux: {
      era: 0,
      idAddr: '0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22',
      version: 1
    }
    mtp0: '00010000000000000000000000000000000000000000000000000000000000011d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c3922',
    mtp1: '03010000000000000000000000000000000000000000000000000000000000011d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c39221c8bdcd862752abf2dd32d16c9c3acfa20ea93cecc64d169c4550ca3e9bca20b1541a6b5aa9bf7d9be3d5cb0bcc7cacbca26242016a0feebfc19c90f2224baed',
    root: '21c6e1a81851f4017139ae8ddfbd5e894376fdd14c73cecf2a81939bae78595b',
  } , {
    aux: null
    mtp0: '0007000000000000000000000000000000000000000000000000000000000041083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f81990fef40cc16896de64be5a0f827799555344fd3d9aade9b65d95ecfbcac3e5a73',
    Mtp1: '0301000000000000000000000000000000000000000000000000000000000001081b6542453a651f2b0fea8b639a8823809f7fc032c051a644d1a8b559ba0322182adc955c46e6629ac74027ded0c843c7c65e8c3c4f12f77add56500f9f402e25451237d9133b0f5c1386b7b822f382cb14c5fff612a913956ef5436fb6208a',
    root: '1560e7b6983491305c6522c4227b98fbf26753b6a7fcb97ffb0ef7d98b271e99',

  }],
  signature:'3cedbb3d6eab5ce9a1f8bb436a080f7ec5ede3526fdcfa094fee33cbbd414d0c6d41a6650f4fdda27a66d51d87d18b4cae0adbd695ccdb152dae65a998ba61f101',
}
Claims
  • Generic claim representation: Entry
  • Claim Types:
    • Basic
    • Authorize Key to sign
    • Set root key
    • Assign name
    • Authorize key to sign secp256k1
Entry 
/**
 * Generic representation of claim elements
 * Entry element structure is as follows: |element 0|element 1|element 2|element 3|
 * Each element contains 253 useful bits enclosed on a 256 bits Buffer
 */
let entry = new iden3.Claim.Entry();
  • Entry Methods:
entry.hi(); // Hash index is calculated from: |element 1|element 0|
entry.hv(); // Hash value is calculated from: |element 3|element 2|
entry.toHexadecimal(); // Concats all the elements of the entry and parse it into an hexadecimal string
entry.fromHexadecimal(); // String deserialization into entry element structure
Basic claim 
const versionExample = 1;
const indexExample = Buffer.alloc(50);
indexExample.fill(41, 0, 1);
indexExample.fill(42, 1, 49);
indexExample.fill(43, 49, 50);
const dataExample = Buffer.alloc(62);
dataExample.fill(86, 0, 1);
dataExample.fill(88, 1, 61);
dataExample.fill(89, 61, 62);
// new basic claim
const claimBasic = new iden3.Claim.Factory(iden3.constants.CLAIMS.BASIC.ID, {
      version: versionExample, index: utils.bytesToHex(indexExample), extraData: utils.bytesToHex(dataExample),
    });
/*
claim.structure:
{
  claimType,
  version,
  index,
  extraData,
};
 * Basic entry representation is as follows:
 * |element 3|: |empty|index[0]|version|claim type| - |1 byte|19 bytes|4 bytes|8 bytes|
 * |element 2|: |empty|index[1]| - |1 bytes|31 bytes|
 * |element 1|: |empty|data[0]| - |1 bytes|31 bytes|
 * |element 0|: |empty|data[1]| - |1 bytes|31 bytes|
*/
// methods of the Basic claim
claimBasic.createEntry(); // Code raw data claim object into an entry claim object
// parse Entry into Basic claim
let entry = new Entry();
entry.fromHexadecimal(leaf); // Leaf is an hexadecimal representation of an Entry
let claimBasicParsed = iden3.claim.claimUtils.newClaimFromEntry(entry);
Authorize KSign claim 
const versionExample = 1;
const signExample = true;
const ayExample = '0x0505050505050505050505050505050505050505050505050505050505050506';
// new authorize ksign claim
const claimAuthorizeKSign = new Claim.Factory(iden3.constants.CLAIMS.AUTHORIZE_KSIGN.ID, {
  version: versionExample, sign: signExample, ay: ayExample,
});
/*
claim.structure:
{
  claimType,
  version,
  sign,
  ay,
};
 * Authorized Ksign element representation is as follows:
 * |element 3|: |empty|sign|version|claim type| - |19 bytes|1 bytes|4 bytes|8 bytes|
 * |element 2|: |Ay| - |32 bytes|
 * |element 1|: |empty| - |32 bytes|
 * |element 0|: |empty| - |32 bytes|
 */
// methods of the authorize Sign claim
claimAuthorizeKSign.createEntry(); // Code raw data claim object into an entry claim object
// parse Entry into authorize kSign claim
let entry = new Entry();
entry.fromHexadecimal(leaf); // Leaf is an hexadecimal representation of an Entry
let claimBasicParsed = iden3.claim.claimUtils.newClaimFromEntry(entry);
Set root key claim 
const versionExample = 1;
const eraExample = 1;
const idExample = '0x393939393939393939393939393939393939393A';
const rootKeyExample = '0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0c';
// new set root key ksign claim
const claimSetRootKey = new Claim.Factory(iden3.constants.CLAIMS.SET_ROOT_KEY.ID, {
  version: versionExample, era: eraExample, id: idExample, rootKey: rootKeyExample,
});
/*
claim.structure:
{
  claimType,
  version,
  er,
  id,
  rootKey,
};
 * Set root key name entry representation is as follows:
 * |element 3|: |empty|era|version|claim type| - |16 bytes|4 bytes|4 bytes|8 bytes|
 * |element 2|: |empty|identity| - |12 bytes|20 bytes|
 * |element 1|: |root key| - |32 bytes|
 * |element 0|: |empty| - |32 bytes|
 */
// methods of the set root key claim
claimSetRootKey.createEntry(); // Code raw data claim object into an entry claim object
// parse Entry into set root key claim
let entry = new Entry();
entry.fromHexadecimal(leaf); // Leaf is an hexadecimal representation of an Entry
let claimBasicParsed = iden3.claim.claimUtils.newClaimFromEntry(entry);
Assign name claim 
const versionExample = 1;
const nameExample = 'example.iden3.eth';
const idExample = '0x393939393939393939393939393939393939393A';
// new set root key ksign claim
const claimAssignName = new Claim.Factory(CONSTANTS.CLAIMS.ASSIGN_NAME.ID, {
  version: versionExample, hashName: nameExample, id: idExample
});
/*
claim.structure:
{
  claimType,
  version,
  hashName,
  id,
};
 * Assign name entry representation is as follows:
 * |element 3|: |empty|version|claim type| - |20 bytes|4 bytes|8 bytes|
 * |element 2|: |hash name| - |32 bytes|
 * |element 1|: |empty|identity| - |12 bytes|20 bytes|
 * |element 0|: |empty| - |32 bytes|
 */
// methods of the set root key claim
claimAssignName.createEntry(); // Code raw data claim object into an entry claim object
// parse Entry into set root key claim
let entry = new Entry();
entry.fromHexadecimal(leaf); // Leaf is an hexadecimal representation of an Entry
let claimBasicParsed = iden3.claim.claimUtils.newClaimFromEntry(entry);
Assign name claim 
const versionExample = 1;
const pubKeyCompressedExample = '0x036d94c84a7096c572b83d44df576e1ffb3573123f62099f8d4fa19de806bd4d593A';
// new authorize kSign secp256k1 claim
const claimAuthKSignSecp256k1 = new Claim.Factory(CONSTANTS.CLAIMS.AUTHORIZE_KSIGN_SECP256K1.ID, {
  version: versionExample, pubKeyCompressed: utils.bytesToHex(pubKeyCompressedExample),
});
/*
claim.structure:
{
  claimType,
  version,
  pubKeyCompressed,
};
 * Authorized KsignSecp256k1 element representation is as follows:
 * |element 3|: |empty|public key[0]|version|claim type| - |18 bytes|2 bytes|4 bytes|8 bytes|
 * |element 2|: |empty|public key[1]| - |1 bytes|31 bytes|
 * |element 1|: |empty| - |32 bytes|
 * |element 0|: |empty| - |32 bytes|
 */
// methods of the authorize ksign secp256k1
claimAuthKSignSecp256k1.createEntry(); // Code raw data claim object into an entry claim object
// parse Entry into set root key claim
let entry = new Entry();
entry.fromHexadecimal(leaf); // Leaf is an hexadecimal representation of an Entry
let claimBasicParsed = iden3.claim.claimUtils.newClaimFromEntry(entry);
checkProofOfClaim

This function checks the data structure of proofOfClaim and returns true if all the proofs are correct. Internally, it usees the iden3.sparseMerkleTree.checkProof() function, for each one of the proofs that are contained inside proofClaim data object.

Checks the full proof of a claim. This means check the: - Merkle Proof of the claim - Merkle Proof of the non revocation claim - Merkle Proof of the claim that the Relay have performed over the identity Merkle Root (this kind of claim is the SetRootClaim) - Merkle Proof of the non revocation of the SetRootClaim

let proofClaim = {
  date: 1549534168,
  leaf:'000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000aac4ed37a11e6a9170cb19a6e558913dc3ef000000000000000000000000000000000000a6a7000000000000000000000004',
  proofs: [{
    aux: {
      era: 0,
      idAddr: '0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22',
      version: 1
    }
    mtp0: '00010000000000000000000000000000000000000000000000000000000000011d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c3922',
    mtp1: '03010000000000000000000000000000000000000000000000000000000000011d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c39221c8bdcd862752abf2dd32d16c9c3acfa20ea93cecc64d169c4550ca3e9bca20b1541a6b5aa9bf7d9be3d5cb0bcc7cacbca26242016a0feebfc19c90f2224baed',
    root: '21c6e1a81851f4017139ae8ddfbd5e894376fdd14c73cecf2a81939bae78595b',
  } , {
    aux: null
    mtp0: '0007000000000000000000000000000000000000000000000000000000000041083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f81990fef40cc16896de64be5a0f827799555344fd3d9aade9b65d95ecfbcac3e5a73',
    mtp1: '0301000000000000000000000000000000000000000000000000000000000001081b6542453a651f2b0fea8b639a8823809f7fc032c051a644d1a8b559ba0322182adc955c46e6629ac74027ded0c843c7c65e8c3c4f12f77add56500f9f402e25451237d9133b0f5c1386b7b822f382cb14c5fff612a913956ef5436fb6208a',
    root: '1560e7b6983491305c6522c4227b98fbf26753b6a7fcb97ffb0ef7d98b271e99',

  }],
  signature:'3cedbb3d6eab5ce9a1f8bb436a080f7ec5ede3526fdcfa094fee33cbbd414d0c6d41a6650f4fdda27a66d51d87d18b4cae0adbd695ccdb152dae65a998ba61f101',
}
let proofClaim = JSON.parse(proofClaim);
let verified = iden3.protocols.verifyProofClaimFull(proofClaim, relayAddr);
// verified === true
Sparse merkletree
Merkle tree initialization

Three parameters as an inputs: - db –> where to store key-value merkle tree nodes - idaddr –> used as key prefix at the time to store key nodes

// New database
const db = new iden3.Db();
// Hardcoded id address for multi identity purposes
const idAddr = '0xq5soghj264eax651ghq1651485ccaxas98461251d5f1sdf6c51c5d1c6sd1c651';
// New merkle tree class instance
const mt = new iden3.sparseMerkleTree.SparseMerkleTree(db, idAddr);
Add claim

Add a leaf into the sparse merkle tree. Note the leaf object structure containing 4 bigInt fields

// Add leaf
// Create data leaf structure
const leaf = [bigInt(12), bigInt(45), bigInt(78), bigInt(41)];
// Add leaf to the merkle tree
mt.addClaim(leaf);
Get leaf data by hash Index

Look for a index leaf on the merkle tree ans retrieves its data

// Get leaf data by hash Index
// Retrieve data of the leaf
const leafData = mt.getClaimByHi(leaf.slice(2));
Generate Proof

Generates an array with all the siblings needed in order to proof that a certain leaf is on a merkle tree.

// Get leafProof for a given leaf index
const leafProof = mt.generateProof(leaf.slice(2));
// Code `leafProof` into a hexadecimal string
const leafProofHex = iden3.utils.bytesToHex(leafProof);
CheckProof

Checks the Merkle Proof of a Leaf. ##### Proof-of-existence

// CheckProof
// Proof-of-existencee
// Retrieve merkle tree root and code it into a string
const rootHex = iden3.utils.bytesToHex(mt.root);
// Code hash index into a hexadecimal string
// Compute total hash of the leaf and code it into an hexadecimal string
const hashes = iden3.sparseMerkleTree.getHiHv(leaf);
const hiHex = iden3.utils.bytesToHex(helpers.bigIntToBuffer(hashes[0]));
const hvHex = iden3.utils.bytesToHex(helpers.bigIntToBuffer(hashes[1]));
// Check if a leaf is on the merkle tree
const verified = iden3.sparseMerkleTree.checkProof(rootHex, leafProofHex, hiHex, hvHex);
Proof-of-non-existence

Generates leafProof of a leaf that is not on the merkle tree and check if it is on the merkle tree.

// CheckProof
// Proof-of-non-existence
// create leaf2 data structure
const leaf2 = [bigInt(1), bigInt(2), bigInt(3), bigInt(4)];
// Code hash index into a hexadecimal string
// Compute total hash of the leaf and code it into an hexadecimal string
const hashes2 = iden3.sparseMerkleTree.getHiHv(leaf2);
const hiHex2 = iden3.utils.bytesToHex(helpers.bigIntToBuffer(hashes2[0]));
const hvHex2 = iden3.utils.bytesToHex(helpers.bigIntToBuffer(hashes2[1]));
// Get leafProof for a given leaf index
const leafProof2 = mt.generateProof(leaf2.slice(2));
// Code `leafProof` into a hexadecimal string
const leafProofHex2 = iden3.utils.bytesToHex(leafProof2);
// Check if a leaf is on the merkle tree
const verified2 = iden3.sparseMerkleTree.checkProof(rootHex, leafProofHex2, hiHex2, hvHex2);

The complete example can be found in `sparse-merkle-tree.example.js <https://github.com/iden3/iden3js/blob/master/examples/sparse-merkle-tree.example.js>`__

Utils 
// hash Buffer
let hash = iden3.utils.hashBytes(b);

let hex = iden3.utils.bytesToHex(buff); // returns a Hexadecimal representation of a Buffer
let buff = iden3.utils.hexToBytes(hex); // returns a Buffer from a Heximal representation string

// verify signature
let verified = iden3.utils.verifySignature(msgHashHex, signatureHex, addressHex);
// verified: true
Relay http

Connectors to interact with the relay API REST.

Create Relay object 
// new relay
const relayAddr = '0xe0fbce58cfaa72812103f003adce3f284fe5fc7c';
const relay = new iden3.Relay('http://127.0.0.1:8000/api/unstable');
relay.getID 
relay.getID(id.idAddr).then((res) => {
  console.log(res.data);
});
  • Output:
// Return object: - IdAddr: Address identity identifier
//                - LocalDb: contins necessary informatin to create counterfactoual
//                - Onchain: information regarding smart contract deployed on the blockchain
{
  IdAddr: '0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22',
  LocalDb: {
    impl:'0x66d0c2f85f1b717168cbb508afd1c46e07227130',
    operational:'0xc7d89fe96acdb257b434bf580b8e6eb677d445a9',
    operationalPk:'0x03c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff57833',
    recoverer:'0xf3c9f94e4eaffef676d4fd3b4fc2732044caea91',
    relayer:'0xe0fbce58cfaa72812103f003adce3f284fe5fc7c',
    revokator:'0xb07079bd6238fa845dc77bbce3ec2edf98ffe735',
  },
  onchain: {
    Codehash:'0x4fec321ffcfdd48cdbe4d02553acb18ddb04cd5c6a78bcaf86e87834b1f3d0ee',
    Impl:'0x66d0c2f85f1b717168cbb508afd1c46e07227130',
    LastNonce:0,
    Recoverer:'0xf3c9f94e4eaffef676d4fd3b4fc2732044caea91',
    RecovererProp:'0x0000000000000000000000000000000000000000',
    Relay:'0xe0fbce58cfaa72812103f003adce3f284fe5fc7c',
    Revoker:'0xb07079bd6238fa845dc77bbce3ec2edf98ffe735',
  },
}
relay.getRelayRoot 
relay.getRelayRoot()
  .then(res => {
    console.log('res.data', res.data);
  });
  • Output:
// Return object: - contractRoot: Address of the relay smart contract
//                - root: Current root of the relay merkle tree
{
  contractRoot: '0x0000000000000000000000000000000000000000000000000000000000000000',
  root: '0x1560e7b6983491305c6522c4227b98fbf26753b6a7fcb97ffb0ef7d98b271e99'
}
relay.getIDRoot 
relay.getIDRoot(id.kc.addressHex())
  .then(res => {
    console.log('res.data', res.data);
  });
  • Output:
// Return object: - idRoot: Root of the identity merkle tree
//                - proofIdRoot: Proof of SetRootClaim that relay merkle tree contains identity root merkle tree
//                - root: Root of the relay merkle tree
{
  idRoot: '0x0000000000000000000000000000000000000000000000000000000000000000',
  proofIdRoot: '0x0000000000000000000000000000000000000000000000000000000000000000',
  root: '0x0000000000000000000000000000000000000000000000000000000000000000'
}
relay.getClaimByHi 
let leaf = new iden3.claims.Entry();
leaf.fromHexadecimal(proofClaim.Leaf);

relay.getClaimByHi(id.idAddr, iden.utils.bytesToHex(leaf.hi()))
  .then(res => {
    console.log('res.data', res.data);
  });

// Return object: - proofOfClaim: Proof of claim for the claim asked
proofClaim = {
  date: 1549534168,
  leaf:'000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000aac4ed37a11e6a9170cb19a6e558913dc3ef000000000000000000000000000000000000a6a7000000000000000000000004',
  proofs: [{
    aux: {
      era: 0,
      idAddr: '0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22',
      version: 1
    }
    mtp0: '00010000000000000000000000000000000000000000000000000000000000011d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c3922',
    mtp1: '03010000000000000000000000000000000000000000000000000000000000011d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c39221c8bdcd862752abf2dd32d16c9c3acfa20ea93cecc64d169c4550ca3e9bca20b1541a6b5aa9bf7d9be3d5cb0bcc7cacbca26242016a0feebfc19c90f2224baed',
    root: '21c6e1a81851f4017139ae8ddfbd5e894376fdd14c73cecf2a81939bae78595b',
  } , {
    aux: null
    mtp0: '0007000000000000000000000000000000000000000000000000000000000041083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f81990fef40cc16896de64be5a0f827799555344fd3d9aade9b65d95ecfbcac3e5a73',
    mtp1: '0301000000000000000000000000000000000000000000000000000000000001081b6542453a651f2b0fea8b639a8823809f7fc032c051a644d1a8b559ba0322182adc955c46e6629ac74027ded0c843c7c65e8c3c4f12f77add56500f9f402e25451237d9133b0f5c1386b7b822f382cb14c5fff612a913956ef5436fb6208a',
    root: '1560e7b6983491305c6522c4227b98fbf26753b6a7fcb97ffb0ef7d98b271e99',

  }],
  signature:'3cedbb3d6eab5ce9a1f8bb436a080f7ec5ede3526fdcfa094fee33cbbd414d0c6d41a6650f4fdda27a66d51d87d18b4cae0adbd695ccdb152dae65a998ba61f101',
}
relay.resolveName 
relay.resolveName('username@iden3.io')
  .then(res => {
    console.log('res.data', res.data);
  });
  • Output:
// Return object: - claim: Hexadecimal representation of the assign name claim
//                - idAddr: Ethereum address associated with the name asked
//                - proofOfClaimAssignName: Proof of the claim requested
{
  claim: '0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000007b471a1bdbd3b8ac98f3715507449f3a8e1f3b22008c8efcda9e563cf153563941b60fc5ac88336fc58d361eb0888686fadb99760000000000000000000000000000000000000000000000000000000000000003',
  ethAddr: '0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22'.
  proofOfClaimAssignName: {
    date: 1549539788,
    leaf: '00000000000000000000000000000000000000000000000000000000000000000000000000000000000000007b471a1bdbd3b8ac98f3715507449f3a8e1f3b22008c8efcda9e563cf153563941b60fc5ac88336fc58d361eb0888686fadb99760000000000000000000000000000000000000000000000000000000000000003',
    proofs:[{
      aux: null,
      mtp0: '0007000000000000000000000000000000000000000000000000000000000041083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f8199200d11c36880f3f48060bc8f09855aeefc9bb1e1374556d02c3f059293df4abe',
      mtp1: '0301000000000000000000000000000000000000000000000000000000000001081b6542453a651f2b0fea8b639a8823809f7fc032c051a644d1a8b559ba0322182adc955c46e6629ac74027ded0c843c7c65e8c3c4f12f77add56500f9f402e25451237d9133b0f5c1386b7b822f382cb14c5fff612a913956ef5436fb6208a',
      root: '1560e7b6983491305c6522c4227b98fbf26753b6a7fcb97ffb0ef7d98b271e99',
    }]
    signature:'0b17f53111f890222d8139e0a400f9dbf900dabdc450759ac9ab19fb9f239f704d250cd3116b6f74905ffccd8754182d3de2e1fc4ac7a35b0db6fe660198422000',
  },
}
Tests

To run unitary test:

npm run test:unit

To run integration test, needs to have a running Relay node.

npm run test:int

To run all test, needs to have a running Relay node.

npm run test:all
Browserify bundle

To generate the browserify bundle:

npm run browserify
WARNING

All code here is experimental and WIP

Releases

Version compatibility

  iden3js go-iden3
tag v0.0.21 v0.0.2
License

iden3js is part of the iden3 project copyright 2018 0kims association and published with GPL-3 license, please check the LICENSE file for more details.

Go-Iden3

Overview

go-iden3

Go implementation of the iden3 system.

Go Report Card Build Status

Install
$ go get github.com/iden3/go-iden3
Documentation

Go Modules documentation: - GoDoc common - GoDoc core - GoDoc db - GoDoc eth - GoDoc crypto - GoDoc merkletree - GoDoc utils - GoDoc services/backupsrv - GoDoc services/centrauthsrv - GoDoc services/claimsrv - GoDoc services/identitysrv - GoDoc services/mongosrv - GoDoc services/namesrv - GoDoc services/rootsrv - GoDoc services/signsrv

Testing

go test ./...

WARNING

All code here is experimental and WIP

License

go-iden3 is part of the iden3 project copyright 2018 0kims association and published with GPL-3 license, please check the LICENSE file for more details.

Merkle Tree

Merkletree usage
Import

Import packages:

import (
  "github.com/iden3/go-iden3/db"
  "github.com/iden3/go-iden3/merkletree"
  "github.com/iden3/go-iden3/core"
  common3 "github.com/iden3/go-iden3/common"
)
New Merkletree

Define new tree:

// first we create the storage, where will be placed the leveldb database
storage, err := db.NewLevelDbStorage("./path", false)
if err!=nil {
  panic(err)
}
// new merkletree of 140 levels of maximum depth using the defined
// storage
mt, err := merkletree.NewMerkleTree(storage, 140)
if err!=nil {
  panic(err)
}
defer mt.Storage().Close()
Add claims

To add claims, first we need to have a claim data struct that fits the Entrier interface:

// Data consists of 4 elements of the mimc7 field.
type Data [4]ElemBytes
// An Entry contains Data where the claim will be serialized.
type Entry struct {
  Data Data
  [...]
}
// Entrier is the interface of a generic claim.
type Entrier interface {
  Entry() *Entry
}

We can use a new struct, or also use one of the already existing in the go-iden3/core/claim.go.

For this example, we will use the core.ClaimAssignName. We add two different claims into the merkletree:

name0 := "alice@iden3.io"
ethAddr0 := common.HexToAddress("0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22")
claim0 := core.NewClaimAssignName(name0, ethAddr0)
claimEntry0 := claim0.Entry()

name1 := "bob@iden3.io"
ethAddr1 := common.HexToAddress("0x28f8267fb21e8ce0cdd9888a6e532764eb8d52dd")
claim1 := core.NewClaimAssignName(name1, ethAddr1)
claimEntry1 := claim1.Entry()

Once we have the claim struct that fits the Entrier interface, we can add it to the merkletree:

err = mt.Add(claimEntry0)
if err != nil {
  panic(err)
}
err = mt.Add(claimEntry1)
if err != nil {
  panic(err)
}
Generate merkle proof

Now we can generat the merkle proof of this claim:

mp, err := mt.GenerateProof(claimEntry0.HIndex(), nil)
if err != nil {
  panic(err)
}

// We can display the merkleproof:
fmt.Println("merkle proof: ", mp)
// out:
// merkle proof:  Proof:
//         existence: true
//         depth: 2
//         notempties: 01
//         siblings: 0 a045683a
Generate merkle proof for a specific tree (with specific root) 
mp, err := mt.GenerateProof(claimEntry0.HIndex(), specificRoot)
if err != nil {
  panic(err)
}
Check merkle proof

Now from a given merkle proof, we can check that it’s data is consistent:

checked := merkletree.VerifyProof(mt.RootKey(), mp,
                  claimEntry0.HIndex(), claimEntry0.HValue())
// checked == true
Get value in position

We can also get the claim byte data in a certain position of the merkle tree (determined by its Hash Index (HIndex)):

claimDataInPos, err := mt.GetDataByIndex(claimEntry0.HIndex())
if err!=nil{
  panic(err)
}
Proof of non existence

Also, we can generate a Proof of non existence, that is, the merkle proof that a claim is not in the tree. For example, we have this claim2 that is not added in the merkletree:

name2 := "eve@iden3.io"
ethAddr2 := common.HexToAddress("0x29a6a240e2d8f8bf39b5338b9664d414c5d793f4")
claim2 := core.NewClaimAssignName(name2, ethAddr2)
claimEntry2 := claim2.Entry()

Now, we can generate the merkle proof of the data in the position of this claim in the merkletree, and print it to see that it’s a non-existence proof:

mp, err = mt.GenerateProof(claimEntry2.HIndex(), nil)
if err != nil {
  panic(err)
}

// We can display the merkleproof:
fmt.Println("merkle proof: ", mp)
// out:
// merkle proof:  Proof:
//         existence: false
//         depth: 2
//         notempties: 01
//         siblings: 0 a045683a
//         node aux: hi: c641b925, ht: eeae8c7e

In the mp we have the merkleproof that in the position of this claim2 (that is determined by its Hash Index (HIndex)) there is no data stored (so, it’s an NodeTypeEmpty not actually stored in the tree).

We can check this proof by calling the VerifyProof function, and in the parameter where we put the Hash Total (HtTotal) we can actually put anything, because we can proof that anything is not there. We will use the Hash Total of the claim2 for convenience.

checked = merkletree.VerifyProof(mt.RootKey(), mp, claimEntry2.HIndex(), claimEntry2.HValue())
// checked == true
Live snapshot of the tree

This option allows to create a read only snapshot of the Merkle Tree, where to perform read actions, while the main tree continues evolving. Basically what it does is to create a new MerkleTree object with the specified Root. Also this Merkle Tree snapshot will not allow to add nodes into it.

snapshot, err := mt.Snapshot(concreteRootKey)
if err!=nil {
    panic(err)
}
// now we can for example, generate proofs for that snapshot of the Merkle Tree
mp, err := snapshot.GenerateProof(claimEntry0.HIndex())
if err != nil {
  panic(err)
}
// and the mp (merkleproof) will be valid for the root of the snapshot
Walk over the Merkle Tree

Walk option allows to iterate through all the branches of a tree with a given RootKey. It allows to give a funcion that will be called inside each node of the tree, returning the a pointer to that Node object.

When calling the Walk function, we can specify a RootKey

We can use a BufferString, that we can use to print to the screen or also into a file all the Leaf nodes:

w := bytes.NewBufferString("")
// mt.Walk(nil, [...] --> as we specify the RootKey as nil, it will use the current mt.RootKey()
err := mt.Walk(nil, func(n *Node) {
    if n.Type == NodeTypeLeaf {
        fmt.Fprintf(w, "node \"%v\"\n", common3.HexEncode(n.Value()))
    }
})
if err != nil {
    panic(err)
}
fmt.Println(w)

Or also we can just print each node inside a switch (also, in this case, we specify a concrete RootKey of the MerkleTree that we want to use):

err := mt.Walk(concreteRootKey, func(n *Node) {
    switch n.Type {
    case NodeTypeEmpty:
        fmt.Println("empty")
    case NodeTypeLeaf:
        fmt.Println("leaf \"%v\"\n", common3.HexEncode(n.Value()))
    case NodeTypeMiddle:
        fmt.Println("node \"%v\"\n", common3.HexEncode(n.Value()))
    default:
        return ErrInvalidNodeFound
    }
})
if err != nil {
    panic(err)
}
Dump all the claims of a MerkleTree

Using this function we can dump all the claims of a MerkleTree, allowing us also to specify a concrete RootKey of the tree that we want to dump. The output generated by this method, can be used from the iden3js library, importing all the dumped claims, allowing to have the same tree from go in javascript.

w := bytes.NewBufferString("")
err := mt.DumpClaims(w, rootKey) // as rootKey we can pass a nil pointer, and it will use the current RootKey
if err!=nil {
    panic(err)
}
fmt.Println(w)
Merkle tree visual representation

Finally, you can get a visual representation of the merkle tree with graphviz, in which only the last bytes of each node key are shown in hexadecimal to make a compact representation. In the following example print the graphviz code for the representation of a merkle tree with 10 claims:

s := bytes.NewBufferString("")
mt2.GraphViz(s, nil)
fmt.Println(s)

GraphViz output code:

digraph hierarchy {
node [fontname=Monospace,fontsize=10,shape=box]
"b0830ca8" -> {"5ae3cb67" "570088ed"}
"5ae3cb67" -> {"6ce2c761" "37b29928"}
"empty0" [style=dashed,label=0];
"6ce2c761" -> {"e82bf1e7" "empty0"}
"e82bf1e7" -> {"6ee500bf" "63289a99"}
"6ee500bf" [style=filled];
"63289a99" [style=filled];
"37b29928" -> {"ef87b970" "8b6e9f1c"}
"ef87b970" -> {"1481190a" "93c79331"}
"1481190a" [style=filled];
"93c79331" [style=filled];
"8b6e9f1c" [style=filled];
"570088ed" -> {"4f3d0101" "8a2524f6"}
"4f3d0101" -> {"74924bbf" "6aa34a3d"}
"74924bbf" [style=filled];
"empty1" [style=dashed,label=0];
"6aa34a3d" -> {"empty1" "69003eca"}
"69003eca" -> {"fac8618d" "43f442c5"}
"fac8618d" [style=filled];
"43f442c5" [style=filled];
"8a2524f6" -> {"3f5e7a5f" "d76c6447"}
"3f5e7a5f" [style=filled];
"d76c6447" [style=filled];
}

The GraphViz visualization looks like this: image0

You can also view the graph using an online graphviz renderer.

Complete example

The complete example can be found in this directory in the file `example.go <https://github.com/iden3/go-iden3/blob/master/merkletreeDoc/example.go>`__.

Backup Server

Backup Server
Backup Service
Wallet                 Backup Service
  +                         +
  |       /register         |
  +------------------------>+
  |        200 OK           |
  +<------------------------+
  |                         |
  |                         |
  |      /backup/upload     |
  +------------------------>+
  |        200 OK           |
  +<------------------------+
  |                         |
  |                         |
  |      /backup/download   |
  +------------------------>+
  |        {backup}         |
  +<------------------------+
  |                         |
  +                         +
Endpoints

  • POST /register

    • in:
    {
    username: "",
    password: ""
}
    • out:
    200 OK

  • POST /backup/upload

    • in:
    {
    username: "",
    password: ""
    backup: "base64"
}
    • out:
    200 OK

  • POST /backup/download

    • in:
    {
    username: "",
    password: ""
}
    • out:
    {
    backup: "base64"
}

  • ERROR

    • out:
    {
    error: "msg"
}

Relay

Relay
Usage
Config

To run a relay we need to build the contracts used for iden3:

git clone https://github.com/iden3/contracts
cd contracts
npm install
node_modules/.bin/truffle compile

Then we create a keystore protected by a password. First you need to install geth. Then run the following commands with your password (we use THEPASSWORD here as an example):

echo "THEPASSWORD" > config-path/keystore.password
geth account new --keystore config-path/keystore # Input the same password as the one stored in keystore.password

Then we will need to have a config file config.yaml with the following data:

server:
  serviceapi: 127.0.0.1:8000
  adminapi: 127.0.0.1:8001

web3:
  url: http://web3-gateway-url

keystore:
  path: config-path/keystore
  address: 0xe0fbce58cfaa72812103f003adce3f284fe5fc7c
  password: config-path/keystore.password

contracts:
  rootcommits:
    jsonabi: contracts-repo-path/build/contracts/RootCommits.json
    address: 0x6A6E04938d66Df5717ec4774E0ca181077e842ed
  iden3impl:
    jsonabi: contracts-repo-path/build/contracts/IDen3Impl.json
    address: 0x66D0c2F85F1B717168cbB508AfD1c46e07227130
  iden3deployer:
    jsonabi: contracts-repo-path/build/contracts/Deployer.json
    address: 0xf02e236F9F6C08966DD63B9fB9C04764E01b0563
  iden3proxy:
    jsonabi: contracts-repo-path/build/contracts/IDen3DelegateProxy.json

storage:
  path: /tmp/treedb

domain: iden3.io
namespace: iden3.io
Running the relay

In the go-iden3/cmd/relay directory, run:

go run main.go --config path-to-config/config.yaml start

Also can be built using:

go build

And then execute:

./relay
API Endpoints
GET http://127.0.0.1:8000/api/v0.1/root

Returns:

{
  "contractRoot": "0x0000000000000000000000000000000000000000000000000000000000000000",
  "root": "0x0458f3531f8292918aabef2d5f1c5a0c35da251c66c3f9d33eb4077e9ed0ec36"
}
POST http://127.0.0.1:8000/api/v0.1/claim/:idaddr

Input:

{
  "valueHex": "0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000025521b25f396b1f62fcc46ce5b9a6b53684d5649958d83d79b5bb6711aa270000000000000000000000000000000000009105000000000000000000000004"
,
  "signatureHex": "0xd7cfe7c0935e27a6ce3c587da2f55a5f6765b859f57baddd22a232bf12563ac60cd91f6c1046acfd2c3d148f9d082e0ec194d72f3f1b2ead7985
9809fa09bcae1c",
  "ksignpk": "0x03c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff57833"
}

Returns:

{
  "proofClaim": {
    "proofs": [
      {
        "mtp0": "0x00030000000000000000000000000000000000000000000000000000000000041d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8
ad761c3922",
        "mtp1": "0x0303000000000000000000000000000000000000000000000000000000000004294c2853becf85699f4d65fa57bd43e5c2e7087e23945d2c5ec52f
903443139728f8267fb21e8ce0cdd9888a6e532764eb8d52dd6c1e354157c78b7ea281ce801541a6b5aa9bf7d9be3d5cb0bcc7cacbca26242016a0feebfc19c90f2224bae
d",
        "root": "0x26815c474fa21c55dbef8e8628fc418946b147278f42402db7f07e4324ae9c5f",
        "aux": {
          "version": 1,
          "era": 0,
          "ethAddr": "0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22"
        }
      },
      {
        "mtp0": "0x0001000000000000000000000000000000000000000000000000000000000001083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59
fad48f8199",
        "mtp1": "0x0301000000000000000000000000000000000000000000000000000000000001296c58506f1f3ecb09122a8eac285cd363840e2da8180d61188f0a
c78189b96a182adc955c46e6629ac74027ded0c843c7c65e8c3c4f12f77add56500f9f402e25451237d9133b0f5c1386b7b822f382cb14c5fff612a913956ef5436fb6208
a",
        "root": "0x141a1d2dceec7ff08497d15fc092f18ac460c8654ff9fed6626c1d66eeb3c75b",
        "aux": null
      }
    ],
    "leaf": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000025521b25f396b1f62fcc46ce5b9a6b53684d5649958d83d79b5bb6711aa270000000000000000000000000000000000009105000000000000000000000004",
    "date": 1548849932,
    "signature": "0x224dca4c57fb4c4bb946ec1ba82cf46d2f12da5a1a73fe143bfcd3ae20212975519c9d711ce2c4e414eae950b28be741e6b9721cd663d71fb2a48
44efa5a84ed00"
  }
}
GET http://127.0.0.1:8000/api/v0.1/claim/:idaddr/root

Returns:

{
  "idRoot": "0x0000000000000000000000000000000000000000000000000000000000000000",
  "idRootProof": "0x01020000000000000000000000000000000000000000000000000000000000030df6a62218b641b022bbd990303ec57411ebfe24965af84a7d3e4
dc8e92d46bb2c7df576dfac28d7b2a9a534e1d099e0438f04f66bebaa03a2349860d26e2e62",
  "root": "0x0458f3531f8292918aabef2d5f1c5a0c35da251c66c3f9d33eb4077e9ed0ec36"
}
GET http://127.0.0.1:8000/api/v0.1/claim_proof/idaddr/:idaddr/hi/:hi

4eb8d52dd6c1e354157c78b7ea281ce80 Returns:

{
  "proofClaim": {
    "proofs": [
      {
        "mtp0": "0x00030000000000000000000000000000000000000000000000000000000000051b12c5489d45a9759a0aa761b4031fc4fa4afac3d6315273eecd13
58d562b9de294c2853becf85699f4d65fa57bd43e5c2e7087e23945d2c5ec52f9034431397",
        "mtp1": "0x03030000000000000000000000000000000000000000000000000000000000051b12c5489d45a9759a0aa761b4031fc4fa4afac3d6315273eecd13
58d562b9de1d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c39221a81d39b8b3f86e7a4b3df400dcb541f478df56414d3bd0d4b3cfa2f8e7df07
c1541a6b5aa9bf7d9be3d5cb0bcc7cacbca26242016a0feebfc19c90f2224baed",
        "root": "0x1a99534d2fad42577649c8fa0af4c2b5610f316f7bf29814ba36a2c4f1e76c21",
        "aux": {
          "version": 2,
          "era": 0,
          "ethAddr": "0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22"
        }
      },
      {
        "mtp0": "0x00020000000000000000000000000000000000000000000000000000000000031744e6cadba4793eacdfb8d32e955ea12f976b72cef88059e09bb5
f6ea5d9de0083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f8199",
        "mtp1": "0x01020000000000000000000000000000000000000000000000000000000000030df6a62218b641b022bbd990303ec57411ebfe24965af84a7d3e4d
c8e92d46bb2c7df576dfac28d7b2a9a534e1d099e0438f04f66bebaa03a2349860d26e2e62",
        "root": "0x0458f3531f8292918aabef2d5f1c5a0c35da251c66c3f9d33eb4077e9ed0ec36",
        "aux": null
      }
    ],
    "leaf": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000003c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff50000000000000000000000000000000000007833000000000000000000000004",
    "date": 1548849932,
    "signature": "0xd18b60beb56a40dcb4ad5648d3b7d122137aa75f96c858cd1e8f0999cb02f35255897d9a6cbbf9df02745c36e6ac4ad2a7a839b81ae4941bcbd4c
0136cb76b5200"
  }
}
POST http://127.0.0.1:8000/api/v0.1/id

Input:

{
  "operationalpk": "0x03c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff57833",
  "recoverer": "0xf3c9f94e4eaffef676d4fd3b4fc2732044caea91",
  "revokator": "0xb07079bd6238fa845dc77bbce3ec2edf98ffe735"
}

Returns:

{
  "idaddr": "0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22",
  "proofClaim": {
    "proofs": [
      {
        "mtp0": "0x0000000000000000000000000000000000000000000000000000000000000000",
        "mtp1": "0x030000000000000000000000000000000000000000000000000000000000000028f8267fb21e8ce0cdd9888a6e532764eb8d52dd6c1e354157c78b
7ea281ce801541a6b5aa9bf7d9be3d5cb0bcc7cacbca26242016a0feebfc19c90f2224baed",
        "root": "0x1d9d41171c4b621ff279e2acb84d8ab45612fef53e37225bdf67e8ad761c3922",
        "aux": {
          "version": 0,
          "era": 0,
          "ethAddr": "0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22"
        }
      },
      {
        "mtp0": "0x0000000000000000000000000000000000000000000000000000000000000000",
        "mtp1": "0x0300000000000000000000000000000000000000000000000000000000000000182adc955c46e6629ac74027ded0c843c7c65e8c3c4f12f77add56
500f9f402e25451237d9133b0f5c1386b7b822f382cb14c5fff612a913956ef5436fb6208a",
        "root": "0x083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f8199",
        "aux": null
      }
    ],
    "leaf": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000003c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff50000000000000000000000000000000000007833000000000000000000000004",
    "date": 1548849932,
    "signature": "0x65312b0604555dd6a406e394d2174bae040a22c13143d3f97b282d55619315765e4fb4f783aa4c26979dc9bbe51ff6c17c1176f57c140a3120e3e
3d2f9044f1001"
  }
}
GET http://127.0.0.1:8000/api/v0.1/id/0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22

Returns:

{
  "IdAddr": "0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22",
  "LocalDb": {
    "Operational": "0xc7d89fe96acdb257b434bf580b8e6eb677d445a9",
    "OperationalPk": "0x03c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff57833",
    "Relayer": "0xe0fbce58cfaa72812103f003adce3f284fe5fc7c",
    "Recoverer": "0xf3c9f94e4eaffef676d4fd3b4fc2732044caea91",
    "Revokator": "0xb07079bd6238fa845dc77bbce3ec2edf98ffe735",
    "Impl": "0x66d0c2f85f1b717168cbb508afd1c46e07227130"
  },
  "Onchain": {
    "Codehash": "0x4fec321ffcfdd48cdbe4d02553acb18ddb04cd5c6a78bcaf86e87834b1f3d0ee",
    "Impl": "0x66d0c2f85f1b717168cbb508afd1c46e07227130",
    "Recoverer": "0xf3c9f94e4eaffef676d4fd3b4fc2732044caea91",
    "RecovererProp": "0x0000000000000000000000000000000000000000",
    "Revoker": "0xb07079bd6238fa845dc77bbce3ec2edf98ffe735",
    "Relay": "0xe0fbce58cfaa72812103f003adce3f284fe5fc7c",
    "LastNonce": 0
  }
}
POST http://127.0.0.1:8000/api/v0.1/id/:idaddr/deploy

Input:

{}

Returns:

{
  idaddr: '0x8435ebb41634c05019be1710be0007fa0d92861f',
  tx: '0x403859ccc701eb358d3a25c908c33de733cbb2d0ebc1c7738eed4908cc8cf5c4'
}
POST http://127.0.0.1:8000/api/v0.1/vinculateid

Input:

{
  "ethAddr": "0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22",
  "name": "testName",
  "signature": "0x8526016fb5f0fda5d04b37725768a82f17c7886541445304730bcf021c96e5ce6181b3a6e1d1ca4faa68f802d169514664f576d006fe872e646c96a
e9a75d6c11c",
  "ksignpk": "0x03c2e48632c87932663beff7a1f6deb692cc61b041262ae8f310203d0f5ff57833"
}

Returns:

{
  "claimAssignName": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000007b471a1bdbd3b8ac98f371550
7449f3a8e1f3b22008c8efcda9e563cf153563941b60fc5ac88336fc58d361eb0888686fadb99760000000000000000000000000000000000000000000000000000000000
000003",
  "ethAddr": "0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22",
  "name": "testName",
  "proofClaimAssignName": {
    "proofs": [
      {
        "mtp0": "0x00070000000000000000000000000000000000000000000000000000000000410df6a62218b641b022bbd990303ec57411ebfe24965af84a7d3e4d
c8e92d46bb296c58506f1f3ecb09122a8eac285cd363840e2da8180d61188f0ac78189b96a",
        "mtp1": "0x03020000000000000000000000000000000000000000000000000000000000031744e6cadba4793eacdfb8d32e955ea12f976b72cef88059e09bb5
f6ea5d9de0083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f8199137896c5dde3243fba9080cd9eb1aad51a293091da7afd15b05f54a82a4633a
c10b8436ad110ba4812e91e282ef9ef833006cda841f9121345a2eb8f76ed09bd",
        "root": "0x0458f3531f8292918aabef2d5f1c5a0c35da251c66c3f9d33eb4077e9ed0ec36",
        "aux": null
      }
    ],
    "leaf": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000007b471a1bdbd3b8ac98f3715507449f3a8e
1f3b22008c8efcda9e563cf153563941b60fc5ac88336fc58d361eb0888686fadb99760000000000000000000000000000000000000000000000000000000000000003",
    "date": 1548849932,
    "signature": "0xd18b60beb56a40dcb4ad5648d3b7d122137aa75f96c858cd1e8f0999cb02f35255897d9a6cbbf9df02745c36e6ac4ad2a7a839b81ae4941bcbd4c
0136cb76b5200"
  }
}
GET http://127.0.0.1:8000/api/v0.1/identities/resolv/testName@iden3.io

Returns:

{
  "claim": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000007b471a1bdbd3b8ac98f3715507449f3a8e1
f3b22008c8efcda9e563cf153563941b60fc5ac88336fc58d361eb0888686fadb99760000000000000000000000000000000000000000000000000000000000000003",
  "ethAddr": "0x7b471a1bdbd3b8ac98f3715507449f3a8e1f3b22",
  "proofClaimAssignName": {
    "proofs": [
      {
        "mtp0": "0x00070000000000000000000000000000000000000000000000000000000000410df6a62218b641b022bbd990303ec57411ebfe24965af84a7d3e4d
c8e92d46bb296c58506f1f3ecb09122a8eac285cd363840e2da8180d61188f0ac78189b96a",
        "mtp1": "0x03020000000000000000000000000000000000000000000000000000000000031744e6cadba4793eacdfb8d32e955ea12f976b72cef88059e09bb5
f6ea5d9de0083dbb7700313075a2b8fe34b0188ff44784e3dc60987ed9277b59fad48f8199137896c5dde3243fba9080cd9eb1aad51a293091da7afd15b05f54a82a4633a
c10b8436ad110ba4812e91e282ef9ef833006cda841f9121345a2eb8f76ed09bd",
        "root": "0x0458f3531f8292918aabef2d5f1c5a0c35da251c66c3f9d33eb4077e9ed0ec36",
        "aux": null
      }
    ],
    "leaf": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000007b471a1bdbd3b8ac98f3715507449f3a8e
1f3b22008c8efcda9e563cf153563941b60fc5ac88336fc58d361eb0888686fadb99760000000000000000000000000000000000000000000000000000000000000003",
    "date": 1548849932,
    "signature": "0xd18b60beb56a40dcb4ad5648d3b7d122137aa75f96c858cd1e8f0999cb02f35255897d9a6cbbf9df02745c36e6ac4ad2a7a839b81ae4941bcbd4c
0136cb76b5200"
  }
}

Crypto

crypto GoDoc

iden3 crypto Go package

MIMC7

MIMC7 Hash function

Usage:

package main

import (
    "math/big"
    "github.com/iden3/go-iden3/crypto/mimc7"
)

func mimc7Example() {
    // for this example, define an array of big ints to hash
    b1 := big.NewInt(int64(1))
    b2 := big.NewInt(int64(2))
    b3 := big.NewInt(int64(3))
    bigArr := []*big.Int{b1, b2, b3}
    arr, err := mimc7.BigIntsToRElems(bigArr)

    // mimc7 hash
    h := mimc7.Hash(arr)
    fmt.Println((*big.Int)(h).String())
    // h == 10001192134743444757278983923787274376044444355175924720153500128284360571540
}

Tx Forwarder

Overview

tx-forwarder

Server that forwards the tx to the specified smart contract.

Usage
Config

Deploy contract:

./tx-forwarder deploy

This will print the deployed contract address, then copy&paste in the config file config.yaml:

server:
        serviceapi: 0.0.0.0:11000
        adminapi: 0.0.0.0:11001
web3:
        url: http://127.0.0.1:8545
keystore:
        path: /var/config/keystore
        address: 0x123456789...
        passwd: /var/config/keystore.password
        keyjsonpath: /var/config/keystore/UTC-etc
contracts:
        samplecontract: 0xasdf
Run

Then, run the server:

./tx-forwarder start
Contract

Current contract is just a working sample contract.

The contract handlers goes inside eth/contract/ directory.

Once having the contract file written in Solidity, in order to generate the Go handlers:

solc --abi --bin SampleContract.sol -o build
abigen --bin=./build/SampleContract.bin --abi=./build/SampleContract.abi --pkg=SampleContract --out=SampleContract.go

And place the sampleContract.go file in the eth/contract/sampleContract.go path.

Discovery Node

Overview

discovery-node Go Report Card GoDoc

Draft implementation of discovery-node of the decentralized discovery protocol over Pss Swarm

Overview
network00

network00

Types of node: - gateway (passive): are the nodes that only perform petitions, acting as gateways to the discovery network. This node can be trustless, as all the data that gets from the network and that is returned to its petitions, have the proofs of validity (merkleproofs) - active: are the nodes that are answering requests, each identity trusts its active discovery-node

Node Storage

The discovery-node data storage is a leveldb database. It’s organized with prefixes, where each type of data is stored under a prefix.

Databases: - dbOwnIds: holds the data about the identities that the discovery-node manages - dbAnswCache: holds the data about the discovered identites. Each data packet of a discovered identity, has a timestamp, the data packets are valid under a time window where the timestamp allows to determine if it’s already valed or is too old

Sample discovery flow

Roles: - user: user identity, from a phone/laptop device - Requester: discovery-node that wants to know about one identity - Id_Agent: discovery-node that knows the info about the identity, and is listening in Swarm Pss in the topic id_discovery

Flow when a discovery-node receives an Id discover request:

flow00

flow00

Discovery flow:

  1. discovery-node receives an https petition from the user asking for an identity info, from now, this discovery-node will be the Requester
  2. Requester checks if already knows a fresh copy of the data packet of the identity
    • in case that has the data, checks that the timestamp is not too old
    • if the data is fresh, returns it and finishes the process
    • if the identity data was not in its databases, ask to the network for it (following steps)
  3. Requester creates Query packet asking for who is the relay of identity john@domain.eth
  4. Requester sends the Query packet into the Swarm Pss network under the topic id_discovery
    • the Requester waits a configured amount of time, if the Answer don’t comes inside that time window, returns an error msg through https to the user
  5. the Id_Agent server of that identity will receive the Query packet and will see that is a user under its umbrella
  6. Id_Agent server will answer the Answer packet (with the proofs of validity, signature, etc) to the Requester
  7. Requester receives the Answer packet (verifies the signature), and now knows how to reach the Relay node of john@domain.eth, and can answer to the user
Requester                       Id_Agent
   +                            +
   |                            |
   * 1                          |
   * 2                          |
   * 3                          |
   |             4              |
   +--------------------------->+
   |                            * 5
   |             6              |
   +<---------------------------+
   * 7                          |
   |                            |
   +                            +
Data structures

Each data packet that is sent over the network, goes with a ProofOfWork, and a Signature of the emmiter.

// Service holds the data about a node service (can be a Relay, a NameServer, a DiscoveryNode, etc)
type Service struct {
    IdAddr       common.Address
    KademliaAddr []byte // Kademlia address
    PssPubK      PubK   // Public Key of the pss node, to receive encrypted data packets
    Url          string
    Type         string // TODO define type specification (relay, nameserver, etc)
    Mode         string // Active or Passive(gateway) (this only affects to discovery-node's type)
    ProofService []byte // TODO ProofClaimService data type (to be defined)
}

// Query is the data packet that a node sends to discover data about one identity
type Query struct {
    Version          string         // version of the protocol
    MsgId            string         // random msg id, to identify and relate Query and Answer
    AboutId          common.Address // About Who is requesting data (about which identity address)
    RequesterId      common.Address
    RequesterKAddr   []byte // Kademlia address
    RequesterPssPubK PubK   // Public Key of the pss node requester, to receive encrypted data packets
    InfoFrom         []byte // TODO to be defined
    Timestamp        int64
    Nonce            uint64 // for the PoW
}

// Answer is the data packet that a node sends when answering to a Query data packet
type Answer struct {
    Version   string // version of the protocol
    MsgId     string // random msg id, to identify and relate Query and Answer
    AboutId   common.Address
    FromId    common.Address
    AgentId   Service
    Services  []Service
    Timestamp int64
    Signature []byte
}
Run
Run one node 
go run *.go --config config0.yaml start
Run 3 nodes and test endpoints 
bash run-tmux-demo.sh
Test

Unit tests:

go test ./...

Notifications Server

Overview

Notification server
Debugging

Dump DB counter collection:

mongo notifications-server --eval "c=db.getCollection('counters'); c.find();"

Dump DB notification collection:

mongo notifications-server --eval "c=db.getCollection('notifications'); c.find();"

Get notifications with curl:

curl -XPOST --data '{"idAddr": "0xd9d6800a1b20ceebef5420f878bbd915f8b4ed85"}' "http://127.0.0.1:10000/api/unstable/notifications?afterid=6&beforeid=9" | jq

Zero Knowledge Proof

zkSNARKs related utilities.

Repo Description
circom zkSNARKs circut compiler
circomlib Circuit libraries implementedin in circom
snarkjs zkSNARKs Javascript implementation (setup, proof, verifier and witness generation)
websnark A fast zkSNARKs proof generator written in native Web Assembly

Circom

Overview

Circom

Circom is a language designed to write arithmetic circuits that can be used in zero knowledge proofs.

In particular, it is designed to work in zksnarks JavaScript library.

Usage
Tutorial

A good starting point is this tutorial

Also this video is a good starting point.

First circuit

Creation of a circuit. This is an example of a NAND door:

template NAND() {
    signal private input a;
    signal input b;
    signal output out;

    out <== 1 - a*b;
    a*(a-1) === 0;
    b*(b-1) === 0;
}

component main = NAND();

The language uses mainly JavaScript/C syntax together with 5 extra operators to define the following constraints:

<== , ==> : These two operators are used to connect signals and at the same time imply a constraint.

As it is shown in the above example, a value is assigned to out and a constraint is also generated. The assigned value must be of the form a*b+c where a,b and c are linear combinations of the signals.

<-- , --> : These operators assign values to signals but do not generate any constraints. This allows to assign to a signal any value involving strange operations like shifts, divisions, modulo operations, etc. In general, these operators are used together with a === operator in order to force the constraint.

=== : This operator defines a constraint. The constraint must be simplificable to a constraint of the form a*b+c=0, where a, b and c are linear combinations of the signals.

In the above example, both inputs are forced to be binary by adding the constraints a*(a-1)===0 and b*(b-1) === 0.

Compilation the circuit

First of all, the compiler must be installed by typing:

npm install -g circom

The circuit is compiled with the following command:

circom mycircuit.circom -o mycircuit.json

The resulting output ( mycircuit.json ) can be used in the zksnarks JavaScript library.

In this library one can do the trusted setup, create the proofs and verify them.

Number to binary

In many situations, one has to convert an input to its binary representation. Therefore, the circuits can be written this way:

template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1=0;

    for (var i = 0; i<n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] -1 ) === 0;
        lc1 += out[i] * 2**i;
    }

    lc1 === in;
}

component main = Num2Bits(8)

First of all, note that templates can have parameters. This allows to create libraries with templates that generate circuits in parametric ways. In this case, the circuit has an output of 8 signals, but one can easily instantiate any circuit with any number of outputs.

The inputs and outputs are defined as arrays. The programm allows multidimensional arrays for signals and variables.

Then, the values are assigned to each of the signals. In this case, the values are assigned without the constraint using the shift and & operators: out[i] <-- (in >> i) & 1;

Afterwards, the constraints need to be defined. In this case, there is a big constraint of the form:

in === out[0]*2**0  + out[1]*2**1 + out[2]*2**2  + ... + out[n-1]*2**(n-1)

We do this by using a variable lc1 and adding each signal multiplied by its coefficient. This variable does not hold a value at compilation time, but it holds a linear combination and it is used in the last constraint:

lc1 === in;

The last step is to force each output to be binary. This is done by adding the following constraint to each output:

out[i] * (out[i] -1 ) === 0;
A binary adder

Let’s now create a 32bits adder.

This operation could be done directly by adding a simple constraint out === in1 + in2, but doing this the operation would not be module 2**32 but r, where ris the range of the elliptic curve. In the case of the zCash current implementation of zkSNARKs this number is typically some prime close to 2**253.

So, the strategy we will follow will be to first convert a number to binary, then do the addition using the binary representation like in regular electronic circuits, and finally change it back to a number.

To do this, we create 3 files: bitify.circom, binsum.circom and sum_test.circom.

bitify.circom:

template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1=0;

    for (var i = 0; i<n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] -1 ) === 0;
        lc1 += out[i] * 2**i;
    }

    lc1 === in;

}

template Bits2Num(n) {
    signal input in[n];
    signal output out;
    var lc1=0;

    for (var i = 0; i<n; i++) {
        lc1 += in[i] * 2**i;
    }

    lc1 ==> out;
}

binsum.circom

/*

Binary sum
==========

This component creates a binary sum componet of ops operands and n bits each operand.

e is number of carries and it depends on the number of operands in the input.

Main Constraint:
   in[0][0]     * 2^0  +  in[0][1]     * 2^1  + ..... + in[0][n-1]    * 2^(n-1)  +
 + in[1][0]     * 2^0  +  in[1][1]     * 2^1  + ..... + in[1][n-1]    * 2^(n-1)  +
 + ..
 + in[ops-1][0] * 2^0  +  in[ops-1][1] * 2^1  + ..... + in[ops-1][n-1] * 2^(n-1)  +
 ===
   out[0] * 2^0  + out[1] * 2^1 +   + out[n+e-1] *2(n+e-1)

To waranty binary outputs:

    out[0]     * (out[0] - 1) === 0
    out[1]     * (out[0] - 1) === 0
    .
    .
    .
    out[n+e-1] * (out[n+e-1] - 1) == 0

 */


/* This function calculates the number of extra bits in the output to do the full sum. */

function nbits(a) {
    var n = 1;
    var r = 0;
    while (n-1<a) {
        r++;
        n *= 2;
    }
    return r;
}


template BinSum(n, ops) {
    var nout = nbits((2**n -1)*ops);
    signal input in[ops][n];
    signal output out[nout];

    var lin = 0;
    var lout = 0;

    var k;
    var j;

    for (k=0; k<n; k++) {
        for (j=0; j<ops; j++) {
            lin += in[j][k] * 2**k;
        }
    }

    for (k=0; k<nout; k++) {
        out[k] <-- (lin >> k) & 1;

        // Ensure out is binary
        out[k] * (out[k] - 1) === 0;

        lout += out[k] * 2**k;
    }

    // Ensure the sum

    lin === lout;
}

sumtest.circom:

include "bitify.circom"
include "binsum.circom"

template Adder() {
    signal private input a;
    signal input b;
    signal output out;

    component n2ba = Num2Bits(32);
    component n2bb = Num2Bits(32);
    component sum = BinSum(32,2);
    component b2n = Bits2Num(32);

    n2ba.in <== a;
    n2bb.in <== b;

    for (var i=0; i<32; i++) {
        sum.in[0][i] <== n2ba.out[i];
        sum.in[1][i] <== n2bb.out[i];
        b2n.in[i] <== sum.out[i];
    }

    out <== b2n.out;
}

component main = Adder();

In this example we have shown how to design a top-down circuit with many subcircuits and how to connect them together. One can also see that auxiliary functions to do specific computations can be created.

More examples.

You can find more examples in this library of basic circits circomlib

License

Circom is part of the iden3 project copyright 2018 0KIMS association and published with GPL-3 license. Please check the COPYING file for more details.

Tutorial

circom and snarkjs tutorial

This tutorial will guide you in creating your first Zero Knowledge zkSnark circuit. It will navegate across the various techniques to write circuits and it will show you how to create proofs and verify them off-chain and on-chain on Ethereum.

1. Installing the tools
1.1 Pre-requisites

If you don’t have it installed yet, you need to install Node.js in your laptop.

Last stable version of Node.js (Or 8.12.0) works just fine. But if you install the latest current version Node.js (10.12.0) you will see significant performance increase. This is because last versions of node includes Big Integer Libraries nativelly. The snarkjs library makes use of this feature if available, and this improves the performance x10 (!).

1.2 Install circom and snarkjs

Just run:

npm install -g circom
npm install -g snarkjs
2. Working with a circuit

Let’s create a circuit that tries to prove that you are able to factor a number!

2.1 Create a circuit in a new directory
  1. Create an empty directory called factor where you will put all the files that you will use in this tutorial.
mkdir factor
cd factor
In a real circuit, you will probably want to create a git repository with a circuits directory and a test directory with all your tests, and the needed scripts to build all the circuits.
  1. Create a new file named circuit.circom with the following content:
template Multiplier() {
    signal private input a;
    signal private input b;
    signal output c;

    c <== a*b;
}

component main = Multiplier();

This circuit has 2 private input signals named a and b and one output named c.

The only thing that the circuit does is forcing the signal c to be the value of a*b

After declaring the Multiplier template, we instantiate it with a component namedmain.

Note: When compiling a circuit a component named main must always exist.

2.2 Compile the circuit

We are now ready to compile the circuit. Run the following command:

circom circuit.circom -o circuit.json

to compile the circuit to a file named circuit.json

3. Taking the compiled circuit to snarkjs

Now that the circuit is compiled, we will continue with snarkjs. Please note that you can always access the help of snarkjs by typing:

snarkjs --help
3.1 View information and stats regarding a circuit

To show general statistics of this circuit, you can run:

snarkjs info -c circuit.json

You can also print the constraints of the circuit by running:

snarkjs printconstraints -c circuit.json
3.2 Setting up using snarkjs

Ok, let’s run a setup for our circuit:

snarkjs setup
By default snarkjs will look for and use circuit.json. You can always specify a different circuit file by adding -c <circuit JSON file name>

The output of the setup will in the form of 2 files: proving_key.json and verification_key.json

3.3. Calculating a witness

Before creating any proof, we need to calculate all the signals of the circuit that match (all) the constrains of the circuit.

snarkjs calculates these for you. You need to provide a file with the inputs and it will execute the circuit and calculate all the intermediate signals and the output. This set of signals is the witness.

The zero knowledge proofs prove that you know a set of signals (witness) that match all the constraints but without revealing any of the signals except the public inputs plus the outputs.

For example, Imagine that you want to prove that you are able to factor 33 that means that you know two numbers a and b that when you multiply them, it results in 33.

Of course you can always use one and the same number as a and b. We will deal with this problem later.

So you want to prove that you know 3 and 11.

Let’s create a file named input.json

{"a": 3, "b": 11}

And now let’s calculate the witness:

snarkjs calculatewitness

You may want to take a look at witness.json file with all the signals.

Create the proof

Now that we have the witness generated, we can create the proof.

snarkjs proof

This command will use the prooving_key.json and the witness.json files by default to generate proof.json and public.json

The proof.json file will contain the actual proof. And the public.json file will contain just the values of the public inputs and the outputs.

Verifying the proof

To verify the proof run:

snarkjs verify

This command will use verification_key.json, proof.json and public.json to verify that is valid.

Here we are veifying that we know a witness that the public inputs and the outputs matches the ones in the public.json file.

If the proof is ok, you will see an OK in the screen or INVALID otherwise.

Generate the solidity verifier 
snarkjs generateverifier

This command will take the verification_key.json and generate a solidity code in verifier.sol file.

You can take the code in verifier.sol and cut and paste in remix.

This code contains two contracts: Pairings and Verifier. You just need to deploy the Verifier contract.

You may want to use a test net like Rinkeby, Kovan or Ropsten. You can also use the Javascript VM, but in some browsers, the verification takes long and it may hang the page.
Verifying the proof on-chain

The verifier contract deployed in the last step has a view function called verifyProof.

This function will return true if the proof and the inputs are valid.

To facilitiate the call, you can use snarkjs to generate the parameters of the call by typing:

snarkjs generatecall

Just cut and paste the output to the parameters field of the verifyProof method in Remix.

If every thing works ok, this method should return true.

If you just change any bit in the parameters, you can check that the result will be false.

Bonus track

We can fix the circuit to not accept one as any of the values by adding some extra constraints.

Here the trick is that we use the property that 0 has no inverse. so (a-1) should not have an inverse.

that means that (a-1)*inv = 1 will be inpossible to match if a is one.

We just calculate inv by 1/(a-1)

So let’s modify the circuit:

template Multiplier() {
    signal private input a;
    signal private input b;
    signal output c;
    signal inva;
    signal invb;

    inva <-- 1/(a-1);
    (a-1)*inva === 1;

    invb <-- 1/(b-1);
    (b-1)*invb === 1;

    c <== a*b;
}

component main = Multiplier();

A nice thing of circom language is that you can split a <== into two independent acions: <– and ===

The <– and –> operators Just assign a value to a signal without creating any constraints.

The === operator just adds a constraint without assigning any value to any signal.

The circuit has also another problem and it’s that the operation works in Zr, so we need to guarantee too that the multiplication does not overflow. This can be done by binarizing the inputs and checking the ranges, but we will reserve it for future tutorials.

Where to go from here.

You may want to read the README to learn more features about circom.

You can also check a a library with many basic circuits lib binaritzations, comparators, eddsa, hashes, merkle trees etc here (Work in progress).

Or a exponentiation in the Baby Jub curve here (Work in progress).

Final note

There is nothing worst for a dev than working with a buggy compiler. This is a very early stage of the compiler, so there are many bugs and lots of works needs to be done. Please have it present if you are doing anything serious with it.

And please contact us for any isue you have. In general, a github issue with a small piece of code with the bug is very worthy!.

Enjoy zero knowledge proving!

CircomLib

SnarkJS

Overview

snarkjs: JavaScript implementation of zkSNARKs.

This is a JavaScript implementation of zkSNARK schemes. It allows the original 8points protocol and the Groth Protocol (3 point only and 3 pairings)

This library allows to do the trusted setup, generate proofs and verify the proofs.

This library uses the compiled circuits generated by the jaz compiler.

Tutorial.

A good starting point is this tutorial

Also this video is a good starting point.

Install. 
npm install snarkjs
Usage from command line. 
snarkjs --help

Will show all the info in how to use the cli.

Usage from javascript
Import.
const zkSnark = require("snarkjs");
Load a circuit.
// "myCircuit.cir" is the output of the jaz compiler

const circuitDef = JSON.parse(fs.readFileSync("myCircuit.cir", "utf8"));
const circuit = new zkSnark.Circuit(circuitDef);
Inspect the circuit.
// `signalId` can always be a number or an alias string

circuit.nConstraints; // number of constraints
circuit.nSignals; // number of signals
circuit.nPublic; // number of public signals (nOutputs + nPublicInputs)

// The array of signals is always sorted in this order:
// [ 1, outputs, publicInputs, privateInputs, internalSignals, constants]

// returns a,b and c coeficients of the `signalId` on a given `constraint`
circuit.a(constraint, signalId)
circuit.b(constraint, signalId)
circuit.c(constraint, signalId)

circuit.nOutputs           // number of public outputs
circuit.pubInputs          // number of public inputs
circuit.nPrvInputs         // number of private inputs
circuit.nInputs            // number of inputs ( nPublicInputs + nPrivateInputs)
circuit.nVars              // number of variables ( not including constants (one is a variable) )
circuit.nSignals           // number of signals ( including constants )

circuit.outputIdx(i)       // returns the index of the i'th output
circuit.inputIdx(i)        // returns the index of the i'th input
circuit.pubInputIdx(i)     // returns the index of the i'th public input
circuit.prvInputIdx(i)     // returns the index of the i'th private input
circuit.varIdx(i)          // returns the index of the i'th variable
circuit.constantIdx(i)     // returns the index of the i'th constant
circuit.signalIdx(i)       // returns the index of the i'th signal

// returns signal Idx given a signalId
// if the idx >= n , it is a constant
// if the idx == -1, the signal does not exist
circuit.getSignalIdx(name);

// returns an array aliases names of the i'th signal
circuit.signalNames(i)

// input is a key value object where keys are the signal names
//   of all the inputs (public and private)
// returns an array of values representing the witness
circuit.calculateWitness(input)
Trusted setup.
const setup = zkSnark.setup(circuit);
fs.writeFileSync("myCircuit.vk_proof", JSON.stringify(setup.vk_proof), "utf8");
fs.writeFileSync("myCircuit.vk_verifier", JSON.stringify(setup.vk_verifier), "utf8");
setup.toxic  // Must be discarded.
Generate proof.
const circuitDef = JSON.parse(fs.readFileSync("myCircuit.cir", "utf8"));
const circuit = new zkSnark.Circuit(circuitDef);
const input = {
    "main.pubIn1": "123",
    "main.out1": "456"
}
const witness = circuit.calculateWitness(input);
const vk_proof = JSON.parse(fs.readFileSync("myCircuit.vk_proof", "utf8"));

const {proof, publicSignals} = zkSnark.genProof(vk_proof, witness);
Verifier.
const vk_verifier = JSON.parse(fs.readFileSync("myCircuit.vk_verifier", "utf8"));

if (zkSnark.isValid(vk_verifier, proof, publicSignals)) {
    console.log("The proof is valid");
} else {
    console.log("The proof is not valid");
}
License

snarkjs is part of the iden3 project copyright 2018 0KIMS association and published with GPL-3 license. Please check the COPYING file for more details.

Websnark

Overview

websnark

A fast zkSnark proof generator written in native Web Assembly.

websnark is used to generate zkSnark Proofs from the browser.

This module generates highly optimized Web Assembly modules for the low level cryptographic primitives.

It also makes use of the Web Workers feature to parallelize the generation of the zero knoledge proofs.

The result is a fast library with times close to libsnarks but fully compatible for browsers.

Usage

You just need to import the websnark.js found in the build directory.

<script src="websnark.js" />

This library has a single javascript function:

genZKSnarkProof(witness, provingKey, cb)

cb is the callback. If cb is undefined, then the function will return a promise.

witness is a binary buffer with all the signals in binnary format. The buffer is packt in 32bytes Little Endian Encoded Field Elements.

You can use the tool to build the binary file from the witness.json file generated by snarkjs.

IMPORTANT: Please be sure you run your setup with --protocol groth websnark only generates groth16 proofs! 
node ../tools/buildwitness.js -i witness.json -o witness.bin

provingKey is the binary buffer with the binary representation of the proving key.

Check the tool tools/buildpkey.js to convert a proving_key.json file generated in snarkjs to a proving_key.bin file that can be used directly with this library.

node ../tools/buildpkey.js -i proving_key.json -o proving_key.bin

The result is a JSON object with pi_a, pi_b and pi_c points.

You can use the stringified version of this JSON as a proof.json in snarkjs

Here is a simple example of a web page that loads a key and a witness and generates the proof when the button is pressed.

<html>
<header>
</header>
<script src="websnark.js"></script>
<script>

var witness;
var proving_key;

function onLoad() {

    fetch("proving_key.bin").then( (response) => {
        return response.arrayBuffer();
    }).then( (b) => {
        provingKey = b;
    });

    fetch("witness.bin").then( (response) => {
        return response.arrayBuffer();
    }).then( (b) => {
        witness = b;
    });
}

function calcProof() {
    const start = new Date().getTime();
    document.getElementById("time").innerHTML = "processing....";
    document.getElementById("proof").innerHTML = "";

    window.genZKSnarkProof(witness, provingKey).then((p)=> {
        const end = new Date().getTime();
        const time = end - start;
        document.getElementById("time").innerHTML = `Time to compute: ${time}ms`;
        document.getElementById("proof").innerHTML = JSON.stringify(p, null, 1);
    });
}

</script>
<body onLoad="onLoad()">
<h1>iden3</h1>
<h2>Zero knowledge proof generator</h2>
<button onClick="calcProof()">Test</button>
<div id="time"></div>
<pre id="proof"></pre>

</body>
</html>

You can test it by running a web server on the example directory

npm -g install http-server
cd example
http-server .

And then navegate to http://127.0.0.1:8080

The generated proof can be cut and pasted to example/proof and tested with snarkjs

snarkjs verify
``

## Building wasm.js

npm run build

## Testing

npm test ```

License

websnark is part of the iden3 project copyright 2019 0KIMS association and published with GPL-3 license. Please check the COPYING file for more details.

Misc

Miscellaneous utilities.

Repo Description
wasmbuilder Javascript library to simplify writing Web Assembly code

Web Assembly Builder

Research Papers

Baby Jubjub

1.2

Scope

This proposal aims to define a specific elliptic curve defined over the large prime subgroup of BN128 elliptic curve.

Motivation

The search for this elliptic curve defined is motivated by its usefulness in zk-SNARK proofs. Moreover the ability to find it in a deterministic way—so that it was clear no other considerations were taken for defining—is paramount as it significantly reduces the possibility of a backdoor being present, thus leading to better security.

Background

With this purpose, we used a deterministic algorithm for finding elliptic curves over a specified finite field (Langley, Hamburg, and Turner, n.d.) together with the restrictions of security parameters described in SafeCurves project (Bernstein and Lange, n.d.).

Terminology And Description

Generation Of Baby Jubjub
In 2016, a group of researchers of IRPF designed a deterministic algorithm that, given a prime number \(p\), it returns the elliptic curve defined over \(\ensuremath{\mathbb{F}_p}\) with smallest coefficient \(A\) such that \(A-2\) is a multiple of 4 and equation \(y^2 = x^3 + Ax^2 + x\) describes a Montgomery curve. The assumption \(A-2\) divisible by 4 comes from the fact that as this value is used in many operations, so trying to keep it smaller and divisible by four is a reasonable assumption (Langley, Hamburg, and Turner, n.d.).
SafeCurves is a project that checks some of the most common and known attacks on several elliptic curves. It also provides the algorithm it was used (Bernstein and Lange, n.d.).
We considered the large prime number dividing the order of BN128 and run algorithm A.1 from (Langley, Hamburg, and Turner, n.d.). The first elliptic curve it was returned satisfying SafeCurves criteria was the Montgomery curve with coefficient \(A = 168698\). We named this curve Baby Jubjub elliptic curve.
Definition Of Baby Jubjub

From now on, let

\[ \begin{align}\begin{aligned} p = 21888242871839275222246405745257275088548364 400416034343698204186575808495617\\and :math:`\ensuremath{\mathbb{F}_p}` the finite field with :math:`p`\end{aligned}\end{align} \]

elements.

Montgomery Form

We define \(E_M\) as the Baby-Jubjub Montgomery elliptic curve defined over \(\ensuremath{\mathbb{F}_p}\) given by equation

\[ \begin{align}\begin{aligned}E: v^2 = u^3 + 168698u^2 + u.\\The order of :math:`E_M` is :math:`n = 8\times r`, where\end{aligned}\end{align} \]
\[ \begin{align}\begin{aligned} r = 2736030358979909402780800718157159386076813972 158567259200215660948447373041\\is a prime number. Denote by :math:`\ensuremath{\mathbb{G}}` the\end{aligned}\end{align} \]

subgroup of points of order \(r\), that is,

\[\ensuremath{\mathbb{G}}= \Set{ P \in E(\ensuremath{\mathbb{F}_p}) | r P = O }.\]
Edwards Form
\(E_M\) is birationally equivalent to the Edwards elliptic curve
\[ \begin{align}\begin{aligned}E: x^2 + y^2 = 1 + d x^2 y^2\\where\end{aligned}\end{align} \]

\(d = 9706598848417545097372247223557719406784115219466060233080913168975159366771.\)

The birational equivalence (Bernstein et al., n.d. Thm. 3.2) from \(E\) to \(E_M\) is the map
\[ \begin{align}\begin{aligned}(x,y) \to (u,v) = \left( \frac{1 + y}{1 - y} , \frac{1 + y}{(1 - y)x} \right)\\with inverse from :math:`E_M` to :math:`E`\end{aligned}\end{align} \]
\[(u, v) \to (x, y) = \left( \frac{u}{v}, \frac{u - 1}{u + 1} \right).\]
Arithmetic In Baby Jubjub

In this section we define how to operate in the elliptic curve group: the addition of points and multiplication of a point by a scalar (an element of \(\ensuremath{\mathbb{F}_p}\)).

Addition Of Points

When adding points of elliptic curves in Montgomery form, one has to be careful if the points being added are equal (doubling) or not (adding) and if one of the points is the point at infinity (Okeya, Kurumatani, and Sakurai 2000). Edwards curves have the advantage that there is no such case distinction and doubling can be performed with exactly the same formula as addition (Bernstein et al., n.d.). In comparison, operating in Montgomery curves is cheaper. In this section, we summarize how addition and doubling is performed in both forms. For the exact number of operations required in different forms of elliptic curves, see (Bernstein et al., n.d.).

  • : Let \(P_{1} = (x_{1}, y_{1})\) and \(P_{2} = (x_{2}, y_{2})\) be points of the Baby-Jubjub twisted Edwards elliptic curve \(E\). The sum \(P_1 + P_2\) is a third point \(P_3 = (x_3, y_3)\) with

    \[ \begin{align}\begin{aligned}\begin{split} \begin{aligned} &\lambda = d x_1x_2y_1y_2,\\ &x_3 = (x_1y_2 + y_1x_2) / (1 + \lambda),\\ &y_3 = (y_1y_2 - x_1x_2) / (1 - \lambda). \end{aligned}\end{split}\\Note that the neutral element is the point :math:`O = (0,1)` and the\end{aligned}\end{align} \]

    inverse of a point \((x,y)\) is \((-x,y)\).

  • : Let \(P_{1} = (x_{1}, y_{1})\not=O\) and \(P_{2} = (x_{2}, y_{2})\not=O\) be two points of the Baby-JubJub elliptic curve \(E_M\) in Montgomery form.

    If \(P_1\not=P_2\), then the sum \(P_1 + P_2\) is a third point \(P_3 = (x_3, y_3)\) with coordinates

    \[ \begin{align}\begin{aligned}\begin{split} \begin{aligned} \label{eq-ted} \begin{split} &\Lambda = (y_2-y_1)/ (x_2-x_1),\\ &x_3 = \Lambda^2 - A - x_1 - x_2,\\ &y_3 = \Lambda(x_1- x_3) - y_1. \end{split} \end{aligned}\end{split}\\If :math:`P_1 = P_2`, then :math:`2\cdot P_1` is a point\end{aligned}\end{align} \]

    \(P_3 = (x_3, y_3)\) with coordinates

    \[\begin{split}\begin{aligned} \label{eq-mont} \begin{split} &\Lambda = (3x_1^2 + 2Ax_1 + 1)/ (2y_1),\\ &x_3 = \Lambda^2 - A - 2x_1,\\ &y_3 = \Lambda(x_1- x_3) - y_1. \end{split} \end{aligned}\end{split}\]
Multiplication Of A Point Of \(E\) By A Scalar

Let \(P\not= O\) be a point of the Edwards curve \(E\) of order strictly greater than 8 (i.e. \(P\in\ensuremath{\mathbb{G}}\)) and let \(k\) a binary number representing an element of \(\ensuremath{\mathbb{F}_p}\). We describe the circuit used to compute the point \(k\cdot P\).

  1. First, we divide \(k\) into chunks of 248 bits. If \(k\) is not a multiple of 248, we take \(j\) segments of 248 bits and leave a last chunk with the remaining bits. More precisly, write

    \[ \begin{align}\begin{aligned}\begin{split} \begin{gathered} k = k_0 k_1 \dots k_j \quad\text{with}\quad \begin{cases} k_i = b^i_0 b^i_1 \dots b^i_{247} \;\text{ for } i = 0, \dots, j-1, \\ k_j = b^j_0 b^j_1 \dots b^j_s \;\text{ with } s\leq 247. \end{cases} \end{gathered}\end{split}\\Then,\end{aligned}\end{align} \]
    \[ \begin{align}\begin{aligned} \label{kP} k\cdot P = k_0\cdot P + k_1\cdot 2^{248}P +\dots+ k_j\cdot 2^{248j}P.\\This sum is done using the following circuit. The terms of the sum\end{aligned}\end{align} \]

    are calculated separately inside the seq boxes and then added together.

    image

  2. Each seq box takes a point of \(E\) of the from \(P_i = 2^{248 i} P\) for \(i=0,\dots,j-1\) and outputs two points

    \[ \begin{align}\begin{aligned} 2^{248} \cdot P_i \quad \text{and} \quad \sum_{n = 0}^{247} b_n \cdot 2^{n} \cdot P_i.\\The first point is the input of the next :math:`(i+1)`-th seq box\end{aligned}\end{align} \]

    (note that \(2^{248} \cdot P_i = P_{i+1}\)) whereas the second output is the computation of the \(i\)-th term in expression ([kP]). The precise circuit is depicted in next two figures seq and window.

    image

    image

    The idea of the circuit is to first compute

    \[ \begin{align}\begin{aligned} Q = P_i + b_1 \cdot (2P_i) + b_2 \cdot (4P_i) + b_3 \cdot (8P_i) + \dots + b_{247} \cdot (2^{247}P_i),\\and output the point\end{aligned}\end{align} \]
    \[ \begin{align}\begin{aligned}Q - b_0 \cdot P_i.\\This permits the computation of :math:`Q` using the Montgomery form\end{aligned}\end{align} \]

    of Baby-Jubjub and only use twisted Edwards for the second calculation. The reason to change forms is that, in the calculation of the output, we may get a sum with input the point at infinity if \(b_0 = 0\).

    Still, we have to ensure that none of the points being doubled or added when working in \(E_M\) is the point at infinity and that we never add the same two points.

    • By assumption, \(P\not= O\) and ord\((P)>8\). Hence, by Lagrange theorem (Baumslag and Chandler 1968 Corollary 4.12), \(P\) must have order \(r\), \(2r\), \(4r\) or \(8r\). For this reason, none of the points in \(E_M\) being doubled or added in the circuit is the point at infinity, because for any integer \(m\), \(2^m\) is never a multiple of \(r\), even when \(2^m\) is larger than \(r\), as \(r\) is a prime number. Hence, \(2^m \cdot P \not= O\) for any \(m\in\ensuremath{\mathbb{Z}}\).
    • Looking closely at the two inputs of the sum, it is easy to realize that they have different parity, one is an even multiple of \(P_i\) and the other an odd multiple of \(P_i\), so they must be different points. Hence, the sum in \(E_M\) is done correctly.

  3. The last term of expression ([kP]) is computed in a very similar manner. The difference is that the number of bits composing \(k_j\) may be shorter and that there is no need to compute \(P_{j+1}\), as there is no other seq box after this one. So, there is only output, the point \(k_j \cdot P_j = k_j\cdot 2^{248j} P\). This circuit is named seq’.

    image

Challenges And Security

As required in the construction of Baby-Jubjub, the curve satisfies SafeCurves criteria. This can be checked following (Hat, n.d.).

Intellectual Property

We will release the final version of this proposal under creative commons, to ensure it is freely available to everyone.

Baumslag, Benjamin, and Bruce Chandler. 1968. Schaum’s Outline of Theory and Problems of Group Theory. Schaum’s Outline Series. New York: McGraw-Hill Book Company.

Bernstein, Daniel J., Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters. n.d. “Twisted Edwards Curves.” Cryptology ePrint Archive, Report 2008/013.

Bernstein, Daniel J., and Tanja Lange. n.d. “SafeCurves: Choosing Safe Curves for Elliptic-Curve Cryptography.”

Hat, Barry White. n.d. “Baby-Jubjub Supporting Evidence.” GitHub.

Langley, Adam, Mike Hamburg, and Sean Turner. n.d. “Elliptic Curves for Security.” Request for Comments. RFC 7748; RFC Editor. https://doi.org/10.17487/RFC7748.

Okeya, Katsuyuki, Hiroyuki Kurumatani, and Kouichi Sakurai. 2000. “Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications.” In Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, 238–57. PKC ’00. London, UK, UK: Springer-Verlag. http://dl.acm.org/citation.cfm?id=648117.746614.

Merkle Tree

Scope

A Merkle tree or hash tree is an authenticated data structure where every leaf node of the tree contains the cryptographic hash of a data block and every non leaf node contains the concatenated hashes of its child nodes (Haider 2018). If the majority of the leaves are empty, then they are called sparse Merkle trees (Dahlberg, Pulls, and Peeters 2016). This proposal aims to standardize the generation of this second kind of binary trees.

Motivation

Merkle trees allow to link a set of data to a unique has value, which is very optimal and useful, specially in blockchain technology, as it provides a secure and efficient verification of large data sets by storing only a little piece of data on-chain. For instance, they can be used to verify any kind of data stored, handled and transferred in and between computers. They can help ensure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, and even to check that the other peers do not lie and send fake blocks (Wikipedians, n.d.).

Background

We are still working on the literature compending the state of the art of this area.

Terminology

The following concepts are definitions and properties we assume across the document.

  • The leaves of the Merkle tree consist of key-value pairs \((k,v)\). We distinguish three different nodes:
    • Empty node: A vertex that stores the key and value zero.
    • Leaf: A vertex with both empty children.
    • Internal node: A vertex with at least one non-empty child. The value is and the key such. It has the hash of its children.
  • A Merkle audit path for a leaf in a Merkle tree is the shortest list of additional nodes in the tree required to compute the root hash for that tree.
  • If the root computed from the audit path matches the true root, then the audit path is a proof of membership for that leaf in the tree.
  • Otherwise, it is a proof of non-membership for that leaf in the tree.

image

Challenges

Work in progress.

Description

Let \(e=(k,v)\) be a new entry in a tree \(T\). The node in which this piece of data \(e\) is stored in \(T\) is uniquely determined from the data itself. Let \(H\) be a secure hash function returning an array of bits. [1] The leaf in which \(e\) should be stored in \(T\) is defined by
\[ \begin{align}\begin{aligned}H_{path} = H(e) = H(1 || k || v).\\This array of bits is going to represent a path through the tree:\end{aligned}\end{align} \]

starting by the less significant bit and from the root of \(T\), it descents the tree by taking the left edge if there is a 0 and right one if there is a 1.

When adding an entry \(e\), we may not (see Sec. 7) go down to the last level of the tree (by last we mean looking at all the bits, length of which depends on the hash function \(H\)). What we do instead, is go down through the path until we find a node without siblings (a leaf). If the leaf is empty, we store \(e\). Otherwise, that node stores some other \(e'\) (as non-empty leafs store claims) with \(H(e') = H'_{path}\). This means that \(H_{path}\) and \(H'_{path}\) start with the same sequence of bits. We compare both hashes and go down the tree until the first different bit. these two values and find the first different bit (included). Then we store \(e\) and \(e'\) in their corresponding leafs of the path.
As an example, consider \(e\) such that \(H_{path}=0111111...\) and the Merkle tree below where in each leaf there is represented the value (and not the key) of each stored piece of data:

image

If we go down the tree following the sequence 01111111… we get to the leaf containing the value 0704eaec of some \(e'\) with \(H'_{path}=0111110...\) . Comparing \(H_{path}\) and \(H'_{path}\), the 7th bit is the first different bit. This means, that we should go down to the 7th level and store there the entries as shown in next figure:

image

Note that \(e\) is stored in the right (as the 7th bit is a 1) and \(e'\) is stored in the left (as it is a 0). Also note that the rest of siblings are empty nodes and how the root and intermediate nodes have changed.
Each node is of the form \((H[b, k, v])\), where \(b = 1\) if terminal node (leaf) and \(b = 0\) otherwise. More precisely,
  • Each leaf consists of a pair (\(H(1 || k || v)\), \(k||v\)).
  • Each intermediate node of a pair (\(H(H_L||H_R)\), \(K_L||K_R\)), where \((H_L,K_L)\) is the key-value of its left child and \((H_L,K_L)\) the key-value of its right child.

The procedure to store an entry in a Merkle tree is described below in pseudocode.

\(H_{path} \gets \text{GetPath($e$)}\) \(b \gets \text{LeastSignificantBit($H_{Index}$)}\) \(r \gets e\) \(r \gets e\) \(H_{Index} \gets H_{Index}\backslash{b}\) \(b \gets \text{LeastSignificantBit($H_{Index}$)}\) \(e' \gets \text{GetEntryStoredIn($r$)}\) \(H'_{path} \gets \text{GetPath($e'$)}\) Find first bit \(b_j\) such that \(H_{path}(j) \not= H'_{path}(j)\) Leaf(\(b_0...b_j\))\(\gets e\) Leaf(\(b_0...b'_j\))\(\gets e'\) RecalculateIntermediateNodeValues(\(T\))

: On one side, DELETE of entries and UPDATE of the tree. On the other side, the generation of MEMBERSHIP proofs and generation of NON-MEMBERSHIP proofs.
These last two procedure, although we are working on explaining them in detail in the following delivery, they have already been implemented in GoLang and JavaScript in the following two repositories:

Security

The security of an audit path reduces to the collision resistance of the underlying hash function. For a proof, see (Dahlberg, Pulls, and Peeters 2016 Lemma 1).

Implementation

The standarisation of Merkle trees we proposed are described an implemented in GoLang and JavaScript by the iden3 team in the following repositories:

Some detailed examples are also provided in these repositories:

Intellectual Property

We will release the final version of this proposal under creative commons, to ensure it is freely available to everyone.

Dahlberg, Rasmus, Tobias Pulls, and Roel Peeters. 2016. “Efficient Sparse Merkle Trees: Caching Strategies and Secure (Non-)Membership Proofs.” Cryptology ePrint Archive, Report 2016/683.

Haider, Faraz. 2018. “Compact Sparse Merkle Trees.” Cryptology ePrint Archive, Report 2018/955.

Wikipedians, B. n.d. Data Structures. PediaPress. https://books.google.es/books?id=aYxSZurAGXEC.

[1]If the hash function \(H\) does not return a binary number, binarize it later.

ED-DSA

1.2

Scope

This proposal aims to standarize the elliptic curve signature scheme Edwards-curve Digital Signature Algorithm (EdDSA) for Baby Jubjub Edwards elliptic curve using MiMC-7 hash function.

Motivation

EdDSA is a variant of Schnorr’s signature scheme and it provides high performance on a variety of platforms (Josefsson and Liusvaara, n.d.).

Background

There are many implementations of EdDSA with Edwards elliptic curves such as Ed25519 or Ed448-Goldilocks and most of them use hash SHA-512. This is the first document specifying a protocol for implementing EdDSA using MiMC-7 and we describe it on the Baby Jubjub Elliptic curve.
The choice of the MiMC-7 hash function makes computations inside circuits very efficient and it has a big potential in zero knowledge protocols such as zk-SNARK.

Terminology

The table below summarizes the terminology used across the document. Each element is explained in greater detail in the following sections.

Notation Description
\(p\) Prime number.
\(\ensuremath{\mathbb{F}_p}\) Finite field with \(p\) elements.
\(E\) Baby Jubjub elliptic curve (defined over \(Fp\)) in Edwards form.
\(E_M\) Baby Jubjub elliptic curve (defined over \(Fp\)) in Montgomery form.
\(l\) Large prime number dividing the order of Baby Jubjub.
\(\ensuremath{\mathbb{F}_l}\) Finite field with \(l\) elements.
\(\ensuremath{\mathbb{G}}\) Group of \(\ensuremath{\mathbb{F}_p}\) -rational points of order \(l\).
\(B\) Base point (generator of \(\ensuremath{\mathbb{G}}\)) of Baby Jubjub.
\(A = (A_x, A_y)\) Public key. \(A\) is a point on \(E\).
\(k\) Private key.
\(M\) Message. \(M\) is an element of \(\ensuremath{\mathbb{F}_l}\) .
\((R,S) = ((R_x, R_y), S)\) Signature on \(M\). \(R\) is a point on \(E\) and \(S\) and element of \(\ensuremath{\mathbb{F}_l}\) .
\(H\) Hash function MiMC-7.
\(r\) Number of rounds of MiMC-7.
\(c_0, c_1, \dots, c_r\) Constants used in MiMC-7.

[tab:notation]

Baby-Jubjub
Consider the prime number
\[ \begin{align}\begin{aligned} p = 21888242871839275222246405745257275088548364 400416034343698204186575808495617\\and let :math:`\ensuremath{\mathbb{F}_p}` be the finite field with\end{aligned}\end{align} \]

\(p\) elements. We define \(E_M\) as the Baby-Jubjub Montgomery elliptic curve defined over \(\ensuremath{\mathbb{F}_p}\) given by equation

\[ \begin{align}\begin{aligned}E: v^2 = u^3 + 168698u^2 + u.\\The order of :math:`E_M` is :math:`n = 8\times l`, where\end{aligned}\end{align} \]
\[ \begin{align}\begin{aligned} l = 2736030358979909402780800718157159386076813972 158567259200215660948447373041\\is a prime number. Denote by :math:`\ensuremath{\mathbb{G}}` the\end{aligned}\end{align} \]

subgroup of points of order \(l\), that is,

\[ \begin{align}\begin{aligned}\ensuremath{\mathbb{G}}= \Set{ P \in E(\ensuremath{\mathbb{F}_p}) | l P = O }.\\Let\end{aligned}\end{align} \]
\[ \begin{align}\begin{aligned}\begin{split} \begin{aligned} B = (17777552123799933955779906779655732241715742912184938656739573121738514868268,\\ 2626589144620713026669568689430873010625803728049924121243784502389097019475)\end{aligned}\end{split}\\be a generator of :math:`\ensuremath{\mathbb{G}}`.\end{aligned}\end{align} \]
\(E_M\) is birationally equivalent to the Edwards elliptic curve
\[ \begin{align}\begin{aligned}E: x^2 + y^2 = 1 + d x^2 y^2\\where\end{aligned}\end{align} \]

\(d = 9706598848417545097372247223557719406784115219466060233080913168975159366771.\)

The birational equivalence (Bernstein et al., n.d. Thm. 3.2) from \(E\) to \(E_M\) is the map
\[ \begin{align}\begin{aligned}(x,y) \to (u,v) = \left( \frac{1 + y}{1 - y} , \frac{1 + y}{(1 - y)x} \right)\\with inverse from :math:`E_M` to :math:`E`\end{aligned}\end{align} \]
\[(u, v) \to (x, y) = \left( \frac{u}{v}, \frac{u - 1}{u + 1} \right).\]
MiMC-7
The hash function used in EdDSA is MiMC-7 based in paper (Albrecht et al. 2016), which describes the hash using exponent 3. In this specification, we use exponent 7 (hence the name MiMC-7) as 3 and \(l-1\) are not coprime and 7 is the optimal choice for exponentiation (Albrecht et al. 2016 Sec. 6).
Let \(\ensuremath{\mathbb{F}_l}\) be the finite field with \(l\) elements. The block cipher is constructed by iterating a round function \(r\) times where each round consists of a key addition with the key \(k\), the addition of a round constant \(c_i\in \ensuremath{\mathbb{F}_r}\), and the application of a non-linear function defined as \(F(x) :=x^7\) for \(x\in \ensuremath{\mathbb{F}_l}\). The ciphertext is finally produced by adding the key \(k\) again to the output of the last round. Hence, the round function is described as \(F_i(x) = F(x) \oplus k \oplus c_i\) where \(c_0 = c_r = 0\) and the encryption process is defined as
\[E_k(x) = (F_{r-1} \circ F_{r-2} \circ ... \circ F_0)(x) \oplus k.\]

= [draw, minimum size=2em] = [pin edge=to-,thin,black]

As the random constants \(c_i\) do not need to be generated for every evaluation of MiMC-7, they are hard-coded into the implementation. The generation of these constants and the required number of rounds is described in section 6.2.

EdDSA

The description of this protocol is based in (Josefsson and Liusvaara, n.d.): Let the public key be a point \(A = (A_x, A_y)\in E\) of order \(l\) and \(M\) a message we wish to sign. The signature on \(M\) by \(A\) consists of a par \((R,S)\) where \(R = (R_x, R_y)\) is a point of order \(l\) of \(E\) and \(S\in\ensuremath{\mathbb{F}_l}\backslash\{0\}\) such that

\[8SB = 8R + 8H(R,A,M)A.\]

Challenges and security

One of the main challenges to create this standard and to see it adopted by the community is to provide correct, usable, and well-maintained implementations in as many languages as possible. Some effort is also required to audit and verify code coming from the community and claiming to implement EdDSA for Baby Jubjub to prevent the propagation of potentially insecure implementations. Part of the work in progress of looking batch verification of short signatures. Lastly, the proposal as it stands uses MiMC-7 as hash function as it works very optimal inside circuits. We believe some work is required to determinate the security MiMC hash functions.

Implementation

In this section, we specify how each of the main operations in the following EdDSA circuit are computed:

image

Operations in the elliptic curve
Addition of points

When adding points of elliptic curves in Montgomery form, one has to be careful if the points being added are equal (doubling) or not (adding) and if one of the points is the point at infinity (Okeya, Kurumatani, and Sakurai 2000). Edwards curves have the advantage that there is no such case distinction and doubling can be performed with exactly the same formula as addition (Bernstein et al., n.d.). In comparison, operating in Montgomery curves is cheaper. In this section, we summarize how addition and doubling is performed in both forms. For the exact number of operations required in different forms of elliptic curves, see (Bernstein et al., n.d.).

  • : Let \(P_{1} = (x_{1}, y_{1})\) and \(P_{2} = (x_{2}, y_{2})\) be points of the Baby-Jubjub twisted Edwards elliptic curve \(E\). The sum \(P_1 + P_2\) is a third point \(P_3 = (x_3, y_3)\) with

    \[ \begin{align}\begin{aligned}\begin{split} \begin{aligned} &\lambda = d x_1x_2y_1y_2,\\ &x_3 = (x_1y_2 + y_1x_2) / (1 + \lambda),\\ &y_3 = (y_1y_2 - x_1x_2) / (1 - \lambda). \end{aligned}\end{split}\\Note that the neutral element is the point :math:`O = (0,1)` and the\end{aligned}\end{align} \]

    inverse of a point \((x,y)\) is \((-x,y)\).

  • : Let \(P_{1} = (x_{1}, y_{1})\not=O\) and \(P_{2} = (x_{2}, y_{2})\not=O\) be two points of the Baby-JubJub elliptic curve \(E_M\) in Montgomery form.

    If \(P_1\not=P_2\), then the sum \(P_1 + P_2\) is a third point \(P_3 = (x_3, y_3)\) with coordinates

    \[ \begin{align}\begin{aligned}\begin{split} \begin{aligned} \label{eq-ted} \begin{split} &\Lambda = (y_2-y_1)/ (x_2-x_1),\\ &x_3 = \Lambda^2 - A - x_1 - x_2,\\ &y_3 = \Lambda(x_1- x_3) - y_1. \end{split} \end{aligned}\end{split}\\If :math:`P_1 = P_2`, then :math:`2\cdot P_1` is a point\end{aligned}\end{align} \]

    \(P_3 = (x_3, y_3)\) with coordinates

    \[\begin{split}\begin{aligned} \label{eq-mont} \begin{split} &\Lambda = (3x_1^2 + 2Ax_1 + 1)/ (2y_1),\\ &x_3 = \Lambda^2 - A - 2x_1,\\ &y_3 = \Lambda(x_1- x_3) - y_1. \end{split} \end{aligned}\end{split}\]
Multiplication of a point of \(E\) by a scalar

Let \(P\not= O\) be a point of the Edwards curve \(E\) of order strictly greater than 8 (i.e. \(P\in\ensuremath{\mathbb{G}}\)) and let \(k\) a binary number representing an element of \(\ensuremath{\mathbb{F}_p}\). We describe the circuit used to compute the point \(k\cdot P\).

  1. First, we divide \(k\) into chunks of 248 bits. If \(k\) is not a multiple of 248, we take \(j\) segments of 248 bits and leave a last chunk with the remaining bits. More precisly, write

    \[ \begin{align}\begin{aligned}\begin{split} \begin{gathered} k = k_0 k_1 \dots k_j \quad\text{with}\quad \begin{cases} k_i = b^i_0 b^i_1 \dots b^i_{247} \;\text{ for } i = 0, \dots, j-1, \\ k_j = b^j_0 b^j_1 \dots b^j_s \;\text{ with } s\leq 247. \end{cases} \end{gathered}\end{split}\\Then,\end{aligned}\end{align} \]
    \[ \begin{align}\begin{aligned} \label{kP} k\cdot P = k_0\cdot P + k_1\cdot 2^{248}P +\dots+ k_j\cdot 2^{248j}P.\\This sum is done using the following circuit. The terms of the sum\end{aligned}\end{align} \]

    are calculated separately inside the seq boxes and then added together.

    image

  2. Each seq box takes a point of \(E\) of the from \(P_i = 2^{248 i} P\) for \(i=0,\dots,j-1\) and outputs two points

    \[ \begin{align}\begin{aligned} 2^{248} \cdot P_i \quad \text{and} \quad \sum_{n = 0}^{247} b_n \cdot 2^{n} \cdot P_i.\\The first point is the input of the next :math:`(i+1)`-th seq box\end{aligned}\end{align} \]

    (note that \(2^{248} \cdot P_i = P_{i+1}\)) whereas the second output is the computation of the \(i\)-th term in expression ([kP]). The precise circuit is depicted in next two figures seq and window.

    image

    image

    The idea of the circuit is to first compute

    \[ \begin{align}\begin{aligned} Q = P_i + b_1 \cdot (2P_i) + b_2 \cdot (4P_i) + b_3 \cdot (8P_i) + \dots + b_{247} \cdot (2^{247}P_i),\\and output the point\end{aligned}\end{align} \]
    \[ \begin{align}\begin{aligned}Q - b_0 \cdot P_i.\\This permits the computation of :math:`Q` using the Montgomery form\end{aligned}\end{align} \]

    of Baby-Jubjub and only use twisted Edwards for the second calculation. The reason to change forms is that, in the calculation of the output, we may get a sum with input the point at infinity if \(b_0 = 0\).

    Still, we have to ensure that none of the points being doubled or added when working in \(E_M\) is the point at infinity and that we never add the same two points.

    • By assumption, \(P\not= O\) and ord\((P)>8\). Hence, by Lagrange theorem (Baumslag and Chandler 1968 Corollary 4.12), \(P\) must have order \(r\), \(2r\), \(4r\) or \(8r\). For this reason, none of the points in \(E_M\) being doubled or added in the circuit is the point at infinity, because for any integer \(m\), \(2^m\) is never a multiple of \(r\), even when \(2^m\) is larger than \(r\), as \(r\) is a prime number. Hence, \(2^m \cdot P \not= O\) for any \(m\in\ensuremath{\mathbb{Z}}\).
    • Looking closely at the two inputs of the sum, it is easy to realize that they have different parity, one is an even multiple of \(P_i\) and the other an odd multiple of \(P_i\), so they must be different points. Hence, the sum in \(E_M\) is done correctly.

  3. The last term of expression ([kP]) is computed in a very similar manner. The difference is that the number of bits composing \(k_j\) may be shorter and that there is no need to compute \(P_{j+1}\), as there is no other seq box after this one. So, there is only output, the point \(k_j \cdot P_j = k_j\cdot 2^{248j} P\). This circuit is named seq’.

    image

MiMC-7

The specifications we use in the hash are (we are working in explaining this section in greater detail):

  1. Number of rounds: \(r = \ceil*{\frac{\log_2l}{\log_27}} = 91.\)
  2. Inputs:
    • Coordinates of the public key: (\(A_x, A_y\)).
    • Coordinates of the point \(8R\): (\(R8_x, R8_y\)).
    • Message \(M\).
  3. Number of inputs: 5.
  4. Generation of constants: https://github.com/iden3/circomlib/blob/master/src/mimc7.js.
Example and test vectors

Work in progress.

Existing implementations
EdDSA for Baby Jubjub implemented by Jordi Baylina in circom (zero knowledge circuit compiler):
https://github.com/iden3/circomlib/blob/master/circuits/eddsamimc.circom

Intellectual Property

We will release the final version of this proposal under creative commons, to ensure it is freely available to everyone.

Albrecht, Martin, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. 2016. “MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity.” Cryptology ePrint Archive, Report 2016/492.

Baumslag, Benjamin, and Bruce Chandler. 1968. Schaum’s Outline of Theory and Problems of Group Theory. Schaum’s Outline Series. New York: McGraw-Hill Book Company.

Bernstein, Daniel J., Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters. n.d. “Twisted Edwards Curves.” Cryptology ePrint Archive, Report 2008/013.

Josefsson, S., and I. Liusvaara. n.d. “Edwards-Curve Digital Signature Algorithm (Eddsa).” Request for Comments. RFC 8032; RFC Editor. https://doi.org/10.17487/RFC8032.

Okeya, Katsuyuki, Hiroyuki Kurumatani, and Kouichi Sakurai. 2000. “Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications.” In Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, 238–57. PKC ’00. London, UK, UK: Springer-Verlag. http://dl.acm.org/citation.cfm?id=648117.746614.

Pedersen Hash

Scope

The 4-bit window Pedersen hash function is a secure hash function which maps a sequence of bits to a compressed point on an elliptic curve (Libert, Mouhartem, and Stehlé, n.d.).

This proposal aims to standardize this hash function for use primarily within the arithmetic circuits of zero knowledge proofs, together with other generic uses such as for Merkle tree or any use cases requiring a secure hash function.

As part of the standard, the paper details the elliptic curve used for the hash function, the process to compute the Pedersen hash from a given sequence of bits, and the computation of the hash from a sequences of bits using an arithmetic circuit—which can be used within zero knowledge proofs.

Moreover the paper includes references to open-source implementations of the Pedersen hash function which follows the computation process details in this proposal.

Motivation

The primary advantage of this Pedersen hash function is its efficiency. The ability to compute the hash efficiently makes it an attractive proposal for use within the circuits associated with zk-SNARK proofs (“ZCash Open Discussion: Choose Improved Hash Function for Merkle Tree (or Replace Merkle Tree),” n.d.).

Having a standard, secure, and efficient hash function is one of the paramount aspect for implementing usable, comprehensible, and easily verifiable zero knowledge proofs.

Background

The Pedersen hash has already been defined and used by the ZCash team in Sapling, their latest network upgrade (Hopwood et al., n.d.). They construct it on the Jubjub elliptic curve and using 3-bit lookup tables. In this document, we propose a different implementation of the Pedersen hash function using Baby-Jubjub elliptic curve and 4-bit windows, which requires less constraints per bit than using 3-bit windows.

Terminology

Elliptic Curve: Baby-Jubjub

Consider the prime number

\[ \begin{align}\begin{aligned} p = 21888242871839275222246405745257275088548364 400416034343698204186575808495617\\and let :math:`\ensuremath{\mathbb{F}_p}` be the finite field with\end{aligned}\end{align} \]

\(p\) elements.

We define \(E_M\) as the Baby-Jubjub Montgomery elliptic curve defined over \(\ensuremath{\mathbb{F}_p}\) given by equation

\[ \begin{align}\begin{aligned}E: v^2 = u^3 + 168698u^2 + u.\\The order of :math:`E_M` is :math:`n = 8\times r`, where\end{aligned}\end{align} \]
\[ \begin{align}\begin{aligned} r = 2736030358979909402780800718157159386076813972 158567259200215660948447373041\\is a prime number. Denote by :math:`\ensuremath{\mathbb{G}}` the\end{aligned}\end{align} \]

subgroup of points of order \(r\), that is,

\[\ensuremath{\mathbb{G}}= \Set{ P \in E(\ensuremath{\mathbb{F}_p}) | r P = O }.\]
\(E_M\) is birationally equivalent to the Edwards elliptic curve
\[ \begin{align}\begin{aligned}E: x^2 + y^2 = 1 + d x^2 y^2\\where\end{aligned}\end{align} \]

\(d = 9706598848417545097372247223557719406784115219466060233080913168975159366771.\)

The birational equivalence (Bernstein et al., n.d. Thm. 3.2) from \(E\) to \(E_M\) is the map
\[ \begin{align}\begin{aligned}(x,y) \to (u,v) = \left( \frac{1 + y}{1 - y} , \frac{1 + y}{(1 - y)x} \right)\\with inverse from :math:`E_M` to :math:`E`\end{aligned}\end{align} \]
\[(u, v) \to (x, y) = \left( \frac{u}{v}, \frac{u - 1}{u + 1} \right).\]
Pedersen Hash

Let \(M\) be a sequence of bits. The Pedersen hash function of \(M\) is defined as follows:

  • Let \(P_0,P_1,\dots,P_k\) be uniformly sampled generators of \(\ensuremath{\mathbb{G}}\) (for some specified integer \(k\)).

  • Split \(M\) into sequences of at most 200 bits and each of those into chunks of 4 bits [1]. More precisely, write

    \[ \begin{align}\begin{aligned}\begin{split} \begin{gathered} M = M_0M_1\dots M_l \quad\text{where}\quad M_i = m_0m_1\dots m_{k_i} \quad\text{with}\quad \begin{cases} k_i = 49 \;\text{ for } i = 0, \dots, l-1, \\ k_i \leq 49 \;\text{ for } i = l, \end{cases} \end{gathered}\end{split}\\where the :math:`m_j` terms are chunks of 4 bits\end{aligned}\end{align} \]

    \([b_0\: b_1\: b_2\: b_3]\). Define

    \[ \begin{align}\begin{aligned} enc(m_j) = (2b_3-1) \cdot (1+b_{0}+2b_{1}+4b_{2})\\and let\end{aligned}\end{align} \]
    \[ \begin{align}\begin{aligned}\langle M_i \rangle = \sum_{j=0}^{k_i-1} enc(m_j) \cdot 2^{5j}.\\We define the Pedersen hash of :math:`M` as\end{aligned}\end{align} \]
    \[ \begin{align}\begin{aligned} \label{eq-ped} H(M) = \langle M_0 \rangle \cdot P_0 + \langle M_1 \rangle \cdot P_1 + \langle M_2 \rangle \cdot P_2 + \dots + \langle M_l \rangle \cdot P_l.\\Note that the expression above is a linear combination of elements\end{aligned}\end{align} \]

    of \(\ensuremath{\mathbb{G}}\), so itself is also an element of \(\ensuremath{\mathbb{G}}\). That is, the resulting Pedersen hash \(H(M)\) is a point of the elliptic curve \(E\) of order \(r\).

Description

Set Of Generators

We generate the points \(P_0,\dots,P_{{k}}\) in such a manner that it is difficult to find a connection between any of these two points. More precisely, we take D = "string\_seed" followed by a byte S holding that smallest number that H = Keccak256(D || S) results in a point in the elliptic curve \(E\).

Computation Of The Pedersen Hash

In the following circuit pedersen hash, we have depicted the circuit used to compute the Pedersen hash of a message \(M\) described in equation [eq-ped]. Each multiplication box returns a term of the sum.

image image

As the set of generators are fixed, we can precompute its multiples and use 4-bit lookup windows to select the right points. This is done as shown in the circuit called selector. This circuit receives 4-bit chunk input and returns a point. The first three bits are used to select the right multiple of the point and last bit decides the sign of the point. The sign determines if the \(x\)-coordinate should be taken positive or negative, as with Edwards curves, negating a point corresponds to the negation of its first coordinate.

image

[sec-computation]

Examples And Test Vectors

Work In Progress

Challenges

One of the main challenges to create this standard and to see it adopted by the community is to provide correct, usable, and well-maintained implementations in as many languages as possible.

Some effort is also required to audit and verify code coming from the community and claiming to implement the 4-bit window Pedersen hash function to prevent the propagation of potentially insecure implementations.

Finally, the proposal as it stands today includes the padding of the message \(M\) to a multiple of four bits. There are potentials issues with this approach where collisions can happen.

Security

Overflow Prevention
As we described in section [sec-computation], we use a windowed scalar multiplication algorithm with signed digits. Each 4-bit message chunk corresponds to a window called selector and each chunk is encoded as an integer from the set \(\{-8..8\}\backslash \{0\}\). This allows a more efficient lookup of the window entry for each chunk than if the set \(\{1..16\}\) had been used, because a point can be conditionally negated using only a single constraint (Hopwood et al., n.d.).
As there are up to 50 segments per each generator \(P_i\), the largest multiple of the generator \(P_i\) is \(n\cdot P_i\) with
\[ \begin{align}\begin{aligned}n = 2^0 \times8 + 2^5 \times 8 + \left(2^5\right)^2 \times8 \dots + 2^{245}\times 8 .\\To avoid overflow, this number should be smaller than\end{aligned}\end{align} \]

\((r-1)/2\). Indeed,

\[ \begin{align}\begin{aligned}\begin{split} \begin{aligned} \quad\; n & = 8 \times \sum_{ k = 0}^{49} 2^{5k} = 8 \times \frac{2^{250}-1}{2^5-1}\\ & = 466903585634339497675689455680193176827701551071131306610716064548036813064%\\\end{aligned}\end{split}\\and\end{aligned}\end{align} \]
\[\begin{split}\begin{aligned} \frac{r-1}{2} &= 1368015179489954701390400359078579693038406986079283629600107830474223686520 \\ & > n.\\ \vspace{0.4cm}\end{aligned}\end{split}\]

Implementation

A Note On Efficency: Number Of Constraints Per Bit
When using 3-bit and 4-bit windows, we have 1 constraint for the sign and 3 for the sum (as we are using the Montgomery form of the curve, that requires only 3). Now let’s look at the constraints required for the multiplexers.
With 3-bit windows we need only one constraint per multiplexer, so 2 constraints in total.
Standard 4-bit windows require two constraints: one for the output and another to compute \(s_0*s_1\). So, a priori we would need 4 constraints, two per multiplexer. But we can reduce it to 3 as the computation of \(s_0*s_1\) is the same in both multiplexers, so this constraint can be reused. This way only 3 constraints are required.
So, the amount of constraints per bit are:
  • 3-lookup window : \((1+3+2)/3 = 2\) constraints per bit.
  • 4-lookup window : \((1 +3+3)/4 = 1.75\) constraints per bit.

The specific constraints can be determined as follows: let the multiplexers of coordinates \(x\) and \(y\) be represented by the following look up tables:

\(s_2\) \(s_1\) \(s_0\) \(out\)
0 0 0 \(a_0\)
0 0 1 \(a_1\)
0 1 0 \(a_2\)
0 1 1 \(a_3\)
1 0 0 \(a_4\)
1 0 1 \(a_5\)
1 1 0 \(a_6\)
1 1 1 \(a_7\)
\(s_2\) \(s_1\) \(s_0\) \(out\)
0 0 0 \(b_0\)
0 0 1 \(b_1\)
0 1 0 \(b_2\)
0 1 1 \(b_3\)
1 0 0 \(b_4\)
1 0 1 \(b_5\)
1 1 0 \(b_6\)
1 1 1 \(b_7\)

We can express them with the following 3 constraints:

  • \(aux = s_0 s_1\)

  • \(out = [ (a_7-a_6-a_5+a_4-a_3+a_2+a_1-a_0)*aux + (a_6-a_4-a_2+a_0)*s_1\)
    \(\text{\qquad\;\;} + (a_5-a_4-a_1+a_0)*s_0 + (a_4 - a_0) ] z + (a_3-a_2-a_1+a_0)*aux + (a_2-a_0)*s_1\)
    \(\text{\qquad\;\;} + (a_1-a_0)*s_0+ a_0\)
  • \(out = [ (b_7-b_6-b_5+b_4-b_3+b_2+b_1-b_0)*aux + (b_6-b_4-b_2+b_0)*s_1\)
    \(\text{\qquad\;\;} + (b_5-b_4-b_1+b_0)*s_0 + (b_4 - b_0)] z + (b_3-b_2-b_1+b_0)*aux + (b_2-b_0)*s_1 \\ \text{\qquad\;\:} + (b_1-b_0)*s_0+ b_0\)
Existing Implementations

Implementation of the specifications and arithmetic of the Baby-Jubjub curve:

Implementation of the Pedersen Hash function:

Intellectual Property

The source code of the implementations listed in this proposal are publicly available. Circom is licensed under GPL3.

Bernstein, Daniel J., Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters. n.d. “Twisted Edwards Curves.” Cryptology ePrint Archive, Report 2008/013.

Hopwood, Daira, Sean Bowe, Taylor Hornby, and Nathan Wilcox. n.d. “ZCash Protocol Specification Version 2018.0-Beta-31.”

Libert, B., F. Mouhartem, and D. Stehlé. n.d. “Tutorial 8.”

“ZCash Open Discussion: Choose Improved Hash Function for Merkle Tree (or Replace Merkle Tree).” n.d.

[1]If \(M\) is not a multiple of 4, pad \(M\) to a multiple of 4 bits by appending zero bits.

Presentations