# Unirep review 2

Previous review: https://hackmd.io/-Qk1NJ2HRN-24LaTp63z2Q
Spec: https://hackmd.io/nYlm7qHhTA-h8JJz3-uCLw
Brief walkthough of Unirep circuits: https://hackmd.io/AwY04HMvRLipbmB-xoU5jQ
Some notes regarding the implementation of Unirep so far: https://hackmd.io/d5KTcXQiSdu_0F2_v25RQw
Milestones: https://hackmd.io/FFpqfj-0RxGPG80GRtTRug

## CLI

### `attesterSignup`
The readme has this instruction:

npx ts-node cli/index.ts attesterSignup -x ... -d ... attest

It worked only after I removed `attest` from the command:

npx ts-node cli/index.ts attesterSignup -x ... -d ... 

> [name=nic] sorry about the typo!

### Serialise proofs, JSON data, etc

Consider using a URL-safe scheme like base64url or hexadecimal to serialise data like proofs and `Identity` data. e.g. instead of:

"[\"e5bf3029a73844f19a5308ad3601b73b967253d8f5c9ae0c19a53e0b2a94de0d\",\"9d50ee25c3e782a859a80cdf58f931fae44f51ae43653614410c59276f4ce8\",\"aebd6ef4b7303273ff1ea31f7f6ffc139f7d89561dcd43a8c927bcc42b70bd\"]"

consider using a format like this:

unirep.identity.qL8R4QIcQ_ZsRqOAbeRfcZhilN_MksRtDaErMA

An example of encoding an epoch key proof using base64url:

unirep.epf.safdsfSsfdsf32r0sjfsdf_ZsRqOsfafcZhilN_MksRtDaErMA_blah_blah_blah

> [name=nic] Feedback applied at commit: https://github.com/NIC619/UniRep/commit/29bf9c7c6b47a5fd2f7346890475936d67ebdf2a

### `verifyEpochKeyProof`

I followed the steps in the readme but I had some trouble verifying my epoch key proof:


Maybe this error came about because I didn't recompile the contracts after I regenerated the snark verifying keys and verifier contracts.

I'm also not sure what my epoch key is - the readme gives a value of `88` but I saw `18` in the output.

> [name=nic]`epk` is computed from identity nullifier, epoch number and noce, so it could be that `genUnirepIdentity` generates a new identity, hence a different `epk`.

## Line-by-line review
> [name=nic] Feedbacks regarding Unirep smart contracts are applied at commit: https://github.com/NIC619/UniRep/commit/ea5b9a44ee72e563b4b34c1146f746f7efc3614f

`contracts/SnarkConstants.sol`, `contracts/Poseidon.sol`, `contracts/UnirepParameters.sol`, `contracts/DomainObjs.sol`, `contracts/ComputeRoot.sol`, `contracts/UserStateTransitionVerifier.sol`, `contracts/ReputationVerifier.sol`, `contracts/EpochKeyValidityVerifier.sol`, `contracts/IncrementalMerkleTree.sol`, `contracts/Hasher.sol`

No comments

`contracts/SafeMath.sol`
Consider adding the OpenZepplin contracts to `package.json` and importing the files from `node_modules`. I'm not sure if Hardhat allows this easily but here is how to get the Solidity compiler to look at the correct directories: https://github.com/appliedzkp/maci/blob/master/contracts/scripts/compileSol.sh#L23-L28

`contracts/Address.sol`

Consider importing this from a `node_modules` installation of the OpenZepplin contracts.

`contracts/Unirep.sol`

