Computer-implemented system and method for exchange of data

Abstract

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.

Claims

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.sub.A) of said pair to the verifier, and retaining a private key (s.sub.A) of said pair; the prover receiving a verifier's public key (P.sub.B) for the first blockchain, said verifier having generated a key-pair for the first blockchain and retaining a private key (s.sub.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.sub.X) and a function circuit output (h); the prover creating a first blockchain transaction Tx.sub.Athat transfers access to the first data to a common public key address (P.sub.c), and broadcasts said transaction on a first blockchain network, said address defined by a sum of the input (P.sub.X) and the verifier's public key (P.sub.B)
P.sub.C=P.sub.B+P.sub.x the prover verifying a second blockchain transaction Tx.sub.B, said transaction created and broadcast on a second blockchain network by the verifier after confirming the inclusion of the first blockchain transaction Tx.sub.A in the first blockchain, said transaction transferring access to the second data to a prover's public key address (P.sub.A) that is accessible by the prover using: a valid signature (s.sub.A)for the prover's public key address (P.sub.A), and a function circuit input value (x) that determines the function circuit output (h); the prover confirming the second blockchain transaction Tx.sub.B is included on the second blockchain and accessing the second data by providing their signature (s.sub.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.sub.c, which is s.sub.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.sub.i is:
W.sub.i=Com(w.sub.i,r.sub.i) wherein Com is the commitment to the function circuit, w.sub.i is the wire value, r.sub.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.sub.1=Com(w.sub.l, r.sub.l)−ko.sub.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 \times F + {.Math.}_{i = 1}^{n} w_{i} \times K_{i} + w_{n} \times G$ wherein r is a random number generated by the prover, the prover computes the commitment to a vector w of wire values w.sub.i (for i=1, . . . , n) where w.sub.n is to be key-opened, K.sub.i are computed elliptic curve points, w.sub.i are wire values, where w.sub.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 \times F + {.Math.}_{i = 1}^{n - 1} w_{i} \times K_{i}$ wherein ko.sub.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.sub.n=Com(w)−ko.sub.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.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) A basic system for an interactive zero-knowledge proof has been described above in the technical background section, using FIG. 1a is a schematic of a multiplication gate with left and right wire inputs and one wire output, while FIG. 1b is a schematic of an arithmetic circuit with three gates, three input wires, one output wire and two internal wires.

(2) Aspects of the present invention will be apparent from and elucidated with reference to, the embodiment described herein. An embodiment of the present invention will now be described, by way of example only, and with reference to the accompany drawings, in which:

(3) FIG. 2 is a schematic of a composite circuit for a statement, containing arithmetic circuits for a hash function and an elliptic curve multiplication;

(4) FIG. 3 is an alternative schematic of an arithmetic circuit for the composite statement of FIG. 1, wherein only one arithmetic circuit is required; FIG. 4 is a schematic of an arithmetic circuit having four gates and five wires, wherein a wire has its public key revealed or opened from a wire commitment with a key-opening value;

(5) FIG. 5 is a schematic representation of the data exchanged between a prover and a verifier for the proof of a statement S, said statement having a circuit description and that the first wire has a corresponding public key;

(6) FIG. 6 is an alternative schematic representation of the data exchanged between a prover and a verifier; and

(7) FIG. 7 is a schematic of the checks performed by a verifier to verify the circuit of FIG. 4 is satisfied, that an input wire has the required public key and that a hash of the output wire has the required value.

(8) FIG. 8 is an example of a variety address encoded in a human readable alphanumeric format.

DETAILED DESCRIPTION

Overview

(9) The invention enables an 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. Public key elliptic curve specifications are employed within a homomorphic commitment function to prove circuit satisfiability. This enables the proof of public key statements corresponding to private keys used as circuit inputs and/or outputs in an efficient manner.

(10) The proof size and computational expense of generating proofs for statements involving both circuit satisfiability and elliptic curve key pairs can be substantially reduced. The method herein can be easily incorporated into existing discrete-log based zero-knowledge proof protocols for circuit satisfiability which do not require the use of bilinear pairing-friendly elliptic curves. The method is fully compatible with the Bitcoin secp256k1 standard.

