SYSTEMS AND METHODS FOR IMPLEMENTING LINEAR VIEW-CHANGE IN A BYZANTINE FAULT TOLERANT (BFT) PROTOCOL

Abstract

A method for implementing linear view-change in a BFT protocol running on a distributed system including n replicas, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables the non-faulty replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients. The method including executing, among and by the n replicas, a phase φ of the BFT protocol, communicating instances of a lock certificate being associated with said phase; and if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiating a view-change with at least the following step: if said current phase φ is different than 1, each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase up to said current phase.

Claims

1. A method for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables the non-faulty replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising: executing, among and by the n replicas, a phase of the BFT protocol, phases being numbered as positive numbers φ=1,2, . . . , in each phase one or several consecutive replicas playing a specific role and being identified as leader replica, a lock certificate being associated with said phase; and if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiating a view-change with at least the following steps: if said current phase number φ is different than 1, each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase φ for which said replica P.sub.i received said lock certificate associated with a value I.sub.i, or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate; each replica P.sub.i sending to a leader replica L.sub.φ a message containing at least a report (φ.sub.iφ), appended with said lock certificate (I.sub.i,φ) if φ.sub.i≥1, and/or on the leader replica L.sub.φ side: if said current phase number φ is equal to 1, said leader replica L.sub.φ sets a value equal to an input I and sends a proposition message to the replicas including said value I, or if said current phase number φ is different than 1, upon receiving messages from 2t+1 distinct replicas, with one such message from a replica i.sub.max containing a report (φ.sub.imax,φ) such that a phase number φ.sub.imax is the highest phase number φ.sub.i out of the said 2+1 reports (φ.sub.i,φ) received, a phase number φ.sub.max, is then set equal to the phase number φ.sub.imax and a value I.sub.max, is set equal to I.sub.max the value contained in the lock certificate (I.sub.imax,φ.sub.imax) appended to the message from i.sub.max, the leader replica L.sub.φ generating a message out of said 2t+1 distinct replicas, with: (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one lock certificate Lc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.maxφ,PnS(φ.sub.max,φ),Lc.sub.max) to the replicas; or (ii) if said phase number φ.sub.max is equal to 0, said leader replica L.sub.φ sets the value I equal to an input I.sub.mod and sends a proposition message (I.sub.mod,φ,PnS(0,φ),), to the replicas, in order to make the view-change effective in said distributed system.

2. The method of claim 1, wherein the message generating by the leader replica contains at least a proof PnS(φ.sub.max,φ), embodied as of proof of existence of 2t+1 reports (φ.sub.i,φ) signed by 2t+1 replicas, including the phase numbers φ.sub.i, which are all lower than or equal to the phase number φ.sub.max.

3. The method of claim 1, wherein, for each non-faulty replica P.sub.i in the phase φ, with φ.sub.i≤φ the highest phase number for which said replica P.sub.i received said lock certificate (I.sub.iφ.sub.i), each message sent by the replicas contains, along with a lock certificate in φ.sub.i if 1≤φ.sub.i, the following embodiment of report (φ.sub.i,φ), denoted as a “list of testimonies to be lower” with: for each integer value φ.sup.0∈[φ.sub.i . . . , φ], a data, which is signed using a threshold signature system σ of threshold (2t+1), said signed data being denoted “testimony(φ.sup.0,φ)”, and carrying the information that {the said phase number set by the sender in phase φ is lower than or equal to φ.sup.0}, the proof PnS(φ.sub.max,φ) being then embodied as a threshold signature with threshold 2t+1 on the testimony (φ.sub.max,φ), which guarantees that 2t+1 replicas signed it.

4. The method of claim 1, wherein each replica P.sub.i(i=1 . . . n), upon receiving said proposition message from the leader replica L.sub.φ for the first time in the phase φ, replies with a signed lock vote message.

5. The method of claim 4, wherein said lock certificate is a (2t+1)-threshold signature on said lock vote message.

6. The method of claim 4, wherein the leader replica L.sub.φ, upon receiving 2t+1 lock vote messages for the same input I.sub.mod or I.sub.max, issues from said lock vote messages a lock certificate, which said leader replica L.sub.φ sends along with said input.

7. The method of claim 6, wherein each replica P.sub.i(i=1 . . . n), upon receiving from the leader replica L.sub.φ a lock certificate for the first time in the phase φ, whatever the input I, replies with a signed decision vote message.

8. The method of claim 7, wherein the leader replica L.sub.φ, upon receiving decision vote messages from 2t+1 distinct replicas for the same input, issues from said decision vote messages a decision certificate, which is sent by said leader replica L.sub.φ to the replicas in order to make the view-change effective in said distributed system, and, upon receiving said decision certificate for the input, each replica outputs the chosen value.

9. The method of claim 1, wherein only one lock certificate associated to one phase is formed.

10. The method of claim 1, wherein, in each phase ϕ≥1, the leader Lϕ is a publicly known replica, being for example selected at random among n replicas.

11. A non-transitory computer readable storage medium having stored thereon program code embodying a method for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables the non-faulty replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising: executing, among and by the n replicas, a phase of the BFT protocol, phases being numbered as positive numbers φ=1,2, . . . , in each phase one or several consecutive replicas playing a specific role and being identified as leader replica, a lock certificate being associated with said phase; and if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiating a view-change with at least the following steps: if said current phase number φ is different than 1, each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase number φ for which said replica P.sub.i received said lock certificate associated with a value I.sub.i, or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate; each replica P.sub.i sending to a leader replica L.sub.φ a message containing at least a report(φ.sub.i,φ), appended with said lock certificate (I.sub.i,φ.sub.i) if φ.sub.i≥1, and/or on the leader replica L.sub.φ side: if said current phase number φ is equal to 1, said leader replica L.sub.φ sets a value equal to an input I and sends a proposition message to the replicas including said value I, or if said current phase number φ is different than 1, upon receiving messages from 2t+1 distinct replicas, with one such message from a replica i.sub.max containing a report(φ.sub.max,φ) such that a phase number φ.sub.imax is the highest phase number φ.sub.i out of the said 2+1 reports (φ.sup.1,φ) received, a phase number φ.sub.max, is then set equal to the phase number φ.sub.max and a value I.sub.max is set equal to I.sub.max the value contained in the lock certificate (I.sub.max,φ.sub.imax) appended to the message from i.sub.max, the leader replica L.sub.φ generating a message out of said 2t+1 distinct replicas, with: (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one lock certificate Lc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,PnS(φ.sub.max,φ),Lc.sub.max) to the replicas; or (ii) if said phase number φ.sub.max is equal to 0, said leader replica L.sub.φ sets the value I equal to an input I.sub.mod and sends a proposition message (φ.sub.mod,φ,PnS(0,φ),) to the replicas, in order to make the view-change effective in said distributed system.

12. A distributed system comprising: n replicas, and a non-transitory computer readable storage medium having stored thereon program code that, when executed, enables the distributed system to implement linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on said distributed system, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables the non-faulty replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the program code causing said distributed system to: execute, among and by the n replicas, a phase of the BFT protocol, phases being numbered as positive numbers φ=1,2, . . . , in each phase one or several consecutive replicas playing a specific role and being identified as leader replica, a lock certificate being associated with said phase; and if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiate a view-change with at least the following steps: if said current phase number φ is different than 1, each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase number φ for which said replica P.sub.i received said lock certificate associated with a value I.sub.i, or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate; each replica P.sub.i sending to a leader replica L.sub.φ a message containing at least a report(φ.sub.i,φ), appended with said lock certificate (I.sub.i,φ.sub.i) if φ.sub.i≥1, and/or on the leader replica L.sub.φ side: if said current phase number φ is equal to 1, said leader replica L.sub.φ sets a value equal to an input I and sends a proposition message to the replicas including said value I, or if said current phase number φ is different than 1, upon receiving messages from 2t+1 distinct replicas, with one such message from a replica i.sub.max containing a report(φ.sub.imax,φ) such that a phase number φ.sub.imax is the highest phase number φ.sub.i out of the said 2+1 reports (φ.sub.iφ) received, a phase number φ.sub.max is then set equal to the phase number φ.sub.max and a value I.sub.max, is set equal to I.sub.max the value contained in the lock certificate (I.sub.imax,φ.sup.imax) appended to the message from i.sub.max, the leader replica L.sub.φ generating a message out of said 2t+1 distinct replicas, with: (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one lock certificate Lc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,PnS(φ.sub.max,φ), Lc.sub.max) to the replicas; or (ii) if said phase number φ.sub.max is equal to 0, said leader replica L.sub.φ sets the value I equal to an input I.sub.mod and sends a proposition message (I.sub.mod,φ,PnS(0,φ),) to the replicas, in order to make the view-change effective in said distributed system.

