KR102835086B1 - System, apparatus, and method for storing byzantine fault tolerant block data utilizing external storage - Google Patents

Abstract

A method and device for storing Byzantine fault-tolerant block data using an external storage device. The device reads block data from an arbitrary blockchain node on a blockchain platform, and conducts BFT consensus on the block data by exchanging consensus messages between separately configured S-nodes. In the case of block data for which BFT consensus has been completed, each S-node generates metadata corresponding to the block, and uses the metadata as proof information that the block data has been agreed upon by the S-node. A representative primary S-node records the block and metadata in external storage, and when receiving data thereafter, consensus verification for the corresponding block is performed based on the metadata.

Description

{SYSTEM, APPARATUS, AND METHOD FOR STORING BYZANTINE FAULT TOLERANT BLOCK DATA UTILIZING EXTERNAL STORAGE}

The present invention relates to a method and device for storing block data in a blockchain network, and more specifically, to a method for storing block data having Byzantine fault tolerance using an external storage device.

The material described in this section merely provides background information for the present embodiment and does not constitute prior art.

Recently, blockchain technology has emerged as a key technology for storing data reliably. Blockchain refers to a technology in which data such as transaction history is distributed and stored and processed by users participating in the network. Examples of platforms that are actually applying blockchain technology include Bitcoin, Ethereum, EOS, Algorand, Hedera, Hyperledger Fabric, and IOTA.

While blockchain has the advantage that all network participants can share and verify different data, it also has problems in terms of storage. For example, in the case of nodes with limited storage capacity, each database they own is quickly saturated (i.e. storage overhead). In particular, when operating a blockchain platform in an Internet Of Things (IoT) environment, the storage overhead problem becomes more severe because the blockchain platform must be integrated with low-level, resource-constrained devices.

To solve storage overhead, each blockchain platform stores only some verifiable data. In the case of Ethereum, a full node transmits and processes blockchain transactions, and only stores the state for the most recent 128 blocks. IOTA uses local snapshot technology to persist only the resulting state of the ledger. After selecting a transaction that has already been verified, it deletes all transactions referencing that transaction. Solana also uses snapshots to maintain the intermediate state of the ledger.

However, there are institutional regulations for block data on each platform, which require that all data be stored for a long period of time. For example, payment-related data must be maintained for a certain period of time, and identity-related data must be maintained until the identity is destroyed.

Each blockchain platform has proposed a new type of blockchain storage-specific node according to storage needs. In the case of Ethereum, in addition to the full node that transmits and processes blockchain transactions according to the storage requirements of block data, it supports archive nodes for all block storage purposes starting from the genesis block. IOTA performs storage in transaction units, stores transaction data through Permanode, and selectively stores necessary transactions through the StoreTransaction API. In Solana, all nodes participating in the blockchain node store all blocks. Solana operates a separate node called archivers for the purpose of distributed storage of block data.

However, in order to verify block data stored in each node or external storage, it is required to receive all data before the block data to be verified according to the hash chain property. Since at least a part of the blockchain network consists of untrusted blockchain nodes, there is a problem that it is difficult for each node to properly respond to storage problems when a blockchain node has a Byzantine fault.

Korean Patent Publication No. KR 10-2022-0035823 "Byzantine fault tolerance device and method in blockchain platform" (Published on March 22, 202)

Fjl, Iceberg [Online], Available: https://github.com/ethereum/go-ethereum/releases/tag/v1.8.0 (February 2018) IOTA (2022) [Online], Available: https://iota.org Snapshot Verification (2022) [Online], Available: https://docs.solana.com/proposals/snapshot-verification Stefano Della Valle, IOTA Permanode As a Service [Online], Available: https://medium.com/things-lab/iota-permanode-as-a-service-b907216c6931 (April 2020)

The purpose of the present invention to solve the above problems is to provide a method and device for storing Byzantine fault-tolerant block data by utilizing an external storage device while satisfying the requirements for data storage of an existing blockchain platform without relying on a node specialized in blockchain block data storage.

Specifically, the present invention aims to propose a large-scale transaction data distributed storage service (Blockchain Storage Service, hereinafter referred to as BSS) that provides a solution to problems in terms of storage on a blockchain platform while also providing Byzantine fault tolerance characteristics on the platform. At this time, the contents of the block data Byzantine fault tolerance guarantee applied within the BSS can be proposed together.

The purpose of the present invention is to propose an S-node concept capable of block data consensus even without guaranteeing the reliability of a blockchain storage specialized node, and to provide a block data storage technique capable of performing block data verification.

The purpose of the present invention is to provide a block data storage technique capable of block data agreement and storage using only block data generated on a blockchain platform without relying on a specific blockchain platform.

The present invention aims to provide a block data storage technique that can be linked with the latest distributed storage technology without relying on specific storage or cloud technology.

The present invention proposes a concept of consensus messages exchanged between S-nodes and metadata stored by S-nodes, and thereby provides a block data storage technique that minimizes the storage overhead found in existing blockchain platforms.

The present invention secures compatibility with various blockchain platforms and storage technologies by designing consensus messages and metadata information to be expandable. Accordingly, the purpose is to provide a block data storage technique that can be utilized in fields that require consensus between nodes and block data storage, such as transaction systems, voting applications, and supply chain management systems.

According to one embodiment of the present invention, a Byzantine fault-tolerant block data storage system utilizing an external storage device for achieving the purpose of the present invention includes: a first entity set including a plurality of first entities which receive a first blockchain block from a blockchain node, perform Byzantine fault-tolerant (BFT) consensus on block data of the first blockchain block, and collect consensus messages for the first blockchain block on which consensus has been performed to generate first blockchain block metadata; and at least one second entity which receives and stores the first blockchain block on which consensus has been performed and the first blockchain block metadata from the first entity set.

A first entity set may provide a Blockchain Storage Service (BSS) that transmits agreed-upon block data for the first blockchain block to blockchain nodes.