(11) Two applications of the method that relate to fair-exchange transactions between two parties on a blockchain, such as the Bitcoin blockchain, are described. The first involves a zero-knowledge contingent payment for the trust-less sale of an outsourced vanity address, which requires a zero-knowledge proof of the equality of a SHA256 hash preimage and an elliptic curve (e.g. Bitcoin) secret key. The second involves improving security on a cross-chain atomic swap, which requires a proof that a SHA256 hash pre-image is equal to unknown private key (with a supplied public key) multiplied by a supplied nonce.

General Solution

(12) This invention concerns a method to enable the proof a particular class of composite statements that involve relationships with elliptic curve public/private key pairs (based on elliptic curve point multiplications).

(13) Using zkSNARKs to prove statements that involve arbitrary cryptographic elliptic curve key operations is deemed impractical and, therefore, the method uses information on elliptic curve public keys that is extracted directly from the ‘homomorphic hiding’ (or commitment scheme) used in the construction of proofs for generic circuit satisfiability. The particular type of elliptic curve involved in the statement of the method is identical to that used in the circuit commitment scheme.

(14) However, the SNARK method involves pairing operations and therefore requires special bilinear pairing-friendly elliptic curves. This precludes using zk-SNARKs because the elliptic curves used on some blockchains are not compatible with bilinear pairing-friendly elliptic curves.

(15) By way of example, statements relating to Bitcoin public keys use the Bitcoin secp256k1 curve, which is not compatible.

(16) The method of the invention, therefore, is compatible with alternative protocols for proving arithmetic circuit satisfiability that do not rely on pairings and have fewer cryptographic assumptions. Overall, the method of the invention is more efficient than zkSNARKS because fewer computations are required and the proof size is reduced for trustless exchange applications.

(17) By way of example, the schematic of FIG. 2, which represents a composite circuit for ‘Statement 1’ below, contains sub-circuits for both a hash function and elliptic curve multiplication. In FIG. 2 the schematic has three inputs: a secret key ‘s’ having a corresponding paired public key ‘P’ and a value ‘h’ which is a hash of the secret key ‘s’. The schematic contains two arithmetic circuits, wherein the first performs a hash on the secret key while the second performs an elliptic curve multiplication on the secret key. The outputs of the circuits are compared against the inputs.

(18) Note that the internal gates are for illustrative purposes only. The circuit checks that the output of the hash is equal to the elliptic curve (EC) public key. Only the inputs ‘h’, ‘P’ and the output are fully revealed to the verifier. All other values are encrypted.

(19) Statement 1 “Given a hash function (H) output h and an elliptic curve point P (the public key), the pre-image of the hash s (i.e. h=H(s)) is equal to the elliptic curve point multiplier (the private key, i.e. P=s×G, wherein G is the elliptic curve generator point)”

(20) The method enables a prover to prove this particular statement in zero-knowledge. Examples of applications that benefit from such a method are described below in relation to the trust-less exchange of data (e.g. sale of outsourced bitcoin vanity addresses) and an anonymised and secure cross chain atomic swap.

(21) The verification of the truth of statement 1 is determinable, by way of example, using the pseudo-code function below, which takes the inputs ‘h’, ‘P’ and ‘s’ and outputs ‘1’ if the statement is true and ‘0’ otherwise:

(22) TABLE-US-00001 int verify(h,P,s) { if(h == H(s) && P == s x G) { return 1 } else { return 0 } }

(23) Verifying ‘Statement 1’ in zero knowledge i.e. where the prover keeps the value of ‘s’ secret from the verifier with the zkSNARK system would require arithmetic circuits for both the hash function AND the elliptic curve point multiplication, as per FIG. 2.

(24) Although arithmetic circuits for the SHA-256 hash function are widely used and optimised, and typically contain less than 30,000 multiplication gates, there are no known examples of arithmetic circuits for cryptographic elliptic curve point multiplication implemented the literature. Even if such circuits were known they would be impractical because of their size and complexity and contain many more gates.

(25) The method functions with a full arithmetic circuit for the single hash function, as shown in FIG. 2, that has a schematic of an arithmetic circuit for the composite Statement 1 employing a key-statement proof and just one arithmetic circuit for the hash function. The circuit checks that the output of the hash is correct and that the public key is equal to the EC encrypted input (a key-statement proof). The values highlighted in blue i.e. the inputs ‘h’, ‘P’ and outputs ‘1’ are revealed to the verifier, all other values are encrypted.

(26) Using the circuit of FIG. 3 a prover is able to explicitly prove via circuit satisfiability that a secret key ‘s’ hashes to ‘h’, and the corresponding public key ‘P’ of the key pair is equal to ‘sxG’, wherein G is an elliptic curve generator point. The secret key ‘s’ is the pre-image of the hash, or input to the function, and not revealed to the verifier when proving the statement.

