Computer-implemented systems and methods for performing computational tasks across a group operating in a trust-less or dealer-free manner

Abstract

The invention relates to secure determination of a solution (S) to a computational task by a dealer-free threshold signature group. Access to a resource or reward is offered in exchange for the solution. The method enables individuals in said group to work together in a trust-less, or dealer-free manner. To achieve this, individuals generate their own key pair and use their public key to establish with the group an initial shared public key that they can all use, in parallel, to find a solution to the task. Their own private keys remain secret and, therefore, the collaboration is trust¬less, and operates efficiently, because a verified shared public key is created using the initial shared public key that was used when a solution is found and verified. The resource or reward can be secured by the verified shared public key. Because the private keys of each participant were used in the determination of the initial shared public key that lead to the solution then participants must then collaborate to unlock the resource or reward because the corresponding shared private key can only be generated by all participants or a pre-agreed threshold of participants. Efficiency is achievable by using an initial shared public key and calculating with the group a verified shared public key after the solution has been found. The invention enables the task to be trust-less by using the homomorphic properties of elliptic curve cryptography when applying Shamir's secret sharing scheme. The inventive concept resides in the secure, trust-less and efficient way in which a group can collaborate. The invention can be agnostic to the task.

Claims

1. A computer-implemented method for secure determination of a solution (S) to a computational task by a pooled resource or group having a plurality of participants (P), said group operating in a trust-less, or dealer-free, system or manner, the method comprising: establishing or joining a group (P) with n participants (P.sub.l . . . n), wherein n≥2; generating an initial private key share(s.sub.n.sup.0) and initial public key share (pk1) and establishing an initial shared public key (pko) with the group; performing the task and searching for the solution (S) that determines an answer (A.sub.c) to the task using an intermediate private key (r.sub.n.sup.0) and the shared public key (pko) of the group; finding and sharing the solution (S) with the group, or receiving the solution (S) from another participant, thus enabling the group to verify the solution to the task; calculating with the group a verified shared public key (pk.sub.v) using the initial shared public key (pk.sub.o) and the intermediate private key (r.sub.n.sup.0) that provided the solution (S); constructing a verified secret key share (s.sub.v.sup.0) by summing the initial private key (s.sub.o.sup.n) and the intermediate private key (r.sub.n.sup.0) that provided the solution (S); collaborating with all of the other participants, or a threshold number of participants, to construct a verified shared secret key (sk.sub.v) for the verified shared public key (pk.sub.v), using verified secret key shares (sk.sub.v), wherein the verified shared secret key (sk.sub.v) is used as a code to enable the group to operate collectively to unlock or access a resource or stage of a process.

2. A computer-implemented method according to claim 1, further comprising: receiving from a client (C) or participant (P) the task and a client public key (pk.sub.c) derived from a client's secret key (sk.sub.c), wherein the client's public key is used in the determination of the solution to the task.

3. A computer-implemented method according to claim 1, wherein performing the task and searching for the solution (S) includes: using the intermediate private key (r.sub.n.sup.0) to create an intermediate public key (R.sub.n.sup.0) that is added to the initial shared public key (pko) to create a temporary public key (pk.sub.n.sup.R) that is processed to determine whether the intermediate private key (r.sub.n.sup.0) was a solution that determined the answer (A.sub.c) sought; and if the answer (A.sub.c) is not determined, incrementing the value of the intermediate private key (r.sub.n.sup.0) and repeating the process until the solution (S) is determined, and the answer (A.sub.c) is proven.

4. A computer-implemented method according to claim 1, wherein the initial shared public key (pk.sub.o) and the verified shared public key (pk.sub.v) are generated once.

5. A method according to claim 1, wherein the task requires at least one group member to find a solution that, when processed, produces a Cryptocurrency address having a specified pattern.

6. A method according to claim 1, wherein the task requires the determination of a set pattern (A), and said set pattern originates from a third-party or another participant, and wherein the third-party generated a third-party secret key (sk.sub.c) and provides to the group a corresponding third party public key (pk.sub.c), wherein pk.sub.c=sk.sub.c×G, and G is an elliptic curve generator, and receiving the third party public key (pk.sub.c), and determining the set pattern using the third party public key (pk.sub.c) with an incremental variable (i), such that pk=pk.sub.c+i×G when the set pattern is determined, sending to the third-party the incremental variable (i) that enabled determination of the solution, such that the third party can verify the solution using their random secret key (sk.sub.c)
sk=sk.sub.c+i, where pk=sk×G due to the homomorphic properties of elliptic curve point multiplication.

7. A method according to claim 1, wherein the group (P) of n participants generate through a secure multiparty computation (MPC).

8. A method to claim 1, wherein the initial shared public key (pko) is established amongst the group using Shamir's secret sharing scheme.

9. A method according to claim 1, wherein the shared secret key (sk.sub.v, sk.sub.o) is established amongst the group using Shamir's secret sharing scheme, and wherein a trust-less relationship is established between each participant P.sub.i by generating their own random degree t polynomial f.sub.i(x), and then securely sending f.sub.i(j) to each other participant P.sub.j, each participant summing all the received points f.sub.1(i)+f.sub.2(i)+ . . . +f.sub.n(i) to obtain their secret share s.sub.i=f (i), which is the P.sub.i point on the shared polynomial f (x).