13. A method for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables at least 2t+1 of the n replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising: executing, among and by the n replicas, a phase φ of the BFT protocol, communicating instances of a lock certificate being associated with said phase; and if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiating a view-change with at least the following steps: each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase φ for which said replica P.sub.i received said lock certificate associated with an input value I.sub.i, or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate; each replica P.sub.i sends to a leader replica L.sub.φ a report(φ.sub.i,φ), appended with a full lock certificate (I.sub.i,φ.sub.i) if φ.sub.i≥1, and initiates an instance of an exclusivity protocol with respect to its respective input value I.sub.i, the leader replica being the chosen prover L, said exclusivity protocol being a protocol that guarantees: (a) if either said prover L, knows a valid value or at least t+1 non-faulty replicas have a valid input value, after a round-trip of messages between said prover L and the replicas, the prover L outputs a valid input I.sub.select, and (b) after another round-trip of messages between said prover L and the replicas, the prover L outputs a report PoE(I.sub.select), the leader replica L.sub.φ, upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ.sub.max set to be the highest phase number φ.sub.i received and associated with a value I.sub.max: (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one full lock certificate FLc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,PnS(φ.sub.max,φ),FLc.sub.max) to the replicas, with PnS(φ.sub.max,φ) a report generated by the leader replica L.sub.φ out of said 2t+1 distinct replicas; or (ii) if said phase number φ.sub.max is equal to 0, then said leader replica L.sub.φ selects said valid input I.sub.select, in function of said exclusivity protocol, and sends a proposition message (I.sub.select,φ,PnS(0,φ), ) to the replicas, in order to make the view-change effective in said distributed system.

14. The method of claim 13, wherein, during an instance of the exclusivity protocol, a value I satisfies a condition denoted the Exclusivity Predicate if and only if no other value I′ is a unanimous input of non-faulty replicas, a report PoE(I) being a proof that I satisfies said condition of Exclusivity Predicate.

15. The method of claim 13, wherein a proof of exclusivity PoE(v) of a value v, relative to a publicly known fixed tag, proves knowledge of one of the two following cases: (i) either of a set I⊂{1, . . . , n} of t+1 distinct indices, together with a signature from each replica i ∈ I for the message (v, tag), (ii) or of a set S of 2t+1 messages (v.sub.j, tag) for j=1, . . . , 2t+1, each signed by a distinct replica, such that no value v.sub.j repeats identically in strictly more than t messages, preferably, if the prover is in the case (i), where some value v repeats t+1 times, then said prover proves this with a (t+1)-threshold signature on v, and preferably, if the prover is in the case (ii), where no value repeats more than t times in S, the prover proves knowledge of a decomposition of S into three disjunct nonempty subsets of values, with repetitions: S=S.sub.low∪{v.sub.med}∪S.sub.high, all of cardinalities at most t, and such that all values in the subset Si are strictly smaller than the value v.sub.med, and proves that the value v.sub.med is itself strictly smaller than all values in the subset S.sub.high.

16. The method of claim 13, wherein each replica P.sub.i(i=1 . . . n), upon receiving said proposition message from the leader replica L.sub.φ for the first time in the phase φ, replies with a signed lock vote message.

17. The method of claim 16, wherein, upon receiving 2t+1 lock vote messages for the same (I.sub.select,φ) or (I.sub.max,φ) and with: i) if the prover L already had a full lock certificate associated with its value I.sub.i, the prover L extracts a report PoE(I.sub.i) according to the exclusivity protocol, or ii) the prover L had selected a valid input I.sub.select in the previous instance of the exclusivity protocol, and has a valid report PoE(I.sub.select). the leader replica L.sub.φ aggregates the 2t+1 lock vote messages, and appends them with said PoE obtained at step i) or step ii), to issue a full lock certificate, which said leader replica L.sub.φ sends along with said selected input I.sub.select or value I.sub.max.

18. The method of claim 17, wherein each replica P.sub.i(i=1 . . . n), upon receiving from the leader replica L.sub.φ a full lock certificate for the first time in the phase φ, whatever the input I, replies with a signed decision vote message.

19. The method of claim 18, wherein the leader replica L.sub.φ, upon receiving decision vote messages from 2t+1 distinct replicas for the same value I.sub.select or I.sub.max, issues from said decision vote messages a decision certificate, which is sent by said leader replica L.sub.φ to the replicas in order to make the view-change effective in said distributed system, and, upon receiving said decision certificate for the value I.sub.select or I.sub.max, each replica outputs the chosen value and continues said exclusivity protocol.

20. The method of claim 13, being applicable to any possible consensus protocol that offers other trade-offs in security, such as allowing 3 messages of latency even if up to a number c of replicas are faulty, at the price of tolerating less corruption threshold: n>=3t+2c−1.

21. The method of claim 13, wherein the exclusivity protocol has a complexity of O(nlog(n)), with n the number of replicas.

22. A non-transitory computer readable storage medium having stored thereon program code embodying a method for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables at least 2t+1 of the n replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising: executing, among and by the n replicas, a phase φ of the BFT protocol, communicating instances of a lock certificate being associated with said phase; and if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiating a view-change with at least the following steps: each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase φ for which said replica P.sub.i received said lock certificate associated with an input value I.sub.i, or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate; each replica P.sub.i sends to a leader replica L.sub.φ a report(φ.sub.i,φ), appended with a full lock certificate (I.sub.i,φ) if φ.sub.i≥1, and initiates an instance of an exclusivity protocol with respect to its respective input value I.sub.i, the leader replica being the chosen prover L, said exclusivity protocol being a protocol that guarantees: (a) if either said prover L, knows a valid value or at least t+1 non-faulty replicas have a valid input value, after a round-trip of messages between said prover L and the replicas, the prover L outputs a valid input I.sub.select, and (b) after another round-trip of messages between said prover L and the replicas, the prover L outputs a report PoE(I.sub.select), the leader replica L.sub.φ, upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ.sub.max set to be the highest phase number φ.sub.i received and associated with a value I.sub.max: (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one full lock certificate FLc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,PnS(φ.sub.max,φ),FLc.sub.max) to the replicas, with PnS(φ.sub.max,φ) a report generated by the leader replica L.sub.φ out of said 2t+1 distinct replicas; or (ii) if said phase number φ.sub.max is equal to 0, then said leader replica L.sub.φ selects said valid input I.sub.select, in function of said exclusivity protocol, and sends a proposition message (I.sub.select,φ,PnS(0,φ),) to the replicas, in order to make the view-change effective in said distributed system.

