bitcoindevkit
Add Efficient Sparse Chain Comparison to `CheckPoint`
Problem
Need to efficiently determine if two CheckPoint chains contain the same set of blocks. Currently requires O(n) traversal to compare sparse chains, even when they have the same tip.
Solution
Add a cumulative XOR field to each CheckPoint that represents the XOR of all block hashes in the sparse chain.
Why XOR Works
- Bitcoin blocks have unique hashes (no collisions)
- XOR is commutative: same blocks = same XOR regardless of order
- O(1) comparison instead of O(n) traversal
- Simple incremental computation during
insert()
Testing Requirements
- [ ] XOR correctly computed during construction
- [ ] XOR maintained during
insert()operations - [ ] Same sparse chains produce identical XOR
- [ ] Different sparse chains produce different XOR
- [ ] Edge cases: empty chain, single block, fork handling
Notes
- 32 bytes per checkpoint overhead (acceptable for O(1) comparison benefit)
Hi, could you please assign this issue to me? I'd like to work on it. Thanks!
As part of a brief discussion with Lloyd, it's valid to note that we should also consider using a salt when hashing/xor'ing in order to make sure that a third-party can build an specific hash from invalid data that would satisfy the expected one.
@oleonardolima What do you mean a "third party"? What do you mean by "invalid data"? Also, how do we know what is expected?
I mean the electrum/esplora servers as the third party, and invalid data is a chain with invalid blocks that would still be considered to have the same blocks as it has data that would output the same data for the XOR.
