Skip to content

Sync Java SDK SMT/RSMT bit ordering with the spec #79

Description

@ristik

The Yellowpaper now treats 32-byte Merkle keys as 256-bit big-endian bit strings: depth 0 is key[0] & 0x80, depth 7 is key[0] & 0x01, and depth 255 is key[31] & 0x01. Bitmap vectors are also big-endian bit vectors. The Java SDK still contains old LSB-oriented tree routing.

Hot spots:

  • src/main/java/org/unicitylabs/sdk/util/BitString.java: retire/avoid fromBytesReversedLSB for Merkle paths; expose one spec-aligned key-path helper.
  • src/main/java/org/unicitylabs/sdk/smt/CommonPath.java: update common-prefix logic from low-bit-first paths to big-endian prefix paths.
  • src/main/java/org/unicitylabs/sdk/smt/radix/SparseMerkleTree.java: update aggregator-facing SMT insertion/routing.
  • src/main/java/org/unicitylabs/sdk/api/InclusionCertificate.java: update key-path conversion, bitmap masks (0x80 >> (depth % 8)), bitmap decoding, and proof reconstruction.
  • src/main/java/org/unicitylabs/sdk/smt/plain/*, src/main/java/org/unicitylabs/sdk/smt/sum/*, and payment split code using toBitString().toBigInteger(): align split-allocation SMT/SMST paths with the same convention.
  • src/test/java/org/unicitylabs/sdk/TestAggregatorClient.java and SMT/proof fixtures: update expected paths, bitmaps, and vectors.
  • src/main/java/org/unicitylabs/sdk/api/bft/ShardId.java / ShardIdMatchesStateIdRule: verify these remain MSB-prefix compatible; they appear to already use high-bit prefix semantics.

Acceptance:

  • Depth/bitmap examples above are covered by tests.
  • Region/path-prefix bytes, where serialized or hashed, preserve high-order prefix bits and zero the suffix.
  • Traversal/sort order is raw unsigned lexicographic byte order (rsmt_sort_key(k) = k).
  • Inclusion certificates and split-allocation proofs interoperate with the spec and aggregator after the bit-order update.

Feel free to tailgate issue-75 if it feels appropriate.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Fields

No fields configured for issues without a type.

Projects

Status
In Dev

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions