Computer-implemented system and method for trustless zero-knowledge contingent payment
This 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 method includes sending to the verifier a statement (S) represented by an arithmetic circuit configured to implement a function circuit and determine whether a 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); individual wire commitments and a batched commitment for wires of the circuit; a function circuit output (h); proving key (PrK) to enable the verifier to determine that the circuit is satisfied and calculate the elliptic curve point (P) to validate the statement, determin that the prover holds the witness (w) to the statement.
1 . A computer-implemented method executed by a computing device associated with a seller or prover for enabling a trustless zero-knowledge contingent payment or exchange of reward data from a buyer or verifier in exchange for access data from the seller or prover, wherein the reward data is data associated with a payment, the method including:
receiving from the buyer a buyer public key (pk B ) derived from multiplying a buyer secret key (sk B ) with an elliptic curve generator point (G), wherein the elliptic curve generator point (G) is defined on an elliptic curve and is selected from elliptic curves used in blockchain network cryptographic operations;
generating a seller public key (pk s ) determined from multiplying a seller secret key (i) with the elliptic curve generator point (G), wherein the seller secret key is the access data or is used to secure the access data required by the buyer;
generating a zero-knowledge proof statement using a Sigma protocol with batched wire commitments for an arithmetic circuit representing the zero-knowledge proof statement, wherein the zero-knowledge proof statement uses publicly verifiable elliptic curve parameters with a prover-generated proving key computed from random numbers, which for a function circuit output of an arithmetic circuit representing the zero-knowledge proof statement, and an elliptic curve point, an input of the function circuit is equal to the seller secret key (i), wherein said zero-knowledge proof statement enables the buyer to determine that the arithmetic circuit is satisfied and validate the zero-knowledge proof statement through verification of the batched wire commitments, thus determining that the seller holds the required seller secret key that unlocks the access data;
preparing and sending a data set to the buyer, the data set including the zero-knowledge proof statement and a hash value computed by applying a hash function to the seller secret key (i);
receiving from the buyer a first transaction Tx 1 that contains an output including a hash-locked output script that specifies a hash value computed by applying a hash function to the seller secret key that allocates the reward data to the buyer, which is accessible using the seller secret key (i) as a preimage to the hash value specified in the hash-locked output script;
responsive to observing the first transaction Tx 1 being broadcast on a blockchain, such that the first transaction Tx 1 is mined into a block by distributed blockchain nodes, accessing the reward data from the output of the first transaction Tx 1 ; and
generating, signing and broadcasting a second transaction Tx 2 that includes a digital signature from the seller or prover and the seller secret key (i) in plaintext form as the preimage to satisfy the hash-locked output script to unlock the reward data, wherein the seller secret key (i) is revealed on the blockchain through publicly recorded inclusion of the plaintext seller secret key in an input script of the second transaction Tx 2 that is stored in a subsequent block on the blockchain, thus enabling the buyer to retrieve the seller secret key (i) by reading the input script of the second transaction Tx 2 from the blockchain and to obtain the access data offered by the seller by deriving the access data from the retrieved seller secret key (i).
2 . A computer-implemented method executed by a computing device associated with a buyer or verifier for enabling a trustless zero-knowledge contingent payment or exchange of reward data from a buyer or verifier in exchange for access data from a seller or prover, wherein the reward data is data associated with a payment, the method including:
sending the seller a buyer public key (pk B ) derived from multiplying a buyer secret key (sk B ) with an elliptic curve generator point (G), wherein the elliptic curve generator point (G) is defined on an elliptic curve and is selected from elliptic curves used in blockchain network cryptographic operations;
receiving from the seller a data set, the data set including a zero-knowledge proof statement using a Sigma protocol with batched wire commitments for an arithmetic circuit representing the zero-knowledge proof statement, wherein the zero-knowledge proof statement uses publicly verifiable elliptic curve parameters with a prover-generated proving key computed from random numbers, which for a function circuit output of an arithmetic circuit representing the statement, and an elliptic curve point, an input of the function circuit input is equal to a seller secret key (i), wherein a seller's public key (pk s ) is derived from multiplying the seller secret key (i) with the elliptic curve generator point (G), wherein the seller secret key is the access data or is used to secure the access data, wherein said zero-knowledge proof statement enables the buyer to determine that the arithmetic circuit is satisfied and validate the zero-knowledge proof statement through verification of the batched wire commitments, thus determining that the seller holds the seller secret key (i) required for unlocking the access data;
receiving from the seller the data set including the zero-knowledge proof statement and a hash value computed by applying a hash function to the seller secret key (i);
verifying the zero-knowledge proof statement;
generating, signing and broadcasting a first transaction Tx 1 , which contains an output including a hash-locked output script that specifies a hash value computed by applying a hash function to the seller secret key that allocates the reward data to the buyer in exchange for obtaining the access data, which is accessible using the seller secret key (i) as a preimage to the hash value specified in the hash-locked output script;
monitoring on a blockchain, for an indication that the seller has signed and broadcasted a second transaction that includes a digital signature from the seller or prover and the seller secret key (i) in plaintext form as the preimage to satisfy the hash-locked output script to unlock the reward data from the output of the first transaction, wherein the seller secret key (i) is revealed on the blockchain through publicly recorded inclusion of the plaintext seller secret key in the input script of the second transaction that is stored in a subsequent block on the blockchain;
retrieve the seller secret key (i) by reading the input script of the second transaction from the blockchain; and
obtaining the access data offered by the seller by deriving the access data from the retrieved seller secret key (i).
3 . The computer-implemented method according to claim 1 , wherein the access data to be provided by the seller is a secret key of a vanity address or enables the determination of a secret key of a vanity address.
4 . 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 the corresponding elliptic curve point multiplier (s);
individual wire commitments and/or a batched commitment for wires of the arithmetic circuit;
a function circuit output (h); and
a proving key (PrK),
which enables the verifier to determine that the arithmetic 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.
5 . The computer-implemented method according to claim 4 , wherein the prover sends an individual wire commitment and communicates with the verifier using the sigma protocol to prove knowledge of the witness (W).
6 . The computer-implemented method according to claim 4 , wherein the prover receives from the verifier a challenge value (x) and responds with an opening.
7 . The computer-implemented method according to claim 4 , 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).
8 . The computer-implemented method according to claim 7 , wherein the random value (x) is computed by hashing the concatenation of all the individual wire commitments generated and sent to the verifier by the prover.
9 . The computer-implemented method according to claim 4 , 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 the 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 an input to a wire l in the arithmetic circuit is:
ko
=
r
1
×
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 the wire l via elliptic curve point subtraction:
pk
l
=
Com
(
w
l
,
r
l
)
-
ko
l
.
12 . The computer-implemented method according to claim 4 , 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
-
1
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 a key-opened,
K i are computed elliptic curve points,
F is a point on an elliptic curve, and
G is an elliptic curve generator point.
14 . The computer-implemented method according to claim 13 , wherein an 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 the elliptic curve.
15 . The computer-implemented method according to claim 14 , wherein the verifier calculates a public key opening of the 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 as an input to at least one wire of the function circuit of the arithmetic circuit.
17 . The computer-implemented method according to claim 1 , wherein the function circuit implements a hash function and, preferably, an SHA-256 hash function.
18 . A non-transitory computer-readable storage medium comprising computer-executable instructions that, 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 that, when executed, configure the one or more processor(s) to perform the method of claim 1 .
20 . A node of a blockchain network, a node configured to perform the method of claim 1 .
21 . A blockchain network having the node according to claim 20 .
22 . The computer-implemented method of claim 1 , wherein the distributed blockchain nodes validate the second transaction Tx 2 by executing verification that confirms a hash of the seller secret key (i) supplied in the input script of the second transaction Tx 2 matches the hash value specified in the hash-locked output script of the first transaction Tx 1 .