`CheckPoint` design issue

[ValuedMammal]

These are some of the proposed changes to CheckPoint. I'm opening this as a record of ongoing discussion as it relates to the CheckPoint structure and functionality.

• Add MTP calculation Add median-time-past (MTP) calculation to CheckPoint #2036
• Validate CheckPoint links via previous hash Ensure CheckPoint chain methods validate and link via previous blockhash #2021
• Add efficient comparison Add cumulative XOR field to CheckPoint for early-termination merge #2033
• Improve search complexity Add skiplist to CheckPoint for O(√n) traversal #2048

[ValuedMammal]

In order to evaluate something proposing a significant change to the structure or design of the CheckPoint, it's important to clarify the specific requirements of the CheckPoint. What does this data structure need to accomplish, and what is the best way to do it while keeping the tradeoffs in mind?

• If there are enhancements or optimizations to be made, can they be done within the current design contraints?
• If it's a design change being proposed, what is the new design? Does it uphold the same requirements?
• Is there a chance to simplify by benefiting from types that exist either in the std library or elsewhere?
• Is there a sufficiently motivated change that warrants the time and investment on a complete rewrite?

[oleonardolima]

Awesome, thanks for compiling all the issues here! Agree, I think it's a good idea to have the big picture and the tradeoffs clear in mind. I'd add that we should probably compile all these changes in a "Checkpoint's ADR" at some point.

I'll try to come up with the answers from my perspective once I settle back home later.

[evanlinjin]

#2024 is a PR attempting to solve #2021. @ValuedMammal I'll address your questions here, in the context of #2021.

---

What does CheckPoint need to accomplish?

At its core, CheckPoint represents a sparse, singly-linked chain of block references used to:

• Track which blocks we know about (for wallet sync and canonicalization)
• Detect reorgs by finding points of agreement between local and remote chains
• Anchor transactions to specific blocks

And in the future:

• Calculate MTP time so we can create/spend time-locked outputs properly.

I thought of the following design constraints for CheckPoint:

• Represent a sparse sample of the blockchain (not every block)
• Support iteration from tip towards genesis
• Detect points of agreement between two chains
• Insert checkpoints at arbitrary heights
• Merge chains (for applying sync updates)
• Multiple components can hold references to the same chain
• Chains can share common tails (diverge at some height, share everything below)
• Cloning a reference should be cheap

Since #1582 made CheckPoint generic to hold Headers (not just BlockHash), a new implicit requirement emerged: where prev_blockhash data exists, adjacent checkpoints should be consistent. I.e., if we have checkpoints at heights N and N-1, then checkpoint N's prev_blockhash should equal checkpoint N-1's blockhash.

Can this be done within current design constraints?

The current design assumes every checkpoint has data, but enforcing prev_blockhash consistency sometimes requires representing "I know a block exists at height N-1 because N's prev_blockhash tells me so, but I don't have its full data yet." This is why the optional data field was introduced—placeholder checkpoints represent inferred-but-not-yet-populated positions in the chain.

The alternative would be to still have data in every checkpoint, but the iterator can report "ghost checkpoints" (where the prev_blockhash of the height above exists, but no data exists at the current height).

Does the new design uphold the same requirements?

Yes. The core operations (iteration, finding points of agreement, inserting blocks) all still work. The change is additive: we now also guarantee that where adjacent prev_blockhash data exists, it's consistent.

Is this sufficiently motivated?