A first entity set may include a plurality of S-nodes, as the plurality of first entities, storing metadata for consensus on block data and data verification. Within the first entity set, one of the plurality of S-nodes may be selected as a primary S-node, and a BFT consensus on a block may be performed by transmitting and receiving a block consensus message between the plurality of S-nodes within the first entity set, and the primary S-node may propagate a block on which BFT consensus has been performed between the plurality of S-nodes to at least one second entity, and may propagate block metadata generated by collecting consensus messages for the block on which BFT consensus has been performed between the plurality of S-nodes to at least one second entity.

At least one of the second entities may include an external storage for storing block data and metadata, and the at least one of the second entities may receive block data and metadata from the first entity set, verify the block data based on the metadata information, and store the block data and metadata.

Each of the plurality of S-nodes may include a block cache that temporarily stores blocks received from blockchain nodes; a message cache that temporarily stores consensus messages exchanged with other S-nodes; a generator that generates consensus messages and propagates them to other S-nodes; an analyzer that determines a consensus state for a block based on consensus messages received from other S-nodes; and a persistent metadata store that stores generated metadata after consensus for a block is completed.

Within a plurality of first entity sets, a plurality of S-nodes can perform a Byzantine agreement protocol, a blockchain node change protocol (BN change protocol), and a primary change protocol.

A consensus message exchanged by a Byzantine agreement protocol may include a block height (h), a block hash signed by a blockchain node, a blockchain node number, an S-node identifier (ID), and an S-node signature, and block metadata exchanged by the Byzantine agreement protocol may include a block height (h), a previous height block hash, a block hash signed by an S-node, an S-node identifier, and a list of consensus messages for the block.

A blockchain node change message exchanged by the blockchain node change protocol may include a round number (r), a most recent prepared block height (hp), a most recent prepared block hash signed by the blockchain node, a set of consensus messages at the most recent prepared block height, a blockchain node number, a blockchain node number at hp, an S-node identifier, and an S-node signature. A new blockchain node proposal message exchanged by the blockchain node change protocol may include a round number (r), a most recent prepared block height (hp), a most recent prepared block hash signed by the blockchain node, a blockchain node number, a blockchain node number at hp, a list of blocks from the lowest hp to the highest hp, an S-node identifier, and an S-node signature.

The Byzantine consensus protocol may include a primary S-node selection step; a block data verification and consensus message exchange step; a consensus message verification and block consensus state determination step; and a metadata and block storage step.

The primary change protocol may include the steps of: detecting that a consensus message has not arrived after a certain period of time; transmitting the consensus message to another primary S-node; and doubling the consensus time.

The blockchain node change protocol may include the steps of: detecting a malicious blockchain node; exchanging a blockchain node change message; exchanging a new blockchain node proposal message; and exchanging a consensus message for blockchain node replacement.

The steps for detecting a malicious blockchain node may include a detection process that starts a blockchain node change protocol when 1) a pair of consensus messages with different block hash values are received, 2) the hash value generated based on the block broadcast by the primary S-node is different, or a block does not arrive from the blockchain node after a certain period of time.

A method for storing Byzantine fault-tolerant block data using an external storage device according to one embodiment of the present invention includes: receiving a first blockchain block from a blockchain node by a plurality of S-nodes in a plurality of first entity sets; performing Byzantine fault-tolerant (BFT) consensus on block data of the first blockchain block by the plurality of S-nodes; collecting consensus messages for the first blockchain block on which consensus has been performed by primary S-nodes in the plurality of first entity sets to generate first blockchain block metadata; and receiving and storing the first blockchain block on which consensus has been performed and the first blockchain block metadata from the first entity set by at least one second entity.

A method for storing Byzantine fault-tolerant block data utilizing an external storage device according to one embodiment of the present invention may further include a step of providing a Blockchain Storage Service (BSS) that transmits agreed-upon block data for a first blockchain block to a blockchain node by a plurality of S-nodes.

A method for storing Byzantine fault-tolerant block data using an external storage device according to one embodiment of the present invention may further include a step of selecting a primary S-node from among a plurality of S-nodes; a step of the primary S-node propagating a block on which a BFT agreement is performed between the plurality of S-nodes to at least one or more second entities; and a step of the primary S-node propagating first blockchain block metadata to at least one or more second entities.

In the step of performing Byzantine fault tolerant (BFT) consensus on block data of the first blockchain block by multiple S-nodes, multiple S-nodes can perform a Byzantine consensus protocol, a blockchain node change protocol (BN change protocol), and a primary change protocol based on the BFT consensus.

The step of receiving and storing the first blockchain block and the first blockchain block metadata by at least one or more second entities may include the step of verifying the first blockchain block based on the first blockchain block metadata by the at least one or more second entities; and the step of storing the verified first blockchain block and the first blockchain block metadata in the at least one or more second entities.

A Byzantine fault tolerant block data storage device utilizing an external storage device according to one embodiment of the present invention receives a first blockchain block from a blockchain node, communicates with a plurality of S-nodes to perform Byzantine fault tolerant (BFT) consensus on block data of the first blockchain block, collects consensus messages for the first blockchain block on which consensus has been performed by the plurality of S-nodes if the device is a primary S-node, and generates first blockchain block metadata, propagates the first blockchain block on which consensus has been performed by the plurality of S-nodes and the first blockchain block metadata to an external storage, and transmits the consensus message for the first blockchain block to the primary S-node if the device is not a primary S-node.

A Byzantine fault tolerant block data storage device utilizing an external storage device according to one embodiment of the present invention can provide a blockchain storage service (BSS) that transmits agreed block data for a first blockchain block to a blockchain node.

A Byzantine fault-tolerant block data storage device utilizing an external storage device according to one embodiment of the present invention may include a block cache that temporarily stores a block received from a blockchain node; a message cache that temporarily stores consensus messages exchanged with other S-nodes; a generator that generates consensus messages and propagates them to other S-nodes; an analyzer that determines an consensus state for a block based on consensus messages received from other S-nodes; and a persistent metadata store that stores generated metadata after consensus for a block is completed.

