METHOD FOR INFORMATION VERIFICATION IN DISTRIBUTED SYSTEMS

Abstract

A method for a node to issue a new block is used for a distributed system in which transactions and records are organized in block. The method comprises the steps of: determining a value R from a common reference string; computing a value s associated to a value of a status with a private key at a node, wherein the private key is a private signing key corresponding to the node, and the value s can only be computed by the node with the private key; computing a value r by taking the value s into a function H at the node, wherein the value r is unpredictable and unique to other nodes; and determining whether the node obtains a right to issue a new block by taking the values R and r into a function V.

Claims

1. A method for a node to issue a new block in a distributed system including a plurality of blocks, comprising: determining a value R from a common reference string; computing a value s associated to a value of a status with a private key at a node; computing a value r by taking the value s into a function H at the node; and determining whether the node obtains a right to issue a new block by taking the values R and r into a function V.

2. The method of claim 1, wherein the private key is a private signing key corresponding to the node.

3. The method of claim 2, wherein the value s can only be computed by the node with the private key.

4. The method of claim 2, wherein the value r is unpredictable and unique to other nodes.

5. The method of claim 1, wherein the value r can be verified with a public key and the value s.

6. The method of claim 1, wherein the status can be defined to be a shard ID of the block.

7. The method of claim 1, wherein the status can be defined to be a chain ID of the block.

8. The method of claim 1, wherein the status can be defined to be a height of the block.

9. The method of claim 1, wherein the common reference string is a public randomness generated by a deterministic algorithm for each epoch.

10. The method of claim 9, wherein the epoch consists of a specific number of blocks.

11. The method of claim 10, wherein the common reference string is defined as: R.sub.i=Hash(TSig(R.sub.i1)), where R.sub.i is generated for the new block, and TSig() is a threshold signature function whose input is some set of share-signatures produced during previous blocks.

12. The method of claim 10, wherein the common reference string is defined as: R.sub.i=(Sig_{authority}(R.sub.i1)), where R.sub.i is generated for the new block.

13. The method of claim 1, wherein the function H is a hash function.

14. The method of claim 13, wherein the function V is defined as: |R.sub.iHash(Sig.sub.sk(status))|, where R.sub.i is the value R and Hash(Sig.sub.sk(status)) is verified by a public key.

15. The method of claim 14, wherein the node obtains the right to issue the new block when a calculated value for the function V is minimum at the node by comparing with other calculated values for the function at other nodes.

16. The method of claim 14, wherein the blocks pertain to a single block chain.

17. A method for a node to issue a new block in a distributed system including a plurality of blocks, comprising: determining a value R from a common reference string; computing a value s associated to a value of a status at a node, wherein the value s can be verified by other nodes; computing a value r by taking the value s into a function H at the node; and determining whether the node obtains a right to issue a new block by taking the values R and r into a function V.

18. The method of claim 17, wherein the value r is unpredictable and unique to other nodes.

19. The method of claim 17, the value r can be verified with a public key and the value s.

20. The method of claim 17, wherein the status can be defined to be a shard ID of the block.

21. The method of claim 17, wherein the status can be defined to be a chain ID of the block.

22. The method of claim 17, wherein the status can be defined to be a height of the block.

23. The method of claim 17, wherein the common reference string is a public randomness generated by a deterministic algorithm for each epoch.

24. The method of claim 23, wherein the epoch consists of a specific number of blocks.

25. The method of claim 24, wherein the common reference string is defined as: R.sub.i=Hash(TSig(R.sub.i1)), where R is generated for the new block, and TSig() is a threshold signature function whose input is some set of share-signatures produced during previous blocks.

26. The method of claim 24, wherein the common reference string is defined as: R.sub.i=(Sig_{authority}(R.sub.i1)), where R.sub.i is generated for the new block.

27. The method of claim 1, wherein the function H is a hash function.

28. The method of claim 27, wherein the function V is defined as: |R.sub.iHash(Sig(status))|, where R is the value R and Hash(Sig(status)) is verified by a public key.

29. The method of claim 27, wherein the node obtains the right to issue the new block when a calculated value for the function V is minimum at the node by comparing with other calculated values for the function at other nodes.

30. The method of claim 29, wherein the blocks pertain to a single block chain.

