Codecov Report

❌ Patch coverage is 80.00000% with 28 lines in your changes missing coverage. Please review.
✅ Project coverage is 51.23%. Comparing base (82b9c74) to head (ab3e24d).
⚠️ Report is 2 commits behind head on develop.

❌ Your patch status has failed because the patch coverage (80.00%) is below the target coverage (90.00%). You can increase the patch coverage or adjust the target coverage.

@@             Coverage Diff             @@
##           develop    #2094      +/-   ##
===========================================
+ Coverage    51.17%   51.23%   +0.05%     
===========================================
  Files          878      878              
  Lines       152499   152602     +103     
===========================================
+ Hits         78041    78179     +138     
+ Misses       69350    69321      -29     
+ Partials      5108     5102       -6     

@claude, review this PR focusing on performance and security. Also, make sure no regression or bug is introduced.

Claude finished @kamuikatsurgi's task in 1m 49s —— View job

PR Review: BlockSTM O(n²) → O(n·R) Performance Optimization

• Read and analyze the changed files
• Review core/blockstm/dag.go for performance and correctness
• Review core/blockstm/dag_test.go for test coverage
• Review miner/worker.go for security and regression issues
• Compile findings and provide detailed feedback

Summary

This PR replaces the O(n²) UpdateDeps algorithm with an O(n·R) DepsBuilder using an inverted index and word-parallel bitsets. The implementation is well-designed and correct. I found no security vulnerabilities or regressions. The bug fixes for ValidatorBytes preservation and the delayFlag off-by-one are both valid and important.

Performance Analysis ✅

Algorithm Improvement

The new DepsBuilder achieves significant performance gains through:

1. Inverted Index (lastWriter map[Key]int) - O(1) lookup for the latest writer of any key, eliminating the O(n·W) scan per transaction in the old algorithm.

2. Word-Parallel Bitsets - Transitive reduction runs in O(N/64) using SIMD-friendly operations (Or, AndNot), compared to O(n) map operations previously.

3. Memory Efficiency - TxBitset uses []uint64 (8 bytes per 64 transactions) vs nested map[int]bool (40+ bytes per dependency entry).

Complexity: O(n·R) vs O(n²·W) where R = avg read-set size, W = avg write-set size.

Bitset Implementation (dag.go:243-292)

The bitset operations are correct:

• Set/Test use proper bit indexing with i/64 for word index and i%64 for bit position
• ForEach uses bits.TrailingZeros64 for efficient iteration (hardware-accelerated on modern CPUs)
• word &= word - 1 clears the lowest set bit correctly

Correctness Analysis ✅

DepsBuilder Algorithm (dag.go:345-390)

The core algorithm is correct:

// For each read, find the latest writer (inverted index lookup)
for _, rd := range readList {
    if writer, ok := db.lastWriter[rd.Path]; ok && writer < index {
        db.directDeps[index].Set(writer)
    }
}

// Compute transitive closure from direct dependencies
db.directDeps[index].ForEach(func(j int) {
    db.reachable[index].Or(&db.reachable[j])
})

// Transitive reduction: remove redundant edges
db.directDeps[index].AndNot(&db.reachable[index])

// Update reachability for future transactions
db.reachable[index].Or(&db.directDeps[index])

The key insight is that reachable[j] is complete for all j < index since transactions are processed sequentially. This allows the reduction in a single pass.

Dynamic Capacity Growth (dag.go:325-343)

The ensureCapacity function correctly handles blocks with >512 transactions:

• Doubles width until it can hold the needed index
• Extends all existing bitsets atomically to maintain the invariant that all bitsets have identical len(words)

Error Handling

Non-sequential indices are properly rejected (dag.go:353-356), and the error is sticky - subsequent calls return the same error, and GetDeps() returns nil.

Bug Fixes ✅

1. ValidatorBytes Preservation (worker.go:1382-1385)

Before: If len(env.mvReadMapList) == 0, the code skipped rlp.DecodeBytes and re-encoded a zero-value BlockExtraData, silently dropping ValidatorBytes.

After: rlp.DecodeBytes is always called before overwriting TxDependency:

// Always decode header extra data before overwriting TxDependency.
if err := rlp.DecodeBytes(env.header.Extra[...], &blockExtraData); err != nil {
    return err
}

This is a consensus-critical fix for Cancun sprint transitions where ValidatorBytes must be preserved.

2. delayFlag Off-by-One (worker.go:1398)

Before: reads := env.mvReadMapList[i-1] - checked the previous transaction's reads, not the current one.

After: reads := env.mvReadMapList[i] - correctly checks transaction i's reads.

This fix ensures the last transaction's coinbase/burnt-contract balance reads are properly detected.

Test Coverage ✅

The test suite is comprehensive:

The TestDepsBuilder_EquivalenceWithUpdateDeps test explicitly documents the behavioral difference on "blind overwrites" (a tx writes a key without reading it first) - this is acceptable because DepsBuilder is more precise in this case.

Potential Minor Improvements

1. Consider Pre-allocating Inner Maps

In GetDeps() (dag.go:402), the inner map is created without capacity hint:

inner := make(map[int]bool)

Since the number of dependencies is known from the bitset's popcount, consider:

inner := make(map[int]bool, bits.OnesCount64(db.directDeps[i].words[0])) // for small blocks

Impact: Minor allocation reduction; not critical.

2. Document Channel Timeout

The 1-second timeout in worker.go:1337 is reasonable but could use a comment explaining why this duration was chosen.

Security Analysis ✅

• No integer overflow risks: Bitset indices are bounded by transaction count (max ~1000 per block)
• No race conditions: DepsBuilder runs in a single goroutine; channel communication is properly synchronized with sync.Once and sync.WaitGroup
• No panic paths: Non-sequential index returns error rather than panicking; bitset operations don't access out-of-bounds indices due to ensureCapacity
• No memory exhaustion: Bitset width grows by doubling (logarithmic memory growth)

Verdict

Approve ✅

The implementation is correct, well-tested, and achieves the stated performance goals. The bug fixes address real issues that could cause consensus failures. The behavioral difference on blind overwrites is documented and actually represents more precise dependency tracking.
|

Quality Gate failed

Failed conditions
11 Security Hotspots

See analysis details on SonarQube Cloud