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 ... 

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

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.

nicepk 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

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 (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?

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.

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?

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.

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$?

nic hmm.. I'm not sure about it. I copied them from Semaphore here

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

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 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$?

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.

nic currently the circuit would check that epoch_key input should be less than 2 ** epochTreeDepth

circuits/incrementalMerkleTree.circom
No comments.

circuits/sparseMerkleTree.circom
No comments.

Tests

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)