Questions about circuit design.

[fitz0401]

ZPiE is the best ZKP lib I've ever seen for IoT devices, especially for those low-resource devices. I've read the article, but I still felt confused about the circuit design. I wonder if there are any detailed information about the usage of GMP, and how can I modify the "circuit.c" and "parser.c" for my own circuit? I'm eager to learn more about it.

[xevisalle]

Unfortunately I never had the time to write down a proper documentation. However, feel free to ask any doubts you might have. circuit.c is basically where you need to define your circuit, the first function to be called will be void circuit(). You can write in there your circuit. You have some examples there, you can call the provided mimc7 and verify_eddsa circuits (what is commonly known as gadget), or you can write your own circuits using the constraint API, defined in parser.c.

A basic example is this one:

// we declare 3 variables
element x, y, z;

// we init z as a public value
init_public(&z);

// x and y are secret values
init(&x);
init(&y);

// we set values to x and y
input(&x, "123");
input(&y, "456");

// we add a constraint x * y - z = 0
mul(&z, &x, &y);

[fitz0401]

Thanks for your kind reply!

Based on your instruction, I've tried on building my own circuits. During this process, I encountered two problems:

1. About the example you provided with (x * y - z = 0). I compiled the circuit, but the proof cannot be verified.

./zpie -s -l
******************* ZPiE v0.2 *******************
--- Starting ZPiE - Groth'16...
  |--- # of constraints: 1
  |--- # of variables: 104
  |--- # of public outputs: 2
  |--- Multi-core execution: OFF
  |--- Elliptic curve: BN128
[log] : Computing R1CS...z = 0
 [OK]
A = 
( 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 )

B = 
( 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 )

C = 
( 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 )
[SUCCESS] : Setup generated successfully in 0.001381s

./zpie -p -l
******************* ZPiE v0.2 *******************
--- Starting ZPiE - Groth'16...
  |--- # of constraints: 1
  |--- # of variables: 104
  |--- # of public outputs: 2
  |--- Multi-core execution: OFF
  |--- Elliptic curve: BN128
  |--- Mode: Prove
  |--- FFT constraints size : 8
[SUCCESS] : ZPiE started successfully in 0.001151s

--- Computing proof...
z = 56088
  |--- Circuit evaluation:  [0.000003s]
  |--- Compute h coefficients:  [0.000047s]
  |--- G1, G2 multiexponentiations:  [0.000747s]
     |--- Bos-Coster:  [0.000468s]
     |--- Heap sorting:  [0.000048s]
[log] : Computing piA, piB1, piB2, piC, htdelta... [OK]
piA = 1 3759619141841650404061214062338360910087201555026304906987970188647175722513 9002328239889501218609600097946312968147497694431445375684394726538870337364
piB1 = 1 4360354937291547834594054044603895397629644495188817042946272487937750907465 14774409891512892628963753478006862814911306096174397397191389245187326604060
piB2 = 1 737425245817544819493936934116563820337314478169314416975927993369931611181 8591424616544818633354699872195099056354054442420303692600672140049754737758 12436759757694816250336361726211862081451240870685907449550911585559745271419 3234021187886887967612952885681706779226830708936492299757343201101601823155
piC = 1 21256770637655127111620036133011538148305848454332188213918766970984503486976 17865885669429412503446441621162887714131058855913393626323093583508865072596
htdelta = 1 16135027617750894576853491865109134518635696057457854061134353748996967498521 21198951113473008218295680481043688574456019164059089244597036770558101763427
[SUCCESS] : Proof generated successfully in 0.001092s

./zpie -v -l
******************* ZPiE v0.2 *******************
--- Starting ZPiE - Groth'16...
  |--- # of constraints: 1
  |--- # of variables: 104
  |--- # of public outputs: 2
  |--- Multi-core execution: OFF
  |--- Elliptic curve: BN128
