README
¶
Binary Reduction
Abstract
The Binary Reduction algorithm lays at the core of SBA*. It converts the problem of reaching consensus on arbitrary values to reaching consensus on one of two values. It is an adaptation of the Turpin and Coan algorithm, originally concocted to solve the general Byzantine agreement when given a binary Byzantine agreement algorithm as a subroutine, for n > 3f (with n defined as total number of nodes and f defined as adversarial nodes).
Unlike other implementations, which normally utilize the original algorithm, Binary Reduction adopted in SBA* follows a two-step approach, with the input of the second step depending on the output of the first one.
If no consensus have been reached on a uniform value, the algorithm returns a default value and waits for the next instantiation.
Binary Reduction acts as a uniform value extraction function which is then fed through the Block Agreement algorithm before exiting the loop in case of a successful termination of the Block Agreement algorithm.
Values
Block Reduction Event
| Field | Type |
|---|---|
| signedblockhash | BLS Signature |
Architecture
The reduction phase is split up into two components - one for each step. This is because, despite their similarity in logic, subtle nuances between the two steps make it more feasible to split the logic between two different components, for readability purposes. At the core, a Reducer works like this:
- It gets triggered by a message of a certain topic (first step:
BestScore/ second step:StepVotes). This instantiates anAggregatorand starts a timer. - It starts collecting Reduction messages, passing them down to the
Accumulator - When the
Aggregatorreaches quorum, or when the timer is triggered, theReducerwill send out one or more messages (first step:StepVotes/ second step:Restart&Agreement) - It stops collecting events, and waits for the next
BestScoreorStepVotes
Aggregator
Each Reducer makes use of an Aggregator, which is a component akin to a storage for incoming messages. It is instantiated with a callback, which it will call after a certain amount of messages are collected. The Aggregator will receive any incoming Reduction messages after they are filtered by the Coordinator and 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 forward the collected information, by providing it as an argument for its given callback. After triggering this callback, the Aggregator will no longer accept new messages, and a new instance needs to be created for subsequent steps.
Documentation
¶
Index ¶
- func Marshal(r *bytes.Buffer, bev Reduction) error
- func MarshalVoteSet(r *bytes.Buffer, evs []Reduction) error
- func MockConsensusEvent(hash []byte, round uint64, step uint8, keys []key.ConsensusKeys, ...) consensus.Event
- func MockVoteSetBuffer(hash []byte, round uint64, step uint8, amount int, keys []key.ConsensusKeys) *bytes.Buffer
- func MockWire(hash []byte, round uint64, step uint8, keys []key.ConsensusKeys, ...) *bytes.Buffer
- func Unmarshal(r *bytes.Buffer, bev *Reduction) error
- type FactoryFunc
- type 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(hdr header.Header, sig []byte) error
- func (b *Handler) VotesFor(pubKeyBLS []byte, round uint64, step uint8) int
- type Helper
- type Reducer
- type Reduction
- func MockEvent(hash []byte, round uint64, step uint8, keys []key.ConsensusKeys, ...) (Reduction, header.Header)
- func MockVoteSet(hash []byte, round uint64, step uint8, keys []key.ConsensusKeys, amount int) []Reduction
- func MockVotes(hash []byte, round uint64, step uint8, keys []key.ConsensusKeys, amount int) []Reduction
- func New() *Reduction
- func UnmarshalVoteSet(r *bytes.Buffer) ([]Reduction, error)
- type Timer
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func MarshalVoteSet ¶ added in v0.2.0
MarshalVoteSet marshals a slice of Reduction events to a buffer.
func MockConsensusEvent ¶ added in v0.2.0
func MockConsensusEvent(hash []byte, round uint64, step uint8, keys []key.ConsensusKeys, iterativeIdx ...int) consensus.Event
MockConsensusEvent mocks a Reduction event already digested by the Coordinator
func MockVoteSetBuffer ¶
func MockVoteSetBuffer(hash []byte, round uint64, step uint8, amount int, keys []key.ConsensusKeys) *bytes.Buffer
MockVoteSetBuffer mocks a slice of Reduction events for two adjacent steps, marshals them as a vote set, and returns the buffer.
Types ¶
type FactoryFunc ¶ added in v0.2.0
FactoryFunc is a shorthand for the reduction factories to create a Reducer
type Handler ¶ added in v0.2.0
Handler is responsible for performing operations that need to know about specific event fields.
func NewHandler ¶ added in v0.2.0
func NewHandler(keys key.ConsensusKeys, p user.Provisioners) *Handler
newHandler will return a Handler, injected with the passed committee and an unmarshaller which uses the injected validation function.
func (*Handler) Committee ¶ added in v0.2.0
func (b *Handler) Committee(round uint64, step uint8) user.VotingCommittee
Committee returns a VotingCommittee for a given round and step.
func (*Handler) VerifySignature ¶ added in v0.2.0
Verify the BLS signature of the Reduction event. Since the payload is nil, verifying the signature equates to verifying solely the Header
type Helper ¶ added in v0.2.0
type Helper struct {
Reducer Reducer
Bus *eventbus.EventBus
RBus *rpcbus.RPCBus
Keys []key.ConsensusKeys
P *user.Provisioners
PubKeyBLS []byte
Handler *Handler
*consensus.SimplePlayer
CollectionWaitGroup sync.WaitGroup
// contains filtered or unexported fields
}
Helper for reducing test boilerplate
func NewHelper ¶ added in v0.2.0
func NewHelper(eb *eventbus.EventBus, rpcbus *rpcbus.RPCBus, provisioners int, factory FactoryFunc, timeOut time.Duration) *Helper
NewHelper creates a Helper
func (*Helper) Initialize ¶ added in v0.2.0
func (hlp *Helper) Initialize(ru consensus.RoundUpdate)
Initialize the reducer with a Round update
func (*Helper) SendBatch ¶ added in v0.2.0
SendBatch of consensus events to the reducer callback CollectReductionEvent
type Reducer ¶ added in v0.2.0
type Reducer interface {
consensus.Component
// Collect collects reduction consensus events in order to generate StepVotes or an Agreement
Collect(consensus.Event) error
}
Reducer abstracts the first and second step Reduction components
type Reduction ¶
type Reduction struct {
SignedHash []byte
}
Reduction represents a provisioner vote during the Block Reduction phase of the consensus.
func MockEvent ¶ added in v0.2.0
func MockEvent(hash []byte, round uint64, step uint8, keys []key.ConsensusKeys, iterativeIdx ...int) (Reduction, header.Header)
MockEvent mocks a Reduction event and returns it. It includes a vararg iterativeIdx to help avoiding duplicates when testing
func MockVoteSet ¶
func MockVoteSet(hash []byte, round uint64, step uint8, keys []key.ConsensusKeys, amount int) []Reduction
MockVoteSet mocks a slice of Reduction events for two adjacent steps, and returns it.
Source Files
Directories