23. A distributed system comprising: n replicas, and a non-transitory computer readable storage medium having stored thereon program code that, when executed, enables the distributed system to implement linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on said distributed system, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables at least 2t+1 of the n replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the program code causing said distributed system to: execute, among and by the n replicas, a phase φ of the BFT protocol, communicating instances of a lock certificate being associated with said phase; and if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiate a view-change with at least the following steps: each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase φ for which said replica P.sub.i received said lock certificate associated with an input value I.sub.i, or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate; each replica P.sub.i sends to a leader replica L.sub.φ a report(φ.sub.i,φ), appended with a full lock certificate (I.sub.i,φ.sub.i) if φ.sub.i≥1, and initiates an instance of an exclusivity protocol with respect to its respective input value I.sub.i, the leader replica being the chosen prover L, said exclusivity protocol being a protocol that guarantees: (a) if either said prover L knows a valid value or at least t+1 non-faulty replicas have a valid input value, after a round-trip of messages between said prover L and the replicas, the prover L outputs a valid input I.sub.select, and (b) after another round-trip of messages between said prover L and the replicas, the prover L outputs a report PoE(I.sub.select), the leader replica L.sub.φ, upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ.sub.max set to be the highest phase number φ.sub.i received and associated with a value I.sub.max: (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one full lock certificate FLc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,PnS(φ.sub.max,φ),FLc.sub.max) to the replicas, with PnS(φ.sub.max,φ) a report generated by the leader replica L.sub.φ out of said 2t+1 distinct replicas; or (ii) if said phase number φ.sub.max is equal to 0, then said leader replica L.sub.φ selects said valid input I.sub.select, in function of said exclusivity protocol, and sends a proposition message (I.sub.select,φ,PnS(0,φ),) to the replicas, in order to make the view-change effective in said distributed system.

24. Method for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables the non-faulty replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising: each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase φ for which said replica P.sub.i received said LockCertificate(input value I.sub.i, phase number φ.sub.i) or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any LockCertificate; each replica P.sub.i sends to a leader replica L.sub.φ a report(φ.sub.i,φ), appended with a LockCertificate(I.sub.i,φ.sub.i) if φ.sub.i≥1 the leader replica L.sub.φ upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ.sub.max set to be the highest phase number φ.sub.i received and associated with a value I.sub.max: (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one LockCertificate.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,LockCertificate(I.sub.max,φ.sub.max)) to the replicas, or, (ii) if said phase number φ.sub.max is equal to 0, said leader replica sets the value I equal to an input I.sub.mod and sends a proposition message (I.sub.mod,φ,⊥) to the replicas the leader replica L.sub.φ, only in the situation where: {it has sent a proposition message with a lock certificate Lc.sub.max(I.sub.max,φ.sub.max), and it receives from some replica P.sub.i, a report(φ.sub.i,φ) message with a phase number φ.sub.i strictly higher than φ.sub.max}: then leader replies to the replica P.sub.i with a Proof_of_non-Supermajority(φ.sub.max,φ) formed out of the report messages, each replica P.sub.i(i=1 . . . n), upon receiving said proposition message (I.sub.max,φ,LockCertificate(I.sub.max,φ.sub.max)) or (I.sub.mod,φ,⊥) from the leader replica L.sub.φ for the first time in the phase φ, i) if the said set phase number φ.sub.i is lower than or equal to said phase number φ.sub.max contained in the proposed LockCertificate(I,φ.sub.max) if any, or than 0 if no LockCertificate is included in the proposition; ii) or if it also received a Proof_of_non-Supermajority(φ.sub.max,φ); then it replies with a signed lock vote message (I.sub.mod,φ) or (I.sub.max,φ). the leader replica L.sub.φ, upon receiving a set of 2t+1 lock votes for said value I: (iii) forms a lock certificate(I,φ), shortened as “Lc”, consisting of the aggregation of the 2t+1 signatures on said signed lock votes, into a threshold signature, then sends it to the replicas. replica P.sub.i(i=1 . . . n), upon receiving from the leader replica L.sub.φ a Lc(I,φ) for the first time in the phase φ, whatever the value I, replies with a signed decision vote message.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0076] The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate various exemplary embodiments and together with the description, serve to explain the principles of the disclosed embodiments.

[0077] FIG. 1 depicts a flowchart of a first exemplary method for implementing linear view-change in a BFT protocol running on a distributed system.

[0078] FIG. 2 depicts a flowchart of a second exemplary method for implementing linear view-change in a BFT protocol running on a distributed system.

DETAILED DESCRIPTION

Definitions

[0079] Consensus

[0080] In the detailed description herein, consensus protocols are considered for n players, also denoted replicas, in a distributed system, especially an asynchronous communication network, where no more than t replicas are maliciously corrupted, or faulty, the others being denoted as honest, or non-faulty. This number n of replicas may be larger or equal to 3t+1. The invention is described on the specific example of a number n=3t+1 replicas but is applicable in general to any n larger than or equal to 3t+1. A method to generalize the description below may consist in replacing the number 2t+1 every time where it appears, denoted as a “supermajority”, by the number n−t.

[0081] The following definition can be used: let π be a protocol in which all in replicas supply an input value and outputs at most one output value. Then, π is called a consensus protocol if it satisfies the Consistency property: no two non-faulty replicas output different values; and the Consensus Weak Unanimity (CWU) property: if all n replicas are non-faulty and have the same input value, then this is the only value that they can possibly output (M. Ben-Or, ACM SIGACT-SIGOPS 1983).

[0082] A consensus has Strong Unanimity if, as soon as all non-faulty replicas have the same input value, then this is the only possible output. It can be noted that a consensus has an (optimistic) Fast Track if one further has the following property: if all replicas are non-faulty and have the same input, then all replicas output within two messages delay from the start of the execution.

