Blockchain network and finalization method therefor

Abstract

Signature handling for a block for which consensus was formed in blockchain network which requires signatures from plurality of nodes to form consensus for block adoption. After completion of the setup, first node 110 sends a first message including a generated block to N nodes (S301). Each node evaluates the validity of the block on basis of the rule for consensus formation (S302). If the block is valid, the node sends a second message which includes signature si, by secret key share f(x.sub.i), with respect to a hash value h of the block for which consensus is to be formed (S303-1). After k signatures are collected at jth node, the node merges these signatures to generate a signature corresponding to a public key PK (S304). A block for which consensus is to be formed has signature SK.Math.h appended thereto and is added to blockchain of each node (S306).

Claims

1. A method of finalizing adoption of a block for a blockchain network in which N nodes, wherein N is an integer greater than or equal to 2, participate in consensus formation for the adoption, requiring signatures by k nodes, wherein k is an integer satisfying 2≤k≤N, wherein the i.sup.th node, wherein i is an integer satisfying 1≤i≤N, performing steps of: transmitting a block to the N nodes, receiving from j.sup.th node, wherein j is an integer satisfying 1≤j≤N, a signature sj obtained by multiplying a hash value h of the block by f(x.sub.j), which is a value at x=x.sub.j of unknown (k-1) order polynomial f(x), calculating f(0).Math.h from coordinates (x.sub.j, s.sub.j) with respect to k nodes, adding calculated f(0).Math.h to the block as a signature corresponding to a public key, and adding the block with the signature to the blockchain by a processor of the i.sup.th node to finalize the adoption of the block, wherein G.sub.1 is a cyclic group with g.sub.1 as a generator, G.sub.2 is a cyclic group with g.sub.2 as a generator, and G.sub.T is a cyclic group with g.sub.T as a generator, wherein a bilinear map e is defined from G.sub.1×G.sub.2 to G.sub.T, and a hash function, which provides the hash value h of a respective block for which consensus is to be formed, is defined from any data to the cyclic group G.sub.2, and wherein i.sup.th node has access to values of x.sub.j for each j from 1 to N, and j.sup.th node has access to a value of f(x.sub.j).

2. The method according to claim 1, wherein calculation of f(0).Math.h is performed using Lagrange interpolation.

3. The method according to claim 1, wherein determination is made as to whether k or more signatures exist and when the determination is positive calculation of the f(0).Math.h is performed.

4. A nontransitory computer readable medium storing a program that when executed causes i.sup.th node, wherein i is an integer satisfying 1≤i≤N, to perform a method of finalizing adoption of a block for a blockchain network in which N nodes, wherein N is an integer greater than or equal to 2, participate in consensus formation for the adoption, requiring signatures by k nodes, wherein k is an integer satisfying 2≤k≤N, wherein the i.sup.th node performing steps of: transmitting a block to the N nodes, receiving from j.sup.th node, wherein j is an integer satisfying 1≤j≤N, a signature sj obtained by multiplying a hash value h of the block by f(x.sub.j), which is a value at x=x.sub.j of unknown (k-1) order polynomial f(x), calculating f(0).Math.h from coordinates (x.sub.j, s.sub.j) with respect to k nodes, adding calculated f(0).Math.h to the block as a signature corresponding to a public key, and adding the block with the signature to the blockchain by a processor of the i.sup.th node to finalize the adoption of the block, wherein G.sub.1 is a cyclic group with g.sub.1 as a generator, G.sub.2 is a cyclic group with g.sub.2 as a generator, and G.sub.T is a cyclic group with g.sub.T as a generator, wherein a bilinear map e is defined from G.sub.1×G.sub.2 to G.sub.T, and a hash function, which provides the hash value h of a respective block for which consensus is to be formed, is defined from any data to the cyclic group G.sub.2, and wherein i.sup.th node has access to values of x.sub.j for each j from 1 to N, and j.sup.th node has access to a value of f(x.sub.j).

5. An i.sup.th node comprising a communication unit, a communication interface, a processing unit, and a storage unit, wherein i is an integer satisfying 1≤i≤N which is part of a blockchain network in which N nodes, wherein N is an integer greater than or equal to 2, participate in consensus formation for adoption of a block, requiring signatures by k nodes, wherein k is an integer satisfying 2≤k≤N, which: transmits a block to the N nodes, receives from j.sup.th node, wherein j is an integer satisfying 1≤j≤N, a signature sj obtained by multiplying a hash value h of the block by f(x.sub.j), which is a value at x=x.sub.j of unknown (k-1) order polynomial f(x), calculates f(0).Math.h from coordinates (x.sub.j, s.sub.j) with respect to k nodes, adds calculated f(0).Math.h to the block as a signature corresponding to a public key, and adds the block with the signature to the blockchain by a processor of the i.sup.th node to finalize the adoption of the block, wherein G.sub.1 is a cyclic group with g.sub.1 as a generator, G.sub.2 is a cyclic group with g.sub.2 as a generator, and G.sub.T is a cyclic group with g.sub.T as a generator, wherein a bilinear map e is defined from G.sub.1×G.sub.2 to G.sub.T, and a hash function, which provides the hash value h of a block for which consensus is to be formed, is defined from any data to the cyclic group G.sub.2, and wherein i.sup.th node has access to values of x.sub.j for each j from 1 to N, and j.sup.th node has access to a value of f(x.sub.j).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a blockchain network according to the first embodiment of the present invention.

