SYSTEMS AND METHODS FOR MINING ON A PROOF-OF-WORK BLOCKCHAIN NETWORK

Abstract

Embodiments of the present disclosure provides protocols, methods and systems which provides advantages such as the resistance of centralisation of mining on a blockchain network, preferably a Proof-of-Work blockchain. A method in accordance with an embodiment may comprise generating a plurality of non-parallelisable challenges (or “puzzles”) and allocating one of said plurality of challenges to each miner on the network. The miner uses an inherently sequential (non-parallelisable) algorithm to find a solution to his allocated challenge. The challenges are generated by a committee of nodes, and a new set of challenges is generated for each block.

Claims

1. A computer-implemented method, comprising: generating a plurality of multiparty computational challenges; and providing each mining node in a plurality of mining nodes on a Proof-of-Work blockchain network with a respective challenge from the plurality of multiparty computational challenges.

2. The method gf claim 1 wherein: each challenge in the plurality of multiparty computational challenges requires use of an inherently sequential algorithm to find a solution to the challenge.

3. The method of claim 1, further comprising the step of: generating a plurality of further multiparty computational challenges; and providing each mining node in the plurality of mining nodes with a respective further challenge from the plurality of further multiparty computational challenges.

4. The method of claim 3, wherein the steps of claim 3 are performed when a solution has been found, by one of the mining nodes in the plurality of mining nodes, to a multiparty computational challenge or a further multiparty computational challenge.

5. The method of claim 1, wherein: generation of the plurality of multiparty computational challenges and/or the plurality of further multiparty computational challenges is performed, at least in part, by a subset of computer-based entities which is selected from a plurality of computer-based entities.

6. The method of claim 5 wherein at least one of the computer-based entities is a mining node on the blockchain network.

7. The method of claim 5, wherein the subset of computer-based entities is selected from the plurality of computer-based entities according to a random or pseudo-random selection process.

8. The method of claim 1, wherein: the generation of at least one of the plurality of multiparty computational challenges and/or further multiparty computational challenges comprises calculation of an output to an operation which uses a random or pseudo-random input.

9. The method of claim 1, wherein: the generation of at least one of the plurality of multiparty computational challenges and/or further multiparty computational challenges comprises the generation of an RSA key pair.

10. The method of claim 1, further comprising the step of using an inherently sequential algorithm to find a solution to at least one of the plurality of multiparty computational challenges and/or further multiparty computational challenges.

11. The method of claim 10, wherein the inherently sequential algorithm comprises at least one of the following operations: a recursive operation; a modular exponentiation; and a repeated squaring operation.

12. The method of claim 1, wherein: the challenge comprises calculation of an RSA modulus; and preferably wherein the RSA modulus is used in a repeated squaring time-lock puzzle.

13. A computer-implemented system comprising: a processor; and memory including executable instructions that, as a result of execution by the processor, causes the system to perform the steps of: generating a plurality of multiparty computational challenges; and providing each mining node in a plurality of mining nodes on a Proof-of-Work blockchain network with a respective challenge from the plurality of multiparty computational challenges.

14. The computer implemented system of claim 13, wherein the system comprises a plurality of nodes on a blockchain network, at least one of the nodes comprising the processor, memory and executable instructions of claim 13.

15. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to perform the steps of: generating a plurality of multiparty computational challenges; and providing each mining node in a plurality of mining nodes on a Proof-of-Work blockchain network with a respective challenge from the plurality of multiparty computational challenges.

16. The computer-implemented system of claim 13, wherein: each challenge in the plurality of multiparty computational challenges requires use of an inherently sequential algorithm to find a solution to the challenge.

17. The computer-implemented system of claim 13, wherein the executable instructions, as a result of execution by the processor, causes the system to perform the steps of: generating a plurality of further multiparty computational challenges; and providing each mining node in the plurality of mining nodes with a respective further challenge from the plurality of further multiparty computational challenges.

18. The computer-implemented system of claim 13, wherein the steps of claim 13 are performed when a solution has been found, by one of the mining nodes in the plurality of mining nodes, to a multiparty computational challenge or a further multiparty computational challenge.

19. The non-transitory computer-readable storage medium of claim 15, wherein: each challenge in the plurality of multiparty computational challenges requires use of an inherently sequential algorithm to find a solution to the challenge.

20. The non-transitory computer-readable storage medium of claim 19, wherein the executable instructions, as a result of being executed by the processor of the computer system, cause the computer system to perform the steps of: generating a plurality of further multiparty computational challenges; and providing each mining node in the plurality of mining nodes with a respective further challenge from the plurality of further multiparty computational challenges.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0025] FIG. 1 is a flowchart illustrating an embodiment of the present disclosure.

