reduction

README

Reduction components

This package defines the components for both the first and second step of reduction individually, as specified in the Binary Reduction Phase of the SBA* consensus protocol.

Due to small, but intricate differences between the two steps, the components are defined individually, with a minimal amount of shared code. This was done in an effort to increase readability, since it avoids massive amounts of abstraction which, on earlier iterations of the package, caused some confusion for readers. That said, code which is identical across the two components is defined in the top-level of the package, and imported down.

Values

Block Reduction Event

Field	Type
signedblockhash	BLS Signature

Architecture

At the core, a Reducer works like this:

• It gets triggered by a call to the Run function. This instantiates an Aggregator, starts a timer, and gossips a Reduction message (using the provided keys on startup)
• The queue is flushed, and it starts collecting Reduction messages, passing them down to the Aggregator
• When the Aggregator reaches quorum, or when the timer is triggered, the Reducer will return a message
• The component is then finished and waits for the next call to Run

Differences between the two components

Since there are subtle differences in the actions that need to be taken per step, the reducers have been split up in a first step and second step. Between the two, these differences can be found:

• Upon reaching quorum, the first step reducer will attempt to retrieve the candidate block corresponding to the winning hash (either through the DB or the network), and attempt to verify it, to make sure it's okay to continue voting on this block for the second step
• When reaching quorum, the first step reducer will return a StepVotes message, which is passed on to the second step reducer. The second step reducer will instead gossip an Agreement message, using the combined StepVotes of the first and second step to create a certificate. The second step reducer does not return anything

Aggregator

Each Reducer makes use of an Aggregator, which is a component akin to a storage for incoming messages. The Aggregator will receive any incoming Reduction messages after they are filtered by the Reducer. It will separate messages by their block hash, and proceed to aggregate the included signedblockhash with other collected signatures for this hash (if any). Additionally, it saves the senders BLS public key in a sortedset.Set. Once the amount of keys and signatures for a certain blockhash exceeds a threshold, the Aggregator will return the collected information.

Documentation

Index

• Constants
• Variables
• func PrepareSendReductionTest(hlp *Helper, stepFn consensus.PhaseFn) func(t *testing.T)
• func ShouldProcess(m message.Message, round uint64, step uint8, queue *consensus.Queue) bool
• type Aggregator
  • func NewAggregator(handler *Handler) *Aggregator
  • func (a *Aggregator) CollectVote(ev message.Reduction) *Result
  • func (a *Aggregator) Log(l *logrus.Entry, round uint64, step uint8)
• type AsyncSend
  • func NewAsyncSend(r *Reduction, round uint64, step uint8, candidate *block.Block) *AsyncSend
  • func (a AsyncSend) Go(ctx context.Context, resp chan message.Message, flags int) context.CancelFunc
• type Handler
  • func NewHandler(keys key.Keys, p user.Provisioners, seed []byte) *Handler
  • func (b *Handler) AmMember(round uint64, step uint8) bool
  • func (b *Handler) Committee(round uint64, step uint8) user.VotingCommittee
  • func (b *Handler) IsMember(pubKeyBLS []byte, round uint64, step uint8) bool
  • func (b *Handler) Quorum(round uint64) int
  • func (b *Handler) VerifySignature(red message.Reduction) error
  • func (b *Handler) VotesFor(pubKeyBLS []byte, round uint64, step uint8) int
• type Helper
  • func NewHelper(provisioners int, timeOut time.Duration) *Helper
  • func (hlp *Helper) FailOnVerification(flag bool)
  • func (hlp *Helper) ProcessCandidateVerificationRequest(ctx context.Context, blk block.Block) error
  • func (hlp *Helper) Spawn(hash []byte, round uint64, step uint8) []message.Reduction
  • func (hlp *Helper) Verify(hash []byte, sv message.StepVotes, round uint64, step uint8) error
• type Reduction
  • func (r *Reduction) IncreaseTimeout(round uint64)
  • func (r *Reduction) SendReduction(ctx context.Context, round uint64, step uint8, candidate *block.Block) (message.Message, []byte, error)
• type Result
  • func (r *Result) IsEmpty() bool

Constants

const (
	// Republish flag instructs AsyncSend to republish the output message.
	Republish = iota
	// ValidateOnly flag instrucst AsyncSend to validate only.
	ValidateOnly
)

Variables

var EmptyStepVotes = message.StepVotes{}

EmptyStepVotes ...

var (
	// ErrLowBlockHeight block height is lower or equal than blockchain tip height.
	ErrLowBlockHeight = errors.New("block height is low")
)

Functions

func PrepareSendReductionTest

func PrepareSendReductionTest(hlp *Helper, stepFn consensus.PhaseFn) func(t *testing.T)

PrepareSendReductionTest tests that the reduction step completes without problems and produces a StepVotesMsg in case it receives enough valid Reduction messages.

func ShouldProcess

func ShouldProcess(m message.Message, round uint64, step uint8, queue *consensus.Queue) bool

ShouldProcess checks whether a message is consistent with the current round and step. If it is not, it either discards it or stores it for later. The function potentially mutates the consensus.Queue.

Types

type Aggregator

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

