qbft

package
v0.2.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 2, 2022 License: GPL-3.0 Imports: 9 Imported by: 0

README

QBFT

Introduction

This is a spec implementation for the QBFT protocol, following formal verification spec / github repo.

Important note on message processing

The spec only deals with message process logic but it's also very important the way controller.ProcessMsg is called. Message queueing and retry are important as there is no guarantee as to when a message is delivered. Examples:

  • A proposal message can be delivered after its respective prepare
  • A next round message can be delivered before the timer hits timeout
  • A late commit message can decide the instance even if it started the next round
  • A message can fail to process because it's "too early" or "too late"

Because of the above, there is a need to order and queue messages based on their round and type so to not lose message and make the protocol round change.

TODO

  • Support 4,7,10,13 committee sizes
  • Message encoding and validation spec tests
  • proposal/ prepare/ commit spec tests
  • round change spec tests
  • [//] Unified test suite, compatible with the formal verification spec
  • [//] Align according to spec and Roberto's comments
  • Remove round check from upon commit as it can be for any round?
  • Use data hashes instead of full data in msgs to save space in justifications

Documentation

Index

Constants

View Source 
const (
	NoRound     Round  = 0 // NoRound represents a nil/ zero round
	FirstRound  Round  = 1 // FirstRound value is the first round in any QBFT instance start
	FirstHeight Height = 0
)
View Source 
const HistoricalInstanceCapacity int = 5

HistoricalInstanceCapacity represents the upper bound of InstanceContainer a controller can process messages for as messages are not guaranteed to arrive in a timely fashion, we physically limit how far back the controller will process messages for

Variables

View Source 
var SignMsg = func(sk *bls.SecretKey, id types.OperatorID, msg *Message) *SignedMessage {
	domain := types.GetDefaultDomain()
	sigType := types.QBFTSignatureType

	r, _ := types.ComputeSigningRoot(msg, types.ComputeSignatureDomain(domain, sigType))
	sig := sk.SignByte(r)

	return &SignedMessage{
		Message:   msg,
		Signers:   []types.OperatorID{id},
		Signature: sig.Serialize(),
	}
}
View Source 
var TestingMessage = &Message{
	MsgType:    ProposalMsgType,
	Height:     FirstHeight,
	Round:      FirstRound,
	Identifier: []byte{1, 2, 3, 4},
	Data:       []byte{1, 2, 3, 4},
}
View Source 
var TestingSK = func() *bls.SecretKey {
	types.InitBLS()
	ret := &bls.SecretKey{}
	ret.SetByCSPRNG()
	return ret
}()

Functions

func ControllerIdToMessageID added in v0.2.2 

func ControllerIdToMessageID(identifier []byte) types.MessageID

func HasPartialQuorum 

func HasPartialQuorum(share *types.Share, msgs []*SignedMessage) bool

HasPartialQuorum returns true if a unique set of signers has partial quorum

func HasQuorum 

func HasQuorum(share *types.Share, msgs []*SignedMessage) bool

HasQuorum returns true if a unique set of signers has quorum

func RoundRobinProposer 

func RoundRobinProposer(state *State, round Round) types.OperatorID

RoundRobinProposer returns the proposer for the round. Each new height starts with the first proposer and increments by 1 with each following round. Each new height has a different first round proposer which is +1 from the previous height. First height starts with index 0

Types

type CommitData 

type CommitData struct {
	Data []byte
}

func (*CommitData) Decode 

func (d *CommitData) Decode(data []byte) error

Decode returns error if decoding failed

func (*CommitData) Encode 

func (d *CommitData) Encode() ([]byte, error)

Encode returns a msg encoded bytes or error

func (*CommitData) Validate 

func (d *CommitData) Validate() error

Validate returns error if msg validation doesn't pass. Msg validation checks the msg, it's variables for validity.

type Config 

type Config struct {
	Signer      types.SSVSigner
	SigningPK   []byte
	Domain      types.DomainType
	ValueCheckF ProposedValueCheckF
	ProposerF   ProposerF
	Storage     Storage
	Network     Network
	Timer       Timer
}

func (*Config) GetNetwork 

func (c *Config) GetNetwork() Network

GetNetwork returns a p2p Network instance

func (*Config) GetProposerF 

func (c *Config) GetProposerF() ProposerF

GetProposerF returns func used to calculate proposer

func (*Config) GetSignatureDomainType 

func (c *Config) GetSignatureDomainType() types.DomainType

GetSignatureDomainType returns the Domain type used for signatures

func (*Config) GetSigner 

func (c *Config) GetSigner() types.SSVSigner

GetSigner returns a Signer instance

func (*Config) GetSigningPubKey 

func (c *Config) GetSigningPubKey() []byte

GetSigningPubKey returns the public key used to sign all QBFT messages

func (*Config) GetStorage added in v0.2.2 

func (c *Config) GetStorage() Storage

GetStorage returns a storage instance

func (*Config) GetTimer 

func (c *Config) GetTimer() Timer

GetTimer returns round timer

func (*Config) GetValueCheckF 

func (c *Config) GetValueCheckF() ProposedValueCheckF

GetValueCheckF returns value check instance

type Controller 

type Controller struct {
	Identifier []byte
	Height     Height // incremental Height for InstanceContainer
	// StoredInstances stores the last HistoricalInstanceCapacity in an array for message processing purposes.
	StoredInstances InstanceContainer
	Domain          types.DomainType
	Share           *types.Share
	// contains filtered or unexported fields
}

Controller is a QBFT coordinator responsible for starting and following the entire life cycle of multiple QBFT InstanceContainer

func NewController 

func NewController(
	identifier []byte,
	share *types.Share,
	domain types.DomainType,
	signer types.SSVSigner,
	valueCheck ProposedValueCheckF,
	storage Storage,
	network Network,
	proposerF ProposerF,
) *Controller

func (*Controller) Decode 

func (c *Controller) Decode(data []byte) error

Decode implementation

func (*Controller) Encode 

func (c *Controller) Encode() ([]byte, error)

Encode implementation

func (*Controller) GenerateConfig added in v0.2.2 

func (c *Controller) GenerateConfig() IConfig

func (*Controller) GetIdentifier 

func (c *Controller) GetIdentifier() []byte

GetIdentifier returns QBFT Identifier, used to identify messages

func (*Controller) InstanceForHeight 

func (c *Controller) InstanceForHeight(height Height) *Instance

func (*Controller) ProcessMsg 

func (c *Controller) ProcessMsg(msg *SignedMessage) (bool, []byte, error)

ProcessMsg processes a new msg, returns true if Decided, non nil byte slice if Decided (Decided value) and error Decided returns just once per instance as true, following messages (for example additional commit msgs) will not return Decided true

func (*Controller) StartNewInstance 

func (c *Controller) StartNewInstance(value []byte) error

StartNewInstance will start a new QBFT instance, if can't will return error

type DecidedMessage 

type DecidedMessage struct {
	SignedMessage *SignedMessage
}

func (*DecidedMessage) Decode 

func (msg *DecidedMessage) Decode(data []byte) error

Decode returns error if decoding failed

func (*DecidedMessage) Encode 

func (msg *DecidedMessage) Encode() ([]byte, error)

Encode returns a msg encoded bytes or error

type Height 

type Height int64

type IConfig 

type IConfig interface {

	// GetValueCheckF returns value check function
	GetValueCheckF() ProposedValueCheckF
	// GetProposerF returns func used to calculate proposer
	GetProposerF() ProposerF
	// GetNetwork returns a p2p Network instance
	GetNetwork() Network
	// GetStorage returns a storage instance
	GetStorage() Storage
	// GetTimer returns round timer
	GetTimer() Timer
	// contains filtered or unexported methods
}

type Instance 

type Instance struct {
	State *State

	StartValue []byte
	// contains filtered or unexported fields
}

Instance is a single QBFT instance that starts with a Start call (including a value). Every new msg the ProcessMsg function needs to be called

func NewInstance 

func NewInstance(
	config IConfig,
	share *types.Share,
	identifier []byte,
	height Height,
) *Instance

func (*Instance) Broadcast 

func (i *Instance) Broadcast(msg *SignedMessage) error

func (*Instance) Decode 

func (i *Instance) Decode(data []byte) error

Decode implementation

func (*Instance) Encode 

func (i *Instance) Encode() ([]byte, error)

Encode implementation

func (*Instance) GetConfig 

func (i *Instance) GetConfig() IConfig

GetConfig returns the instance config

func (*Instance) GetHeight 

func (i *Instance) GetHeight() Height

GetHeight interface implementation

func (*Instance) IsDecided 

func (i *Instance) IsDecided() (bool, []byte)

IsDecided interface implementation

func (*Instance) ProcessMsg 

func (i *Instance) ProcessMsg(msg *SignedMessage) (decided bool, decidedValue []byte, aggregatedCommit *SignedMessage, err error)

ProcessMsg processes a new QBFT msg, returns non nil error on msg processing error

func (*Instance) Start 

func (i *Instance) Start(value []byte, height Height)

Start is an interface implementation

func (*Instance) UponCommit 

func (i *Instance) UponCommit(signedCommit *SignedMessage, commitMsgContainer *MsgContainer) (bool, []byte, *SignedMessage, error)

UponCommit returns true if a quorum of commit messages was received.

type InstanceContainer 

type InstanceContainer [HistoricalInstanceCapacity]*Instance

func (InstanceContainer) FindInstance 

func (i InstanceContainer) FindInstance(height Height) *Instance

type Message 

type Message struct {
	MsgType    MessageType
	Height     Height // QBFT instance Height
	Round      Round  // QBFT round for which the msg is for
	Identifier []byte // instance Identifier this msg belongs to
	Data       []byte
}

func (*Message) Decode 

func (msg *Message) Decode(data []byte) error

Decode returns error if decoding failed

func (*Message) Encode 

func (msg *Message) Encode() ([]byte, error)

Encode returns a msg encoded bytes or error

func (*Message) GetCommitData 

func (msg *Message) GetCommitData() (*CommitData, error)

GetCommitData returns commit specific data

func (*Message) GetPrepareData 

func (msg *Message) GetPrepareData() (*PrepareData, error)

GetPrepareData returns prepare specific data

func (*Message) GetProposalData 

func (msg *Message) GetProposalData() (*ProposalData, error)

GetProposalData returns proposal specific data

func (*Message) GetRoot 

func (msg *Message) GetRoot() ([]byte, error)

GetRoot returns the root used for signing and verification

func (*Message) GetRoundChangeData 

func (msg *Message) GetRoundChangeData() (*RoundChangeData, error)

GetRoundChangeData returns round change specific data

func (*Message) Validate 

func (msg *Message) Validate() error

Validate returns error if msg validation doesn't pass. Msg validation checks the msg, it's variables for validity.

type MessageType 

type MessageType int
const (
	ProposalMsgType MessageType = iota
	PrepareMsgType
	CommitMsgType
	RoundChangeMsgType
)

type MsgContainer 

type MsgContainer struct {
	Msgs map[Round][]*SignedMessage
}

func NewMsgContainer 

func NewMsgContainer() *MsgContainer

func (*MsgContainer) AddIfDoesntExist 

func (c *MsgContainer) AddIfDoesntExist(msg *SignedMessage) (bool, error)

AddIfDoesntExist will add a msg only if there isn't an existing msg with the same root and signers

func (*MsgContainer) AllMessaged 

func (c *MsgContainer) AllMessaged() []*SignedMessage

AllMessaged returns all messages

func (*MsgContainer) Decode 

func (c *MsgContainer) Decode(data []byte) error

Decode returns error if decoding failed

func (*MsgContainer) Encode 

func (c *MsgContainer) Encode() ([]byte, error)

Encode returns the encoded struct in bytes or error

func (*MsgContainer) LongestUniqueSignersForRoundAndValue 

func (c *MsgContainer) LongestUniqueSignersForRoundAndValue(round Round, value []byte) ([]types.OperatorID, []*SignedMessage)

LongestUniqueSignersForRoundAndValue returns the longest set of unique signers and msgs for a specific round and value

func (*MsgContainer) MessagesForRound 

func (c *MsgContainer) MessagesForRound(round Round) []*SignedMessage

MessagesForRound returns all msgs for Height and round, empty slice otherwise

func (*MsgContainer) MessagesForRoundAndValue 

func (c *MsgContainer) MessagesForRoundAndValue(round Round, value []byte) []*SignedMessage

MessagesForRoundAndValue returns all msgs for round and value, empty slice otherwise

type Network 

type Network interface {
	Broadcast(msg types.Encoder) error
	BroadcastDecided(msg types.Encoder) error
}

Network is a collection of funcs for the QBFT Network

type PrepareData 

type PrepareData struct {
	Data []byte
}

func (*PrepareData) Decode 

func (d *PrepareData) Decode(data []byte) error

Decode returns error if decoding failed

func (*PrepareData) Encode 

func (d *PrepareData) Encode() ([]byte, error)

Encode returns a msg encoded bytes or error

func (*PrepareData) Validate 

func (d *PrepareData) Validate() error

Validate returns error if msg validation doesn't pass. Msg validation checks the msg, it's variables for validity.

type ProposalData 

type ProposalData struct {
	Data                     []byte
	RoundChangeJustification []*SignedMessage
	PrepareJustification     []*SignedMessage
}

func (*ProposalData) Decode 

func (d *ProposalData) Decode(data []byte) error

Decode returns error if decoding failed

func (*ProposalData) Encode 

func (d *ProposalData) Encode() ([]byte, error)

Encode returns a msg encoded bytes or error

func (*ProposalData) Validate 

func (d *ProposalData) Validate() error

Validate returns error if msg validation doesn't pass. Msg validation checks the msg, it's variables for validity.

type ProposedValueCheckF 

type ProposedValueCheckF func(data []byte) error

type ProposerF 

type ProposerF func(state *State, round Round) types.OperatorID

type Round 

type Round uint64

type RoundChangeData 

type RoundChangeData struct {
	PreparedValue            []byte
	PreparedRound            Round
	RoundChangeJustification []*SignedMessage
}

func (*RoundChangeData) Decode 

func (d *RoundChangeData) Decode(data []byte) error

Decode returns error if decoding failed

func (*RoundChangeData) Encode 

func (d *RoundChangeData) Encode() ([]byte, error)

Encode returns a msg encoded bytes or error

func (*RoundChangeData) Prepared 

func (d *RoundChangeData) Prepared() bool

func (*RoundChangeData) Validate 

func (d *RoundChangeData) Validate() error

Validate returns error if msg validation doesn't pass. Msg validation checks the msg, it's variables for validity.

type SignedMessage 

type SignedMessage struct {
	Signature types.Signature
	Signers   []types.OperatorID
	Message   *Message // message for which this signature is for
}

func CreateCommit 

func CreateCommit(state *State, config IConfig, value []byte) (*SignedMessage, error)

CreateCommit * Commit( 

signCommit(
    UnsignedCommit(
        |current.blockchain|,
        current.round,
        signHash(hashBlockForCommitSeal(proposedBlock), current.id),
        digest(proposedBlock)),
        current.id
    )
);

func CreatePrepare 

func CreatePrepare(state *State, config IConfig, newRound Round, value []byte) (*SignedMessage, error)

CreatePrepare * Prepare( 

    signPrepare(
        UnsignedPrepare(
            |current.blockchain|,
            newRound,
            digest(m.proposedBlock)),
        current.id
        )
);

func CreateProposal 

func CreateProposal(state *State, config IConfig, value []byte, roundChanges, prepares []*SignedMessage) (*SignedMessage, error)

CreateProposal * 

	Proposal(
                      signProposal(
                          UnsignedProposal(
                              |current.blockchain|,
                              newRound,
                              digest(block)),
                          current.id),
                      block,
                      extractSignedRoundChanges(roundChanges),
                      extractSignedPrepares(prepares));

func CreateRoundChange 

func CreateRoundChange(state *State, config IConfig, newRound Round, instanceStartValue []byte) (*SignedMessage, error)

CreateRoundChange * RoundChange( 

    signRoundChange(
        UnsignedRoundChange(
            |current.blockchain|,
            newRound,
            digestOptionalBlock(current.lastPreparedBlock),
            current.lastPreparedRound),
    current.id),
    current.lastPreparedBlock,
    getRoundChangeJustification(current)
)

func (*SignedMessage) Aggregate 

func (signedMsg *SignedMessage) Aggregate(sig types.MessageSignature) error

Aggregate will aggregate the signed message if possible (unique signers, same digest, valid)

func (*SignedMessage) CommonSigners 

func (signedMsg *SignedMessage) CommonSigners(ids []types.OperatorID) bool

CommonSigners returns true if there is at least 1 common signer

func (*SignedMessage) Decode 

func (signedMsg *SignedMessage) Decode(data []byte) error

Decode returns error if decoding failed

func (*SignedMessage) DeepCopy 

func (signedMsg *SignedMessage) DeepCopy() *SignedMessage

DeepCopy returns a new instance of SignedMessage, deep copied

func (*SignedMessage) Encode 

func (signedMsg *SignedMessage) Encode() ([]byte, error)

Encode returns a msg encoded bytes or error

func (*SignedMessage) GetRoot 

func (signedMsg *SignedMessage) GetRoot() ([]byte, error)

GetRoot returns the root used for signing and verification

func (*SignedMessage) GetSignature 

func (signedMsg *SignedMessage) GetSignature() types.Signature

func (*SignedMessage) GetSigners 

func (signedMsg *SignedMessage) GetSigners() []types.OperatorID

func (*SignedMessage) MatchedSigners 

func (signedMsg *SignedMessage) MatchedSigners(ids []types.OperatorID) bool

MatchedSigners returns true if the provided signer ids are equal to GetSignerIds() without order significance

func (*SignedMessage) Validate 

func (signedMsg *SignedMessage) Validate() error

Validate returns error if msg validation doesn't pass. Msg validation checks the msg, it's variables for validity.

type State 

type State struct {
	Share                           *types.Share
	ID                              []byte // instance Identifier
	Round                           Round
	Height                          Height
	LastPreparedRound               Round
	LastPreparedValue               []byte
	ProposalAcceptedForCurrentRound *SignedMessage
	Decided                         bool
	DecidedValue                    []byte

	ProposeContainer     *MsgContainer
	PrepareContainer     *MsgContainer
	CommitContainer      *MsgContainer
	RoundChangeContainer *MsgContainer
}

func (*State) Decode 

func (s *State) Decode(data []byte) error

Decode returns error if decoding failed

func (*State) Encode 

func (s *State) Encode() ([]byte, error)

Encode returns a msg encoded bytes or error

func (*State) GetRoot 

func (s *State) GetRoot() ([]byte, error)

GetRoot returns the state's deterministic root

type Storage 

type Storage interface {
	// SaveHighestDecided saves (and potentially overrides) the highest Decided for a specific instance
	SaveHighestDecided(signedMsg *SignedMessage) error
	// GetHighestDecided returns highest decided if found, nil if didn't
	GetHighestDecided(identifier []byte) (*SignedMessage, error)
}

type Timer 

type Timer interface {
	// TimeoutForRound will reset running timer if exists and will start a new timer for a specific round
	TimeoutForRound(round Round)
}

Source Files

View all Source files

Directories

Path Synopsis
generate command
tests
tests/commit
tests/controller
tests/messages
tests/prepare
tests/processmsg
tests/proposal
tests/proposer
tests/roundchange

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.