Optimize StoredNibbles&StoredNibblesSubKey storage format to reduce size and fix ambiguity

[AshinGau]

Problem Description

The current StoredNibblesSubKey implementation in crates/trie/common/src/nibbles.rs has a significant storage inefficiency:

Storage Inefficiency: Uses a fixed 65-byte format (64 bytes for nibbles data + 1 byte for length) regardless of actual content size. This doubles the storage requirement from 32 bytes to 64 bytes for nibbles data, resulting in unnecessary storage overhead.

Current Implementation

#[cfg(any(test, feature = "reth-codec"))]
impl reth_codecs::Compact for StoredNibblesSubKey {
    fn to_compact<B>(&self, buf: &mut B) -> usize
    where
        B: bytes::BufMut + AsMut<[u8]>,
    {
        assert!(self.0.len() <= 64);

        // right-pad with zeros
        buf.put_slice(&self.0.to_vec());
        static ZERO: &[u8; 64] = &[0; 64];
        buf.put_slice(&ZERO[self.0.len()..]);

        buf.put_u8(self.0.len() as u8);
        64 + 1
    }

    fn from_compact(buf: &[u8], _len: usize) -> (Self, &[u8]) {
        let len = buf[64] as usize;
        (Self(Nibbles::from_nibbles_unchecked(&buf[..len])), &buf[65..])
    }
}

Constraints for Solution

Any optimization must satisfy these requirements:

1. Ambiguity Resolution: The Nibbles::pack() method pads odd-length nibbles with a zero nibble, causing ambiguity between ["0x0A"] and ["0x0A", "0x00"] - both produce the same packed result. The solution must preserve the original length to distinguish between these cases.

2. Dictionary Order Preservation: Reth relies on proper dictionary ordering of Nibbles for trie operations, which must be preserved in any storage optimization.

Proposed Solution

Use the existing Nibbles::pack() and Nibbles::unpack() methods to compress storage while preserving the original length to avoid ambiguity:

#[cfg(any(test, feature = "reth-codec"))]
impl reth_codecs::Compact for StoredNibblesSubKey {
    fn to_compact<B>(&self, buf: &mut B) -> usize
    where
        B: bytes::BufMut + AsMut<[u8]>,
    {
        let pack = self.0.pack();
        let encoded_len = self.len() + 1;
        buf.put_u8(encoded_len as u8);
        buf.put_slice(&pack);
        pack.len() + 1
    }

    fn from_compact(buf: &[u8], _len: usize) -> (Self, &[u8]) {
        let encoded_len = buf[0];
        let odd = encoded_len % 2 == 0;
        let pack_len = (encoded_len / 2) as usize;
        let mut nibbles = Nibbles::unpack(&buf[1..1 + pack_len]);
        if odd {
            nibbles.pop();
        }

        (Self(nibbles), &buf[pack_len + 1..])
    }
}

Benefits

1. Storage Reduction: Reduces storage size from 65 bytes to approximately 17-33 bytes (depending on content)
2. Ambiguity Resolution: Preserves original length to distinguish between ["0x0A"] and ["0x0A", "0x00"]
3. Dictionary Order Preservation: Maintains correct ordering through pack()/unpack() methods

Impact

• Storage Savings: ~20% reduction in storage size for StoragesTrie table
• Performance: Slightly faster serialization/deserialization due to smaller data size
• Compatibility: Cannot be compatible with previous data

[Rjected]

filed a more detailed issue here:
#17843

if we can discern between the new and old format (at least for storage subkeys) we could do this in a backwards compatible way