[log] : Computing e(piA, piB2), e(Vu, gamma), e(piC, delta)... [OK]
e(piA, piB2) = 14327193653168357035226823980902740284836851413681131891123727308583101460326 1593019530000824043083773887968597933716914029308191275219226515090806010977 16780154036704740249545789059166389038571726286118367034685978051493266526931 2093530449349322630146314725618628542145672098731244484364146627479961630590 2189951405580736172383374180699023238814634777927738293583826965558740196086 14090036418409427781040291711345652739038762621248044410339272545119379814590 5106754661896655492909588721165415144555609553260758601606483125831372061420 9038188305912575859598323696118687903666406130168864970045497362633080540046 4782297760378200493259003596748067043799095356059717649256545029153674708306 8523913880711694039504602893370424395088218698308732917509473430220646187784 6642559826054626978251412551632080292182023304762977676127262639051784545830 3720077592605994003151426653112311583028031865548251902392377771897835505064
e(Vu, gamma) = 17941584213333465904503356783515478743699217802056681811499615879513765534313 9142057490661835224569414669630975993532194434679954145959863424677375055412 11332358167093055345298102680638479079545386987485761388405794196775651081715 4220638617627872796470407007931154889386356246091017467570591298282147828670 17981574787876578073809108680232211638111468388131624925422441067069714827336 4206656224933245884736335405342165180373854136499111845555181326650428771101 18644220226566508803619655585702577639100865644415159694433295026808943103648 19007792643698132723105365332221816162966265242089935238137783930057015363107 15636254353761658349456451833406164472694323861151476169850333584622239628159 14933215351500677198993026539711941614222042060276547468922677478228033209322 2858904885953065155407110956445562471595673173348115542913527324046960452558 4866351197575340676050860866289080104525312019716429321722460931798058895267
e(piC, delta) = 1204787370864913943298443530856092599340769943102557213563147502957258167831 8250862500769965108780332347271352177664934493922249924557325834440013637691 20183028844518360347865541859933499097835856453984180317325955996686509168815 16134336706984095296307391631157106521651930191190093812558704545935152840014 17525724076975432488404765823532972199115527467249946626941953800746628152693 14946734162207721983315633925982212815570673477772836955144365468007305496766 12566313275705622232166314754294713773909277436602361433170302480043241649865 686430012284418421407137758529406409478139372086672911511958915161188173574 17196894229554941864845116634487211610254216354824124556935567460519925390204 3480685708659332226335219112911474323397190058046062384612580294886295562792 11540965378446732880011010020278646763779177860204177532732616320933300268132 4601270875455999861247071684611884465506373508823079479785425931702276800066
[log] : Computing e(alpha, beta) * e(Vu, gamma) * e(piC, delta)... [OK]
e(alpha, beta) * e(Vu, gamma) * e(piC, delta) = 15597029577961779234172544075791565604394938954369135247630366193125948432541 21557495917625873697597395462121084973139703479884589736848003970673276271435 4307629703203084253109587666091748411867861705936455100007270487016306119488 21441572083414292038418801201208153659678994176417547353928638010838258427869 12779283902512931579540717908498610392135053784782875751339976510193481505161 8361446283718810155436414746641214459730541579479928985430139840163539236569 14512132889405660363645439017216746900978411237817953691111225139180967489171 21013709112104468523894912600560200457331392700446988509233339928442024520487 5253621901829642824010239350047128081236424660132875996692797962671282172374 2180088399572184838147196530011195584029771066509901362741174149087022425138 521784541342980659422047946487167931695159209174988135678931566492272868818 1259220116869720446297330106235424067028217741347880536730143782107025985953
[log] : e(piA, piB2) = e(alpha, beta) * e(Vu, gamma) * e(piC, delta)??? [ERROR]
[FAIL] : Proof cannot be verified

Actually, I wonder why the total number of variables(M) is added by 100 in init_setup():

 M+=100; // experimental

but even without M += 100, the proof still cannot be verified.

I found this problem may be caused by the number of constraints, because when N is a big number, the proof can be verified. That is, in init_setup():

M = 100;
N = 100;
nPublic = 0;

the N and M is initially set to 100. In this case, the proof can be verified.

Currently, I didn't figure out what causes this BUG.

2. What if I want to design a circuit which contains logical switch, for example, if. Is this supported by parser.c?

An example is like this:

void test(){
    // we declare 2 variables
    element a, out;

    // we init out as a public value
    init_public(&out);

    // a is secret value, we verify whether it's within [1, 5].
    // True: out = 1; 
    // False: out = 0;
    init(&a);

    // we set values to a
    input(&a, "2");

    // define 1 and 0 for calculation
    element one, zero;
    init(&one);
    init(&zero);
    input(&one, "1");
    input(&zero, "0");

    // Can I add constraint like this?
    if(uw[a.index] >= 1 && uw[a.index] <= 5){
        mul(&out, &one, &one);
    } else {
        mul(&out, &one, &zero);
    }
    element_log("out=", &out);
}