The alternative is allowing CheckPoint to represent states that are impossible in Bitcoin (two adjacent blocks where the link doesn't match). This means:

• Bugs in chain-source implementations go undetected until they cause downstream issues.
• Merge logic errors silently produce corrupt state.
• Debugging becomes harder because the corruption point is far from where symptoms appear.

The complexity in insert() is real, but it's concentrated in one place. The benefit is that every consumer of CheckPoint will catch problems earlier, remove blocks that are meant to be removed, and even anchor transactions where only a prev_blockhash matches.

Re: std library types

Not relevant here.

[evanlinjin]

Addressing #2036 and associated PR #2037 :

What does CheckPoint need to accomplish (for MTP)?

MTP is needed for BIP 113 compliance. The wallet needs to know whether a timelocked transaction can be included in the next block, which requires calculating the median of the previous 11 block timestamps.

Can this be done within current design constraints?

Yes, and it is. The PR does not make any structural changes and only adds:

• A block_time() method to the ToBlockHash trait.
• median_time_past() and next_median_time_past() methods on CheckPoint.

Does it uphold the same requirements?

Yes. This is purely additive and does not change existing behaviour.

Is there a chance to simplify using std library types?

No. The median calculation itself is straightforward and domain-specific.

Is this sufficiently motivated?

Yes. Without MTP, wallets cannot correctly calculate when a timelocked output can be spent.

[evanlinjin]

Addressing #2048:

What does CheckPoint need to accomplish?

CheckPoints need a somewhat-efficient traversal for operations like get(), floor_at(), and range(). Currently these are O(n) - a 10,000 checkpoint chain requires traversing up to 10,000 nodes to find a block near genesis. This becomes a bottleneck for wallets with long checkpoint histories, especially during canonicalization where many lookups occur.

Can this be done within current design constraints?

Yes, and it is - with minor additions. The PR adds two fields to CheckPoint:

• skip: Option<Arc<Self>> - a pointer that jumps ahead ~100 nodes.
• index: u32 - tracks position in the chain for skip pointer calculation.

The fundamental structure (singly-linked list with Arc sharing) is preserved. The skip pointers are maintained during push() and rebuilt during insert(). All existing APIs remain unchanged—the optimization is internal.

Is there a chance to simplify using std library types?

No.

Skip lists are a well-known data structure, but std doesn't provide one.

The domain-specific simplifications here (append-mostly, immutable nodes, single-level) make a custom implementation cleaner than adapting a generic skip list crate.

Is this sufficiently motivated?

Yes. Benchmarks show:

• get() on a 10k chain: 261x faster (140μs → 540ns).
• Worst case (full 870k checkpoint chain, 10k tx wallet): canonicalization drops from ~18 seconds to ~83ms.

[ValuedMammal]

The alternative would be to still have data in every checkpoint, but the iterator can report "ghost checkpoints"

+1

[ValuedMammal]

CheckPoints need a somewhat-efficient traversal for operations like get(), and range(). Currently these are O(n) - a 10,000 checkpoint chain requires traversing up to 10,000 nodes to find a block near genesis. This becomes a bottleneck for wallets with long checkpoint histories, especially during canonicalization where many lookups occur.

To have efficient lookups you could maintain a separate index inside the local chain with block height as the key, like BTreeMap<u32, CheckPoint> or similar. The chain syncing code generally only needs to iterate the chain in a linear fashion anyway (to find the PoA).

[evanlinjin]

The chain syncing code generally only needs to iterate the chain in a linear fashion anyway (to find the PoA).

The chain source sometimes needs to ask the local chain "does this block exist?" and if it doesn't exist, it needs to fetch it.

This happens often for spk-based syncing where the chain source provides a txid and a height, and you need to make sure that height exists in your chain.

For block-by-block, if the caller needs to resync against a newly-introduced (but used-before) spk, we will need to check whether certain heights exist in the chain (and if not, we need to insert them).

[hash-ty]

Bitcoin Core achieves skiplist-like performance using CBlockIndex::pskip which is a pointer to a further back ancestor. Basically, every CBLockIndex has a pskip whose skip height is determined by GetSkipHeight. When a new block is added the pskip is set using BuildSkip. Then when looking up an ancestor block in GetAncestor there is dedicated logic for deciding when it would be advantageous to follow the pskip to jump further back instead of the normal pprev. That is not to say BDK has to do everything the Bitcoin Core way, but it might serve as a reference.

[ValuedMammal]

MTP discussion (revisited)

The general problem is that timelocked funds should be excluded from coin selection by default. To evaluate whether a timelock condition is met we need two bits of information: 1) the median time of the current chain tip (tip_mtp), and 2) for relative timelocks the median time 1-block prior to the confirmation block (prev_mtp).

Right now the local chain has no notion of clock time. We can find the age of a UTXO in blocks, but that doesn't help if the coin is locked to an absolute timestamp or a relative duration in 512-second intervals.

Proposal

1. Store prev_mtp in the confirmation block-time anchor (the chain source computes it from the 11-block window preceding the confirmation block). Absent such a feature, we can fallback to using the header time of the confirmation block as an approximation.

2. Store tip_mtp in the LocalChain, set by the chain source and persisted in the ChangeSet. Whenever the chain tip changes, the tip_mtp is recalculated ¹. Since that is a breaking change, a simple solution in the short run is to make the chain source guarantee that the update consists of 11 blocks up to and including the new tip, thereby allowing the local chain to compute it.

3. Evaluating timelocks. A wallet implementation should try to evaluate timelocks when considering utxos for coin selection. If we have the necessary time data and the timelock is expired, then the coin can be selected, and excluded otherwise.

If the utxo is locked to an absolute or relative time and we can't compute the tip time and/or coin age due to missing data, the coin should be excluded from selection. If a user wants to create a transaction that won't be valid until some time in the future, they can manually supply the timestamp which they intend to satisfy.

Footnotes

1. rationale: Perhaps counterintuitively, the local chain doesn't need to compute the MTP at any arbitrary height, it only needs to keep track of the current tip time. Making the local chain responsible for the MTP calculation is unreliable, as it's fundamentally designed to be sparse. It remains the responsibility of the chain source to report the current tip time, BDK just needs a way to receive it. ↩

[evanlinjin]

@ValuedMammal How does this relate to #2037 which is already merged? What problem does it solve that the existing CheckPoint::median_time_past() doesn't?

Fundamentally, it's better to derive from raw data and don't store derived data (which is the #2037 approach).