10. A method according to claim 1, wherein following creation of the initial private key share (s.sub.n.sup.0) the initial public key share (pk.sub.1) is computed using an elliptic curve generator G, as b.sub.is.sub.n×G, wherein the interpolation coefficient b.sub.i is: $b_i={\Pi }_{j\in U,j\ne i}\frac{i}{j-i},$ and the initial public key shares are then broadcast to all participants and the initial shared public key (pk.sub.o) is then calculated as the sum of any t+1 shares according to: $\mathrm{pk}=\underset{i=1}{\overset{t+1}{.Math.}}{b}_i{s}_i\times G$

11. A method according to claim 1, wherein the task is received from a client (C) or participant (P), said task being to find a private key for a Cryptocurrency address having a specified pattern therein, wherein the intermediate private key (r.sub.n.sup.0) is randomly generated and an intermediate public key (R.sub.n.sup.0) is a multiple of the seed number by (r.sub.n.sup.0) with an elliptic curve generator (G), and the intermediate public key (R.sub.n.sup.0) is added to the shared public key (pko) and processed to produce a Cryptocurrency address.

12. A method according to claim 1, wherein upon all participants having the seed number (r.sub.v.sup.0) that provided the solution (S), calculating the verified shared public key from
pk.sub.v=pk.sub.o+r.sub.v.sup.0×G, and constructing a verified secret key (sk.sub.v) from verified secret key shares of each participant, calculated from,
s.sub.v.sup.n=s.sub.o.sup.n+r.sub.v.sup.0.

13. A method according to claim 1, the method further comprises sharing with the group, periodically, intermediate results that are demonstrable of computational resource applied to the task.

14. A method according to claim 13, wherein the intermediate results correspond to a portion of the answer (A.sub.c) to the task.

15. A method according to claim 13, wherein the intermediate results have a proportional level of difficulty, and one or more participants assess the computational resource applied by a fellow participant based on the frequency and/or difficulty of intermediate results submitted.

16. A computer readable storage medium comprising computer-executable instructions which, when executed, configure a processor to perform the method of claim 1.

17. An electronic device comprising: an interface device; one or more processor(s) coupled to the interface device; 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.

18. A hardware node of a blockchain network, the node configured to perform the method of claim 1.

19. A blockchain network having a hardware node according to claim 18.

20. An electronic device comprising: one or more processor(s); 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.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) These and other 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:

(2) FIG. 1 is an element of a process in which a task is addressed using the system or method of the invention;

(3) FIG. 2 is an address for use on the blockchain having a set human readable pattern “nChain” therein;

(4) FIG. 3 is a table summarising a difficulty level and average time expected to be taken to determine an address with various set patterns using a standard computer processing unit (CPU) using expected at a rate of 1 million keys per second;

(5) FIG. 4 is a flow-chart indicating the steps taken to determine an address for use on the blockchain from an example of a specific secret key;

(6) FIG. 5 is a flow-chart indicating the calculations for deriving a vanity address and encompasses steps performed in FIG. 4;

(7) FIG. 6a is a flow chart indicating how participants initially collaborate to establish a shared public key, while FIG. 6b is a flow chart indicating how the participants determine an address using the calculations shown in FIG. 5;

(8) FIG. 7 illustrates the logic of updating key shares on a secret sharing polynomial; and

(9) FIG. 8 is a schematic diagram illustrates a computing environment in which various embodiments can be implemented.

DETAILED DESCRIPTION

Overview

(10) In this specification a solution to the problem of sharing a computational task in a secure, efficient and dealer-free or trust-less system is described. The method, and system for implementing the method, takes an input and determines an output.

(11) Computational Task Overview

(12) FIG. 1 is the simplest illustration of a system according to the invention, in which an input or requirement is set, and a task must be performed to provide an output.

(13) The input can be the output from an earlier task, or can be set by a third party outsourcing a task. The task, in theory, can be performed by one individual or entity. The invention, however, is concerned with a number of parties, such as individuals or entities, collaborating on the task to generate the output. The output can be used as the input to a subsequent task and, therefore, can be embodied as a code or set of data.

(14) A third party setting the input to a task and receiving the output can do so openly, such that the solution and answer is known to said third party and at least one of the group collaborating on determining the output, or solution.

(15) Alternatively, should a third party client wish to assign the task securely, they can generate a secret key (sk.sub.c) and corresponding public key (pk.sub.c). The client's public key can be provided to the group (G) of participants (P) for use in determining the solution and answer to the task set. The participants use a new public key (determined from a secret key sk.sub.G) in the determination of the solution, which is achieved by adding a group public key (pk.sub.G) to the client public key (pk.sub.c). To be clear, the solution can be determined using the client's public key added to a shared public key generated by the group i.e. pk.sub.c+pk.sub.G..

(16) When the group determine a solution and answer, they collaborate to generate a code that enables the group, for example, to share with the client the secret key (sk.sub.G) that corresponds to the group public key (pk.sub.G) that lead to the determination of the solution.

(17) The client can then add said group secret key (sk.sub.G) to their own secret key (sk.sub.c) to determine the solution. In this manner, only the client knows the secret key that enables the solution to the task.sup.8.

(18) For simplicity, examples below will assume that a third party client (providing a task to a collaboration to solve) trusts the collaboration and does not provide a ‘client’ public key (pk.sub.c) to the group for the encryption of the solution.

(19) Example Computational Task

