Protocol Design

Claim

Definition

Some pieces of information about a holder, more particularly some properties of an identity (ex. name, age, gender, …) are encoded to the form of a claim. Technically, a claim can be seen as a storage for credential data with fixed capability, that also means if the amount of credential information exceeds its capability, we must divide and allocate these pieces of data into plural claims. In this protocol, having the KYC process done, the issuer composes KYC data received into one or more claims, sends them to the holder, and with the holder keeps these claims in secret.

Properties

Claims are characterized by the following properties:

• Holders can input data stored in their claim to generate proofs when being asked by the verifiers.

• Holders use cryptographic keys to affirm their ownership on their claims, therefore, no one else can generate proof on those claims, even when they are somehow leaked.

• When a claim is no longer valid, the issuer can revoke it. A proof from a revoked claim should be rejected by the verifiers.

• Claims are non updateable, that means if an issuer wants to change the information in a current claim, it must revoke the claim and issue a new one with the information updated.

• From the verifier point of view, a claim is valid if it satisfies 2 criterias:

• Issued by a certain issuer that they trust.

• Not revoked.

Structure

Technically, claims are treated as leaves of an SMT (will be discussed in the next section), thus they are constructed as a composition of two parts: index part (which determines the index of the claim in the tree) and value part (which determines the value part of the leaf). And due to the fact that later, we must pass claims into ZK circuits where every data unit is a number of a 254-bit field, each part of the claim contains 4 253-bit slots for storing data, resulting in the storing capability of 2024 bits (253 * 8) for each claim.

$Claim = {i_0, i_1, i_2, i_3, v_0, v_1, v_2, v_3}$

The content for each slot is specified as follow:

Claim schema is defined by the issuer for a certain type of claim. For example, with a claim encoding information of the ID card, $i_2$ stores the name, $i_3$ stores the age, $v_1$stores the nationality, etc. These definitions are documented in JSON form, then being hashed to a 128-bit value stored in slot $i_0$ of the claim. During the verification process, the verifier queries this value to guarantee the claim schema matches the one they expect.

For each claim schema, an issuer only grants one claim per holder, therefore, the above claim structure guarantees the exclusivity: each claim of an issuer possesses an unique index part. Since later on, they must be inserted to an issuer's SMT, this exclusivity absolutely helps avoid conflicts between every leaf.

When the expiration date is set to 0 (disabled), the claim is timeless. Otherwise, during the verification process, the verifier can give a certain timestamp and require the expired timestamp in the claim must not be passed it.

Identity

Definition

An identity in this protocol represents an individual or organization in real life, characterized by

• A set of claims it has issued for the others

• A set of claims it has received from the others

• A set of cryptographic keys that proves the ownership of the real entity on it.

Using SMTs, all the claims an identity has issued and its keys are accumulated into a public root. Facilitated by ZKP technique, an identity can prove its ownership, the properties of its claims without exposing its credential data.

An identity is an accumulation of 3 SMTs: Authentication Tree, Issued Claims Tree, Revoked Claims Tree.

The next 3 corresponding subsections will discuss them in detail.

Authentication Tree

The protocol uses Baby Jubjub cryptographic keys and EDDSA to authenticate every interaction. An identity must provide its signature each time it proves some credential data or modifies its trees.

Authentication tree, in definition, is a quinary sparse merkle tree with each leaf storing a Baby Jubjub key. The corresponding private key must be kept in secret by the identity. A signature is considered valid only when its public key is stored in the latest version of the authentication tree.

Here is the detailed structure of an authentication tree's leaf:

• Index: arbitrary value

• Value: $Poseidon(x|y)$with $x, y$ is the horizontal and vertical coordination of the public key

Due to the fact that we only require the existence of the public key in the tree while verifying, as long as there are not 2 different leaves with the same index, the identity can set any value for the index of every leaf in the tree.

Given a message or a challenge from the verifier, an identity must execute the following steps to prove their ownership when interacting with the protocol:

• Chose a key pair existing in their authentication tree

• Sign on the message and output the signature

• Provide merkle proof convincing the public key exists in the authentication tree

The whole tree, including the root itself, should not be revealed to achieve 2 layers of privacy for the identities. Even when a key pair is leaked for some reason, the other people without information about the tree still can't prove the existence of that key in the authentication tree, therefore, are not able to steal either the tree or the identity.

Issued Claim Tree

As its name suggests, this tree basically is used to store claims issued by the owner for the other identities, where each claim is located in one leaf.

