METHOD FOR PIPELINED FORMATION OF A BLOCKCHAIN GUARANTEEING TRANSACTION LIVENESS

Abstract

A method for forming a blockchain allowing to ensure that any transaction emitted by a client is incorporated into the blockchain. This method involves N validator nodes of the network, including at most F faulty nodes with N > 3F , and implements a consensus mechanism tolerant of Byzantine faults. Each validator node forms a block of transactions received from the clients by selecting them according to their order of arrival and broadcasts this block to the other validator nodes. The validator node concatenates the block that it formed with a plurality of blocks received from the other nodes to form a composite block of f ≥ F + 1 blocks. Each validator node determines whether the composite blocks that it receives from the other validator nodes are valid, and if it receives N - F approval messages for the same composite block, validates the latter in the form of a decided composite block by adding to it a quorum certificate.

Claims

1. A method for forming a blockchain involving a plurality N of validator nodes, comprising at most F faulty nodes with N > 3F , each validator node having available a local copy of the blockchain and receiving the transactions emitted by clients, each validator node further storing these transactions according to their order of arrival in a queue and creating a block of transactions by popping the queue starting from the oldest transaction, wherein each validator node: during a consensus phase of the BFT type, determines whether composite blocks, formed by a number ƒ of blocks with ƒ ≥F+1, proposed by the other validator nodes during the current instance of validation are valid and, if yes, sends back to these nodes an extended approval message, said extended approval message comprising the composite block validated during the current instance of validation as well as a new block of transactions intended to form a new composite block during the following instance of validation; when it has available at least N - F messages of approval of the same composite block, creates a decided block comprising said composite block and an extended quorum certificate, the extended quorum certificate being composed of said at least N - F extended approval messages relative to said composite block; when it has available a decided block, adds the composite block in question to the local copy of the blockchain; forms said new composite block from the new blocks of transactions contained in the ƒ extended approval messages of the extended quorum certificate.

2. The method for forming a blockchain according to claim 1, wherein each validator node transmits the transactions received from the clients to the other validator nodes according to a service of the Best Effort type.

3. The method for forming a blockchain according to claim 1, wherein the number of validator nodes comprises exactly F faulty ones and ƒ ≤N-F.

4. The method for forming a blockchain according to claim 1, wherein after having formed the new composite block, the validator node adds to it the quorum certificate of the preceding composite block as well as a pointer to the preceding composite block.

5. The method for forming a blockchain according to claim 1, wherein when a composite block is incorporated into the blockchain, the validator node advantageously deletes from its queue all the transactions present in said composite block.

6. The method for forming a blockchain according to claim 1, wherein the consensus phase comprises a plurality of successive iterations, each iteration comprising a proposition step in which each validator node proposes a block of transactions, a step of consultation among the validator nodes, and an approval step in which each validator node indicates to the others the composite block that it validated via an extended approval message that it transmits to them.

7. The method for forming a blockchain according to claim 5, wherein an extended approval message emitted by a validator node comprises the composite block validated by this said node, the index of the iteration and the step of the iteration during which it validated it, the new block of transactions intended to form a new composite block during the following instance of validation, said approval message being signed by a private key of the validator node.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0045] Other features and advantages of the invention will appear upon reading a preferred embodiment of the invention, described in reference to the appended drawings in which:

[0046] FIG. 1, already described, schematically shows a consensus mechanism of the BFT type used to validate a block in a blockchain;

[0047] FIG. 2, already described, shows various iterations involved in the execution of the consensus mechanism of FIG. 1;

[0048] FIG. 3, already described, shows in the form of a flowchart the steps carried out by a validator node in a method for forming a blockchain using a known consensus mechanism of the BFT type;

[0049] FIG. 4 schematically shows a consensus mechanism of the BFT type used in a method for forming a blockchain, according to an embodiment useful to the understanding of the invention;

[0050] FIGS. 5A to 5C schematically show a phase of certification of composite blocks and a consensus phase of the BFT type relating to these composite blocks, implemented in the consensus mechanism of FIG. 4;

[0051] FIG. 6 shows in the form of a flowchart the various steps carried out by a validator node in a method for forming a blockchain using a consensus mechanism of FIG. 4;

[0052] FIG. 7 schematically shows a consensus mechanism of the BFT type used in a method for forming a blockchain according to an embodiment of the present invention;

[0053] FIG. 8 shows in the form of a flowchart the steps carried out by a validator node in a method for forming a blockchain using a consensus mechanism of the BFT type, according to the embodiment of FIG. 7.