(2) FIG. 2 is a flowchart of the method of key generation according to the first embodiment of the present invention.

(3) FIG. 3 is a flowchart of the method of finalization of the adoption of a block according to the second embodiment of the present invention.

DETAILED DESCRIPTION OF THE DRAWINGS

(4) The embodiments of the present invention will be described in detail with reference to the drawings below.

First Embodiment

(5) FIG. 1 illustrates a blockchain network for the first embodiment of the present invention. In the network 100, N equals 5 as an example and has the first node 110, the second node 120, the third node 130, the fourth node 140, and the fifth node 150. Each node is a computer comprising a communication unit 111, such as a communication interface, a processing unit 112, such as a processor or CPU, and a storage unit 113 including a storage device or storage medium, such as a memory or a hard disk, as illustrated for the first node 110, and can realize respective processes explained below by executing a predetermined program. The node 110 may include one or more apparatuses or servers. The program may include one or more programs, and it may be stored on a computer-readable storage medium to provide a non-transitory program product. The configurations of the hardware are the same for the other nodes. Although the following description will focus on the first node 110, the same processes can be performed at other nodes. Also, nodes that do not participate in consensus formation may be included in the network 100.

(6) The rules for the consensus algorithm and the rules for the setup are defined in the given program, and can be stored in a storage unit 113 or in a storage device or storage medium accessible from the first node 110 via the network.

(7) The process by which N nodes participating in consensus formation are transitioned from a state in which they can communicate with each other to a state in which consensus formation for adoption of a block can be performed is referred to as a “setup”. The setup is initiated by receiving a request for setup outside or inside the network 100, and FIG. 1 shows an example of the request being sent from outside. Such a request may include the specification of the number of signatures k required for consensus formation. The specification may be defined in the rules for the setup in advance. The request may include the specification of N nodes which participate in the consensus. The specification may be defined in advance in the rules for the setup.

(8) Once the values of N and k have been determined in either form and the setup process has made progress, each node will maintain one public key assigned to the entire nodes participating in the consensus, N public key shares assigned to respective nodes participating in the consensus, and one secret key share assigned to the node in question. The values of N and k or k/N are also maintained by each node. The value of N can also be determined from the number of public key shares.

(9) The relationship between a secret key and a public key is that the plaintext signed by the secret key can be verified by the public key in question, and the same is true for the secret key share and its corresponding public key share. Here, “secret key share” refers to any one of a set of secret key shares generated so that a signature by a secret key can be generated using signatures by a predetermined number of k secret key shares out of a set of N secret key shares. Thus, a signature corresponding to the public key can be generated based on the k secret key shares without knowing the secret key in question, and the signature can be added to the block that is the subject of consensus formation. The added signature is verifiable by the public key.

(10) To further explain the example in FIG. 1, below notations are used: PK (abbreviation for Public Key) for one public key assigned to the entire network 100; SK (abbreviation for Secret Key) for the secret key corresponding to the public key; PK1 and SK1, PK2 and SK2, PK3 and SK3, PK4 and SK4, and PK5 and SK5 for the public key shares and secret key shares assigned to the first node 110, the second node 120, the third node 130, the fourth node 140, and the fifth node 150, respectively. After the setup, for example, the first node will have stored PK, PK1 through PK5 and SK1 in its storage unit 113 or in a storage device or storage medium capable of communicating with the node. These stored data will be accessible by the node in a later consensus formation or its finalization process.

(11) Here, the public key PK may not be generated at the setup stage, although it is required for verification of the signature that is eventually added. This is because the node or apparatus that verifies the signature need only have the public key PK at the time of verification, and it is not necessarily necessary that each node of the network 100 has it at the time of initial setup.

(12) FIG. 2 shows the flow of the key generation method for the present embodiment. As an example, let us consider the (k−1)-order polynomial f(x) and let the value of f(x.sub.i) (where i is an integer from 1 to N representing the ith node and x.sub.i is an arbitrary integer) be the secret key share SKi for each node.