(27) It is not be noted that verifying that ‘s×G’ is equal to ‘P’ can be extracted from the circuit proof at negligible extra computational cost by employing the required elliptic curve in a commitment scheme as part of the proof protocol. Such an operation is referred to a ‘key-statement proof’, and uses a commitment opening procedure referred to as a ‘key-opening’.

Technical Effect

(28) Known Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) are an implementation of a general purpose proof system for arithmetic circuit satisfiability. In the SNARK framework, a statement encoded as an arithmetic circuit is converted into a construct called a Quadratic Arithmetic Program (QAP), which consists of a set of polynomial equations. The statement can them be proved by demonstrating the validity of this set of equations at a single point. The main advantage of the SNARK method is that the verifier only needs to perform a few elliptic curve (pairing) operations (taking a few ms) and the proof is very small (288 bytes) and independent of the circuit size.

(29) The very small proof and verification time achieved by the SNARK method comes at the expense of a trusted set-up, non-standard cryptographic assumptions and a much heavier computational burden placed upon the prover. The SNARK method also requires the use of elliptic curve bi-linear pairings. However, the use of computationally feasible bi-linear pairings requires the use of special ‘pairing-friendly’ elliptic curves. This precludes the use of many standard cryptographic elliptic curve parameter sets, including the Bitcoin secp256k1. Statements involving general elliptic curve point-multiplications must then employ explicit circuits (which may be very large).

(30) By way of comparison with the Σ protocol approach to proving SHA circuit satisfiability described in the previous section, with the SNARK (Pinocchio) framework, the proving key would take approximately 10 seconds to generate and be approximately 7 MB in size, and the proof would also take approximately 10 second to generate. The proof size would however be 288 B and only take approximately 5 ms to verify .sup.[Bootle 2016].

(31) Additionally incorporating an explicit elliptic curve multiplication (key-statement) into the circuit, would multiply both the proving key size and proof generation time by at least an order of magnitude.

(32) The invention enables the zero-knowledge proof of statements that involve elliptic curve public-private key relationships simultaneously with general arithmetic circuit satisfiability. This is achieved with negligible computational expense beyond proving satisfiability of the arithmetic circuit, and avoids the requirement of creating explicit arithmetic circuits for elliptic curve point multiplication operations which would increase the computational expense of the proof substantially.

Implementation

(33) The implementation of the invention is described below for both batched and un-batched commitment based zero-knowledge proof systems.

(34) In the examples, two parties are involved in the zero-knowledge proof protocol: the prover (P) and the verifier (V). The purpose of the protocol is for the prover to convince the verifier that a given statement ( custom character ) is true, while keeping information about the witness to the statement secret. The statement consists of an arithmetic circuit () with m gates and n wires, as well as dependent assertions about the elliptic curve public key(s) corresponding to one (or more) of the circuit wire values: pk.sub.l, where the sub-script l is the wire index of the key statement. In addition, the statement may also include assertions about fully opened (public) wire values (i.e. public inputs/outputs of the circuit).

(35) The elliptic curve public key(s) specified in the statement correspond to a target elliptic curve specification (which is defined by the full set of elliptic curve parameters: custom character =(p, a, b, G, n, h)).

(36) In the case of Bitcoin script, these parameters are defined by the specification of secp256k1.sup.[SEC 2010]. This specification includes the base generator point G. In addition to the specifying the base point, the statement must also specify a second point F (where F=f×G and f is an element of custom character .sub.p). The value of f must be provably random (e.g. the Bitcoin genesis block hash), or a ‘nothing up my sleeve’ number, such as the first 256 bits of the binary representation of π because allowing the prover a free choice over f could enable them to generate fake proofs.

(37) Batched and unbatched commitments are described in relation to FIG. 4, which is a representative arithmetic circuit having four gates and five wires. Input wire (w.sub.1) has it's public key revealed, or opened, from the wire commitment W.sub.1 with the ‘key-opening’ value ko.sub.1

Implementation—Individual Wire Commitments

(38) Using FIG. 4 as an example, ‘key openings’ are individual commitments to each wire in the circuit that are created by the prover and sent to the verifier. These key openings follow known Σ protocols for arithmetic circuit satisfiability. FIG. 5 illustrates the data exchanged between the prover and verifier.

