invalidate_branch.rs

Overview

The invalidate_branch.rs file provides functionality to traverse and invalidate a blockchain branch starting from a specified root block state. The primary function, invalidate_branch, marks the entire branch as invalidated if it meets certain conditions related to the block sequence numbers, ensuring that branches older than a given cutoff are not processed unnecessarily. This operation is critical in maintaining the integrity and correctness of the blockchain state by preventing finalized or already invalidated blocks from being reprocessed.

Function: invalidate_branch

pub fn invalidate_branch(
    branch_root_block_state: BlockState,
    block_state_repository: &BlockStateRepository,
    filter: &FilterPrehistoric,
)

Purpose

Traverses through a branch of blocks starting at branch_root_block_state and marks each block in the branch as invalidated unless the branch is newer or equal to a given filter sequence number. The function ensures that blocks which are finalized or already invalidated are not processed again to avoid redundant operations or corrupting finalized data.

Parameters

Behavior and Implementation Details

  1. Filter Check:

    The function first checks the sequence number (block_seq_no()) of the root block state. If the filter's sequence number is greater than or equal to the root block's sequence number, the function returns early without processing. This prevents invalidation of branches that are not prehistoric relative to the filter.

  2. Breadth-First Traversal:

    The function uses a VecDeque as a queue to perform a breadth-first traversal of the branch starting from the root block.

  3. Invalidation Logic:

    • For each block state dequeued:

      • It asserts that the block is not finalized, as finalized blocks should never be invalidated.

      • If the block is already invalidated, it skips further processing for that block.

      • Otherwise, it marks the block as invalidated by calling set_invalidated().

      • It collects all children of the current block from the known_children map and adds them to the queue for subsequent processing.

  4. Child Block Retrieval:

    Child blocks are retrieved from the block_state_repository using their identifiers. The function panics if a child block is not found (unwrap()), implying that the repository must be consistent and contain all referenced children.

Return Value

The function returns nothing (()); the operation modifies the internal state of BlockState instances by marking them invalidated.

Usage Example

// Assuming `root_block_state` is a BlockState instance representing the branch root,
// `block_repo` is a BlockStateRepository reference,
// and `filter` is a FilterPrehistoric instance:

invalidate_branch(root_block_state, &block_repo, &filter);

This will traverse the branch starting at root_block_state and invalidate all blocks in that branch which are older than the filter's cutoff sequence number.

Important Types and Components

Algorithmic Flow

The function implements a Breadth-First Search (BFS) over the blockchain branch starting from the root block state. It ensures that:

This approach guarantees a complete and efficient invalidation of the entire branch.

Interaction with Other System Components

Mermaid Diagram: Function Workflow

flowchart TD
A[Start: invalidate_branch] --> B{Check root block seq_no vs filter}
B -- seq_no >= filter --> C[Return early]
B -- seq_no < filter --> D[Initialize queue with root block]
D --> E[Pop next block from queue]
E --> F{Is block finalized?}
F -- Yes --> G[Assert failure]
F -- No --> H{Is block invalidated?}
H -- Yes --> I[Skip processing]
H -- No --> J[Set block invalidated]
J --> K[Collect children from known_children]
K --> L{Are there children?}
L -- Yes --> M[Enqueue all children]
L -- No --> N[Continue]
M & N --> O{Queue empty?}
O -- No --> E
O -- Yes --> P[End]

Notes