[0083] The protocol proceeds in intervals denoted views or phases, and numbered as positive integers φ=1,2, . . . Each honest replica maintains a phase counter, the counters may not evolve at the same pace from one replica to another. For simplicity in the following description, it is assumed a model where all counters are synchronized, e.g. they may be controlled by a global clock. Given by the model, in each phase φ≥1, the publicly known identity of a replica is assumed, marked as a distinguished replica and denoted the leader replica L.sub.100, a replica in the n replicas corresponding to a new proposer for the view-change. The invention applies also to systems where the identity of the leader replica may change within a phase, as for instance in the “chained Hotstuff” (Yin et al Podc'21).

[0084] In the detailed description herein, a round-trip has to be understood as a complete exchange of messages between the replicas.

[0085] In the detailed description herein, a view change has to be understood as a phase change.

[0086] In the detailed description herein, a k-threshold signature scheme (TSS), is the data of a secret algorithm for each participant that outputs a signature share on a message, in a way that signature shares are unforgeable; of a public algorithm enabling to check that signature shares are correctly computed, and of a public algorithm that aggregates k valid signature shares on the same message m into one signature, denoted “threshold signature” on m, such that it is unforgeable without knowledge of k signature shares on m. A TSS can be embodied from the said specific TSS mentioned above. It can also be embodied with transparent setup, as defined for example in T. Attema et al, Asiacrypt 2021, as follows. Considering a baseline digital signature scheme, a k-threshold signature provides, for any integer k, an algorithm Aggregate.sub.k which, on input a set S of k messages of identical content m, signed by any distinct k out of n replicas, outputs a proof of knowledge of such a set S, including the predicate that the k signers are distinct.

[0087] In the detailed description herein, a “report (φ.sub.i,φ) “denotes any data that carries the information that this data is included in a message sent in phase φ, by a replica whose said set phase number was equal to φ.sub.i when it sent the message.

[0088] In the detailed description herein, a “proof PnS (φ.sub.max,φ)” denotes any data proving the following predicate: there exists t+1 honest replicas that, in phase φ, have their said set phase number lower than or equal to the phase number φ.sub.max.

[0089] In the detailed description herein, “proving” denotes that there is a said verification algorithm, that outputs “true” on the said data if and only if the predicate is true.

[0090] In the detailed description herein, for a<=b integers and I a subset of [1 . . . n], we denote R_{S,[a,b]} a data proving knowledge of numbers w_i, such that each number w_i is signed by a replica i indexed in the set I, and such that the numbers w_i are all in the interval [a,b].

[0091] Miscellaneous

[0092] In the detailed description herein, references to “embodiment,” “an embodiment,” “one non-limiting embodiment.,” “in various embodiments,” etc., indicate that the embodiment(s) described can include a particular feature, structure, or characteristic, but every embodiment might not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described. After reading the description, it will be apparent to one skilled in the relevant art(s) how to implement the disclosure in alternative embodiments.

[0093] In general, terminology can be understood at least in part from usage in context.

[0094] For example, terms, such as “and”, “or”, or “and/or,” as used herein can include a variety of meanings that man depend at least in part upon the context in which such terms are used. Typically, “or” if used to associate a list, such as A, B or C, is intended to mean A, B, and C, here used in the inclusive sense, as well as A, B or C, here used in the exclusive sense. In addition, the term “one or more” as used herein, depending at least in part upon context, can be used to describe any feature, structure, or characteristic in a singular sense or can be used to describe combinations of features, structures or characteristics in a plural sense.

[0095] Similarly, terms, such as “a,” “an,” or “the,” again, can be understood to convey a singular usage or to convey a plural usage, depending at least in part upon context. In addition, the term “based on” can be understood as not necessarily intended to convey an exclusive set of factors and can, instead, allow for existence of additional factors not necessarily expressly described, again, depending at least in part on context.

[0096] The terms “having,” “including,” “containing” and “comprising” or any other variation thereof, are interchangeable, and one of skill in the art will recognize that these terms are open ended terms. They are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but can include other elements not expressly listed or inherent to such process, method, article, or apparatus.

[0097] As used herein, the term “about” or “approximately” means within an acceptable error range for the particular value as determined by one of ordinary skill in the art, which will depend in part on how the value is measured or determined. i.e., the limitations of the measurement system.

[0098] Certain non-limiting embodiments are described below with reference to block diagrams and operational illustrations of methods, processes, devices, and apparatus. It is understood that each block of the block diagrams or operational illustrations, and combinations of blocks in the block diagrams or operational illustrations, can be implemented by means of analog or digital hardware and computer program instructions. These computer program instructions can be provided to a processor of a general-purpose computer to alter its function as detailed herein, a special purpose computer, ASIC, or other programmable data processing apparatus, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, implement the functions/acts specified in the block diagrams or operational block or blocks. In some alternate implementations, the functions/acts noted in the blocks can occur out of the order noted in the operational illustrations. For example, two blocks shown in succession can in fact be executed substantially concurrently or the blocks can sometimes be executed in the reverse order, depending upon the functionality/acts involved.

[0099] Methods for Implementing Linear View-Change in a BFT Protocol

[0100] Responsive Linear View Change from any Proof of Non-Supermajority (PnS)

[0101] According to an aspect, the disclosure relates to a method for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables the non-faulty replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising: [0102] executing, among and by the n replicas, a phase of the BFT protocol, phases being numbered as positive numbers φ=1,2, . . . , in each phase one or several consecutive replicas playing a specific role and being identified as leader replica, a lock certificate being associated with said phase; and [0103] if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiating a view-change with at least the following steps: [0104] if said current phase number φ is different than 1, each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase φ for which said replica P.sub.i received said lock certificate associated with a value I.sub.i, or each replica P.sub.i(i=1 . . . n), sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate: each replica P.sub.i sending to a leader replica L.sub.φ a message containing at least a report(φ.sub.i,φ), appended with said lock certificate (I.sub.i,φ.sub.i) if φ.sub.i≥1, and/or [0105] on the leader replica L.sub.φ side: [0106] if said current phase number φ is equal to 1, said leader replica L.sub.φ sets a value equal to an input I and sends a proposition message to the replicas including said value I, or [0107] if said current phase number φ is different than 1, upon receiving messages from 2t+1 distinct replicas, with one such message from a replica i.sub.max containing a report (φ.sub.imax,φ) such that a phase number φ.sub.imax is the highest phase number φ.sub.i out of the said 2+1 reports (φ.sub.i,φ) received, a phase number φ.sub.max, is then set equal to the phase number φ.sub.imax and a value I.sub.max, is set equal to I.sub.imax the value contained in the lock certificate (I.sub.imax,φ.sub.imax) appended to the message from i.sub.max, the leader replica L.sub.φ generating a message out of said 2t+1 distinct replicas, with: [0108] (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one lock certificate Lc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,PnS(φ.sub.max,φ),Lc.sub.max) to the replicas; or [0109] (ii) if said phase number φ.sub.max is equal to 0, said leader replica L.sub.φ sets the value I equal to an input I.sub.mod and sends a proposition message (I.sub.mod,φ,PnS(0,φ),) to the replicas, in order to make the view-change effective in said distributed system.

[0110] The communication bottleneck of PBFT lies in the subprotocol, denoted as “view change”, in which the leader replica forwards 2t+1 signed messages to each replica. Then, each replica checks that these 2t+1 messages satisfy some predicate, which is that no message content has value is greater than φ.sub.max. In the invention, this is replaced by any responsive subprotocol, denoted as “PnS protocol” that enables replicas to check a generalized version of this predicate. The generalized predicate, denoted PnS, is that no t+1 honest replicas have their PnS protocol input numbers φ.sub.i higher than φ.sub.max. Notice that in the use case of the invention, where such a PnS protocol is used for BFT view change, used with PnS protocol inputs φ.sub.i equal the highest received lock certificate, then, the predicate PnS guarantees that no 2t+1 replicas, i.e., no supermajority, can ever make a report(φ′, φ) for some phase number φ′ strictly greater than φ.sub.max. Since the number 2t+1, which is n-t in the general case, is also known as a “quorum”, then PnS could also be named as “Proof of non-quorum”.

[0111] The invention also allows reducing the latency, by at least two messages. Indeed, in the known methods, the latency was of seven messages before output (8 messages, if the first leader is faulty), while the invention brings a latency of 5 messages (6 messages, if the first leader is faulty).

[0112] The invention thus allows removing the so far quadratic bit communication cost of three desirable properties of consensus protocols with leaders: Responsiveness with Optimal latency, Optimistic Fast Track and Strong Unanimity. In addition, this is achieved simultaneously, with optimal corruption threshold.

[0113] In the case where said phase number φ.sub.max is greater than 0, said at least one lock certificate Lc.sub.max(I.sub.max,φ.sub.max) received by the leader replica L.sub.φ is associated with a value I.sub.max which became the new value for I. If said phase number φ.sub.max is equal to 0, the leader replica L.sub.φ sets itself the value I to an input I.sub.mod. Said input I.sub.mod may be the same at the beginning of the phase, and advantageously is the own input value of the leader replica. Such input values satisfy some publicly checkable validity predicate, as described above, and are considered as “valid” inputs.

[0114] The first phase ϕ=1 differs from the higher ones ϕ≥2, in that it does not contain the first step, denoted “report”. It can be noted that replicas in a phase ϕ perform the instructions of the method as soon as they can, and the numbered steps do not denote any waiting instruction.

[0115] Such a PnS protocol may be applied to the following embodiments: such as in PBFT SBFT, containing 2t+1 strings reports (φ.sub.i,φ) sent by 2t+1 distinct replicas. Thus, they have a size linear in n the number of replicas. The invention as described in this section applies in particular to PnS protocols with size sublinear in n, some of which are exemplified below.

[0116] In an embodiment, the message generating by the leader replica contains at least a proof PnS(φ.sub.max,φ), embodied as of proof of existence of 2t+1 reports (φ.sub.i,φ) signed by 2t+1 replicas, including the phase numbers φ.sub.i, which are all lower than or equal to the phase number φ.sub.max.

[0117] In the known methods, the forwarding of the 2t+1 messages of R to all replicas, done in the step “propose” relative to the proposition messages, has quadratic bit complexity. This is removed thanks to the invention: the steps relative to the setting of φ.sub.i and to the proposition and lock vote messages contain a subprotocol whose purpose is to prove replicas that the value proposed in the step “propose” is such that it comes with a lock certificate formed in some phase ϕ′, and that at most t non-faulty replicas could possibly have received lock certificates formed in phases strictly higher than ϕ′.

[0118] Relatively to such a specific set of inputs (φ.sub.i,Ic.sub.i), a PnS protocol as defined in the invention is advantageously one in which non-faulty replicas in phase φ send one message to a designated leader L.sub.φ among them, such that, upon receiving 2t+1 well-formed messages, a honest leader, also called prover, is able to output a phase number φ.sub.max≤φ, a lock certificate Lc.sub.max relative to this phase, and a proof PnS(φ.sub.max,φ) as defined.

[0119] In an embodiment, for each non-faulty replica P.sub.i in the phase φ, with φ.sub.i≤φ the highest phase number for which said replica P.sub.i received said lock certificate (I.sub.i,φ.sub.i), each message sent by the replicas contains, along with a lock certificate in φ.sub.i if 1≤φ.sub.i, the following embodiment of report (φ.sub.i, φ), denoted as a “list of testimonies to be lower” with: for each integer value φ.sup.0∈[φ.sub.i, . . . , φ], a data, which is signed using a threshold signature system σ of threshold (2t+1), Said signed data is denoted “testimony(φ.sup.0, φ)”, and carries the information that {the said phase number set by the sender in phase φ is lower than or equal to φ.sup.0}, the proof PnS(φ.sub.max, φ) being then embodied as a threshold signature with threshold 2t+1 on the testimony (φ.sub.max,φ), which guarantees that 2t+1 replicas signed it.

[0120] In such an embodiment, in said 2t+1-TSS σ, with L.sub.φ the prover associated to the phase φ, a PnS protocol as defined in the invention may include the following steps: [0121] 1 Every replica P.sub.i sends to L.sub.φ a report (φ.sub.i,φ) (along with a lock certificate in φ.sub.i if 1≤φ.sub.i) along with, for each integer value φ.sup.0∈[φ.sub.i, . . . , φ], one testimony signed using said threshold signature system σ, of the form: “my locked phase number up to φ is lower or equal to φ.sup.0”. [0122] 2 Upon receiving from 2t+1 replicas such well-formed messages, that is: containing a lock certificate for the claimed φ.sub.i, a list of testimonies which is consistent with the claimed φ.sub.i, and such that all the messages specify “up to φ” with φ the current phase number. Then, define φ.sub.max the lowest value for which there exists 2t+1 identical testimonies: “my locked phase number up to φ is lower or equal to φ.sub.max”. The leader L.sub.φ then: [0123] extracts this φ.sub.max and a lock certificate Lc.sub.max relative to φ.sub.max from one of the 2t+1 messages received (it has to be noted that the leader is always able to do so); and [0124] aggregates the 2t+1 testimonies with σ, which constitutes a PnS on (φ.sub.max,φ).

[0125] Such a protocol is a PnS protocol with respect to the locked phase numbers (φ.sub.Plock,Lc(φ.sub.Plock)) held by non-faulty replicas in the phase φ, and the PnS obtained consists of at most φ signatures. In particular, it is of bit size independent of the number of replicas.

[0126] According to another embodiment, a PnS protocol as defined in the invention may include the following steps: [0127] 1. Every replica P.sub.i sends to L.sub.φ a report (φ.sub.i,φ) (along with a lock certificate in φ.sub.i if 1≤φ.sub.i) along with a signature σ.sub.i on φ.sub.i generated using the algorithm AS.SignShare of (Giridharan et al 2021), [0128] 2. Upon receiving from 2t+1 replicas such well-formed messages, that is: [0129] i) containing a lock certificate for the claimed number φ.sub.i, [0130] ii) a signature σ.sub.i on number φ.sub.i such that σ.sub.i verifies the last line “Check” of algorithm AS.VerifyShare of (Giridharan et al 2021). [0131] iii) and such that all n public keys are published with a valid proof of possession (“PoP”, not necessarily the one specified by (Giridharan et al 2021)), then, define φ.sub.max the highest value among the numbers φ.sub.i reported in the 2t+1 well-formed report messages, then a PnS on (φ.sub.max,φ) is constituted by the output of algorithm AS.Agg of (Giridharan et al 2021) applied on the 2t+1 signatures σ.sub.i.