(39) Satisfiability is achieved by including a number of steps, as follows: 1. Each wire i (i=1, . . . , n) of the circuit is committed to with a Pedersen commitment:
W.sub.i=Com(w.sub.i,r.sub.i)

(40) Where:
Com(w,r)=w×G+r×F 2. For the circuit wire l that requires a proof of its corresponding public key (a key-statement proof), the prover also sends a key-opening:
ko.sub.l=r.sub.1×F 3. Optionally, if a circuit wire j requires being publically revealed (a fully public wire), the prover sends the full opening tuple:
(w.sub.j, r.sub.j) 4. Each gate of the circuit is then proven satisfied in zero knowledge using the Σ protocols, which involves the prover computing and sending the Σ.sub.zero and Σ.sub.prod commitments (i.e. B or C.sub.1, C.sub.2, C.sub.3 respectively) for each gate, and the verifier replying with a challenge value (x), the prover then sending the opening values (z and e values) and the verifier checking against the commitments. 5. Once the verifier has confirmed that the circuit is satisfied, the verifier then calculates the public key for the wire l via elliptic curve point subtraction:
pk.sub.l=Com(w.sub.l, r.sub.l)−ko.sub.1 6. The verifier then confirms that each pk.sub.l matches the key(s) specified in the statement (and that the fully opened wires match specified values) to complete the validation.

Implementation in Detail—Individual Wire Commitments

(41) Continuing with FIG. 4, an explicit example detailing the individual commitments and validations of the example is provided which describes verifying the satisfiability of a simple arithmetic circuit with both a key-statement proof of one of the wires and a full revealing of another wire.

(42) The circuit custom character as shown in FIG. 4 has 5 wires w.sub.i (i=1, . . . , 5) and 4 gates g.sub.j(j=1, . . . ,4). Gates 1 and 3 are addition gates and gates 2 and 4 are multiplication gates.

(43) The prover and verifier agree on the statement, which includes the circuit, the value of wire 5 and the public key of wire 1, along with the elliptic curve and commitment specification. The statement ( custom character ) the prover wants to prove the truth of to the verifier is:

(44) “I know a satisfying assignment to the circuit custom character (i.e. wire values {w.sub.i}.sub.i=1.sup.5 that satisfy all the gates), where wire 1 has a public key P (i.e. P=w.sub.1×G) and wire 5 has a value h (i.e. w.sub.n=h)”

(45) The values of wires 1 to 4 are not revealed. The prover and verifier then interact as shown in FIG. 6, and as described below: 1. The prover generates 5 random blinding values (r.sub.1, . . . , r.sub.5) and then calculates the 5 wire commitments (W.sub.1, . . . , W.sub.5) and sends these to the verifier. 2. The prover computes the key opening for wire 1: ko.sub.1=r.sub.1×F and sends it to the verifier. 3. The prover sends the full opening information for wire 5 (w.sub.5, r.sub.5) to the verifier. 4. For the addition gates (g.sub.1 and g.sub.3) the prover generates a commitment to zero (with a random nonces r.sub.B1 and r.sub.B3): B.sub.1=Com(0, r.sub.B1) and B.sub.3=COM(0, r.sub.B3) and sends them to the verifier. 5. For the multiplication gates (g.sub.2 and g.sub.4) the prover generates the commitments as follows: For gate 2:
C.sub.12=Com(t.sub.12, t.sub.32),
C.sub.2=Com(t.sub.22, t.sub.52) and
C.sub.3=t.sub.12×W.sub.1+t.sub.42×F

(46) For gate 4:
C.sub.14=Com(t.sub.14, t.sub.34),
C.sub.2=Com(t.sub.24, t.sub.54) and
C.sub.3=t.sub.14×W.sub.3+t.sub.44×F