A Byzantine-resistant block data storage technique utilizing an external storage device according to one embodiment of the present invention can satisfy the data storage requirements of an existing blockchain platform without relying on a blockchain block data storage specialized node.

A Byzantine-resistant block data storage technique utilizing an external storage device according to one embodiment of the present invention can respond to a system Byzantine failure by performing a Byzantine agreement between S-nodes.

A Byzantine-resistant block data storage technique utilizing an external storage device according to one embodiment of the present invention can perform block data consensus and block data verification even without guaranteeing the reliability of a blockchain storage specialized node.

A Byzantine-resistant block data storage technique utilizing an external storage device according to one embodiment of the present invention is designed not to depend on a specific blockchain platform, and thus block data consensus and storage are possible using only block data generated on a blockchain platform.

A Byzantine-resistant block data storage technique utilizing an external storage device according to one embodiment of the present invention is designed not to depend on specific storage or cloud technologies, and can be linked with the latest distributed storage technologies.

A Byzantine-resistant block data storage technique utilizing an external storage device according to one embodiment of the present invention minimizes storage overhead that appears in existing blockchain platforms by utilizing consensus messages exchanged between S-nodes and metadata stored by S-nodes.

A Byzantine-resistant block data storage technique utilizing an external storage device according to one embodiment of the present invention is designed to allow expansion of consensus messages and metadata information, thereby being compatible with various blockchain platforms and storage technologies through subsequent addition of attribute information.

A Byzantine-resistant block data storage technique utilizing an external storage device according to one embodiment of the present invention can be applied to fields requiring inter-node consensus and block data storage, such as transaction systems, voting applications, and supply chain management (supply chain) systems.

FIG. 1 is a schematic block diagram of a blockchain network system implementing a Byzantine fault tolerant block data storage method according to one embodiment of the present invention.
FIG. 2 is a block diagram illustrating the structure and operation of an S-node according to one embodiment of the present invention.
FIG. 3 is a diagram illustrating an example of the structure of an agreement message and block metadata according to one embodiment of the present invention.
FIG. 4 is a diagram illustrating an example of the structure of a BN change message and a New BN Proposal according to one embodiment of the present invention.
FIG. 5 is a diagram illustrating an example of a message pattern according to a Byzantine agreement protocol according to one embodiment of the present invention.
FIG. 6 is a diagram illustrating an example of a message pattern according to a BN change protocol according to one embodiment of the present invention.
FIG. 7 is a diagram illustrating an example of a message pattern according to a primary change protocol according to one embodiment of the present invention.
FIG. 8 is a diagram illustrating storage overhead according to one embodiment of the present invention compared to existing Ethereum and block space partitioning techniques (ECC).
FIG. 9 is a conceptual diagram illustrating an example of a computing system that constitutes a generalized blockchain node, S-node, or external storage capable of performing at least a portion of the processes of FIGS. 1 through 8.

The present invention can have various modifications and various embodiments, and specific embodiments are illustrated in the drawings and described in detail. However, this is not intended to limit the present invention to specific embodiments, but should be understood to include all modifications, equivalents, or substitutes included in the spirit and technical scope of the present invention.

The terms first, second, etc. may be used to describe various components, but the components should not be limited by the terms. The terms are only used to distinguish one component from another. For example, without departing from the scope of the present invention, the first component could be referred to as the second component, and similarly, the second component could also be referred to as the first component. The term "and/or" includes any combination of a plurality of related listed items or any item among a plurality of related listed items.

In the embodiments of the present application, “at least one of A and B” can mean “at least one of A or B” or “at least one of combinations of one or more of A and B.” Furthermore, in the embodiments of the present application, “at least one of A and B” can mean “at least one of A or B” or “at least one of combinations of one or more of A and B.”

When it is said that a component is "connected" or "connected" to another component, it should be understood that it may be directly connected or connected to that other component, but that there may be other components in between. On the other hand, when it is said that a component is "directly connected" or "directly connected" to another component, it should be understood that there are no other components in between.

The terminology used in this application is only used to describe specific embodiments and is not intended to limit the present invention. The singular expression includes the plural expression unless the context clearly indicates otherwise. In this application, it should be understood that the terms "comprises" or "has" and the like are intended to specify the presence of a feature, number, step, operation, component, part or combination thereof described in the specification, but do not exclude in advance the possibility of the presence or addition of one or more other features, numbers, steps, operations, components, parts or combinations thereof.

Unless otherwise defined, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Terms defined in commonly used dictionaries, such as those defined in common dictionaries, should be interpreted as having a meaning consistent with the meaning they have in the context of the relevant art, and will not be interpreted in an idealized or overly formal sense unless expressly defined in this application.

Meanwhile, even if it is a technology known prior to the filing date of this application, it may be included as a part of the composition of the invention of this application if necessary, and this will be described in this specification within the scope that does not obscure the purpose of the invention. However, in explaining the composition of the invention of this application, a detailed description of matters that were known prior to the filing date of this application and could be clearly understood by those skilled in the art may obscure the purpose of the invention, and therefore, an excessively detailed description of the known technology will be omitted.

For example, technologies for implementing Byzantine Fault Tolerance (BFT) consensus can utilize technologies known prior to the filing of the present invention, and at least some of these known technologies can be applied as element technologies necessary for implementing the present invention.

However, the purpose of the present invention is not to claim rights to these known technologies, and the contents of the known technologies may be included as part of the present invention within a scope that does not deviate from the purpose of the present invention.

Hereinafter, with reference to the attached drawings, a preferred embodiment of the present invention will be described in more detail. In order to facilitate an overall understanding in describing the present invention, the same reference numerals are used for the same components in the drawings, and redundant descriptions of the same components are omitted.

The present invention relates to a method and device for storing block data in a blockchain network, and more particularly, to a method for storing block data with Byzantine fault tolerance by utilizing an external storage device. In particular, the present invention proposes a blockchain storage service structure with Byzantine fault tolerance, and relates to a technology for storing block data.

