Computer-implemented system and method for exchange of data
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. The method enables a prover to prove this particular statement in zero-knowledge. More specifically, the invention relates to 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 invention also relates to the reciprocal method employed by a verifier who verifies the proof. The method includes the prover sending to the verifier a statement (S) having 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), the function circuit input (s) to a wire of the function circuit is equal to the corresponding elliptic curve point multiplier(s). The prover also sends individual wire commitments and/or a batched commitment for wires of the circuit, an input for a wire in the arithmetic circuit; and a function circuit output (h). The prover receives from the verifier a challenge value (x) and responding with an opening or additionally sends a proving key (PrK) to the verifier. The statement and the data enables the verifier to determine that the circuit is satisfied and calculate the elliptic curve point (P) and validate the statement, thus determining that the prover holds the witness (W) to the statement.
1. A computer-implemented method for enabling zero-knowledge proof or verification of a statement (S) for enabling exchange of data between a prover and a verifier, wherein the prover has access to first data on a first blockchain, and the verifier has access to second data on a second blockchain, the method including:
the prover generating a key-pair for the second blockchain, sending a public key (P A ) of said pair to the verifier, and retaining a private key (s A ) of said pair;
the prover receiving a verifier's public key (P B ) for the first blockchain, said verifier having generated a key-pair for the first blockchain and retaining a private key (s B ) of said pair;
the prover sending a data set to the verifier, said data set including a zero-knowledge proof statement (S), one or more commitments, an input (P X ) and a function circuit output (h);
the prover creating a first blockchain transaction Tx A that transfers access to the first data to a common public key address (P c ), and broadcasts said transaction on a first blockchain network, said address defined by a sum of the input (P X ) and the verifier's public key (P B )
P C =P B +P x
the prover verifying a second blockchain transaction Tx B , said transaction created and broadcast on a second blockchain network by the verifier after confirming the inclusion of the first blockchain transaction Tx A in the first blockchain, said transaction transferring access to the second data to a prover's public key address (P A ) that is accessible by the prover using:
a valid signature (s A )for the prover's public key address (P A ), and
a function circuit input value (x) that determines the function circuit output (h);
the prover confirming the second blockchain transaction Tx B is included on the second blockchain and accessing the second data by providing their signature (s A ) and the value (x) that is the function circuit input of the function circuit output (h);
thus enabling the verifier to observe the value (x) that is the function circuit input that determines the function circuit output (h) and access the first data by providing a signature using a private key corresponding to the common public key address P c , which is s B +x from the homomorphic properties of elliptic curve point multiplication.
2. The computer-implemented method according to claim 1 , wherein the data exchanged are cryptocurrencies and the first data corresponds to an amount of a first cryptocurrency and/or the second data corresponds to an amount of a second cryptocurrency.
3. The computer-implemented method according to claim 1 , 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:
a 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), the function circuit input (s) to a wire of the function circuit is equal to a corresponding elliptic curve point multiplier (s);
individual wire commitments and/or a batched commitment for wires of the circuit;
a function circuit output (h); and
a proving key (PrK),
which enables the verifier to determine that the circuit is satisfied and calculate the elliptic curve point (P) and validate the statement, thus determining that the prover holds the witness (w) to the statement.
4. The computer-implemented method according to claim 3 , wherein the prover sends an individual wire commitment and communicates with the verifier using Σ protocols to prove knowledge of the witness (w).
5. The computer-implemented method according to claim 3 , wherein the prover
receives from the verifier a challenge value (x) and responds with an opening.
6. The computer-implemented method according to claim 3 , 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).
7. The computer-implemented method according to claim 6 , wherein the random value (x) is a function of at least one commitment.
8. The computer-implemented method according to claim 6 , wherein the random value (x) is computed by hashing a concatenation of all the commitments generated and sent to the verifier by the prover.
9. The computer-implemented method according to claim 3 wherein
the commitment W i is:
W i =Com( w i ,r i )
wherein
Com is the 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.
10. The computer-implemented method according to claim 9 , wherein the input for a wire l in the arithmetic circuit is:
ko=n×F,
wherein
ko is a key-opening input,
n is a random number, and
F is a point on an elliptic curve.
11. The computer-implemented method according to claim 10 , wherein the verifier confirms that the circuit is satisfied, and is able to calculate the public key for a wire l via elliptic curve point subtraction:
pk 1 =Com( w l , r l )− ko l
12. The computer-implemented method according to claim 3 , 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).
13. The computer-implemented method according to claim 12 , wherein the batched commitment for the witness is
Com
(
w
)
=
r
×
F
+
∑
i
=
1
n
w
i
×
K
i
+
w
n
×
G
wherein
r is a random number generated by the prover,
the prover computes the 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 is a point on an elliptic curve.
14. The computer-implemented method according to claim 12 , wherein the input for the wire n in the arithmetic circuit is:
ko
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.
15. The computer-implemented method according to claim 14 , wherein the verifier calculates the public key opening of a key-statement wire, via elliptic curve arithmetic:
pk n =Com( w )− ko n
16. The computer-implemented method according to claim 1 , wherein the prover additionally sends a fully opened commitment to at least one wire of the function circuit.
17. The computer-implemented method according to claim 1 , wherein the method uses Pedersen commitments.
18. The computer-implemented method according to claim 1 , wherein the statement uses only one arithmetic circuit for the function circuit.
19. TheA computer-implemented method according to claim 1 , wherein the function circuit implements a hash function.
20. A non-transitory computer readable storage medium comprising computer-executable instructions that, when executed, configure a processor to perform the method of claim 1 .
21. 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 that, when executed, configure the one or more processor(s) to perform the method of claim 1 .
22. A node of a blockchain network, the node configured to perform the method of claim 1 .
23. A blockchain network having a node according to claim 22 .