[0026] FIG. 2 is a schematic diagram illustrates a computing environment in which various embodiments can be implemented.

DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

[0027] Embodiments of the present disclosure utilize a mining puzzle which comprises a ‘trap-door’ computation with the following characteristics: [0028] 1. Can be performed quickly, if some secret information is known; [0029] 2. Requires a configurable time to perform, if the solver does not know some secret information.

[0030] As disclosed in Rivest, Ronald L., Adi Shamir, and David A. Wagner “Time-lock puzzles and timed-release crypto” (1996)—herein after “Rivest et al—the ‘trap door’ could be knowledge of an RSA private key, or at least the ability to compute two independent values using the private key.

[0031] In accordance with one or more preferred embodiments of the present disclosure we generate a new puzzle for each miner and for each block, via a multi-party computation (MPC) between a committee of agents (nodes). In some embodiments, the committee comprises a subset of eligible miners which is selected in a random or pseudo-random fashion from the plurality of mining nodes on the blockchain network. Shares in the randomly generated RSA modulus are held by committee members such that the secret keys corresponding to the puzzles for a given block is not known to anyone (until the block is confirmed). In one or more embodiments, the committee and/or secret keys change after each block.

[0032] This is illustrated in FIG. 1, in which a committee of trusted, independent nodes (eg miners) is selected at step 1. At step 2, each node in the committee generates a non-parallelisable computational challenge. This challenge has to be solved using a non-parallelisable, inherently sequential algorithm. At step 3, each miner receives a challenge. Thus, the miners seek to find a solution to their own problem, which they do at step 4. When a miner has found a solution to their challenge, the cycle repeats for each block that is mined into the blockchain.

[0033] Components of an arrangement in accordance with the present disclosure comprise: [0034] 1. a committee of independent miners (See Gilad, Yossi, et al. “Algorand: Scaling byzantine agreements for croptocurrencies” Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 2017) [0035] 2. Multiparty primes computation (See Algesheimer, Joy, Camenisch, Jan and Shoup, Victor, Efficient Computation Modulo a Shared Secret with Application to the Generation of Shared Safe-Prime Products [Online]; and Boneh, Dan, and Matthew Franklin, “Efficient generation of shared RSA keys” Annual International Cryptology Conference, Springer, Berlin, Heidelberg, 1997) [0036] 3. Hash functions as pseudorandom number generators [0037] 4. Time-lock puzzles based on repeated squaring (See Rivest et al) [0038] 5. MPC to verify solutions block (See Algesheimer, Joy, Camenisch, Jan and Shoup, Victor “Efficient Computation Modulo a Shared Secret with Application to the Generation of Shared Safe-Prime Products” [Online])

[0039] Mining Algorithms

[0040] Any mining algorithm, non-parallelisable or otherwise, fundamentally must adhere to the following properties if it is to be used to achieve consensus on the state of a blockchain: [0041] Property 1: The process of completing the mining algorithm, by generating a valid proof of computation C, must take a sufficiently long time. [0042] Property 2: Given a candidate proof of computation C, it must be possible to verify that C is a valid proof of computation in a much shorter time than taken to generate a valid C.

[0043] In general, there are two broad ways in which we can have a mining algorithm achieve the paradigm defined by these properties: by using a trap-door mining function, or by using time-based constraints that observes both above properties.

[0044] Trap-Door Mining Function

[0045] In general, a good one-way trap-door function will be difficult to compute but will be easy to verify when presented with some additional information and can therefore be mapped to a mining process that has both properties one and two.

[0046] For example, in the Rabin Cryptosystem a public key n=p.Math.q is generated from a private key (p, q) where p, q are both primes. Calculating a signature (S, U) on a message m is a one-way function whose solution is a value S which satisfies the equation

[00001]$H\left(m.Math..Math.U\right)=S^2\mathrm{mod}n.$

[0047] The algorithm for finding a valid Sis a trap-door algorithm or function because it is difficult to find S given (n, m, U), but is easy if the factorisation of n is known. The important point here is that, before knowledge of the trap door, mining should be hard and thus take a period of time sufficiently larger than network messaging latency. However, once the solution is found the trap door can be published or jointly computed enabling fast verification the solution using that trap door. Herein, a trap-door mining function known as a time-lock puzzle is used to construct a consensus algorithm for non-parallelisable mining on a blockchain network

[0048] Time Lock Puzzles

[0049] Time-lock puzzles are problems that take a predetermined time to complete. We call an algorithm F.sub.h a time-lock puzzle if for some given input parameters a, t such that

[00002]$F_h\left(a,t\right)=L,$

[0050] there exists another algorithm F.sub.e with O(F.sub.e)<<O(F.sub.h) such that

[00003]$F_e\left(a,t,s\right)=L$

[0051] if and only if s is known. Moreover, the ability to accurately control the time taken for a computer to complete the algorithm though the input parameters requires F.sub.h be a function that is inherently sequential so that the task cannot be shared between machines.

[0052] Repeated Squaring as an Inherently Sequential Algorithm

[0053] The core problem is to compute a.sup.2.sup.t mod n for specified values of a, t and n. In this paper we consider the problem when n is the product of two large primes, and t is chosen to set the desired level of difficulty of the puzzle. a is chosen to be a random and can be player specific. The most efficient way of solving the puzzle is by performing t successive squarings modulo n, beginning with the value a. That is, perform the following algorithm:

TABLE-US-00001 Algorithm 1 For i from 0 to t − 1 compute   W(0) = a  W(i + 1) = W(i).sup.2 mod n

[0054] to yield W(t). There is no known way to perform this computation in a more efficient way without knowing the factorization of n.

[0055] RSA Repeated Squaring Time-Lock Puzzle

[0056] Rivest et al introduced a time-lock puzzle based on repeated squaring. Consider a scenario in which Alice creates a puzzle for Bob to solve [0057] 1. Alice generates a composite modulus

[00004]$n=pq$ [0058] Where p, q are prime. She keeps ret. [0059] 2. Alice computes a second modulus

[00005]$\varphi \left(n\right)=\left(p-1\right)\left(q-1\right)$ [0060] which is kept secret. [0061] 3. Alice selects puzzle computational time, T, and computes

[00006]$t=TS$ [0062] where S is the squaring rate (measure of computational speed) for Bob. [0063] 4. Alice picks random base, a, and computes {circumflex over (L)}:=F.sub.e(a, t, ϕ(n)) efficiently by using the following algorithm

[00007]$\begin{array}{cc}e=2^t\mathrm{mod}\varphi \left(n\right)& a.\end{array}$$\begin{array}{cc}\hat{L}=a^e\mathrm{mod}n& b.\end{array}$ [0064] where ϕ(n) is the trap-door function. [0065] 5. Alice sends the time-lock puzzle (a, t, n) to Bob and asks him to find L=F.sub.h(a, t), where

[00008]$L=a^{2^t}\mathrm{mod}n$

[0066] It can be shown by using Fermat's test that {circumflex over (L)}=L. The fastest known way of computing L without knowing (p, q) and ϕ(n) is to use Algorithm 1. Step 4a, however, significantly increases efficiency of computing the puzzle solution. The time-complexity of F.sub.e(a, t, ϕ(n)) is O(log (t)) whilst F.sub.h(a, t) has complexity O(t).

[0067] Repeated squaring is considered an ‘inherently sequential’ process, meaning that there is no obvious way of parallelising it to any large degree—see Rivest et al. Therefore, having many computers solving the puzzle gains no advantage over having one and the variation in computational time is related to the speed of single computers, which can be much more easily gauged by the puzzle creator. In other words, the puzzle sent by Alice has a solution time that is controllable independent of Bob's computational resources.

[0068] Prime Factorisation Difficulty

[0069] An important assumption in the implementation of the time-lock puzzle is that finding the prime factorisation of n is a hard problem that cannot be solved faster than the puzzle itself. To justify this assumption, consider the following reasoning. The best algorithm for solving the integer factorisation problem, the general number field sieve (NFS) has time complexity O(exp{c(ln n).sup.1/3(ln ln n).sup.2/3}) (c≈2.77). (See Buchmann, Johannes, Jiirgen Loho, and Jorg Zayer. “An implementation of the general number field sieve.” Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1993).

[0070] A 256-bit RSA key for example can be factorised in approximately O(exp(46.6))=2.5×10E20 operations. Assuming that each operation in NFS is equivalent to 1 floating point operation, cracking 256-bit keys still takes approximately 250,000 seconds for a 1 petaFLOPS (floating point operations per second) computer.

[0071] Within the context of a regularly updated blockchain, we require a different RSA modulus to be created every new block. Therefore, we only require that finding the prime factorisation of n be infeasible in the same amount of time as the block generation time (a few minutes for example). By setting the RSA keys to 512-bits it can be safely assumed that factorisation of the RSA moduli within the mining cycle is infeasible.

[0072] Verifiable Random Functions