A Byzantine fault-tolerant blockchain storage service utilizing an external storage device according to one embodiment of the present invention includes a first entity, which is an S-node that stores metadata for consensus on block data and data verification; and a second entity, which is an external storage that stores block data and metadata.

The first entity can proceed with BFT consensus on the block data after receiving a blockchain block from an arbitrary blockchain node (i.e. BSS client). BFT consensus is performed by exchanging block consensus messages between each S-node. After BFT consensus on one block data is completed, each S-node collects consensus messages and creates BFT block metadata.

The second entity receives block data and metadata from the first entity, verifies the block data based on the metadata information, and performs a process of storing the block data and metadata.

A Byzantine fault-tolerant blockchain storage service utilizing an external storage device according to an embodiment of the present invention can sufficiently increase the number of S-nodes corresponding to a first entity for availability of block data. A Byzantine fault-tolerant blockchain storage service according to an embodiment of the present invention can be designed to provide a similar level of availability to existing storage services. For example, five-nine, i.e., 99.999% block data availability can be provided by an embodiment of the present invention.

In a Byzantine fault tolerant blockchain storage service according to one embodiment of the present invention, reliability may increase as the number of S-nodes increases. Reliability may increase as the probability of success in reaching an agreement on a blockchain block increases.

Blockchain nodes can receive agreed-upon block data by using blockchain storage services.

FIG. 1 is a schematic block diagram of a blockchain network system implementing a Byzantine fault tolerant block data storage method according to one embodiment of the present invention. The blockchain network system processes transactions from a client and stores the transactions in the form of block data. The blockchain network system includes a blockchain service client (not shown), a blockchain platform (100), and a blockchain storage service (BSS: Blockchain Storage Service) system (200).

A client (not shown) is a user who uses a blockchain platform (100). When a client transmits a client transaction to the blockchain platform (100), the blockchain platform (100) bundles data related to the transaction and stores it in the form of block data. The blockchain platform (100) includes a blockchain node (110). The blockchain node (110) may include a smart contract and a blockchain block (121). A blockchain (120) may be formed by connecting blockchain blocks (121). The blockchain nodes (110) may directly perform client transactions transmitted from the client, bundle the results of the performance, and store them in the form of block data.

The BSS system (200) includes a set (210) of storage nodes (S-nodes. 210a, 210b) and an external storage (220). The S-nodes (210a, 210b) may be expressed as a first entity, the S-node set (210) may be expressed as a first entity set, and the external storage (220) may be expressed as a second entity. At this time, the S-node set (210) includes a plurality of S-nodes (210a, 210b) that derive an agreement process internally, and the external storage (220) may be implemented as at least one module or element.

The S-node set (210) includes a plurality of S-nodes (210a, 210b). Each S-node (210a, 210b) receives a blockchain block B (121) from one or more blockchain nodes (110) and proceeds with an agreement on the data of the corresponding block (121) by exchanging a block agreement message (α _h ) with other S-nodes (210a, 210b). After the BFT agreement on the data of one block (121) is completed, each S-node (210a, 210b) can collect the agreement messages to generate block metadata.

S-nodes (210a, 210b) within the S-node set (210) can perform BFT consensus by generating consensus messages and exchanging consensus messages with each other. In this respect, the configuration of the present invention is differentiated from the conventional technologies, and the computational and storage load of the blockchain nodes (110) can be reduced by performing the BFT consensus performed by the blockchain nodes (110) within the S-node set (210).

S-nodes (210a, 210b) within the S-node set (210) verify all block (121) data transmitted from the blockchain node (110) and block metadata previously generated for the block (121), and such verification may be essential in the consensus process.

S-nodes (210a, 210b) within the S-node set (210) store block metadata newly generated based on the consensus result, and all block data and block metadata can be stored in external storage/external storage (220).

S-nodes (210a, 210b) within the S-node set (210) may include a primary S-node (210a) that collects consensus messages according to their roles and transmits them to external storage (220), and a general S-node (210b) that transmits consensus messages to the primary S-node (210a).

Both the Primary S-node (210a) and the general S-node (210b) participate in the consensus process, and for example, as shown in Fig. 1, the Primary S-node (210a) and the general S-node (210b) can be implemented by forming a kind of circular network. Both the Primary S-node (210a) and the general S-node (210b) participating in the consensus can generate consensus messages.

The entity that provides the BSS service to the blockchain node (110) is the S-node set (210), and at this time, the blockchain node (110) can be considered as a provider of the blockchain service to the user and as a client of the BSS service in its relationship with the S-node set (210).

In the relationship with the blockchain node (110), since each S-node (210a, 210b) in the S-node set (210) corresponds to the transaction of the blockchain node (110), the entity that provides the BSS service to the blockchain node (110) can be interpreted as the S-node set (210). Meanwhile, in the relationship between the S-node set (210) and external storage (220), the primary S-node (210a) can collect consensus messages and metadata and transmit them to the external storage (220), thereby performing a kind of hub role.

An S-node set (210) is positioned between a blockchain node (110) and an external storage (220), so that the external storage (220) interacts with the blockchain node (110) via the S-node set (210), and the blockchain node (110) may not be aware of the existence of the external storage (220).

The S-node set (210) performs an agreement on a block received from a blockchain node (110) and then transmits the agreed block data to the blockchain node (110), which can be interpreted as providing a BSS service.

External storage (220) is an external storage that receives and stores blocks (121) and metadata from a set of S-nodes (210).

A blockchain node (BSS client) can support two interfaces: the AddBlock(B _h ) interface and the GetBlockByNumber (h) interface: The AddBlock(B _h ) interface writes a block B _h to the BSS. AddBlock(B _h ) returns a consensus result from the BSS. GetBlockByNumber(h) reads a block B _h with height h stored on the BSS.

Each S-node generates metadata M _h for the purpose of verifying whether the block B _h satisfies the global predicate P _h . In this specification, P _h is set to "whether a consensus result for the block can be derived by nf or more S-nodes."