In this test, I want to use ZKP to verify whether a is within [1,5]. Does this design make sense?

Looking forward to your reply. Thanks your sooooo much.

[xevisalle]

Hey, thanks for your questions.

1) About this, yes, it is a bug that I tried to fix with this temporary patch, but it seems that you also need to set a big value to N. Indeed, the problem comes when using small values. My intuition is that it comes from the Heap Sorting algorithm needed to perform the Bos-Coster multiexponentiation. I will need to add tests and work further on this. By now, you can also try to use the multiexponentiation algorithm provided by the MCL library (which happens to be a bit less efficient). Just recompile with:

make single MULEXP=MCL_MULEXP

2) Sadly I haven't implemented comparators. But you can take this code as a good reference: https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom

It should be pretty simple to implement, as the Num2Bit function that they use is already implemented for ZPiE here: https://github.com/xevisalle/zpie/blob/7e944d43ba34d9747fafe4ef691c575ba8fd9287/circuits/eddsa.c#L129C8-L129C8

Once you have these functions, and for what concerns the circuit workflow, the idea is that if an input is within the range, the proof will verify, and won't verify otherwise. It's like, you don't really need to "print" anything, simply check whether the proof is verified or not.

On the other hand, you can use if, else, for, etc. when writing the circuit, but these won't be part of the arithmetic circuit, they will be executed when compiling that circuit (e.g. you can write a loop that adds X constraints to the circuit).

Hope this helps! :)

EDIT: I just implemented an assertEqual() function here: https://github.com/xevisalle/zpie/tree/assertequal

and I remembered that the evaluation of the comparison has to be done off-circuit. What I mean is that, even if the assertation is not correct, the proof will verify. The result of the evaluation is a public value of the circuit, and in this case, it has to be checked if it equals to 0. You can check the example that I added, in test2(), in this same branch.

I will try to figure out if there is a workaround, so that the verification fails if it's not 0.

EDIT2: ok, fixed :) you can check how assertEqual works here: https://github.com/xevisalle/zpie/blob/d06b9f077ae1359accce608f771f53d6a2f2d483/circuits/eddsa.c#L224

[fitz0401]

Thanks for your kind help!

The assertEqual function worked. And as for the first BUG mentioned before, currently I just simple modify N to a big value.

I've checked the https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom for reference of comparators these days. But there is no progress yet, I wonder can you offer a simple demo of how LessThan or something like this work?

Basically, I want to fulfill a function like this:

private a;
temp_value b;
public out;

if(a < 1){
b = b + 1;
} else {
b = b - 1;
}

assert_equal(out == b);

[fitz0401]

Hey, I rethought about you advice, and wrote the circuit below to achieve my goal:

void test(int private_num, char* public_value){
    int temp_val = 100;

    // The operational logic
    if(private_num < 1){
        temp_val = temp_val + 1;
    } else {
        temp_val = temp_val - 1;
    }
    char buff[255];
    sprintf(buff, "%d", temp_val);

    // The circuit constraint
    element temp_val_to_verify, public_value_to_verify;
    init(&temp_val_to_verify);
    input(&temp_val_to_verify, buff);
    init(&public_value_to_verify);
    input(&public_value_to_verify, public_value);

    assertEqual(&public_value_to_verify, &temp_val_to_verify);
}

That is, the operation logic can be done first and achieved by c operators. After obtaining the OUTPUT of the operation function, I just need to verify whether the public_value equals to the OUTPUT.

I wonder if this is the right way? :->

[xevisalle]

It is correct as long as you keep in mind that the condition at the begining is NOT in-circuit. For in-circuit comparisions you will need to write the comparision utility using logic gates.

[fitz0401]

Thanks a lot!

Recently, I'm studying ZoKrates. I find it can generate verifier in Solidity applications based on the verification.key.

May I ask if I could integrate verifyingkey.params generated by ZPiE into ZoKrates to generate Solidity applications?

I found ZoKrates needs alpha、beta、 gamma、 delta、 gamma_abc. I checked the source code but could not figure out where is gamma_abc. Do you have some ideas about how to associate the verifyingkey.params in ZPiE with verification.key in ZoKrates?

(verification.key in Zokrates)

[xevisalle]

Yes it can be done. Actually I did tried it out time ago. Their gamma_abc is the array that we call in ZPiE vk.vk1[].

[fitz0401]