(13) First, the ith node determines the (k−1) order polynomial f.sub.i(x), where a.sub.im (m is an integer between 0 and k−1) is a coefficient (S201). Each node can calculate f.sub.i(x) by selecting or generating and storing a.sub.im according to the setup rule.

(14) $\begin{array}{cc}{f}_i\left(x\right)=\underset{m=0}{\overset{k-1}{.Math.}}{a}_{\mathrm{im}}{x}^m& \left[\mathrm{equation}4\right]\end{array}$

(15) Next, the ith node sends the value of a.sub.im.Math.g.sub.1 or a message including it at each m from 0 to k−1 to the other nodes using the generator g.sub.1 of the cyclic group G.sub.1 (S202). The ith node also sends the value of f.sub.i(x.sub.j) or a message including it to the jth node (j is an integer from 1 to N). Here, the transmission of f.sub.i(x.sub.j) may be sent before or at the same time as m and a.sub.im.Math.g.sub.1.

(16) The generator g.sub.1 shall be accessible and usable by each of the N nodes, either stored and known at each node or given to the N nodes participating in the consensus formation from any of the nodes. Similarly, the value of the integer x.sub.i that gives the ith node its secret key share f(x.sub.i) shall be accessible and usable by each of the N nodes. For example, these values can be stored in the storage unit of each node or in a storage device or storage medium accessible from each node.

(17) Then, at the jth node, we calculate f(x.sub.j), or secret key share SKj, by adding f.sub.i(x.sub.j) for i from 1 to N (S204). If we define the polynomial f(x) as below,

(18) $\begin{array}{cc}{f}_i\left(x\right)=\underset{m=0}{\overset{k-1}{.Math.}}{a}_m{x}^m& \left[\mathrm{equation}5\right]\end{array}$
although this is not known for any node, the value of f(x.sub.j) can be calculated at each node without each node knowing f(x) itself, by considering f(x.sub.j) as shown in the following equation:

(19) $\begin{array}{cc}f\left(x_j\right)=\underset{i=1}{\overset{N}{.Math.}}{f}_i\left(x_j\right)=\underset{i=1}{\overset{N}{.Math.}}\left(\underset{m=0}{\overset{k-1}{.Math.}}{a}_{\mathrm{im}}{x_j}^m\right)=\underset{m=0}{\overset{k-1}{.Math.}}\left(\underset{i=1}{\overset{N}{.Math.}}{a}_{\mathrm{im}}\right){x_j}^m=\underset{m=0}{\overset{k-1}{.Math.}}{a}_m{x_j}^m& \left[\mathrm{equation}6\right]\end{array}$

(20) Since each node can calculate m and a.sub.im.Math.g.sub.1 at its own node and has already received those of other nodes, each node can calculate SKj.Math.g.sub.1 as the public key share PKj according to the following equation (S205):

(21) $\begin{array}{cc}\mathrm{SKj}.Math.g_1=f\left(x_j\right).Math.g_1=\left(\underset{m=0}{\overset{k-1}{.Math.}}{a}_m{x_j}^m\right)g_1=\left(\underset{m=0}{\overset{k-1}{.Math.}}\left(\underset{i=1}{\overset{N}{.Math.}}{a}_{\mathrm{im}}\right){x_j}^m\right)g_1=\underset{m=0}{\overset{k-1}{.Math.}}\left(\underset{i=1}{\overset{N}{.Math.}}{a}_{\mathrm{im}}{g}_1\right){x_j}^m& \left[\mathrm{equation}7\right]\end{array}$

(22) The calculation of public key share PKi by this formula is possible for all nodes without knowing f(x), since m and a.sub.im.Math.g.sub.1, and x.sub.i are known for all i.

(23) It can be understood that the pair of public and secret key shares thus obtained can be used as a cryptographic scheme by defining a hash function, that gives a hash value h of a block which is the subject of consensus formation, as a mapping from any data to a cyclic group G.sub.2 whose generator is g.sub.2, a signature sj as SKj.Math.h obtained by multiplying h by SKj, and a bilinear map as a mapping e from G1×G2 to a cyclic group G.sub.T whose generator is g.sub.T which satisfies the below equation, where a and b are arbitrary integers:
e(ag.sub.1,bg.sub.2)=g.sub.T.sup.ab  [equation 8]

(24) That is, when the ith node receives the hash value h of the block which is the subject of consensus formation and signature sj from the jth node, using the public key share PKj, which is known by the algorithm described above, we get the following:
e(PKj,h)=e(SKj.Math.g.sub.1,h)=e(g.sub.1,SKj.Math.h)=e(g.sub.1,s.sub.j)  [equation 9]

(25) Therefore, the signature sj received from the jth node can be verified using a known generator g.sub.1. The hash value may be calculated at each node from the block which is the subject to consensus formation by defining a hash function in the setup rule.