- Lines 29-54: Some of these storage variables can be marked as [`immutable`](https://solidity.readthedocs.io/en/v0.6.5/contracts.html#constant-and-immutable-state-variables) (if we use a version of Solidity that supports it).
- Lines 181-198: This function doesn't seem to insert a state leaf into the global state tree. Wondering if this is intended.
- Lines 314-341: The proof isn't verified - is this function currently WIP?

> [name=nic] in the current implementation, the lazyledger approach is taken and so
> 1. proofs are verified offchain and
> 2. trees are updated offchain.
> If everyone has processed all Unirep transactions (whether succeed or fail) in the same order, they should derive the same global state trees, epoch trees and nullifier tree.

- Line 220: Consider using OpenZepplin's ECDSA key recovery function instead of `ecrecover` directly.

> [name=nic] Feedbacks applied at commit: https://github.com/NIC619/UniRep/commit/4938371c389825e765a283a06abbe3f5399fa785

- Line 237: What happens if an attester doesn't verify an epoch key? Will their attestation be processed?

> [name=nic] An attester can choose to not verify an epoch key and just attest to it, and this attestation will be processed (assumes that the user can prove that this is his epoch key). I suppose this indiscretion of attester is acceptable as this wouldn't hurt the system as a whole but the attester's own credit.
> Or an attester can even attest to a random junk value, however, since no one can prove that he owns the epoch key, i.e., the random junk value, the attestation will not be processed.

- Line 266: Consider implementing a `hashAttestation()` function in `DomainObjs.sol`.
- Line 283-285: As the `require` statement consumes gas, consider swapping lines 283 and 285.
- Line 314: This function doesn't seem to update anything or verify the proof. Is it currently WIP?

`contracts/OneTimeSparseMerkleTree.sol`

This file isn't referenced anywhere - is this intended?

`circuits/identityCommitment.circom`
- Line 7: `identity_pk` is actually `IdentityCommitment.identity_pk` doubled thrice. Consider renaming this circuit and the `identity_pk` signal name to something else to make the naming clearer.

> [name=nic] Line 7 feedbacks applied at commit: https://github.com/NIC619/UniRep/commit/a898e53afd2ee9b03efd8dd4b33074094ff5a44d

- Line 47: I haven't followed the chat very closely so I might have missed the discussion about generating the identity commitment. Why do we have to derive a prime subgroup element $pk \cdot 8$?

> [name=nic] hmm.. I'm not sure about it. I copied them from Semaphore [here](https://github.com/appliedzkp/semaphore/blob/856e04fc89de58a8e914c542b0c852019d4dd684/circuits/circom/semaphore-base.circom#L189-L207)

>[name=wj] Oops, never mind!

`circuits/proveReputation.circom`, `circuits/userStateTransition.circom` and `circuits/processAttestations.circom`

There is some circuit code regarding calculating quotients and remainders and performing range checks that they are correct. This code looks similar across these three files, so it might be good to create a circuit that abstracts away these operations. Check out the modulo circuit here: https://github.com/agajews/circom-dsl

> [name=nic] Line 7 feedbacks applied at commit: https://github.com/NIC619/UniRep/commit/0a955bc0d33eae070a360963761e148904a9dfc1
I tried to use the modulo circuit in https://github.com/agajews/circom-dsl but ran into a few problems so I currently just move the duplicated circuits into one circuit:
- problem 1: in agajews's modulo circuit a `IsNegative()` circuit is used, and in `IsNegative()` circuit a `sign()` circuit is used, but `sign()` cirucit [compares the input with cosntant](https://github.com/iden3/circomlib/blob/411a7d7576df02476c6f6310f66fef9c96e5daff/circuits/sign.circom#L26) `10944121435919637611123202872628637544274182200208017171849102093287904247808` which is a value between `2^252` and `2^253`, but the output from poseidon hash function could be larger than this constant and hence be taken as a negative value and result in wrong modulo.
- problem 2: there's a `MultiRangeProof` in agajews's modulo circuit but I did not find an example in the codebase or the circomlib codebase. I guess it' just a circuit that perfomrs range checks on given inputs but not sure about it.

`circuits/proveReputation.circom`, `circuits/processAttestations.circom`, `circuits/userStateTransition.circom`
Looks good. I'll take a another look next week.

`circuits/verifyHashChain.circom`
No comments.

`circuits/poseidon/poseidonHashT3.circom`
No comments.

`circuits/poseidon/common.circom`
No comments.

`circuits/poseidon/poseidonHashT6.circom`
No comments.

`circuits/hasherPoseidon.circom`
No comments.

`circuits/verifiyEpochKey.circom`

- Line 45: Is the highest possible nonce $2^8 = 256$?

> [name=nic] yes, though I just hardcoded this limit in the circuit as the highest possible nonce wasn't specified in the spec. But there's another system parameter `numEpochKeyNoncePerEpoch` outside of circuit that would limit the actual number of possible nonce in the system (which is currently set to `2`).

- Line 69: The circuit uses `epoch_key_depth` (which is 8 for the test circuit) bits for `LessThan`, but uses `LessThan` to check `epoch_key`. Could a user pass in an epoch key that is larger than $2^8$? Even though `genEpochKey()` in `test/utils.ts` adjusts the epoch key to be mod `2 ** _epochTreeDepth`, consider checking whether it's possible for a user to bypass this.

> [name=nic] currently the circuit would [check that `epoch_key` input should be less than `2 ** epochTreeDepth`](https://github.com/NIC619/UniRep/blob/0802117baa1a05622584545b37e9058d9957d631/circuits/verifiyEpochKey.circom#L68-L72)

`circuits/incrementalMerkleTree.circom`
No comments.

`circuits/sparseMerkleTree.circom`
No comments.

## Tests

> [name=nic] Feedback applied at commit: https://github.com/NIC619/UniRep/commit/95d64f80ceda4dd3670c14ce2f546942a8b5e5b0

**`npm run test`**

- Commands to run tests should set this environment variable:
`NODE_OPTIONS=--max-old-space-size=4096`. Otherwise some circuit-related tests will run out of memory. Consider adding it to the testing shell scripts and `package.json` commands.

  User State Transition circuits                                                                                                                                                             
    Epoch key exists                                                                                                                                                                         
Compile time: 8 seconds                                                                                                                                                                      
      ✓ Existed epoch key should pass check (629ms)                                                                                                                                          
    User State Transition                                                                                                                                                                    
                                                                                                                                                                                             
<--- Last few GCs --->

[26775:0x3e49270]   216821 ms: Mark-sweep 1358.6 (1440.2) -> 1344.3 (1440.2) MB, 792.7 / 0.0 ms  (average mu = 0.183, current mu = 0.112) allocation failure scavenge might not succeed
[26775:0x3e49270]   217417 ms: Mark-sweep 1358.9 (1440.2) -> 1345.2 (1440.7) MB, 545.1 / 0.0 ms  (average mu = 0.139, current mu = 0.084) allocation failure scavenge might not succeed


<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x106e3f4fc5d]
    1: StubFrame [pc: 0x106e3f38bac]
Security context: 0x32ffc431d9d1 <JSObject>
    2: inv [0x339acd570f99] [/home/di/UniRep/node_modules/ffjavascript/build/main.cjs:~3201] [pc=0x106e61596b4](this=0x0d37efe22579 <ZqField map = 0xa4f03ec5eb1>,0x32f19feaeab1 <BigInt ...$
0651079904119584648>)
    3: isolateSignal [0x1801db57591] [/home/di/UniRep/node_modules/circom/src/compiler.js:~491] [pc=0x106e619a0bd...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory
 1: 0x95b8f0 node::Abort() [node]
 2: 0x95c836 node::OnFatalError(char const*, char const*) [node]
 3: 0xb3b77e v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [node]
 4: 0xb3b9b4 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [node]
 5: 0xf3b002  [node]
 6: 0xf3b108 v8::internal::Heap::CheckIneffectiveMarkCompact(unsigned long, double) [node]
 7: 0xf47828 v8::internal::Heap::PerformGarbageCollection(v8::internal::GarbageCollector, v8::GCCallbackFlags) [node]
 8: 0xf4833b v8::internal::Heap::CollectGarbage(v8::internal::AllocationSpace, v8::internal::GarbageCollectionReason, v8::GCCallbackFlags) [node]
 9: 0xf4b071 v8::internal::Heap::AllocateRawWithRetryOrFail(int, v8::internal::AllocationSpace, v8::internal::AllocationAlignment) [node]
10: 0xf1b89d v8::internal::Factory::NewBigInt(int, v8::internal::PretenureFlag) [node]
11: 0x1096654 v8::internal::BigInt::Multiply(v8::internal::Isolate*, v8::internal::Handle<v8::internal::BigInt>, v8::internal::Handle<v8::internal::BigInt>) [node]
12: 0x11a2605 v8::internal::Runtime_BigIntBinaryOp(int, v8::internal::Object**, v8::internal::Isolate*) [node]
13: 0x106e3f4fc5d
Aborted (core dumped)
npm ERR! code ELIFECYCLE
npm ERR! errno 134

**`testCLI.sh`**

eth_call                                                                                                                                                                    
  Contract call:       <UnrecognizedContract>                                                                                                                               
  From:                0xf39fd6e51aad88f6f4ce6ab8827279cfffb92266                                                                                                           
  To:                  0xb3dd32d090f05afd6225e6b611bb25c1e87a650b                                                                                                           
                                                                                                                                                                            
npx ts-node cli/index.ts userStateTransition -x 0xb3dD32d090f05Afd6225e6b611bb25C1E87a650B  -d 0xb10e2d527612073b26eecdfd717e6a320cf44b4afac2b0732d9fcbe2b7fa0cf6  -id "[\"$
33a8388b299f2f75916a5baa869bbb0c1fe9327c91595588c177d3aae63d2bd\",\"34279446944fcabdf5e1a5d929483872db83146d2f850759946c819b7ea8b4\",\"61d6e7bba7e5ce64c25311f9aea31e058be5$
23c34e9b27403db65a6903d1d\"]"                                                                                                                                               
<--- Last few GCs --->                                                                                                                                                      
                                                                                                                                                                            
[25005:0x3a766a0]    64347 ms: Mark-sweep 1371.0 (1441.2) -> 1357.2 (1441.7) MB, 624.0 / 0.0 ms  (average mu = 0.182, current mu = 0.085) allocation failure scavenge might 
not succeed                                                                                                                                                                 
[25005:0x3a766a0]    65104 ms: Mark-sweep 1371.8 (1441.7) -> 1357.8 (1443.2) MB, 665.7 / 0.0 ms  (average mu = 0.152, current mu = 0.121) allocation failure scavenge might 
not succeed                                                                                                                                                                 
                                                                                                                                                                            
                                                                                                                                                                            
<--- JS stacktrace --->                                                                                                                                                     
                                                                                                                                                                            
==== JS stack trace =========================================

    0: ExitFrame [pc: 0x3202da9cfc5d]
    1: StubFrame [pc: 0x3202da9b8bac]
Security context: 0x3edb53f1d9d1 <JSObject>
    2: inv [0x622d6af0b39] [/home/di/UniRep/node_modules/ffjavascript/build/main.cjs:~3201] [pc=0x3202dae2a1d8](this=0x12f4bf25c7a1 <ZqField map = 0x3942b4c83381>,0x3d2e9c$
f8ad9 <BigInt ...2102584561527894431>)
    3: reduceConstrains [0x2d4c984fea9] [/home/di/UniRep/node_modules/circom/src/compiler.js:~305] [pc=0x3202db...
      1) should transition user state
    genReputationProof CLI subcommand

And:

eth_call                                                                                                                                                                             [1/1033]
  Contract call:       <UnrecognizedContract>                                                                                                                                                
  From:                0xf39fd6e51aad88f6f4ce6ab8827279cfffb92266
  To:                  0xb3dd32d090f05afd6225e6b611bb25c1e87a650b

npx ts-node cli/index.ts verifyReputationProof -x 0xb3dD32d090f05Afd6225e6b611bb25C1E87a650B  -a 1  -mp 0  -mn 10  -gp 0  -pf undefined                                                     

      3) should verify user reputation proof


  8 passing (3m)
  3 failing

  1) test all CLI subcommands
       userStateTransition CLI subcommand
         should transition user state:

      AssertionError: expected null to not equal null
      + expected - actual


      at Context.it (cli/test/testAllCommands.ts:226:48)
      at processImmediate (internal/timers.js:443:21)

  2) test all CLI subcommands
       genReputationProof CLI subcommand
         should generate user reputation proof:
     TypeError: Cannot read property '1' of null
      at Context.it (cli/test/testAllCommands.ts:246:48)
      at processImmediate (internal/timers.js:443:21)

  3) test all CLI subcommands
       verifyReputationProof CLI subcommand
         should verify user reputation proof:

      AssertionError: expected null to not equal null
      + expected - actual


      at Context.it (cli/test/testAllCommands.ts:266:40)
      at processImmediate (internal/timers.js:443:21)