Here, n represents the number of S-nodes, and f can be a value determined based on the Byzantine tolerance.

Each S-node can support five operations: The key h is defined as the block height. write( ) is a block Metadata used in agreement with Writes metadata to external storage returns valid( )silver If it has valid information, it returns true. read( is write( ) was preceded by a block is received from external storage. read_causal( ) is a block All blocks of previous height is received from external storage. Finally, audit(h) is received from external storage. Metadata associated with Receive.

In the following description, we assume that malicious nodes (i.e. replica or blockchain nodes) can cause general node failures. However, we assume that malicious nodes cannot violate cryptographic techniques (i.e. collision-resistant hashes, signatures).

The system of the present invention satisfies two security properties. It satisfies the safety and liveness properties until at most f replicas are malicious nodes. Additionally, we assume that a finite number of blockchain nodes are malicious.

- Safety: All normal nodes cannot commit different blocks for the same height.

- Liveness: At least one block consensus result at a certain height is guaranteed to be reached at some point.

In a system according to one embodiment of the present invention, the safety and liveness properties assume a partially synchronous network where nodes can have byzantine faults (i.e., not sending messages or sending conflicting messages). In a partially synchronous network, a message propagated therethrough is ultimately transmitted within a fixed but unknown time bound.

Accordingly, BSS satisfies the following additional properties:

- Integrity: Two different reads (called by a normal S-node) ) is the same if the external storage is normal. Returns .

- Block Availability: write( by a normal primary S-node) ) and then read from a normal S-node ( ) is called, read( ) is finally executed, and if external storage is normal, Returns .

- Containment: read_causal( ) A set of blocks returned from About ( ), read_causal( ) returned from ( )silver Satisfies .

- Causality: read_causal( ) is committed write( about ) before it is performed, at least Contains all blocks committed by honest S-nodes.

- External validity: If a normal S-node blocks To derive consensus results on metadata If you created it, is true.

At least some of the concepts of the above properties have been disclosed in the prior art literature. For example, Danezis, G., Kokoris-Kogias, L., Sonnino, A., & Spiegelman, A. (2022, March). Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. In Proceedings of the Seventeenth European Conference on Computer Systems (pp. 34-50) presented block availability, containment, and causality properties as system properties. Also, C. Cachin, K. Kursawe, F. Petzold, and V. Shoup. Secure and efficient asynchronous broadcast protocols. In Proc. of the 21st Annual Int. Cryptology Conf. on Advances in Cryptology - CRYPTO'01, 2001 first proposed external validity. J. Sousa and A. Bessani, "From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation," in Ninth European Dependable Computing Conference, 2012, pp. 37-48, doi: 10.1109/EDCC.2012.32. and S. Duan and H. Zhang, "PACE: Fully Parallelizable BFT from Reproposable Byzantine Agreement." Cryptology ePrint Archive (2022) mentioned external validity as a characteristic of their system. However, the present invention did not use the above concepts as they are, but modified the definition of each characteristic so that it can be applied to BSS.

Figure 2 is a block diagram illustrating the structure and operation of each S-node (210a, 210b) within the S-node set (210). The S-nodes (210a, 210b) within the S-node set (210) may include a Primary S-node (210a) that generates a consensus message and collects and propagates the exchanged consensus messages, and a general S-node (210b) that generates a consensus message and propagates the generated consensus message to the Primary S-node (210a).

For convenience of explanation, in Fig. 2, a general S-node (210b) is illustrated as including a block cache (211), a message cache (212), a generator (213), an analyzer (214), and a persistent metadata cache (215), but the structure of the primary S-node (210a) can also be implemented in the same manner as the general S-node (210b). Which S-node is the primary S-node (210a) and which S-node is the general S-node (210b) is not determined from the beginning, and depending on the situation, it can be sequentially designated as the primary S-node (210a) using a round robin method, etc.

Each S-node (210a, 210b) may include a block cache (211), a message cache (212), a generator (213), an analyzer (214), and a persistent metadata cache (215). The block cache (211) temporarily stores a block received from a blockchain node (110). The message cache (212) temporarily stores an exchanged consensus message. The generator (213) generates and propagates a consensus message. The analyzer (214) determines an consensus state for a block based on the received consensus message. The persistent metadata store (215) stores the generated metadata after an agreement on a block is completed.

Each S-node (210a, 210b) can sequentially perform the following operations.

First, a block is received from a blockchain node (110) (S230). The propagated block is temporarily stored in the block cache (211), and the block cache notifies the generator (213) of the block reception (S231a), and the analyzer pulls the block from the block cache (S231b). Thereafter, the generator (213) submits a consensus message for the received block to the primary S-node (210a) (S232a). The primary S-node (210a) propagates a set of consensus messages to an external storage (220) (S232b). The S-nodes (210a, 210b) receive the consensus message (S233a), temporarily store it in the message cache (212), and notifies the analyzer (214) of the consensus message reception (S234). The analyzer (214) determines the consensus state based on the received consensus message, and stores metadata in a persistent metadata store (215) (S235a). Analyzer (214) stores blocks and metadata in external storage (220) immediately after agreement is concluded (S235b).

In Fig. 2, this operation is illustrated with a focus on a general S-node (210b), but a primary S-node (210a) can also participate in the consensus process by receiving a block from a blockchain node (110) (S230) just like a general S-node (210b). However, the primary S-node (210a) differs from a general S-node (210b) in that instead of performing a process of submitting a consensus message to itself (S232a), it collects consensus messages from a general S-node (210b) (S232a) and transmits a set of consensus messages to external storage (220) (S232b).

Each S-node (210) can maintain the consensus state of a block for a specific height in one of three stages through block data consensus. The consensus state of a block B _h for height h can be divided into three stages: Level-0 (also called 'None' state), Level-1 (also called 'Prepared' state), and Level-2 (also called 'Committed' state).

