Sync Aggregator SMT bit ordering with Yellowpaper big-endian bit strings

[ristik]

Summary

The Yellowpaper RSMT/RSMST specification now defines keys, regions, and inclusion bitmaps using big-endian bit-string notation:

• SMT keys are 32-byte values read as 256-bit big-endian bit strings.
• Depth d addresses bit d of that big-endian bit string.
• rsmt_sort_key(k) = k; ordinary unsigned lexicographic byte order is the tree traversal order.
• Inclusion certificate bitmaps are 256-bit big-endian bit vectors.
• Regions are packed as 256-bit big-endian bit strings: the first d bits are the key prefix and the suffix is zero.

The Go Aggregator still has explicit LSB-in-byte assumptions in the SMT implementation, proof verification, sharding prefix checks, and disk SMT encoding. Update the implementation and tests to match the spec.

Why

The change should make Go follow the natural bit order used by ordinary byte comparisons and big-endian bit-string notation.

Current Hotspots

Likely places that need changes:

• pkg/api/state_id.go

  • PathToFixedBytes and FixedBytesToPath currently reverse byte order for an LSB-first SMT key layout.
  • Comments explicitly say key bit d is bit (d%8) of key[d/8].

• pkg/api/state_id_bitorder_test.go

  • Tests pin LSB-first semantics (TestFixedBytesToPath_UsesLSBFirstBitAddressing, RoundtripLSBFirst).

• pkg/api/inclusion_cert.go

  • verifyBitmapPath tests bitmap bits using (bitmap[d/8] >> (d%8)) & 1.
  • keyBitAt uses LSB-in-byte.
  • RegionFromKeyBytes packs prefixes by copying low-order bits in each byte and masking with (1 << rem) - 1.
  • Comments mention LSB-first layout.

• pkg/api/inclusion_cert_compose.go

  • bitmapDepthRange uses LSB-in-byte bitmap indexing.

• pkg/api/smt.go

  • RegionFromPathBits packs path.Bit(i) into region[i/8] |= 1 << (i % 8).
  • Comments describe v6a region bits as LSB-in-byte.

• pkg/api/shard_match.go

  • MatchesShardPrefix checks LSB-first key bits and reads expected shard bits from the low bits of shardBitmask.
  • This should be reconciled with the spec's shard-prefix interpretation.

• internal/smt/smt.go

  • populate sets region bits with rightRegion[depth/8] |= 1 << (depth % 8).
  • Parent-mode shard tree construction depends on this bit convention.

• internal/smt/disk/hash.go

  • HashNode comment says region is packed LSB-in-byte.
  • RegionFromKey and KeyBit use LSB-in-byte.

• internal/smt/disk/path.go

  • CompressedPath construction, BitAt, and unused-bit canonicalization use LSB-in-byte packing.

• internal/smt/disk/node_key.go

  • clearUnusedPrefixBits masks unused bits as if prefix bits are LSB-in-byte.
  • Persisted node keys include prefix bytes, so this affects disk compatibility and migration decisions.

• internal/smt/disk/persist/tree.go

  • Inclusion certificate generation sets bitmap bits with 1 << (depth % 8).
  • setPrefixBit uses LSB-in-byte prefix packing.

