# UniRep Specification

Authors: Barry, Vitalik, WJ, CC

*one private reputation system to rule them all,*
*one to send reputation,*
*one to force the acceptance,*
*one to make proofs,*
*one to bring them all,*
*and the in darkness bind them.*

https://miro.com/welcomeonboard/lmfmiqyo8sLA9swYrWhrTh0fRqRvyTtY1ZQLVRdPdUEjLoi4SQGcSlBy4XHMCrHb

Todo: 1 to 2 more rounds of polishing
Onboard Nic

[TOC]

## Introduction

UniRep is a private and nonrepudiable repuation system. Users can receive positive and negative reputation from attesters, and voluntarily prove that they have at least certain amount of reputation without revealing the exact amount. Moreover, users cannot refuse to receive reputation from an attester.

The high-level goal for UniRep is to be a base layer on top of which anyone can easily build custom, yet interoperable, reputation systems, For instance, users could create combined proofs of reputation across different social media platforms, consumer apps, or financial applications, in order to provide holistic, private, and trustworthy information about themselves to others.

TODO: update this spec to describe how to do interop between different applications

### Example flow

Alice is a user registered with UniRep. She currently has 0 positive reputation points and 2 negative reputation points.

Alice creates an epoch key and shares it with Bob. With this epoch key, Bob submits to the UniRep contract an Ethereum transaction which contains an attestation which gives Alice 10 positive reputation points. At the end of the week, Alice generates a zero-knowledge proof to the UniRep contract which updates her cumulative reputation information from before the current epoch with the reputation that she received from the 10 attesters during the week.

Now, Alice has 10 positive and 2 negative reputation points.

Charlie asks Alice to prove that she has at least 5 positive and less than 5 negative reputation points, Alice generates another zero-knowledge proof and sends it to Charlie. Charlie verifies the proof, and now knows that Alice has at least 5 positive and less than 5 negative reputation points, but does not know exactly how many points she has.

## Actors

There are two actors in UniRep: users and attesters.

### Users

A user is any entity which receives reputation. For instance, a user could be a taxi driver who receives ratings from passengers.