[0073] A verifiable random function (VRF) is a triple of algorithms (See https://medium.com/algorand/algorand-releases-first-open-source-code-of-verifiable-random-function-93c2960abd61): [0074] Keygen(r).fwdarw.(VK, SK)—On a random input seed r the key generation algorithm produces a verification key VK and a secret key SK pair [0075] Evaluate(SK, m).fwdarw.(Y, ρ)—The evaluation algorithm takes as input the secret key SK, a message m and produces a pseudorandom output string Y and a proof ρ [0076] Verify(VK, m, Y, ρ).fwdarw.0/1—The verification algorithm takes as input the verification key VK, the message m, the output Y and the proof ρ. It outputs 1 if and only if it verifies that Y is the output produced by the evaluation algorithm on inputs SK and m.

[0077] Importantly, the output Y is unique, meaning that it is impossible to find unless the secret key is known. Below, we provide a detailed implementation of subcommittee selection using verifiable random functions.

[0078] Unique and Secure Subcommittee Selection

[0079] In accordance with some embodiments of the disclosure, the subcommittee selection uses an ECDSA signature to replicate the verifiable random function. The process can be categorised into 3 stages: setup, pseudorandom value creation and subcommittee selection.

[0080] Consider a network of miners M.sub.1, . . . , M.sub.N (N>3).

[0081] Setup

[0082] Step 1: Miners have public keys PK.sub.1, PK.sub.2, . . . , PK.sub.N respectively

[0083] Step 2: Miners choose unique seeds S.sub.1, . . . , S.sub.N. These values are propagated and are fixed for each public key

[0084] Pseudorandom Value Creation

[0085] Step 3: for each new block the miner creates a message. The message is simply the hash of miner's seed value concatenated with the previous block header. That is for miner PK.sub.i mining block B.sub.k his unique message is

[00009]$m_{i,k}=H\left(S_i.Math..Math.X_{k-1}\right)$

[0086] where X.sub.k-1 is the hash of the previous block header X.sub.k-1=H(BH.sub.k-1)

[0087] Step 4: Miners produce ECDSA signatures on their messages that is

[00010]$\mathrm{ECDSA}\left(s{k}_i,m_{i,k}\right).fwdarw.\left(s_i,r_i\right)$ [0088] The miner records the time elapsed between at when the timestamp for block B.sub.k-1 and when signature was generated. The difference is denoted T.sub.i.sup.e

[0089] Step 5: Each Miner M.sub.i propagates his proof (PK.sub.i, m.sub.i,k, s.sub.i, r.sub.i, T.sub.i.sup.e)

[0090] Subcommittee Selection

[0091] Step 6: On receiving the proof each network node checks the following [0092] 1) The message m.sub.i,k is valid for miner PK.sub.i [0093] 2) The signature (s.sub.i, r.sub.i) for message m.sub.i is valid against PK.sub.i [0094] 3) The difference between T.sub.i.sup.e and the time the proof message was received is less than the network latency, T.sub.L. i.e. when a message is received miner j checks

[00011]$T_L<T_{Recieved}^j-\left(T_i^e+T_B\right)$ [0095] Where T.sub.B is the timestamp for the most recent block and T.sub.Received.sup.j is the time the message is received by miner j. This constraint prevents miners from falsely reporting the time the signature was created [0096] 4) Only one proof message will be accepted for a miner PK.sub.i. Any further proof messages will be ignored.

[0097] Step 7: The subcommittee members is selected by the following process [0098] 1) The value for miner with public key PK.sub.i is

[00012]$V_i=s_i.Math.{16}^{T_i^e}$ [0099] 2) The public keys are ranked in order of value V.sub.i i∈{1, . . . , N} [0100] 3) The subcommittee is selected by choosing the miners with the 3 lowest values of V.sub.i

[0101] V.sub.i is the output of the VRF with components s.sub.i and T.sub.i.sup.e. s.sub.i is the pseudo randomly generated component of the ECDSA signature. The time value acts as a penalty to prevent miners from brute-forcing through ECDSA ephemeral keys until a value of s.sub.i is low enough for them to increase their chances in being selected for the subcommittee. Although other solutions that prevent brute-force attacks have been investigated by Goldberg and Reyzin they require the creation of new elliptic curve algorithms and cannot be implemented as easily as embodiments of the present disclosure (Goldberg, Sharon, et al. “Verifiable random functions (VRFs)” (2018)).

[0102] In order for miners to agree on the subcommittee candidate list, each proof needs to be propagated throughout the network. Assuming low latency and high connectivity, the network should be able to quickly establish a global list of miner values and therefore establish the subcommittee. Furthermore, the network will only accept one proof message (the first one sent) per miner preventing the risk of spam attacks.

[0103] Multiparty Computations

[0104] A multiparty computation may be described as a calculation that requires more than one (independent) entity to collaborate in order to generate some final value. Ideally, the entities do not share or communicate their inputs, and keep their inputs private, whilst generating this final output. Within the context of non-parallelised mining, and in accordance with one or more embodiments of the present disclosure, a multiparty computation may comprise the calculation of anRSA modulus used in a repeated squaring time-lock puzzle. In such an embodiment, it is important that the prime factorization of the RSA modulus is not controlled by any single miner.

