akosba / jsnark Goto Github PK

Hi Ahmed @akosba

Could you please clarify if we have to run the AES128CipherCircuit multiple times (from generateCircuit()->evalCircuit()->prepFiles()->runLibsnark()) for plain texts of size more than 16 bytes? Or could there be a better way to use this circuit for larger plaintext sizes?

Thank you very much.

Do we really need JAVA 8? Or can we go with JAVA current?

$ java -cp bin examples.generators.SimpleCircuitGenerator

on the original code produces these two files and the following result.

# simple_example.arith
total 12
input 0                  # The one-input wire.
const-mul-0 in 1 <0> out 1 <1>
input 2
input 3
input 4
input 5
mul in 2 <2 3> out 1 <6>
add in 2 <4 5> out 1 <7>
const-mul-5 in 1 <0> out 1 <8>
add in 2 <6 8> out 1 <9>
const-mul-6 in 1 <7> out 1 <10>
mul in 2 <9 10> out 1 <11>
output 11

# simple_example.in
0 1
2 1
3 2
4 3
5 4

Running Circuit Generator for < simple_example >
Circuit Generation Done for < simple_example >
     Total Number of Constraints :  2

Running Circuit Evaluator for < simple_example >
    [output] Value of Wire # 11 :: 294
Circuit Evaluation Done for < simple_example >



-----------------------------------RUNNING LIBSNARK -----------------------------------------
Reset time counters for profiling
(enter) Parsing and Evaluating the circuit  [             ] (0.0011s x1.00 from start)
     Evaluation Done in 0.000002 seconds
(leave) Parsing and Evaluating the circuit  [0.0002s x0.98] (0.0013s x1.00 from start)
Translating Constraints ...
    Constraint translation done
    Memory usage for constraint translation: 0 MB
Assignment of values done ..

Printing output assignment::
[output] Value of Wire # 11 :: 294

...

========================================================================
R1CS ppzkSNARK Verifier
========================================================================
* The verification result is: PASS

But when I intentionally change the contents of the input or the circuit file,
the result does not change.

For example, I tried to run libsnark with the following setup by manually changing the files.

# simple_example.arith
total 12
input 0                  # The one-input wire.
const-mul-0 in 1 <0> out 1 <1>
input 2
input 3
input 4
input 5
mul in 2 <3 2> out 1 <6>
add in 2 <3 2> out 1 <7>
const-mul-5 in 1 <0> out 1 <8>
add in 2 <3 2> out 1 <9>
const-mul-6 in 1 <7> out 1 <10>
mul in 2 <3 2> out 1 <11>
output 11

# simple_example.in
0 10
2 10
3 10
4 10
5 10
6 10

and I get this result.

Running Circuit Generator for < simple_example >
Circuit Generation Done for < simple_example >
     Total Number of Constraints :  2

Running Circuit Evaluator for < simple_example >
    [output] Value of Wire # 11 :: 294
Circuit Evaluation Done for < simple_example >



-----------------------------------RUNNING LIBSNARK -----------------------------------------
Reset time counters for profiling
(enter) Parsing and Evaluating the circuit  [             ] (0.0017s x0.67 from start)
     Evaluation Done in 0.000002 seconds
(leave) Parsing and Evaluating the circuit  [0.0002s x0.99] (0.0019s x0.70 from start)
Translating Constraints ...
    Constraint translation done
    Memory usage for constraint translation: 0 MB
Assignment of values done ..

Printing output assignment::
[output] Value of Wire # 11 :: 256

...

========================================================================
R1CS ppzkSNARK Verifier
========================================================================
* The verification result is: PASS

I've tried many different variations, but always get the same result.

Hi.I want to use jsnark to prove that I know a value x that enc(x) == y that y is a public value.but actually I have lots of problem in how to start. Isn't there any useful tutorial that can help me how to do this step by step?

When I follow the README, ./prepare-depends.sh runs fine. After that,

make yields