Recall the structure of the claim in the section \ref{claim structure}, a leaf of an issued claims tree is constructed as follows:

With: $H_i = Poseidon(i_0|i_1|i_2|i_3)$, $H_v = Poseidon(v_0|v_1|v_2|v_3)$

• Index: $H_i$
• Value: $Poseidon(H_i|H_v|1)$

Upon constructing the claim for the holder, issuer inserts the corresponding leaf to their issued claims tree, then extracting the merkle proof of that leaf, sending it back to the holder, which later on is used by the holder to prove that this claim has already been issued by the issuer.

Revoked Claim Tree

As described before, each claim is constructed with an unique 64-bit revocation nonce. When the issuer wants to revoke the claim which is no longer valid, they have to insert a leaf carrying its revocation nonce into their revoked claims tree. Here is the structure of the tree's leaf:

• Index: revocation nonce

• Value: 0

The whole revoked claims tree, which indicates the revocation status of each claim by the owner, should be published to everyone to query. To prove the validity of a claim, along with the proof of its existence in the issued claims tree, the holder must convince that their claim's revocation nonce hasn't been added to the revoked claims tree of the issuer.

Identity State

Technically, the identity state is the 32-byte final hash of 3 roots: authentication tree root, issued claims tree root, revoked claims tree root. Being published on the blockchain, states of an identity represent its different versions. Each time the identity updates its keys, issues or revokes claims, as the result it generates a new state and broadcasts to the public.

Genesis ID: the very first state of an identity, right after constructing an identity from a couple of key pairs, the state generated is used as a name of the identity for its whole lifetime and called the genesis ID.

Recalling the identity structure of Iden3 protocol, which uses the Issued Claim Tree for storing both keys and claims, regarding the fact that the number of keys used by an identity usually falls under 100, while the tree still has to be capable of storing the billions of claims, its depth must be at least 32 for binary version and 14 for quinary version. By separating the storage for claims and keys into 2 distinct trees, and reducing the depth for the Auth tree to 4, we can cut off more than 8000 constraints on the IdOwnership circuit compared to the solution of iden3.

Interactions

Here are all the possible interactions and associated actors in the system:

All the interactions can be divided into 2 groups of actions:

• State Transition which contains business processes that change the state of the identity, including Construct new identity, adding, removing keys, issuing, removing claims. Except identity construction, every change which results in a new identity state, before being published on the blockchain, must be authorized by the signature of the owner.

• Two remaining use cases containing Prove claim and create attestations relate to the verification process of the issued claim, conducted by the holder and the verifier.

Construct a new identity

An unconnected user, if wants to participate in the system, must construct an identity from one or a set of key pairs specified by the user. The Issued Claims Tree and Revoked Claims Tree remain empty, while the Authentication Tree is constructed by the generated public keys. They are calculated returning a new identity with its genesis ID which also is its first state, and does not have to be published on the blockchain.

Adding, Removing keys

Adding or removing keys is quite similar to constructing a new identity, except the newborn identity state must be published on blockchain.

Issue a new Claim

This interaction is the equivalent of constructing a new claim and add it to the Issuer’s Issued Claim Tree, at the same time a new nonce for revocation is calculated and assigned to the claim by the Issuer to use when revoking.

Revoke a Claim

Attestation

An attestation, given by the verifier, acts as a question for the holder about their credential data. In case the verifier is the service provider, they can use attestations as an authentication layer to guarantee the users must possess one or some claims which satisfy some criterias to use their service. An attestation includes some information about the issuer of the claims, type of the claims, a challenge or message which must be signed by the holder, and a set of requirements for the credential data stored in those claims.

Here are different possible requirements (or operations) for the credential value, with the aid of ZKP technology, the value can be proved satisfying these operations without being exposed:

• $EQUAL$: the credential value must equal a given value (ex. the age must be 18)
• $LESS\;THAN$: the credential value must be less than a given value (ex. the birth year must be sooner than 2001)
• $GREATER\;THAN$: the credential value must be greater than a given value
• $IN\;RANGE$: the credential value must be in the range between a given lower bound and upper bound
• $IN$: the credential value must belong to a set of given values (ex. the nationality must be one of USA, Canada, Mexico)
• $NOT\;IN$: the credential value must be excluded in a set of given values (ex. the nationality must not be anyone of USA, Canada, Mexico)

Prove Claims

Given an attestation from a verifier, knowing their claims satisfy every requirement, a holder can construct a ZK proof including the assertions of the issuer, the signature on the challenge, the specified operations being passed, which are all specified in the attestation.