(20) By way of example, the method, and system for implementing the method, is described using the determination of a vanity address by a dealer-free threshold signature group. This task is represented in FIG. 1 and is explained independently from the secure assignment of the task, and delivery of result, from a third party (or any other process).

(21) The method involves a group of participants who generate a shared public key via a secret sharing scheme without the use of a trusted third party dealer. The method utilises the arithmetic properties of secret sharing polynomials and the homomorphic properties of elliptic curve multiplication to enable parallel determination for vanity address strings.

(22) The method enables the distribution of the computational task, such as determining a vanity address, without any loss of security. A dealer or similar trusted party is not needed. The method can additionally enable an assessment or measurement of the computational resource utilised by each participant on a group task.

(23) FIG. 2 shows an address for use in a cryptocurrency system such as Bitcoin. The address is an identifier that defines a destination for the payment of cryptocurrency tokens. In the Bitcoin protocol, an address is a 160-bit hash of the elliptic curve public key corresponding to a private key generated by the party receiving a payment. Sending cryptocurrency payments to an address instead of a full public key means that the corresponding full public key is not revealed on the blockchain until an output (unspent transaction—UTXO) is spent (i.e. as part of the scriptSig in P2PKH). This offers protection against potential future weaknesses in elliptic curve cryptography that may arise due to the rapid advancement of quantum computing.

(24) Bitcoin addresses are typically converted to an alpha-numeric format using a custom Base58Check encoding scheme, which results in a text string that is 25-34 characters in length. The Base58 encoding scheme is employed to make addresses both compact and human readable: in this format, payment addresses can easily be made available (on a website, for example) for copying or transcribing.

(25) The human-readable text string of FIG. 2 is derived from a random private key in a deterministic way. It is possible, therefore, to perform calculations repeatedly to find a private key that results in particular pre-determined sub-string in the Base58 encoded address. This kind of intensive search is often referred to as a “brute-force” search.

(26) The address of FIG. 2 is known as a “vanity address” and can be used to make addresses more identifiable and less susceptible to fraudulent activity. For example, an address can be determined that starts with a personal or company name, e.g. 1David, or some other pre-determined string. In this case, an address with the term “nChain” has been determined from a private key.

(27) Determining a vanity addresses requires a probabilistic search of the private key space, and therefore significant computational expense, depending on the required sub-string pattern. The computational expense of finding a required sub-string is quantified as the difficulty (D), which is defined as the expected (average) number of random private keys that must be tried (i.e. converted to an address).

(28) FIG. 3 shows a table listing the difficulty of finding addresses beginning with a specific case-sensitive sub-string of different lengths, and the corresponding average search time based on search speed of 1 million keys per second. Even with specialist hardware, such as graphic processing units (GPUs) or application specific integrated circuits (ASICs) the search remains computationally expensive for long strings and parallel searching is faster.

(29) FIG. 4 illustrates the steps taken to establish an address from a private or secret key, said secret key being a 256 bit secure random number, which is the private key (and which must be kept secret).sup.2. The corresponding full public key is then generated via point multiplication on the Secp256k1 elliptic curve (xG), which results in two 256 bit numbers (for the x and y coordinates of the elliptic curve point). These coordinates are concatenated, and prefixed with 0x04, resulting in a 520 bit number. The public key is then hashed with the SHA-256 function to result in a 256-bit number, which is then hashed with the RIPEMD-160 function to result in the160-bit address, prefixed with aversion byte (0x00 for the main Bitcoin network). The address can then be converted into a human readable representation using Base58check encoding. This encoding features a set of 58 alpha-numeric symbols: numbers, upper and lower case letters (the 0, O, I (Uppercase-I) and 1 (Lowercase-L) characters are not used as they can be difficult to distinguish in some fonts). In addition, a 4-byte error checking code is added to the end of the address to automatically detect typographical errors (and prevent funds being sent to unspendable addresses).sup.3.

(30) FIG. 5 shows the actions taken to determine a Base58 encoded addresses containing specific sub-strings (or patterns) that can be determined through a brute-force search of the private key space.sup.1. The pattern (Str) considered is part of the client answer (A.sub.c) being sought. The values used in the calculations used to determine the answer, including the values that enabled the answer to be determined are considered a components of the solution (S). The solution is a private key which, when processed using steps disclosed in FIG. 4, lead to an address (A.sub.c) having the desired string.

(31) In FIG. 5, an answer (A.sub.c) in the form of a blockchain address having a pattern in which the first four characters of the address are to be ‘Coin’, is set. The term ‘Coin’ is the string (str) of characters sought. Following the steps of FIG. 4, a random number representing a secret or private key (sk.sub.0) is generated. A public key (pk.sub.0) is calculated by multiplying the secret key with an elliptic curve generator (G). An encoded address in Base58check is determined from the public key and if the pattern (str) of the address has ‘Coin’ in the first 4 letters then the secret key (sk.sub.0) is the solution. Otherwise, the secret key (sk.sub.0) is incremented by one i.e. +1 bit, and the calculation of another public key established and the process repeated.

(32) This probabilistic generation of the answer (A.sub.c) often requires millions of cycles of the process and the difficulty increases as the length of pattern sought increases, as suggested in FIG. 3. The search is probabilistic because the output of a hash function can be considered random, assuming a random oracle model. The expected number of attempts or cycles required will depend on the complexity of the pattern. A vanity address is as secure (unbreakable) as an address created from any other random key, irrespective of the search complexity.