(47) Where the t.sub.xx values are random blinding nonces. The prover sends these commitments to the verifier. 6. The verifier then generates a random challenge value x, and sends it to the prover. Alternatively, the prover can generate value x by hashing a concatenation of all the commitments, using the Fiat-Shamir heuristic. 7. For the addition gates (g.sub.1 and g.sub.3) the prover computes the following openings and sends them to the verifier:
z.sub.1=x(r.sub.1+r.sub.1−r.sub.2)+r.sub.B1
z.sub.3=x(r.sub.2+r.sub.1−r.sub.4)+r.sub.B3 8. For the multiplication gates (g.sub.2 and g.sub.4) the prover computes the following openings and sends them to the verifier:
e.sub.12=W.sub.1x+t.sub.12
e.sub.22=w.sub.2x+t.sub.22
z.sub.12=r.sub.1x+t.sub.32
z.sub.22=r.sub.2x+t.sub.52
z.sub.32=(r.sub.3−w.sub.1r.sub.2)x+t.sub.42
e.sub.14=w.sub.3x+t.sub.14
e.sub.24=w.sub.4x+t.sub.24
z.sub.14=r.sub.3x+t.sub.34
z.sub.24=r.sub.4x+t.sub.54
z.sub.34=(r.sub.5−w.sub.3r.sub.4)x+t.sub.44 9. Finally, the verifier checks the equalities. If these pass, then the proof is verified.

(48) The verification performed by the verifier is outlined in FIG. 7, wherein the checks in the inner-box verify that the circuit is satisfied, and that the first wire has the required public key and that wire 5 has the required value.

(49) The challenge ‘x’ in FIGS. 5 and 6 provides for an interactive proof, wherein communications are passed back-and-forth between the prover and the verifier.

(50) This interaction can be inconvenient when a zero-knowledge contingent payment (ZKCP) takes place because the seller and buyer might not be available, or on-line, at the same time. Moreover, the buyer (verifier) may wish for a proof to be publically verifiable e.g. it may be part of an advertisement for the digital goods.

(51) In addition, the proofs are only strictly zero-knowledge in the perfect special-honest verifier model: that is, it is assumed the verifier generates a genuine random number as the challenge, and does not choose the challenge value to try and extract information about the witness.

(52) To solve these problems, the Fiat-Shamir heuristic is applied, which replaces the random challenge value ‘x’ with the output of a hash of the commitments made by the prover. In the random oracle model (where the output of a cryptographic hash function is considered truly random), the prover cannot cheat, and the verifier can check the challenge value generated.

(53) The example can be improved, therefore, by using the Fiat-Shamir heuristic to convert an interactive proof system into a non-interactive one, and the prover can generate a proof that can be independently and publically verified, off-line.

(54) More specifically, the challenge value (x) is replaced with a value computed by hashing (with for example SHA-256) the concatenation of all of the commitments generated by the prover (i.e. all of the wire commitments and all of the B and C.sub.1, C.sub.2, C.sub.3 commitments for sum and product gates respectively).

Implementation—Batched Vector Commitments

(55) Compressed proof systems for circuit satisfiability that involve the batching of vector commitments.sup.[Bootle 2016, Groth 2009] use the method described below, wherein the method enables the extraction of key-statement proofs from batched circuit wire commitments.

(56) The full process is not described to avoid repetition, and the steps below focus on the generation of the batched wire commitment and demonstrating it contains a specified public key. In the steps below, a batched commitment is generated as follows, where the wire l is to be supplied with a key opening—n wires are batched together in the vector commitment. 1. The prover generates n−1 random numbers x.sub.1, . . . , x.sub.n-1← custom character .sub.p 2. The prover computes the elliptic curve points K.sub.i=x.sub.i×G (for i=1, . . . , n−1).

(57) These values plus K.sub.n=G form a proving key PrK that is sent to the verifier. 3. The prover generates a random value: r← custom character .sub.p 4. The prover computes the commitment to the vector w of wire values w.sub.i (for i=1, . . . , n) where w.sub.n is to be key-opened:

(58) $Com (w) = r \times F + {.Math.}_{i = 1}^{n} w_{i} \times K_{i} + w_{n} \times G$
and sends it to the verifier. 5. The prover also sends the key opening for the vector commit:

(59) ${ko}_{n} = r \times F + {.Math.}_{i = 1}^{n - 1} w_{i} \times K_{i}$ 6. The verifier calculates the public key opening of the key-statement wire, via elliptic curve arithmetic:
pk.sub.n=Com(w)−ko.sub.n

Invention Overview

(60) The proof of equivalence of a hash pre-image and elliptic curve private key can be utilised in numerous applications. Two applications are described below, which outline the construction of a specific example of a key-statement zero-knowledge proof for utilisation.

(61) The statement custom character below is, for the purposes of the example applications, a more specific version of Statement 1 described above, wherein.

(62) custom character : “Given a SHA-256 hash function (H) with a public output h and a public point P on the secp256k1 elliptic curve, the secret pre-image of the hash, s (i.e. h=H(s)) is equal to the elliptic curve point multiplier (i.e. the corresponding private key, i.e. P=s×G)”