[0132] The method according to the invention does not have a higher complexity than the known methods.

[0133] According to an embodiment, each replica P.sub.i(i=1 . . . n), upon receiving said proposition message (I.sub.mod,φ,PnS(0,φ)) or (I.sub.max,φ,PnS(φ.sub.max,φ),Lc.sub.max) from the leader replica L.sub.φ for the first time in the phase φ, replies with a signed lock vote message (I.sub.mod,φ) or (I.sub.max,φ).

[0134] According to an embodiment, said lock certificate is a (2t+1)-threshold signature on said lock vote message.

[0135] According to an embodiment, the leader replica L.sub.φ, upon receiving 2t+1 lock vote messages for the same (I.sub.mod,φ) or (I.sub.max,φ), issues from said lock vote messages a lock certificate (I.sub.mod,φ) or (I.sub.max,φ), which said leader replica L.sub.φ sends along with said input I.sub.mod or I.sub.max.

[0136] According to an embodiment, each replica P.sub.i(i=1 . . . n), upon receiving from the leader replica L.sub.φ a lock certificate (I.sub.mod,φ) or (I.sub.max,φ) for the first time in the phase φ, whatever the input I, replies with a signed decision vote message (I.sub.mod,φ) or (I.sub.max,φ).

[0137] According to an embodiment, the leader replica L.sub.φ, upon receiving decision vote messages (I.sub.mod,φ) or (I.sub.max,φ) from 2t+I distinct replicas for the same value I.sub.mod or I.sub.max, issues from said decision vote messages a decision certificate (I.sub.mod) or (I.sub.max), which is sent by said leader replica L.sub.φ to the replicas in order to make the view-change effective in said distributed system, and, upon receiving said decision certificate for the value I.sub.mod or I.sub.max, each replica outputs the chosen value I.sub.mod or I.sub.max.

[0138] According to an embodiment, only one lock certificate associated to one phase is formed.

[0139] According to an embodiment, in each phase ϕ≥1, the leader L.sub.ϕ is a publicly known replica, being for example selected at random among n replicas. Then, since less than one third of the replicas are corrupt, thus the expected number of phases until an honest leader replica L.sub.ϕ is selected, is lower than 1.5.

[0140] The method according to the invention may be applied to improve the latency of consensus protocols, as the recent consensus protocol published by Facebook (https://arxiv.orgpdf/2103.03181.pdf), which is faster but has quadratic message complexity.

[0141] In a variant and optimized method, in a step called “alternative condition”, the if condition for replicas to send a lock vote message is strictly relaxed, in that replicas also send a lock vote if their highest phase number for which they have a lock is at least as high as the lock certificate received from the leader. This is the rule for voting applied in (Buchman 2016), (Abraham Gueta Malkhi 2018) and (Giridharan et al 2021).

[0142] In a step called “restriction of communication”, a leader sends a PnS only to replicas for which it received a report message alter it sent the proposition message, and which report a strictly higher lock certificate than the one sent in the report message.

[0143] The benefits of the said “alternative condition” is that it saves on computation complexity, since replicas do not have to check a PnS, unless in the rare event where the leader would not have the highest lock certificate. The benefits of the restriction b) is that it saves on communication complexity since the leader does not send a PnS, unless is the rare event where a replica would report, in a message arriving late, a strictly higher lock certificate than in all 2t+1 reports previously received by the leader.

[0144] It is to be noticed that a variant of the said “restriction on communication” is proposed in (Giridharan et al 2021), under the name “optional unlocking”. There, the leader waits to receive a message of the form “NAck” in response of its proposition message, before it sends a PnS to the sender of the “NAck “message. Hence, this variant has one more round-trip of communication compared to the said “restriction on communication” described here.