[0105] MPC for Generating Secret RSA Moduli

[0106] While other algorithms or methods may be selected by the skilled person, for illustrative purposes embodiments of the present disclosure may use the method disclosed by Boneh and Franklin for generation of a shared prime modulus n (Boneh, Dan, and Matthew Franklin, “Efficient generation of shared RSA keys.” Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1997, herein after “Boneh et al”). In their algorithm 3, independent entities (Alice, Bob and Henry) establish an RSA modulus of arbitrary size. The method is a quintuple of algorithms: [0107] PickCandidates(k).fwdarw.(p.sub.i, q.sub.i)—Each entity picks two random k-bit integers [0108] Compute N—Using a private and distributed computation (p. 3 of Boneh et al) the 3 servers compute

[00013]$n=\left(p_1+p_2+p_3\right).Math.\left(q_1+q_2+q_3\right)$ [0109] without explicitly sharing (p.sub.i, q.sub.i) [0110] Since n is now public the entities perform trial division to check that n is not divisible by small primes e.g. the method which is used in the joint verifiable random secret sharing (JVRSS) protocol in threshold ECDSA signature implementations. [0111] Primality Test—The 3 servers use a private distributed computation to test that n is in fact the product of two primes (See p. 4, Boneh et al). If the test fails, then the protocol is restarted from step 1.

[0112] Boneh et al give empirical data for experiments generating 512, 1024 and 2048-bit moduli (Table 2, p. 10, Boneh et al). Notably, the total time for 3 parties (using 333 MHz Pentium IIs running Solaris 2.5.1) to generate a 512-bit modulus was 9 seconds and had a total network traffic of 0.18 Mb.

[0113] MPC For Computing n

[0114] For the multiparty generation of the RSA modulus n=pq with private key (p, q) we adapt the method outlined in Boneh et al. The algorithm assumes a randomly selected subcommittee of 3 miners using a minimal number of rounds of communication.

[0115] Setup

[0116] Miners M.sub.1, M.sub.2, M.sub.3 are selected using the Unique and Secure Subcommittee Selection. Miners must establish a direct connection with one-another and all messages between them are encrypted using AES symmetric encryption. The AES key is established using elliptic curve Diffie Hellmann key exchange.

[0117] Multiparty Computation

[0118] Step 1: Miners M.sub.1, M.sub.2, M.sub.3 pick candidates (p.sub.1, q.sub.1), (p.sub.2, q.sub.3) and (p.sub.3, q.sub.3), respectively, keeping the information secret.

[0119] Step 2: Miners M.sub.1, M.sub.2, M.sub.3 use JVRSS to compute

[00014]$n=\left(p_1+p_2+p_3\right).Math.\left(q_1+q_2+q_3\right)$

[0120] Step 3: Miners M.sub.1, M.sub.2, M.sub.3 perform a distributed primality test (see p. 4, Boneh et al) to determine whether n is a product of two primes.

[0121] Step 4: If step 3 results in a valid composite n being found n is propagated to the rest of the network

[0122] MPC For Computing Ø(n)

[0123] Given that the multiparty computation been computed above, the next stage is computing ϕ(n). To do this the miners need to know who miner M.sub.1 is as the calculation becomes asymmetric. However, this can be established during the subcommittee selection process

[0124] Step 1: Miner M.sub.1 computes

[00015]${\varphi }_1=n-p_1-q_1+1$

[0125] Step 2: M.sub.2 and M.sub.3 compute

[00016]${\varphi }_2=-p_2-q_2,{\varphi }_3=-p_3-q_3,$

[0126] Step 3: Each of the subcommittee members can use a distributed computation to compute

[00017]$\varphi \left(n\right)={\varphi }_1+{\varphi }_2+{\varphi }_3$ [0127] Observe that

[00018]$\begin{array}{c}\varphi \left(n\right)=\left({\varphi }_1+{\varphi }_2+{\varphi }_3\right)\\ =\left(n-p_1-q_1+1\right)+\left(-p_2-q_2\right)+\left(-p_3-q_3\right)\\ =n-\left(p_1+p_2+p_3\right)-\left(q_1+q_2+q_3\right)+1\\ =n-p-q+1\\ =\left(p-1\right)\left(q-1\right).\end{array}$

[0128] Note that once ϕ(n) is known to the committee, everyone in the committee will be able to deduce (p, q). It can be shown (without loss of generality) that