We represent a user by a [Semaphore](https://github.com/appliedzkp/semaphore/) identity, which is in possession of a private key, an identity nullifier, and an identity trapdoor. Using the Semaphore identity construction allows the user to prove their membership in the set of registered users.

### Attesters

An attester is any entity which controls an externally owned account or smart contract which gives reputation to a user. For example, they could be a taxi passenger who wants to rate their driver.

Another example is: a user rents a bike, and the bike company gives the user customer reputation (e.g. positive reputation if they did not damage the bike). We could have more total users than total attesters or the other way around.

## Cryptographic primitives

### Hash function

We recommend to use the Poseidon hash function. Please refer to [this document](https://github.com/appliedzkp/maci/tree/master/circuits) for more information on its parameters and limitations.

### Incremental Merkle Tree

We recommend to adapt the audited incremental Merkle tree contract and circuits from [Semaphore](https://github.com/appliedzkp/semaphore/).

It may also be a good idea to use incremental quinary Merkle trees (5 leaves per node) if the gas tradeoffs are worth it. Please refer to [this post](https://ethresear.ch/t/gas-and-circuit-constraint-benchmarks-of-binary-and-quinary-incremental-merkle-trees-using-the-poseidon-hash-function/7446) for more information on how to reason about these tradeoffs.

### Sparse Merkle Tree

TODO

## Data structures

### Identity

Each user has an `Identity` which is the same as a [Semaphore](https://github.com/appliedzkp/semaphore) identity.

| Field | Type | Notes |
|-|-|-|
| `keypair` | `EddsaKeyPair` | An EdDSA keypair|
| `identityNullifier` | BabyJub value | Randomly generated |
| `identityTrapdoor` | BabyJub value | Randomly generated |

> [name=Wei Jie] The EdDSA private key, `identityNullifier`, and `identityTrapdoor` are secret values. Only the user knows what they are.

We define a BabyJub value as a positive integer less than the snark field size as defined in [EIP-197](https://github.com/ethereum/EIPs/blob/master/EIPS/eip-197.md):

`21888242871839275222246405745257275088548364400416034343698204186575808495617`

### Attestations

An attestation contains the following data:

| Field | Type | Notes |
|-|-|-|
| `attesterId` | Numeric | The attester's ID |
| `pos` | Numeric | Positive reputation |
| `neg` | Numeric | Negative reputation |
| `graffiti` | BabyJub value | A hash of an arbitary string |
| `overwriteGraffiti` | Boolean | Whether or not to overwrite the graffiti in the user's state |

### Epoch keys

Each attester can give a single user a single attestation per epoch (key). In order to receive attestations, a user generates an epoch key which they share with an attester. An epoch key is generated as such: `hash(identityNullifier, epoch, nonce)` where the `epoch` and `nonce` are integers.

> [name=Wei Jie] Since `identityNullifier` is secret, only the user is able to generate an epoch key.

> [name=Wei Jie] During each epoch, a user can give multiple attesters one epoch key each. For instance, Alice may give Bob an epoch key `epoch_1_b` and Charlie the epoch key `epoch_1_c`. We use the nonce to differentiate these keys.
> For instance, we can compute `epoch_1_b = hash(aliceIdNullifier, 1, 1)` and `epoch_1_b = hash(aliceIdNullifier, 1, 2)`.
> Additionally, there is a predefined maximum number of epoch keys per epoch; in other words, there is a maximum nonce value.

The epoch key must be a BabyJub value as it will be one of the inputs to the epoch transition ZK circuit.

The maximum nonce can be set as a config option, and the epoch is an incrementing value (e.g. if one epoch lasts a week, the first week is epoch 0, the second week is epoch 1, and so on).

Note: epoch key is generated deterministically as `nonce` is in the range `[0, max_nonce]` and this is intended because we need to ensure that user includes attestations to all of his epoch keys during epoch transition.

Each epoch key does not have to be public, but the user may choose to reveal it.

> Qn: can a different attester give reputation to a key they are not assigned?
> Barry: Yes

> How to prevent frontrunning?
> Barry: Each attester is allowed to submit a single attestation there is no way to frount run.

> How to prevent sybil attacks (create 10 attesters and send 10 attestations?) via an attester signup fee?

Barry: Yes. signup fee

TODO: since smart contract epoch keys are public, there should be a way to limit the `msg.sender` for an attestation to an epoch key to either a whitelist of addresses, or any address.

## Ethereum contract

### State

UniRep has an Ethereum contract which maintains the following state:

| Name | Type | Notes |
|-|-|-|
| `userIds` | `mapping (uint256 => uint256)` | A mapping between user IDs and their current global state tree index |
| `attesters` | `mapping (address => uint256)` | A mapping between each attesters' Ethereum address and their attester ID . Attester IDs are incremental and start from 1. No attesters with and ID of `0` should exist. |
| `globalStateTree` | An `IncrementalMerkleTree` | The global state tree (see below) |
| `epochKeys` | `mapping(bytes32 => bytes32)` | Associates each epoch keys with an attestation hashchain |
| `attestationsMade` | `mapping(bytes32 => mapping(address => bool))` | Keeps track of whether an address has already attested to a particular epoch key. |

#### Global state tree

The global state tree is an Incremental Merkle Tree which associates users' identities with their reputation information. Whenever a user signs up, a the contract appends a new leaf to the tree. Each of its leaves has the following format:

| Name | Type | Notes |
|-|-|-|
| `pubKey` | EdDSAPubKey | The public key of the user's `keypair` |
| `identityNullifier` | BabyJub value | Part of a Semaphore identity |
| `identityTrapdoor` | BabyJub value | Part of a Semaphore identity |
| `userStateRoot` | BabyJub value | The Merkle root of this user's state tree (see below) |

Each user's reputation information is accumulated into a Merkle tree whose root is the `userStateRoot`. We also call this information the user's state.

At the end of each epoch, the contract transitions to a new global state tree.

#### User state tree

A user state tree holds the attestations from all attesters to a particular user. It is a Merkle tree where each leaf is assigned to an attester. Note that it only contains cumulative reputation data from all previous epochs, but not the current epoch, until after an epoch transition is performed (see below).

| Name | Type | Notes |
|-|-|-|
| `attesterId` | Numeric | The attester's ID |
| `pos` | Numeric | Positive reputation |
| `neg` | Numeric | Negative reputation |
| `graffiti` | BabyJub value | A hash of an arbitary string |

### Functions

| Name | Parameters | Notes |
|-|-|-|
| `userSignUp` | `identityCommitment: bytes32` | |
| `attesterSignUp` | None | |
| `attesterSignUpViaRelayer` | `attesterAddr: address, signature: bytes32[]` | Allows an attester to sign up via a relayer |
| `submitAttestation`| `attestation: Attestation`, `epochKey: bytes32` | |

### Signing up as a user

This function inserts a new leaf into the global state tree. It also assigns the user with an ID which will not change across epoch transitions.

def userSignUp(identityCommitment: bytes32):
    uint256 index = globalStateTree.insert(
        hash(
            identityCommitment,
            emptyUserStateRoot
        )
    )
    
    userIds[identityCommitment] = index
    emit(index)

### Signing up as an attester

Any externally owned account or smart contract may sign up as an attester as long as they call this function.

def attesterSignUp():
    require(msg.sender not in attesters)
    attesters[msg.sender] = next_attester_id
    next_attester_id += 1

### Submitting an attestation

Any attester can send an attestation to this epoch key as long as they pay a fee of `x` gwei, to prevent spam attacks. The contract will burn this fee.

The contract function prevents an attester from sending subsequent attestations.

Each attestation is taken and hashed with the previous ones on-chain.

A fee is charged to prevent somebody registering many attesters and collude with a user who created many epoch keys to those attesters.

Contract function pseudocode:

def submitAttestation(attestation: Attestation, epochKey: bytes32):

    # Ensure that the attester has been registered
    assert(msg.sender in attesters)
    
    # Ensure that the attester has not already submitted an 
    # attestation to this key
    assert(msg.sender not in attestationsMade[epochKey])
    
    # Ensure that the attester pays a small fee
    assert(msg.value == some_gwei)
    
    # Burn the fee
    burn(msg.value)

    # Get the hashchain, or inititalize it if it's nonexistent
    hashchain: bytes32 = epochKeys.get(epochKey, b'')
    
    # Update the hashchain
    # Problem: since each epoch key is unique to an attester,
    # this code won't work!
    epochKeys[epochKey] = hash(attestation, hashchain)
    
    # suggestion:
    # store the hashchains in a new mapping:
    # hashChains mapping(userId => mapping (epoch => hashchain))
    # hashchain:bytes32
    # if (hashChains[userId][epoch]):
    #     hashchain = hashChains[userId][epoch]
    # else:
    #     hashchain = b''
    # hashChains[userId][epoch] = hash(attestation, hashchain)
    
    # Mark the attester has submitted the attestation
    attestationsMade[epochKey][msg.sender] = True

> Problem: if each attester gets a different epoch key, we can't create the hashchain

> [name=wei jie] Question: how to prevent frontrunning?

The value in `epochKeys[epochKey]` is now a hashchain of all attestations. For example, if we have 3 attestations, the hashchain should look like this:

hash(att3, hash(att2, hash(att1, b'')))

### Epoch transitions

At the end of each epoch, the user calls the `updateUserStateRoot()` smart contract function which:

1. Seals the hashchain of attestations to each epoch key
2. Generates a sparse Merkle tree.
3. Verifies a zero-knowledge proof that the epoch transition is valid. If it is invalid, revert the transaction. If it is valid, update the global state tree root

TODO: maybe each user should be responsible to seal their own attestation hashchain.

To seal a hashchain of attestations is to do the following:

hash(1, hashchain)

For instance:

hash(1, hash(att3, hash(att2, hash(att1, b''))))

This makes it possible for the epoch transition circuit to verify that it has processed the entire attestation hashchain.

TODO: explain why we need to use a sparse Merkle tree.

Next, they have to generate an epoch transition proof and submit it to the contract.

def updateUserStateRoot(proof, newRoot: bytes32):
    # TODO
    # This pseudocode is incomplete
    
    epochTree: SparseMerkleTree = finalizeAttestations()

    publicInputs: List[bytes32] = [
        newRoot, # a circuit output, which is a public input
        epochTree,
        nullifiers # not sure
    ]
    
    # TODO: revert if any nullifier has been seen before
    
    require(verifyProof(publicInputs, proof))
    # TODO
    globalStateRoot = newRoot
    
def finalizeAttestations():
    # TODO: maybe this should be for just one hashchain instead of all?
    for key in epoch_keys.key():
        #seal
        attestationHashchain = epoch_keys[key]
        epochKeys[key] = hash(1, attestationHashchain)
    
    epochTree = generateSparseMerkleTree(epochKeys)
    return epochTree

TODO: transition to a new global state tree!

Qn: Who inserts each user's identity into the fresh global state tree?
Barry: We can do this one by one like the mixer or all at once with some reqward for it.

>[name=wei jie] here is how i suggest doing an epoch transition such that the global state tree is renewed each time

# Anyone can call this once per epoch
def beginEpochTransition():
    # Ensure that this is only called once per epoch
    assert(completedEpochTransitions[currentEpoch] == false)
    
    # Initialise a new global state tree
    globalStateTrees[currentEpoch] = new IncrementalMerkleTree(...)
    
    # Finalize all attestations and store the epoch tree
    epochTrees[currentEpoch] = finalizeAllAttestations()
    
    # Mark the epoch transition as complete
    completedEpochTransitions[currentEpoch] = true
    
    # Pay the caller some ETH? (TBD)
    pay(msg.sender, reward)
    
def updateUserStateRoot(proof, newUserStateRoot: bytes32):
    # Check that the current epoch transition is underway
    assert(completedEpochTransitions[currentEpoch] == true)
    
    # Reject spent nullifiers (TBD)
    uint256 index = 0
    for (attestation, epochKey in epochTree):
        nullifer = hash(
            identity_nullifier, # not sure how to get this
            attestation.attester_id,
            epochKey,
            i
        )
        assert(attestationNullifiers[nullifier] == false)
        i ++
        
    publicInputs: List[bytes32] = [
        newUserStateRoot, # a circuit output, which is a public input
        epochTree,
        nullifiers # not sure
    ]
    
    require(verifyProof(publicInputs, proof))
    
    globalStateTrees[currentEpoch].insert(
        identityCommitment,
        newUserStateRoot
    )

## Zero Knowledge Circuits

### Epoch transitions

Now, each user needs to move their attestations from the Epoch Tree to their User State so that they can make proofs about them.

To do so, they need to execute a contract function to change their user state root. The function should only do so if they provide a proof that this user state root transition is valid.

Recall that an epoch tree is a sparse MT which contains all attestations (as the tail of a hash chain) to a particular user, ordered by epoch keys. The goal is to iterate through each epoch leaf and update the corresponding leaf in the user's state tree. Each update can only occur once, so we also use nullifiers and rely on the contract to keep track of them.

This circuit must prove the following:

1. That the epoch leaf is part of the epoch tree
2. That the user is part of the global state tree
3. Knowledge of exactly all the correct attestations

The circuit must output:

1. A nullifier per attestation, so that the contract can prevent a double attestation.
2. The updated user state root.

> Qn: do we need one nullifier per attestation or can we have one nullifier per hashchain?

Barry: I am worried the hash chain will grow too big to be processed in a single snark. In that case we need a nullifier for each chunk of the hash chain that can fit into a single snark.

**Pseudocode (WJ)**

# First, we verify that the epoch leaf is part of the epoch tree.

input epoch_leaf_path
input epoch_tree_root
input epoch_tree_leaf

assert(
    merkleInclusionProof(
        epoch_tree_root,
        epoch_leaf_path,
        epoch_tree_leaf
    ) == true
)

# Next, verify that the user is part of the global state tree.

input user_pubkey
input identity_nullifier
input identity_trapdoor
input user_state_root

identity_commitment = hash(
    user_pubkey,
    identity_nullifier,
    identity_trapdoor
)

global_tree_leaf = hash(identity_commitment, user_state_root)

assert(
    merkleInclusionProof(
        global_tree_root,
        global_leaf_path,
        global_tree_leaf
    ) == true
)

# Next, verify that the epoch tree leaf matches the hash chain of
# attestations.

private input attestations[n]

# Build the hashchain
hashChain = 0
for each attestation of attestations:
    hashChain = hash(hashChain, attestation)

hashChain = hash(1, hashChain) # seal the hashchain

# Check the hashchain
assert(hashChain == epoch_tree_leaf)

# Next, calculate the nullifiers. Each attestation has one
# nullifier. The contract is responsible for checking whether
# each nullifier has been spent.

input epoch_key

# TODO: might be just 1 nullifier?
output nullifiers[]

for (var index = 0; index < attestations.length; index ++):
    
    nullifer = hash(
        identity_nullifier,
        attestations[i].attester_id,
        epoch_key,
        index
    )
    nullifiers[index] <== nullifier


# Next, update the user's state tree

input user_state_paths[n]
input user_state_indices[n]
input user_state_leaves[n]

var temp_root

# For each attestation, update a user state leaf
for (var index = 0; index < attestations.length; index ++):
    # Verify that the leaf exists
    assert(
        verifyMerklePath(
            user_state_paths[index],
            user_state_indices[index],
            user_state_leaves[index],
        ) == true
    )
    
    assert(
        attestations[index].id == user_state_leaves[index].attestation_id
    )
    
    # TODO: add an additional check that the attestations
    # come from unique attesters. The uniqueness of attesters
    # is already enforced by the smart contract but it may be
    # prudent to do this check in the circuit as well.
    
    # Update the repuation score and graffiti
    var leaf = user_state_leaves[index]
    leaf.pos += attestations[index].pos
    leaf.neg += attestations[index].neg
    
    if attestations[index].overwrite_graffiti or 
       attestations[index].graffiti == 0:
        leaf.graffiti = attestations[index].graffiti
    
    temp_root = updateMerkleTree(
        user_state_paths[index],
        user_state_indices[index],
        leaf
    )
    
# output the new user state root
output new_user_state_root <== temp_root

var r = hash(
    user_pubkey, 
    identity_nullifier, 
    identity_trapdoor
    new_user_state_root
)

output new_global_state_leaf <== r

**Pseudocode (Barry)**

def prove(epoch_tree):
    # private inputs
    private leaf 
    # merkle proof
    assert(leaf in epoch_tree)
    assert(old_leaf in leaf.attester_tree)
    # check the first attestation is really the first one
    assert(leaf.attestation == 0)

    new_leaf = old_leaf
    
    # process the rest. 
    for attestation in leaf.attestations:
        nullifier, new_leaf = process(attestation, new_leaf)
        nullifiers.append(nullifier)
    # make sure we did them all
    assert attestation == 1

def process(attestation, new_leaf):
    nullifier = gen_nullifier()
    # nullifer = hash (
    #     user_secret, attester_id, epoch_key, attestation_index
    # )
    # attestation_index is the position of the attestation in 
    # the list of all attestations

    
    new_leaf.update(attestation)
    return nullifier, new_leaf
    
def update(attestation):
    leaf = new_leaf.load(attestation.attester)
    leaf.pos_rep += attestation.pos_rep
    leaf.neg_rep += attestation.neg_rep
    if attestation.overwrite_graffiti or attestation.graffiti == 0:
        leaf.graffiti = attestation.graffiti
    

> ✳️ Question: `assert(old_leaf in leaf.attester_tree)` What is the `old_leaf`? and what is the `attester_tree`
> [name=barryWhiteHat] The old leaf is the previous state of that users attestations from all attesters. Each leaf has an attester_tree which is a mt containting that users attestations from all attesters

In the smart contract we check that
1. The correct epoch tree is being used
2. All the nullifiers have been used only once `nullifer = hash(user_secret, attester_id, epoch)`
3. If its a chain or proof that the link between the intermediate leaf has been maintained.

We then save the new_leaf and use this to create the new epoch tree.

#### Chaining proofs

If a proof is not enough to process all attestations, we can chain them together, connecting each and making sure that the intermediate leaf from one is used as input to the next.

In a future version, it would be ideal to use a ZKP scheme which supports recursion, so that we can optimise this process.

### Proving reputation

When a user wishes to prove that they have a certain amount of reputation, they can generate a proof using the following circuit:

Circuit pseudocode:

input userStateLeaf
input userStateTreePath
input userStateTreeIndices
input userStateRoot

# First, verify that the state leaf exists in the tree

assert(
    genMerkleRoot(
        userStateLeaf,
        userStateTreePath,
        userStateTreeIndices
    ) == userStateRoot
)

# Next, verify that the leaf is valid
input numAttesters
input attestations[numAttesters]

r = genMerkleTree(attestations)
assert(r == userStateRoot)

# Sum the pos and neg values
totalPos = 0
totalNeg = 0
for (var attestation of attestations):
    totalPos += attestation.pos
    totalNeg += attestation.neg

# Do the range check

input minPosRep
input minNegRep

assert(minPosRep <= totalPos)
assert(minNegRep <= totalNeg)

Note that it should be impossible for a user to create a proof of reputation which they do not have, nor for them to omit any negative attestations they received.

Anyone can verify this proof using the UniRep contract.

def verifyMinReputation(
    globalStateIndex: uint256,
    minPos: uint256,
    minNeg: uint256,
    proof: bytes32[8]
):

    bool isValid = verifyProof(
        [
            minPos,
            minNeg,
            globalStateIndex
        ],
        proof
    )
    
    return isValid

### Fast forward

Currently we have a source and target for each epoch transition. Where the target is the current state and the source is the state that the user currently has received their last unprocessed attestation.

This leaks privacy because you can see where each new leaf is coming from. Instead we can arrange all epoch trees into a Merkle tree and inside the transition snark we prove that a user is in one of these epoch trees and transitions to the next one.

There are a few attacks that we need to be aware of
1. A user reuses an old epoch tree to transition to the current state skipping picking up attestations along the way.

(1) is prevented by nullifier that only lets the user leave each epoch tree once. So if i am in an epoch tree where my nullifier has not been "spent" then its impossible for me to be in any epoch tree along the way so i must be allowed to transition from this tree directly to the most recent tree.

So now the source for every transition is all previous epoch trees and the destination is the current epoch tree.

Note: A user upon producing an epoch key must prove that they are in the latest state.

## Security Assumptions
TODO
e.g. if nullifier ___ has been spent then __ cannot happen

## Conclusion

## Appendices