darkfi/blockchain/monero/
merkle_tree_parameters.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2026 Dyne.org foundation
4 * Copyright (C) 2021 The Tari Project (BSD-3)
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU Affero General Public License as
8 * published by the Free Software Foundation, either version 3 of the
9 * License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU Affero General Public License for more details.
15 *
16 * You should have received a copy of the GNU Affero General Public License
17 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
18 */
19
20use monero::VarInt;
21
22use crate::{Error, Result};
23
24/// Based on <https://github.com/SChernykh/p2pool/blob/master/docs/MERGE_MINING.MD#merge-mining-tx_extra-tag-format>
25#[derive(Debug, Clone, PartialEq)]
26pub struct MerkleTreeParameters {
27    number_of_chains: u8,
28    aux_nonce: u32,
29}
30
31impl MerkleTreeParameters {
32    pub fn new(number_of_chains: u8, aux_nonce: u32) -> Result<Self> {
33        if number_of_chains == 0u8 {
34            return Err(Error::MoneroNumberOfChainZero)
35        }
36
37        Ok(Self { number_of_chains, aux_nonce })
38    }
39
40    pub fn from_varint(merkle_tree_varint: VarInt) -> Self {
41        let bits = get_decode_bits(merkle_tree_varint.0);
42
43        let number_of_chains = get_aux_chain_count(merkle_tree_varint.0, bits);
44        let aux_nonce = get_aux_nonce(merkle_tree_varint.0, bits);
45
46        Self { number_of_chains, aux_nonce }
47    }
48
49    pub fn to_varint(&self) -> VarInt {
50        // 1 is encoded as 0
51        let num = self.number_of_chains.saturating_sub(1);
52        let size = u8::try_from(num.leading_zeros())
53            .expect("This can't fail, u8 can only have 8 leading 0s which will fit in 255");
54        // size must be >0, so saturating sub should be safe.
55        let mut size_bits = encode_bits(7u8.saturating_sub(size));
56        let mut n_bits = encode_aux_chain_count(self.number_of_chains);
57        let mut nonce_bits = encode_aux_nonce(self.aux_nonce);
58        // This won't underflow as max size will be size_bits(3) + n_bits(8) + nonce_bits(32) = 43
59        let mut zero_bits = vec![0; 64 - size_bits.len() - n_bits.len() - nonce_bits.len()];
60        zero_bits.append(&mut nonce_bits);
61        zero_bits.append(&mut n_bits);
62        zero_bits.append(&mut size_bits);
63
64        let num: u64 = zero_bits.iter().fold(0, |result, &bit| (result << 1) ^ u64::from(bit));
65        VarInt(num)
66    }
67
68    pub fn number_of_chains(&self) -> u8 {
69        self.number_of_chains
70    }
71
72    pub fn aux_nonce(&self) -> u32 {
73        self.aux_nonce
74    }
75}
76
77fn get_decode_bits(num: u64) -> u8 {
78    let bits_num: Vec<u8> = (0..=2).rev().map(|n| ((num >> n) & 1) as u8).collect();
79    bits_num.iter().fold(0, |result, &bit| (result << 1) ^ bit)
80}
81
82fn encode_bits(num: u8) -> Vec<u8> {
83    (0..=2).rev().map(|n| (num >> n) & 1).collect()
84}
85
86fn get_aux_chain_count(num: u64, bits: u8) -> u8 {
87    let end = 3 + bits;
88    let bits_num: Vec<u8> = (3..=end).rev().map(|n| ((num >> n) & 1) as u8).collect();
89    (bits_num.iter().fold(0, |result, &bit| (result << 1) ^ bit)).saturating_add(1)
90}
91
92fn encode_aux_chain_count(num: u8) -> Vec<u8> {
93    // 1 is encoded as 0
94    let num = num.saturating_sub(1);
95    if num == 0 {
96        return vec![0]
97    }
98
99    let size = u8::try_from(num.leading_zeros())
100        .expect("This can't fail, u8 can only have 8 leading 0s which will fit in 255");
101    let bit_length = 8 - size;
102    (0..bit_length).rev().map(|n| (num >> n) & 1).collect()
103}
104
105fn get_aux_nonce(num: u64, bits: u8) -> u32 {
106    // 0,1,2 is storing bits, then amount of bits, then start at next bit to read
107    let start = 3 + bits + 1;
108    let end = start + 32;
109    let bits_num: Vec<u32> = (start..=end).rev().map(|n| ((num >> n) & 1) as u32).collect();
110    bits_num.iter().fold(0, |result, &bit| (result << 1) ^ bit)
111}
112
113fn encode_aux_nonce(num: u32) -> Vec<u8> {
114    (0..=31).rev().map(|n| ((num >> n) & 1) as u8).collect()
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120
121    #[test]
122    fn test_en_decode_bits() {
123        let num = 24u64; // 11000
124        let bit = get_decode_bits(num);
125        assert_eq!(bit, 0);
126        let bits = encode_bits(0);
127        let arr = vec![0, 0, 0];
128        assert_eq!(bits, arr);
129
130        let num = 0b1100000000000000000000000000000000000000000000000000000000000101;
131        let bit = get_decode_bits(num);
132        assert_eq!(bit, 5);
133        let bits = encode_bits(5);
134        let arr = vec![1, 0, 1];
135        assert_eq!(bits, arr);
136
137        let num = 0b0100000000000000000000000000000000000000000000000000000000000110;
138        let bit = get_decode_bits(num);
139        assert_eq!(bit, 6);
140        let bits = encode_bits(6);
141        let arr = vec![1, 1, 0];
142        assert_eq!(bits, arr);
143
144        let num = 0b1010000000000000000000000000000000000000000000000000000000000111;
145        let bit = get_decode_bits(num);
146        assert_eq!(bit, 7);
147        let bits = encode_bits(7);
148        let arr = vec![1, 1, 1];
149        assert_eq!(bits, arr);
150
151        let num = 0b0011000000000000000000000000000000000000000000000000000000000001;
152        let bit = get_decode_bits(num);
153        assert_eq!(bit, 1);
154        let bits = encode_bits(1);
155        let arr = vec![0, 0, 1];
156        assert_eq!(bits, arr);
157    }
158
159    #[test]
160    fn test_get_decode_aux_chain() {
161        let num = 24u64; // 11000
162        let aux_number = get_aux_chain_count(num, 0);
163        assert_eq!(aux_number, 2);
164        let bits = encode_aux_chain_count(2);
165        let arr: Vec<u8> = vec![1];
166        assert_eq!(bits, arr);
167
168        let num = 0b1101111111100000000000000000000000000000000000000000011111110000;
169        let aux_number = get_aux_chain_count(num, 7);
170        assert_eq!(aux_number, 255);
171        let bits = encode_aux_chain_count(255);
172        let arr = vec![1, 1, 1, 1, 1, 1, 1, 0];
173        assert_eq!(bits, arr);
174
175        let num = 0b1100000000100000000000000000000000000000000000000000000000101101;
176        let aux_number = get_aux_chain_count(num, 3);
177        assert_eq!(aux_number, 6);
178        let bits = encode_aux_chain_count(6);
179        let arr = vec![1, 0, 1];
180        assert_eq!(bits, arr);
181
182        let num = 0b1100000000000000000000000000000000000000000000000000000000011101;
183        let aux_number = get_aux_chain_count(num, 2);
184        assert_eq!(aux_number, 4);
185        let bits = encode_aux_chain_count(4);
186        let arr = vec![1, 1];
187        assert_eq!(bits, arr);
188
189        let num = 0b1100111000000000000000000000000000000000000000000000000000000101;
190        let aux_number = get_aux_chain_count(num, 1);
191        assert_eq!(aux_number, 1);
192        let bits = encode_aux_chain_count(1);
193        let arr = vec![0];
194        assert_eq!(bits, arr);
195
196        let num = 0b1100000100000000000000000000000000000000000000000000000000111101;
197        let aux_number = get_aux_chain_count(num, 3);
198        assert_eq!(aux_number, 8);
199        let bits = encode_aux_chain_count(8);
200        let arr = vec![1, 1, 1];
201        assert_eq!(bits, arr);
202
203        let num = 0b1100000001000000000000000000000000000000000000000000000001111101;
204        let aux_number = get_aux_chain_count(num, 4);
205        assert_eq!(aux_number, 16);
206        let bits = encode_aux_chain_count(16);
207        let arr = vec![1, 1, 1, 1];
208        assert_eq!(bits, arr);
209
210        let num = 0b1100000010000000000000000000000000000000000000000000001111000101;
211        let aux_number = get_aux_chain_count(num, 7);
212        assert_eq!(aux_number, 121);
213        let bits = encode_aux_chain_count(121);
214        let arr = vec![1, 1, 1, 1, 0, 0, 0];
215        assert_eq!(bits, arr);
216
217        let num = 0b1100000100000000000000000000000000000000000000000000001100000101;
218        let aux_number = get_aux_chain_count(num, 7);
219        assert_eq!(aux_number, 97);
220        let bits = encode_aux_chain_count(97);
221        let arr = vec![1, 1, 0, 0, 0, 0, 0];
222        assert_eq!(bits, arr);
223
224        let num = 0b1111000110000000000000000000000000000000000000000000000111000101;
225        let aux_number = get_aux_chain_count(num, 6);
226        assert_eq!(aux_number, 57);
227        let bits = encode_aux_chain_count(57);
228        let arr = vec![1, 1, 1, 0, 0, 0];
229        assert_eq!(bits, arr);
230    }
231
232    #[test]
233    #[allow(clippy::too_many_lines)]
234    fn test_get_decode_aux_nonce() {
235        let num = 24u64; // 11000
236        let aux_number = get_aux_nonce(num, 0);
237        assert_eq!(aux_number, 1);
238        let bits = encode_aux_nonce(1);
239        let arr = vec![
240            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
241            0, 0, 1,
242        ];
243        assert_eq!(bits, arr);
244
245        let num = 0b1100000000110000000000000000000000000000000000000000100000000101;
246        let aux_number = get_aux_nonce(num, 7);
247        assert_eq!(aux_number, 1);
248        let bits = encode_aux_nonce(1);
249        let arr = vec![
250            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
251            0, 0, 1,
252        ];
253        assert_eq!(bits, arr);
254
255        let num = 0b1100000000110000000000000000000000000000000000000000010000000101;
256        let aux_number = get_aux_nonce(num, 6);
257        assert_eq!(aux_number, 1);
258        let bits = encode_aux_nonce(1);
259        let arr = vec![
260            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
261            0, 0, 1,
262        ];
263        assert_eq!(bits, arr);
264
265        let num = 0b1100000000110000000000000000000000000000000000000000001000000101;
266        let aux_number = get_aux_nonce(num, 5);
267        assert_eq!(aux_number, 1);
268        let bits = encode_aux_nonce(1);
269        let arr = vec![
270            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
271            0, 0, 1,
272        ];
273        assert_eq!(bits, arr);
274
275        let num = 0b1100000000110000000000000000000000000000000000000000000100000101;
276        let aux_number = get_aux_nonce(num, 4);
277        assert_eq!(aux_number, 1);
278        let bits = encode_aux_nonce(1);
279        let arr = vec![
280            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
281            0, 0, 1,
282        ];
283        assert_eq!(bits, arr);
284
285        let num = 0b1100000000110000000000000000000000000000000000000000000010000101;
286        let aux_number = get_aux_nonce(num, 3);
287        assert_eq!(aux_number, 1);
288        let bits = encode_aux_nonce(1);
289        let arr = vec![
290            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
291            0, 0, 1,
292        ];
293        assert_eq!(bits, arr);
294
295        let num = 0b1100000000110000000000000000000000000000000000000000000001000101;
296        let aux_number = get_aux_nonce(num, 2);
297        assert_eq!(aux_number, 1);
298        let bits = encode_aux_nonce(1);
299        let arr = vec![
300            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
301            0, 0, 1,
302        ];
303        assert_eq!(bits, arr);
304
305        let num = 0b1100000000110000000000000000000000000000000000000000000000100101;
306        let aux_number = get_aux_nonce(num, 1);
307        assert_eq!(aux_number, 1);
308        let bits = encode_aux_nonce(1);
309        let arr = vec![
310            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
311            0, 0, 1,
312        ];
313        assert_eq!(bits, arr);
314
315        let num = 0b1100000000110000000000000000000000000000000000000000000000010101;
316        let aux_number = get_aux_nonce(num, 0);
317        assert_eq!(aux_number, 1);
318        let bits = encode_aux_nonce(1);
319        let arr = vec![
320            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
321            0, 0, 1,
322        ];
323        assert_eq!(bits, arr);
324
325        let num = 0b1100000000110000000000000000000000000000000000000000010000000101;
326        let aux_number = get_aux_nonce(num, 7);
327        assert_eq!(aux_number, 0);
328        let bits = encode_aux_nonce(0);
329        let arr = vec![
330            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
331            0, 0, 0,
332        ];
333        assert_eq!(bits, arr);
334
335        let num = 0b1100000000110000000001111111111111111111111111111111110000000101;
336        let aux_number = get_aux_nonce(num, 7);
337        assert_eq!(aux_number, u32::MAX);
338        let bits = encode_aux_nonce(u32::MAX);
339        let arr = vec![
340            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
341            1, 1, 1,
342        ];
343        assert_eq!(bits, arr);
344
345        let num = 0b1100000000110000000001111111111100011111111111111111110000000101;
346        let aux_number = get_aux_nonce(num, 7);
347        assert_eq!(aux_number, 4293132287);
348        let bits = encode_aux_nonce(4293132287);
349        let arr = vec![
350            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
351            1, 1, 1,
352        ];
353        assert_eq!(bits, arr);
354
355        let num = 0b1100000000110000000001010101010101010101010101010101010000000101;
356        let aux_number = get_aux_nonce(num, 7);
357        assert_eq!(aux_number, 2863311530);
358        let bits = encode_aux_nonce(2863311530);
359        let arr = vec![
360            1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
361            0, 1, 0,
362        ];
363        assert_eq!(bits, arr);
364
365        let num = 0b110000000011000000000000000000000000011110011110111010000000101;
366        let aux_number = get_aux_nonce(num, 7);
367        assert_eq!(aux_number, 31214);
368        let bits = encode_aux_nonce(31214);
369        let arr = vec![
370            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1,
371            1, 1, 0,
372        ];
373        assert_eq!(bits, arr);
374    }
375
376    #[test]
377    fn merkle_complete() {
378        let num = VarInt(24);
379        let merkle_tree_params = MerkleTreeParameters::from_varint(num);
380        assert_eq!(merkle_tree_params.aux_nonce, 1);
381        assert_eq!(merkle_tree_params.number_of_chains, 2);
382
383        let ser_num = merkle_tree_params.to_varint();
384        assert_eq!(ser_num, VarInt(24));
385    }
386}
darkfi/blockchain/monero/merkle_tree_parameters.rs

darkfi/blockchain/monero/
merkle_tree_parameters.rs
