mirbft

README

MirBFT Library

⚠ ⚠ ⚠

This project has been archived by the project maintainers as the development has been moved to https://github.com/filecoin-project/mir.

This open-source project is part of Hyperledger Labs.

It aims at developing a production-quality implementation of:

• a general framework for easily implementing distributed protocols
• the ISS Byzantine fault tolerant consensus protocol.

MirBFT is intended to be used as a scalable and efficient consensus layer in Filecoin subnets and, potentially, as a Byzantine fault tolerant ordering service in Hyperledger Fabric.

Overview

MirBFT is a library that provides a general framework for implementing distributed algorithms in a network transport, storage, and cryptographic algorithm agnostic way. MirBFT hopes to be a building block of a next generation of distributed systems, being used by many applications.

Insanely Scalable State Machine Replication

The first algorithm to be implemented in MirBFT is called ISS (Insanely Scalable SMR), a state-of-the-art atomic broadcast protocol which can be utilized by any distributed system.

ISS improves on traditional atomic broadcast protocols like PBFT and Raft, which always have a single active leader that proposes batches of requests for ordering, by allowing multiple leaders to do so concurrently, without giving up total order guarantees. The multi-leader nature of ISS leads to exceptional performance, especially on wide area networks, but should be suitable for LAN deployments as well.

Structure and Usage

MirBFT is a framework for implementing distributed algorithms (also referred to as distributed protocols) meant to run on a distributed system. The basic unit of a distributed system is a node. Each node locally executes (its portion of) an algorithm, sending and receiving messages to and from other nodes over a communication network.

MirBFT models a node of such a distributed system and presents the consumer (the programmer using MirBFT) with a Node abstraction. The Node receives requests, processes them (while coordinating with other Nodes using the distributed protocol), and eventually delivers them to a (consumer-defined) application. Fundamentally, MirBFT's purpose can be summed up simply as receiving requests from the consumer and delivering them to an application as prescribed by some protocol. Te ISS protocol, for example, being a total order broadcast protocol, guarantees that all requests received by the nodes will be delivered to the application in the same order.

Note that the application need not necessarily be an end-user application - any program using MirBFT is, an application from MirBFT's point of view. While the application logic is (except for the included sample demos) always expected to be provided by the MirBFT consumer, this need not be the case for the protocol. While the consumer is free to provide a custom protocol component, MirBFT will provide out-of-the-box implementations of different distributed protocols for the consumer to select (the first of them being ISS).

We now describe how the above (providing an application, selecting a protocol, etc.) works in practice. This is where MirBFT's modular design comes into play. The Node abstraction mentioned above is implemented as a Go struct that contains multiple modules. In short, when instantiating a Node, the consumer of MirBFT provides implementations of these modules to MirBFT. For example, instantiating a node might look as follows:

    // Example Node instantiation adapted from samples/chat-demo/main.go
    node, err := mirbft.NewNode(/*some more arguments*/ &modules.Modules{
        Net:      grpcNetworking,
        // ...
        Protocol: issProtocol,
        App:      NewChatApp(reqStore),
        Crypto:   ecdsaCrypto,
    })

Here the consumer provides modules for networking (implements sending and receiving messages over the network, in this case using gRPC), the protocol logic (using the ISS protocol), the application (implementing the logic of a chat app), and a cryptographic module (able to produce and verify digital signatures using the ECDSA algorithm). There are more modules a Node is using, some of them always have to be provided, some can be left out and MirBFT will fall back to default built-in implementations. Some modules, even though they always need to be explicitly provided at Node instantiation, are part of MirBFT and can themselves be instantiated easily using MirBFT library functions.

Inside the Node, the modules interact using Events. Each module independently consumes, processes, and outputs Events. This approach bears resemblance to the actor model, where Events exchanged between modules correspond to messages exchanged between actors.

The Node implements an event loop, where all Events created by modules are stored in a buffer and, based on their types, distributed to their corresponding modules for processing. For example, when the networking module receives a protocol message over the network, it generates a MessageReceived Event (containing the received message) that the Node implementation routes to the protocol module, which processes the message, potentially outputting SendMessage Events that the Node implementation routes back to the networking module.

The architecture described above enables a powerful debugging approach. All Events in the event loop can, in debug mode, be recorded, inspected, or even replayed to the Node using a debugging interface.

The high-level architecture of a Node is depicted in the figure below. For more details, see the module interfaces and a more detailed description of each module in the Documentation.

Relation to the Mir-BFT algorithm

The term Mir-BFT was introduced as a name for a scalable atomic broadcast algorithm - the Mir-BFT algorithm. The MirBFT library initially started as an implementation of that (old) algorithm - thus the shared name - but the algorithm implemented within the library has since been replaced by its modular and superior successor, ISS. Thus, we refer to the library / framework as MirBFT, and to the algorithm it currently implements as ISS. Since MirBFT is designed to be modular and versatile, ISS is just one (the first) of the algorithms implemented in ISS.

Current Status

This library is in development and not usable yet. This document describes what the library should become rather than what it currently is. This document itself is more than likely to still change. You are more than welcome to contribute to accelerating the development of the MirBFT library. Have a look at the Contributions section if you want to help out!

Compiling and running tests

The MirBFT library relies on Protocol Buffers. The protoc compiler and the corresponding Go plugin need to be installed. Moreover, some dependencies require gcc to be installed as well. On Ubuntu Linux, those can be installed using

sudo snap install --classic go
sudo snap install --classic protobuf
sudo apt install gcc

Once instaled, the Protocol Buffer files need to be generated by executing

go generate ./protos

in the mirbft root repository directory. This command also has to be executed each time the .proto files in the protos folder change.

Now the tests can be run by executing

go test