(33) Although the invention is described herein using a computational task to determine a solution (S), which is the determination of the answer (A.sub.c), in this case a vanity address—the secure and efficient parallelisation of performing such as task is not limited to the determination of vanity addresses for Bitcoin use. The solution can be used to access an asset or resource.

(34) Known Parallel Searching

(35) Performing a task collaboratively, using a pooled resource of a plurality of participants (P) in a group is known from blockchain mining. In a mining pool, a dealer coordinates the participants and establish a private and public key pair. Shares of the private key are then distributed by the dealer to the participants. Further, it is possible for a congresses, or groups of participants, to have their funds collectively secured with a single public key or address. In a mining pool and congress scenario a signature corresponding to the shared public key can be produced via a threshold signature scheme thus enabling the group, and a part thereof, to collectively access funds or rewards.

(36) However, for congresses to be completely trust-less and secure, the shared public key (and corresponding address) must be generated without a trusted third party (‘dealer’).

(37) A dealer-free secret sharing protocol requires significant communication between the participants in multiple rounds. This takes a significant amount of time to complete—typically seconds to minutes, depending on network latency. Further, in a dealer-free secret sharing protocol, a new shared public key would be required each time a participant used their share of the shared public key to attempt to determine a solution to a task. With each attempt at determining a vanity address pattern, a new shared public key is required.

(38) Each time a participant wishes to verify progress or share with the group a status update or a potential solution during a collaborative search on a computational task, such as a vanity address search, then a new dealer-free shared public key is required at each step, which makes the task is completely infeasible. In other words, a task such as a search has a plurality of steps and a group collaborating on the task collectively perform each step, in parallel. To maintain a secure yet trust-less relationship the group are required to collectively generate a new public key at each step of the task. For example, assuming a shared public key generation time of 10 s, to find an address beginning with a pattern of just 4 characters (‘1CoinXXX . . . ’) would take over a year (compared to a few seconds for a single party with an individual private key). It is for this reason that the invention establishes a second shared public key that is based upon an original public key and a solution.

(39) Improved Parallel Searching Generating a Shared Public Key

(40) The invention relates to collaborative working in a trust-less system. Without a dealer the group must establish a mechanism for securely sharing the solution and/or answer to the set task. To achieve this, a dealer-free threshold group is established.

(41) The group has a number (n) of participants (P). Each participant establishes a secret share (s.sub.o.sup.n) of a shared secret, or private, key. The shared secret key can be determined from a threshold (m) number of secret shares (wherein m≤n). The shared secret can be established when it is constructed from a threshold of shares, although it is not necessary to do so.

(42) Before the secret share (s.sub.o.sup.n) of a shared secret key is established, the group agree on a generator and other parameters that define an elliptic curve standard (G). The generator or point is used, as part of elliptic curve point multiplication, to convert secret keys into public keys. In group multi-party calculations (MPC), it is used as part of the process of deriving the shared public key from the individual secret key shares. Said generator can then be used by each participant to establish a secret share (pk.sub.1) of a secret key and a corresponding share of a public key that is used to generate a shared public key (pk.sub.O). The group calculate an initial shared public key (pk.sub.O) using their secret shares. The group can use a secure multiparty computation (MPC) to achieve this.

(43) It is to be noted that the shared secret key does not need to be calculated because it will not be used by the group. Later in the process each participant's share of the shared secret key is used to unlock an asset.

(44) The shared public key (pk.sub.O) can be used to determine a solution/answer and the output sought by the group, which is an asset to be accessed, is placed under the control of a shared group key, and a corresponding address. The shared public key (pk.sub.O) enables the group to collaborate in a completely trust-less way, because the secret, or private, key that is required to access the asset can only be determined (or a signature generated) when a threshold of participants collaborate.

(45) The establishment of each participant's share of the shared secret, and the shared public key uses Shamir's secret sharing scheme (SSSS).sup.4, which employs the fact a polynomial of degree t can fit or match to any set of t+1 points. A polynomial f(x) of degree t is created where the shared secret key is defined as the constant term (a.sub.0=f(0)) and the remaining coefficients are securely generated random numbers. A number n of distinct arbitrary points on the polynomial are the secret shares for each participant. If m=t+1 or more of the participants then combine their points, there is sufficient information to fit (via Lagrange interpolation) the order t polynomial to these points, and a.sub.0=f(0) is revealed as the shared secret. This scheme enables the sharing of a single private key among an arbitrarily large number of parties with any threshold.

(46) Removing a dealer and making the system trust-less can be achieved.sup.5. Rather than a dealer creating the initial polynomial and distributing the secret shares, each participant P.sub.i generates their own random degree t polynomial f.sub.i(x) and then securely sends f.sub.i(j) to each other participant P.sub.j. Each participant P.sub.i then sums all the received points i.e. f.sub.1(i)+f.sub.2(i)+ . . . +f.sub.n(i), to obtain their secret share s.sub.i f(i), which is the P.sub.i point on the shared polynomial f(x).

(47) After the secret shares have been created, the shared public key (pk.sub.O) corresponding to the shared secret key is computed using the elliptic curve generator G). The shared secret key, however, is not known and does not need to be calculated, as will become clear below.

(48) Participants P.sub.i then compute their public key shares as b.sub.is.sub.i×G, where the interpolation coefficient:

