Computer-implemented system and method for enabling zero-knowledge proof

Patent metadata

Field	Value
Publication number	US-11995648-B2
Application number	US-201917040480-A
Country	US
Kind code	B2
Filing date	Mar 18, 2019
Priority date	Mar 23, 2018
Publication date	May 28, 2024
Grant date	May 28, 2024

Abstract

The invention relates to a computer-implemented method for enabling zero-knowledge proof or verification of a statement in which a prover proves to a verifier that a statement is true while keeping a witness to the statement a secret. The method includes the prover sending to the verifier a set of data including a statement, which for a given function circuit output and an elliptic curve point, the function circuit input is equal to the corresponding elliptic curve point multiplier. The data includes individual wire commitments and/or a batched commitment for wires of the circuit, a function circuit output, and a prover key, which enables the verifier to determine that the circuit is satisfied and calculate the elliptic curve point and validate the statement, thus determining that the prover holds the witness to the statement.

First claim

The invention claimed is:

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:
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), a function circuit input to a wire of the function circuit is equal to a corresponding elliptic curve point multiplier, wherein the function circuit implements the function of a hash function;
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;
wherein the method is used by the prover to enable a zero-knowledge contingent transaction for data, such as an encryption key,
and further wherein:
the prover liaises with a verifier to confirm the data to be provided and the data to be received and establishes a communication channel with the verifier,
the prover receives an elliptic curve public key pk B from the verifier, said verifier having generated the elliptic curve public key pk B from a secure random secret key sk B , wherein
pk V =sk V ×G and G is an elliptic curve point,

the prover secures the data to be provided with a locking value i, such that
data= pk V +i×G

and the prover sends, to the verifier, their public key, wherein pk P =i×G, and an output f(i) from the function circuit wherein a function circuit input is the locking value i, wherein the function circuit implements the function of a hash function,
the prover sending the statement (S) proof to the verifier that proves to the verifier that the input to the function circuit is a private key corresponding to pk P ,
thus enabling the verifier to verify the proof and confirm that an address corresponding to pk=pk V +pk P matches an agreed pattern, and thus further determine that knowing the locking value i enables derivation of a full private key for the data (sk B +i), and that the locking value i is the function circuit input to the function circuit i,
the prover receiving from the verifier a transaction Tx 1 , which contains an output that contains the data to be received, which can be accessed by a signature from the prover and the function circuit input, i, and
the prover signs and broadcasts the transaction on a blockchain, where it is mined into a block, enabling the prover to access the data from the output of the transaction Tx 1 by providing a second transaction Tx 2 supplying their signature and the value i to unlock the transaction, which is then revealed on the blockchain,
thus enabling the verifier to identify the locking value i and access the data offered by the prover, wherein
sk=sk B +i,
where pk=sk×G.

2. A computer-implemented method according to claim 1 , wherein the prover sends an individual wire commitment and communicates with the verifier using Σ protocols to prove knowledge of the witness (w).

3. A computer-implemented method according to claim 1 , wherein the prover receives from the verifier a challenge value (x) and responds with an opening.

4. A 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. A computer-implemented method according to claim 4 , wherein the random value (x) is a function of at least one commitment.

6. A computer-implemented method according to claim 4 , wherein the random value (x) is computed by hashing a concatenation of all the commitments generated and sent to the verifier by the prover.

7. A computer-implemented method according to claim 1 , 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.

8. A computer-implemented method according to claim 7 , wherein the input to a wire l in the arithmetic circuit is:
ko=n×F,
wherein
ko is a key-opening input,
r l is a random number, and
F is a point on an elliptic curve.

9. A computer-implemented method according to claim 8 , wherein the verifier confirms that the 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. A 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. A 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:
G is an elliptic curve generator point,
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 to be key-opened, and
F is a point on an elliptic curve.

12. A computer-implemented method according to claim 11 , wherein the input to the wire n in the arithmetic circuit is:

ko
n

=

r
×
F

+

∑

i
=
1

n
-
1

⁢

Assignees

• Nchain Licensing Ag

Inventors

• Trevethan Thomas

Classifications

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• G06F21/6218

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• H04L9/3221 Primary

  interactive zero-knowledge proofs · CPC title

• H04L9/3066

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title

• G06Q20/3829 Primary

  involving key management · CPC title