g++ -o src/interface/run_libsnark.o   src/interface/run_libsnark.cpp -c -MMD -std=c++11 -Wall -Wextra -Wno-unused-parameter -Wno-comment -Wfatal-errors -O2 -march=native -mtune=native -DUSE_ASM  -DCURVE_BN128 -Idepinst/include -Isrc -DBN_SUPPORT_SNARK -fPIC
In file included from src/common/data_structures/sparse_vector.hpp:77:0,
                 from src/common/data_structures/accumulation_vector.hpp:15,
                 from src/zk_proof_systems/ppzksnark/r1cs_ppzksnark/r1cs_ppzksnark.hpp:52,
                 from src/zk_proof_systems/ppzksnark/r1cs_ppzksnark/examples/run_r1cs_ppzksnark.tcc:18,
                 from src/zk_proof_systems/ppzksnark/r1cs_ppzksnark/examples/run_r1cs_ppzksnark.hpp:33,
                 from src/interface/../interface/CircuitReader.hpp:10,
                 from src/interface/run_libsnark.cpp:7:
src/common/data_structures/sparse_vector.tcc: In constructor �libsnark::sparse_vector<T>::sparse_vector(std::vector<T>&&)�:
src/common/data_structures/sparse_vector.tcc:26:10: error: �iota� is not a member of �std�
     std::iota(indices.begin(), indices.end(), 0);
          ^~~~
compilation terminated due to -Wfatal-errors.
Makefile:230: recipe for target 'src/interface/run_libsnark.o' failed
make: *** [src/interface/run_libsnark.o] Error 1

Can you put it under MIT or GPLv3?

edit:

Ok, if there is no License, the code apparently seems to be in the public domain, which is fine with me also.

When i call the interface "run_ppzksnark", i set params described in doc, file name of .arirth and .in; However i get the error info :Floating point exception (core dumped); I just use the output file of SimpleCircuitGenerator as param of the interface. Does any one know how to fix it?

Hi Ahmed,

Great project! Thanks a lot for such a contribution. Please excuse me that there might be a naive question.

I have look at the FieldDivision example and find the prover_witness_wire seems to be directed to output. I read your document and am thinking any output will be public to the verifier. As a result, will the prover_witness_wire in that example become public?

If the prover_witness_wire in that example is public, is it possible to make a prover_witness_wire as a secret one, like NIZKInput does in Pinocchio? For example, a prover has ten numbers, and she only would like to convince the verifier their average instead of leaking these numbers. Will prover_witness_wires work in this scenario?

Hi akosba, I am learning about RSAEncryptionCircuitGenerator and I would appreciate if you could please clarify the following questions.
My idea is that for RSA zero-knowledge proof, the privKey and the plainText should be private input, the pubKey and the cipherText should be public input. The prover can use the private input and the public input to generate proof, and the verifier can only use the public input and proof to verify (pk, vk are ignored here). But I don't understand much about this generator. This class has only private input inputMessage and randomness, while cipherText is used as output. What I want to ask is, is the pubKey (and the cipherText) not needed here as public input, in other words, is this circuit making a commitment to inputMessage and randomness in RSA rather than the entire encryption process?
In addition, if one has the value of public input, how can one recover the primary_input in libsnark to achieve validation without the verifier knowing the private input?

Hi Ahmed @akosba

Could you please clarify why 'bitwidthPerInputElement' is given as user input in SHA256 gadget? Shouldn't it always be 8 bits? Are there any use cases where it could be different than 8 bits?

I actually tried to make use of this parameter to set 16 hexdigits long words to an input wire (i.e bitwidthPerInputElement=64bits) of the SHA256 gadget. However, the output digest I got in that case is different from the case where I set 2 hexdigits long words (i.e bitwidthPerInputElement=8bits) to an input wire of the SHA256 gadget. In both the cases, I used the same hexdigit string (of length 128) derived from the same character string (of length 64).

Could you please clarify if it is valid to set 'bitwidthPerInputElement' to any value other than 8 and if so, is it expected that the output digest changes for different 'bitwidthPerInputElement' values, although we use the same original string?

Thank you very much!

Hello, I would like to implement a zk-SNARKs scenario using jsnark but I can't figure out if it is indeed possible and how to approach the implementation in practice.

