Circom Verification Circuit

BlakeMScurr commented 1 year ago

Implement the nullifier verification circuits in circom as specified here. The entire circuit is in verify_nullifier.circom, and the entry point is the verify_nullifier template.

The circuit is tested over the same values as the wallet js code. c comes out to the right value, as shown by the "Circuit verifies valid nullifier" test. All sub-circuits are also tested.

NOTE: I made 3 changes to the wallet code:

Changed the hash function from sha512 to sha256 to match the available circuit - please let me know if it was supposed to be sha512!!!
Calculated the $r + sk * c$ modulo CURVE.n rather than CURVE.p. Note that n is the size of the scalar field (i.e., the number of group elements) whereas p is the size of the base field over which the elliptic curve is defined. This was critical in getting any equation of the form $g^{a + b}/g^b = g^a$ to work (the form of the first two equations).
Split out the test constants into a separate file from the tests to import them into the circuit tests.

To run the tests, run npm run flatten-dependencies then npm run test (the longest test took ~20mins on my 8GB ram macbook pro, so be prepared to wait - the whole suite would probably take about 35 mins). Known to work with circom 2.1.2.

weijiekoh commented 1 year ago

Amazing stuff, I'll try it out!

+1 to using SHA256 instead of SHA512. @Divide-By-0, did we chat about this some time ago?

Divide-By-0 commented 1 year ago

Amazing stuff, I'll try it out!

+1 to using SHA256 instead of SHA512. @Divide-By-0, did we chat about this some time ago?

We probably did, I don't remember. sha256 sounds good, happy to switch over the standard and existing code! I assume the main reason would be for efficiency and having a pre-existing circuit?

SHA256 would drop the security to 128 bits for the hash, but since BTC/ETH keys only have 128 bits of security anyways, that seems fine to me.

weijiekoh commented 1 year ago

I assume the main reason would be for efficiency and having a pre-existing circuit?

Yup! I'm thinking the same!

weijiekoh commented 1 year ago

Suggestion to modify the readme to add test instructions; feel free to edit as you see fit

diff --git a/README.md b/README.md
index 7d620fe..df3dc0c 100644
--- a/README.md
+++ b/README.md
@@ -8,10 +8,26 @@ This allows for the construction of deterministic nullifiers. We intend to deplo
 - `rust-arkworks`: Rust, using arkworks
 - `javascript`: JavaScript, using MIRACL

+## Testing the circom circuit
+
+First, clone this repository and navigate to the `circuits/` directory.
+
+Install dependencies:
+
+```bash
+npm i
+```
+
+Run the tests:
+```bash
+npm run npm run flatten-deps && \
+npm run test
+```
+
+Be prepared to wait around 20-40 minutes for the tests to complete.
+
 ## TODO