(49) $b_i=\underset{j\in U,j\ne i}{.Math.}\frac{i}{j-i}$

(50) These public key shares are then broadcast to all participants and the shared public key (pk.sub.O) is then calculated simply as the sum of any t+1 shares:

(51) ${\mathrm{pk}}_O=\underset{i=1}{\overset{t+1}{.Math.}}{b}_i{s}_i\times G$

(52) Each participant can verify that all the public key shares received are consistent.

(53) When the group collaborate or a threshold number of participants of the group collaborate then a code can be generated, said code being the solution that in these examples is a private key. The collaborative generation of the code enables the group to access or unlock an asset, or function to close a stage in process, such as the completion of a task shown in FIG. 1. The task completed can be one of a plurality of tasks in a process, such as an encryption process.

(54) By way of example, the signature corresponding to an address can be used to unlock funds and those funds can only be unlocked when a threshold of m participants of the group cooperate to either recreate the shared secret key or, more securely, collectively sign a spending transaction using a threshold signature scheme.sup.6.

(55) Improved Parallel Searching—Collaborative Calculation

(56) The determination of a solution by a group of participants in a trust-less manner is described, by way of example, in relation to finding a secret key that, when processed, produces a Bitcoin address. The steps taken to maintain secure and efficient collaboration in a trust-less manner can be applied to any cryptocurrency with an alpha-numeric address format and exponentiation based public key signatures, or any computational process or task.

(57) In line with the example computational task, the invention is illustrated by the determination of a vanity address. Elliptic curve (EC) operations are performed using the parameters defined by the Secp256k1 curve.sup.7, which is employed in Bitcoin. This standard specifies (in addition to the curve parameters) the generator point G and orderp. If not specified otherwise, all operations (including polynomial) are performed over modulop, and all secret keys are 256 bit numbers. All public keys are EC coordinates.

(58) The protocol operates between a group of participants (the ‘threshold group’) and it is assumed that all participants can authenticate each other and communicate via secure channels. This can be achieved using a public key cryptosystem or a Diffie-Hellman key exchange protocol. The purpose of the group will depend on the specific application, and one of these may be in the formation of congresses.

(59) Each participant in the scheme is required to generate secret keys that are derived from cryptographically secure pseudo random number generators (CSPRNG) with an adequate source of entropy.

(60) Establishing the Group

(61) FIG. 6(a) represents the group initially generating a shared polynomial and an associated shared public key, as described above. An optional additional verification step can be performed to ensure the validity of the individual shares.

(62) The group has a number (n) of participants (P.sub.i: P.sub.1, P.sub.2, P.sub.3, . . . , P.sub.n), who establish secure communication channels, and all agree on the threshold (m) and the address pattern Str (a Base58 string). The address pattern is the answer (A.sub.c) being sought.

(63) Each participant (P.sub.i) generates a degree m−1 polynomial with random coefficients: f.sub.i(x). Each participant P.sub.i sends the value of f.sub.i(j) to each other participant (j=1, . . . , n). Each participant then sums all the received values, with their own value of f.sub.i(i)), to obtain their secret share s.sub.0.sup.i=f(i), wherin:

(64) $f\left(i\right)=\underset{j=1}{\overset{n}{.Math.}}{f}_j\left(i\right)$

(65) The corresponding shared public key (pk.sub.0) is then computed and verified by all participants using Lagrange interpolation, as described above.

(66) At this point, each participant now has their initial secret share (s.sub.0.sup.i) and the initial shared public key (pk.sub.0). The shared public key (pk.sub.O) established by the group is used by each participant during the task. The shared key (sk.sub.O) is not calculated and not used. It is important to note, however, that although the shared key is (sk.sub.O) is not calculated, each participants share of the shared secret (s.sub.0.sup.i) and the shared public key is used to determine a solution (S). The process is described below.

(67) Parallel Searching

(68) The task to be performed is shown in FIG. 5 and discussed above. The group then perform a search for the specified pattern in parallel, in the sequence shown in FIG. 6(b).

(69) Each participant P.sub.n generates a random number r.sub.i.sup.0, which is a search seed (to prevent overlap of search space between participants). The random number r.sub.i.sup.0, in this example, is a secret key from which an address is to be derived.

(70) Then, each participant P.sub.i calculates an elliptic curve point number R.sub.i.sup.0 from the search seed according to:
R.sub.i.sup.0=r.sub.n.sup.0×G,

(71) wherein G is an elliptic curve generator and when multiplied by the secret key r.sub.n.sup.0 a temporary public key R.sub.i.sup.0 is established.

(72) The shared public key pk.sub.0 is used to determine a new public key share pk.sub.i.sup.R according to:
pk.sub.i.sup.R=pk.sub.0+R.sub.i.sup.0.

(73) The new public key share pk.sub.i.sup.R is converted to a Base58 address A.sub.i.sup.R, according to
A.sub.i.sup.R=Ad(pk.sub.i.sup.R)

(74) The participant then checks whether the Base58 address A.sub.i.sup.R matches the answer (A.sub.c), i.e. that it contains or begins with the specified pattern Str. In other words, has the random number r.sub.i.sup.0 lead to an address that begins with the pattern sought.

