BLS Signature Batch Verification Cache Index Collision via Truncated Message Root

[JamesEjembi]

Problem Statement / Feature Objective

The BLS signature batch verification cache uses a HashMap keyed by (message_root, aggregator_index). When two distinct committees produce aggregates for different messages that hash-collide on the 32-bit truncated message_root (a XOR-fold of SHA-256), the cache returns a cached verification result for the wrong aggregate, either falsely accepting an invalid signature or falsely rejecting a valid one.

Technical Invariants & Bounds

• Cache key: (message_root_32: u32, aggregator_index: u32) -> u64 bit key.
• Message root is SHA-256 truncated to 32 bits via XOR-folding.
• Collision probability per 10k entries: ~1.2% (birthday bound for 32-bit space).
• Cache size: LRU with max 8192 entries.
• Verification result is a bool (pass/fail) with no context.

Codebase Navigation Guide

• src/attestation/bls-aggregator.rs - verify_batch_with_cache() and cache data structures.
• src/crypto/merkle.rs - hash_message_to_root() truncation logic.
• src/crypto/verifier.rs - batch_verify() underlying pairing computation.
• tests/crypto/bls_cache_collision_test.rs - cache collision tests.

Implementation Blueprint

1. In src/attestation/bls-aggregator.rs, expand the cache key to (message_root_256: [u8; 32], aggregator_index: u64) using the full hash.
2. Replace the HashMap with a BTreeMap or a custom fixed-size associative cache using the full 40-byte key.
3. Alternatively, keep the truncated key but store a full hash alongside the result and verify match on lookup.
4. Add a property test that artificially generates hash collisions (by iterating messages) and asserts the cache never returns a false positive.
5. Benchmark cache hit rate before and after; ensure no more than 5% throughput regression.