hotstuff

README

hotstuff

relab/hotstuff is an implementation of the HotStuff protocol [1]. It uses the Gorums [2] RPC framework for sending messages between replicas.

Running the examples

We have written an example client located in cmd/hotstuffclient and an example server located in cmd/hotstuffserver. These can be compiled by running make. They read a configuration file named hotstuff.toml from the working directory. An example configuration that runs on localhost is included in the root of the project. To generate public and private keys for the servers, run cmd/hotstuffkeygen/hotstuffkeygen -p 'r*' -n 4 --hosts 127.0.0.1 --tls keys. To start four servers, run scripts/run_servers.sh with any desired options. To start the client, run cmd/hotstuffclient/hotstuffclient.

TODO

• Further benchmarking and testing
• Improving performance
  • Allow leaders to send command hashes instead of resending whole commands.
• Allow a replica to "catch up" by fetching missing nodes
• Add reconfiguration

References

[1] M. Yin, D. Malkhi, M. K. Reiter, G. Golan Gueta, and I. Abraham, “HotStuff: BFT Consensus in the Lens of Blockchain,” Mar 2018.

[2] Tormod Erevik Lea, Leander Jehl, and Hein Meling. Towards New Abstractions for Implementing Quorum-based Systems. In 37th International Conference on Distributed Computing Systems (ICDCS), Jun 2017.

Documentation

Overview

Package hotstuff defines the core types and interfaces that implement the HotStuff protocol. These interfaces allow us to split the implementations into different modules, and each module can have multiple can have multiple implementations.

The following diagram illustrates the relationships between these interfaces:

                OnDeliver()------------------------+
                                                   |                 +--------------+
                OnPropose()---------------------+  |  +--Accept()--->|   Acceptor   |
                                                |  |  |              +--------------+
                OnVote()---------------------+  |  |  |
                                             |  |  |  |              +--------------+
                OnNewView()---------------+  |  |  |  |  +--Exec()-->|   Executor   |
                                          |  |  |  |  |  |           +--------------+
                                          v  v  v  v  |  |
+--------------+                       +-------------------------+                  +------------------+
|              |                       |                         |<--Propose()------|                  |
|              |<--------Sign()--------|                         |                  |                  |
|    Signer    |                       |                         |<--NewView()------|                  |
|              |<--CreateQuorumCert()--|                         |                  |                  |
|              |                       |                         |---OnPropose()--->| ViewSynchronizer |
+--------------+                       |                         |                  |                  |
                                       |        Consensus        |---OnNewView()--->|                  |
+--------------+                       |                         |                  |                  |
|              |                       |                         |---OnFinishQC()-->|                  |
|              |<--VerifyQuorumCert()--|                         |                  +------------------+
|   Verifier   |                       |                         |                              |
|              |<-VerifyPartialCert()--|                         |                              |
|              |                       |                         |-------GetLeader()------------+
+--------------+                       +-------------------------+             |
                                         |  |  |  |  |  |                      v
+----------------+                       |  |  |  |  |  |             +----------------+
|                |<----Propose()---------+  |  |  |  |  |             | LeaderRotation |
|                |                          |  |  |  |  |             +----------------+
|                |<----Vote()---------------+  |  |  |  |
| Config/Replica |                             |  |  |  |             +----------------+
|                |<----NewView()---------------+  |  |  +-Store()---->|                |
|                |                                |  |                |   BlockChain   |
|                |<----Fetch()--------------------+  +----Get()------>|                |
+----------------+                                                    +----------------+

The Consensus interface is the "core" of the system, and it is the part that implements the consensus algorithm. The OnDeliver(), OnPropose(), OnVote(), and OnNewView() methods should be called by some backend service to deliver messages to the Consensus algorithm. The Server struct in the backend/gorums package is an example of such a service.

Index

• type Acceptor
• type Block
  • func GetGenesis() *Block
  • func NewBlock(parent Hash, cert QuorumCert, cmd Command, view View, proposer ID) *Block
  • func (b *Block) Command() Command
  • func (b *Block) Hash() Hash
  • func (b *Block) Parent() Hash
  • func (b *Block) Proposer() ID
  • func (b *Block) QuorumCert() QuorumCert
  • func (b *Block) String() string
  • func (b *Block) ToBytes() []byte
  • func (b *Block) View() View