Thanks for your reply. I've tried to obtain the verification.key and proof by:

// alpha、beta、 gamma、 delta、 gamma_abc for verification.key
    char buff[2048];    
    mclBnG1_getStr(buff, sizeof(buff), &s1.alpha, 16);
    printf("s1->alpha: %s\n", buff);
    mclBnG2_getStr(buff, sizeof(buff), &s2.beta, 16);
    printf("s2->beta: %s\n", buff);
    mclBnG2_getStr(buff, sizeof(buff), &s2.delta, 16);
    printf("s2->delta: %s\n", buff);
    mclBnG2_getStr(buff, sizeof(buff), &s2.gamma, 16);
    printf("s2->gamma: %s\n", buff);
    mclBnG1_getStr(buff, sizeof(buff), &s1.vk[0], 16);
    printf("s1->vk[0]: %s\n", buff);
    mclBnG1_getStr(buff, sizeof(buff), &s1.vk[1], 16);
    printf("s1->vk[1]: %s\n", buff);

// piA, piB2, piC for proof.json
    mclBnG1_getStr(buff, sizeof(buff), &piA, 16);
    printf("piA: %s\n", buff);
    mclBnG2_getStr(buff, sizeof(buff), &piB2, 16);
    printf("piB2: %s\n", buff);
    mclBnG1_getStr(buff, sizeof(buff), &piC, 16);
    printf("piC: %s\n", buff);

I've got:

s1->alpha: 1 11218b2c4979cdfb29c631587be5be2b9458195b1622f9e79479ed40a966a388 a6d71fe7936d64e73bc3aa31692f0f6dfa67342c19bf544d9a5587009aad03e
s2->beta: 1 96cdb1feb344a2e8052266b084973c28ad8b9711d49c64f06fc04272e8a12c3 d58d321c543dd112838de6a5e1ff9b23b233f6b33847ca0e9247ec2808005b4 193b6ac5db714d7bc7f5fb9ed2825b8bc6359e5f0ab1120b49fdbb6d7fb8998 398dcc663de38b92ca2929189cc5132bc945be13a0d48d1b8c4d25eaaff9628
s2->delta: 1 27515cfa786bc9fa1521db13c4f6d90f48e7ee55564b7de32fd48305d5218fa0 181309d22b99e4eb3b0286ee43a5bc358eb21f48121728d2eb6d553695e9a864 67fe17170f13d916a9a860bef0da5421570f383934e8088cd939fdfa7858410 3679115fe05745ad03583730e28445f3deb080eb7da4baee0fb1f4feca3dbd5
s2->gamma: 1 110e5d38f8b2d57d8aade2574ac76545064242ca5a131845627ab3eb211fc4e9 20cc4090ba1f0feb30a91dd4f018600aad440a7df2c2e518d8df9c5c85a541ff 13c46168bbb3417dd23f93b45b4d1d4bcd2ffe1c9164091b01dc32482e10ddd9 2d6a0bae9d5c6af881031d21a5aa3eb4714c19c901f2f1ae92149a413d637e26
s1->vk[0]: 1 1b901078bf090b75d688cb3aaa52edfbbff1c77f0cd8e6ed2a9df8d8071d2923 2788636c6d5ccb92c7990e73aec11975cbac04e93f936cb6d03579297b128b7b
s1->vk[1]: 1 920a31b4059f3470c2d53743c6b78be3b8cb14ba8cf76664951b9e02b051110 c5e912a871575689470e207a1a5df85260ec82ca76420ff4aa90719c5185521

piA: 1 16d9d966f370367154be010a6990b7efd031b445f3a56bbb168b7923d016dbd5 37104d626ff02ae9053036b710972032be3eb12d4cc94da723ef9081b833488
piB2: 1 11d20fb0e8eb2374d483b16311d127c7299a024ffa3e916ba781392e31fb48e4 f8840195af384527afb982bd7f6de5fb00dcd51305b6c10f7c622f3a77f4590 76fced461bb38eaf246b0bd0673af8ac04632da0ff912b02670bb1a7f3e561b 294ed9883a31d16eb22efecb5dd8e9ad20e76f611add5d0f68ead09f48663bb5
piC: 1 341fc0280046b839574d84d7e273a977e7ad171015dfb5a8a3fa12736d92d5a b44661279f69b6921a2b5137090bf38deac780187f538f3db145b67daa5f830

And in Zokrates:

{
  "scheme": "g16",
  "curve": "bn128",
  "alpha": [
    "0x11218b2c4979cdfb29c631587be5be2b9458195b1622f9e79479ed40a966a388",
    "0x0a6d71fe7936d64e73bc3aa31692f0f6dfa67342c19bf544d9a5587009aad03e"
  ],
  "beta": [
    [
      "0x096cdb1feb344a2e8052266b084973c28ad8b9711d49c64f06fc04272e8a12c3",
      "0x0d58d321c543dd112838de6a5e1ff9b23b233f6b33847ca0e9247ec2808005b4"
    ],
    [
      "0x0193b6ac5db714d7bc7f5fb9ed2825b8bc6359e5f0ab1120b49fdbb6d7fb8998",
      "0x0398dcc663de38b92ca2929189cc5132bc945be13a0d48d1b8c4d25eaaff9628"
    ]
  ],
  "gamma": [
    [
      "0x110e5d38f8b2d57d8aade2574ac76545064242ca5a131845627ab3eb211fc4e9",
      "0x20cc4090ba1f0feb30a91dd4f018600aad440a7df2c2e518d8df9c5c85a541ff"
    ],
    [
      "0x13c46168bbb3417dd23f93b45b4d1d4bcd2ffe1c9164091b01dc32482e10ddd9",
      "0x2d6a0bae9d5c6af881031d21a5aa3eb4714c19c901f2f1ae92149a413d637e26"
    ]
  ],
  "delta": [
    [
      "0x27515cfa786bc9fa1521db13c4f6d90f48e7ee55564b7de32fd48305d5218fa0",
      "0x181309d22b99e4eb3b0286ee43a5bc358eb21f48121728d2eb6d553695e9a864"
    ],
    [
      "0x067fe17170f13d916a9a860bef0da5421570f383934e8088cd939fdfa7858410",
      "0x03679115fe05745ad03583730e28445f3deb080eb7da4baee0fb1f4feca3dbd5"
    ]
  ],
  "gamma_abc": [
    [
      "0x1b901078bf090b75d688cb3aaa52edfbbff1c77f0cd8e6ed2a9df8d8071d2923",
      "0x2788636c6d5ccb92c7990e73aec11975cbac04e93f936cb6d03579297b128b7b"
    ],
    [
      "0x0920a31b4059f3470c2d53743c6b78be3b8cb14ba8cf76664951b9e02b051110",
      "0x0c5e912a871575689470e207a1a5df85260ec82ca76420ff4aa90719c5185521"
    ]
  ]
}

{
  "scheme": "g16",
  "curve": "bn128",
  "proof": {
    "a": [
      "0x16d9d966f370367154be010a6990b7efd031b445f3a56bbb168b7923d016dbd5",
      "0x037104d626ff02ae9053036b710972032be3eb12d4cc94da723ef9081b833488"
    ],
    "b": [
      [
        "0x11d20fb0e8eb2374d483b16311d127c7299a024ffa3e916ba781392e31fb48e4",
        "0x0f8840195af384527afb982bd7f6de5fb00dcd51305b6c10f7c622f3a77f4590"
      ],
      [
        "0x076fced461bb38eaf246b0bd0673af8ac04632da0ff912b02670bb1a7f3e561b",
        "0x294ed9883a31d16eb22efecb5dd8e9ad20e76f611add5d0f68ead09f48663bb5"
      ]
    ],
    "c": [
      "0x0341fc0280046b839574d84d7e273a977e7ad171015dfb5a8a3fa12736d92d5a",
      "0x0b44661279f69b6921a2b5137090bf38deac780187f538f3db145b67daa5f830"
    ]
  },
  "inputs": [
    "0x0000000000000000000000000000000000000000000000000000000000000002"
  ]
}

(There is one public parameter in this question.)

But the verification can not be passed. Did I get the right values of those parameters from ZPiE?

[fitz0401]

Sorry for wasting your time.

Initially, I didn't understand why there is a public value one, so I deleted it unintentionally.

I thoroughly read the article about Groth' 16, and found:

where a0 = 1. So, this value maybe ensure the subsequent correct calculation and pairing.

Thank you again for your help. There is a lot for me to learn. For now, I think I can close this issue. :>

[xevisalle]

that 1 is a constant value needed to perform some operations. I set it as a public value because of the way how the library parses the circuit, to not overcomplicate other parts of the code. Indeed, it is not how other solutions work. Some day I will give it a thought!