The dependencies should be downloaded and installed automatically.

Documentation

For a description of the design and inner workings of the library, see MirBFT Library Architecture.

For a small demo application, see /samples/chat-demo

Contributing

Contributions are more than welcome!

If you want to contribute, have a look at our Contributor's guide and at the open issues. If you have any questions (specific or general), do not hesitate to drop an email to the active maintainer(s).

Public Bi-Weekly Community Call

There is a public community call once every two weeks. The current status, any issues, future plans, and anything relevant to the project will be discussed. Whether you have any questions that you want to ask or you have a proposal to discuss, or whether you just want to listen in, feel free to join!

Meeting information:

• Time: Tuesdays in the even weeks (wrt. week number in the calendar year), between 09:00 GMT and 09:40 GMT
• Join link: https://us05web.zoom.us/j/82410342226?pwd=bmxnOXBxZnRUN2dyTGVWQk16RW9JUT09
• Meeting ID: 824 1034 2226
• Passcode: HQG5z5
• Upcoming calls:
  • Mar 22nd 2022
  • Apr 5th 2022 -- CANCELED
  • Apr 19th 2022

Research prototypes

The research branch contains code developed independently as a research prototype of the (old) Mir BFT protocol and was used to produce experimental results for the (old) Mir BFT research paper.

The research-iss branch contains code developed independently as a research prototype of the ISS protocol and was used to produce experimental results for the EuroSys22 research paper.

Summary of references

• Public Discord channel
• Hyperledger Labs page
• Paper describing the algorithm: Extended version
• Original PBFT paper

Active maintainer(s)

• Matej Pavlovic (matopavlovic@gmail.com)

Initial committers

• Jason Yellick
• Matej Pavlovic
• Chrysoula Stathakopoulou
• Marko Vukolic

Sponsor

Angelo de Caro (adc@zurich.ibm.com).

License

The MirBFT library source code is made available under the Apache License, version 2.0 (Apache-2.0), located in the LICENSE file.

Acknowledgments

This work has been supported in part by the European Union's Horizon 2020 research and innovation programme under grant agreement No. 780477 PRIViLEDGE.

Documentation

Index

• Variables
• type Node
  • func NewNode(id t.NodeID, config *NodeConfig, m *modules.Modules) (*Node, error)
  • func (n *Node) Run(exitC <-chan struct{}, tickC <-chan time.Time) error
  • func (n *Node) Status(ctx context.Context) (*statuspb.NodeStatus, error)
  • func (n *Node) Step(ctx context.Context, source t.NodeID, msg *messagepb.Message) error
  • func (n *Node) SubmitRequest(ctx context.Context, clientID t.ClientID, reqNo t.ReqNo, data []byte, ...) error
• type NodeConfig
  • func DefaultNodeConfig() *NodeConfig

Variables

var ErrStopped = fmt.Errorf("stopped at caller request")

Types

type Node

type Node struct {
	ID     t.NodeID    // Protocol-level node ID
	Config *NodeConfig // Node-level (protocol-independent) configuration, like buffer sizes, logging, ...
	// contains filtered or unexported fields
}

Node is the local instance of MirBFT and the application's interface to the mirbft library.

func NewNode

func NewNode(
	id t.NodeID,
	config *NodeConfig,
	m *modules.Modules,
) (*Node, error)

NewNode creates a new node with numeric ID id. The config parameter specifies Node-level (protocol-independent) configuration, like buffer sizes, logging, ... The modules parameter must contain initialized, ready-to-use modules that the new Node will use.

func (*Node) Run

func (n *Node) Run(exitC <-chan struct{}, tickC <-chan time.Time) error

Run starts the Node. First, it loads the contents of the WAL and enqueues all its contents for processing. This makes sure that the WAL events end up first in all the modules' processing queues. Then it adds an Init event to the work items, giving the modules the possibility to perform additional initialization based on the state recovered from the WAL. Run then launches the processing of incoming messages, time ticks, and internal events. The node stops when exitC is closed. Logical time ticks need to be written to tickC by the calling code. The function call is blocking and only returns when the node stops.

func (*Node) Status

func (n *Node) Status(ctx context.Context) (*statuspb.NodeStatus, error)

Status returns a static snapshot in time of the internal state of the Node. TODO: Currently a call to Status blocks until the node is stopped, as obtaining status is not yet implemented.

Also change the return type to be a protobuf object that contains a field for each module
with module-specific contents.

func (*Node) Step

func (n *Node) Step(ctx context.Context, source t.NodeID, msg *messagepb.Message) error

Step inserts a new incoming message msg in the Node. The source parameter specifies the numeric ID of the sender of the message. The Node assumes the message to be authenticated and it is the caller's responsibility to make sure that msg has indeed been sent by source, for example by using an authenticated communication channel (e.g. TLS) with the source node.

func (*Node) SubmitRequest

func (n *Node) SubmitRequest(
	ctx context.Context,
	clientID t.ClientID,
	reqNo t.ReqNo,
	data []byte,
	authenticator []byte) error

SubmitRequest submits a new client request to the Node. clientID and reqNo uniquely identify the request. data constitutes the (opaque) payload of the request. SubmitRequest is safe to be called concurrently by multiple threads.

type NodeConfig

type NodeConfig struct {
	// Logger provides the logging functions.
	Logger logging.Logger
}

The NodeConfig struct represents configuration parameters of the node that are independent of the protocol the Node is executing. NodeConfig only contains protocol-independent parameters. Protocol-specific parameters should be specified when instantiating the protocol implementation as one of the Node's modules.

func DefaultNodeConfig

func DefaultNodeConfig() *NodeConfig

DefaultNodeConfig returns the default node configuration. It can be used as a base for creating more specific configurations when instantiating a Node.