-- zk verifier circuits (WIP Circom here: https://github.com/geometryresearch/secp256k1_hash_to_curve/tree/main/circuits)
-- change SHA512 to Poseidon (wallets are onboard)
 - improve `rust-k256` to use a similar interface as `rust-arkworks` - i.e.
   generate/accept arbitrary keypairs and `r` values, and not just hardcoded
   values

weijiekoh commented 1 year ago

Attempted to run npm i, but ran into this error:

$ npm i
npm WARN skipping integrity check for git dependency ssh://git@github.com/weijiekoh/circomlib.git 
npm WARN deprecated crypto@1.0.1: This package is no longer supported. It's now a built-in Node module. If you've depended on crypto, you should switch to the one that's built-in.
npm WARN tarball tarball data for secp256k1_hash_to_curve_circom@https://gitpkg.now.sh/geometryresearch/secp256k1_hash_to_curve/circuits?main (sha512-kTtN+pSxEITN3Co28HORjrlGSs1pmLRNrwBPGXyMY1fCUIxBMc7TtW3zkrDxd7cSKb1i70tLHD8eAPSHmZ6RRQ==) seems to be corrupted. Trying again.
npm WARN tarball tarball data for secp256k1_hash_to_curve_circom@https://gitpkg.now.sh/geometryresearch/secp256k1_hash_to_curve/circuits?main (sha512-kTtN+pSxEITN3Co28HORjrlGSs1pmLRNrwBPGXyMY1fCUIxBMc7TtW3zkrDxd7cSKb1i70tLHD8eAPSHmZ6RRQ==) seems to be corrupted. Trying again.
npm ERR! code EINTEGRITY
npm ERR! sha512-kTtN+pSxEITN3Co28HORjrlGSs1pmLRNrwBPGXyMY1fCUIxBMc7TtW3zkrDxd7cSKb1i70tLHD8eAPSHmZ6RRQ== integrity checksum failed when using sha512: wanted sha512-kTtN+pSxEITN3Co28HORjrlGSs1pmLRNrwBPGXyMY1fCUIxBMc7TtW3zkrDxd7cSKb1i70tLHD8eAPSHmZ6RRQ== but got sha512-KDaov5Lz44OeGcuLHhElC8+Lbup6x43LIFRd7em1lJPqO5Vw5IOFBOK8QVKSsGJTxvqFfSzXHHbpu/X/umRpIQ==. (143888 bytes)

It seems that npm i failed so Jest was not installed:

$ npm run test

> zk-nullifier-sig-circuit@1.0.0 test
> NODE_OPTIONS=--max_old_space_size=8192 jest --runInBand

sh: 1: jest: not found

BlakeMScurr commented 1 year ago

@weijiekoh thanks for the feedback! I couldn't recreate your issue exactly, but I think the issue was that I manually edited the hash to curve dependency while I was waiting for my PR to be merged. Since it's merged I reinstalled the dependency, so I don't see why the integrity check should fail now. Are you able to install now?

Also, I kept the TODO item "change SHA256 to Poseidon (wallets are onboard)" since that would probably still be a significant improvement, even if we use SHA256 as opposed to SHA512.

weijiekoh commented 1 year ago

Got this error when running npm run test:

$ npm run test

> zk-nullifier-sig-circuit@1.0.0 test
> NODE_OPTIONS=--max_old_space_size=8192 jest --runInBand

 FAIL  test/vfy_nullifier.test.ts
  ● Test suite failed to run

    test/vfy_nullifier.test.ts:23:103 - error TS2769: No overload matches this call.
      Overload 1 of 2, '(...items: ConcatArray<number>[]): number[]', gave the following error.
        Argument of type 'unknown[]' is not assignable to parameter of type 'ConcatArray<number>'.
          The types returned by 'slice(...)' are incompatible between these types.
            Type 'unknown[]' is not assignable to type 'number[]'.
              Type 'unknown' is not assignable to type 'number'.
      Overload 2 of 2, '(...items: (number | ConcatArray<number>)[]): number[]', gave the following error.
        Argument of type 'unknown[]' is not assignable to parameter of type 'number | ConcatArray<number>'.
          Type 'unknown[]' is not assignable to type 'ConcatArray<number>'.

    23   const hash_to_curve_inputs = utils.stringifyBigInts(generate_inputs_from_array(message_bytes.concat(public_key_bytes)));
                                                                                                             ~~~~~~~~~~~~~~~~

Test Suites: 1 failed, 1 total
Tests:       0 total
Snapshots:   0 total
Time:        1.926 s
Ran all test suites.

BlakeMScurr commented 1 year ago

@weijiekoh strange, I don't get that error. Also, my IDE is able to infer that public_key_bytes is a number[]. Perhaps we are running with a different version/configuration of typescript that is somehow specified outside the repo. Could you please check your typescript version using tsc -v? Mine is Version 4.0.2.

For a sanity check, does that error go away if you declare the type of public_key_bytes? I.e., change line 16 to const public_key_bytes: number[] = Array.from(testPublicKey);

weijiekoh commented 1 year ago

I don't have tsc installed globally, but it is installed locally:

$ npx tsc --version
Version 4.9.5

The error does go away after I edit line 16 but there are more build errors:

$ npx tsc
../javascript/src/index.ts:1:23 - error TS2307: Cannot find module '@noble/secp256k1' or its corresponding type declarations.

1 import { Point } from "@noble/secp256k1";
                        ~~~~~~~~~~~~~~~~~~

../javascript/src/utils/curve.ts:1:23 - error TS2307: Cannot find module '@noble/secp256k1' or its corresponding type declarations.

1 import { Point } from "@noble/secp256k1";
                        ~~~~~~~~~~~~~~~~~~

../javascript/src/utils/hashToCurve.ts:1:21 - error TS2307: Cannot find module 'amcl-js' or its corresponding type declarations.

1 import { CTX } from "amcl-js";
                      ~~~~~~~~~

../javascript/test/test_consts.ts:1:44 - error TS2307: Cannot find module '@noble/secp256k1' or its corresponding type declarations.

1 import { CURVE, getPublicKey, Point } from "@noble/secp256k1";
                                             ~~~~~~~~~~~~~~~~~~

Found 4 errors in 4 files.

Errors  Files
     1  ../javascript/src/index.ts:1
     1  ../javascript/src/utils/curve.ts:1
     1  ../javascript/src/utils/hashToCurve.ts:1
     1  ../javascript/test/test_consts.ts:1

There's also another error:

$ npm run test                                                                                                                                           

> zk-nullifier-sig-circuit@1.0.0 test                                                                                                                                                        
> NODE_OPTIONS=--max_old_space_size=8192 jest --runInBand                                     

 FAIL  dist/circuits/test/vfy_nullifier.test.js
  ● Test suite failed to run                                                                                                                                                                 

    Cannot find module 'amcl-js' from 'dist/javascript/src/utils/hashToCurve.js'              

    Require stack:                                                                            
      dist/javascript/src/utils/hashToCurve.js 
      dist/javascript/src/index.js             
      dist/javascript/test/test_consts.js
      dist/circuits/test/vfy_nullifier.test.js                                                

      1 | "use strict";                                                                       
      2 | Object.defineProperty(exports, "__esModule", { value: true });                      
    > 3 | const amcl_js_1 = require("amcl-js");                                               
        |                   ^              
      4 | const encoding_1 = require("./encoding");                                           
      5 | // Refactored from miracl-core     
      6 | const ctx = new amcl_js_1.CTX("SECP256K1");                                                                                                                                        

      at Resolver._throwModNotFoundError (node_modules/jest-resolve/build/resolver.js:427:11) 
      at Object.<anonymous> (dist/javascript/src/utils/hashToCurve.js:3:19)                   
      at Object.<anonymous> (dist/javascript/src/index.js:9:39)                               
      at Object.<anonymous> (dist/javascript/test/test_consts.js:5:15)                                                                                                                       
      at Object.<anonymous> (dist/circuits/test/vfy_nullifier.test.js:7:23)                   

 FAIL  test/vfy_nullifier.test.ts         
  ● Test suite failed to run                   

    ../javascript/test/test_consts.ts:1:44 - error TS2307: Cannot find module '@noble/secp256k1' or its corresponding type declarations.                                                     

    1 import { CURVE, getPublicKey, Point } from "@noble/secp256k1";                          
                                                 ~~~~~~~~~~~~~~~~~~                           

Test Suites: 2 failed, 2 total                 
Tests:       0 total                                                                          
Snapshots:   0 total                                                                          
Time:        1.824 s                           
Ran all test suites.

BlakeMScurr commented 1 year ago

@weijiekoh ooh OK, thank you. I just realised the problem is that you have to go to ../javascript and run npm install there too. I guess it's kinda janky - we have two different npm packages, since they're used for different purposes, javascript goes in the wallet, whereas circuit is for generating proofs in the browser. Yet the circuit tests depend on javascript. I guess I could make the javascript package an actual dependency in package.json, but for now I'll just update the readme to require another npm install.

By the way, you might want to run npm run test -- -t "compressed" to make sure we've solved all the typescript issues. That test should finish in less than 10 seconds.

weijiekoh commented 1 year ago

Still having trouble...

$ npm run flatten-deps                                                                                                                 

> zk-nullifier-sig-circuit@1.0.0 flatten-deps                                                                                                                              
> bash flatten-nested-dependencies.sh                                                                                                                                      

sed: can't read s/"\.\.\/\.\.\/node_modules\/circomlib/"\.\.\/\.\.\/\.\.\/circomlib/: No such file or directory
sed: can't read s/"\.\.\/node_modules\/circomlib/"\.\.\/\.\.\/circomlib/: No such file or directory

This is followed by a lot of the same error messages from sed.

$ npm run test                                   

> zk-nullifier-sig-circuit@1.0.0 test                                                                                                                                      
> NODE_OPTIONS=--max_old_space_size=8192 jest --runInBand                                     

 FAIL  test/vfy_nullifier.test.ts                                                             
  Nullifier Circuit                                                                                                                                                                          
    ✕ hash_to_curve outputs same value (46 ms)                                                
    ✕ Correct sha256 value (28 ms)                                                                                                                                         
    ✕ Correct compressed values are calculated (25 ms)                                        
    ✕ Compressed points are permitted iff they are valid (25 ms)                              
    ✕ Circuit verifies valid nullifier (25 ms)                                                                                                                                               
    ✕ a/b^c subcircuit (25 ms)                                                                                                                                                               
    ✓ bigint <-> register conversion (1 ms)                                                                           

  ● Nullifier Circuit › hash_to_curve outputs same value                                      

    ENOENT: no such file or directory, open '/tmp/circom_-884456-AhxreDf8s0Bo/hash_to_curve_test_js/hash_to_curve_test.wasm'                                                                 

  ● Nullifier Circuit › Correct sha256 value                                                  

    ENOENT: no such file or directory, open '/tmp/circom_-884456-UribBMDkquMV/12_point_sha_256_test_js/12_point_sha_256_test.wasm'                                                           

  ● Nullifier Circuit › Correct compressed values are calculated                              

    ENOENT: no such file or directory, open '/tmp/circom_-884456-0A56qadS5gzk/compression_test_js/compression_test.wasm'                                                                     

  ● Nullifier Circuit › Compressed points are permitted iff they are valid                    

    ENOENT: no such file or directory, open '/tmp/circom_-884456-2iLq0m0rfPeD/compression_verification_test_js/compression_verification_test.wasm'                                           

  ● Nullifier Circuit › Circuit verifies valid nullifier                                                              

    ENOENT: no such file or directory, open '/tmp/circom_-884456-7OVtL1TXzOts/vfy_test_js/vfy_test.wasm'                                                                                     

  ● Nullifier Circuit › a/b^c subcircuit       

    ENOENT: no such file or directory, open '/tmp/circom_-884456-T4Hk8zZce05A/a_div_b_pow_c_test_js/a_div_b_pow_c_test.wasm'                                                                                                                

Test Suites: 1 failed, 1 total                      
Tests:       6 failed, 1 passed, 7 total            
Snapshots:   0 total                                
Time:        2.918 s                                       
Ran all test suites.

weijiekoh commented 1 year ago

I'm using sed v4.8 and node v18.14.0.

BlakeMScurr commented 1 year ago

I assume you're using Linux? It looks like sed is failing because I'm using a Mac specific syntax to specify interactive mode. So the circom isn't properly edited, and doesn't compile, which causes the no such file or directory errors (this is a common circom-tester error).

I have replaced the syntax with something that should be compatible across Mac and Linux. Let me know if it works!

sripwoud commented 1 year ago

@BlakeMScurr I am getting all the same errors as @weijiekoh when trying to run the test suite.

npm WARN skipping integrity check for git dependency ssh://git@github.com/weijiekoh/circomlib.git

Fixed that one by dumping and recreating package-lock.json

Consider restricting the node version between 16 and 19 (>= 16 <19) with the engines option in package.json. I had node-gyp errors otherwise.

Maybe specify in the PR description which circom version is required? I first had 2.0.0 and had some errors when running the test.

Finally after

cd javascript && npm i
cd circuits && npm i && npm flatten-deps

npm t ran all circuits tests successfully for me on macOS only.

On linux, I have lot of

tsc errors

```commandline Nullifier Circuit ✓ hash_to_curve outputs same value (70615 ms) ✕ Correct sha256 value (122 ms) ✕ Correct compressed values are calculated (120 ms) ✕ Compressed points are permitted iff they are valid (113 ms) ✕ Circuit verifies valid nullifier (112 ms) ✕ a/b^c subcircuit (111 ms) ✓ bigint <-> register conversion (1 ms) ● Nullifier Circuit › Correct sha256 value assert.notStrictEqual(received, expected) Expected value not be strictly equal to: undefined Received: null Message: circom compiler error Error: Command failed: circom --wasm --sym --r1cs --json --output /tmp/circom_-81034-hbW0pPIaOQ5c /home/r1oga/dev/zk-nullifier-sig/circuits/test/12_point_sha_256_test.circom error[P1000]: Include not found: ./node_modules/secp256k1_hash_to_curve_circom/circom/sha256.circom previous errors were found Difference: Comparing two different types of values. Expected undefined but received null. 58 | 59 | const p = join(__dirname, '12_point_sha_256_test.circom') > 60 | const circuit = await wasm_tester(p, {"json":true, "sym": true}) | ^ 61 | 62 | const w = await circuit.calculateWitness({coordinates, preimage_bit_length: sha256_preimage_bit_length}, true) 63 | await circuit.checkConstraints(w); at compile (node_modules/circom_tester/wasm/tester.js:91:2) at wasm_tester (node_modules/circom_tester/wasm/tester.js:45:2) at Object. (test/vfy_nullifier.test.ts:60:21) ● Nullifier Circuit › Correct compressed values are calculated assert.notStrictEqual(received, expected) Expected value not be strictly equal to: undefined Received: null Message: circom compiler error Error: Command failed: circom --wasm --sym --r1cs --json --output /tmp/circom_-81034-nJusIiW8EEES /home/r1oga/dev/zk-nullifier-sig/circuits/test/compression_test.circom error[P1000]: Include not found: ./node_modules/secp256k1_hash_to_curve_circom/circom/sha256.circom previous errors were found Difference: Comparing two different types of values. Expected undefined but received null. 67 | test("Correct compressed values are calculated", async () => { 68 | const p = join(__dirname, 'compression_test.circom') > 69 | const circuit = await wasm_tester(p, {"json":true, "sym": true}) | ^ 70 | 71 | for (var i = 0; i < sha_preimage_points.length; i++) { 72 | const w = await circuit.calculateWitness({uncompressed: pointToCircuitValue(sha_preimage_points[i])}, true) at compile (node_modules/circom_tester/wasm/tester.js:91:2) at wasm_tester (node_modules/circom_tester/wasm/tester.js:45:2) at Object. (test/vfy_nullifier.test.ts:69:21) ● Nullifier Circuit › Compressed points are permitted iff they are valid assert.notStrictEqual(received, expected) Expected value not be strictly equal to: undefined Received: null Message: circom compiler error Error: Command failed: circom --wasm --sym --r1cs --json --output /tmp/circom_-81034-65lChAFEeJSW /home/r1oga/dev/zk-nullifier-sig/circuits/test/compression_verification_test.circom error[P1000]: Include not found: ./node_modules/secp256k1_hash_to_curve_circom/circom/sha256.circom previous errors were found Difference: Comparing two different types of values. Expected undefined but received null. 78 | test("Compressed points are permitted iff they are valid", async () => { 79 | const p = join(__dirname, 'compression_verification_test.circom') > 80 | const circuit = await wasm_tester(p, {"json":true, "sym": true}) | ^ 81 | 82 | for (var i = 0; i < sha_preimage_points.length; i++) { 83 | for (var j = 0; j <= i; j++) { at compile (node_modules/circom_tester/wasm/tester.js:91:2) at wasm_tester (node_modules/circom_tester/wasm/tester.js:45:2) at Object. (test/vfy_nullifier.test.ts:80:21) ● Nullifier Circuit › Circuit verifies valid nullifier assert.notStrictEqual(received, expected) Expected value not be strictly equal to: undefined Received: null Message: circom compiler error Error: Command failed: circom --wasm --sym --r1cs --output /tmp/circom_-81034-DvYrpwI2Ad63 /home/r1oga/dev/zk-nullifier-sig/circuits/test/vfy_test.circom error[P1000]: Include not found: ./node_modules/secp256k1_hash_to_curve_circom/circom/sha256.circom previous errors were found Difference: Comparing two different types of values. Expected undefined but received null. 99 | test("Circuit verifies valid nullifier", async () => { 100 | const p = join(__dirname, 'vfy_test.circom') > 101 | const circuit = await wasm_tester(p) | ^ 102 | 103 | const {msg: _, ...htci} = hash_to_curve_inputs; 104 | at compile (node_modules/circom_tester/wasm/tester.js:91:2) at wasm_tester (node_modules/circom_tester/wasm/tester.js:45:2) at Object. (test/vfy_nullifier.test.ts:101:21) ● Nullifier Circuit › a/b^c subcircuit assert.notStrictEqual(received, expected) Expected value not be strictly equal to: undefined Received: null Message: circom compiler error Error: Command failed: circom --wasm --sym --r1cs --output /tmp/circom_-81034-mazY7qJF7uAI /home/r1oga/dev/zk-nullifier-sig/circuits/test/a_div_b_pow_c_test.circom error[P1000]: Include not found: ./node_modules/secp256k1_hash_to_curve_circom/circom/sha256.circom previous errors were found Difference: Comparing two different types of values. Expected undefined but received null. 120 | test("a/b^c subcircuit", async () => { 121 | const p = join(__dirname, 'a_div_b_pow_c_test.circom') > 122 | const circuit = await wasm_tester(p) | ^ 123 | 124 | // Verify that gPowS/pkPowC = gPowR outside the circuit, as a sanity check 125 | const gPowS = Point.fromPrivateKey(s); at compile (node_modules/circom_tester/wasm/tester.js:91:2) at wasm_tester (node_modules/circom_tester/wasm/tester.js:45:2) at Object. (test/vfy_nullifier.test.ts:122:21) Test Suites: 1 failed, 1 total Tests: 5 failed, 2 passed, 7 total Snapshots: 0 total Time: 72.419 s, estimated 73 s Ran all test suites. ```

So maybe there is still an issue with the flatten-deps script?

BlakeMScurr commented 1 year ago

Thanks @r1oga, I was able to recreate your issues on Linux and fix them. It looks like I had a capitalization typo, but it wasn't causing a problem on Mac for whatever reason. Let me know if it works for you now!

sripwoud commented 1 year ago

Thanks @r1oga, I was able to recreate your issues on Linux and fix them. It looks like I had a capitalization typo, but it wasn't causing a problem on Mac for whatever reason. Let me know if it works for you now!

Yep! I confirm I could run all the tests on linux successfully too.

Divide-By-0 commented 1 year ago

Cool! Ready to merge once the conflict is fixed. Constraint breakdown from Blake here: 6.5 million constraints. Mostly dominated by EC operations, but the hashes are very expensive too.

sha256 ~1.5M hash_to_curve ~0.5M a/b^c ~1.5 each (this is the sub circuit for the first 2 verification equations) the remaining 1.5M is probably dominated by calculating g^s and h^s

BlakeMScurr commented 1 year ago

Sweet! @Divide-By-0 merge conflicts fixed, all tests still passing.

BlakeMScurr commented 1 year ago

@Divide-By-0, just resolved conflicts again, tests still working.

We should get this merged soon, since I've had to re-fix the CURVE.P vs CURVE.n bug each time I've resolved conflicts, which feels kinda error prone.

Divide-By-0 commented 1 year ago

Merged! Sorry about delay, I'll give you merge access for the future as well.

BlakeMScurr commented 1 year ago

Thanks!! No problem!

plume-sig / zk-nullifier-sig

Circom Verification Circuit #7