Describe the enhancement
Making this issue so my subsequent PRs are not logic bombs that come out of no where. Currently, the header chain stores the header chain of most work, and nothing else. Forks with equal work are rejected instead of held in a neutral state. Assessing the changes to the chain, difficulty adjustments, etc are all hard to reason about. This is due to: 1. trying to evaluate header messages in a batch 2. indexing by height alone, without having a strict ordering on block hashes.
Instead, the data structure that represents the block headers should resemble a simple directed graph, where each header points to its parent. In practice with Rust, it can be hard to hold pointers to other objects of the same type. Luckily each block header contains a pointer to the hash of the previous block, so this fact may be used to implement a header chain using a HashMap. Sometimes it is preferable to access a header by height, which may be done by storing this relationship in a separate map within the structure. Ultimately these changes should make accesses to the data within the chain faster, and forks become less jarring for the users.
Use case
There are a number of improvements that can be made by taking a directed graph approach:
- Right now, the chain of filters, filter headers, and filter hashes are all represented separately from the chain of block data. All of these can be consolidated to a single structure that manages the metadata associated with a block header
- Forks are easily held in memory and assessed for their work. Swapping between forks is trivial.
- Data access is constant time in both height and block hash.
- Changes to the chain can be made more granular. The chain can report small changes to a database, which may implement its own caching/storage strategy. Forks may also be stored within a backend.
- The
Chain structure could be greatly simplified, and made into more-or-less a state manager.
Steps
Describe the enhancement
Making this issue so my subsequent PRs are not logic bombs that come out of no where. Currently, the header chain stores the header chain of most work, and nothing else. Forks with equal work are rejected instead of held in a neutral state. Assessing the changes to the chain, difficulty adjustments, etc are all hard to reason about. This is due to: 1. trying to evaluate header messages in a batch 2. indexing by height alone, without having a strict ordering on block hashes.
Instead, the data structure that represents the block headers should resemble a simple directed graph, where each header points to its parent. In practice with Rust, it can be hard to hold pointers to other objects of the same type. Luckily each block header contains a pointer to the hash of the previous block, so this fact may be used to implement a header chain using a
HashMap. Sometimes it is preferable to access a header by height, which may be done by storing this relationship in a separate map within the structure. Ultimately these changes should make accesses to the data within the chain faster, and forks become less jarring for the users.Use case
There are a number of improvements that can be made by taking a directed graph approach:
Chainstructure could be greatly simplified, and made into more-or-less a state manager.Steps
HeaderChainintoBlockTree#324HeaderChainintoBlockTree#324CFHeaderChainandFilterChainstructures, storing the data within theBlockTreefiltermodule and move anything else remaining intoliborchain