[00019]$p=\frac{n+1-\varphi \left(n\right)+\sqrt{{\left(n+1-\varphi \left(n\right)\right)}^2-4n}}{2},q=\frac{n+1-\varphi \left(n\right)-\sqrt{{\left(n+1-\varphi \left(n\right)\right)}^2-4n}}{2},$

[0129] and so ϕ(n) must not be computed until after a solution to the time-lock puzzle has been proposed. Therefore, it is especially important that ϕ(n) is not be shared by the committee until after a valid block is found.

[0130] Time-Locked Puzzle Mining on the Non-Parallelisable Mining (NPM) Blockchain

[0131] Embodiments of the disclosure combine verifiable random functions, multiparty computations and time lock puzzles in a novel way to create a mining algorithm for a PoW blockchain network. The aim of the algorithm is to compute a number, L, that is hard to find but can be verified if some secret information is known.

[0132] Assumptions:

[0133] In order for network-wide consensus to be achieved for each cycle we require the following: [0134] Honest majority: At least 51% of the miners must be honest. Same requirement exists for all public blockchain networks [0135] Honest majority subcommittee: 2 out of 3 members of each subcommittee must be honest to prevent the leaking of private keys or trap door function. Any suitable incentivisation strategy may be employed. [0136] Full Connectivity: The selection of random subcommittees in the network require full connectivity between miners so that multiparty computations can be carried out efficiently

[0137] Method 1: Predetermined number of Squarings

[0138] Method

[0139] Step 1: A group of network miners M.sub.1, . . . , M.sub.n (n>3) start the cycle by selecting a subcommittee of 3 (connected) miners (M.sub.1, M.sub.2 and M.sub.3 without loss of generality) using a verifiable random function.

[0140] Step 2a: Miners M.sub.1, M.sub.2 and M.sub.3 do a multiparty computation to compute

[00020]$n=pq$

without any individual miner able to calculate (p, q).

[0141] Step 2b: Miners M.sub.1, M.sub.2 and M.sub.3 propagate time-lock puzzle (t, n) along with a proof that they were chosen at random

[0142] Step 3a: Miner M.sub.i with public key PK.sub.i receives (t, n) and computes

[00021]$L_i=2^{H\left(X\left|\right|P{K}_i\right)\left[0:4\right]}\mathrm{mod}n$

[0143] where X is the previous block header hash.

[0144] Step 3b: Miner M.sub.i receives (t, n) and computes

[00022]$a=L_i\mathrm{mod}32b=L_i+4\mathrm{mod}32t_i=H\left(X.Math..Math.{\mathrm{PK}}_i\right)\left[a:b\right]$

[0145] Step 3c (HARD PROBLEM): Miner M.sub.i computes a verifiably random

[00023]$L=L_i^{2^{t+t_i}}\mathrm{mod}n$

[0146] L is the solution

[0147] Step 4: (Assuming M.sub.i wins) Miner M.sub.i propagates (L, L.sub.i, t.sub.i, PK.sub.i). This solution will be propagated along with the miner's block.

[0148] Step 5a: Verifier checks

[00024]$L_i=2^{H\left(X.Math..Math.P.Math.K.Math.\right)\left[0:4\right]}\mathrm{mod}n.$

[0149] Step 5b: Miners M.sub.1, M.sub.2 and M.sub.3 use a secure multiparty computation to compute

[00025]$\varphi \left(n\right)=\left(p-1\right)\left(q-1\right)$

[0150] and computes the shortcut e and e.sub.i efficiently using the formula

[00026]$e=2^t\mathrm{mod}\varphi \left(n\right)$$e_i=2^{t_i}\mathrm{mod}\varphi \left(n\right),$

[0151] Step 5c: Each subcommittee member can check that

[00027]$\tilde{L}=L_i^{e.Math.e_i}\mathrm{mod}n.\mathrm{And}$$\tilde{L}=L$

[0152] Step 6: The block is accepted as valid by the subcommittee if Step 5c passes. ϕ(n) can be propagated along with the valid block and (L, L.sub.i, t.sub.i, PK.sub.i) to the rest of the network for other miners to validate the solution before updating the blockchain.

[0153] Analysis:

[0154] The scheme presented has the following key features [0155] Puzzles are time-locked using two values: t and t.sub.i. t is the minimum number of squarings for the puzzle and acts as a network-wide difficulty parameter. t.sub.i is a pseudo randomly generated value, unique to each miner and each new block. Furthermore t.sub.i cannot be immediately deduced, instead requiring some initial computations in order to be worked out. [0156] Puzzle solution can only be solved using sequential computation [0157] Hash function digest acts as a random number generator so that the puzzle is unique to each miner

[0158] The pseudorandom nature of the base and exponent used in the calculation means that, whilst miners can estimate the approximate time that the solution will take to compute, they will not be able to tell exactly until they begin to mine.