31. A distributed system including a plurality of blocks comprising: a plurality of first nodes determining a value R from a common reference string; and a plurality of second nodes computing a value s associated to a value of a status and computing a value r by taking the value s into a function H, and allowing one of the second nodes to issue a new block by taking the values R and r into a function V; wherein the plurality of first nodes and the plurality of second nodes are connected to each other via an internet.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0022] In order to sufficiently understand the essence, advantages and the preferred embodiments of the present invention, the following detailed description will be more clearly understood by referring to the accompanying drawings.

[0023] FIG. 1 is a block diagram of a system in which some exemplary embodiments of the disclosed subject matter may be implemented.

[0024] FIG. 2 is a flow diagram of a process in accordance with some exemplary embodiments of the disclosed subject matter.

[0025] FIG. 3 is a flow diagram of a process in accordance with some exemplary embodiments of the disclosed subject matter.

[0026] FIG. 4 is a timeline diagram of building a blockchain in accordance with some exemplary embodiments of the disclosed subject matter.

DETAILED DESCRIPTION OF THE INVENTION

[0027] The following description shows the preferred embodiments of the present invention. The present invention is described below by referring to the embodiments and the figures. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the principles disclosed herein. Furthermore, that various modifications or changes in light thereof will be suggested to persons skilled in the art and are to be included within the spirit and purview of this application and scope of the appended claims.

[0028] FIG. 1 is a diagram that shows a plurality of nodes 108-122 (e.g., devices, workstations, computers, or miners) connected to an internet 102 and connected to each other via the internet 102. The distributed system 100 in which transactions and records are organized in blocks includes a plurality of nodes 108-122. In the distributed system 100, a user is uniquely identified by its public key (pk) and private key (sk) pair, where the private key is a private signing key corresponding to one of nodes 108-122. All users at the nodes 108-122 can transfer and receive the stakes from other users. The blockchain of the present application is maintained by a special set of users S.sub.node where the members of S.sub.node are called nodes. All users can also verify the correctness of the blockchain. There are two special sets of nodes of the present application: the CRS (common reference string) set S.sub.CRS 104 and the notary set S.sub.notary 106 (a node can be in two sets at the same time). The consensus of distributed system 100 is based on proof-of-participation; that is, each node has equal chance to propose a block. One of nodes 108-122 can pack a batch of transactions into a block. A node proposes a block if the block is a candidate that can be selected (i.e., a node is allowed to issue a block if the block is selected and become a block in the blockchain). The blocks may pertain to a single blockchain.

[0029] The members in S.sub.CRS 104 are responsible for updating the CRS. The members in S.sub.notary 106 have right to propose a block and are responsible for deciding whose block can be chosen for the single chain.

[0030] FIG. 2 is a flowchart diagramming a process 200, in accordance with some exemplary embodiments of the disclosed subject matter. Those skilled in the art will appreciate the method illustrated by the flowchart of FIG. 2 is merely exemplary and that alternate variations may be employed, all in accordance with the present technique.

[0031] Process 200 begins with step 202, in which the members in S.sub.CRS generate a value R from a common reference string (CRS). An epoch consists of a specific number of blocks. The CRS is a public randomness generated by a deterministic algorithm for each epoch; no user in the system can predict the CRS of any future epoch. In an exemplary embodiment, the CRS of epoch i is updated by R.sub.i=Hash(TSig (R.sub.i1)), where R.sub.i is generated for the new block, Hash() is a hash function that maps arbitrarily long strings to binary strings of fixed length, and TSig() is a threshold signature function whose input is some set of share-signatures produced during previous blocks (i.e., the CRS nodes compute the randomness according to results from a previous epoch).

[0032] In another exemplary embodiment, the common reference string is defined as: R.sub.i=(Sig_{authority}(R.sub.i1)) under Proof-of-Authority blockchain, where R.sub.i is generated for the new block.

[0033] At Step 204, each node in S.sub.notary computes a value s associated to a value of a status with the private key, and the status is the public predictable information of the block (e.g. shard ID, chain ID or block height). In an exemplary embodiment, each node in S.sub.notary computes the signature with its private key sk as: s=Sig.sub.sk(status), where Sig.sub.sk(status) is a binary string and referred to as the digital signature of the status of the private key sk.

[0034] At next step 206, each node in S.sub.notary computes a value r by taking value s into a function H, where the function H may be a Hash function. The value r can be verified with the public key and the value s by other nodes.