[0145] The method may comprise: [0146] each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase φ for which said replica P.sub.i received said Lc(input value I.sub.i, phase number φ.sub.i) or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any Lc; [0147] each replica P.sub.i sends to a leader replica L.sub.φ a report(φ.sub.i,φ), appended with a Lc(I.sub.i,φ.sub.i) if φ.sub.i≥1 [0148] said “restriction on communication”: the leader replica L.sub.φ, upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ.sub.max set to be the highest phase number φ.sub.i received and associated with a value I.sub.max: [0149] (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one Lc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,Lc(I.sub.max,φ.sub.max)) to the replicas, or, [0150] (ii) if said phase number φ.sub.max is equal to 0, said leader replica sets the value I equal to an input I.sub.mod and sends a proposition message (I.sub.mod,φ,⊥) to the replicas, in order to make the view-change effective. [0151] said “restriction on communication”: the leader replica L.sub.φ, only in the situation where: {it has sent a proposition message with a lock certificate Lc.sub.max(I.sub.max,φ.sub.max), and it receives from some replica P.sub.i a report(φ.sub.i,φ) message with a phase number φ.sub.i strictly higher than φ.sub.max}: then leader replica replies to the replica with a PnS(φ.sub.max,φ) [0152] said “alternative condition”: each replica P.sub.i(i=1 . . . n), upon receiving said proposition message (I.sub.max,φ,Lc(I.sub.max, φ.sub.max)) or (I.sub.mod,φ,⊥) from the leader replica L.sub.φ for the first time in the phase φ, if the said set phase number φ.sub.i is lower than or equal to said phase number φ.sub.max contained in the proposed Lc(I,φ.sub.max) if any, or than 0 if no Lc is included in the proposition, replies with a signed lock vote message (I.sub.mod,φ) or (I.sub.max,φ). [0153] i) if the said set phase number φ.sub.i is lower than or equal to said phase number φ.sub.max contained in the proposed Lc(I,φ.sub.max) if any, or than 0 if no Lc is included in the proposition; [0154] ii) [said “alternative condition”] or if it also received a PnS(φ.sub.max,φ);
then it replies with a signed lock vote message (I.sub.mod,φ) or (I.sub.max,φ). [0155] the leader replica L.sub.φ, upon receiving a set of 2t+1 lock votes for said value I: [0156] (iii) forms a lock certificate(I,φ), shortened as “Lc”, consisting of the aggregation of the 2t+1 signatures on said signed lock votes, into a threshold signature, then sends it to the replicas. [0157] replica P.sub.i(i=1 . . . n), upon receiving from the leader replica L.sub.φ a Lc(I,φ) for the first time in the phase φ, whatever the value I, replies with a signed decision vote message.

[0158] The features described above in relation to claim 1 apply as well to this variant.

[0159] Proof of exclusivity (PoE)

[0160] According to another aspect, the disclosure relates to a method for implementing linear view-change in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than t of the n replicas are faulty, and wherein the BFT protocol enables at least 2t+1 of the n replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising: [0161] executing, among and by the n replicas, a phase φ of the BFT protocol, communicating instances of a lock certificate being associated with said phase; and [0162] if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, initiating a view-change with at least the following steps: [0163] each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase φ for which said replica P.sub.i received said lock certificate associated with an input value I.sub.i, or each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate; [0164] each replica P.sub.i sends to a leader replica L.sub.φ a report(φ.sub.i,φ, appended with a full lock certificate (I.sub.i,φ.sub.i) if φ.sub.i≥1, and initiates an instance of an exclusivity protocol with respect to its respective input value h, the leader replica being the chosen prover L, said exclusivity protocol being a protocol that guarantees: [0165] (a) if either said prover L knows a valid value or at least t+1 non-faulty replicas have a valid input value, after a round-trip of messages between said prover L and the replicas, the prover L outputs a valid input I.sub.select and [0166] (b) after another round-trip of messages between said prover L and the replicas, the prover L outputs a report PoE(I.sub.select), [0167] the leader replica L.sub.φ, upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ.sub.max set to be the highest phase number φ.sub.i received and associated with a value I.sub.max: [0168] (i) if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one full lock certificate FLc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φ,PnS(φ.sub.max,φ),FLc.sub.max) to the replicas, with PnS(φ.sub.max,φ) a report generated by the leader replica L.sub.φ out of said 2t+1 distinct replicas; or [0169] (ii) if said phase number φ.sub.max is equal to 0, then said leader replica L.sub.φ selects said valid input I.sub.select, in function of said exclusivity protocol, and sends a proposition message (I.sub.select,φ,PnS(0,φ),) to the replicas, in order to make the view-change effective in said distributed system.

[0170] According to an embodiment, during an instance of the proof of exclusivity protocol, a value I satisfies a condition denoted the Exclusivity Predicate if and only if no other value I′ is a unanimous input of non-faulty replicas, a report PoE(I) being a proof that I satisfies said condition of Exclusivity Predicate.

[0171] An example of such an exclusivity protocol is described in § 5.1.2 of https://eprint.iacr.org/2020/1480 version 25 Nov. 2020.

[0172] The proof of exclusivity protocol may be expressed as followed: every non-faulty replica starts with an input value in some integer range, appended with a certificate of validity that can be publicly checked, this predicate especially being denoted as “certificate” and consisting in the signatures of n-t replicas. A 3-move asynchronous protocol begins between the replicas with any prover, that enables: after the first move, the prover outputs a value I carrying a valid certificate, after the third move, the prover outputs a proof that no more than t non-faulty replicas have the same input value I′, except possibly for I′=I.

[0173] Such an exclusivity protocol, and thus a consensus, may be achieved with better complexity, but without being responsive: each round takes a fixed time, whatever the speed of the network of the distributed system.

[0174] A full lock certificate (v,φ) is the concatenation of a lock certificate (v,φ) and of a PoE(v).

[0175] According to an embodiment, a proof of exclusivity PoE(v) of a value v, relative to a publicly known fixed tag, proves knowledge of one of the two following cases:

[0176] (i) either of a set I ⊂{1, . . . , n} of t+1 distinct indices, together with a signature from each replica i ∈1 for the message (v, tag).

[0177] (ii) or of a set S of 2 t+1 messages (v.sub.j, tag) for j=1, . . . , 2t+1, each signed by a distinct replica, such that no value v.sub.j repeats identically in strictly more than 1 messages.

[0178] According to an embodiment, the proof of knowledge in if the prover is in the case (i), where some value v repeats t+1 times, then said prover proves this with a (t+1)-threshold signature on v

[0179] According to an embodiment, if the prover is in the case (ii), where no value repeats more than t times in S, the prover proves knowledge of a decomposition of S into three disjunct nonempty subsets of values, with repetitions: S=S.sub.low∪ {v.sub.ned} ∪ S.sub.high, all of cardinalities at most t, and such that all values in the subset S.sub.low are strictly smaller than the value v.sub.med, and proves that the value v.sub.med is itself strictly smaller than all values in the subset S.sub.high.

[0180] This output is advantageously a PoE(v). The data provided by the prover implies knowledge of some set S′ of 2t+1 pairs (v.sub.i, tag) signed by distinct replicas, such that the values v.sub.i are organized in three nonempty subsets which are disjunct, each of cardinality at most t. Thus no value v.sub.i repeats identically more than t times in S′.

[0181] According to an embodiment, the exclusivity protocol has a complexity of O(nlog(n)), with n the number of replicas. The known methods have a latency of 3 messages before the output in an execution without corruption, but with a communication complexity of O(n.sup.2|TSS|).

[0182] According to an embodiment, each replica P.sub.i(i=1 . . . n), upon receiving said proposition message (I.sub.select,φ,PnS(0,φ),) from the leader replica L.sub.φ for the first time in the phase φ, replies with a signed lock vote message (I.sub.select,φ).

[0183] According to an embodiment, upon receiving 2t+1 lock vote messages for the same (I.sub.select,φ) and with:

[0184] i) if the prover L already had a full lock certificate associated with its value I.sub.i, the prover L extracts a report PoE(I.sub.i) according to the exclusivity protocol, or

[0185] ii) the prover L had selected a valid input I.sub.select in the previous instance of the exclusivity protocol, and has a valid report PoE(I.sub.select).

the leader replica L.sub.φ aggregates the 2t+1 lock vote messages (I.sub.select,φ), and appends them with said PoE obtained at step i) or step ii), to issue a full lock certificate (I.sub.select,φ), which said leader replica L.sub.φ sends along with said selected input I.sub.select.

[0186] According to an embodiment, each replica P.sub.i(i=1 . . . n), upon receiving from the leader replica L.sub.φ a full lock certificate (I.sub.select,φ) for the first time in the phase φ, whatever the input I, replies with a signed decision vote message (I.sub.select,φ).

[0187] According to an embodiment, the leader replica L.sub.φ, upon receiving decision vote messages (I.sub.select,φ) from 2t+1 distinct replicas for the same value I.sub.select, issues from said decision vote messages a decision certificate (I.sub.select), which is sent by said leader replica L.sub.φ to the replicas in order to make the view-change effective in said distributed system, and, upon receiving said decision certificate for the value I.sub.select, each replica outputs the chosen value I.sub.select and continues said exclusivity protocol.

