# US 2020/0403776 A1 · Apparatus and method for achieving distributed consensus based on decentralized byzantine fault tolerance

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0403776 A1
- Document ID: US20200403776A1
- Status: Published application
- Kind: A1
- Application number: 16/903,057
- Filed: 2020-06-16
- Published: 2020-12-24
- Earliest claimed: 2019-06-18
- Assignees: Electronics and Telecommunications Research Institute
- Applicants: Electronics and Telecommunications Research Institute
- Inventors: Jin-Tae OH; Joon-Young PARK; Ki-Young KIM; Dong-Oh KIM; Young-Chang KIM
- Web page: https://patentgrep.com/patent/US20200403776A1

## CPC

- H04L 9/0637: {Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]}
- H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD}
- G06F 11/2005: {using redundant communication controllers}
- H04L 9/085: {Secret sharing or secret splitting, e.g. threshold schemes}
- H04L 9/30: Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L 9/3247: {involving digital signatures}
- H04L 9/3255: {using group based signatures, e.g. ring or threshold signatures}
- H04L 63/123: {received data contents, e.g. message integrity}
- H04L 9/50: {using hash chains, e.g. blockchains or hash trees}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed herein are an apparatus and method for achieving distributed consensus based on decentralized Byzantine fault tolerance. The apparatus may include one or more processors and an execution memory for storing at least one program that is executed by the one or more processors, wherein the program is configured to receive delegate request messages, each including a first transaction for requesting distributed consensus proposed by a client, and determine congress candidate nodes forming a consensus quorum, to be consensus nodes based on the delegate request messages, generate a prepare message that includes a second transaction for obtaining consent to results of determination of the consensus nodes, and send the prepare message to the consensus nodes, and receive commit messages, each including an electronic signature of a corresponding consensus node, from the respective consensus nodes, and broadcast a reply message indicative of results of verification of the electronic signatures.

## Claims

### Claim 1

An apparatus for achieving distributed consensus based on decentralized Byzantine fault tolerance, comprising:
one or more processors; and
an execution memory for storing at least one program that is executed by the one or more processors,
wherein the at least one program is configured to:
receive delegate request messages, each including a first transaction for requesting distributed consensus proposed by a client, from congress candidate nodes in a blockchain, and determine congress candidate nodes forming a consensus quorum, among the congress candidate nodes, to be consensus nodes based on the delegate request messages,
generate a prepare message that includes a second transaction for obtaining consent to results of determination of the consensus nodes from the consensus nodes, and send the prepare message to the consensus nodes, and
receive commit messages, each including an electronic signature of a corresponding consensus node, in response to the prepare message from the respective consensus nodes, and broadcast a reply message indicative of results of verification of the electronic signatures included in the commit messages, to the congress candidate nodes, thus completing distributed consensus,
wherein the consensus quorum is 2f+1, where f is an integer of 1 or more,
wherein f satisfies both a first condition and a second condition,
wherein the first condition is a condition satisfied in a case where, when the congress candidate nodes are selected from among all nodes of the blockchain with a probability of p (where p is a real number that is equal to or greater than 0 and is less than or equal to 1), a first probability that a number of Byzantine nodes to be selected as the congress candidate nodes will be greater than f is less than or equal to a preset first reference probability, and
wherein the second condition is a condition satisfied in a case where a second probability that a number of congress candidate nodes will be less than or equal to 3f is less than or equal to a preset second reference probability.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the at least one program is configured to:
receive the delegate request messages along with next consensus group messages, each including information indicating whether a corresponding node has been selected as the congress candidate node, from all nodes, and
when a number of nodes that sent the next consensus group messages is 3f+1 or more, select 3f+1 nodes and determine the selected nodes to be the congress candidate nodes for a next distributed consensus, whereas when the number of nodes that sent the next consensus group messages is less than or equal to 3f, not update the congress candidate nodes.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the at least one program is configured to, when a number of delegate request messages forming the consensus quorum are received, determine the second transaction based on identical f+1 first transactions included in the delegate request messages forming the consensus quorum.

### Claim 4 (depends on 2)

The apparatus of claim 2, wherein the at least one program is configured to generate first bitmap information corresponding to the first transactions of the congress candidate nodes and second bitmap information including the results of determination of the consensus nodes, and to generate the prepare message including the first bitmap information, the second bitmap information, and the second transaction.

### Claim 5 (depends on 4)

The apparatus of claim 4, wherein each of the consensus nodes checks a validity of the prepare message based on whether the first bitmap information corresponds to the second transaction.

### Claim 6 (depends on 5)

The apparatus of claim 5, wherein the at least one program is configured to generate a first aggregated public key and a first aggregated quorum value by respectively aggregating public keys and quorum values included in the delegate request messages, and to generate the prepare message further including a first hash value obtained by hashing the first aggregated public key and the first aggregated quorum value.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein each of the consensus nodes is configured to generate a second aggregated public key and a second aggregated quorum value by respectively aggregating previously registered public keys and previously registered quorum values, and to compare a second hash value, obtained by hashing the second aggregated public key and the second aggregated quorum value, with the first hash value as to whether the second hash value is identical to the first hash value, thus checking the validity of the prepare message.

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein each of the consensus nodes is configured to, when the second hash value is identical to the first hash value, generate a signature value including the first hash value and a secret value prestored in the corresponding consensus node, include the signature value in the prepare message, and generate a corresponding commit message by adding the electronic signature based on the signature value to the prepare message.

