Consensus Potpourri: Information Theoretic HotStuff
Stern, Gilad
Abraham, Ittai
This work presents Information Theoretic HotStuff (IT-HS), a new optimally resilient protocol for solving Byzantine Agreement in partial synchrony with information theoretic security guarantees. In particular, IT-HS does not depend on any PKI or common setup assumptions and is resilient to computationally unbounded adversaries. IT-HS is based on the Primary-Backup view-based paradigm. In IT-HS, in each view, each party sends only a constant number of words to every other party. This yields an O(n2) word and message complexity in each view. In addition, IT-HS requires just O(1) persistent local storage and O(n) transient local storage. Finally, like all Primary-Backup view-based protocols in partial synchrony, after the system becomes synchronous, all nonfaulty parties decide on a value in the first view a nonfaulty leader is chosen. Moreover, like PBFT and HotStuff, IT-HS is optimistically responsive: with a nonfaulty leader, parties decide as quickly as the network allows them to do so, without regard for the known upper bound on network delay. Our work improves in multiple dimensions upon the information theoretic version of PBFT presented by Miguel Castro, and can be seen as an information theoretic variant of the HotStuff paradigm.
 Hello, I will be presenting a work by a tableham myself, Gilan Stel, about an information theoretic approach to the HOSF protocol. So a little bit about the task that we're trying to solve in the network and computation model. We wanna solve the task of Byzantine consensus in a partially synchronous network. We have n parties, f of them can be Byzantine, and we assume that f is strictly less than a third of the total number of parties. The network is partially synchronous, so that means it starts off completely asynchronous, any message can be delayed any finite amount of time. And then at some point in time, called the GST or the global stabilization time, the network becomes synchronous with some known bound delta on maximum message delay. Now it is important to note that parties know when GST is going to occur, or even if it has previously occurred sometime in the past. In addition, parties may crash and then be rebooted any number of times while the network is still asynchronous. And if that happens, only information that they store and persistent memory is saved after a reboot. We want to achieve information theoretic security, so we don't assume our adversary is computationally bounded. And as a standard setting, we only assume that we have authenticated channels, that the adversary cannot break. And by authenticated channels, we mean that when a party receives a message, it knows who sends that message. In consensus protocols, every party i has some input xi. Now a protocol is called a consensus protocol that has the following three properties. The first one is correctness. All non-faulty parties that complete the protocol have the same output. The second one is validity. And validity means that if all parties are non-faulty and they have the same input x, then any non-faulty party that terminates outputs that value of x. And finally, termination, if all non-faulty parties participate in the protocol, they eventually complete it. A common approach to solving the task of consensus in purpose synchrony are primary backup protocols or passes like protocols. In this type of protocol, we have meta rounds called views. And each view has a designated leader. Now we think of the view as an attempt by that leader to reach consensus. Now this attempt might fail, so we might need to run many of those views. And in between each two consecutive views, we also have a view change protocol. Two important metrics for the efficiency of such protocols are the maximal size of messages sent throughout the protocol and the maximum possible amount of persistent memory that any one-party requires. Now with cryptography, it is relatively easy to achieve constant message size and constant persistent memory requirements. So a little bit about the information theoretic solutions to this problem and this approach. In the information theoretic setting, only Casters thesis on PBFT achieved constant persistent memory requirement. Now Casters thesis has a few shortcomings. The first one is that it isn't peer reviewed. The second one is that it requires linear size messages, linear in N in the view change protocol. And technically that linear message size was achieved with cryptographic hash functions. And without those, the protocols are less efficient. The main result of our paper is the following theorem. There exists an optimally resilient, which means N is greater than or equal to 3F plus one. Information theoretic is secure. Byzantine consensus protocol in partial synchrony with constant message size and constant persistent memory requirement. Now the protocol, ITHS, information theoretic hot stuff, only requires authenticated channels. In addition, it has standard performance for information theoretic solutions on other metrics. For example, constant rounds per view, O of N squared messages overall per view and O of N transient memory requirements. So now we will move on to describe different primary backup solutions to the task of consensus and partial synchronous. The first very famous solution is the Texas solution by Leslie Lampert. And in this protocol, we have two rounds per view. The first one is a lock round and the second one is a dumb round. And in addition, when you have the view change protocol that we think of is happening before each view. Now, this solution is not secure in the face of a Byzantine adversary. It is only secure in the face of a crash fault or an emission fault advocacy. And conceptually, the big idea here is that the lock round is supposed to help protect the consensus value. And by that we mean that if consensus has been reached, then having that first lock round will help maintain consensus. The next solution we're gonna look at is the PBFT protocol by Castel and Liskov. So this protocol enhances the risk of the original Paxus protocol and allows us to deal with the Byzantine adversary as well. And this is done by adding another round at the beginning, a proposed round, that is supposed to guarantee non-oppublication. Now, this comes at the cost of a linear message size in the view change protocol. In addition, the PBFT protocol also achieves a strong likeness guarantee called optimistic responsiveness. And intuitively, optimistic responsiveness means that we go as fast as the network allows us to go. Now, more specifically, if we have a non-faulty leader and messages are actually delayed much less than the upper bounded message delay delta, we don't want to achieve consensus in time that is proportional to delta, but in time that is proportional to the actual message delay. And PBFT achieves this. The next solution we're going to look at is the Tenderin protocol by Buchman et al. This protocol manages to lower the maximum message size back to constant size, but loses the optimistic responsiveness property. Now, this happens because of a problem called the hidden lock problem. Intuitively, in the view change, a non-faulty leader needs to wait to hear but locks from all non-faulty parties. And if it wants to guarantee that it hears from all non-faulty parties, then it has to wait delta time to make sure that their messages have arrived. The last solution we're going to look at is the Hotsp protocol by Abel Hamet al. Now, this protocol achieves constant message size and constant persistent memory requirement, but also achieves optimistic responsiveness as well. Now, this is done by adding another round before the lock round, the key round, which solves the hidden lock problem. Now we'll move on to describe our solution, the ITHS protocol. So the ITHS protocol has all of the rounds that the Hotsp protocol has. They propose a key three, a lock and a done round with slightly different names and adds three more rounds in the middle and echo a key one and a key two round, which we'll describe soon. As the diagram suggests in previous solutions, such as the Hotsp protocol, in each round, the leader sends a message to all parties and then they all reply to the leader with a signed message. Now, this allows the leader in a given round to prove that it received a large enough number of messages from a large enough number of parties in a previous round by simply supplying those signatures. Clearly, this is not possible if we don't assume cryptography. So we replace this fan out, fan in type of round with an all to all type of round. Now, for anybody that's familiar with their reliable broadcast protocol, we had to add also an echo round in order to guarantee non-equivocation in the case of a faulty leader. So now we want to talk about our protocol in some more detail and primary backup protocols in general in some more detail. In this type of protocol, in order to guarantee safety and by that we mean that we never commit to two different values. We don't have two parties that commit to two different values. We want to make sure that if a commitment takes place, let's say to a value val in some view V, no other value should ever advance past even the proposal round in any future view V10 so that V tag is greater than V. Now, the way this is implemented is using a locking mechanism. So before sending a lock message with some value val, a non-faulty party sets a local field lock to equal the current view number V and another local field lock val to be the current value descent val. In any future view, that non-faulty party won't be willing to send any advanced message, any message from an advanced round about any other value val tag, unless it receives ample proof that that val tag already advanced past the proposal round in a view later than V. Now, before committing to a value, a non-faulty party receives N minus F lock messages with that same val. Out of those N minus F, at least F plus one are sent by non-faulty parties and intuitively those F plus one parties are gonna be our sentinels. They're gonna make sure that our safety property continues to hold. And intuitively those F plus one parties are never gonna allow any other value to advance past even the proposal stage and then any other value won't ever receive ample proof to open any of the locks. Now we can take our previous intuition and translate it into an important insight of the Paxus protocol. This insight has two parts. So the first one is that if the commitment takes place, we know that F plus one parties set their lock and lock val fields to appropriate values. Now this means that in any future view, they will be willing to inform the view leader about their current lock. Now, that leader can always wait for at least one of those F plus one non-faulty parties and always hear about lock information. A second part of that insight is that it is really enough to receive any late message, any message that is later than a proposed message in order to prove that no commitment took place because if a commitment takes place, no such message should ever be possible in any later view. So if some party is locked on some view lock and with some value val, and it receives a key message in this diagram, a key five and a val five message from a later view with a different value, then it knows that its lock is irrelevant and it can discard it from that. So as stated before, in order to prove that parties can open their locks since no commitment took place, it is enough to show that some other value advanced past the proposal round in the later view. This is done by either proving that a lock was achieved in some protocols or in the hostile protocol, showing that a key was set by some non-faulty party. Now, those proofs need to be transferable. So if a leader receives such a proof and believes that, for example, it received a key and it believes that it can open any lock from an older view, but a different value, it needs to be able to pass that proof on past the proof that a key was set to other parties that might have locks. Now, with cryptography, this is relatively easy. We can use signatures and pass on the signatures as well. Without cryptography, this transferability is entirely non-trivial to achieve. And the first attempt, and it might have been in a very natural first attempt, is just broadcasting every message using Brahma's reliable broadcast. Now, in this case, if some non-faulty party, for example, the leader receives a message, for example, a key message or a lock message, then eventually every non-faulty party will receive that message as well. Now, this means that if a leader receives enough proof that any lock can be opened, then eventually every non-faulty party will receive that proof as well and will be willing to open their locks. Unfortunately, this approach requires unbounded space. This happens because we might need to maintain broadcast sessions from the distant past into the far future. We can't actually bound the number of views we're gonna have, and we might need a broadcast session in each or maybe many broadcast sessions in each view. And each one of those sessions requires some persistent space. A second attempt at achieving transferability notices that we don't actually need to broadcast all messages forever. We only need to show which keys were achieved when. If we remember our intuition from before, even one key that was achieved that was set after a lock was set is enough to open that lock if that key is non-faulty. So in order to achieve this transferability, we can save a full history of our key information. And then we need to send that history to all parties. And then if they have a lock, they will be willing to open their lock if they see that enough keys were set. Now, this is an accentuation, but this still requires unbounded space. I need to save all of my history of keys and even unbounded message size. I need to send a full history of my keys as well. Our third attempt at achieving transferability uses a technique from the Hastov protocol. So from the Hastov protocol, there was notice that if we add around before the lock round, we guarantee that information is passed on in future views as well. More specifically, if some non-faulty party sets a lock with some value val, then it first received N-minusf key messages with that same value val. Now, out of those messages, at least F plus one were sent by non-faulty parties. And we know that we can always wait for at least one of those parties to send its key information in a future view. In our protocol, we know that if a key three is set, then any future leader will hear about key two. And if a leader hears about a key two, then all of their parties will hear about key ones. So each time we add around here, we add a layer of transferability. Now, if we just send one key one, this might not be enough. That is because a key one can change many times while a key two only changes once. So intuitively, when a leader hears about a key two, it expects that everybody will hear about key ones that show that any relevant lock can be opened. Now, a key one, in this case, can change many times. It can for some time have a different value than any lock's value, a given lock's value. And then revert back to the lock's value later. Now, at that point, when it has the same value as a lock's value, it doesn't actually show that the lock can be opened. As stated before, in order to prove to a locked party that it can open its lock, since no commitment took place, we only need to show it that some other value has to be closed around. Now, if some party has a lock with some value val, and the key two is achieved with some different value val tag in a later view, then before setting that key two, a party receives n minus f key one messages. Now, those key one messages have the same value val tag, and at least f plus one of them were sent by non-faulty parties. Now, again, as stated before, the issue with this is that those parties might update their key one values many, many times, but they're not always the same value. So, the key one values many, many times before the key two value is updated again. However, if we look at the last two key one values that those parties set, they're always going to show us that the lock is irrelevant. Either the last one is different than the lock, if it doesn't change. If it's not just enough to show that the lock is irrelevant, or we have two different key ones that are set after the lock, and at least one of them doesn't have the same value as the lock. So, if we either show one key one that is later than the lock and has a different value, or two key ones that are later than the lock, we know that the lock can be opened. So, now we want to actually be convinced that this type of proof actually shows that the lock can be opened. So, the first case, as said before, is that if we have a single key one that is set after a lock with a different value, for example, the last key set is key five with some value of five, which is different than that. Now, if we send the last two keys, in this case key four and key five, we'll see that key five was set later and it has a different value, and the lock can be open. On the other hand, it might be the case that we've changed our keys many times after a lock was set. So, for example, in this diagram, if we send the last two keys and their corresponding values, the key four and key five with val four and val five, we're only going to send ones that have different values. It can't be the case that both val four and val five equal the lock, the lock's value. So, at least one of them will provide proof that the lock is irrelevant. Finally, using this insight, we see that two keys are actually enough. We need to save two keys of each type, and this only requires a constant amount of persistent storage, just the last two keys of each type, and constant message size as well. We can just send the keys and their value. In conclusion, in this work, we present ITHS. ITHS is an optimally resilient, information-theoretically secure, Byzantine consensus protocol and partial synchrony with constant message size and constant persistent space requirement. Thank you very much.
 Hello, I will be presenting a work by a tableham myself,  Gilan Stel, about an information theoretic approach  to the HOSF protocol.  So a little bit about the task that we're trying to solve  in the network and computation model.  We wanna solve the task of Byzantine consensus  in a partially synchronous network.  We have n parties, f of them can be Byzantine,  and we assume that f is strictly less than a third  of the total number of parties.  The network is partially synchronous,  so that means it starts off completely asynchronous,  any message can be delayed any finite amount of time.  And then at some point in time,  called the GST or the global stabilization time,  the network becomes synchronous  with some known bound delta on maximum message delay.  Now it is important to note that parties  know when GST is going to occur,  or even if it has previously occurred  sometime in the past.  In addition, parties may crash and then be rebooted  any number of times while the network is still asynchronous.  And if that happens, only information that they store  and persistent memory is saved after a reboot.  We want to achieve information theoretic security,  so we don't assume our adversary is computationally bounded.  And as a standard setting,  we only assume that we have authenticated channels,  that the adversary cannot break.  And by authenticated channels,  we mean that when a party receives a message,  it knows who sends that message.  In consensus protocols, every party i has some input xi.  Now a protocol is called a consensus protocol  that has the following three properties.  The first one is correctness.  All non-faulty parties that complete the protocol  have the same output.  The second one is validity.  And validity means that if all parties are non-faulty  and they have the same input x,  then any non-faulty party that terminates outputs  that value of x.  And finally, termination,  if all non-faulty parties participate in the protocol,  they eventually complete it.  A common approach to solving the task of consensus  in purpose synchrony are primary backup protocols  or passes like protocols.  In this type of protocol,  we have meta rounds called views.  And each view has a designated leader.  Now we think of the view as an attempt by that leader  to reach consensus.  Now this attempt might fail,  so we might need to run many of those views.  And in between each two consecutive views,  we also have a view change protocol.  Two important metrics for the efficiency of such protocols  are the maximal size of messages  sent throughout the protocol  and the maximum possible amount of persistent memory  that any one-party requires.  Now with cryptography, it is relatively easy  to achieve constant message size  and constant persistent memory requirements.  So a little bit about the information theoretic solutions  to this problem and this approach.  In the information theoretic setting,  only Casters thesis on PBFT  achieved constant persistent memory requirement.  Now Casters thesis has a few shortcomings.  The first one is that it isn't peer reviewed.  The second one is that it requires linear size messages,  linear in N in the view change protocol.  And technically that linear message size  was achieved with cryptographic hash functions.  And without those, the protocols are less efficient.  The main result of our paper is the following theorem.  There exists an optimally resilient,  which means N is greater than or equal to 3F plus one.  Information theoretic is secure.  Byzantine consensus protocol in partial synchrony  with constant message size  and constant persistent memory requirement.  Now the protocol, ITHS, information theoretic hot stuff,  only requires authenticated channels.  In addition, it has standard performance  for information theoretic solutions on other metrics.  For example, constant rounds per view,  O of N squared messages overall per view  and O of N transient memory requirements.  So now we will move on to describe  different primary backup solutions  to the task of consensus and partial synchronous.  The first very famous solution  is the Texas solution by Leslie Lampert.  And in this protocol, we have two rounds per view.  The first one is a lock round  and the second one is a dumb round.  And in addition, when you have the view change protocol  that we think of is happening before each view.  Now, this solution is not secure  in the face of a Byzantine adversary.  It is only secure in the face of a crash fault  or an emission fault advocacy.  And conceptually, the big idea here  is that the lock round is supposed to help protect  the consensus value.  And by that we mean that if consensus has been reached,  then having that first lock round  will help maintain consensus.  The next solution we're gonna look at  is the PBFT protocol by Castel and Liskov.  So this protocol enhances the risk  of the original Paxus protocol  and allows us to deal with the Byzantine adversary as well.  And this is done by adding another round  at the beginning, a proposed round,  that is supposed to guarantee non-oppublication.  Now, this comes at the cost of a linear message size  in the view change protocol.  In addition, the PBFT protocol also achieves  a strong likeness guarantee  called optimistic responsiveness.  And intuitively, optimistic responsiveness  means that we go as fast as the network allows us to go.  Now, more specifically, if we have a non-faulty leader  and messages are actually delayed much less  than the upper bounded message delay delta,  we don't want to achieve consensus  in time that is proportional to delta,  but in time that is proportional  to the actual message delay.  And PBFT achieves this.  The next solution we're going to look at  is the Tenderin protocol by Buchman et al.  This protocol manages to lower the maximum message size  back to constant size,  but loses the optimistic responsiveness property.  Now, this happens because of a problem  called the hidden lock problem.  Intuitively, in the view change,  a non-faulty leader needs to wait to hear  but locks from all non-faulty parties.  And if it wants to guarantee  that it hears from all non-faulty parties,  then it has to wait delta time  to make sure that their messages have arrived.  The last solution we're going to look at  is the Hotsp protocol by Abel Hamet al.  Now, this protocol achieves constant message size  and constant persistent memory requirement,  but also achieves optimistic responsiveness as well.  Now, this is done by adding another round  before the lock round, the key round,  which solves the hidden lock problem.  Now we'll move on to describe our solution,  the ITHS protocol.  So the ITHS protocol has all of the rounds  that the Hotsp protocol has.  They propose a key three, a lock and a done round  with slightly different names  and adds three more rounds in the middle  and echo a key one and a key two round,  which we'll describe soon.  As the diagram suggests in previous solutions,  such as the Hotsp protocol,  in each round, the leader sends a message to all parties  and then they all reply to the leader  with a signed message.  Now, this allows the leader in a given round  to prove that it received a large enough number of messages  from a large enough number of parties  in a previous round  by simply supplying those signatures.  Clearly, this is not possible  if we don't assume cryptography.  So we replace this fan out, fan in type of round  with an all to all type of round.  Now, for anybody that's familiar  with their reliable broadcast protocol,  we had to add also an echo round  in order to guarantee non-equivocation  in the case of a faulty leader.  So now we want to talk about our protocol  in some more detail and primary backup protocols  in general in some more detail.  In this type of protocol, in order to guarantee safety  and by that we mean that we never commit  to two different values.  We don't have two parties that commit to two different values.  We want to make sure that if a commitment takes place,  let's say to a value val in some view V,  no other value should ever advance  past even the proposal round in any future view V10  so that V tag is greater than V.  Now, the way this is implemented  is using a locking mechanism.  So before sending a lock message with some value val,  a non-faulty party sets a local field lock  to equal the current view number V  and another local field lock val  to be the current value descent val.  In any future view, that non-faulty party  won't be willing to send any advanced message,  any message from an advanced round  about any other value val tag,  unless it receives ample proof that that val tag  already advanced past the proposal round  in a view later than V.  Now, before committing to a value,  a non-faulty party receives N minus F lock messages  with that same val.  Out of those N minus F,  at least F plus one are sent by non-faulty parties  and intuitively those F plus one parties  are gonna be our sentinels.  They're gonna make sure that our safety property  continues to hold.  And intuitively those F plus one parties  are never gonna allow any other value  to advance past even the proposal stage  and then any other value won't ever receive ample proof  to open any of the locks.  Now we can take our previous intuition  and translate it into an important insight  of the Paxus protocol.  This insight has two parts.  So the first one is that if the commitment takes place,  we know that F plus one parties set their lock  and lock val fields to appropriate values.  Now this means that in any future view,  they will be willing to inform the view leader  about their current lock.  Now, that leader can always wait  for at least one of those F plus one non-faulty parties  and always hear about lock information.  A second part of that insight  is that it is really enough to receive any late message,  any message that is later than a proposed message  in order to prove that no commitment took place  because if a commitment takes place,  no such message should ever be possible in any later view.  So if some party is locked on some view lock  and with some value val,  and it receives a key message in this diagram,  a key five and a val five message from a later view  with a different value,  then it knows that its lock is irrelevant  and it can discard it from that.  So as stated before,  in order to prove that parties can open their locks  since no commitment took place,  it is enough to show that some other value advanced  past the proposal round in the later view.  This is done by either proving that a lock was achieved  in some protocols or in the hostile protocol,  showing that a key was set by some non-faulty party.  Now, those proofs need to be transferable.  So if a leader receives such a proof  and believes that, for example, it received a key  and it believes that it can open any lock  from an older view, but a different value,  it needs to be able to pass that proof on  past the proof that a key was set  to other parties that might have locks.  Now, with cryptography, this is relatively easy.  We can use signatures and pass on the signatures as well.  Without cryptography, this transferability  is entirely non-trivial to achieve.  And the first attempt,  and it might have been in a very natural first attempt,  is just broadcasting every message  using Brahma's reliable broadcast.  Now, in this case, if some non-faulty party,  for example, the leader receives a message,  for example, a key message or a lock message,  then eventually every non-faulty party  will receive that message as well.  Now, this means that if a leader receives enough proof  that any lock can be opened,  then eventually every non-faulty party  will receive that proof as well  and will be willing to open their locks.  Unfortunately, this approach requires unbounded space.  This happens because we might need to maintain broadcast  sessions from the distant past into the far future.  We can't actually bound the number of views we're gonna have,  and we might need a broadcast session in each  or maybe many broadcast sessions in each view.  And each one of those sessions requires  some persistent space.  A second attempt at achieving transferability  notices that we don't actually need to broadcast  all messages forever.  We only need to show which keys were achieved when.  If we remember our intuition from before,  even one key that was achieved that was set  after a lock was set is enough to open that lock  if that key is non-faulty.  So in order to achieve this transferability,  we can save a full history of our key information.  And then we need to send that history to all parties.  And then if they have a lock,  they will be willing to open their lock  if they see that enough keys were set.  Now, this is an accentuation,  but this still requires unbounded space.  I need to save all of my history of keys  and even unbounded message size.  I need to send a full history of my keys as well.  Our third attempt at achieving transferability  uses a technique from the Hastov protocol.  So from the Hastov protocol,  there was notice that if we add around before the lock round,  we guarantee that information is passed on  in future views as well.  More specifically, if some non-faulty party  sets a lock with some value val,  then it first received N-minusf key messages  with that same value val.  Now, out of those messages,  at least F plus one were sent by non-faulty parties.  And we know that we can always wait  for at least one of those parties  to send its key information in a future view.  In our protocol, we know that if a key three is set,  then any future leader will hear about key two.  And if a leader hears about a key two,  then all of their parties will hear about key ones.  So each time we add around here,  we add a layer of transferability.  Now, if we just send one key one,  this might not be enough.  That is because a key one can change many times  while a key two only changes once.  So intuitively, when a leader  hears about a key two,  it expects that everybody will hear about key ones  that show that any relevant lock can be opened.  Now, a key one, in this case, can change many times.  It can for some time have a different value  than any lock's value, a given lock's value.  And then revert back to the lock's value later.  Now, at that point,  when it has the same value as a lock's value,  it doesn't actually show that the lock can be opened.  As stated before,  in order to prove to a locked party that it can open its lock,  since no commitment took place,  we only need to show it  that some other value has to be closed around.  Now, if some party has a lock with some value val,  and the key two is achieved  with some different value val tag in a later view,  then before setting that key two,  a party receives n minus f key one messages.  Now, those key one messages  have the same value val tag,  and at least f plus one of them  were sent by non-faulty parties.  Now, again, as stated before,  the issue with this is that those parties  might update their key one values many, many times,  but they're not always the same value.  So, the key one values many, many times  before the key two value is updated again.  However, if we look at the last two key one values  that those parties set,  they're always going to show us that the lock is irrelevant.  Either the last one is different than the lock,  if it doesn't change.  If it's not just enough to show that the lock is irrelevant,  or we have two different key ones  that are set after the lock,  and at least one of them doesn't have the same value as the lock.  So, if we either show one key one that is later than the lock  and has a different value,  or two key ones that are later than the lock,  we know that the lock can be opened.  So, now we want to actually be convinced  that this type of proof actually shows that the lock can be opened.  So, the first case, as said before,  is that if we have a single key one  that is set after a lock with a different value,  for example, the last key set is key five  with some value of five, which is different than that.  Now, if we send the last two keys,  in this case key four and key five,  we'll see that key five was set later  and it has a different value, and the lock can be open.  On the other hand, it might be the case  that we've changed our keys many times after a lock was set.  So, for example, in this diagram,  if we send the last two keys and their corresponding values,  the key four and key five with val four and val five,  we're only going to send ones that have different values.  It can't be the case that both val four and val five  equal the lock, the lock's value.  So, at least one of them will provide proof  that the lock is irrelevant.  Finally, using this insight,  we see that two keys are actually enough.  We need to save two keys of each type,  and this only requires a constant amount of persistent storage,  just the last two keys of each type,  and constant message size as well.  We can just send the keys and their value.  In conclusion, in this work, we present ITHS.  ITHS is an optimally resilient, information-theoretically secure,  Byzantine consensus protocol and partial synchrony  with constant message size  and constant persistent space requirement.  Thank you very much.