The Aggregator acts as a de facto storage unit for Reduction messages. Any message it receives will be Aggregated into a StepVotes struct, organized by block hash. Once the key set for a StepVotes of a certain block hash reaches quorum, this StepVotes is passed on to the Reducer by use of the `haltChan` channel. An Aggregator should be instantiated on a per-step basis and is no longer usable after reaching quorum and sending on `haltChan`.

func NewAggregator

func NewAggregator(handler *Handler) *Aggregator

NewAggregator returns an instantiated Aggregator, ready for use by both reduction steps.

func (*Aggregator) CollectVote

func (a *Aggregator) CollectVote(ev message.Reduction) *Result

CollectVote collects a Reduction message, and add its sender public key and signature to the StepVotes/Set kept under the corresponding block hash. If the Set reaches or exceeds quorum, a result is created with the voted hash and the related StepVotes added. The validation of the candidate block is left to the caller.

func (*Aggregator) Log

func (a *Aggregator) Log(l *logrus.Entry, round uint64, step uint8)

Log dumps current state of voteSets in passed logrus.

type AsyncSend

type AsyncSend struct {
	*Reduction
	// contains filtered or unexported fields
}

AsyncSend is wrapper of SendReduction to call it in an asynchronous manner.

func NewAsyncSend

func NewAsyncSend(r *Reduction, round uint64, step uint8, candidate *block.Block) *AsyncSend

NewAsyncSend ...

func (AsyncSend) Go

func (a AsyncSend) Go(ctx context.Context, resp chan message.Message, flags int) context.CancelFunc

Go executes SendReduction in a separate goroutine. Returns cancel func for canceling the started job.

type Handler

type Handler struct {
	*committee.Handler
}

Handler is responsible for performing operations that need to know about specific event fields.

func NewHandler

func NewHandler(keys key.Keys, p user.Provisioners, seed []byte) *Handler

NewHandler will return a Handler, injected with the passed committee and an unmarshaller which uses the injected validation function.

func (*Handler) AmMember

func (b *Handler) AmMember(round uint64, step uint8) bool

AmMember checks if we are part of the committee.

func (*Handler) Committee

func (b *Handler) Committee(round uint64, step uint8) user.VotingCommittee

Committee returns a VotingCommittee for a given round and step.

func (*Handler) IsMember

func (b *Handler) IsMember(pubKeyBLS []byte, round uint64, step uint8) bool

IsMember delegates the committee.Handler to check if a BLS public key belongs to a committee for the specified round and step.

func (*Handler) Quorum

func (b *Handler) Quorum(round uint64) int

Quorum returns the amount of committee votes to reach a quorum.

func (*Handler) VerifySignature

func (b *Handler) VerifySignature(red message.Reduction) error

VerifySignature verifies the BLS signature of the Reduction event. Since the payload is nil, verifying the signature equates to verifying solely the Header.

func (*Handler) VotesFor

func (b *Handler) VotesFor(pubKeyBLS []byte, round uint64, step uint8) int

VotesFor delegates the committee.Handler to accumulate Votes for the specified BLS public key identifying a Provisioner.

type Helper

type Helper struct {
	*consensus.Emitter

	ThisSender       []byte
	ProvisionersKeys []key.Keys
	P                *user.Provisioners
	Nr               int
	Handler          *Handler
	// contains filtered or unexported fields
}

Helper for reducing test boilerplate.

func NewHelper

func NewHelper(provisioners int, timeOut time.Duration) *Helper

NewHelper creates a Helper.

func (*Helper) FailOnVerification

func (hlp *Helper) FailOnVerification(flag bool)

FailOnVerification tells the RPC bus to return an error.

func (*Helper) ProcessCandidateVerificationRequest

func (hlp *Helper) ProcessCandidateVerificationRequest(ctx context.Context, blk block.Block) error

ProcessCandidateVerificationRequest is a callback used by the firststep reduction to verify potential winning candidates.

func (*Helper) Spawn

func (hlp *Helper) Spawn(hash []byte, round uint64, step uint8) []message.Reduction

Spawn a number of different valid events to the Agreement component bypassing the EventBus.

func (*Helper) Verify

func (hlp *Helper) Verify(hash []byte, sv message.StepVotes, round uint64, step uint8) error

Verify StepVotes. The step must be specified otherwise verification would be dependent on the state of the Helper.

type Reduction

type Reduction struct {
	*consensus.Emitter
	TimeOut time.Duration

	// VerifyFn verifies candidate block
	VerifyFn consensus.CandidateVerificationFunc
}

Reduction is a struct to be embedded in the reduction steps.

func (*Reduction) IncreaseTimeout

func (r *Reduction) IncreaseTimeout(round uint64)

IncreaseTimeout is used when reduction does not reach the quorum or converges over an empty block.

func (*Reduction) SendReduction

func (r *Reduction) SendReduction(ctx context.Context, round uint64, step uint8, candidate *block.Block) (message.Message, []byte, error)

SendReduction propagates a signed vote for the candidate block, if block is fully valid. A full block validation will be performed if Candidate Hash differs from r.VerifiedHash. Error is returned only if the reduction should be not be registered locally.

type Result

type Result struct {
	Hash []byte
	SV   message.StepVotes
}

Result of the Reduction steps.

var EmptyResult *Result

EmptyResult ...

func (*Result) IsEmpty

func (r *Result) IsEmpty() bool

IsEmpty tests if the result of the aggregation is empty.