rebro

README

ReBro - Reliable Broadcast

Rebro - is an asynchronous byzantine reliable quorum broadcast

Package rebro defines interfaces enabling:

• High throughput censorship resistant data certification(e.g. for availability)
• Static, dynamic or randomized quorums
• Customization of hashing functions and signing schemes, including aggregatable signatures.
• Customization of broadcasting algorithms and networking stacks
• Customizable quorum fault parameters and sizes.

For more details on the interfaces see code comments.

Use Cases

Besides using it for data availability certification, on can use it for sequencing.

Variant 1

A trivial sequencing scheme to implement here would be to:

• Require full quorum as finalization condition
• Order blocks by public keys of quorum participants lexicographically

This scheme pertains censorship resistant and has multiple data proposers within a round.

Variant 2

A round-robin without a stake:

• A QuorumCertificate is initialized with a list of sequencer public keys in the order.
• On each round, the QuorumCertificate only accepts messages from the predefined rotating sequencer and signatures over those from all other sequencers.

Then, on top of that, more sophisticated schemas can be applied, like the addition of stakes, etc.

Gossip Based implementation

gossip is the current only rebro implementation uses gossiping as its backbone, which tradeoffs propagation speed for scalability.

Why GossipSub?

As we already covered libp2p, the GossipSub question becomes half covered. Still, we don't want to pull every single protocol that libp2p ecosystem brings and deliberately select protocols that solve relevant problems. The GossipSub version of reliable broadcast has one important property - peer/node number scale. The GossipSub can scale to dozens thousands nodes network as demonstrated by Ethereum's beacon chain. Initial implementation of reliable broadcast uses GossipSub to enable full and (potentially) light clients to follow the reliable broadcast network along, allowing networks to scale to thousands of simultaneous validators/proposers.

Documentation

Index

• type Broadcaster
• type Certificate
• type Certifier
• type Hasher
• type Message
  • func (m *Message) Validate() error
• type MessageID
• type MessageIDDecoder
• type NetworkID
  • func (nid NetworkID) String() string
• type Orchestrator
• type QuorumCertificate

Types

type Broadcaster

type Broadcaster interface {
	// Broadcast broadcasts and delivers messages from quorum participants and signatures over them
	// until QuorumCertificate is finalized.
	// Broadcast takes full ownership over QuorumCertificate, and it must not be modified until
	// Broadcast finishes execution.
	Broadcast(context.Context, Message, QuorumCertificate) error
}

Broadcaster reliably broadcasts, delivers and commits over messages. It verifies Messages delivered from other quorum participants and accumulates them into QuorumCertificate until its finalized.

Broadcaster defines interface for asynchronous byzantine reliable quorum broadcast. It is responsible for reliable broadcasting and certification of an arbitrary data without partial synchrony. It enables parallel quorum certificates and multiple broadcasters can propose their Messages simultaneously that other quorum participants attest to.

Broadcaster enables optionality(through polymorphism) for networking algorithms (leader-based or mesh-based) by decoupling certificate data structure.

It signs over broadcasted MessageIDs automatically after verifying them using Signer. TODO: Explain rules around rounds

type Certificate

type Certificate interface {
	// Message returns Message that Certificate attests to.
	Message() Message
	// Signatures provides list of all the signatures in the Certificate.
	Signatures() []crypto.Signature
	// AddSignature appends signature of a particular signer to the Certificate.
	// Signature is expected to be verified beforehand.
	// Reports true if enough signatures were collected for complete Certificate.
	AddSignature(crypto.Signature) (bool, error)
}

Certificate maintains a set of signatures/acknowledgements from a quorum certifying validity of an arbitrary broadcasted message. Validity rules are not defined by Certificate and are an external concern.

type Certifier

type Certifier interface {
	// Certify executes verification of every Message delivered to QuorumCertificate
	// within a broadcasting round.
	// Message is guaranteed to be valid by the rules in QuorumCertificate.
	Certify(context.Context, Message) error
}

Certifier performs application-specific stateful certification of messages. It used by Broadcaster during broadcasting rounds.

type Hasher

type Hasher interface {
	Hash(Message) ([]byte, error)
}

Hasher hashes Messages to cross-check their validity with MessageID.Hash

type Message

type Message struct {
	// ID holds MessageID of the Message.
	ID MessageID
	// Data holds arbitrary bytes data of the message.
	Data []byte
}

Message is message to be reliably broadcasted.

func (*Message) Validate

func (m *Message) Validate() error

type MessageID

type MessageID interface {
	// Round returns the monotonically increasing round of the broadcasted message.
	Round() uint64
	// Signer returns identity of the entity committing to the message.
	Signer() []byte
	// Hash returns the hash digest of the message.
	Hash() []byte
	// String returns string representation of the message.
	String() string
	// MarshalBinary serializes MessageID into series of bytes.
	// Must return canonical representation of MessageData
	MarshalBinary() ([]byte, error)
	// UnmarshalBinary deserializes MessageID from a series of bytes.
	UnmarshalBinary([]byte) error
	// Validate performs the basic validation messageID's properties before it will be used across the protocol.
	Validate() error
}

MessageID contains metadata that uniquely identifies a broadcasted message. It specifies a minimally required canonical interface all messages should conform to in order to be securely broadcasted.

type MessageIDDecoder

type MessageIDDecoder func([]byte) (MessageID, error)

MessageIDDecoder unmarshalls Messages of a particular type.

type NetworkID

type NetworkID string

NetworkID identifies a particular network of nodes.

func (NetworkID) String

func (nid NetworkID) String() string

String returns string representation of NetworkID.

type Orchestrator

type Orchestrator interface {
	// NewBroadcaster instantiates a new Broadcaster.
	NewBroadcaster(NetworkID, crypto.Signer, Certifier, Hasher, MessageIDDecoder) (Broadcaster, error)
}

Orchestrator orchestrates multiple Broadcaster instances.

type QuorumCertificate

type QuorumCertificate interface {
	// Add constructs new Certificate from given the given message and adds it to the set
	// performing necessary verification.
	Add(Message) error
	// Get retrieves particular Certificate by the MessageID of the committed MessageData.
	Get(MessageID) (Certificate, bool)
	// Delete deletes Certificate by the MessageID of the committed MessageData.
	Delete(MessageID) bool
	// List provides all completed Certificates in the QuorumCertificate.
	List() []Certificate
	// Finalize attempts to finalize the QuorumCertificate.
	// It reports whether the finalization conditions were met.
	// The finalization conditions are defined by the implementation.
	// It may additionally perform expensive computation, like signature aggregation.
	Finalize() (bool, error)
}

QuorumCertificate is a set data Certificates by a quorum. It accumulates data Certificates propagated over Broadcaster network by quorum participants and maintains *local view* of Certificates.

QuorumCertificate is mutable and append-only until its finalized. It expects arbitrary number of new Certificates to be added until finalization is triggered. The finalization conditions and quorums are implementation specific.