This library seems too technical for me at the moment. I would really appreciate it if there was anyone able to tell me if the following is possible and how to approach the implementation problem in practice, meaning how can I reach a point in which a prover can actually produce a proof file and then a verifier can simply take that file and verify it.

I would like to implement a scenario in which a prover P wants to prove the knowledge of the decrypted version of a file to a verifier V using zk-SNARKs. (The set-up phase to produce the proving and verification keys is done by a trusted third party of course.)

In this scenario there is a file f and its encrypted version is fE = Enc(f, k). Here Enc is a strong symmetric encryption algorithm such as AES and k is the key used to encrypt the file f.

The hash of the file f is Hf = SHA256(f)

In this scenario, I want the prover to be able to prove that:
SHA256(Dec(fE, k)) == Hf AND SHA256(k) == Hk
where obviously Dec( fE, k ) will produce the original file f.

The prover P will send to the verifier V the following elements, and V will be then able to verify the proof:

• the proof itself just produced by P
• the encrypted file fE
• the hash of the file Hf
• the hash of the key Hk

If the verification output is true (the proof is valid) the verifier V will be sure of the following:

• Hf is the hash of a file f and the encrypted version of this file is fE (note that V doesn't have/know the original file f)
• Hk is the hash of the key k used to encrypt the file f to obtain fE

Many thanks to anyone who takes the time to read!

Hi Ahmed @akosba

I was trying to write a verification circuit using SHA256 gadget using an assert operation.
However, assert operation complains that the output wires of SHA256 have negative ids.

When I debugged, I found that the negative ids for the output wires of SHA256 gadget are injected within the 'trimBits' method, which is first invoked at line 158 of SHA256Gadget.java class.

This is because trimBits method returns a VariableWire without an id. Could you please let me know if this is the expected behavior?

Thank you.

I was testing the circuit evaluation, and I am trying to initialize some random number on the prime field by doing this in jsnark/libsnark/src/CircuitReader.cpp:

FieldT a = 10000000000000;

When I do a.print(), I got some garbage value. But when I run it on a real circuit and trying to print out some of the wire values, it actually works. Did I do something wrong?

Hi.Can a prover put her proof that has created using jsnark on blockchain and is there any smart contract auto created by jsnark that can verify these proofs?I mean something like what Zokrates does.

Hi,

In this line: https://github.com/akosba/jsnark/blob/master/JsnarkCircuitBuilder/src/circuit/auxiliary/LongElement.java#L238

a witness wire array is created when multiplying a LongElement with another.

This has the effect of creating several secret input variables, which get put together with the real user-provided secret inputs of the circuit.

Is there a way to perform the multiplication without having these generated variables as secret or even public input ?

Hi akosba,
Is it still correct if I implement another curve in libsnark and use the same .arith and .in file directly as my input? I tried using the MNT4753 for libsnark which is a 768bit-curve but the constraint system doesn't satisfy itself. (assertion in CircuitReader.cpp, some assigned value changes because the field changes) I wonder whether this library can only use a 254-bit curve as its backend now?

But the way I used the implementation from coda, I think the curve has the same api as other curves in libsnark.
https://github.com/CodaProtocol/gpu-groth16-prover-3x

-- Checking for module 'libcrypto'
-- No package 'libcrypto' found
CMake Error at /usr/local/Cellar/cmake/3.12.1/share/cmake/Modules/FindPkgConfig.cmake:436 (message):
A required package was not found

Hi @akosba,

I am using the arithmetic operations on the elliptic curve provided in the ECDHKeyExchange gadget in jsnark, in order to implement a circuit which computes some linear operations on Elgamal encryption in the exponent, carried out in the elliptic curve domain.

Out of the three basic arithmetic operations on elliptic curves (i.e. addition of two points, multiplication of a point by a scalar and negation of a point), ECDHKeyExchange gadget only uses the first two operations. In my circuit, given a positive scalar 'a' (which is a secret input to the circuit) and a point 'P' (which is a public input to the circuit), I need to compute (-a).P inside the circuit (i.e. the result of multiplying 'P' by negated 'a').

Could you please advice what is the recommended way to do this in jsnark? Is it fine to first compute the scalar multiplication a.P and then negate the resulting point? Or, should I first negate the scalar, and then perform scalar multiplication? I followed the first approach, by introducing a 'negateAffinePoint' function as below, because I am not sure how to do it using the latter approach in jsnark. I would appreciate a lot your insight on this.

AffinePoint negateAffinePoint(AffinePoint p){
return new AffinePoint(p.getX(), p.getY().mul(-1));
}

Thank you very much.

Hi Ahmed @akosba

I have studied the RSAEncryptionV1_5_Gadget and I would appreciate if you could please clarify the following two questions.

1. I found in the comments that the gadget assumes a hard coded public exponent of 0x10001. If I want to give public exponent as input to the gadget, where should I change the encryption logic?
   According to my understanding, following is the code snippet that is related with the encryption logic using the public exponent, however, I am not clear why it runs for only 16 iterations for the public exponent of 0x10001.

`LongElement s = paddedMsg;

	for (int i = 0; i < 16; i++) {
		s = s.mul(s);
		s = new LongIntegerModGadget(s, modulus, false).getRemainder();
	}
	s = s.mul(paddedMsg);
	s = new LongIntegerModGadget(s, modulus, true).getRemainder();`

2. RSA key length is given as input to the gadget, shouldn't it have any effect on the public exponent?

Thank you very much.

public void setWireValue(Wire wire, long v) {
	setWireValue(wire, new BigInteger(v + ""));
}

For the above method, I found a trivial issue when I occasionally gave a "negative" v.
In this case, "circuitName.in" will have negative signs shown, and the libsnark interface cannot understand negative signs correctly. The prover will fail to create proof.

A temporary fix is as following:

public void setWireValue(Wire wire, int v) {
	setWireValue(wire, v & 0xffffffffL);
}
	
public void setWireValue (Wire wire, Long v) {
	setWireValue(wire, new BigInteger(Long.toUnsignedString(v)));
}

Hi!

I recently ran into an issue when creating a circuit in which checkNonZero gets called on wires whose values themselves depend on the results of calls to checkNonZero. The jsnark circuit generation and evaulation work without any issues, but when libsnark gets called, it often fails with the error message The constraint system is not satisifed by the value assignment - Terminating.

The strange part is that whether libsnark fails or not seems to depend on the execution order / order of operations in circuit.arith. For instance, in the minimal(-ish) example I've included below, sumPrime.add(cPrime) works just fine while cPrime.add(sumPrime) causes the aforementioned error in libsnark. If I replace calls to checkNonZero with a gadget that simply ORs all bit wires together, I'm also unable to reproduce the libsnark exception.

I think the root cause of this issue is how NonZeroCheckBasicOp is implemented in CircuitReader.cpp. In addNonzeroCheckConstraint and mapValuesToProtoboard, there seems to be an assumption that when the non-checkNonZero circuit inputs are set, all inputs of checkNonZero are present and can be used to compute the value of an auxiliary wire, which ultimately doesn't hold if the inputs of checkNonZero themselves depend on the outputs of other calls to checkNonZero.

Given that NonZeroCheckBasicOp already has 2 output wires and the order of operations is correct inside jsnark, wouldn't it be possible to define the required auxiliary wire as a witness wire, assign its value in NonZeroCheckBasicOp.compute, and then just read in that value in libsnark? If you'd like, I could try to implement this in both jsnark and libsnark and create a pull request for both on your repos 😄

Thank you very much for your work on this project!

Minimal example:

import circuit.eval.CircuitEvaluator;
import circuit.structure.CircuitGenerator;
import circuit.structure.Wire;

public class MinimalExample extends CircuitGenerator {

	public static void main(String[] args) {
		MinimalExample example = new MinimalExample();
		example.generateCircuit();
		example.evalCircuit();
		example.prepFiles();
		example.runLibsnark();
	}

	private Wire a, b, c;

	public MinimalExample() {
		super("MinimalExample");
	}

	@Override
	protected void buildCircuit() {
		a = createInputWire("a");
		b = createInputWire("b");
		c = createInputWire("c");

		Wire aPrime = a.checkNonZero("a nonzero"); // = 0
		Wire bPrime = b.checkNonZero("b nonzero"); // = 0
		Wire sumPlusOne = aPrime.add(bPrime, "sum").add(1, "sum + 1"); // = 1
		Wire sumPrime = sumPlusOne.sub(sumPlusOne.checkNonZero("sum nonzero")); // = 0
		Wire cPrime = c.checkNonZero("c nonzero"); // = 0

		// Works
		// Wire resultPlusOne = sumPrime.add(cPrime, "result").add(1, "result + 1"); // = 1

		// Doesn't work
		Wire resultPlusOne = cPrime.add(sumPrime, "result").add(1, "result + 1"); // = 1

		addOneAssertion(resultPlusOne, "result + 1 == 1");
	}

	@Override
	public void generateSampleInput(CircuitEvaluator evaluator) {
		evaluator.setWireValue(a, 0);
		evaluator.setWireValue(b, 0);
		evaluator.setWireValue(c, 0);
	}
}

Output:

Running Circuit Generator for < MinimalExample >
Circuit Generation Done for < MinimalExample >  
 	 Total Number of Constraints :  9
 	 Total Number of Wires : 19
Running Circuit Evaluator for < MinimalExample >
Circuit Evaluation Done for < MinimalExample >



-----------------------------------RUNNING LIBSNARK -----------------------------------------
Reset time counters for profiling
(enter) Parsing and Evaluating the circuit 	[             ]	(0.0000s x0.99 from start)
(leave) Parsing and Evaluating the circuit 	[0.0001s x1.00]	(0.0001s x1.00 from start)
Translating Constraints ... 
	Constraint translation done
Note: Protoboard Not Satisfied .. 
Assignment of values done .. 
Num constraints: 9
constraint 5 (no annotation) unsatisfied
<a,(1,x)> = 1
<b,(1,x)> = 0
<c,(1,x)> = 1
constraint was:
terms for a:
    1 * 0
    x_1 * 1
    where x_1 (no annotation) was assigned value 1
      i.e. negative of 21888242871839275222246405745257275088548364400416034343698204186575808495616
    x_6 * 1
    where x_6 (no annotation) was assigned value 0
      i.e. negative of 0
    x_9 * 1
    where x_9 (no annotation) was assigned value 0
      i.e. negative of 0
terms for b:
    1 * 0
    x_13 * 1
    where x_13 (no annotation) was assigned value 0
      i.e. negative of 0
terms for c:
    1 * 0
    x_12 * 1
    where x_12 (no annotation) was assigned value 1
      i.e. negative of 21888242871839275222246405745257275088548364400416034343698204186575808495616
The constraint system is  not satisifed by the value assignment - Terminating.

(edit:) The generated circuit file:

total 19
input 0			 # The one-input wire.
const-mul-0 in 1 <0> out 1 <1>
input 2			 # a
input 3			 # b
input 4			 # c
zerop in 1 <2> out 2 <5 6> 		# a nonzero
zerop in 1 <3> out 2 <7 8> 		# b nonzero
add in 2 <6 8> out 1 <9> 		# sum
add in 2 <9 0> out 1 <10> 		# sum + 1
zerop in 1 <10> out 2 <11 12> 		# sum nonzero
const-mul-neg-1 in 1 <12> out 1 <13>
add in 2 <10 13> out 1 <14>
zerop in 1 <4> out 2 <15 16> 		# c nonzero
add in 2 <16 14> out 1 <17> 		# result
add in 2 <17 0> out 1 <18> 		# result + 1
assert in 2 <18 0> out 1 <0> 		# result + 1 == 1

I know that jsnark uses prepFiles() to generate .arith and .in files, but how can verifiers recover the circuit outputs from these two files?
For example, a prover generates a rsa circuit, uses pubkey to encrypt a plaintext and provides two files.
A verifier can easily use runLibsnark() for verification, but how can he get the pubkey value and cipherText from the two files?