[0188] This aspect of the invention is applicable to any possible consensus protocol that offers other trade-offs in security, such as allowing 3 messages of latency even if up to a number c of replicas are faulty, at the price of tolerating less corruption threshold: n>=3t+2c−1.

[0189] Devices & Computer-Implemented Methods & Mediums

[0190] The Provided Methods are Advantageously Computer-Implemented Methods.

[0191] Hence, in one embodiment, the provided methods for implementing linear view-change with optimistic responsiveness in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system can be achieved either offline, i.e., not controlled by a device such as a computer-aided system; or alternatively online, i.e. controlled by a computer-aided system, such as one including a device suitable for implementing linear view-change with optimistic responsiveness in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system, and having means adapted to execute the steps of the said methods; or alternatively both offline and online.

[0192] The disclosure hence relates to the non-transitory computer readable storage media and distributed systems as disclosed above.

[0193] The features described above for the methods according to the invention apply to the non-transitory computer readable storage media and the distributed systems.

[0194] A computer-aided system of the disclosure typically includes one or more user interface(s) enabling entry of an input data.

[0195] Embodiments of the disclosure and all of the functional operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the disclosure can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer-readable medium for execution by, or to control the operation of, data processing apparatus.

[0196] The computer-readable medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more of them. The term “data processing apparatus” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them. A propagated signal is an artificially generated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus.

[0197] A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub-programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network

[0198] A computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio player, a Global Positioning System (GPS) receiver, to name just a few. Computer-readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices. e.g., EPROM. EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks.

[0199] Embodiments of the disclosure can be implemented in a computing system that can include a back-end component, e.g., as a data server, or that can include a middleware component, e.g., an application server, or that can include a front-end component. e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the disclosure, or any combination of one or more such back-end, middleware, or front-end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet.

EXAMPLES

Example 1

[0200] Various steps in a first example of a method, according to the disclosure, for implementing linear view-change in a BFT protocol running on a distributed system are depicted in FIG. 1 and will be described in detail in what follows.

[0201] Said distributed system comprises n replicas, with no more than t of the n replicas being faulty, the BFT protocol enabling at least 2t+1 of the n replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients.

[0202] During the execution, among and by the n replicas, of a phase V of the BFT protocol, with communicating instances of a lock certificate being associated with said phase, if 2t+1 communicating instances of said lock certificate are not received by the n replicas within a predetermined timeout period, the method initiates a view-change with at least the following illustrated steps.

[0203] In a step 11, if said current phase number φ is different than 1, each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase number φ for which said replica P.sub.i received said lock certificate associated with a value I.sub.i. If a replica did not receive any lock certificate, said replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0. In a step 12, if φ.sub.i≥1, each replica P.sub.i sending to a leader replica L.sub.φ a message containing at least a report(φ.sub.i,φ), appended with said lock certificate (I.sub.i,φ.sub.i).

[0204] On the leader replica L.sub.φ side, in a step 13, if said current phase number φ is equal to 1, said leader replica L.sub.φ sets a value equal to an input I and sends a proposition message to the replicas including said value I. Otherwise, if said current phase number φ is different than 1, upon receiving valid report messages from 2t+1 distinct replicas, a phase number  .sub.max is set to be the highest φ.sub.i received in a step 14, associated with a value I.sub.max.

[0205] In a step 15, the leader replica L.sub.φ generates a message containing at least a proof PnS(φ.sub.max,φ) out of said 2t+1 distinct replicas, depending on the value of φ.sub.max. Indeed, if said phase number φ.sub.max is greater than 0, said leader replica L.sub.φ, having received at least one lock certificate Lc.sub.max(I.sub.max,φ.sub.max), sends a proposition message (I.sub.max,φPnS(φ.sub.max,φ),Lc.sub.max) to the replicas. Otherwise, if said phase number φ.sub.max, is equal to 0, said leader replica L.sub.φ value I equal to an input I.sub.mod and sends a proposition message (I.sub.mod,φ,PnS(0,φ),) to the replicas. The view-change is thus effective in the distributed system.

[0206] In a step 16, each replica P.sub.i(i=1 . . . n), upon receiving said proposition message (I.sub.mod,φPnS(0,φ),) from the leader replica L.sub.φ for the first time in the phase φ, replies with a signed lock vote message (I.sub.mod,φ). Then, in a step 17, the leader replica L.sub.φ, upon receiving 2t+1 lock vote messages for the same (I.sub.mod,φ), issues from said lock vote messages a lock certificate (I.sub.modφ), which said leader replica L.sub.φ sends along with said input I.sub.mod.

[0207] In a step 18, each replica P.sub.i(i=1 . . . n), upon receiving from the leader replica L.sub.φ a lock certificate (I.sub.mod,φ) for the first time in the phase φ, whatever the input I, replies with a signed decision vote message (I.sub.mod,φ). In a step 19, the leader replica L.sub.φ, upon receiving decision vote messages (I.sub.mod,φ) from 2t+1 distinct replicas for the same value I.sub.mod, issues from said decision vote messages a decision certificate (I.sub.mod), which is sent by said leader replica L.sub.φ to the replicas in order to make the view-change effective in said distributed system.

[0208] In a step 20, each replica outputs the chosen value I.sub.mod.

Example 2

[0209] Various steps in a second example of a method, according to the disclosure, for implementing linear view-change in a BFT protocol running on a distributed system are depicted in FIG. 2 and will be described in detail in what follows.

[0210] This example uses an exclusivity protocol as described above. In a step 21, each replica P.sub.i(i=1 . . . n) sets φ.sub.i the highest phase number up to said current phase number φ for which said replica P.sub.i received said lock certificate associated with an input value I.sub.i. Each replica P.sub.i(i=1 . . . n) sets said phase number φ.sub.i equal to 0 if said replica did not receive any lock certificate.

[0211] In a step 22, each replica P.sub.i sends to a leader replica I.sub.φ a report(φ.sub.i,φ), appended with a full lock certificate (I.sub.i,φ.sub.i) if φ.sub.i≥1, and initiates an instance of an exclusivity protocol with respect to its respective input value I.sub.i, one of the replicas being a chosen prover L.

[0212] Said exclusivity protocol being a protocol that guarantees: (a) (step 23) if either said prover L knows a valid value or at least t+1 non-faulty replicas have a valid input value, after a round-trip of messages between said prover L and the replicas, the prover L outputs a valid input I.sub.select, and (b) (step 24) after another round-trip of messages between said prover L and the replicas, the prover L outputs a report PoE(I.sub.select).

[0213] In a step 25, upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ.sub.max set to be the highest φ.sub.i received and associated with a value I.sub.max, said leader replica L.sub.φ, if said phase number φ.sub.max is greater than 0, having received at least one full lock certificate FLc.sub.max(I.sub.select,φ.sub.max), sends a proposition message (I.sub.max,φ,PnS(φ.sub.max,φ),FLc.sub.max) to the replicas, with PnS(φ.sub.max,φ) a report generated by the leader replica L.sub.φ out of said 2t+1 distinct replicas. Otherwise, if said phase number φ.sub.max is equal to 0, in function of said exclusivity protocol, said leader replica L.sub.φ selects said valid input I.sub.select, and sends a proposition message (I.sub.select,φ,PnS(0,φ),) to the replicas, in order to make the view-change effective in said distributed system.

[0214] In this example, during an instance of the exclusivity protocol, a value I satisfies a condition denoted the Exclusivity Predicate if and only if no other value I′ is a unanimous input of non-faulty replicas, a report PoE(I) being a proof that I satisfies said condition of Exclusivity Predicate.

[0215] In a step 26, each replica P.sub.i(i=1 . . . n), upon receiving said proposition message (I.sub.select,φ,PnS(0,φ),) from the leader replica L.sub.φ for the first time in the phase φ, replies with a signed lock vote message (I.sub.select,φ).

