trie panics with cannot convert a slice of length 29 to FixedBytes<32> with small data

[ufoscout]

I am trying to replace triehash::ordered_trie_root with an equivalent function based on alloy-trie. Even if it works pretty well, sometimes alloy-trie panics with a cannot convert a slice of length 29 to FixedBytes<32> error. Here is a complete reproducer for the issue:

use std::collections::BTreeMap;

use alloy_primitives::{keccak256, B256};
use alloy_rlp::Encodable;
use alloy_trie::HashBuilder;
use nybbles::Nibbles;

fn triehash_ordered_trie_root<I>(iter: I) -> B256
where
    I: IntoIterator,
    I::Item: AsRef<[u8]>,
{
    struct Keccak256Hasher;
    impl hash_db::Hasher for Keccak256Hasher {
        type Out = B256;
        type StdHasher = plain_hasher::PlainHasher;

        const LENGTH: usize = 32;

        fn hash(x: &[u8]) -> Self::Out {
            keccak256(x)
        }
    }

    triehash::ordered_trie_root::<Keccak256Hasher, _>(iter)
}

fn alloy_ordered_trie_root<I>(iter: I) -> B256
where
    I: IntoIterator,
    I::Item: AsRef<[u8]>,
{

    let hashed = iter
    .into_iter()
    .enumerate()
    .map(|(i, v)| {
        let mut buf = Vec::new();
        i.encode(&mut buf);
        (buf, v)
    })
    .collect::<BTreeMap<_, _>>();

    let mut hb = HashBuilder::default();

    hashed.iter().for_each(|(key, val)| {
        let nibbles = Nibbles::unpack(key);
        hb.add_leaf(nibbles, val.as_ref());
    });

    hb.root()
}

// This fails with error:
// cannot convert a slice of length 29 to FixedBytes<32>
#[test]
fn small_data() {
    let data = &["cake", "pie", "candy"];
    assert_eq!(triehash_ordered_trie_root(data), alloy_ordered_trie_root(data));
}

// This succeeds.
#[test]
fn big_data() {
    let data = &["a_very_big_cake", "a_very_big_pie", "a_lots_of_candies"];
    assert_eq!(triehash_ordered_trie_root(data), alloy_ordered_trie_root(data));
}

[DaniPopes]

cc @rkrasiuk @klkvr

Should we also add these helpers in this crate?

[0xaatif]

I'm hitting this too, here's a simpler repro:

let mut builder = alloy_trie::HashBuilder::default();
for i in [0x01, 0x02, 0x80] {
    let nibbles = alloy_trie::Nibbles::unpack([i]);
    builder.add_leaf(nibbles, &[])
}
builder.root(); // boom

alloy-trie = "0.4.1"

thread 'main' panicked at /../alloy-trie-0.4.1/src/nodes/branch.rs:164:35:
cannot convert a slice of length 21 to FixedBytes<32>
stack backtrace:
   0: rust_begin_unwind
             at /rustc/../library/std/src/panicking.rs:652:5
   1: core::panicking::panic_fmt
             at /rustc/../library/core/src/panicking.rs:72:14
   2: alloy_primitives::bits::fixed::FixedBytes<_>::from_slice
             at /../alloy-primitives-0.7.7/src/bits/fixed.rs:476:23
   3: alloy_trie::nodes::branch::BranchNodeRef::child_hashes
             at /../alloy-trie-0.4.1/src/nodes/branch.rs:164:35
   4: alloy_trie::hash_builder::HashBuilder::push_branch_node
             at /../alloy-trie-0.4.1/src/hash_builder/mod.rs:314:24
   5: alloy_trie::hash_builder::HashBuilder::update
             at /../alloy-trie-0.4.1/src/hash_builder/mod.rs:279:32
   6: alloy_trie::hash_builder::HashBuilder::root
             at /../alloy-trie-0.4.1/src/hash_builder/mod.rs:137:13
   7: sketchbook::main
             at ./src/main.rs:7:5

[jonas089]

@0xaatif

        let key = load_infura_key_from_env();
        println!("Key: {}", key);
        let rpc_url = "https://mainnet.infura.io/v3/".to_string() + &key;
        let provider = Provider::try_from(rpc_url).expect("Failed to construct provider!");
        let block_hash = "0x8230bd00f36e52e68dd4a46bfcddeceacbb689d808327f4c76dbdf8d33d58ca8";
        //let untrusted_hash = "0xacb81623523bbabccb1638a907686bc2f3229c70e3ab51777bef0a635f3ac03f";

        let block = provider
            .get_block_with_txs(H256::from_str(block_hash).unwrap())
            .await
            .expect("Failed to get Block!")
            .expect("Block not found!");

        let mut builder = alloy_trie::HashBuilder::default();
        for (index, tx) in block.transactions.iter().enumerate() {
            let bytes = alloy_rlp::encode(index);
            println!("bytes: {:?}", &bytes);
            let nibbles = alloy_trie::Nibbles::unpack(bytes);
            println!("Nibbles: {:?}", &nibbles);
            builder.add_leaf(nibbles, &tx.rlp())
        }
        let root = builder.root();
        println!("Root: {:?}", &root);
        println!("Expected Root: {:?}", &block.transactions_root);

I'm having a hard time verifying the transaction trie root, can you help :)?

[rkrasiuk]

@jonas089 all indexes need to be adjusted by calling adjust_index_for_rlp

trie/src/root.rs

Lines 8 to 17 in 25c252f

	/// Adjust the index of an item for rlp encoding.
	pub const fn adjust_index_for_rlp(i: usize, len: usize) -> usize {
	if i > 0x7f {
	i
	} else if i == 0x7f || i + 1 == len {
	0
	} else {
	i + 1
	}
	}

e.g.

trie/src/root.rs

Lines 33 to 38 in afc50b7

	let mut hb = HashBuilder::default();
	let items_len = items.len();
	for i in 0..items_len {
	let index = adjust_index_for_rlp(i, items_len);