• type BlockChain
• type Command
• type CommandQueue
• type Config
• type Consensus
• type Executor
• type Hash
  • func (h Hash) String() string
• type ID
• type LeaderRotation
• type NewView
  • func (n NewView) String() string
• type PartialCert
• type PrivateKey
• type PublicKey
• type QuorumCert
• type Replica
• type Signature
• type Signer
• type ToBytes
• type Verifier
• type View
• type ViewSynchronizer

Types

type Acceptor

type Acceptor interface {
	// Accept returns true if the replica should accept the command, false otherwise.
	Accept(Command) bool
}

Acceptor decides is a replica should accept a command.

type Block

type Block struct {
	// contains filtered or unexported fields
}

Block contains a propsed "command", metadata for the protocol, and a link to the "parent" block.

func GetGenesis

func GetGenesis() *Block

GetGenesis returns a pointer to the genesis block, the starting point for the hotstuff blockchain.

func NewBlock

func NewBlock(parent Hash, cert QuorumCert, cmd Command, view View, proposer ID) *Block

NewBlock creates a new Block

func (*Block) Command

func (b *Block) Command() Command

Command returns the command

func (*Block) Hash

func (b *Block) Hash() Hash

Hash returns the hash of the Block

func (*Block) Parent

func (b *Block) Parent() Hash

Parent returns the hash of the parent Block

func (*Block) Proposer

func (b *Block) Proposer() ID

Proposer returns the id of the replica who proposed the block.

func (*Block) QuorumCert

func (b *Block) QuorumCert() QuorumCert

QuorumCert returns the quorum certificate in the block

func (*Block) String

func (b *Block) String() string

func (*Block) ToBytes

func (b *Block) ToBytes() []byte

ToBytes returns the raw byte form of the Block, to be used for hashing, etc.

func (*Block) View

func (b *Block) View() View

View returns the view in which the Block was proposed

type BlockChain

type BlockChain interface {
	// Store stores a block in the blockchain.
	Store(*Block)
	// Get retrieves a block given its hash.
	Get(Hash) (*Block, bool)
}

BlockChain is a datastructure that stores a chain of blocks. It is not required that a block is stored forever, but a block must be stored until at least one of its children have been committed.

type Command

type Command string

Command is a client request to be executed by the consensus protocol.

The string type is used because it is immutable and can hold arbitrary bytes of any length.

type CommandQueue

type CommandQueue interface {
	// GetCommand returns the next command to be proposed.
	GetCommand() *Command
}

CommandQueue is a queue of commands to be proposed.

type Config

type Config interface {
	// ID returns the id of the local replica.
	ID() ID
	// PrivateKey returns the id of the local replica.
	PrivateKey() PrivateKey
	// Replicas returns all of the replicas in the configuration.
	Replicas() map[ID]Replica
	// Replica returns a replica if present in the configuration.
	Replica(ID) (replica Replica, ok bool)
	// Len returns the number of replicas in the configuration.
	Len() int
	// QuorumSize returns the size of a quorum.
	QuorumSize() int
	// Propose sends the block to all replicas in the configuration.
	Propose(block *Block)
	// Fetch requests a block from all the replicas in the configuration.
	Fetch(ctx context.Context, hash Hash)
}

Config holds information about the current configuration of replicas that participate in the protocol, and some information about the local replica. The methods Propose and Fetch should send their respective arguments to all replicas in the configuration, execept the caller.

type Consensus

type Consensus interface {
	// Config returns the configuration used by the replica.
	Config() Config
	// LastVote returns the view in which the replica last voted.
	LastVote() View
	// HighQC returns the highest QC known to the replica.
	HighQC() QuorumCert
	// Leaf returns the last block that was added to the chain.
	// This should be the block with the highest view that is known to the replica.
	Leaf() *Block
	// BlockChain returns the datastructure containing the blocks known to the replica.
	BlockChain() BlockChain
	// CreateDummy inserts a dummy block at View+1.
	// This is useful when a view must be skipped.
	CreateDummy()
	// Propose starts a new proposal. The command is fetched from the command queue.
	Propose()
	// NewView sends a NewView message to the next leader.
	NewView()
	// OnPropose handles an incoming proposal.
	// A leader should call this method on itself.
	OnPropose(block *Block)
	// OnVote handles an incoming vote.
	// A leader should call this method on itself.
	OnVote(cert PartialCert)
	// OnNewView handles an incoming NewView.
	// A leader should call this method on itself.
	OnNewView(msg NewView)
	// OnDeliver handles an incoming block that was requested through the "fetch" mechanism.
	OnDeliver(block *Block)
}