[0159] Additionally, time-constraints can be imposed on Steps 1-2b and 5c so that corrupted, slow or dishonest subcommittees are rejected and can easily be reselected. Note, this system does not require use proof-of-stake in the selection of the subcommittee (although this may be desirable in implementation).

[0160] Method 2: Repeated Squaring Nonce with a Target Threshold

[0161] An alternative application of the time-lock puzzle mining for the NPM blockchain uses a target so that the number of squarings cannot be predetermined by the miner before calculation begins.

[0162] Target and Difficulty:

[0163] We introduce the target

[00028]$T_i=\frac{n}{D_i}$

[0164] The target value represents the maximum value that will be accepted as a valid solution. This value is analogous to the target difficulty parameter in Bitcoin (it can be encoded in the block header for example) and the subcommittee will know this value at the time of verification—see https://en.bitcoin.it/wiki/Difficulty.

[0165] Distribution of Squares

[0166] Note that approximately ¼ of all values in the range {0, . . . , n−1} are quadratic residues when n is a product of two primes. This result is derived from Euler's criterion (Lehmer, Emma. “On Euler's criterion.” Journal of the Australian Mathematical Society 1.1 (1959): 64-70). Furthermore, for sufficiently large random composite modulus, n, the distribution of quadratic residues is approximately uniform, meaning that the likelihood of selecting a quadratic residue in the range 0, 1, . . . , T.sub.i is equivalent to the likelihood of selecting a random number from .sub.n in the range 0, 1 . . . , T.sub.i multiplied by the likelihood of selecting a quadratic residue .sub.n. This constraint is important because we assume that for a given input L.sub.i∈.sub.n and random t∈.sub.n with

[00029]$A=L_i^{2^t}\mathrm{mod}n,$

[0167] then

[00030]$P\left(A<T_i\right)\approx \frac{T_i}{n}.$

[0168] Hashing the Solution: Our solution to the perceived ambiguity of the distribution of squares is to hash L and measure that value against the target i.e. to check if

[00031]$H\left(L\right)<T_i.$

[0169] Method

[0170] Step 1: A group of network miners M.sub.1, . . . , M.sub.n (n>3) start the cycle by selecting a subcommittee of 3 (connected) miners (M.sub.1, M.sub.2 and M.sub.3 w.l.o.g.).

[0171] Step 2a: Miners M.sub.1, M.sub.2 and M.sub.3 perform a multiparty computation to compute

[00032]$n=pq$

[0172] without explicitly calculating (p, q).

[0173] Step 2b: Miners M.sub.1, M.sub.2 and M.sub.3 propagate time-lock puzzle (t, n) along with a proof that they were chosen at random

[0174] Step 3a: Miner M.sub.i with public key PK.sub.i receives (t, n) and computes

[00033]$L_i=2^{H\left(X\left|\right|P{K}_i\right)\left[0:4\right]}\mathrm{mod}n$

[0175] where X is the previous block header hash.

[0176] Step 3b (HARD PROBLEM): Miner M.sub.i receives (t, n) and tries to find t.sub.i such that

[00034]$L=L_i^{2^{t+t_i}}\mathrm{mod}n,\mathrm{and}H\left(L\right)<T_i.$

[0177] L is the solution and T.sub.i is the target.

[0178] Step 4: (Assuming M.sub.i wins) Miner M.sub.i propagates (L, L.sub.i, t.sub.i, PK.sub.i). This solution will be propagated along with the miner's block.

[0179] Step 5a: Verifier checks

[00035]$L_i=2^{H\left(X.Math..Math.{\mathrm{PK}}_i\right)\left[0:4\right]}\mathrm{mod}n$

[0180] Step 5b: Miners M.sub.1, M.sub.2 and M.sub.3 use a secure multiparty computation to compute

[00036]$\varphi \left(n\right)=\left(p-1\right)\left(q-1\right)$

[0181] and computes the shortcut e and e.sub.i efficiently using the formula

[00037]$e=2^t\mathrm{mod}\varphi \left(n\right)e_i=2^{t_i}\mathrm{mod}\varphi \left(n\right),\mathrm{and}e.Math.e_i\mathrm{mod}\varphi \left(n\right)$

[0182] Step 5c: Each subcommittee member can check that

[00038]$\tilde{L}=L_i^{e.Math.e_i}\mathrm{mod}n.\mathrm{and}$$H\left(\tilde{L}\right)<T_i.$

[0183] Step 6: The block is accepted as valid by the subcommittee if Step 5c passes. #(n) can be propagated along with the valid block and (L, L.sub.i, t.sub.i, PK.sub.i) to the rest of the network for other miners to validate the solution before updating the blockchain.