DETAILED DISCLOSURE OF SPECIFIC EMBODIMENTS

[0054] Below, a method for forming blockchains using a mechanism for consensus of the BFT type among validator nodes, as disclosed in the introduction, will be considered. The method for forming a blockchain involves here again N validator nodes of the network, including at most F faulty nodes.

[0055] A first idea forming the basis of the present invention is to form composite blocks, each composite block resulting from the concatenation of ƒ candidate blocks, with ƒ ≥ F+1, out of the N candidate blocks proposed by the validator nodes and of the quorum certificate of the composite block. When the number of faulty nodes is exactly equal to F, the number f of candidate blocks concatenated in a composite block must satisfy the condition ƒ ≤ N-F. These composite blocks are then submitted to a consensus mechanism of the BFT type.

[0056] FIG. 4 schematically shows a consensus mechanism of the BFT type used in a method for forming a blockchain according to an embodiment useful to the comprehension of the present invention.

[0057] This consensus mechanism comprises a certification phase 410, aiming to generate certified composite blocks, followed by a consensus phase of the BFT type, 420.

[0058] As above, the case of N = 4 validator nodes was considered, each validator node executing a validation process, P.sub.n ,n = 1,..,N . Only the node 1 is supposed to be Byzantine, in other words F = 1.

[0059] Each validator node forms a block by concatenating a predetermined number of successive transactions in the order of the queue, that is to say according to their order of arrival. It broadcasts the block thus obtained to all the other validator nodes via a service of the Best Effort type.

[0060] When a validator node has available ƒ ≥ F+1 blocks, here ƒ = N-F blocks, it constructs a composite block by concatenating the N-F blocks thus received.

[0061] FIG. 5A illustrates the exchanges of blocks among validator nodes during the certification phase, as well as the formation of composite blocks by each of them. Thus, for example, the node 1 forms a composite block

[00004]$b_1{}^{\prime },b_1{{}^{\prime }}^{\prime },b_1{{}^{\prime }}^{\prime }{}^{\prime },$

the node 2 forms a composite block

[00005]$b_1{{}^{\prime }}^{\prime },b_1{{}^{\prime }}^{\prime }{}^{\prime },b_1{{}^{\prime }}^{\prime }{{}^{\prime }}^{\prime },$

etc.

[0062] Each of the composite blocks is then the object of a certification by adding to it on the one hand a pointer to the preceding certified composite block, B.sub.0, stored in the blockchain and, on the other hand, the quorum certificate of the preceding composite block, QC.sub.0.

[0063] The certified composite blocks are then submitted to a consensus mechanism of the BFT type in 420, also involving the N validator nodes. The consensus mechanism comprises a plurality of successive iterations, each iteration comprising a proposition step, a consultation step and an approval step, as described above.

[0064] Each validator node having formed a composite block from at least F + 1 blocks stored in its queue proposes it to the other validator nodes, which validate it or not. When a validator node validates a composite block, it diffuses a validation message to all of the nodes and signs it digitally (for example via its private key).

[0065] The operation of the consensus mechanism was illustrated in FIG. 5B.

[0066] Only the last iteration of the consensus phase is shown here for reasons of simplification. After the steps of proposition, 510, and of consultation, 520, the approval step 530 leads to a consensus among the N-F =3 validator nodes 1, 3 and 4 on the composite block

[00006]${b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1.$

[0067] Thus, in the example illustrated, the first validator node, after having broadcast the composite block b'.sub.1,b.sub.1″,b.sub.1‴ , receives, after the consultation step, an approval message signed by the third node, Endorse

[00007]$\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1\right)\_p_3,$

as well as an approval message signed by the fourth node

[00008]$\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1\right)\_p_4.$

[0068] Similarly, the third validator node, after having transmitted to the other validator nodes the composite block

[00009]${b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1,$

receives an approval message signed by the first node,

[00010]$Endorse\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1\right)\_p_1,$

as well as an approval message signed by the fourth node,

[00011]$Endorse(b_1^{\text{'}},b_1^{"},b_1^{"\text{'}})\_p_4\text{.}$

[0069] When at the end of an iteration a validator node has available the approval of at least N-F validator nodes on a composite block (including its own approval), the process stops and the composite block in question takes on the status of decided composite block.

[0070] Each decided composite block is associated with a quorum certificate. This quorum certificate consists of all of the approval messages that the validator node has available. All of the approval messages means those that it received from the other validator nodes as well as that which it generated during the same approval step of the same iteration.