Level-0 (None): Block B _h from blockchain node and block hash signed by blockchain node BN has been received.

Level-1 (Prepared): S-node in None state receives nf or more consensus messages This is the status when it is received.

Level-2 (Committed): S-node has nf or more consensus messages in the Prepared state. This is the status when it is received.

Fig. 3 illustrates an example of the format of a consensus message (230) and block metadata (240) on the Byzantine agreement protocol. The message properties can be expanded depending on the blockchain platform (100) and the external storage (220). S-nodes (210) maintain the consensus state for a block and perform an audit protocol or Byzantine agreement protocol after receiving a block from a blockchain node (110) to proceed with the consensus. There are two messages on the audit protocol or Byzantine agreement protocol: 1) Consensus Message (330) and 2) Metadata (340) can be defined.

h is the block height (331, 341), H(B _h ) is the block hash (332, 343) signed by the blockchain node BN, is the number (view number) (333) for the blockchain receiving the current block, is S-node ID(334, 344), silver A list of consensus messages (345) that changed the consensus state to committed, H _prev is the previous height block hash (342), is the signature of the blockchain node (332), means S-node signature (335, 343).

When malicious behavior of a blockchain node is discovered by an audit protocol or Byzantine agreement protocol, the BN (Blockchain Node) change protocol is initiated.

Fig. 4 illustrates an example of the format of a BN change message (250) and a New BN Proposal (260) exchanged according to the BN change protocol. The message properties can be expanded according to the blockchain platform (100) and the external storage (220). There are two messages on the BN change protocol:

(1) BN Change Message ,

(2) New BN Proposal can be defined.

r is the primary decision round number (251, 261) for collecting and propagating messages in the BN change protocol, h _p is the highest prepared block height (252, 262), is h _p Block of height Hash(253, 263), is a set of consensus messages (254) of height h _p , is a new blockchain node number (255, 264), is the blockchain node number at h _p height (256, 265), is S-node ID(257, 267), is an S-node signature (258, 268), is nf or more It means a set (266). can mean blocks from lowest hp to highest hp.

Each S-node (210) performs the Byzantine agreement protocol, BN change protocol, and Primary change protocol. Each node performs the Byzantine agreement protocol for block agreement and write functions. After performing the Byzantine agreement protocol over two phases, each S-node performs the block To arrive at a consensus on the results.

The blockchain nodes, each S-node, and the blockchain storage subsystem (i.e., the external storage subsystem) perform the audit protocol and the view change protocol. Each node performs the audit protocol (or Byzantine agreement protocol) for block consensus and write functions. After performing the audit protocol over two phases, each S-node To arrive at a consensus on the results.

Fig. 5 illustrates an example of a message pattern according to the Byzantine agreement protocol. The role of the primary S-node (210a) includes the process of writing a block agreed upon between S-nodes (210b) to external storage (220) and collecting and propagating an agreement message (230). One primary S-node (210a) can be selected in a round-robin manner for each agreement round.

Each S-node (210) receives a block from one of the blockchain nodes. and block hash signed by blockchain node (110). Receive.

Each S-node (210) transmits a consensus message to the primary S-node (210a) after block signature verification and hash chain verification (230a). The primary S-node (210a) collects the consensus messages (230a). Same block When more than nf consensus messages are collected, the primary S-node (210a) propagates the consensus message set to the S-nodes (230b).

Even a single pair of consensus messages for blocks of the same height are different. If it has, it broadcasts the corresponding consensus message pair to the S-nodes. In addition, the primary S-node broadcasts the consensus messages submitted by other nodes. To prevent the generation of consensus messages based on the primary S-node, the primary S-node must be in the background Broadcast.

The problem of consensus messages not arriving even after a certain amount of time can be solved by (1) changing the primary S-node (see Figure 7) and (2) doubling the time it takes to wait for a consensus message.

FIG. 7 is a diagram illustrating an example of a message pattern according to a primary change protocol according to one embodiment of the present invention.

Referring to FIG. 5 and FIG. 7 together, each S-node (210b) receives a block height from the primary S-node (210a). If you confirm more than one valid consensus message (230b), you change the consensus state for the block you have. For a higher height. If more than one valid consensus message is confirmed, it changes the consensus state for all blocks of lower height than the block of that height. Since all blocks are linked by hash pointers, consensus on a block of a higher height guarantees consensus on blocks of lower heights.

Figure 6 illustrates an example of a message pattern according to the BN change protocol. Each S-node (210b) (1) has different Receives a pair of consensus messages having (2) a primary S-node (210a) broadcast Created based on and If this is different, or (3) a block does not arrive from the blockchain node (110) for a certain period of time, a BN change message (250) is submitted to another assigned Primary S-node (210a). The Primary S-node (210a) selects the largest h _p based on the BN change messages (250) it has received. , and generates and propagates a new BN proposal (260). Other S-nodes (210b) vote for the new BN proposal (260) by exchanging consensus messages (230). When the S-node (210b) collects the nf consensus message (230), it moves on to the next blockchain node.

FIG. 8 illustrates the storage overhead according to one embodiment of the present invention in comparison with the existing Ethereum and block space partitioning technique (ECC). In the case of ECC, since metadata is not managed separately and only blocks are partitioned and managed, it can be confirmed that the Ethereum storage overhead is calculated to be lower than that of the present invention. However, due to the characteristics of the ECC technique that partitions and manages block data, it may work more unfavorably than the embodiments of the present invention in terms of block availability such as block recovery. In the embodiments of the present invention, block availability has the characteristic of being bound to the availability value of external storage.

FIG. 9 is a conceptual diagram illustrating an example of a computing system that constitutes a generalized blockchain node, S-node, or external storage capable of performing at least a portion of the processes of FIGS. 1 through 8.

In the embodiments of FIGS. 1 to 8, although omitted in the drawings, a processor and a memory are electronically connected to each component, and the operation of each component can be controlled or managed by the processor.

At least a portion of the process of the method according to one embodiment of the present invention can be executed by the computing system (1000) of FIG. 9.