(75) If there is no match, then the random number r.sub.i.sup.0 seed number (the secret key) is incremented e.g. increasing r.sub.i.sup.0 by 1 bit and the process is repeated by calculating another secondary random number R.sub.i.sup.0 (the temporary public key) from the search seed, determining another new public key by adding the original public key and the temporary public key and converting it to a Base58 address and checking whether it matches the specified pattern Str.

(76) If the Base58 address A.sub.i.sup.R contains or matches the specified pattern Str then the participant broadcasts the solution, which is the seed number r.sub.i.sup.0 that enabled the answer to be determined, said seed number or secret key subsequently referred to as the vanity seed number r.sub.v.sup.0.

(77) Once another participant receives a broadcast r.sub.v.sup.0=r.sub.i.sup.0 from another group member, they can verify that the secret key corresponds to an address having the target text string (Str) by multiplying it by the elliptic curve generator (×G) and adding the original shared public key (pk.sub.O).

(78) Using the original shared public key the group then calculates a new shared public key pk.sub.v that corresponds to the vanity address sought according to
pk.sub.v=pk.sub.0+r.sub.v.sup.0×G

(79) The creation of a temporary public key share using a seed number (a secret key), said temporary public key leading to the creation of a new public key when a solution (the secret key that can determine an answer) is found, enables the group to work quickly and efficiently in parallel without the need to generate a new shared public key at each step taken by a participant. Each participant can share their progress with others without limitation and only when a solution is found is a new shared public key established.

(80) Updating the Secret Share

(81) Each participant P.sub.i now has their initial secret share so, shared public key pk.sub.0 and r.sub.i.sup.0, which led to an address containing the desired text string. To update their secret shares, each participant simply adds r.sub.v.sup.0 to the value:
s.sub.v.sup.i=s.sub.0.sup.i+r.sub.v.sup.0

(82) wherein r.sub.v.sup.0 is the secret key that led to the answer.

(83) A threshold (m) of the updated shares s.sub.v.sup.i will then be able to reconstruct the full secret key sk.sub.v corresponding to the new shared public key that corresponds to the vanity address sought, according to
pk.sub.v=pk.sub.0+r.sub.v.sup.0×G,

(84) and by using Shamir's scheme. This arises from the polynomial arithmetic, wherein adding a constant to all secret (non-zero x) points will increase the interpolated zero-point (the secret) by that same constant, as illustrated in FIG. 7.

(85) Although all participants can establish the new shared public key independently, they must work together to create the corresponding private key, or generate a valid digital signature, which is required access or unlock any resource secured by the old or the new shared public key.

(86) Validation

(87) To confirm and validate the new secret shares, the group performs the procedure to generate new shared public key pk.sub.v using their new secret shares (s.sub.v.sup.i) as described above in relation to a corresponding shared public key (pk.sub.0) that was the computed and verified by all participants using Lagrange interpolation, said public key shares having been broadcast to all participants and the shared public key (pk.sub.v) is then calculated simply as the sum of any t+1 shares, according to

(88) ${\mathrm{pk}}_v=\underset{i=1}{\overset{t+1}{.Math.}}{b}_i{s}_i\times G$

(89) Each participant can verify that all the public key shares received are consistent.

(90) Process Overview

(91) Participants form a group and a shared public key (pk.sub.O), which is the ‘original’ shared public key. The original shared public key was established from each participant's share of a corresponding shared secret key and each participant's share of the original shared public key. It is to be noted that a shared secret key is not established, and does not need to be established.

(92) The group are set a task, which may be set by a third party. In exchange for the solution to the task a resource or reward is offered or available. When the solution is found the resource or reward can be secured by a new shared public key, said key being established using the solution. Accessing or unlocking the resource or reward requires the group to collaborate and generate a corresponding new shared private key.

(93) By way of example the task is the determination of a vanity address in exchange for a financial reward. The address sought can be considered as the answer to a task and is a predetermined (by a client) pattern or text-string. The solution is the proof of that task.

(94) Individually, and in parallel, each participant generates a temporary secret key, which functions as a seed, and determines whether that seed leads to the address sought. If not, the seed is incremented and the determination repeated until one of the participants identifies a temporary secret key for an address having the desired text-string.

(95) During the determination, the temporary secret key is converted by each participant to a public key (temporary) for their own use in the determination, which is then added to the original shared public key, the summed public keys are added to make a combined public that is hashed to determine whether the address produced contains the text-string sought.

(96) Using a further public key, temporarily and for their own use, enables the participants to operate independently of the original shared public key thus overcoming the burden of having to create a new shared public key at each step.

(97) When one of the participants identifies a temporary secret key for an address having the desired text-string they share it with the others, who then check that the secret key derived from the further public key is the solution that leads to the address sought.

(98) If the secret key derived from the further public key is the solution then a new shared public key—the validated or ‘vanity’ key—is created by the participants in the same manner as they established the original shared public key.

(99) An asset or reward can be secured by the new shared public key, which can be unlocked by the solution. The asset can be a procedural step and function, for example, to close a stage in process, such as the completion of a task shown in FIG. 1. In this way the group can collaborate to access or unlock an asset, or obtain a reward—they use the solution to do so.

(100) In this example, for the purposes of illustrating the unlocking of an asset, the new shared public key is used to determine a new shared public address for the receipt of a Bitcoin or other cryptocurrency payment.

(101) This payment can only be accessed using the corresponding shared secret or private key. The shared secret key required to unlock an unspent transaction (UTXO) does not exist until all the participants or a threshold number of participants create a shared secret key.