Consensus implements a byzantine consensus protocol, such as HotStuff. It contains the protocol data for a single replica. The methods OnPropose, OnVote, OnNewView, and OnDeliver should be called upon receiving a corresponding message.

type Executor

type Executor interface {
	// Exec executes the given command.
	Exec(Command)
}

Executor is responsible for executing the commands that are committed by the consensus protocol.

type Hash

type Hash [32]byte

Hash is a SHA256 hash

func (Hash) String

func (h Hash) String() string

type ID

type ID uint32

ID uniquely identifies a replica

type LeaderRotation

type LeaderRotation interface {
	// GetLeader returns the id of the leader in the given view.
	GetLeader(View) ID
}

LeaderRotation implements a leader rotation scheme.

type NewView

type NewView struct {
	// The ID of the replica who sent the message.
	ID ID
	// The view that the replica wants to enter.
	View View
	// The highest QC known to the sender.
	QC QuorumCert
}

NewView represents a new-view message.

func (NewView) String

func (n NewView) String() string

type PartialCert

type PartialCert interface {
	ToBytes
	// Signature returns the signature of the block.
	Signature() Signature
	// BlockHash returns the hash of the block that was signed.
	BlockHash() Hash
}

PartialCert is a partial certificate for a block created by a single replica.

type PrivateKey

type PrivateKey interface {
	// PublicKey returns the public key associated with this private key.
	PublicKey() PublicKey
}

PrivateKey is the private part of a replica's key pair.

type PublicKey

type PublicKey interface{}

PublicKey is the public part of a replica's key pair.

type QuorumCert

type QuorumCert interface {
	ToBytes
	// BlockHash returns the hash of the block that the QC was created for.
	BlockHash() Hash
}

QuorumCert (QC) is a certificate for a Block created by a quorum of partial certificates.

type Replica

type Replica interface {
	// ID returns the replica's id.
	ID() ID
	// PublicKey returns the replica's public key.
	PublicKey() PublicKey
	// Vote sends the partial certificate to the other replica.
	Vote(cert PartialCert)
	// NewView sends the quorum certificate to the other replica.
	NewView(msg NewView)
	// Deliver sends the block to the other replica.
	Deliver(block *Block)
}

Replica represents a remote replica participating in the consensus protocol. The methods Vote, NewView, and Deliver must send the respective arguments to the remote replica.

type Signature

type Signature interface {
	ToBytes
	// Signer returns the ID of the replica that generated the signature.
	Signer() ID
}

Signature is a cryptographic signature of a block.

type Signer

type Signer interface {
	// Sign signs a single block and returns the partial certificate.
	Sign(block *Block) (cert PartialCert, err error)
	// CreateQuourmCert creates a quorum certificate from a list of partial certificates.
	CreateQuorumCert(block *Block, signatures []PartialCert) (cert QuorumCert, err error)
}

Signer implements the methods required to create signatures and certificates.

type ToBytes

type ToBytes interface {
	// ToBytes returns the object as bytes.
	ToBytes() []byte
}

ToBytes is an object that can be converted into bytes for the purposes of hashing, etc.

type Verifier

type Verifier interface {
	// VerifyPartialCert verifies a single partial certificate.
	VerifyPartialCert(cert PartialCert) bool
	// VerifyQuorumCert verifies a quorum certificate.
	VerifyQuorumCert(qc QuorumCert) bool
}

Verifier implements the methods required to verify partial and quorum certificates.

type View

type View uint64

View is a number that uniquely identifies a view.

type ViewSynchronizer

type ViewSynchronizer interface {
	LeaderRotation
	// OnPropose should be called when the local replica has received a new valid proposal.
	OnPropose()
	// OnFinishQC should be called when the local replica has created a new qc.
	OnFinishQC()
	// OnNewView should be called when the local replica receives a valid NewView message.
	OnNewView()
	// Init gives the synchronizer a consensus instance to synchronize.
	Init(Consensus)
	// Start starts the synchronizer.
	Start()
	// Stop stops the synchronizer.
	Stop()
}

ViewSynchronizer synchronizes replicas to the same view.