[0035] The value r may be unpredictable and unique to other nodes.

[0036] At step 208, the node in S.sub.notary determines which node obtains a right to issue a new block by taking the value R and r into a function V. The function V is the verifiable random function (VRF), defined as: |R.sub.iHash(Sig.sub.sk(status))| where, the R.sub.i is the value R and Hash(Sig.sub.sk(status)) is verified by the public key. The node obtains the right to issue the new block when a calculated value for the function V is minimum at the node by comparing with other calculated values for the function at other nodes. To determine which node obtains the right to issue a block by computing:

l.sub.q=arg min.sub.jU.sub.q|R.sub.iHash(Sig.sub.skj(status))|

[0037] Where, l.sub.q is the node obtaining the right or the leader of node q, the U.sub.q is the set of nodes whose signatures are valid, and Sig.sub.skj(status) is the digital signature of the status of the private key sk at the node j.

[0038] The embodiment adopt a VRF to decide the node q to issue a block. This serves to minimize the communication cost so that a large population can join the protocol. The determination is independent of the round index so that the nodes are not required to propose their values at each round.

[0039] Consequently, except for the first round, the running time of each round reduces to 2, where is a time bound for the messages between any two correct nodes. The blocks may pertain to a single block chain.

[0040] The VRF has three benefits compared to the VRF in the prior art. The verifiable random function used in the prior art is Hash(Sig.sub.skj(Q.sub.i1; x)), where Q.sub.i1 is the randomness from the previous block. It is troublesome whether an adversary can choose to propose a block depends on the randomness of that adversary's block. If the randomness has advantage for Byzantine nodes (e.g. the probability of proposing a block for next block), then the adversary proposes the block. Thus, the overall advantage of the adversary increases up to (1/3)/(11/3)=1/2. The main problem is that the proposer decides the block and the randomness at the same time. Therefore, this embodiment separates the permission of proposing a block and generating the randomness in order to avoid such bias attacks. Second, the configuration is more flexible to compute the function because each user can compute part of the VRF for any status at any time, say, Hash Sig.sub.skj(x). At the beginning of each epoch, any user or node can get the CRS of the epoch and compute the probability of proposing a block in the epoch. However, The VRF of the prior art requires Q.sub.i1 to compute Q.sub.i. Third, the configuration has better space consumption. This embodiment uses the same randomness for many blocks in one epoch. Thus, the space complexity is reduced by a constant.

[0041] FIG. 3 is a flowchart diagramming a process 300, in accordance with some exemplary embodiments of the disclosed subject matter. Those skilled in the art will appreciate the method illustrated by the flowchart of FIG. 3 is merely exemplary and that alternate variations may be employed, all in accordance with the present technique.

[0042] Process 300 begins with step 302, in which the members in S.sub.CRS generate a value R from a common reference string (CRS). An epoch consists of a specific number of blocks. The CRS is a public randomness generated by a deterministic algorithm for each epoch; no user in the system can predict the CRS of any future epoch. In an exemplary embodiment, the CRS of epoch i is updated by R.sub.i=Hash(TSig(R.sub.i1)), where R.sub.i is generated for the new block, and TSig() is a threshold signature function whose input is some set of share-signatures produced during previous blocks (i.e., the CRS nodes compute the randomness according to results from a previous epoch).

[0043] In another exemplary embodiment, the common reference string is defined as: R.sub.i=(Sig_{authority}(R.sub.i1)) under Proof-of-Authority blockchain, where R.sub.i is generated for the new block.

[0044] At step 304, each node in S.sub.notary computes a value s associated to a value of a status, the status is the public predictable information of the block (e.g. shard ID, chain ID or block height), wherein the value s can be verified by other nodes. In an exemplary embodiment, one of node q in S.sub.notary computes the value s, and other nodes can verify the value s with public key pk.sub.q using zero-knowledge proofs (one party, usually called PROVER, to convince another party, called VERIFIER, that PROVER knows some facts without revealing to the VERIFIER any information about his knowledge).

[0045] At step 306, each node in S.sub.notary computes a value r by taking value s into a function H, where the function H may be a Hash function. The value r can be verified with the public key and the value s by other nodes. The value r may be unpredictable and unique to other nodes.