(102) The new shared secret key is created from each participants secret key share, which is a summation of their original secret key shared (used to create the original shared public key) and the secret key (the solution) that determined the address having the desired text-string (which was used to create the new shared public key).

(103) The process is trust-less because the secret shares underlying the original shared public key are not only used to establish the solution (secret key) but are unknown to the other participants. To be clear, at any one time no shared secret key can be established without at least a threshold of shares i.e. m participants' secret shares. This applies to the original shared secret key (not determined in this process) and the new shared secret key, which is based upon the solution.

(104) Initially, the shared public key establishes a reference point for the trust-less collaboration and by using the shared public key as starting point, and generating a new shared public key using the solution, neither the secret shares that created the shared public key nor the secret shares (solution) that provide the new shared private key are known without collaboration.

(105) Inhibiting Abuse in the Collaboration

(106) Trust-less collaborations are susceptible to abuse in the form of free-riding, wherein one or more participants deliberately contribute little or nothing to the determination of the solution of the task and expect to obtain an equal allocation or fair share of the allocated rewards. The reward can be monetary or can be the allocation of a subsequent resource, such as a computing processing resource or energy supply.

(107) In threshold groups that are formed from anonymous participants they are economically incentivised to not perform the search and do not actively participate in the determining a solution to the task, or do not commit commensurate computational resources to the task.

(108) To address this problem, participants are allocated shares of the reward, such allocations being proportional, or at least indicative, of the computational resource applied to the task. The actual number or percentage of allocations each participant receives for the resource they utilise can be established in advance. The mechanism for measuring the resource applied to the task can assess of the difficulty level of the actions taken by each participant in attempting to determine a solution to the task. A measurement, or indication of the resource applied, can provide evidence that a particular participant have performed the task or search at a given rate. Sub-measurements or sub-indications can be used to indicate the difficulty level. A difficulty level can be determined from a partial result, or partial solution to the task.

(109) By way of example, and using the determination of a vanity address, the group of participants can agree on how an allocation, or percentage of the share, is to be determined. If, for example, the answer being sought was a secret key corresponding to an address “1Bitcoin” then it can be agreed that finding a public key share that produces a sub-string of the agreed pattern e.g. “Bitco” is indicative of a certain level of computational resource being applied.

(110) During the parallel search, each participant individually performs the search for an address beginning with “1Bitcoin” and when a participant finds a temporary public key share corresponding to an address with the sub-string pattern, they broadcast the random number, or nonce, r.sub.i.sup.0 that was used to generate said temporary public key share the to the rest of the group. The other participants can verify each received nonce r.sub.i.sup.0: i.e. that the address derived from pk.sub.i.sup.R=pk.sub.0+r.sub.i.sup.0×G matches the sub-string pattern and keep a record of the number of valid nonces r.sub.i.sup.0 received from each other participant P.sub.i.

(111) It is to be noted that the expected frequency of a received valid nonce r.sub.i.sup.0 from each participant P.sub.i will be proportional to their computational (search) effort, and inversely proportional to the difficulty of the sub-string pattern. By way of example, a threshold group of 20 participants searching for an address pattern ‘1Bitcoin’ (difficulty 8.7×10.sup.13) with standard CPUs would be expected to find a solution in a few hours. However, each participant would be expected to produce and broadcast a r.sub.i.sup.0 value matching the sub-string address pattern ‘1Bitco’ (difficulty 2.6×10.sup.8) about every 4 minutes. Any participant not providing valid rti values with approximately this frequency can be penalised by the remainder of the group, for example by charging congress fees or excluding them from the group (by re-performing the dealer-free secret sharing).

(112) Computing Environment

(113) FIG. 8 is a schematic diagram illustrates a computing environment in which various embodiments can be implemented. There is provided an illustrative, simplified block diagram of a computing device 2600 that may be used to practice at least one embodiment of the present disclosure. In various embodiments, the computing device 2600 may be used to implement any of the systems illustrated and described above. For example, the computing device 2600 may be configured for use as a data server, a web server, a portable computing device, a personal computer, or any electronic computing device. As shown in FIG. 8, the computing device 2600 may include one or more processors with one or more levels of cache memory and a memory controller (collectively labelled 2602) that can be configured to communicate with a storage subsystem 2606 that includes main memory 2608 and persistent storage 2610. The main memory 2608 can include dynamic random-access memory (DRAM) 2618 and read-only memory (ROM) 2620 as shown. The storage subsystem 2606 and the cache memory 2602 and may be used for storage of information, such as details associated with transactions and blocks as described in the present disclosure. The processor(s) 2602 may be utilized to provide the steps or functionality of any embodiment as described in the present disclosure.

(114) The processor(s) 2602 can also communicate with one or more user interface input devices 2612, one or more user interface output devices 2614, and a network interface subsystem 2616.

(115) A bus subsystem 2604 may provide a mechanism for enabling the various components and subsystems of computing device 2600 to communicate with each other as intended. Although the bus subsystem 2604 is shown schematically as a single bus, alternative embodiments of the bus subsystem may utilize multiple busses.

(116) The network interface subsystem 2616 may provide an interface to other computing devices and networks. The network interface subsystem 2616 may serve as an interface for receiving data from, and transmitting data to, other systems from the computing device 2600. For example, the network interface subsystem 2616 may enable a data technician to connect the device to a network such that the data technician may be able to transmit data to the device and receive data from the device while in a remote location, such as a data centre.

