hpl_interface/types/
merkle.rs

1use cosmwasm_schema::cw_serde;
2use cosmwasm_std::{ensure, HexBinary, StdError, StdResult};
3
4use super::keccak256_hash;
5
6pub const HASH_LENGTH: usize = 32;
7pub const TREE_DEPTH: usize = 32;
8pub const MAX_LEAVES: u128 = (2_u128.pow(TREE_DEPTH as u32)) - 1;
9
10pub const ZERO_BYTES: &str = "0000000000000000000000000000000000000000000000000000000000000000";
11pub const ZERO_HASHES: [&str; TREE_DEPTH] = [
12    "0000000000000000000000000000000000000000000000000000000000000000",
13    "ad3228b676f7d3cd4284a5443f17f1962b36e491b30a40b2405849e597ba5fb5",
14    "b4c11951957c6f8f642c4af61cd6b24640fec6dc7fc607ee8206a99e92410d30",
15    "21ddb9a356815c3fac1026b6dec5df3124afbadb485c9ba5a3e3398a04b7ba85",
16    "e58769b32a1beaf1ea27375a44095a0d1fb664ce2dd358e7fcbfb78c26a19344",
17    "0eb01ebfc9ed27500cd4dfc979272d1f0913cc9f66540d7e8005811109e1cf2d",
18    "887c22bd8750d34016ac3c66b5ff102dacdd73f6b014e710b51e8022af9a1968",
19    "ffd70157e48063fc33c97a050f7f640233bf646cc98d9524c6b92bcf3ab56f83",
20    "9867cc5f7f196b93bae1e27e6320742445d290f2263827498b54fec539f756af",
21    "cefad4e508c098b9a7e1d8feb19955fb02ba9675585078710969d3440f5054e0",
22    "f9dc3e7fe016e050eff260334f18a5d4fe391d82092319f5964f2e2eb7c1c3a5",
23    "f8b13a49e282f609c317a833fb8d976d11517c571d1221a265d25af778ecf892",
24    "3490c6ceeb450aecdc82e28293031d10c7d73bf85e57bf041a97360aa2c5d99c",
25    "c1df82d9c4b87413eae2ef048f94b4d3554cea73d92b0f7af96e0271c691e2bb",
26    "5c67add7c6caf302256adedf7ab114da0acfe870d449a3a489f781d659e8becc",
27    "da7bce9f4e8618b6bd2f4132ce798cdc7a60e7e1460a7299e3c6342a579626d2",
28    "2733e50f526ec2fa19a22b31e8ed50f23cd1fdf94c9154ed3a7609a2f1ff981f",
29    "e1d3b5c807b281e4683cc6d6315cf95b9ade8641defcb32372f1c126e398ef7a",
30    "5a2dce0a8a7f68bb74560f8f71837c2c2ebbcbf7fffb42ae1896f13f7c7479a0",
31    "b46a28b6f55540f89444f63de0378e3d121be09e06cc9ded1c20e65876d36aa0",
32    "c65e9645644786b620e2dd2ad648ddfcbf4a7e5b1a3a4ecfe7f64667a3f0b7e2",
33    "f4418588ed35a2458cffeb39b93d26f18d2ab13bdce6aee58e7b99359ec2dfd9",
34    "5a9c16dc00d6ef18b7933a6f8dc65ccb55667138776f7dea101070dc8796e377",
35    "4df84f40ae0c8229d0d6069e5c8f39a7c299677a09d367fc7b05e3bc380ee652",
36    "cdc72595f74c7b1043d0e1ffbab734648c838dfb0527d971b602bc216c9619ef",
37    "0abf5ac974a1ed57f4050aa510dd9c74f508277b39d7973bb2dfccc5eeb0618d",
38    "b8cd74046ff337f0a7bf2c8e03e10f642c1886798d71806ab1e888d9e5ee87d0",
39    "838c5655cb21c6cb83313b5a631175dff4963772cce9108188b34ac87c81c41e",
40    "662ee4dd2dd7b2bc707961b1e646c4047669dcb6584f0d8d770daf5d7e7deb2e",
41    "388ab20e2573d171a88108e79d820e98f26c0b84aa8b2f4aa4968dbb818ea322",
42    "93237c50ba75ee485f4c22adf2f741400bdf8d6a9cc7df7ecae576221665d735",
43    "8448818bb4ae4562849e949e17ac16e0be16688e156b5cf15e098c627c0056a9",
44];
45
46#[cw_serde]
47pub struct MerkleTree {
48    pub branch: [HexBinary; TREE_DEPTH],
49    pub count: u128,
50}
51
52impl Default for MerkleTree {
53    fn default() -> Self {
54        Self {
55            branch: ZERO_HASHES
56                .into_iter()
57                .map(HexBinary::from_hex)
58                .collect::<StdResult<Vec<HexBinary>>>()
59                .unwrap()
60                .try_into()
61                .unwrap(),
62            count: Default::default(),
63        }
64    }
65}
66
67impl MerkleTree {
68    pub fn insert(&mut self, node: HexBinary) -> StdResult<()> {
69        ensure!(
70            self.count < MAX_LEAVES,
71            StdError::generic_err("tree is full")
72        );
73
74        self.count += 1;
75
76        let mut node = node;
77        let mut size = self.count;
78        for (i, next) in self.branch.iter().enumerate() {
79            if (size & 1) == 1 {
80                self.branch[i] = node;
81                return Ok(());
82            }
83            node = keccak256_hash(&[next.to_vec(), node.to_vec()].concat());
84            size /= 2;
85        }
86        panic!("unreachable code")
87    }
88
89    pub fn root_with_ctx(&self, zeroes: [[u8; HASH_LENGTH]; TREE_DEPTH]) -> StdResult<HexBinary> {
90        let idx = self.count;
91
92        Ok(zeroes
93            .iter()
94            .enumerate()
95            .fold(MerkleTree::zero()?.into(), |current, (i, zero)| {
96                let ith_bit = (idx >> i) & 1;
97                let next = self.branch[i].clone();
98                if ith_bit == 1 {
99                    keccak256_hash(&[next.to_vec(), current.to_vec()].concat())
100                } else {
101                    keccak256_hash(&[current.to_vec(), zero.to_vec()].concat())
102                }
103            }))
104    }
105
106    pub fn root(&self) -> StdResult<HexBinary> {
107        self.root_with_ctx(MerkleTree::zeroes()?)
108    }
109
110    pub fn branch_root(item: HexBinary, branch: [HexBinary; TREE_DEPTH], idx: u128) -> HexBinary {
111        branch
112            .into_iter()
113            .enumerate()
114            .fold(item, |current, (i, next)| match (idx >> i) & 1 {
115                1 => keccak256_hash(&[next.to_vec(), current.to_vec()].concat()),
116                _ => keccak256_hash(&[current.to_vec(), next.to_vec()].concat()),
117            })
118    }
119
120    pub fn zero() -> StdResult<[u8; HASH_LENGTH]> {
121        Ok(HexBinary::from_hex(ZERO_BYTES)?
122            .to_vec()
123            .try_into()
124            .expect("invalid length"))
125    }
126
127    pub fn zeroes() -> StdResult<[[u8; HASH_LENGTH]; TREE_DEPTH]> {
128        Ok(ZERO_HASHES
129            .into_iter()
130            .map(|v| {
131                Ok(HexBinary::from_hex(v)?
132                    .to_vec()
133                    .try_into()
134                    .expect("invalid hash"))
135            })
136            .collect::<StdResult<Vec<_>>>()?
137            .try_into()
138            .expect("invalid depth"))
139    }
140}
141
142#[cfg(test)]
143mod tests {
144    use super::*;
145
146    #[test]
147    fn test_default_merkle_tree() {
148        for (i, branch) in MerkleTree::default().branch.into_iter().enumerate() {
149            assert_eq!(branch.to_hex(), super::ZERO_HASHES[i]);
150        }
151    }
152
153    #[test]
154    fn test_compatibility() {
155        let digest: HexBinary = [
156            keccak256_hash("hello_world".as_bytes()).to_vec(),
157            keccak256_hash("world_hello".as_bytes()).to_vec(),
158        ]
159        .concat()
160        .into();
161
162        assert_eq!(
163            format!("0x{}", digest.to_hex()),
164            // abi.encodePacked(bytes32(keccak256("hello_world")), bytes32(keccak256("world_hello")));
165            "0x5b07e077a81ffc6b47435f65a8727bcc542bc6fc0f25a56210efb1a74b88a5ae5e3b3917b0a11fc9edfc594b3aabbc95167d176fcc17aa76c01d7bda956862cd",
166        );
167    }
168}
hpl_interface/types/merkle.rs

hpl_interface/types/
merkle.rs