[0071] Thus, in the example of FIG. 5B, the quorum certificate associated with the decided composite block

[00012]${b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1$

by the first validator node is given by

[00013]$QC=\left\{Endorse\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1\right)\_p_1,\right)$

[00014]$Endorse\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1\right)\_p_3,$

[00015]$\left(Endorse\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1\right)\_p_4\right\}.$

[0072] It should be noted that other validator nodes can provide validation certificates for the same composite block insofar as they do not necessarily receive the same approval messages.

[0073] According to one alternative, the approval message also comprises the number of the step and the index of the iteration during which it was generated. In this case the quorum certificate can take on the following form:

[00016]$QC=\left\{Endorse\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1;i,r\right)\_p_1,\right)$

[00017]$Endorse\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1;i,r\right)\_p_3,$

[00018]$\left(Endorse\left({b^{\prime }}_1,{b^{″}}_1,{b^{‴}}_1;i,r\right)\_p_4\right\}.$

where i is the index of the iteration and r is the number of the step of generation of the approval messages in question.

[0074] More generally, the quorum certificate associated with the instance of validation j is in the form:

[00019]$Q{C}_j=\left\{Endorse\left(b_j^{\left(k_1\right)},\mathrm{...},b_j^{\left(k_{N-F}\right)};i,r\right)\_p_{k_1}\right),$

[00020]$\left(\mathrm{...},Endorse\left(b_j^{\left(k_1\right)},\mathrm{...},b_j^{\left(k_{N-F}\right)};i,r\right)\_p_{k_{N-F}}\right\}$

where

[00021]$b_j^{\left(k_1\right)},\mathrm{...},b_j^{\left(k_{N-F}\right)}$

denotes here the composite block approved by the N-F nodes k.sub.1,...,k.sub.N_.sub.F during the instance of validation j.

[0075] FIG. 6 shows in the form of a flowchart the steps carried out by a validator node in a method for forming a blockchain using the consensus mechanism of FIG. 4.

[0076] It is recalled that each validator node receives the transactions emitted by the clients and transmits them to the other validator nodes according to a service of the Best Effort type. It also has available its own local copy of the blockchain.

[0077] One validator node out of N will now be considered.

[0078] When this validator node observes in 610 that a new composite block having a rank j has been decided, in other words validated by consensus with at least ƒ validations in the associated quorum certificate QC.sub.j, it adds this new composite block to its local copy of the blockchain.

[0079] As soon as a new composite block is incorporated into the blockchain, more precisely into its local copy, the validator node deletes from the queue all the transactions present in the composite block in question, 620.

[0080] The validator node then prepares in 630 a block by selecting the transactions available in the queue, starting with the oldest, in other words by popping the transactions of the FIFO buffer that stores them. In order to order the transactions, each transaction can be timestamped during its reception. It transmits the block thus formed, called proposed block, to all of the other validator nodes.

[0081] In 640, it forms a composite block comprising ƒ ≥ F+1 proposed blocks and generates a certified composite block, that is to say a composite block to which a pointer pointing to the preceding composite block, as well as the quorum certificate of the preceding composite block, are added.

[0082] In 650, the validator node submits the certified composite block that it generated in the previous step to a consensus mechanism of the BFT type. In this consensus mechanism, each validator node proposes for the approval of the other validator nodes the certified composite block that it generated.

[0083] In 660, if the validator node has available at least N-F (and thus at least 2F + 1) approval messages of validator nodes, it declares it as decided and adds to it the quorum certificate.

[0084] The process then continues by returning to step 610.

[0085] FIG. 7 schematically shows a consensus mechanism of the BFT type used in a method for forming a blockchain according to an embodiment of the present invention.

[0086] This embodiment differs from the previous one in that the phase of combination/certification and the phase of consensus are pipelined. In other words, each validator node proposes a block to form the following composite block at the same time as it carries out a validation of the current composite block. This feature allows to reduce the time separating the sending of a transaction by a client from its incorporation into the blockchain, and thus the latency of the formation of the blockchain.

[0087] More precisely, according to the present invention, each validator node transmits to the other validator nodes an extended approval message, approving on the one hand a current composite block like in FIG. 5B and proposing on the other hand a new block for the formation of the following composite block.

[0088] The extended approval message emitted by the validator node k can for example take on the following form:

[00022]$Endorse*\left\{\left({b^{\prime }}_j,{b^{″}}_j,{b^{‴}}_j;i,r\right),b_{j+1}\right\}{P}_k$

