Computer-implemented system and method for enabling zero-knowledge proof
The invention relates to efficient zero knowledge verification of composite statements that involve both arithmetic circuit satisfiability and dependent statements about the validity of public keys (key-statement proofs) simultaneously. A method is disclosed for a prover proving to a verifier that a statement is true, while keeping a witness (w) to the statement a secret, and a verifier using a reciprocal method to verify the proof. The prover sends, to the verifier, data including a statement represented by an implemented function circuit, individual wire commitments and/or a batched commitment for the function circuit of the statement, a given function circuit output, and a proving key. Based on the sent data, the verifier is able to determine satisfiability of the function circuit, calculate an elliptic curve point, and validate the statement, thus determining that the prover holds the witness to the statement and ensuring the data complies with the statement.
1. A computer-implemented method for enabling zero-knowledge proof or verification of a statement(S) in which a prover proves to a verifier that a statement is true while keeping a witness (w) to the statement a secret, the method including:
the prover sending to the verifier:
data comprising the statement(S) represented by an arithmetic circuit with m gates and n wires configured to implement a function circuit and determine whether, for a given function circuit output (h) and an elliptic curve point (P), a function circuit input(s) to a wire of the function circuit is equal to a corresponding elliptic curve point multiplier(s), wherein the function circuit is a circuit that implements a hash function;
individual wire commitments and/or a batched commitment for wires of the function circuit;
the given function circuit output (h); and
a proving key (PrK),
which enables the verifier to determine that the function circuit is satisfied, calculate the elliptic curve point (P), and validate the statement, thus determining that the prover holds the witness (w) to the statement, wherein each commitment is encrypted.
2. The computer-implemented method according to claim 1 , wherein the prover sends an individual wire commitment and communicates with the verifier using Sigma (Σ) protocols to prove knowledge of the witness (w).
3. The computer-implemented method according to claim 1 , wherein the prover receives from the verifier a challenge value (x) and responds with an opening.
4. The computer-implemented method according to claim 1 , wherein the prover sends to the verifier a random value (x) for enabling the verifier to determine that the statement is true and calculate the elliptic curve point (P).
5. The computer-implemented method according to claim 4 , wherein the random value (x) is a function of at least one commitment.
6. The computer-implemented method according to claim 4 , wherein the random value (x) is computed by hashing a concatenation of all the individual wire commitments generated and sent to the verifier by the prover.
7. The computer-implemented method according to claim 1 , wherein a commitment W i is:
W i =Com( w i ,r i )
wherein
Com is a commitment to the function circuit,
w i is the wire value,
r i is a random number—different for each wire commitment, and
i is a wire denomination,
such that
Com( w,r )= w×G+r×F
wherein
F and G are elliptic curve points.
8. The computer-implemented method according to claim 7 , wherein an input for a wire l in the arithmetic circuit is:
k 0t =r 1 ×F,
wherein
ko is a key-opening input,
r is a random number, and
F is a point on an elliptic curve.
9. The computer-implemented method according to claim 8 , wherein the verifier confirms that the function circuit is satisfied, and is able to calculate a public key for the wire l via elliptic curve point subtraction:
pk l =Com( w l ,r l )− ko l .
10. The computer-implemented method according to claim 1 , wherein the prover sends a batch of wire commitments and generates random numbers to compute elliptic curve points for each wire to form the proving key (PrK).
11. The computer-implemented method according to claim 10 , wherein the batched commitment for the witness is
Com
(
w
)
=
r
×
F
+
∑
i
=
1
n
-
1
w
i
×
K
i
+
w
n
×
G
wherein
r is a random number generated by the prover,
the prover computes the batched commitment to a vector w of wire values w i (for i=1, . . . , n) where w n is to be key-opened,
K i are computed elliptic curve points,
w i are wire values, where w n is the be key opened, and
F and G are points on an elliptic curve.
12. The method according to claim 11 , wherein an input for a wire n in the arithmetic circuit is:
k
o
n
=
r
×
F
+
∑
i
=
1
n
-
1
w
i
×
K
i
wherein
ko n is a key-opening input,
r is a random number, and
F is a point on an elliptic curve.
13. The computer-implemented method according to claim 12 , wherein the verifier calculates a public key opening of a key-statement wire, via elliptic curve arithmetic:
pk n =Com( w )− ko n .
14. The computer-implemented method according to claim 1 , wherein the prover additionally sends a fully opened commitment to at least one wire.
15. The computer-implemented method according to claim 1 , wherein the method uses Pedersen commitments.
16. The computer-implemented method according to claim 1 , wherein the statement uses only one arithmetic circuit for the function circuit.
17. The computer-implemented method according to claim 1 , wherein the function circuit implements an SHA-256 hash function.
18. A non-transitory computer-readable storage medium comprising computer-executable instructions which, when executed, configure a processor to perform the method of claim 1 .
19. An electronic device comprising:
an interface device;
one or more processor(s) coupled to the interface device; and
a memory coupled to the one or more processor(s), the memory having stored thereon computer executable instructions which, when executed, configure the one or more processor(s) to perform the method of claim 1 .
20. An electronic device as claimed in claim 19 , wherein the electronic device is a node of a blockchain network.