Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PendingBlockVertex ¶
type PendingBlockVertex struct {
flow.CertifiedBlock
// contains filtered or unexported fields
}
PendingBlockVertex wraps a block proposal to implement forest.Vertex so the proposal can be stored in forest.LevelledForest
func NewVertex ¶
func NewVertex(certifiedBlock flow.CertifiedBlock, connectedToFinalized bool) (*PendingBlockVertex, error)
NewVertex creates new vertex while performing a sanity check of data correctness.
func (*PendingBlockVertex) Level ¶
func (v *PendingBlockVertex) Level() uint64
func (*PendingBlockVertex) Parent ¶
func (v *PendingBlockVertex) Parent() (flow.Identifier, uint64)
func (*PendingBlockVertex) VertexID ¶
func (v *PendingBlockVertex) VertexID() flow.Identifier
type PendingTree ¶
type PendingTree struct {
// contains filtered or unexported fields
}
PendingTree is a mempool holding certified blocks that eventually might be connected to the finalized state. As soon as a valid fork of certified blocks descending from the latest finalized block is observed, we pass this information to caller. Internally, the mempool utilizes the LevelledForest. PendingTree is NOT safe to use in concurrent environment. Note:
- The ability to skip ahead is irrelevant for staked nodes, which continuously follow the chain. However, light clients don't necessarily follow the chain block by block. Assume a light client that knows the EpochCommit event, i.e. the consensus committee authorized to certify blocks. A staked node can easily ship a proof of finalization for a block within that epoch to such a light client. This would be much cheaper for the light client than downloading the headers for all blocks in the epoch.
- The pending tree supports skipping ahead, as this is a more general and simpler algorithm. Removing the ability to skip ahead would restrict the PendingTree's domain of potential applications _and_ would require additional code and additional tests making it more complex.
Outlook:
- At the moment, PendingTree relies on notion of a `Certified Block` which is a valid block accompanied by a certifying QC (proving block validity). This works well for consensus follower, as it is designed to work with certified blocks.
- In the future, we could use the PendingTree also for consensus participants. Therefore, we would need to abstract out CertifiedBlock or replace it with a generic argument that satisfies some contract (returns View, Height, BlockID). Then, consensus participants could use the Pending Tree without QCs and instead fully validate inbound blocks (incl. payloads) to guarantee block validity.
func NewPendingTree ¶
func NewPendingTree(finalized *flow.Header) *PendingTree
NewPendingTree creates new instance of PendingTree. Accepts finalized block to set up initial state.
func (*PendingTree) AddBlocks ¶
func (t *PendingTree) AddBlocks(certifiedBlocks []flow.CertifiedBlock) ([]flow.CertifiedBlock, error)
AddBlocks accepts a batch of certified blocks, adds them to the tree of pending blocks and finds blocks connected to the finalized state.
Details: Adding blocks might result in additional blocks now being connected to the latest finalized block. The returned slice contains:
- the subset of `certifiedBlocks` that are connected to the finalized block - excluding any blocks whose view is smaller or equal to the finalized block - if a block `B ∈ certifiedBlocks` is already known to the PendingTree and connected, `B` and all its connected descendants will be in the returned list
- additionally, all of the _connected_ descendants of the blocks from step 1.
PendingTree treats its input as a potentially repetitive stream of information: repeated inputs are already consistent with the current state. While repetitive inputs might cause repetitive outputs, the implementation has some general heuristics to avoid extra work:
- It drops blocks whose view is smaller or equal to the finalized block
- It deduplicates incoming blocks. We don't store additional vertices in tree if we have that block already stored.
Expected errors during normal operations:
- model.ByzantineThresholdExceededError - detected two certified blocks at the same view
All other errors should be treated as exceptions.
func (*PendingTree) FinalizeFork ¶
func (t *PendingTree) FinalizeFork(finalized *flow.Header) ([]flow.CertifiedBlock, error)
FinalizeFork takes last finalized block and prunes all blocks below the finalized view. PendingTree treats its input as a potentially repetitive stream of information: repeated and older inputs (out of order) are already consistent with the current state. Repetitive inputs might cause repetitive outputs. When a block is finalized we don't care for any blocks below it, since they were already finalized. Finalizing a block might causes the pending PendingTree to detect _additional_ blocks as now being connected to the latest finalized block. This happens if some connecting blocks are missing and then a block higher than the missing blocks is finalized. In the following example, B is the last finalized block known to the PendingTree
A ← B ←-?-?-?-- X ← Y ← Z
The network has already progressed to finalizing block X. However, the interim blocks denoted by '←-?-?-?--' have not been received by our PendingTree. Therefore, we still consider X,Y,Z as disconnected. If the PendingTree tree is now informed that X is finalized, it can fast- forward to the respective state, as it anyway would prune all the blocks below X. Note:
- The ability to skip ahead is irrelevant for staked nodes, which continuously follows the chain. However, light clients don't necessarily follow the chain block by block. Assume a light client that knows the EpochCommit event, i.e. the consensus committee authorized to certify blocks. A staked node can easily ship a proof of finalization for a block within that epoch to such a light client. This would be much cheaper for the light client than downloading the headers for all blocks in the epoch.
- The pending tree supports skipping ahead, as this is a more general and simpler algorithm. Removing the ability to skip ahead would restrict the PendingTree's its domain of potential applications _and_ would require additional code and additional tests making it more complex.
If the PendingTree detects additional blocks as descending from the latest finalized block, it returns these blocks. Returned blocks are ordered such that parents appear before their children.
No errors are expected during normal operation.
Source Files