(63) In the examples provided, this statement consists of a single arithmetic circuit for the SHA-256 hash function custom character .sub.SHA256 (with n wires w.sub.i (i=1, . . . , n) and m gates) along with an assertion that the input wire (w.sub.1) is the private key for public point P and that the output wire (w.sub.n) is equal to h. i.e.:

(64) custom character :.sub.SHA256 is satisfied by the wires {w.sub.i}.sub.i=1.sup.n AND w.sub.1×G=P AND w.sub.n

(65) Therefore, to fully verify this statement, the prover must demonstrate to the verifier that they know a satisfying assignment to the SHA256 circuit using the secp256k1 based commitment scheme, and then simply provide the key-opening for wire 1 (ko.sub.1) and the full opening for wire n (w.sub.n, r.sub.n). The verifier does not learn the value of the input wire (w.sub.1), or the values of any of the other wires except for the fully opened output wire w.sub.n.

Application I

(66) Examples of the invention, as described in the implementation sections above, can be applied to a ZKCP for an outsourced bitcoin vanity address, which represents data to be exchanged for a payment, or access to a resource.

(67) Bitcoin addresses are encoded in a human readable alphanumeric format (Base58 encoding) in order to make them easy to publish, copy and transcribe. The use of this format has led to the popularity of so-called vanity addresses, where the key space is brute-force searched in order to find a private key that results an address that contains a desired string (like a name). FIG. 8 shows an example of a vanity address encoded in a human readable alphanumeric format.

(68) Since deriving a vanity address with a significant pattern can be computationally expensive (for example, the address shown above required the generation of approximately 10.sup.13 different public keys before a match was found) it is common for the search to be outsourced, and there are several online marketplaces where vanity addresses are commissioned and sold. This can be done securely using the homomorphic properties of elliptic curve point multiplication .sup.[JoelKatz 2012].

(69) Although outsourcing the generation is secure, the sale of the vanity address is not trustless. Either the buyer gets the required value before the seller gets paid, or the seller gets paid before releasing the required value, or they must both trust an escrow service. The invention can be employed to enable the trustless sale of a vanity address via a ZKCP. The steps taken between the buyer/verifier and the seller/prover are described below. 1. The buyer and seller agree on the required vanity pattern (Str) and the price (a Bitcoin), and establish a communication channel, which does not need to be secure. 2. The buyer generates a secure random secret key sk.sub.B and corresponding elliptic curve public key, wherein the public key pk.sub.B=sk.sub.B×G 3. The buyer sends pk.sub.B to the seller. 4. The seller then performs a search for the required pattern in the Base58 encoded address derived from pk=pk.sub.B+i×G by changing i. 5. When an address with the required pattern is found, the seller saves the value i, signals to the buyer and sends them pk.sub.s=i×G and the SHA256 hash H(i). 6. The seller also provides a proof to the buyer that the pre-image to H(i) is the private key corresponding to pk.sub.s, as described in the examples above. 7. The buyer verifies the proof, and also confirms that the address corresponding to pk=pk.sub.B+pk.sub.s matches the agreed pattern. At this point (by virtue of the proof), the buyer knows that learning the value i will enable them derive the full private key for the vanity address (sk.sub.B+i), and that the particular value i hashes to h=H(i). 8. The buyer then constructs a hash-time-locked contract (HTLC) transaction Tx.sub.1 which contains an output that contains the agreed fee (a). This output can be unlocked in in two ways: i. With a signature from the seller and the hash pre-image, i, at any time. ii. With a signature from the buyer after a specified time, using, for example, the CHECKLOCKTIMEVERIFY (OP_CLTV) script op code, which can be used to prevent an output from being spent until a specified time or block height.

(70) 9. The buyer then signs and broadcasts this transaction to the blockchain, where it is mined into a block.

(71) 10. Once confirmed, the seller can claim the fee in the output of Tx.sub.1 by providing a transaction Tx.sub.2 supplying their signature and the value i to unlock the hash-lock, which is then revealed on the blockchain.

(72) 11. The buyer can calculates the final vanity address private key sk=sk.sub.B+i, where pk=sk×G 12. If the buyer fails to supply the value i before a specified OP_CLTV time, then the seller can provide their signature to re-claim the fee (to prevent the fee being lost due to an un-cooperative buyer).

