chain: make use of pskip in LastCommonAncestor (optimization)
What the developer wrote
Authored by Pieter Wuille
chain: make use of pskip in LastCommonAncestor (optimization)
By using the pskip pointer, which regularly allows jumping back much faster
than pprev, the forking point between two CBlockIndex entries can be found
much faster.
A simulation shows that no more than 136 steps are needed to jump anywhere
within the first 2^20 block heights, and on average 65 jumps for uniform
forking points around that height.
What changed, and why it matters
This commit is a straightforward performance optimization for a Bitcoin Core function that finds the last common ancestor between two blocks. It replaces a slow block-by-block walk with a faster skip-pointer jump. There is no security issue visible in the diff or commit message.
No security action required. Treat as a normal performance improvement; standard code review and testing are sufficient.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The change updates LastCommonAncestor() in src/chain.cpp to use CBlockIndex::pskip (the skip-list pointer) to jump back more quickly to the common height/fork point, then falls back to pprev once the skip ancestors match. It adds Assume() checks for equal heights and removes the previous assert(pa == pb). The commit is explicitly described as an optimization, with simulation stats provided.
Changed components
src/chain.cppLastCommonAncestorInspect captured patch +14 / −5
diff --git a/src/chain.cpp b/src/chain.cpp
index 4e2d1bf0..3dd22634 100644
--- a/src/chain.cpp
+++ b/src/chain.cpp
@@ -5,6 +5,7 @@
#include <chain.h>
#include <tinyformat.h>
+#include <util/check.h>
#include <util/time.h>
std::string CBlockFileInfo::ToString() const
@@ -158,18 +159,26 @@ int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& fr
/** Find the last common ancestor two blocks have.
* Both pa and pb must be non-nullptr. */
const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
+ // First rewind to the last common height (the forking point cannot be past one of the two).
if (pa->nHeight > pb->nHeight) {
pa = pa->GetAncestor(pb->nHeight);
} else if (pb->nHeight > pa->nHeight) {
pb = pb->GetAncestor(pa->nHeight);
}
-
- while (pa != pb && pa && pb) {
+ while (pa != pb) {
+ // Jump back until pa and pb have a common "skip" ancestor.
+ while (pa->pskip != pb->pskip) {
+ // This logic relies on the property that equal-height blocks have equal-height skip
+ // pointers.
+ Assume(pa->nHeight == pb->nHeight);
+ Assume(pa->pskip->nHeight == pb->pskip->nHeight);
+ pa = pa->pskip;
+ pb = pb->pskip;
+ }
+ // At this point, pa and pb are different, but have equal pskip. The forking point lies in
+ // between pa/pb on the one end, and pa->pskip/pb->pskip on the other end.
pa = pa->pprev;
pb = pb->pprev;
}
-
- // Eventually all chain branches meet at the genesis block.
- assert(pa == pb);
return pa;
}
Why this scored 15/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.