where

[00023]${b^{\prime }}_j,{b^{″}}_j,{b^{‴}}_j$

form the j.sup.th composite block approved by the node k to be incorporated into the blockchain as a composite block having the rank j (that is to say the instance of validation j) and where b.sub.j+1 is the block of transactions proposed by this same node to form the (j + 1).sup.th composite block and finally ­_p.sub.k means that the message is signed by this node.

[0089] An extended quorum certificate of a composite block can thus be formed:

[00024]$Q{C}_j^{*}=\left\{Endorse*\left\{\left(b_j^{\left(k_1\right)},.Math.,b_j^{\left(k_{N-F}\right)};i,r\right)b_{j+1}^{\left(k_1\right)}\right\}\_p_{k_1},.Math.,Endorse*\left\{\left(b_j^{\left(k_1\right)},.Math.,b_j^{\left(k_{N-F}\right)};i,r\right)b_{j+1}^{\left(k_{N-F}\right)}\right\}\_p_{k_{N-F}}\right\}$

where it has been supposed that the nodes k.sub.1,...,.sup.kN.sub.-F approved the composite block

[00025]$b_j^{\left(k_1\right)},.Math.,b_j^{\left(k_{N-F}\right)}\left({b^{\prime }}_j,{b^{″}}_j,{b^{‴}}_j\right)$

in the example illustrated in FIG. 7) during the instance of validation j and that the blocks of transactions proposed by these same nodes for the formation of the following composite block are respectively

[00026]$b_{j+1}^{\left(k_1\right)},.Math.,b_{j+1}^{\left(k_{N-F}\right)}\cdot$

According to a specific alternative embodiment, the blocks of transactions

[00027]$b_{j+1}^{\left(k_1\right)},.Math.,b_{j+1}^{\left(k_{N-F}\right)}$

can include only a single transaction each, in other words

[00028]$b_{j+1}^{\left(k_1\right)},.Math.,b_{j+1}^{\left(k_{N-F}\right)}=t_{j+1}^{\left(k_1\right)},.Math.,t_{j+1}^{\left(k_{N-F}\right)}.$

[0090] It is noted in the expression (4) that the extended quorum certificate of the composite block

[00029]$b_j^{\left(k_1\right)},.Math.,b_j^{\left(k_{N-F}\right)}$

gives the proposition of the following composite block

[00030]$b_{j+1}^{\left(k_1\right)},.Math.,b_{j+1}^{\left(k_{N-F}\right)}.$

In other words, any proposition of a composite block is thus accompanied by a construction of the quorum certificate of the preceding composite block. It is therefore implicitly certified, which allows to do without a distinct previous certification phase. This new certified composite block is thus submitted to a new instance of validation j+1.

[0091] FIG. 8 shows in the form of a flowchart the steps carried out by a validator node in a method for forming a blockchain using the consensus mechanism of FIG. 7.

[0092] Like in the first embodiment, each validator node receives the transactions emitted by the clients and transmits them to the other validator nodes according to a service of the Best Effort type.

[0093] One validator node out of N will now be considered.

[0094] When this validator node observes in 810 a new decided composite block having the rank j, in other words validated by an extended quorum certificate

[00031]$Q{C}_j^{\ast },$

it adds this new composite block to its local copy of the blockchain. The composite block stored in the blockchain is certified, that is to say that it is stored with the extended quorum certificate of the preceding composite block,

[00032]$Q{C}_{j-1}^{*},$

as well as with a pointer to the latter.

[0095] As soon as a new composite block having the rank j is incorporated into the blockchain, more precisely into its local copy, the validator node deletes from the queue all the transactions present in the composite block in question, 820.

[0096] In 830, the validator node forms a new composite block from at least ƒ extended approval messages that it has available, contained by construction in the last extended quorum certificate,

[00033]$Q{C}_j^{*}.$

[0097] In 840, the validator node submits the certified composite block to the extended process of consensus of the BFT type, for the instance of validation j .

[0098] In 850, in this consensus process, the validator node determines whether the composite blocks that it receives from the other nodes are valid and if yes returns to them an extended approval message, said extended approval message containing a new transaction block to form the next composite block.

[0099] In step 860, if the validator node observes at least N-F extended approval messages for a composite block, it creates a decided composite block by addition of the extended quorum certificate. The extended quorum certificate comprises all of the extended messages received by the validator node, approving the composite block in question.

[0100] The process then continues by returning to step 810.