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 Credentials
• 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 is the mechanism that decides wether a command should be accepted by the replica

type Block

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

func GetGenesis

func GetGenesis() *Block

Genesis 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

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 theBlock

func (*Block) Parent

func (b *Block) Parent() Hash

Parent returns the hash of the parentBlock

func (*Block) Proposer

func (b *Block) Proposer() ID

Proposer returns the id of the proposer

func (*Block) QuorumCert

func (b *Block) QuorumCert() QuorumCert

Certificate returns the certificate that this Block references

func (*Block) String

func (b *Block) String() string

func (*Block) ToBytes

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

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

type Command

type Command string

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

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 this replica
	ID() ID
	// PrivateKey returns the id of this 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 Replicas and provides methods to send messages to the replicas

type Consensus

type Consensus interface {
	// Config returns the configuration of this 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 proposed block
	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
	Propose()
	// NewView sends a NewView message to the next leader
	NewView()
	// OnPropose handles an incoming proposal
	OnPropose(block *Block)
	// OnVote handles an incoming vote
	OnVote(cert PartialCert)
	// OnNewView handles an incoming NewView
	OnNewView(msg NewView)
	// OnDeliver handles an incoming block
	OnDeliver(block *Block)
}

Consensus implements a consensus protocol

type Credentials

type Credentials interface{}

Credentials are used to authenticate communication between replicas

type Executor

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

Executor executes a command

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 quorum certificate
	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
	Signature() Signature
	// BlockHash returns the hash of the block that was signed
	BlockHash() Hash
}

PartialCert is a 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 for which the certificate was created
	BlockHash() Hash
}

QuorumCert is a certificate for a Block created by a quorum of replicas

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 implements the methods that communicate with another replica

type Signature

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

Signature is a signature of a block

type Signer

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

Signer implements the methods requried 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 uniquely identifies a view

type ViewSynchronizer

type ViewSynchronizer interface {
	LeaderRotation
	// OnPropose should be called when a replica has received a new valid proposal.
	OnPropose()
	// OnFinishQC should be called when a replica has created a new qc
	OnFinishQC()
	// OnNewView should be called when a 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