[0046] At step 308 the node in S.sub.notary determines which node obtains a right to issue a new block by taking the value R and r into a function V. The function V is the verifiable random function (VRF), defined as: |R.sub.iHash(Sig(status))| where, the R.sub.i is the value R and Hash(Sig(status)) is verified by the public key. The node obtains the right to issue the new block when a calculated value for the function V is minimum at the node by comparing with other calculated values for the function at other nodes. To determine which node obtains the right to issue a block by computing:

l.sub.q=arg min.sub.jU.sub.q|R.sub.iHash(Sig.sub.j(status))|

[0047] Where, l.sub.q is the node obtaining the right or the leader of node q, the U.sub.q is the set of nodes whose signatures are valid, and Sig.sub.skj(status) is the digital signature of the status at the node j. This embodiment serves to minimize the communication cost so that a large population can join the protocol. The determination is independent of the round index, so the nodes are not required to propose their values at each round. Consequently, except for the first round, the running time of each round reduces to 2, where is a time bound for the messages between any two correct nodes. The blocks may pertain to a single block chain.

[0048] FIG. 4 is a timeline diagram, in accordance with some exemplary embodiments of the disclosed subject matter. Those skilled in the art will appreciate the method illustrated by the flowchart of FIG. 4 is merely exemplary and that alternate variations may be employed, all in accordance with the present technique.

[0049] The timeline 400 shows the method for building a single chain of the present invention, the method providing: a single blockchain 402; a plurality of randomness R.sub.i 404, R.sub.i+1 406 and R.sub.i+2 408 of a CRS chain 418; a plurality of epoch: epoch i1 410, epoch i 412, epoch i+1 414 and epoch i+2 416; and a plurality of valid nodes set S.sub.node.sup.i1, S.sub.node.sup.i and S.sub.node.sup.i+1.

[0050] Any user with enough deposit can register its own public key in the blockchain 402. The users who want to enter or leave S.sub.node can announce the request. The request will be recorded in the blocks. The node is called valid if it owns enough deposit and has registered a valid public key. The set S.sub.node.sup.i+1 can be updated by S.sub.node.sup.i and the blocks in the epoch i 412.

[0051] The members in S.sub.CRS are responsible for updating the CRS chain 418. The members in S.sub.notary have right to propose a block and are responsible for deciding whose block can be chosen for the single chain 402. The decision of whose block can be chosen is determined by the public predictable information status, R.sub.i 404 and the private keys, the node in S.sub.notary compute the value |R.sub.iHash (Sig.sub.skq(status))| locally.

[0052] The members in S.sub.CRS and S.sub.notary are re-elected for each epoch. Each epoch i correspond to the randomness R.sub.i 404 of CRS chain 418. When S.sub.CRS is re-elected, the members in S.sub.CRS will update the CRS chain 418 for the next epoch. In an exemplary embodiment, the set S.sub.CRS.sup.i and the set S.sub.notary.sup.i are the CRS set and the notary set of epoch i 412. The set S.sub.CRS.sup.i, the set S.sub.notary.sup.i and the randomness R.sub.i 404 are decided before the epoch i 412 starts. When the epoch i 412 starts, the members in S.sub.CRS.sup.i generate the randomness R.sub.i+1 406 as: R.sub.i+1=Hash(TSig(R.sub.i)), where TSig(R.sub.i) is the threshold signature signed by the nodes in S.sub.CRS.sup.i. After R.sub.i+1406 is decided, the set S.sub.CRS.sup.i+1 and the set S.sub.notary.sup.i+1 can be elected by Fisher-Yate shuffle with the randomness R.sub.i+1406 from the set S.sub.node.sup.i. Finally, the members in S.sub.CRS.sup.i+1 and S.sub.notary.sup.i+1 run the key generation algorithm of the threshold signature scheme, respectively.

[0053] According to the present invention, the method and system for a node to issue a new block for building an agreed single chain by using the common reference string (CRS) and verifiable random function (VRF). It minimizes the communication cost and reduces the time bound so that achieving high decentralization and low latency.

[0054] The foregoing embodiments of the invention have been presented for the purpose of illustration. Although the invention has been described by certain preceding examples, it is not to be construed as being limited by them. They are not intended to be exhaustive, or to limit the scope of the invention. Modifications, improvements and variations within the scope of the invention are possible in light of this disclosure.