Systems and methods for implementing linear view-change in a byzantine fault tolerant (BFT) protocol
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 i(i=1 . . . n) sets φ i the highest phase up to said current phase.
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 current phase number φ is different than 1, each replica P i(1=1 . . . n) sets φ i the highest phase number up to said current phase φ for which said replica P i received said lock certificate associated with a value I i , or each replica P i(1=1 . . . n) sets said phase number φ i equal to 0 if said replica did not receive any lock certificate; each replica P i sending to a leader replica L φ a message containing at least a report (φ i ,φ), appended with said lock certificate (I i ,φ i ) if φ i ≥1, and
on the leader replica L φ side:
if said current phase number φ is equal to 1, said leader replica L φ 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 max containing a report (φ imax ,φ) such that a phase number φ imax is the highest phase number φ i out of the said 2t+1 reports (φ i ,φ) received, a phase number φ max is then set equal to the phase number φ imax and a value I max is set equal to I imax the value contained in the lock certificate (I imax ,φ imax) appended to the message from i max , the leader replica L φ generating a message out of said 2t+1 distinct replicas, with:
(i) if said phase number φ max is greater than 0, said leader replica L φ , having received at least one lock certificate Lc max (I max ,φ max ), sends a proposition message (I max ,φ,PnS(φ max ,φ), Lc max ) to the replicas; or
(ii) if said phase number φ max is equal to 0, said leader replica L φ sets the value/equal to an input I mod and sends a proposition message (I 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 generated by the leader replica contains at least a proof PnS((φ max ,φ), embodied as of proof of existence of 2t+1 reports (φ i ,φ) signed by 2t+1 replicas, including the phase numbers φ i , which are all lower than or equal to the phase number φ max .
3. The method of claim 1 , wherein, for each non-faulty replica P i in the phase φ, with φ i ≤φ the highest phase number for which said replica P i received said lock certificate (I i ,φ i ), each message sent by the replicas contains, along with a lock certificate in φ i if 1≤φ i , the following embodiment of report (φ i ,φ), denoted as a “list of testimonies to be lower” with: for each integer value φ 0 ∈[φ i , . . . ,φ], a data, which is signed using a threshold signature system σ of threshold (2t+1), said signed data being denoted “testimony (φ 0 , φ)”, and carrying the information that {the said phase number set by the sender in phase φ is lower than or equal to φ 0 }, the proof PnS(φ max , φ) being then embodied as a threshold signature with threshold 2t+ 1 on the testimony (φ max , φ), which guarantees that 2t+1 replicas signed it.
4. The method of claim 1 -or 2 , wherein each replica P i (i=I . . . n), upon receiving said proposition message from the leader replica L φ 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 φ , upon receiving 2t+ 1 lock vote messages for the same input I mod or I max , issues from said lock vote messages a lock certificate, which said leader replica L φ sends along with said input.
7. The method of claim 6 , wherein each replica P i (i=1 . . . ) , upon receiving from the leader replica L φ 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 φ , 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 φ 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 a value I corresponding to said decision certificate.
9. The method of any one of claims 1 , wherein only one lock certificate associated to one phase is formed.
10. The method of any one of claims 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 current phase number φ is different than 1, each replica P i(1=1 . . . n) sets φ i the highest phase number up to said current phase φ for which said replica Pi received said lock certificate associated with a value I i , or each replica P i(1=1 . . . n) sets said phase number φ i equal to 0 if said replica did not receive any lock certificate; each replica P i sending to a leader replica L φ a message containing at least a report (φ i ,φ), appended with said lock certificate (I i ,φ i ) if φ i ≥1, and
on the leader replica L φ side:
if said current phase number φ is equal to 1, said leader replica L φ 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 max containing a report (φ imax, φ) such that a phase number φ imax is the highest phase number φ i out of the said 2t+1 reports (φ i ,φ) received, a phase number φ max is then set equal to the phase number φ imax and a value I max is set equal to I imax the value contained in the lock certificate (I imax , φ max ) appended to the message from i max , the leader replica L φ generating a message out of said 2t+1 distinct replicas, with:
(i) if said phase number φ max is greater than 0, said leader replica L φ , having received at least one lock certificate Lc max (I max ,φ max ), sends a proposition message (I max , φ,PnS(φ max ,φ) Lc max ) to the replicas; or
(ii) if said phase number φ max is equal to 0, said leader replica L φ sets the value I equal to an input I mod and sends a proposition message (I 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, initiating a view-change with at least the following steps:
if current phase number φ is different than 1, each replica P i(1=1 . . . n) sets φ i the highest phase number up to said current phase φ for which said replica Pi received said lock certificate associated with a value I i , or each replica P i(1=1 . . . n) sets said phase number φ i equal to 0 if said replica did not receive any lock certificate; each replica P i sending to a leader replica L φ a message containing at least a report (φ i ,φ), appended with said lock certificate (I i ,φ i ) if φ i ≥1, and
on the leader replica Lo side:
if said current phase number φ is equal to 1, said leader replica L φ 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 max containing a report (φ imax ,φ) such that a phase number φ imax is the highest phase number oi out of the said 2t+1 reports (φ i ,φ) received, a phase number φ max is then set equal to the phase number P imax and a value I max is set equal to I imax the value contained in the lock certificate (I imax ,φ imax ) appended to the message from i max , the leader replica L φ generating a message out of said 2t+1 distinct replicas, with:
(i) if said phase number φ max is greater than 0, said leader replica Lo, having received at least one lock certificate Lc max (I max ,φ max ), sends a proposition message (I max , φ,PnS(φ max ,φ), Lc max ) to the replicas; or
(ii) if said phase number φ max is equal to 0, said leader replica L φ sets the value I equal to an input I mod and sends a proposition message (I 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 i(i=1 . . . n) sets φ i the highest phase number up to current phase o for which said replica P i received said lock certificate associated with an input value I i , or each replica P i(i=1 . . . n) sets said phase number oi equal to 0 if said replica did not receive any lock certificate;
each replica P i sends to a leader replica L φ a report (φ i ,φ), appended with a full lock certificate (I i ,φ i ) if φ i ≥1, and initiates an instance of an exclusivity protocol with respect to its respective input value I i ,, the leader replica being a 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 select , and
(b) after another round-trip of messages between said prover L and the replicas, the prover L outputs a report POE (I select ),
the leader replica L φ , upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ max set to be the highest phase number φ i received and associated with a value I max :
(i) if said phase number φ max is greater than 0, said leader replica L φ , having received at least one full lock certificate FLc max (I max, φ max ), sends a proposition message (I max ,φ,PnS(φ max ,φ), FLc max ) to the replicas, with PnS(φ max,φ) a report generated by the leader replica L φ out of said 2t+ 1 distinct replicas; or
(ii) if said phase number φ max is equal to 0, then said leader replica L φ selects said valid input I select , in function of said exclusivity protocol, and sends a proposition message (I 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 j , tag) for j=1, . . . , 2t+1, each signed by a distinct replica, such that no value v 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 low ∪{V med }∪S high , all of cardinalities at most t, and such that all values in the subset S low are strictly smaller than the value V med , and proves that the value V med is itself strictly smaller than all values in the subset S high .
16. The method of any one of claims 13 , wherein each replica P i(i=1 . . . n) , upon receiving said proposition message from the leader replica L φ 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 select, φ ) or (I max ,φ) and with:
i) if the prover L already had a full lock certificate associated with its value I i , the prover L extracts a report PoE(I i ) according to the exclusivity protocol, or
ii) the prover L had selected a valid input I select in the previous instance of the exclusivity protocol, and has a valid report POE (I select ), the leader replica L φ 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 φ sends along with said selected input I select or value I max .
18. The method of claim 17 , wherein each replica P i(i=1 . . .n) , upon receiving from the leader replica L φ 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 φ , upon receiving decision vote messages from 2t+1 distinct replicas for the same value I select or I max , issues from said decision vote messages a decision certificate, which is sent by said leader replica L φ 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 select or I 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.
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 i(i=1 . . . n) sets φ i the highest phase number up to current phase φ for which said replica P i received said lock certificate associated with an input value I i , or each replica P i(i=1 . . . n) sets said phase number φ i equal to 0 if said replica did not receive any lock certificate;
each replica P i sends to a leader replica L φ a report (φ i ,φ), appended with a full lock certificate (I i ,φ i ) if φ i ≥1, and initiates an instance of an exclusivity protocol with respect to its respective input value I i ,, the leader replica being a 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 select , and
(b) after another round-trip of messages between said prover L and the replicas, the prover L outputs a report POE(I select ),
the leader replica L φ , upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ max set to be the highest phase number φ i received and associated with a value I max :
(i) if said phase number φ max is greater than 0, said leader replica L φ , having received at least one full lock certificate FLc max (I max ,φ max ), sends a proposition message (I max ,φ, PnS(φ max ,φ), FLc max ) to the replicas, with PnS(φ max ,φ) a report generated by the leader replica L φ out of said 2t+ 1 distinct replicas; or
(ii) if said phase number φ max is equal to 0, then said leader replica L φ selects said valid input I select , in function of said exclusivity protocol, and sends a proposition message (I 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 i(i=1 . . . n) sets φ i the highest phase number up to current phase φ for which said replica P i received said lock certificate associated with an input value I i , or each replica P i(i=1 . . . n) sets said phase number φ i equal to 0 if said replica did not receive any lock certificate;
each replica P i sends to a leader replica L φ a report (φ i ,φ), appended with a full lock certificate (I i ,φ i ) if φ i ≥1, and initiates an instance of an exclusivity protocol with respect to its respective input value I i ,, the leader replica being a 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 select , and
(b) after another round-trip of messages between said prover L and the replicas, the prover L outputs a report POE(I select ),
the leader replica L φ , upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ max set to be the highest phase number φ i received and associated with a value I max :
(i) if said phase number φ max is greater than 0, said leader replica L φ , having received at least one full lock certificate FLc max (I max ,φ max ), sends a proposition message (I max ,φ, PnS(φ max ,φ), FLc max ) to the replicas, with PnS(φ max ,φ) a report generated by the leader replica L φ out of said 2t+1 distinct replicas; or
(ii) if said phase number φ max is equal to 0, then said leader replica L φ selects said valid input I select , in function of said exclusivity protocol, and sends a proposition message (I select ,φ,PnS(0,φ),⊥) to the replicas, in order to make the view-change effective in said distributed system.
24. 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:
each replica P i(i=1 . . . n) sets φ i the highest phase number up to current phase φ for which said replica P i received a LockCertificate (input value I i , phase number φ i ) or each replica P i(i=1 . . . n) sets said phase number φ i equal to 0 if said replica did not receive any LockCertificate;
each replica P i sends to a leader replica L φ a report (φ i ,φ), appended with a LockCertificate (I i ,φ i ) if φ i ≥1
the leader replica L φ , upon receiving a set R of report messages from 2t+1 distinct replicas, with a phase number φ max set to be the highest phase number oi received and associated with a value I max :
(i) if said phase number φ max is greater than 0, said leader replica L φ , having received at least one LockCertificatemax (I max ,φ max ), sends a proposition message (I max ,φ, LockCertificate(I max ,φ max )) to the replicas, or, (ii) if said phase number (max is equal to 0, said leader replica sets the value I equal to an input I mod and sends a proposition message (I mod ,φ,⊥) to the replicas,
the leader replica L φ , only in the situation where: {it has sent a proposition message with a lock certificate Lc max (I max ,φ max ), and it receives from some replica P i , a report (φ i ,φ) message with a phase number φ i strictly higher than φ max }: then leader replies to the replica P i with a Proof_of_non-Supermajority(φ max ,φ) formed out of the report messages,
each replica P i(i=1 . . . n) , upon receiving said proposition message (I max ,φ,LockCertificate(I max ,φ max )) or (I mod ,φ,⊥) from the leader replica L φ for the first time in the phase φ,
i) if the said set phase number φ i is lower than or equal to said phase number φ max contained in the proposed LockCertificate (I,φ 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(φ max ,φ); then it replies with a signed lock vote message (I mod ,φ) or (I max ,φ),
the leader replica L φ , 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 i(i=1 . . . n), upon receiving from the leader replica L φ a Lc(I,φ) for the first time in the phase φ, whatever the value I, replies with a signed decision vote message.