Hierarchical Byzantine Agreement. Nearly all of the Byzantine fault tolerant agreement strategies published in the literature assume a flat peer-to-peer communication model. This assumption does not necessarily mean that all the parties are connected with point-to-point links. But, it does mean that the algorithms/mechanisms used to tolerate Byzantine faults attempt to establish agreement among all of the participants as a whole set. A contrasting approach is to first reach agreement within small subsets, for example pairs, of the participants and then reach agreement among the subsets. One benefit of the latter approach is greatly reduced bandwidth. The following paragraphs describe Hierarchical Byzantine Agreement and how this bandwidth is saved. To reach agreement in Byzantine fault scenarios, multiple rounds of communication exchange are required. According to the well-developed understanding of Byzantine fault tolerance, an additional round of exchange is needed for every additional Byzantine fault to be tolerated. In nearly all of the published algorithms, each of the rounds of exchange requires retransmitting all the data received in the previous round. A reduced representation of a data message (e.g. a hash) could be sent out during all but the first round of exchanges. However, using a reduced representation would lead to reduced coverage for failures. The extreme case makes this point obvious—if the hash was simply parity, half of all failures would not be detected. Note that this hash should not be confused with the digital signatures referenced above. These two mechanisms serve totally different purposes. The hash would be used to reduce the size of messages in subsequent rounds of communication; whereas, digital signatures are used to reduce the number of fault containment zones required. In hierarchical Byzantine agreement, each subset of receivers agree among themselves whether they have all received a message correctly. If they have received the message correctly, they need only send out a single status bit that indicates this during the next round of exchange. Thus, subsequent rounds of communication that would require entire messages to be exchanged in the well-known Byzantine algorithms are now reduced to a single status bit that indicates whether the entire message was received correctly or not. One could construct a hierarchical Byzantine agreement scheme that relaxes this all-or-nothing agreement, but that is outside the scope of this report. Another variation of hier...