(26) The above explanation assumes a signature scheme in which the value of (k−1)-order polynomial function f(x) is defined as a secret key share, and the value of the secret key share multiplied by the generator of a cyclic group is a public key share, but different signature schemes can be used as long as a signature by a secret key can be generated using a predetermined number of k secret key shares out of a set of N secret key shares. In this case, it is desirable that respective secret key shares can be generated in a distributed manner at respective nodes, rather than giving respective nodes a set of secret key shares generated by any of the nodes of the network 100 or a node outside thereof.

(27) In the description above, we have used public key share PKj and secret key share SKj at the jth node as an example, but we add that when describing the processes performed at the ith node from its viewpoint, it goes without saying that the subscripts are changed accordingly.

Second Embodiment

(28) FIG. 3 illustrates the flow of the method of finalizing the adoption of a block according to the second embodiment of the invention. Beginning from the state where the setup is completed, the first node 110 generates a block and transits a first message including the block to N nodes participating in consensus formation (S301). The transmitting node can also receive the block by itself. Here, messages can be transmitted or received directly or indirectly between the nodes, and a node can convey data related to the consensus formation to other nodes that are part of the network 100 and it can also receive data from other nodes.

(29) Each node receiving the first message evaluates the validity of the block in question based on the rules of consensus formation set forth in the program that each node has (S302). The details of the evaluation of validity can include various rules, such as whether the transmitter is a legitimate transmitting node, whether the data format of the block meets a predetermined format or other predetermined condition depending on the application, and whether fork has not occurred, and there may be different rules for different nodes. It may also require transmitting and/or receiving messages to and from other nodes in order to evaluate the validity.

(30) If evaluated as valid, the node sends a second message to each node with a signature si, with respect to the hash value h of the block for which consensus is to be formed, by the secret key share f(x.sub.i) accessible to the node (S303-1). The signature can be performed by multiplying the hash value by the secret key share given to the node. The destination may include its own node. If the block is evaluated as invalid, the block is rejected (S303-2).

(31) After k signatures have been collected at the jth node, the node merges these signatures to generate a signature corresponding to the public key PK (S304). Specifically, each node periodically or intermittently determines whether the k/N condition is satisfied or not, and if it is satisfied, f(0).Math.h can be calculated from received k or more signatures by secret key shares as the signature SK.Math.h by the secret key SK corresponding to the public key PK. Here, we use the fact that a (k−1)-order polynomial f(x) can be uniquely determined if k or more points (x.sub.i, f(x.sub.i)) are known, and the value of f(0) can be considered as the value of an unknown secret key SK. If k points (x.sub.i, f(x.sub.i).Math.h) are known from the k signatures, then the function f(x).Math.h is determined. f(0).Math.h can be calculated using Lagrange interpolation, for example.

(32) The public key PK can be calculated from k or more points (x.sub.j, PKj)=(x.sub.j, f(x.sub.j).Math.g.sub.1), for example, by Lagrange interpolation, which may be done at the setup stage and distributed as needed, or it may be generated based on k public key shares PKj by a node or apparatus inside or outside of the network 100 that verifies the signature, at or before verification.

(33) Then, if necessary, the generated single signature SK.Math.h is broadcast or transmitted to other nodes (S305). Since the validity has already been evaluated by k or more nodes, it may be possible to add the block to the blockchain of the node at the time of successful merge, but as an example, the nodes that have successfully merged can transmit the merged signatures to other nodes, and each node may add the block in response to receiving a predetermined number or more merged signatures.

(34) Finally, the block subject to consensus formation is added to the blockchain of each node with the signature SK.Math.h added (S306). This finalizes the adoption of the block in the network 100.

(35) Although the above description considers the case where one secret key share is given to each node, the number of shares to be given to a single node may be multiple. Also, although the description above does not mention the details of the block to be evaluated for validity, it can be a block including one or more transactions, or it can include one or more pieces of arbitrary data. And it is also possible to apply the spirit of the present invention to the evaluation of validity by a computer network with a plurality of nodes, with respect to one or more pieces of data that do not necessarily form a chain.

(36) It is to be noted that if the term “only” is not written, such as in “based only on x”, “in response to x only”, or “in the case of x only”, in the present specification, it is assumed that additional information may also be taken into account.

(37) In addition, as a caveat, even if there are aspects of a method, program, terminal, apparatus, server or system (hereinafter referred to as “method, etc.”) that perform operations different from those described herein, each aspect of the invention is intended to perform the same operation as one of the operations described herein, and the existence of an operation different from those described herein does not mean that the method, etc. is outside the scope of each aspect of the invention.

REFERENCE SIGNS LIST

(38) 100 network 110 first node 111 communication unit 112 processing unit 113 storage unit 120 second node 130 third node 140 fourth node 150 fifth node