firewood_triehash/
lib.rs

1// Copyright 2020 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9//! Generetes trie root.
10//!
11//! This module should be used to generate trie root hash.
12
13#![expect(
14    clippy::arithmetic_side_effects,
15    reason = "Found 7 occurrences after enabling the lint."
16)]
17#![expect(
18    clippy::bool_to_int_with_if,
19    reason = "Found 1 occurrences after enabling the lint."
20)]
21#![expect(
22    clippy::indexing_slicing,
23    reason = "Found 13 occurrences after enabling the lint."
24)]
25
26use std::cmp;
27use std::collections::BTreeMap;
28use std::iter::once;
29
30use hash_db::Hasher;
31use rlp::RlpStream;
32
33fn shared_prefix_len<T: Eq>(first: &[T], second: &[T]) -> usize {
34    first
35        .iter()
36        .zip(second.iter())
37        .position(|(f, s)| f != s)
38        .unwrap_or_else(|| cmp::min(first.len(), second.len()))
39}
40
41/// Generates a trie root hash for a vector of values
42///
43/// ```
44/// use hex_literal::hex;
45/// use ethereum_types::H256;
46/// use firewood_triehash::ordered_trie_root;
47/// use keccak_hasher::KeccakHasher;
48///
49/// let v = &["doe", "reindeer"];
50/// let root = H256::from(hex!("e766d5d51b89dc39d981b41bda63248d7abce4f0225eefd023792a540bcffee3"));
51/// assert_eq!(ordered_trie_root::<KeccakHasher, _>(v), root.as_ref());
52/// ```
53pub fn ordered_trie_root<H, I>(input: I) -> H::Out
54where
55    I: IntoIterator,
56    I::Item: AsRef<[u8]>,
57    H: Hasher,
58    <H as hash_db::Hasher>::Out: cmp::Ord,
59{
60    trie_root::<H, _, _, _>(
61        input
62            .into_iter()
63            .enumerate()
64            .map(|(i, v)| (rlp::encode(&i), v)),
65    )
66}
67
68/// Generates a trie root hash for a vector of key-value tuples
69///
70/// ```
71/// use hex_literal::hex;
72/// use firewood_triehash::trie_root;
73/// use ethereum_types::H256;
74/// use keccak_hasher::KeccakHasher;
75///
76/// let v = vec![
77///     ("doe", "reindeer"),
78///     ("dog", "puppy"),
79///     ("dogglesworth", "cat"),
80/// ];
81///
82/// let root = H256::from(hex!("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3"));
83/// assert_eq!(trie_root::<KeccakHasher, _, _, _>(v), root.as_ref());
84/// ```
85pub fn trie_root<H, I, A, B>(input: I) -> H::Out
86where
87    I: IntoIterator<Item = (A, B)>,
88    A: AsRef<[u8]> + Ord,
89    B: AsRef<[u8]>,
90    H: Hasher,
91    <H as hash_db::Hasher>::Out: cmp::Ord,
92{
93    // first put elements into btree to sort them and to remove duplicates
94    let input = input.into_iter().collect::<BTreeMap<_, _>>();
95
96    let mut nibbles = Vec::with_capacity(input.keys().map(|k| k.as_ref().len()).sum::<usize>() * 2);
97    let mut lens = Vec::with_capacity(input.len() + 1);
98    lens.push(0);
99    for k in input.keys() {
100        for &b in k.as_ref() {
101            nibbles.push(b >> 4);
102            nibbles.push(b & 0x0F);
103        }
104        lens.push(nibbles.len());
105    }
106
107    // then move them to a vector
108    let input = input
109        .into_iter()
110        .zip(lens.windows(2))
111        .map(|((_, v), w)| (&nibbles[w[0]..w[1]], v))
112        .collect::<Vec<_>>();
113
114    let mut stream = RlpStream::new();
115    hash256rlp::<H, _, _>(&input, 0, &mut stream);
116    H::hash(&stream.out())
117}
118
119/// Generates a key-hashed (secure) trie root hash for a vector of key-value tuples.
120///
121/// ```
122/// use hex_literal::hex;
123/// use ethereum_types::H256;
124/// use firewood_triehash::sec_trie_root;
125/// use keccak_hasher::KeccakHasher;
126///
127/// let v = vec![
128///     ("doe", "reindeer"),
129///     ("dog", "puppy"),
130///     ("dogglesworth", "cat"),
131/// ];
132///
133/// let root = H256::from(hex!("d4cd937e4a4368d7931a9cf51686b7e10abb3dce38a39000fd7902a092b64585"));
134/// assert_eq!(sec_trie_root::<KeccakHasher, _, _, _>(v), root.as_ref());
135/// ```
136pub fn sec_trie_root<H, I, A, B>(input: I) -> H::Out
137where
138    I: IntoIterator<Item = (A, B)>,
139    A: AsRef<[u8]>,
140    B: AsRef<[u8]>,
141    H: Hasher,
142    <H as hash_db::Hasher>::Out: cmp::Ord,
143{
144    trie_root::<H, _, _, _>(input.into_iter().map(|(k, v)| (H::hash(k.as_ref()), v)))
145}
146
147/// Hex-prefix Notation. First nibble has flags: oddness = 2^0 & termination = 2^1.
148///
149/// The "termination marker" and "leaf-node" specifier are completely equivalent.
150///
151/// Input values are in range `[0, 0xf]`.
152///
153/// ```markdown
154///  [0,0,1,2,3,4,5]   0x10012345 // 7 > 4
155///  [0,1,2,3,4,5]     0x00012345 // 6 > 4
156///  [1,2,3,4,5]       0x112345   // 5 > 3
157///  [0,0,1,2,3,4]     0x00001234 // 6 > 3
158///  [0,1,2,3,4]       0x101234   // 5 > 3
159///  [1,2,3,4]         0x001234   // 4 > 3
160///  [0,0,1,2,3,4,5,T] 0x30012345 // 7 > 4
161///  [0,0,1,2,3,4,T]   0x20001234 // 6 > 4
162///  [0,1,2,3,4,5,T]   0x20012345 // 6 > 4
163///  [1,2,3,4,5,T]     0x312345   // 5 > 3
164///  [1,2,3,4,T]       0x201234   // 4 > 3
165/// ```
166fn hex_prefix_encode(nibbles: &[u8], leaf: bool) -> impl Iterator<Item = u8> + '_ {
167    let inlen = nibbles.len();
168    let oddness_factor = inlen % 2;
169
170    let first_byte = {
171        let mut bits = ((inlen as u8 & 1) + (2 * u8::from(leaf))) << 4;
172        if oddness_factor == 1 {
173            bits += nibbles[0];
174        }
175        bits
176    };
177    once(first_byte).chain(
178        nibbles[oddness_factor..]
179            .chunks(2)
180            .map(|ch| (ch[0] << 4) | ch[1]),
181    )
182}
183
184fn hash256rlp<H, A, B>(input: &[(A, B)], pre_len: usize, stream: &mut RlpStream)
185where
186    A: AsRef<[u8]>,
187    B: AsRef<[u8]>,
188    H: Hasher,
189{
190    let inlen = input.len();
191
192    // in case of empty slice, just append empty data
193    if inlen == 0 {
194        stream.append_empty_data();
195        return;
196    }
197
198    // take slices
199    let key: &[u8] = input[0].0.as_ref();
200    let value: &[u8] = input[0].1.as_ref();
201
202    // if the slice contains just one item, append the suffix of the key
203    // and then append value
204    if inlen == 1 {
205        stream.begin_list(2);
206        stream.append_iter(hex_prefix_encode(&key[pre_len..], true));
207        stream.append(&value);
208        return;
209    }
210
211    // get length of the longest shared prefix in slice keys
212    let shared_prefix = input
213        .iter()
214        // skip first tuple
215        .skip(1)
216        // get minimum number of shared nibbles between first and each successive
217        .fold(key.len(), |acc, (k, _)| {
218            cmp::min(shared_prefix_len(key, k.as_ref()), acc)
219        });
220
221    // if shared prefix is higher than current prefix append its
222    // new part of the key to the stream
223    // then recursively append suffixes of all items who had this key
224    if shared_prefix > pre_len {
225        stream.begin_list(2);
226        stream.append_iter(hex_prefix_encode(&key[pre_len..shared_prefix], false));
227        hash256aux::<H, _, _>(input, shared_prefix, stream);
228        return;
229    }
230
231    // an item for every possible nibble/suffix
232    // + 1 for data
233    stream.begin_list(17);
234
235    // if first key len is equal to prefix_len, move to next element
236    let mut begin = if pre_len == key.len() { 1 } else { 0 };
237
238    // iterate over all possible nibbles
239    for i in 0..16 {
240        // count how many successive elements have same next nibble
241        let len = input
242            .iter()
243            .skip(begin)
244            .take_while(|pair| pair.0.as_ref()[pre_len] == i)
245            .count();
246
247        // if at least 1 successive element has the same nibble
248        // append their suffixes
249        match len {
250            0 => {
251                stream.append_empty_data();
252            }
253            _ => hash256aux::<H, _, _>(&input[begin..(begin + len)], pre_len + 1, stream),
254        }
255        begin += len;
256    }
257
258    // if fist key len is equal prefix, append its value
259    if pre_len == key.len() {
260        stream.append(&value);
261    } else {
262        stream.append_empty_data();
263    }
264}
265
266fn hash256aux<H, A, B>(input: &[(A, B)], pre_len: usize, stream: &mut RlpStream)
267where
268    A: AsRef<[u8]>,
269    B: AsRef<[u8]>,
270    H: Hasher,
271{
272    let mut s = RlpStream::new();
273    hash256rlp::<H, _, _>(input, pre_len, &mut s);
274    let out = s.out();
275    match out.len() {
276        0..=31 => stream.append_raw(&out, 1),
277        _ => stream.append(&H::hash(&out).as_ref()),
278    };
279}
280
281#[cfg(test)]
282mod tests {
283    use super::{hex_prefix_encode, shared_prefix_len, trie_root};
284    use ethereum_types::H256;
285    use hex_literal::hex;
286    use keccak_hasher::KeccakHasher;
287
288    #[test]
289    fn test_hex_prefix_encode() {
290        let v = vec![0, 0, 1, 2, 3, 4, 5];
291        let e = vec![0x10, 0x01, 0x23, 0x45];
292        let h = hex_prefix_encode(&v, false).collect::<Vec<_>>();
293        assert_eq!(h, e);
294
295        let v = vec![0, 1, 2, 3, 4, 5];
296        let e = vec![0x00, 0x01, 0x23, 0x45];
297        let h = hex_prefix_encode(&v, false).collect::<Vec<_>>();
298        assert_eq!(h, e);
299
300        let v = vec![0, 1, 2, 3, 4, 5];
301        let e = vec![0x20, 0x01, 0x23, 0x45];
302        let h = hex_prefix_encode(&v, true).collect::<Vec<_>>();
303        assert_eq!(h, e);
304
305        let v = vec![1, 2, 3, 4, 5];
306        let e = vec![0x31, 0x23, 0x45];
307        let h = hex_prefix_encode(&v, true).collect::<Vec<_>>();
308        assert_eq!(h, e);
309
310        let v = vec![1, 2, 3, 4];
311        let e = vec![0x00, 0x12, 0x34];
312        let h = hex_prefix_encode(&v, false).collect::<Vec<_>>();
313        assert_eq!(h, e);
314
315        let v = vec![4, 1];
316        let e = vec![0x20, 0x41];
317        let h = hex_prefix_encode(&v, true).collect::<Vec<_>>();
318        assert_eq!(h, e);
319    }
320
321    #[test]
322    fn simple_test() {
323        assert_eq!(
324            trie_root::<KeccakHasher, _, _, _>(vec![(
325                b"A",
326                b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" as &[u8]
327            )]),
328            H256::from(hex!(
329                "d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab"
330            ))
331            .as_ref(),
332        );
333    }
334
335    #[test]
336    fn test_triehash_out_of_order() {
337        assert_eq!(
338            trie_root::<KeccakHasher, _, _, _>(vec![
339                (vec![0x01u8, 0x23], vec![0x01u8, 0x23]),
340                (vec![0x81u8, 0x23], vec![0x81u8, 0x23]),
341                (vec![0xf1u8, 0x23], vec![0xf1u8, 0x23]),
342            ]),
343            trie_root::<KeccakHasher, _, _, _>(vec![
344                (vec![0x01u8, 0x23], vec![0x01u8, 0x23]),
345                (vec![0xf1u8, 0x23], vec![0xf1u8, 0x23]), // last two tuples are swapped
346                (vec![0x81u8, 0x23], vec![0x81u8, 0x23]),
347            ]),
348        );
349    }
350
351    #[test]
352    fn test_shared_prefix() {
353        let a = vec![1, 2, 3, 4, 5, 6];
354        let b = vec![4, 2, 3, 4, 5, 6];
355        assert_eq!(shared_prefix_len(&a, &b), 0);
356    }
357
358    #[test]
359    fn test_shared_prefix2() {
360        let a = vec![1, 2, 3, 3, 5];
361        let b = vec![1, 2, 3];
362        assert_eq!(shared_prefix_len(&a, &b), 3);
363    }
364
365    #[test]
366    fn test_shared_prefix3() {
367        let a = vec![1, 2, 3, 4, 5, 6];
368        let b = vec![1, 2, 3, 4, 5, 6];
369        assert_eq!(shared_prefix_len(&a, &b), 6);
370    }
371}
firewood_triehash/lib.rs

firewood_triehash/
lib.rs