(73) The transaction is then fully atomic and trustless: the buyer only gets paid if they provide a valid value i which is revealed publically on the blockchain. Due to the splitting of the private key, this value is of no use to anyone else and does not compromise the security of the full private key.

Application II

(74) Examples of the invention, as described in the implementation sections above, can be applied to a private exchange of data between two parties, each having their respective data to be swapped registered on different blockchains.

(75) More specifically, the invention can be applied to a privacy preserving cross-chain atomic swap, which is a trustless fair-exchange protocol that leverages blockchain transaction features—also known as an atomic trade. The protocol is used to trade two different cryptocurrency tokens on two different blockchains without a third party centralised exchange. The word ‘atomic’ in this context refers to the fair exchange property: either the both parties complete their transactions or neither do.

(76) An example of a known basic protocol is executed as per the steps below. To be secure, both of the cryptocurrencies used in the swap must have scripting functionality that enables hashed and time-locked contracts. The swap involves two parties: Alice and Bob. In this example, Alice has 1 Bitcoin and has agreed to trade it for Bob's 100 Litecoins. 1. Alice generates a Litecoin public key P.sub.A which she sends to Bob 2. Bob generates a Bitcoin public key P.sub.B which he sends to Alice 3. Alice generates a secure random number x 4. Alice computes the SHA-256 hash of x: h=H(x) 5. Alice creates a Bitcoin transaction Tx.sub.A which: i. Pays 1 Bitcoin to P.sub.B with a valid signature AND a value that hashes to h ii. OR pays 1 Bitcoin back to Alice after 24 hours. 6. Alice broadcasts the transaction to the Bitcoin network. 7. Once Bob observes Tx.sub.A is confirmed on the Bitcoin blockchain, he creates a Litecoin transaction Tx.sub.B which: i. Pays 100 Litecoin to P.sub.A with a valid signature AND a value that hashes to h ii. OR pays 100 Litecoin back to Bob after 24 hours. 8. Bob broadcasts the transaction to the Litecoin network. 9. Once the transaction has confirmed, Alice can then claim the Litecoin output by providing her signature and the value x. 10. Once Bob observes the value x on the Litecoin blockchain and can then claim the Bitcoin output by providing his signature and the value x.

(77) This example ensures that either both parties get their coins, or neither do. Alice generates the hash value and only she knows the pre-image, but she is required to reveal this pre-image to claim the coins, which then enables Bob to claim his coins. If either party does not follow the protocol to completion, both of them can re-claim their coins after a lock-out period.

(78) One significant disadvantage feature of the known protocol described above is that the transactions on both blockchains are trivially linkable: once confirmed, the unique value x is publically visible on both blockchains, forever. This affects both the fungibility of the coins and the privacy of the transaction.

(79) In order to un-link the two transactions, different keys must be used for the outputs on each chain, but in order for the protocol to be secure and trustless, Bob must be given a proof by Alice that he will learn the information needed to unlock his coin when she reveals her hash pre-image.

(80) By employing the key-statement proof described in the examples above, the hash-locked output on the second blockchain can be converted to a normal pay-to-public-key-hash (P2PKH) output, both disguising the nature of the transaction and breaking any possible link.

(81) Applied to the example above in which Alice has 1 Bitcoin and has agreed to trade it for Bob's 100 Litecoins, the improved process would include the actions below: 2. Alice generates a Litecoin public key P.sub.A (with private key s.sub.A) which she sends to Bob 3. Bob generates a Bitcoin public key P.sub.B (with private key s.sub.B) which he sends to Alice 4. Alice generates a secure random number x← custom character .sub.p 5. Alice computes the SHA-256 hash of x: h=H(x) and a the elliptic curve public key corresponding to x: P.sub.x=x×G 6. Alice securely sends both h and P.sub.x to Bob. 7. Alice also sends a key-statement proof to Bob that the pre-image of h is equal to the private key that generated P.sub.x. 8. Alice creates a Bitcoin transaction Tx.sub.A which: i. Pays 1 Bitcoin to public key P.sub.C=P.sub.B+P.sub.x ii. OR pays 1 Bitcoin back to Alice after 24 hours. 9. Alice broadcasts the transaction to the Bitcoin network. 10. Once Bob observes Tx.sub.A is confirmed on the Bitcoin blockchain, he creates a Litecoin transaction Tx.sub.B which: i. Pays 100 Litecoin to P.sub.A with a valid signature AND a value that SHA-256 hashes to h ii. OR pays 100 Litecoin back to Bob after 24 hours. 11. Bob broadcasts the transaction to the Litecoin network. 12. Once the transaction has confirmed, Alice can then claim the Litecoin output by providing her signature and the value x. 13. Once Bob observes the value x on the Litecoin blockchain and can then claim the Bitcoin output by providing a signature using the private key for P.sub.C, which is S.sub.B+x from the homomorphic properties of elliptic curve point multiplication.