[0216] In a step 27, upon receiving 2t+1 lock vote messages for the same (I.sub.select,φ) and with a step i) if the prover L already had a full lock certificate associated with its value I.sub.i, the prover L extracts a report PoE(I.sub.i) according to the exclusivity protocol, or a step ii) the prover L had selected a valid input I.sub.select in the previous instance of the exclusivity protocol, and has a valid report PoE(I.sub.select), the leader replica L.sub.φ aggregates the 2t+1 lock vote messages (I.sub.select,φ), and appends them with said PoE obtained at step i) or step ii), to issue a full lock certificate(I.sub.select,φ), which said leader replica L.sub.φ sends along with said selected input I.sub.select.

[0217] In a step 28, each replica P.sub.i(i=1 . . . n), upon receiving from the leader replica L.sub.φ a full lock certificate (I.sub.select,φ) for the first time in the phase φ, whatever the input I, replies with a signed decision vote message (I.sub.select,φ).

[0218] In a step 29, the leader replica L.sub.φ, upon receiving decision vote messages (I.sub.select,φ) from 2t+1 distinct replicas for the same value I.sub.select, issues from said decision vote messages a decision certificate (I.sub.select), which is sent by said leader replica L.sub.φ to the replicas in order to make the view-change effective in said distributed system. In a step 30, upon receiving said decision certificate for the value I.sub.select, each replica outputs the chosen value I.sub.select and continues said exclusivity protocol.

[0219] It should be appreciated that in the above description of exemplary embodiments of the disclosure, various features of the disclosure are sometimes grouped together in a single embodiment, figure, or description thereof for the purpose of streamlining the disclosure and aiding in the understanding of one or more of the various inventive aspects. This method of disclosure, however, is not to be interpreted as reflecting an intention that the disclosure requires more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive aspects lie in less than all features of a single foregoing disclosed embodiment. Thus, the claims following the detailed description are hereby expressly incorporated into this detailed description, with each claim standing on its own as a separate embodiment of this disclosure.

[0220] Furthermore, while some embodiments described herein include some, but not other features included in other embodiments, combinations of features of different embodiments are meant to be within the scope of the disclosure, and form different embodiments, as would be understood by those skilled in the art.

[0221] Thus, while certain embodiments have been described, those skilled in the art will recognize that other and further modifications may be made thereto without departing from the spirit of the disclosure, and it is intended to claim all such changes and modifications as falling within the scope of the disclosure. For example, functionality may be added or deleted from the block diagrams and operations may be interchanged among functional blocks. Steps may be added or deleted to methods described within the scope of the present disclosure.

[0222] The above disclosed subject matter is to be considered illustrative, and not restrictive, and the appended claims are intended to cover all such modifications, enhancements, and other implementations, which fall within the true spirit and scope of the present disclosure. Thus, to the maximum extent allowed by law, the scope of the present disclosure is to be determined by the broadest permissible interpretation of the following claims and their equivalents and shall not be restricted or limited by the foregoing detailed description. While various implementations of the disclosure have been described, it will be apparent to those of ordinary skill in the art that many more implementations are possible within the scope of the disclosure. Accordingly, the disclosure is not to be restricted except in light of the attached claims and their equivalents.

REFERENCES

[0223] Christian Badertscher, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. 2017. Bitcoin as a Transaction Ledger: A Composable Treatment. In Advances in Cryptology-CRYPTO 2017-37th Annual International Cryptology Conference, Santa Barbara. Calif., USA, Aug. 20-24, 2017, Proceedings, Part 1 Springer, 324-356. [0224] Michael Ben-Or, 1983, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols (Extended Abstract). In Proceedings of the Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. Montreal, Quebec, Canada. Aug. 17-19, 1983. ACM, 27-30. [0225] Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. 1988. Consensus in the presence of partial synchrony. J. ACM (1988). [0226] Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32, 2 (1985), 374-382. [0227] Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2020. Tight Consistency bounds for Bitcoin. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. [0228] Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. (1982). [0229] Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001. Secure and Efficient Asynchronous Broadcast Protocols. In Advances in Cryptology CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, Calif., USA. Aug. 19-23, 2001, Proceedings (Lecture Notes in Computer Science, Vol. 2139). Springer, 524-541. [0230] Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (New Orleans, Louisiana, USA) (OSDI '99). USENIX Association, Berkeley, Calif., USA. [0231] Neil Giridharan and Heidi Howard and Ittai Abraham and Natacha Crooks and Alin Tomescu, No-Commit Proofs: Defeating Livelock in BFT, Cryptology ePrint Archive, Paper 2021/1308, 2021/09/28, https://eprint.iacr.org/2021/1308 [0232] Leslie Lamport. 1998. The Part-time Parliament. ACM Trans. Comput. Syst. 16, 2 (May 1998), 133-169. [0233] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. 2019. Hotstuff: BFT Consensus with Linearity and Responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019. Toronto, O.N., Canada. Jul. 29-Aug. 2, 2019. ACM, 347-356. [0234] Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32, 2 (1985), 374-382. [0235] Ittai Abraham, T.-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2019. Communication Complexity of Byzantine Agreement, Revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. PODC 2019. Toronto, O.N., Canada, July 29-Aug. 2, 2019. ACM, 317-326. [0236] Erica Blum, Jonathan Katz, Chen-Da Liu Zhang, and Julian Loss. 2020. Asynchronous Byzantine Agreement with Subquadratic Communication. IACR Cryptol, ePrint Arch. 2020 (2020), 851. [0237] Ran Canetti and Tal Rabin. 1993. Fast Asynchronous Byzantine Agreement with Optimal Resilience. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. [0238] Ittai Abraham, Philipp Jovanovic, Mary Mailer, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu. 2021. Reaching Consensus for Asynchronous Distributed Key Generation. In Podc '21. [0239] Eleftherios Kokoris-Kogias, Alexander Spiegelman, and Dahlia Malkhi. 2020. Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures. In ACM CCS 2020. [0240] Pierre-Louis Aublin, Rachid Guerraoui, Nikola Knezevic, Vivien Quéma, and Marko Vukolic. 2015. The Next 700 BFT Protocols. ACM Trans. Comput. Syst. 32, 4 (2015). 12:1-12:45 [0241] Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2018. SBFT: a Scalable Decentralized Trust Infrastructure for Blockchains. CoRR abs/1804.01626 (2018). arXiv:1804.01626 http://arxiv.org/abs/1804.01626 [0242] Ramakrishna Kotla, Lorenzo Alvisi, Michael Dahlin, Allen Clement, and Edmund L. Wong. 2009. Zyzzyva: Speculative Byzantine fault tolerance. ACM Trans. Comput. Syst. 27, 4 (2009), 7:1-7:39. [0243] Ittai Abraham, Guy Gueta, and Dahlia Malkhi. 2018. Hot-Stuff the Linear, Optimal Resilience, One-Message BFT Devil. CoRR abs/1803.05069 (2018). https://eprint, iacr.org/2020/406. [0244] Ittai Abraham, Guy Gueta, Dahlia Malkhi. Lorenzo Alvisi, Ramakrishna Kotla, and Jean-Philippe Martin. 2017. Revisiting Fast Practical Byzantine Fault Tolerance. CoRR abs/1712.01367 (2017). [0245] Ethan Buchman. 2016. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains. Ph.D. Dissertation. University of Guelph. [0246] Vitalik Buterin and Virgil Griffith. 2017. Casper the Friendly Finality Gadget. CoRR abs/1710.09437 (2017). [0247] Thomas Attema, Ronald Cramer, and Matthieu Rambaud. 2020. Compressed Sigma-Protocols for Bilinear Circuits and Applications. Asiacrypt 2021. Cryptology ePrint Archive, Report 2020/1447. version 2021/3/10 https://eprint.iacr.org/eprintbin/getfile.pl?entry=2020/1447&version=20210310:160359&file=1447.pdf. [0248] Xiao Sui and Sisi Duan and Haibin Zhang, BG: A Modular Treatment of BFT Consensus, Cryptology ePrint Archive, Paper 2022/1433, 2022 https://eprint.iacr.org/2022-1433