(117) The user interface input devices 2612 may include one or more user input devices such as a keyboard; pointing devices such as an integrated mouse, trackball, touchpad, or graphics tablet; a scanner; a barcode scanner; a touch screen incorporated into the display; audio input devices such as voice recognition systems, microphones; and other types of input devices. In general, use of the term “input device” is intended to include all possible types of devices and mechanisms for inputting information to the computing device 2600.

(118) The one or more user interface output devices 2614 may include a display subsystem, a printer, or non-visual displays such as audio output devices, etc. The display subsystem may be a cathode ray tube (CRT), a flat-panel device such as a liquid crystal display (LCD), light emitting diode (LED) display, or a projection or other display device. In general, use of the term “output device” is intended to include all possible types of devices and mechanisms for outputting information from the computing device 2600. The one or more user interface output devices 2614 may be used, for example, to present user interfaces to facilitate user interaction with applications performing processes described and variations therein, when such interaction may be appropriate.

(119) The storage subsystem 2606 may provide a computer-readable storage medium for storing the basic programming and data constructs that may provide the functionality of at least one embodiment of the present disclosure. The applications (programs, code modules, instructions), when executed by one or more processors, may provide the functionality of one or more embodiments of the present disclosure, and may be stored in the storage subsystem 2606. These application modules or instructions may be executed by the one or more processors 2602. The storage subsystem 2606 may additionally provide a repository for storing data used in accordance with the present disclosure. For example, the main memory 2608 and cache memory 2602 can provide volatile storage for program and data. The persistent storage 2610 can provide persistent (non-volatile) storage for program and data and may include flash memory, one or more solid state drives, one or more magnetic hard disk drives, one or more floppy disk drives with associated removable media, one or more optical drives (e.g. CD-ROM or DVD or Blue-Ray) drive with associated removable media, and other like storage media. Such program and data can include programs for carrying out the steps of one or more embodiments as described in the present disclosure as well as data associated with transactions and blocks as described in the present disclosure.

(120) The computing device 2600 may be of various types, including a portable computer device, tablet computer, a workstation, or any other device described below. Additionally, the computing device 2600 may include another device that may be connected to the computing device 2600 through one or more ports (e.g., USB, a headphone jack, Lightning connector, etc.). The device that may be connected to the computing device 2600 may include a plurality of ports configured to accept fibre-optic connectors. Accordingly, this device may be configured to convert optical signals to electrical signals that may be transmitted through the port connecting the device to the computing device 2600 for processing. Due to the ever-changing nature of computers and networks, the description of the computing device 2600 depicted in FIG. 8 is intended only as a specific example for purposes of illustrating the preferred embodiment of the device. Many other configurations having more or fewer components than the system depicted in FIG. 8 are possible.

SUMMARY

(121) Today's blockchain relies heavily on computational effort, whether for mining or the determination of a vanity address. It can be advantageous to distribute the computational tasks across a group to make use of their collective computational processing power.

(122) The solution described in this specification uses the determination of a vanity address to demonstrate improved secure collaboration techniques that enable more efficient collaboration in a trust-less or dealer-free system.

(123) It is to be noted that although a vanity address is, theoretically, as secure as any other address, the use of a distinctive address makes it harder for fraudsters to provide substitute addresses that could deceive and lead to a payment being made in to a different account. By presenting machine readable code in a user-friendly human-readable format, or pattern, minimises this risk. Each character in a vanity address is selectable from 58 different characters. The frequency of the pattern “1n” in an address is 1 in 58. Each additional character decreases the frequency by a factor of 58 (1 in 3364). Replicating a vanity address gets more difficult, by a factor of 58, for each new character added to the string thus making longer addresses more secure.

(124) Collaborating in a dealer-free pool according to the invention enables the pool to operate together securely and efficiently—in a completely parallel way—enabling rapid solutions without relying on a third party and without any loss of security.

(125) Dealer-free generation of a shared public key only needs to be performed once, and each participant can independently search for a satisfying vanity address. Once found, the individual key shares of the group participants are updated to correspond to the full shared address.

(126) Abuse, or free-riding is also inhibited by a regular secure and trust-less means of sharing progress, or resource applied, on the computational task

(127) It should also be noted that the above-mentioned embodiments and examples 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. 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”. 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. 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

(128) 1. [Vanitygen 2016]https://en.bitcoin.it/wiki/Vanitygen 2. [Addr 2016]https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses 3. [Base58 2016]https://en.bitcoin.it/wiki/Base58Check_encoding 4. [Shamir 1979]Shamir, Adi. “How to share a secret.” Communications of the ACM 22.11 (1979): 612-613. 5. [Nojourmian 2013]Nojoumian, Mehrdad, and Douglas R. Stinson. “On dealer-free dynamic threshold schemes.” Adv. in Math. of Comm. 7.1 (2013): 39-56 6. [Goldfeder 2015]Goldfeder, Steven, et al. “Securing Bitcoin wallets via a new DSA/ECDSA threshold signature scheme.” 7. [SEC 2010]Standards for Efficient Cryptography (SEC)—Certicom Research, https://www.secg.org/sec2-v2.pd 8. [JoelKatz 2012]https://bitcointalk.org/index.php?topic=81865.msg901491 #msg901491

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