bracha

Documentation

Overview

package bracha implements Bracha's Reliable Broadcast. The original version of this RBC can be found here (see "FIG. 1. The broadcast primitive"):

Gabriel Bracha. 1987. Asynchronous byzantine agreement protocols. Inf. Comput.
75, 2 (November 1, 1987), 130–143. DOI:https://doi.org/10.1016/0890-5401(87)90054-X

Here we follow the algorithm presentation from (see "Algorithm 2 Bracha’s RBC [14]"):

Sourav Das, Zhuolun Xiang, and Ling Ren. 2021. Asynchronous Data Dissemination
and its Applications. In Proceedings of the 2021 ACM SIGSAC Conference on Computer
and Communications Security (CCS '21). Association for Computing Machinery,
New York, NY, USA, 2705–2721. DOI:https://doi.org/10.1145/3460120.3484808

The algorithms differs a bit. The latter supports predicates and also it don't imply sending ECHO messages upon receiving F+1 READY messages. The pseudo-code from the Das et al.:

01: // only broadcaster node
02: input 𝑀
03: send ⟨PROPOSE, 𝑀⟩ to all
04: // all nodes
05: input 𝑃(·) // predicate 𝑃(·) returns true unless otherwise specified.
06: upon receiving ⟨PROPOSE, 𝑀⟩ from the broadcaster do
07:     if 𝑃(𝑀) then
08:         send ⟨ECHO, 𝑀⟩ to all
09: upon receiving 2𝑡 + 1 ⟨ECHO, 𝑀⟩ messages and not having sent a READY message do
10:     send ⟨READY, 𝑀⟩ to all
11: upon receiving 𝑡 + 1 ⟨READY, 𝑀⟩ messages and not having sent a READY message do
12:     send ⟨READY, 𝑀⟩ to all
13: upon receiving 2𝑡 + 1 ⟨READY, 𝑀⟩ messages do
14:     output 𝑀

In the above 𝑡 is "Given a network of 𝑛 nodes, of which up to 𝑡 could be malicious", thus that's the parameter F in the specification bellow.

On the predicates. If they are updated via `MakePredicateUpdateMsg` and similar, they have to be monotonic. I.e. if a predicate was true for the broadcaster's message, then all the following predicates supplied to the algorithm must be true for that message as well.

Index

• func New(peers []gpa.NodeID, f int, me, broadcaster gpa.NodeID, maxMsgSize int, ...) gpa.GPA

Functions

func New

func New(peers []gpa.NodeID, f int, me, broadcaster gpa.NodeID, maxMsgSize int, predicate func([]byte) bool) gpa.GPA

Create new instance of the RBC.