### Claim 9 (depends on 8)

The apparatus of claim 8, wherein the at least one program is configured to generate a multi-signature from the electronic signatures by respectively aggregating the signature values included in the commit messages, public keys of the first aggregated public key, and quorum values of the first aggregated quorum value in a form of a signature value tree of the multi-signature, a public key tree of the multi-signature, and a quorum value tree of the multi-signature.

### Claim 10 (depends on 9)

The apparatus of claim 9, Wherein the at least one program is configured to, when a result of verification of the multi-signature is true, generate the reply message including the second transaction and the multi-signature.

### Claim 11

A method for achieving distributed consensus based on decentralized Byzantine fault tolerance, the method being performed by an apparatus for achieving distributed consensus based on decentralized Byzantine fault tolerance, the method comprising:
receiving delegate request messages, each including a first transaction for requesting distributed consensus proposed by a client, from congress candidate nodes in a blockchain, and determining congress candidate nodes forming a consensus quorum, among the congress candidate nodes, to be consensus nodes based on the delegate request messages;
generating a prepare message that includes a second transaction for obtaining consent to results of determination of the consensus nodes from the consensus nodes, and sending the prepare message to the consensus nodes; and
receiving commit messages, each including an electronic signature of a corresponding consensus node, in response to the prepare message from the respective consensus nodes, and broadcasting a reply message indicative of results of verification of the electronic signatures included in the commit messages, to the congress candidate nodes, thus completing distributed consensus,
wherein the consensus quorum is 2f+1, where f is an integer of 1 or more,
wherein f satisfies both a first condition and a second condition,
wherein the first condition is a condition satisfied in a case where, when the congress candidate nodes are selected from among all nodes of the blockchain with a probability of p (where p is a real number that is equal to or greater than 0 and is less than or equal to 1), a first probability that a number of Byzantine nodes to be selected as the congress candidate nodes will be greater than f is less than or equal to a preset first reference probability, and
wherein the second condition is a condition satisfied in a case where a second probability that a number of congress candidate nodes will be less than or equal to 3f is less than or equal to a preset second reference probability.

### Claim 12 (depends on 11)

The method of claim 11, wherein determining the congress candidate nodes to be the consensus nodes is configured to:
receive the delegate request messages along with next consensus group messages, each including information indicating whether a corresponding node has been selected as the congress candidate node, from all nodes, and
when a number of nodes that sent the next consensus group messages is 3f+1 or more, select 3f+1 nodes and determine the selected nodes to be the congress candidate nodes for a next distributed consensus, whereas when the number of nodes that sent the next consensus group messages is less than or equal to 3f, not update the congress candidate nodes.

### Claim 13 (depends on 12)

The method of claim 12, wherein determining the congress candidate nodes to be the consensus nodes is configured to, when a number of delegate request messages forming the consensus quorum are received, determine the second transaction based on identical f+1 first transactions included in the delegate request messages forming the consensus quorum.

### Claim 14 (depends on 12)

The method of claim 12, wherein sending the prepare message is configured to generate first bitmap information corresponding to the first transactions of the congress candidate nodes and second bitmap information including the results of determination of the consensus nodes, and to generate the prepare message including the first bitmap information, the second bitmap information, and the second transaction.

### Claim 15 (depends on 14)

The method of claim 14, wherein sending the prepare message is configured such that each of the consensus nodes checks a validity of the prepare message based on whether the first bitmap information corresponds to the second transaction.

### Claim 16 (depends on 15)

The method of claim 15, wherein sending the prepare message is configured to generate a first aggregated public key and a first aggregated quorum value by respectively aggregating public keys and quorum values included in the delegate request messages, and to generate the prepare message further including a first hash value obtained by hashing the first aggregated public key and the first aggregated quorum value.

### Claim 17 (depends on 16)

The method of claim 16, wherein sending the prepare message is configured to generate a second aggregated public key and a second aggregated quorum value by respectively aggregating previously registered public keys and previously registered quorum values, and to compare a second hash value, obtained by hashing the second aggregated public key and the second aggregated quorum value, with the first hash value as to whether the second hash value is identical to the first hash value, thus checking the validity of the prepare message.

### Claim 18 (depends on 17)

The method of claim 17, wherein completing the distributed consensus is configured to, when the second hash value is identical to the first hash value, generate a signature value including the first hash value and a secret value prestored in the corresponding consensus node, include the signature value in the prepare message, and generate a corresponding commit message by adding the electronic signature based on the signature value to the prepare message.

### Claim 19 (depends on 18)

The method of claim 18, wherein completing the distributed consensus is configured to generate a multi-signature from the electronic signatures by respectively aggregating the signature values included in the commit messages, public keys of the first aggregated public key, and quorum values of the first aggregated quorum value in a form of a signature value tree of the multi-signature, a public key tree of the multi-signature, and a quorum value tree of the multi-signature.

### Claim 20 (depends on 19)

The method of claim 19, wherein completing the distributed consensus is configured to, when a result of verification of the multi-signature is true, generate the reply message including the second transaction and the multi-signature.
