snowman

Documentation

Index

• type Block
• type Consensus
• type Factory
• type Topological
  • func (m *Topological) Accepted(id ids.ID)
  • func (ts *Topological) Add(blk Block)
  • func (ts *Topological) Finalized() bool
  • func (ts *Topological) Initialize(ctx *snow.Context, params snowball.Parameters, rootID ids.ID)
  • func (ts *Topological) Issued(blk Block) bool
  • func (ts *Topological) Parameters() snowball.Parameters
  • func (ts *Topological) Preference() ids.ID
  • func (ts *Topological) RecordPoll(votes ids.Bag)
  • func (m *Topological) Rejected(id ids.ID)
• type TopologicalFactory
  • func (TopologicalFactory) New() Consensus

Types

type Block

type Block interface {
	choices.Decidable

	// Parent returns the block that this block points to.
	//
	// If the parent block is not known, a Block should be returned with the
	// status Unknown.
	Parent() Block

	// Verify that the state transition this block would make if accepted is
	// valid. If the state transition is invalid, a non-nil error should be
	// returned.
	//
	// It is guaranteed that the Parent has been successfully verified.
	Verify() error

	// Bytes returns the binary representation of this block.
	//
	// This is used for sending blocks to peers. The bytes should be able to be
	// parsed into the same block on another node.
	Bytes() []byte
}

Block is a possible decision that dictates the next canonical block.

Blocks are guaranteed to be Verified, Accepted, and Rejected in topological order. Specifically, if Verify is called, then the parent has already been verified. If Accept is called, then the parent has already been accepted. If Reject is called, the parent has already been accepted or rejected.

If the status of the block is Unknown, ID is assumed to be able to be called. If the status of the block is Accepted or Rejected; Parent, Verify, Accept, and Reject will never be called.

type Consensus

type Consensus interface {
	// Takes in the context, snowball parameters, and the last accepted block.
	Initialize(*snow.Context, snowball.Parameters, ids.ID)

	// Returns the parameters that describe this snowman instance
	Parameters() snowball.Parameters

	// Adds a new decision. Assumes the dependency has already been added.
	Add(Block)

	// Issued returns true if the block has been issued into consensus
	Issued(Block) bool

	// Returns the ID of the tail of the strongly preferred sequence of
	// decisions.
	Preference() ids.ID

	// RecordPoll collects the results of a network poll. Assumes all decisions
	// have been previously added.
	RecordPoll(ids.Bag)

	// Finalized returns true if all decisions that have been added have been
	// finalized. Note, it is possible that after returning finalized, a new
	// decision may be added such that this instance is no longer finalized.
	Finalized() bool
}

Consensus represents a general snowman instance that can be used directly to process a series of dependent operations.

type Factory

type Factory interface {
	New() Consensus
}

Factory returns new instances of Consensus

type Topological

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

Topological implements the Snowman interface by using a tree tracking the strongly preferred branch. This tree structure amortizes network polls to vote on more than just the next block.

func (*Topological) Accepted

func (m *Topological) Accepted(id ids.ID)

func (*Topological) Add

func (ts *Topological) Add(blk Block)

Add implements the Snowman interface

func (*Topological) Finalized

func (ts *Topological) Finalized() bool

Finalized implements the Snowman interface

func (*Topological) Initialize

func (ts *Topological) Initialize(ctx *snow.Context, params snowball.Parameters, rootID ids.ID)

Initialize implements the Snowman interface

func (*Topological) Issued

func (ts *Topological) Issued(blk Block) bool

Issued implements the Snowman interface

func (*Topological) Parameters

func (ts *Topological) Parameters() snowball.Parameters

Parameters implements the Snowman interface

func (*Topological) Preference

func (ts *Topological) Preference() ids.ID

Preference implements the Snowman interface

func (*Topological) RecordPoll

func (ts *Topological) RecordPoll(votes ids.Bag)

RecordPoll implements the Snowman interface

The votes bag contains at most K votes for blocks in the tree. If there is a vote for a block that isn't in the tree, the vote is dropped.

Votes are propagated transitively towards the genesis. All blocks in the tree that result in at least Alpha votes will record the poll on their children. Every other block will have an unsuccessful poll registered.

After collecting which blocks should be voted on, the polls are registered and blocks are accepted/rejected as needed. The tail is then updated to equal the leaf on the preferred branch.

To optimize the theoretical complexity of the vote propagation, a topological sort is done over the blocks that are reachable from the provided votes. During the sort, votes are pushed towards the genesis. To prevent interating over all blocks that had unsuccessful polls, we set a flag on the block to know that any future traversal through that block should register an unsuccessful poll on that block and every decendant block.

The complexity of this function is: - Runtime = 3 * |live set| + |votes| - Space = 2 * |live set| + |votes|

func (*Topological) Rejected

func (m *Topological) Rejected(id ids.ID)

type TopologicalFactory

type TopologicalFactory struct{}

TopologicalFactory implements Factory by returning a topological struct

func (TopologicalFactory) New

func (TopologicalFactory) New() Consensus

New implements Factory