Applications in General

(82) The invention is suited to 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 secret can be processed by a function, such as a hash function, but additionally include cryptographic elliptic curve key operations, for example the validity of statements regarding public keys. In an example above the method of the invention has been used to enable a trustless ZKCP for a vanity address. This can also be applied to, for example: the derivation of a password; the verification of a valid machine-readable document, such as a passport or identify card; or other such confidential transactions.

(83) It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be capable of designing many alternative embodiments without departing from the scope of the invention as defined by the appended claims.

(84) In the claims, any reference signs placed in parentheses shall not be construed as limiting the claims. The word “comprising” and “comprises”, and the like, does not exclude the presence of elements or steps other than those listed in any claim or the specification as a whole. In the present specification, “comprises” means “includes or consists of” and “comprising” means “including or consisting of”.

(85) The singular reference of an element does not exclude the plural reference of such elements and vice-versa. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer.

(86) In a device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

REFERENCES

(87) [Campanelli 2017] Campanelli, Matteo, et al. “Zero-knowledge contingent payments revisited: Attacks and payments for services.” Commun. ACM (2017).

(88) [Maxwell 2016] https://github.com/zcash-backworks/pay-to-sudoku

(89) [Parno 2016] Parno, Bryan, et al. “Pinocchio: Nearly practical verifiable computation.” Security and Privacy (SP), 2013 IEEE Symposium on. IEEE, 2013.

(90) [Libsnark 2016] https://github.com/scipr-lab/libsnark

(91) [Bootle 2015] Bootle, Jonathan, et al. “Efficient zero-knowledge proof systems.” Foundations of Security Analysis and Design VIII. Springer, Cham, 2015. 1-31.

(92) [Groth 2009] Groth, Jens. “Linear Algebra with Sub-linear Zero-Knowledge Arguments.” CRYPTO. Vol. 5677. 2009.

(93) [JoelKatz 2012] https://bitcointalk.org/index.php!topic=81865.msg901491#msg901491

(94) [Bootle 2016] Bootle, Jonathan, et al. “Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2016.

(95) [SEC 2010] Standards for Efficient Cryptography (SEC) (Certicom Research, http://www.secg.org/sec2-v2.pd

(96) A Bitcoin Developer Reference is retrievable from http://bitcoin.org/en/developer-reference.

Computer-implemented system and method for exchange of data

Assignee

Inventors

Cpc classification

Classification Explorer

G06Q20/1235

PHYSICS

Classification Explorer

G06Q20/3829

PHYSICS

Classification Explorer

G06Q30/0215

PHYSICS

Classification Explorer

G06F16/2465

PHYSICS

Classification Explorer

H04L9/0819

ELECTRICITY

Classification Explorer

G06F16/2379

PHYSICS

Classification Explorer

G06Q20/3827

PHYSICS

Classification Explorer

H04L9/3221

ELECTRICITY

Classification Explorer

G06Q20/38215

PHYSICS

Classification Explorer

G06F7/725

PHYSICS

Classification Explorer

G06Q20/401

PHYSICS

Classification Explorer

G06Q40/04

PHYSICS

Classification Explorer

G06Q30/0185

PHYSICS

Classification Explorer

H04L9/50

ELECTRICITY

Classification Explorer

G06F16/2365

PHYSICS

Classification Explorer

G06Q20/389

PHYSICS

Classification Explorer

H04L9/3066

ELECTRICITY

Classification Explorer

G06Q2220/00

PHYSICS

Classification Explorer

H04L9/0869

ELECTRICITY

Classification Explorer

G06Q20/3825

PHYSICS

Classification Explorer

G06F2216/03

PHYSICS

Classification Explorer

G06Q20/0655

PHYSICS

Classification Explorer

H04L9/0637

ELECTRICITY

Classification Explorer

H04L9/008

ELECTRICITY

Classification Explorer

H04L9/3073

ELECTRICITY

International classification