• Test/vector files

  • internal/smt/golden_vectors_test.go
  • internal/smt/v6a_interop_vectors_test.go
  • internal/smt/yellowpaper_hash_semantics_test.go
  • pkg/api/inclusion_cert_test.go
  • internal/smt/disk/*_test.go
  • Any golden roots or certificates generated under the old convention must be regenerated or explicitly marked legacy.

Implementation Notes

Prefer introducing small shared helpers instead of repeating shifts everywhere:

• KeyBit(key []byte, d int) byte: return (key[d/8] >> (7 - uint(d%8))) & 1
• SetBitBE(bits []byte, d int): bits[d/8] |= 0x80 >> uint(d%8)
• ClearSuffixBE(prefix []byte, bitLen int) for region/bitmap/path canonicalization.
• RegionFromKeyBytes(key []byte, depth int) should copy the prefix bytes and keep the high depth % 8 bits in the boundary byte.

For non-byte-aligned prefixes, the old LSB mask (1 << rem) - 1 becomes a high-bit mask, e.g. 0xff << (8 - rem) when rem != 0.

Migration / Compatibility

Changing bit order changes:

• SMT root hashes.
• Inclusion certificate bitmap bytes.
• Internal-node region bytes, hence node hashes.
• Shard routing and split behavior.
• Persisted disk SMT node keys and stored roots.
• Existing golden vectors.

No backwards compatibility needed. Old-format disk-backed SMT data can be deleted.

Acceptance Criteria

• All SMT key-bit access, bitmap access, region packing, and prefix packing in Aggregator use big-endian bit-string semantics.
• FixedBytesToPath / PathToFixedBytes round-trip without reversing the 32-byte key order relative to spec key bytes.
• Inclusion certificate verification and generation use big-endian bitmap bits.
• RSMT node hashes match the updated Yellowpaper region packing.
• Batch/traversal ordering is ordinary unsigned lexicographic byte order (rsmt_sort_key(k)=k).
• Shard-prefix matching and shard split/parent proof logic are aligned with the same bit convention.
• Disk SMT metadata/versioning prevents old-layout persisted data from being silently interpreted as new-layout data.
• Tests cover boundary depths: 0, 1, 7, 8, 200, 255.
• Golden vectors are regenerated for the new convention, with any retained old vectors clearly labeled legacy.

Out of Scope

• Changing CBOR serialization structure or public proof envelope shapes.
• Changing hash domain separators.
• Changing key byte order on the wire; only bit indexing within the existing byte string changes.

[b3y0urs3lf]

QA verification report — Issue #169

Aggregator-side + SDK-side testing complete for the big-endian bit-ordering switch delivered by PR #170 (commits 3d78046 + 319228d). All 9 acceptance criteria in this issue
verified. Recommended to close after PR #170 merges.

Setup tested

• Branch: ha-bft-hardening HEAD + feat/smt-bigendian-bits merged (fd6901f).
• Topology: 2-shard, 2-replica HA bft-sharding stack (bft-sharding-ha-compose.yml).
• SMT backend: RocksDB with layout string yellowpaper-rsmt-sha256-v6a-be (bumped from PR Switch SMT node hashing to the v6a construction #168's v6a).
• Host: Intel i7-11375H (4C/8T), 62 GB RAM, ext4 on LVM, Ubuntu 24.04.4, kernel 6.17, Docker 29.5.0.

Acceptance criteria — verification status

• BE bit semantics everywhere. New helpers KeyBitBE, SetBitBE, ClearSuffixBE in pkg/api/bits.go:15-38 with formulas matching this issue byte-for-byte. Grep for the old
  LSB pattern (>> uint(d%8) without 7 - prefix) returns zero non-test matches across pkg/api and internal/smt. Verified by aggregator Go unit test suite (all packages green)
  and SDK's independent BE implementation.
• Round-trip conversion without reversing 32-byte key order. pkg/api/state_id.go:102-131 FixedBytesToPath uses bits.Reverse8 per byte over reversed byte order; :68-99
PathToFixedBytes inverts the same. Verified by TestPathToFixedBytes_RoundtripBigEndian PASSED.
• Inclusion certificate verification matches BE bitmap bits. pkg/api/inclusion_cert.go:140,153 verifier uses KeyBitBE. Cert build uses SetBitBE at
  internal/smt/disk/persist/tree.go:574 (disk) and internal/smt/smt.go:714 (in-memory). Verified by SDK V7 100 / 100 live hash reconstruction (see below).
• RSMT node hashes align with updated region packing. RegionFromKeyBytes at pkg/api/inclusion_cert.go:250-265 and RegionFromKey at internal/smt/disk/hash.go:68-75 use
  ClearSuffixBE. Node hash formula unchanged (H(0x01 || depth || region || L || R)) but region is now BE-packed.
• Batch / traversal is ordinary unsigned lexicographic byte order. internal/smt/disk/tree.go:530-532 and internal/smt/disk/persist/tree.go:1689-1692 both collapse
  keyPathLess to bytes.Compare(left[:], right[:]) < 0. Yellowpaper's rsmt_sort_key(k) = k reference honored.
• Shard-prefix matching uses consistent bit convention. pkg/api/shard_match.go:28 uses KeyBitBE for the key side. Mask side stays LSB (correct — sentinel-prefixed shard ID).
  Verified live: cross-shard traffic in T3 (below) routes correctly to both shards.
• Disk SMT metadata prevents silent misinterpretation of old-layout data. internal/smt/disk/rocksstore/store.go:67 sets TreeLayout = "yellowpaper-rsmt-sha256-v6a-be".
  Open-time reject at :950-951 with error unsupported disk SMT tree layout %q, want %q. Verified runtime end-to-end — see T2 below.
• Boundary depth tests at 0, 1, 7, 8, 200, 255. pkg/api/state_id_bitorder_test.go:14-48 TestFixedBytesToPath_UsesBigEndianBitAddressing covers all 6, plus extras at 9, 254,

256. PASSED.

• Golden vectors regenerated. internal/smt/v6a_interop_vectors_test.go roots updated for BE construction. JS SDK parity vector root changed from cd23fc12654... to
  c854db11e92d269e7a4dc558adb201da311604d0bcc9883a8f1f017862166ede. Shallow-split, deep-split, multi-leaf constants regenerated.

How verified — QA aggregator-side direct tests

Four runtime tests against the live cluster on the merged HEAD:

• T1 Empty-root sanity — passed. All 4 replicas started with diskRootHash: 0000000000000000000000000000000000000000000000000000000000000000 in their startup logs. BE genesis
  matches Yellowpaper's ⊥.
• T2 Layout rejection of pre-BE data — passed. Generated v6a data by checking out ddb1d5c (PR Switch SMT node hashing to the v6a construction #168 HEAD) + boot + 40 finalized blocks + snapshot. Restored the snapshot into a
  fresh v6a-BE image build. All 4 aggregator containers entered Restarting (1) loop with exit code 1, logging the exact expected error: open RocksDB SMT backend: unsupported disk SMT tree layout "yellowpaper-rsmt-sha256-v6a", want "yellowpaper-rsmt-sha256-v6a-be". Silent misinterpretation of legacy data is prevented as designed.
• T3 HA leader kill under load — passed. cmd/performance-test at target ~1000 rps × 2 shards for 60s, docker kill shard0 leader at T+15s. Zero verification failures among
  the 26,673 proofs retrieved — BE hash formula correct end-to-end. Submission losses on the killed shard are 12-second HAProxy 503 outage window (same as PR Switch SMT node hashing to the v6a construction #168 baseline); shard1
  untouched at 100%. Aggregator side: 0 ERROR-level logs, 0 panics. Not a BE regression.
• T4 Cross-shard correlated crash — passed. Killed both shard leaders simultaneously; both standby's promoted within 30s; block production resumed on both.

Plus Go unit test suite for all packages touched by PR #170 (internal/smt, internal/smt/disk, pkg/api, internal/service) — all green, including the independent BE
reference test TestBigEndianReferenceMatchesProduction at internal/smt/be_reference_anchor_test.go:96.

How verified — SDK external independent track

SDK BDD suite delivered under @disk-smt-coverage @v6a-hash-parity (via state-transition-sdk-js PR #135):

• 15 / 15 hermetic scenarios green — covers empty tree, one-leaf, shallow split at bit 0, deep split at bit 255, shallow-key regression against commit 319228d, sequential mint
  burst, depth-boundary sweep at bits 8/16/32/64/128/240/255, and BE golden wire vector. Runs in ~150ms.
• 6-key JS SDK parity vector reproduces c854db11e92d269e7a4dc558adb201da311604d0bcc9883a8f1f017862166ede byte-for-byte from internal/smt/v6a_interop_vectors_test.go:61-80.
  Pinned in 3 SDK locations plus aggregator fixture at docs/interop-fixtures/v6a-jssdk-parity.json.
• V7 live-cluster hash reconstruction, 100 real mints against this PR's cluster. SDK reconstructs the aggregator-returned root via its own BE InclusionCertificate.calculateRoot
  for each proof. 100 / 100 byte-matched over 4m59s wall clock. Definitive interop-contract proof.
• Asymmetric bit0-vs-bit7 canary — cross-parity verified byte-for-byte. Two 2-key trees differing at bit 0 (0x80) vs bit 7 (0x01) respectively yield roots
  8889167c4c199349bd145eb5c7b1b96f512d4ca029aa2e5e9e3520510dc2a194 and abf5e8c8a65b3eabed79867e518852001aaccf05cd95878a9ea3feabcda6f47d. Reproduced identically on aggregator side
  via a Go test that constructs SDK's exact tree setup (internal/smt/sdk_v13_cross_verify_test.go). A half-flipped implementation cannot pass this test — proves BE indexing is
  complete and consistent across both implementations.
• Additional SDK BEBitOrderingComplianceTest.ts — 40 unit tests across static pins, region-from-key sweeps at 10 depths, defensive-copy invariants, encoding stability.

What was NOT runtime-tested by QA (with reasons)

• Interop vector via aggregator JSON-RPC API. submit_commitment requires cryptographic signatures and cannot accept raw (key, value) tuples. Covered externally by SDK's V5
  (hermetic) and V7 (100 / 100 live) instead.
• Deep-split bit-255 via aggregator JSON-RPC API. Same crypto-signature blocker. Covered by SDK V4 + V10 (Scenario Outline across 7 depths).
• Application-sharding topology (parent + child aggregators) under BE. Attempted end-to-end via sharding-ha-compose.yml, hit orchestration issues unrelated to BE (Mongo replica
  set init timing + bind-mount permission requirements for genesis directories). The compose file appears to lack user: directives that its bft-sharding sibling has. Parent-mode
  BE region math is covered by internal/smt/thread_safe_smt_test.go unit tests (PASSED) which exercise NewParentSparseMerkleTree(SHA256, 2) with sentinel-bit paths; recommend a
  follow-up fix to the compose file for future application-sharding E2E runs, tracked separately from this issue.
• Java + Rust SDK cross-implementation vectors. Deferred to separate rounds when those SDKs land BE.

Delivered by PR #170 but not documented in this issue

Not defects — design decisions and defensive additions worth noting:

• internal/smt/be_reference_anchor_test.go NEW 155 lines — an independent big-endian reference implementation sharing zero code with production; canary case
  asymmetric_bit0_vs_bit7 designed so a half-flipped implementation cannot pass. Substantial hardening beyond what this issue asked.
• internal/smt/smt.go:132-134 NewParentSparseMerkleTree parent-mode region init uses api.SetBitBE(rightRegion, 0) — changes parent-mode tree shape and root hash under BE.
• NodeKey.clearUnusedPrefixBits at internal/smt/disk/node_key.go:118-124 and CompressedPath.hasCanonicalUnusedBits at internal/smt/disk/path.go:103-108 delegate to
  api.ClearSuffixBE — silent semantic change to on-disk prefix mask, gated by TreeLayout bump.
• Randomized full-width parity test at internal/smt/disk/persist/tree_test.go:35-95 — 400 leaves × 20 batches, RNG seed 42, cross-checks disk vs in-memory. New test coverage.
• internal/service/service_test.go:310-317 shard-mismatch fixture stateId byte flipped 0x01 → 0x80 to actually mismatch shard 4 under BE. Anyone writing similar tests must
  update.
• internal/smt/disk/persist/tree_test.go:325-333 fixture bytes flipped explicitly per BE convention.
• Exported RegionFromKeyBytes (pkg/api/inclusion_cert.go:250-265) and RegionFromPathBits (pkg/api/smt.go:192-206) — signatures unchanged, semantics silently changed from LSB
  to BE packing. Downstream Go consumers see behavior change.
• internal/smt/smt.go:435 comment retained "v6a internal-node hash" — region-packing description in the comment did not update to reflect BE. Minor doc drift.

Verdict

• Every one of the 9 acceptance criteria in this issue has code evidence at specific file:line locations, and every one is verified by direct QA test, SDK-side test, or Go unit test.
• T2 layout rejection was runtime-verified end-to-end with the exact expected reject string.
• V13 asymmetric bit0-vs-bit7 canary is the strongest interop proof to date — an independent SDK BE implementation and the aggregator's independent Go BE implementation converge on
  identical hex values for tests specifically designed to fail on half-flipped code.
• No data loss, no root divergence, no verification failures observed under any tested scenario.

Issue #169 delivery satisfies the acceptance criteria. Ready to close after PR #170 merges.