[0184] Analysis

[0185] This technique has the following features [0186] Puzzles are time-locked using two values: t and t.sub.i. t acts as a standard difficulty parameter and is a uniform minimum number of squarings for the puzzle whereas t.sub.i is analogous to a nonce. This means that a miner will not be able to tell how many additional squarings are required without doing the computations [0187] Puzzle solution (analogous to the nonce in Bitcoin) can only be found using sequential computation. [0188] The puzzle solution (nonce) is public key dependent. This means that a new public key has to be generated for each entity that iterates nonce values

[0189] As with Method 1, time-constraints can be imposed on Steps 1-2b and 5c so that corrupted, slow or dishonest subcommittees are rejected and can easily be reselected. Furthermore, the nonce iteration path is inherently sequential and dependent on a public key, resulting in an inability for miners to gain any advantage by mining on the same block candidate. This significantly reduces the incentive to form mining pools.

[0190] Thus, embodiments of the disclosure provide a method that enables a flat network of distributed computers to establish consensus through sequential proof of computation. Four algorithms may be used: subcommittee selection using verifiable random functions, multiparty computations for establishing RSA modulus, time-lock puzzles with pseudo-random inputs. Embodiments of the disclosure also make use of cryptographic primitives native to the Bitcoin protocol (hash functions, elliptic curve cryptography) as well as puzzles based on the difficulty of prime factorisation.

[0191] Given the assumptions of low network latency and an honest majority of network participants as well as honest majority subcommittee selection, embodiments are both economically feasible at scale and strongly resistant to mining centralisation.

[0192] Turning now to FIG. 2, 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. 2, 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.

[0193] 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.

[0194] 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.

[0195] 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.

[0196] 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.

[0197] 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.

[0198] 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.

[0199] 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. 2 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. 2 are possible.

[0200] 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. 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.

[0201] An embodiment of the disclosure may provide a computer-implemented method comprising the steps: [0202] generating a plurality of multiparty computational challenges; [0203] providing each mining node in a plurality of mining nodes on a Proof-of-Work blockchain network with a respective challenge from the plurality of multiparty computational challenges.

[0204] Preferably, each mining node receives a different challenge relative to the other nodes. Thus, each challenge may be unique to the node to which it is provided, and no two challenges within the plurality of multiparty computational challenges may be the same.

[0205] Each mining node in the plurality of mining nodes attempts to find a solution to its respective multiparty computational challenge. This may comprise each node generating an output/value. This may be performed by using one or more inputs to an algorithm. The input(s) may be kept secret or private by the respective nodes, in that they do not share or communicate their respective input values with the other nodes in the plurality of nodes.

[0206] Preferably, each challenge in the plurality of multiparty computational challenges requires the use of an inherently sequential algorithm to find a solution to the challenge. The method may further comprise the steps of: [0207] generating a plurality of further multiparty computational challenges; and/or [0208] providing each mining node in the plurality of mining nodes with a respective further challenge from the plurality of further multiparty computational challenges.

[0209] Preferably, these steps are performed when a solution has been found, by one of the mining nodes in the plurality of mining nodes, to a multiparty computational challenge or a further multiparty computational challenge.

[0210] Preferably, generation of the plurality of multiparty computational challenges and/or the plurality of further multiparty computational challenges is performed, at least in part, by a subset of computer-based entities which is selected from a plurality of computer-based entities. At least one of the computer-based entities may be a mining node on the blockchain network. The subset of computer-based entities may be selected from the plurality of computer-based entities according to a random or pseudo-random selection process.

[0211] Generation of at least one of the multiparty computational challenges and/or further multiparty computational challenges may comprise the calculation of an output to an operation which uses a random or pseudo-random input. Generation of at least one of the multiparty computational challenges and/or further multiparty computational challenges may comprise the generation of an RSA key pair.

[0212] The challenge may comprise the calculation of an RSA modulus. Preferably, the RSA modulus is used in a repeated squaring time-lock puzzle.

[0213] The method may further comprise the step of using an inherently sequential algorithm to find a solution to at least one of the multiparty computational challenges and/or further multiparty computational challenges. The inherently sequential algorithm may comprise at least one of the following operations: a recursive operation; a modular exponentiation; and/or a repeated squaring operation.

[0214] The invention also provides a system, comprising: [0215] a processor; and [0216] memory including executable instructions that, as a result of execution by the processor, causes the system to perform any embodiment of the computer-implemented method described herein.

[0217] Preferably, the system comprises a plurality of nodes on a blockchain network, at least one of the nodes comprising the processor, memory and executable instructions.

[0218] The invention also provides a non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform an embodiment of the computer-implemented method described herein.