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 ¶
- 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(red message.Reduction) error
- func (b *Handler) VotesFor(pubKeyBLS []byte, round uint64, step uint8) int
- type Helper
- type Reducer
- type Timer
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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.Keys, 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) IsMember ¶ added in v0.2.0
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 ¶ added in v0.2.0
Quorum returns the amount of committee votes to reach a quorum
func (*Handler) VerifySignature ¶ added in v0.2.0
VerifySignature verifies 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 {
PubKeyBLS []byte
Reducer Reducer
Bus *eventbus.EventBus
RBus *rpcbus.RPCBus
Keys []key.Keys
P *user.Provisioners
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.InternalPacket) error
}
Reducer abstracts the first and second step Reduction components
Source Files
Directories