darkfi_sdk/monotree/
node.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2025 Dyne.org foundation
4 * Copyright (C) 2021 MONOLOG (Taeho Francis Lim and Jongwhan Lee) MIT License
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 super::{
21    bits::Bits,
22    utils::{bytes_to_int, nbytes_across},
23    BitsLen, HASH_LEN,
24};
25use crate::GenericResult;
26
27/// A type for describing components of `Node`: a real element of `Unit`
28/// or a virtual element `None`.
29pub type Cell<'a> = Option<Unit<'a>>;
30
31/// A component of `Node` consisting of `Hash` and `Bits`, which represents
32/// a joint of subtrees it has.
33#[derive(Clone, Debug, PartialEq)]
34pub struct Unit<'a> {
35    pub hash: &'a [u8],
36    pub bits: Bits<'a>,
37}
38
39/// The only component of `monotree`. In a big picture, `monotree` simply
40/// consists of structured `Node`s.
41///
42/// # Schematic
43/// There are two types of `Node` -- ___Soft node___ and ___Hard node___.
44/// * ___Hard___: A node that has two real cells as components. Two links to child nodes.
45/// * ___Soft___: A node that has only one real cell and it has only one link going out to child node.
46/// ```text
47///            Root
48///           /    \
49///         NodeA   NodeB
50///        /    \        \
51///    NodeC    LeafB    LeafC
52///     /
53///   LeafA
54/// ```
55/// Where NodeA is a _Hard node_, NodeB and NodeC are _Soft nodes_.
56///
57/// # Byte-Serialized View
58/// Numbers in parentheses refer to byte length.
59/// By default `HashLen = 32`, `BitsLen = 2`.
60///
61/// _SoftNode_ = `Cell` + `0x00`(1), where
62/// `Cell` = `hash`(`HASH_LEN`) + `path`(`< HASH_LEN`) + `range_start`(`BitsLen`) + `range_end`(`BitsLen`).
63/// `0x00` is an indicator for soft node.
64///
65/// _HardNode_ = `Cell_L` + `Cell_R` + `0x01`(1), where
66/// `Cell_L` = `hash_L`(`HASH_LEN`) + `path_L`(`< HASH_LEN`) + `range_L_start`(`BitsLen`) + `range_L_end`(`BitsLen`
67/// `Cell_R` = `path_R`(`< HASH_LEN`) _ `range_R_start`(`BitsLen`) + `range_R_end`(`BitsLen`) + `hash_R`(`HASH_LEN`).
68/// `0x01` is an indicator for hard node.
69///
70/// To make ***Merkle proof*** easier, we purposely placed the _hashes_ on outskirts of the serialized form.
71/// With only 1-bit information of left or right, provers can easily guess
72/// which side of the hash they hold should be appended for the next step.
73/// Refer to `verify_proof()` implementation regarding on this discussion.
74pub enum Node<'a> {
75    Soft(Cell<'a>),
76    Hard(Cell<'a>, Cell<'a>),
77}
78
79impl<'a> Node<'a> {
80    pub fn new(lc: Cell<'a>, rc: Cell<'a>) -> Self {
81        match (&lc, &rc) {
82            (&Some(_), &None) => Node::Soft(lc),
83            (&None, &Some(_)) => Node::Soft(rc),
84            (&Some(_), &Some(_)) => Node::Hard(lc, rc),
85            _ => unreachable!("Node::new()"),
86        }
87    }
88
89    /// Construct `Cell`s by deserializing bytes slice.
90    pub fn cells_from_bytes(bytes: &'a [u8], right: bool) -> GenericResult<(Cell<'a>, Cell<'a>)> {
91        match Node::from_bytes(bytes)? {
92            Node::Soft(cell) => Ok((cell, None)),
93            Node::Hard(lc, rc) => {
94                if right {
95                    Ok((rc, lc))
96                } else {
97                    Ok((lc, rc))
98                }
99            }
100        }
101    }
102
103    fn parse_bytes(bytes: &'a [u8], right: bool) -> GenericResult<(Cell<'a>, usize)> {
104        let len_bytes = bytes.len();
105        let len_bits = std::mem::size_of::<BitsLen>();
106        let offset_hash = if right { 0_usize } else { HASH_LEN };
107        let range_hash = if right { len_bytes - HASH_LEN..len_bytes } else { 0..HASH_LEN };
108        let start: BitsLen = bytes_to_int(&bytes[offset_hash..offset_hash + len_bits]);
109        let end: BitsLen = bytes_to_int(&bytes[offset_hash + len_bits..offset_hash + 2 * len_bits]);
110        let offset_bits = nbytes_across(start, end) as usize;
111
112        Ok((
113            Some(Unit {
114                hash: &bytes[range_hash],
115                bits: Bits {
116                    path: &bytes
117                        [offset_hash + 2 * len_bits..offset_hash + 2 * len_bits + offset_bits],
118                    range: start..end,
119                },
120            }),
121            offset_hash + 2 * len_bits + offset_bits,
122        ))
123    }
124
125    /// Construct `Node` by deserializing bytes slice.
126    pub fn from_bytes(bytes: &'a [u8]) -> GenericResult<Self> {
127        match bytes.last() {
128            Some(&0x00) => {
129                let (cell, _) = Node::parse_bytes(&bytes[..bytes.len() - 1], false)?;
130                Ok(Node::Soft(cell))
131            }
132            Some(&0x01) => {
133                let (lc, size) = Node::parse_bytes(bytes, false)?;
134                let (rc, _) = Node::parse_bytes(&bytes[size..bytes.len() - 1], true)?;
135                Ok(Node::Hard(lc, rc))
136            }
137            _ => unreachable!("Node::from_bytes()"),
138        }
139    }
140
141    /// Serialize `Node` into bytes.
142    pub fn to_bytes(&self) -> GenericResult<Vec<u8>> {
143        match self {
144            Node::Soft(Some(unit)) => Ok([unit.hash, &unit.bits.to_bytes()?, &[0x00]].concat()),
145            Node::Hard(Some(lu), Some(ru)) => {
146                let (lu, ru) = if ru.bits.first() { (lu, ru) } else { (ru, lu) };
147                Ok([lu.hash, &lu.bits.to_bytes()?, &ru.bits.to_bytes()?, ru.hash, &[0x01]].concat())
148            }
149            _ => unreachable!("node.to_bytes()"),
150        }
151    }
152}
darkfi_sdk/monotree/node.rs

darkfi_sdk/monotree/
node.rs