Referring to FIG. 9, a computing system (1000) according to one embodiment of the present invention may be configured to include a processor (1100), a memory (1200), a communication interface (1300), a storage device (1400), an input interface (1500), an output interface (1600), and a bus (1700).

A computing system (1000) according to one embodiment of the present invention may include at least one processor (1100) and a memory (1200) storing instructions that instruct the at least one processor (1100) to perform at least one step. At least some steps of a method according to one embodiment of the present invention may be performed by the at least one processor (1100) loading and executing instructions from the memory (1200).

The processor (1100) may mean a central processing unit (CPU), a graphics processing unit (GPU), or a dedicated processor on which methods according to embodiments of the present invention are performed.

Each of the memory (1200) and the storage device (1400) may be configured with at least one of a volatile storage medium and a nonvolatile storage medium. For example, the memory (1200) may be configured with at least one of a read only memory (ROM) and a random access memory (RAM).

Additionally, the computing system (1000) may include a communication interface (1300) that performs communication via a wireless network.

Additionally, the computing system (1000) may further include a storage device (1400), an input interface (1500), an output interface (1600), etc.

Additionally, each component included in the computing system (1000) may be connected to each other by a bus (1700) and communicate with each other.

Examples of the computing system (1000) of the present invention may include a desktop computer, a laptop computer, a notebook, a smart phone, a tablet PC, a mobile phone, a smart watch, a smart glass, an e-book reader, a portable multimedia player (PMP), a portable game console, a navigation device, a digital camera, a digital multimedia broadcasting (DMB) player, a digital audio recorder, a digital audio player, a digital video recorder, a digital video player, a PDA (Personal Digital Assistant), etc.

The operation of the method according to an embodiment of the present invention can be implemented as a computer-readable program or code on a computer-readable recording medium. The computer-readable recording medium includes all types of recording devices that store information that can be read by a computer system. In addition, the computer-readable recording medium can be distributed over network-connected computer systems so that the computer-readable program or code can be stored and executed in a distributed manner.

Additionally, the computer-readable recording medium may include hardware devices specifically configured to store and execute program instructions, such as ROM, RAM, flash memory, etc. The program instructions may include not only machine language codes produced by a compiler, but also high-level language codes that can be executed by the computer using an interpreter, etc.

While some aspects of the invention have been described in the context of an apparatus, they may also represent a description of a corresponding method, wherein a block or device corresponds to a method step or a feature of a method step. Similarly, aspects described in the context of a method may also be represented as a feature of a corresponding block or item or a corresponding device. Some or all of the method steps may be performed by (or using) a hardware device, such as, for example, a microprocessor, a programmable computer or an electronic circuit. In some embodiments, at least one or more of the most important method steps may be performed by such a device.

In embodiments, a programmable logic device (e.g., a field-programmable gate array) may be used to perform some or all of the functions of the methods described herein. In embodiments, a field-programmable gate array may operate in conjunction with a microprocessor to perform one of the methods described herein. In general, the methods are preferably performed by some hardware device.

Although the present invention has been described above with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various modifications and changes may be made to the present invention without departing from the spirit and scope of the present invention as set forth in the claims below.

Claims (20)