session3_2_Information_Theoretic_HotStuff_0_47.png session3_2_Information_Theoretic_HotStuff_48_275.png session3_2_Information_Theoretic_HotStuff_276_2639.png session3_2_Information_Theoretic_HotStuff_2640_2687.png session3_2_Information_Theoretic_HotStuff_2688_3587.png session3_2_Information_Theoretic_HotStuff_3588_3635.png session3_2_Information_Theoretic_HotStuff_3636_5267.png session3_2_Information_Theoretic_HotStuff_5268_5399.png session3_2_Information_Theoretic_HotStuff_5400_5999.png session3_2_Information_Theoretic_HotStuff_6000_6371.png session3_2_Information_Theoretic_HotStuff_6372_7391.png session3_2_Information_Theoretic_HotStuff_7392_14111.png session3_2_Information_Theoretic_HotStuff_14112_14159.png session3_2_Information_Theoretic_HotStuff_14160_14843.png session3_2_Information_Theoretic_HotStuff_14844_14903.png session3_2_Information_Theoretic_HotStuff_14904_15791.png session3_2_Information_Theoretic_HotStuff_15792_17111.png session3_2_Information_Theoretic_HotStuff_17112_19259.png session3_2_Information_Theoretic_HotStuff_19260_19871.png session3_2_Information_Theoretic_HotStuff_19872_20855.png session3_2_Information_Theoretic_HotStuff_20856_22715.png session3_2_Information_Theoretic_HotStuff_22716_22787.png session3_2_Information_Theoretic_HotStuff_22788_24227.png session3_2_Information_Theoretic_HotStuff_24228_26987.png session3_2_Information_Theoretic_HotStuff_26988_27035.png session3_2_Information_Theoretic_HotStuff_27036_28895.png session3_2_Information_Theoretic_HotStuff_28896_29591.png session3_2_Information_Theoretic_HotStuff_29592_31535.png session3_2_Information_Theoretic_HotStuff_31536_31619.png session3_2_Information_Theoretic_HotStuff_31620_32231.png session3_2_Information_Theoretic_HotStuff_32232_32279.png session3_2_Information_Theoretic_HotStuff_32280_32762.png
Hello, I will be presenting a work by a tableham myself, Gilan Stel, about an information theoretic approach to the HOSF protocol. So a little bit about the task that we're trying to solve in the network and computation model. We wanna solve the task of Byzantine consensus in a partially synchronous network. We have n parties, f of them can be Byzantine, and we assume that f is strictly less than a third of the total number of parties. The network is partially synchronous, so that means it starts off completely asynchronous, any message can be delayed any finite amount of time. And then at some point in time, called the GST or the global stabilization time, the network becomes synchronous with some known bound delta on maximum message delay. Now it is important to note that parties know when GST is going to occur, or even if it has previously occurred sometime in the past. In addition, parties may crash and then be rebooted any number of times while the network is still asynchronous. And if that happens, only information that they store and persistent memory is saved after a reboot. We want to achieve information theoretic security, so we don't assume our adversary is computationally bounded. And as a standard setting, we only assume that we have authenticated channels, that the adversary cannot break. And by authenticated channels, we mean that when a party receives a message, it knows who sends that message. In consensus protocols, every party i has some input xi. Now a protocol is called a consensus protocol that has the following three properties. The first one is correctness. All non-faulty parties that complete the protocol have the same output. The second one is validity. And validity means that if all parties are non-faulty and they have the same input x, then any non-faulty party that terminates outputs that value of x. And finally, termination, if all non-faulty parties participate in the protocol, they eventually complete it. A common approach to solving the task of consensus in purpose synchrony are primary backup protocols or passes like protocols. In this type of protocol, we have meta rounds called views. And each view has a designated leader. Now we think of the view as an attempt by that leader to reach consensus. Now this attempt might fail, so we might need to run many of those views. And in between each two consecutive views, we also have a view change protocol. Two important metrics for the efficiency of such protocols are the maximal size of messages sent throughout the protocol and the maximum possible amount of persistent memory that any one-party requires. Now with cryptography, it is relatively easy to achieve constant message size and constant persistent memory requirements. So a little bit about the information theoretic solutions to this problem and this approach. In the information theoretic setting, only Casters thesis on PBFT achieved constant persistent memory requirement. Now Casters thesis has a few shortcomings. The first one is that it isn't peer reviewed. The second one is that it requires linear size messages, linear in N in the view change protocol. And technically that linear message size was achieved with cryptographic hash functions. And without those, the protocols are less efficient. The main result of our paper is the following theorem. There exists an optimally resilient, which means N is greater than or equal to 3F plus one. Information theoretic is secure. Byzantine consensus protocol in partial synchrony with constant message size and constant persistent memory requirement. Now the protocol, ITHS, information theoretic hot stuff, only requires authenticated channels. In addition, it has standard performance for information theoretic solutions on other metrics. For example, constant rounds per view, O of N squared messages overall per view and O of N transient memory requirements. So now we will move on to describe different primary backup solutions to the task of consensus and partial synchronous. The first very famous solution is the Texas solution by Leslie Lampert. And in this protocol, we have two rounds per view. The first one is a lock round and the second one is a dumb round. And in addition, when you have the view change protocol that we think of is happening before each view. Now, this solution is not secure in the face of a Byzantine adversary. It is only secure in the face of a crash fault or an emission fault advocacy. And conceptually, the big idea here is that the lock round is supposed to help protect the consensus value. And by that we mean that if consensus has been reached, then having that first lock round will help maintain consensus. The next solution we're gonna look at is the PBFT protocol by Castel and Liskov. So this protocol enhances the risk of the original Paxus protocol and allows us to deal with the Byzantine adversary as well. And this is done by adding another round at the beginning, a proposed round, that is supposed to guarantee non-oppublication. Now, this comes at the cost of a linear message size in the view change protocol. In addition, the PBFT protocol also achieves a strong likeness guarantee called optimistic responsiveness. And intuitively, optimistic responsiveness means that we go as fast as the network allows us to go. Now, more specifically, if we have a non-faulty leader and messages are actually delayed much less than the upper bounded message delay delta, we don't want to achieve consensus in time that is proportional to delta, but in time that is proportional to the actual message delay. And PBFT achieves this. The next solution we're going to look at is the Tenderin protocol by Buchman et al. This protocol manages to lower the maximum message size back to constant size, but loses the optimistic responsiveness property. Now, this happens because of a problem called the hidden lock problem. Intuitively, in the view change, a non-faulty leader needs to wait to hear but locks from all non-faulty parties. And if it wants to guarantee that it hears from all non-faulty parties, then it has to wait delta time to make sure that their messages have arrived. The last solution we're going to look at is the Hotsp protocol by Abel Hamet al. Now, this protocol achieves constant message size and constant persistent memory requirement, but also achieves optimistic responsiveness as well. Now, this is done by adding another round before the lock round, the key round, which solves the hidden lock problem. Now we'll move on to describe our solution, the ITHS protocol. So the ITHS protocol has all of the rounds that the Hotsp protocol has. They propose a key three, a lock and a done round with slightly different names and adds three more rounds in the middle and echo a key one and a key two round, which we'll describe soon. As the diagram suggests in previous solutions, such as the Hotsp protocol, in each round, the leader sends a message to all parties and then they all reply to the leader with a signed message. Now, this allows the leader in a given round to prove that it received a large enough number of messages from a large enough number of parties in a previous round by simply supplying those signatures. Clearly, this is not possible if we don't assume cryptography. So we replace this fan out, fan in type of round with an all to all type of round. Now, for anybody that's familiar with their reliable broadcast protocol, we had to add also an echo round in order to guarantee non-equivocation in the case of a faulty leader. So now we want to talk about our protocol in some more detail and primary backup protocols in general in some more detail. In this type of protocol, in order to guarantee safety and by that we mean that we never commit to two different values. We don't have two parties that commit to two different values. We want to make sure that if a commitment takes place, let's say to a value val in some view V, no other value should ever advance past even the proposal round in any future view V10 so that V tag is greater than V. Now, the way this is implemented is using a locking mechanism. So before sending a lock message with some value val, a non-faulty party sets a local field lock to equal the current view number V and another local field lock val to be the current value descent val. In any future view, that non-faulty party won't be willing to send any advanced message, any message from an advanced round about any other value val tag, unless it receives ample proof that that val tag already advanced past the proposal round in a view later than V. Now, before committing to a value, a non-faulty party receives N minus F lock messages with that same val. Out of those N minus F, at least F plus one are sent by non-faulty parties and intuitively those F plus one parties are gonna be our sentinels. They're gonna make sure that our safety property continues to hold. And intuitively those F plus one parties are never gonna allow any other value to advance past even the proposal stage and then any other value won't ever receive ample proof to open any of the locks. Now we can take our previous intuition and translate it into an important insight of the Paxus protocol. This insight has two parts. So the first one is that if the commitment takes place, we know that F plus one parties set their lock and lock val fields to appropriate values. Now this means that in any future view, they will be willing to inform the view leader about their current lock. Now, that leader can always wait for at least one of those F plus one non-faulty parties and always hear about lock information. A second part of that insight is that it is really enough to receive any late message, any message that is later than a proposed message in order to prove that no commitment took place because if a commitment takes place, no such message should ever be possible in any later view. So if some party is locked on some view lock and with some value val, and it receives a key message in this diagram, a key five and a val five message from a later view with a different value, then it knows that its lock is irrelevant and it can discard it from that. So as stated before, in order to prove that parties can open their locks since no commitment took place, it is enough to show that some other value advanced past the proposal round in the later view. This is done by either proving that a lock was achieved in some protocols or in the hostile protocol, showing that a key was set by some non-faulty party. Now, those proofs need to be transferable. So if a leader receives such a proof and believes that, for example, it received a key and it believes that it can open any lock from an older view, but a different value, it needs to be able to pass that proof on past the proof that a key was set to other parties that might have locks. Now, with cryptography, this is relatively easy. We can use signatures and pass on the signatures as well. Without cryptography, this transferability is entirely non-trivial to achieve. And the first attempt, and it might have been in a very natural first attempt, is just broadcasting every message using Brahma's reliable broadcast. Now, in this case, if some non-faulty party, for example, the leader receives a message, for example, a key message or a lock message, then eventually every non-faulty party will receive that message as well. Now, this means that if a leader receives enough proof that any lock can be opened, then eventually every non-faulty party will receive that proof as well and will be willing to open their locks. Unfortunately, this approach requires unbounded space. This happens because we might need to maintain broadcast sessions from the distant past into the far future. We can't actually bound the number of views we're gonna have, and we might need a broadcast session in each or maybe many broadcast sessions in each view. And each one of those sessions requires some persistent space. A second attempt at achieving transferability notices that we don't actually need to broadcast all messages forever. We only need to show which keys were achieved when. If we remember our intuition from before, even one key that was achieved that was set after a lock was set is enough to open that lock if that key is non-faulty. So in order to achieve this transferability, we can save a full history of our key information. And then we need to send that history to all parties. And then if they have a lock, they will be willing to open their lock if they see that enough keys were set. Now, this is an accentuation, but this still requires unbounded space. I need to save all of my history of keys and even unbounded message size. I need to send a full history of my keys as well. Our third attempt at achieving transferability uses a technique from the Hastov protocol. So from the Hastov protocol, there was notice that if we add around before the lock round, we guarantee that information is passed on in future views as well. More specifically, if some non-faulty party sets a lock with some value val, then it first received N-minusf key messages with that same value val. Now, out of those messages, at least F plus one were sent by non-faulty parties. And we know that we can always wait for at least one of those parties to send its key information in a future view. In our protocol, we know that if a key three is set, then any future leader will hear about key two. And if a leader hears about a key two, then all of their parties will hear about key ones. So each time we add around here, we add a layer of transferability. Now, if we just send one key one, this might not be enough. That is because a key one can change many times while a key two only changes once. So intuitively, when a leader hears about a key two, it expects that everybody will hear about key ones that show that any relevant lock can be opened. Now, a key one, in this case, can change many times. It can for some time have a different value than any lock's value, a given lock's value. And then revert back to the lock's value later. Now, at that point, when it has the same value as a lock's value, it doesn't actually show that the lock can be opened. As stated before, in order to prove to a locked party that it can open its lock, since no commitment took place, we only need to show it that some other value has to be closed around. Now, if some party has a lock with some value val, and the key two is achieved with some different value val tag in a later view, then before setting that key two, a party receives n minus f key one messages. Now, those key one messages have the same value val tag, and at least f plus one of them were sent by non-faulty parties. Now, again, as stated before, the issue with this is that those parties might update their key one values many, many times, but they're not always the same value. So, the key one values many, many times before the key two value is updated again. However, if we look at the last two key one values that those parties set, they're always going to show us that the lock is irrelevant. Either the last one is different than the lock, if it doesn't change. If it's not just enough to show that the lock is irrelevant, or we have two different key ones that are set after the lock, and at least one of them doesn't have the same value as the lock. So, if we either show one key one that is later than the lock and has a different value, or two key ones that are later than the lock, we know that the lock can be opened. So, now we want to actually be convinced that this type of proof actually shows that the lock can be opened. So, the first case, as said before, is that if we have a single key one that is set after a lock with a different value, for example, the last key set is key five with some value of five, which is different than that. Now, if we send the last two keys, in this case key four and key five, we'll see that key five was set later and it has a different value, and the lock can be open. On the other hand, it might be the case that we've changed our keys many times after a lock was set. So, for example, in this diagram, if we send the last two keys and their corresponding values, the key four and key five with val four and val five, we're only going to send ones that have different values. It can't be the case that both val four and val five equal the lock, the lock's value. So, at least one of them will provide proof that the lock is irrelevant. Finally, using this insight, we see that two keys are actually enough. We need to save two keys of each type, and this only requires a constant amount of persistent storage, just the last two keys of each type, and constant message size as well. We can just send the keys and their value. In conclusion, in this work, we present ITHS. ITHS is an optimally resilient, information-theoretically secure, Byzantine consensus protocol and partial synchrony with constant message size and constant persistent space requirement. Thank you very much.
asynchronous, any message can be delayed any time, the network becomes synchronous with some known bound delta on maximum message delay. Now information theoretic security, so we don't termination, if all non-faulty parties primary backup protocols or passes like designated leader. Now we think of the view as an protocol. Two important metrics for the Byzantine consensus protocol in partial synchrony each view. Now, this solution is not secure in protocol. In addition, the PBFT protocol also fast as the network allows us to go. Now, more round, the leader sends a message to all parties number of parties in a previous round by simply before committing to a value, a non-faulty party first attempt, is just broadcasting every message requires unbounded space. This happens because we and this only requires a constant amount of persistent storage, just the last two keys of conclusion, in this work, we present ITHS. ITHS is an optimally resilient, consensus protocol and partial synchrony with