A first entity set including a plurality of first entities that receive a first blockchain block from a blockchain node, perform Byzantine fault tolerant (BFT) consensus on block data of the first blockchain block, and collect consensus messages for the first blockchain block on which consensus has been performed to generate first blockchain block metadata; and
At least one second entity functioning as an external storage device that receives and stores the first blockchain block and the first blockchain block metadata on which an agreement has been performed from the first entity set;
Including,
The first entity set is located between the blockchain node and the at least one second entity that functions as the external storage device, and the at least one second entity interacts with the blockchain node via the first entity set,
The above first entity set provides a blockchain storage service (BSS) that transmits agreed block data for the first blockchain block to the blockchain node.
A Byzantine fault-tolerant block data storage system utilizing external storage devices. delete In the first paragraph,
The above first entity set includes a plurality of S-nodes as the plurality of first entities, storing metadata for consensus on block data and data verification,
Within the above first entity set, one of the plurality of S-nodes is selected as the primary S-node,
BFT consensus on a block is performed by transmitting and receiving block consensus messages between the plurality of S-nodes within the first entity set.
The primary S-node propagates a block on which BFT agreement is performed between the plurality of S-nodes to the at least one second entity, and collects consensus messages for the block on which BFT agreement is performed between the plurality of S-nodes and propagates block metadata generated by collecting the consensus messages to the at least one second entity.
A Byzantine fault-tolerant block data storage system utilizing external storage devices. In the third paragraph,
At least one of the second entities above,
Includes external storage for storing block data and metadata;
The at least one second entity receives block data and metadata from the first entity set, verifies the block data based on metadata information, and stores the block data and metadata.
A Byzantine fault-tolerant block data storage system utilizing external storage devices. In the third paragraph, each of the plurality of S-nodes
Block cache that temporarily stores blocks received from the above blockchain nodes;
Message cache that temporarily stores consensus messages exchanged with other S-nodes;
A generator that generates consensus messages and propagates them to other S-nodes;
An analyzer that determines the consensus status for a block based on consensus messages received from the other S-nodes; and
Persistent metadata store that stores the generated metadata after consensus on the block is reached;
Including,
A Byzantine fault-tolerant block data storage system utilizing external storage devices. In the third paragraph,
Within the above set of multiple first entities, the multiple S-nodes perform a Byzantine agreement protocol, a blockchain node change protocol (BN change protocol), and a primary change protocol.
A Byzantine fault-tolerant block data storage system utilizing external storage devices. In Article 6,
The consensus message exchanged by the above Byzantine agreement protocol includes a block height (h), a block hash signed by a blockchain node, a blockchain node number, an S-node identifier (ID), and an S-node signature.
The block metadata exchanged by the above Byzantine agreement protocol includes the block height (h), the previous height block hash, the block hash signed by the S-node, the S-node identifier, and the list of consensus messages for the block.
A Byzantine fault-tolerant block data storage system utilizing external storage devices. In Article 6,
The blockchain node change message exchanged by the above blockchain node change protocol includes a round number (r), the latest prepared block height (h _p ), the latest prepared block hash signed by the blockchain node, a set of consensus messages at the latest prepared block height, a blockchain node number, a blockchain node number at h _p , an S-node identifier, and an S-node signature.
A new blockchain node proposal message exchanged by the above blockchain node change protocol includes a round number (r), the latest prepared block height (h _p ), the latest prepared block hash signed by the blockchain node, the blockchain node number, the blockchain node number in h _p , a list of blocks from the lowest h _p to the highest h _p , an S-node identifier, and an S-node signature.
A Byzantine fault-tolerant block data storage system utilizing external storage devices. In Article 6,
The above Byzantine agreement protocol,
Primary S-node selection step;
Block data verification and consensus message exchange phase;
Consensus message verification and block consensus state determination step; and
Metadata and block storage phase;
A byzantine fault tolerant block data storage system utilizing an external storage device, comprising: In Article 6,
The above primary change protocol is,
A step for detecting that a consensus message has not arrived after a certain period of time;
A step of transmitting a consensus message to another primary S-node; and
Step 2: Double the consensus time;
A byzantine fault tolerant block data storage system utilizing an external storage device, comprising: In Article 6,
The above blockchain node change protocol is:
Steps to detect malicious blockchain nodes;
Steps to exchange blockchain node change messages;
Steps for exchanging new blockchain node proposal messages; and
Steps to exchange consensus messages for replacing blockchain nodes
A byzantine fault tolerant block data storage system utilizing an external storage device, comprising: In the 11th paragraph, the step of detecting the malicious blockchain node is:
Receive a pair of consensus messages with different block hash values, or
Including a detection process for starting a blockchain node change protocol if the hash value generated based on the block broadcasted by the primary S-node is different or if a block does not arrive from the blockchain node after a certain period of time.
A Byzantine fault-tolerant block data storage system utilizing external storage devices. A step of providing a Blockchain Storage Service (BSS) in which a first entity set including a plurality of first entities, which is located between a blockchain node and an external storage device, transmits agreed block data for a first blockchain block to the blockchain node; and
A step of receiving and storing the first blockchain block and the first blockchain block metadata on which an agreement has been performed from the first entity set, by at least one second entity functioning as the external storage device;
Including,
The step of providing the BSS by the first entity set is:
Providing the BSS so that the interaction between the blockchain node and the at least one second entity is performed via the first entity set,
The step of providing the BSS by the first entity set is:
A step of receiving the first blockchain block from the blockchain node by a plurality of S-nodes within the plurality of first entity sets;
A step of performing Byzantine fault tolerant (BFT) consensus on block data of the first blockchain block by the plurality of S-nodes; and
A step of generating first blockchain block metadata by collecting consensus messages for the first blockchain block on which consensus has been performed by the primary S-node within the plurality of first entity sets;
Including,
A method for storing Byzantine fault tolerant block data utilizing external storage devices. In Article 13,
A step of providing a blockchain storage service (BSS) that transmits agreed block data for the first blockchain block to the blockchain node by the plurality of S-nodes;
Including more,
A method for storing Byzantine fault tolerant block data utilizing external storage devices. In Article 13,
A step in which the primary S-node is selected from among the plurality of S-nodes;
The step of the primary S-node transmitting the block on which the BFT agreement between the plurality of S-nodes is performed to at least one second entity; and
A step in which the primary S-node propagates the first blockchain block metadata to at least one second entity;
Including more,
A method for storing Byzantine fault tolerant block data utilizing external storage devices. In Article 13,
In the step of performing Byzantine fault tolerant (BFT) consensus on the block data of the first blockchain block by the above plurality of S-nodes,
The above multiple S-nodes perform the Byzantine agreement protocol, the blockchain node change protocol (BN change protocol), and the primary change protocol based on the BFT consensus.
A method for storing Byzantine fault tolerant block data utilizing external storage devices. In Article 13,
The step of receiving and storing the first blockchain block and the first blockchain block metadata by at least one second entity,
A step of verifying the first blockchain block based on the first blockchain block metadata by at least one second entity; and
A step of storing the verified first blockchain block and the first blockchain block metadata in at least one second entity;
Including,
A method for storing Byzantine fault tolerant block data utilizing external storage devices. Located between the blockchain node and the external storage, and receives the first blockchain block from the blockchain node,
Communicate with multiple S-nodes to perform Byzantine fault tolerant (BFT) consensus on block data of the first blockchain block;
If it is a primary S-node, it collects consensus messages for the first blockchain block on which consensus has been performed by the plurality of S-nodes and generates first blockchain block metadata.
The first blockchain block and the first blockchain block metadata, on which agreement has been made by the plurality of S-nodes, are transmitted to the external storage,
By sending a consensus message for the first blockchain block to the primary S-node, if it is not the primary S-node,
A blockchain storage service (BSS) is provided between the blockchain node and the external storage, and collectively transmits agreed block data for the first blockchain block to the blockchain node so that interaction between the blockchain node and the external storage is performed via the primary S-node or the plurality of S-nodes.
A Byzantine fault tolerant block data storage device utilizing external storage devices. In Article 18,
Providing a blockchain storage service (BSS) that transmits agreed block data for the first blockchain block to the blockchain node.
A Byzantine fault tolerant block data storage device utilizing external storage devices. In Article 18,
Block cache that temporarily stores blocks received from the above blockchain nodes;
Message cache that temporarily stores consensus messages exchanged with other S-nodes;
A generator that generates consensus messages and propagates them to other S-nodes;
An analyzer that determines the consensus status for a block based on consensus messages received from the other S-nodes; and
Persistent metadata store that stores the generated metadata after consensus on the block is reached;
Including,
A Byzantine fault tolerant block data storage device utilizing external storage devices.