commit_verify/mpc/
block.rs

1// Client-side-validation foundation libraries.
2//
3// SPDX-License-Identifier: Apache-2.0
4//
5// Designed in 2019-2025 by Dr Maxim Orlovsky <orlovsky@lnp-bp.org>
6// Written in 2024-2025 by Dr Maxim Orlovsky <orlovsky@lnp-bp.org>
7//
8// Copyright (C) 2019-2024 LNP/BP Standards Association, Switzerland.
9// Copyright (C) 2024-2025 LNP/BP Laboratories,
10//                         Institute for Distributed and Cognitive Systems
11// (InDCS), Switzerland. Copyright (C) 2019-2025 Dr Maxim Orlovsky.
12// All rights under the above copyrights are reserved.
13//
14// Licensed under the Apache License, Version 2.0 (the "License"); you may not
15// use this file except in compliance with the License. You may obtain a copy of
16// the License at
17//
18//        http://www.apache.org/licenses/LICENSE-2.0
19//
20// Unless required by applicable law or agreed to in writing, software
21// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
22// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
23// License for the specific language governing permissions and limitations under
24// the License.
25
26#![allow(unused_braces)]
27
28use std::cmp::Ordering;
29use std::collections::{BTreeMap, BTreeSet};
30
31use amplify::confinement::{Confined, NonEmptyVec, U32 as U32MAX};
32use amplify::num::u5;
33use strict_encoding::{StrictDeserialize, StrictDumb, StrictEncode, StrictSerialize};
34
35use crate::id::CommitId;
36use crate::merkle::{MerkleBuoy, MerkleHash};
37use crate::mpc::atoms::Leaf;
38use crate::mpc::tree::protocol_id_pos;
39use crate::mpc::{Commitment, MerkleTree, Message, MessageMap, Method, Proof, ProtocolId};
40use crate::{Conceal, LIB_NAME_COMMIT_VERIFY};
41
42/// Error indicating that a given [`ProtocolId`] does not participate in a
43/// specific MPC Merkle tree.
44#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug, Display, Error)]
45#[display(
46    "commitment under protocol id {0} is absent from the known part of a given LNPBP-4 Merkle \
47     block"
48)]
49pub struct LeafNotKnown(pub ProtocolId);
50
51/// Error constructing MPC Merkle tree due to invalid [`MerkleProof`] data.
52///
53/// # Returned by
54///
55/// - [`MerkleBlock::with`]
56/// - [`MerkleProof::convolve`]
57#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug, Display, Error)]
58#[display(
59    "the provided merkle proof protocol id {protocol_id} position {actual} doesn't match the \
60     expected position {expected} within the tree of width {width}."
61)]
62#[cfg_attr(feature = "serde", derive(Serialize, Deserialize), serde(rename_all = "camelCase"))]
63pub struct InvalidProof {
64    /// The protocol id which position is mismatched.
65    pub protocol_id: ProtocolId,
66    /// The position in which the protocol should appear.
67    pub expected: u32,
68    /// The position in which the protocol appears in the proof.
69    pub actual: u32,
70    /// The width of the MPC Merkle tree.
71    pub width: u32,
72}
73
74/// Errors happening during the [`MerkleBlock::merge_reveal_path`] procedure.
75#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug, Display, Error, From)]
76pub enum MergeError {
77    /// Invalid [`MerkleProof`] data.
78    ///
79    /// See [`InvalidProof`] inner error type for the details.
80    #[from]
81    #[display(inner)]
82    InvalidProof(InvalidProof),
83
84    /// Attempt to merge two unrelated [`MerkleBlock`]s.
85    #[display(
86        "attempt to merge two unrelated LNPBP-4 blocks with different Merkle roots (base \
87         {base_root}, merged-in {merged_root})."
88    )]
89    UnrelatedBlocks {
90        /// The merkle root of the first merged MPC block.
91        base_root: Commitment,
92        /// The merkle root of the second merged MPC block.
93        merged_root: Commitment,
94    },
95}
96
97/// LNPBP-4 Merkle tree node.
98#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
99#[derive(StrictType, StrictDumb, StrictEncode, StrictDecode)]
100#[strict_type(
101    lib = LIB_NAME_COMMIT_VERIFY,
102    tags = order,
103    dumb = { TreeNode::ConcealedNode { depth: u5::ZERO, hash: [0u8; 32].into() } }
104)]
105#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
106enum TreeNode {
107    /// A node of the tree with concealed leaf or tree branch information.
108    ConcealedNode {
109        /// Depth of the node.
110        depth: u5,
111        /// Node hash.
112        hash: MerkleHash,
113    },
114    /// A tree leaf storing specific commitment under given protocol.
115    CommitmentLeaf {
116        /// Protocol under which the commitment is created.
117        protocol_id: ProtocolId,
118        /// Message this leaf commits to.
119        message: Message,
120    },
121}
122
123impl TreeNode {
124    fn with(hash1: MerkleHash, hash2: MerkleHash, depth: u5, width: u32) -> TreeNode {
125        TreeNode::ConcealedNode {
126            depth,
127            hash: MerkleHash::branches(depth, width, hash1, hash2),
128        }
129    }
130
131    pub fn depth(&self) -> Option<u5> {
132        match self {
133            TreeNode::ConcealedNode { depth, .. } => Some(*depth),
134            TreeNode::CommitmentLeaf { .. } => None,
135        }
136    }
137
138    pub fn depth_or(&self, tree_depth: u5) -> u5 { self.depth().unwrap_or(tree_depth) }
139
140    pub fn is_leaf(&self) -> bool { matches!(self, TreeNode::CommitmentLeaf { .. }) }
141
142    pub fn to_merkle_node(self) -> MerkleHash {
143        match self {
144            TreeNode::ConcealedNode { hash, .. } => hash,
145            TreeNode::CommitmentLeaf {
146                protocol_id,
147                message,
148            } => Leaf::inhabited(protocol_id, message).commit_id(),
149        }
150    }
151}
152
153/// A fully concealed MPC Merkle tree, consisting just of the Merkle root and
154/// information about its original depth and used cofactor.
155#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
156#[derive(StrictType, StrictDumb, StrictEncode, StrictDecode)]
157#[strict_type(lib = LIB_NAME_COMMIT_VERIFY)]
158#[derive(CommitEncode)]
159#[commit_encode(crate = crate, strategy = strict, id = Commitment)]
160#[cfg_attr(feature = "serde", derive(Serialize, Deserialize), serde(rename_all = "camelCase"))]
161pub struct MerkleConcealed {
162    /// Tree depth (up to 16).
163    depth: u5,
164
165    /// Cofactor is used as an additive to the modulo divisor to improve packing
166    /// of protocols inside a tree of a given depth.
167    cofactor: u16,
168
169    /// The root of the Merkle Tree
170    merkle_root: MerkleHash,
171}
172
173impl Conceal for MerkleConcealed {
174    type Concealed = Self;
175
176    fn conceal(&self) -> Self::Concealed { *self }
177}
178
179/// Partially-concealed merkle tree data.
180#[derive(Getters, Clone, PartialEq, Eq, Hash, Debug)]
181#[derive(StrictType, StrictEncode, StrictDecode)]
182#[strict_type(lib = LIB_NAME_COMMIT_VERIFY)]
183#[derive(CommitEncode)]
184#[commit_encode(crate = crate, strategy = conceal, id = Commitment)]
185#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
186pub struct MerkleBlock {
187    /// Method used to construct MPC proof (hash function, merklization).
188    #[getter(as_copy)]
189    method: Method,
190
191    /// Tree depth (up to 16).
192    #[getter(as_copy)]
193    depth: u5,
194
195    /// Cofactor is used as an additive to the modulo divisor to improve packing
196    /// of protocols inside a tree of a given depth.
197    #[getter(as_copy)]
198    cofactor: u16,
199
200    /// Tree cross-section.
201    #[getter(skip)]
202    cross_section: NonEmptyVec<TreeNode, U32MAX>,
203
204    /// Entropy used for placeholders. May be unknown if the message is provided
205    /// by a third party, wishing to conceal that information.
206    #[getter(as_copy)]
207    entropy: Option<u64>,
208}
209
210impl StrictDumb for MerkleBlock {
211    fn strict_dumb() -> Self {
212        MerkleBlock {
213            method: Method::Sha256t,
214            depth: u5::ONE,
215            cofactor: 0,
216            cross_section: NonEmptyVec::with(TreeNode::strict_dumb()),
217            entropy: Some(8845),
218        }
219    }
220}
221
222impl StrictSerialize for MerkleBlock {}
223impl StrictDeserialize for MerkleBlock {}
224
225impl Proof for MerkleBlock {
226    fn matches(&self, other: &Self) -> bool { self.commit_id() == other.commit_id() }
227}
228
229impl From<&MerkleTree> for MerkleBlock {
230    fn from(tree: &MerkleTree) -> Self {
231        let map = &tree.map;
232
233        let iter = (0..tree.width_limit()).map(|pos| {
234            map.get(&pos)
235                .map(|(protocol_id, message)| TreeNode::CommitmentLeaf {
236                    protocol_id: *protocol_id,
237                    message: *message,
238                })
239                .unwrap_or_else(|| TreeNode::ConcealedNode {
240                    depth: tree.depth,
241                    hash: Leaf::entropy(tree.entropy, pos).commit_id(),
242                })
243        });
244        let cross_section =
245            NonEmptyVec::try_from_iter(iter).expect("tree width guarantees are broken");
246
247        MerkleBlock {
248            method: tree.method,
249            depth: tree.depth,
250            cofactor: tree.cofactor,
251            cross_section,
252            entropy: Some(tree.entropy),
253        }
254    }
255}
256
257impl From<MerkleTree> for MerkleBlock {
258    fn from(tree: MerkleTree) -> Self { MerkleBlock::from(&tree) }
259}
260
261impl MerkleBlock {
262    /// Constructs merkle block from a merkle proof
263    pub fn with(
264        proof: &MerkleProof,
265        protocol_id: ProtocolId,
266        message: Message,
267    ) -> Result<Self, InvalidProof> {
268        let path = proof.as_path();
269        let mut pos = proof.pos;
270        let mut width_limit = proof.width_limit();
271
272        let expected = protocol_id_pos(protocol_id, proof.cofactor, proof.depth());
273        if expected != pos {
274            return Err(InvalidProof {
275                protocol_id,
276                expected,
277                actual: pos,
278                width: width_limit,
279            });
280        }
281
282        let mut dir = Vec::with_capacity(path.len());
283        let mut rev = Vec::with_capacity(path.len());
284        for (depth, hash) in path.iter().enumerate() {
285            let list = if pos >= width_limit / 2 {
286                pos -= width_limit / 2;
287                &mut dir
288            } else {
289                &mut rev
290            };
291            list.push(TreeNode::ConcealedNode {
292                depth: u5::with(depth as u8) + 1,
293                hash: *hash,
294            });
295            width_limit /= 2;
296        }
297
298        let mut cross_section = Vec::with_capacity(path.len() + 1);
299        cross_section.extend(dir);
300        cross_section.push(TreeNode::CommitmentLeaf {
301            protocol_id,
302            message,
303        });
304        cross_section.extend(rev.into_iter().rev());
305        let cross_section =
306            NonEmptyVec::try_from(cross_section).expect("tree width guarantees are broken");
307
308        Ok(MerkleBlock {
309            method: proof.method,
310            depth: u5::with(path.len() as u8),
311            cofactor: proof.cofactor,
312            cross_section,
313            entropy: None,
314        })
315    }
316
317    /// Conceals all commitments in the block except for the commitment under
318    /// given `protocol_id`. Also removes information about the entropy value
319    /// used.
320    ///
321    /// # Error
322    ///
323    /// If leaf with the given `protocol_id` is not found (absent or already
324    /// concealed), errors with [`LeafNotKnown`] error.
325    pub fn conceal_other(&mut self, protocol: ProtocolId) -> Result<(), LeafNotKnown> {
326        self.conceal_except([protocol])?;
327        Ok(())
328    }
329
330    /// Conceals all commitments in the block except for the commitment under
331    /// given `protocol_id`s. Also removes information about the entropy value
332    /// used.
333    ///
334    /// # Returns
335    ///
336    /// Number of concealed nodes.
337    ///
338    /// # Error
339    ///
340    /// If leaf with the given `protocol_id` is not found (absent or already
341    /// concealed), errors with [`LeafNotKnown`] error.
342    pub fn conceal_except(
343        &mut self,
344        protocols: impl AsRef<[ProtocolId]>,
345    ) -> Result<usize, LeafNotKnown> {
346        let protocols = protocols.as_ref();
347
348        let mut count = 0usize;
349        let mut not_found = protocols.iter().copied().collect::<BTreeSet<_>>();
350
351        self.entropy = None;
352
353        // Conceal all leafs except of one
354        for node in &mut self.cross_section {
355            match node {
356                TreeNode::ConcealedNode { .. } => {
357                    // Do nothing
358                }
359                TreeNode::CommitmentLeaf { protocol_id: p, .. } if protocols.contains(p) => {
360                    not_found.remove(p);
361                }
362                TreeNode::CommitmentLeaf { .. } => {
363                    count += 1;
364                    *node = TreeNode::ConcealedNode {
365                        depth: self.depth,
366                        hash: node.to_merkle_node(),
367                    };
368                }
369            }
370        }
371
372        if let Some(protocol_id) = not_found.into_iter().next() {
373            return Err(LeafNotKnown(protocol_id));
374        }
375
376        loop {
377            debug_assert!(!self.cross_section.is_empty());
378            let prev_count = count;
379            let mut offset = 0u32;
380            let mut pos = 0usize;
381            let mut len = self.cross_section.len();
382            while pos < len {
383                let (n1, n2) = (self.cross_section[pos], self.cross_section.get(pos + 1).copied());
384                match (n1, n2) {
385                    // Two concealed nodes of the same depth: aggregate if they are on the same
386                    // branch, skip just one otherwise
387                    (
388                        TreeNode::ConcealedNode {
389                            depth: depth1,
390                            hash: hash1,
391                        },
392                        Some(TreeNode::ConcealedNode {
393                            depth: depth2,
394                            hash: hash2,
395                        }),
396                    ) if depth1 == depth2 => {
397                        let depth = depth1 - 1;
398                        let height = self.depth.to_u8() as u32 - depth.to_u8() as u32;
399                        let pow = 2u32.pow(height);
400                        if offset % pow != 0 {
401                            offset += 2u32.pow(self.depth.to_u8() as u32 - depth1.to_u8() as u32);
402                        } else {
403                            self.cross_section[pos] =
404                                TreeNode::with(hash1, hash2, depth, self.width_limit());
405                            self.cross_section
406                                .remove(pos + 1)
407                                .expect("we allow 0 elements");
408                            count += 1;
409                            offset += pow;
410                            len -= 1;
411                        }
412                    }
413                    // Two concealed nodes at different depth, or the last concealed node:
414                    // - we skip one of them and repeat
415                    (
416                        TreeNode::ConcealedNode { depth, .. },
417                        Some(TreeNode::ConcealedNode { .. }) | None,
418                    ) => {
419                        offset += 2u32.pow(self.depth.to_u8() as u32 - depth.to_u8() as u32);
420                    }
421                    // Two commitment leafs: skipping both
422                    (TreeNode::CommitmentLeaf { .. }, Some(TreeNode::CommitmentLeaf { .. })) => {
423                        offset += 2;
424                        pos += 1;
425                    }
426                    // Concealed node followed by a leaf: skipping both
427                    (
428                        TreeNode::ConcealedNode { depth, .. },
429                        Some(TreeNode::CommitmentLeaf { .. }),
430                    ) => {
431                        offset += 2u32.pow(self.depth.to_u8() as u32 - depth.to_u8() as u32);
432                        offset += 1;
433                        pos += 1;
434                    }
435                    // Leaf followed by a concealed node: skipping leaf only, repeating
436                    (
437                        TreeNode::CommitmentLeaf { .. },
438                        Some(TreeNode::ConcealedNode { .. }) | None,
439                    ) => {
440                        offset += 1;
441                    }
442                }
443                pos += 1;
444            }
445            if count == prev_count {
446                break;
447            }
448            debug_assert_eq!(offset, self.width_limit());
449        }
450
451        Ok(count)
452    }
453
454    /// Merges information from the given `proof` to the merkle block, revealing
455    /// the path related to te `commitment` to the message under the given
456    /// `protocol_id`.
457    pub fn merge_reveal_path(
458        &mut self,
459        proof: &MerkleProof,
460        protocol_id: ProtocolId,
461        message: Message,
462    ) -> Result<u16, MergeError> {
463        let block = MerkleBlock::with(proof, protocol_id, message)?;
464        self.merge_reveal(&block)
465    }
466
467    /// Merges two merkle blocks together, joining revealed information from
468    /// each one of them.
469    pub fn merge_reveal(&mut self, other: &MerkleBlock) -> Result<u16, MergeError> {
470        let orig = self.clone();
471        let base_root = self.commit_id();
472        let merged_root = other.commit_id();
473        if base_root != merged_root {
474            return Err(MergeError::UnrelatedBlocks {
475                base_root,
476                merged_root,
477            });
478        }
479
480        let mut cross_section =
481            Vec::with_capacity(self.cross_section.len() + other.cross_section.len());
482        let mut a = self.cross_section.iter().copied();
483        let mut b = other.cross_section.iter().copied();
484
485        let mut last_a = a.next();
486        let mut last_b = b.next();
487        while let (Some(n1), Some(n2)) = (last_a, last_b) {
488            let n1_depth = n1.depth_or(self.depth);
489            let n2_depth = n2.depth_or(self.depth);
490            match n1_depth.cmp(&n2_depth) {
491                Ordering::Equal if n1 == n2 => {
492                    cross_section.push(n1);
493                    last_a = a.next();
494                    last_b = b.next();
495                }
496                Ordering::Equal => {
497                    match (n1.is_leaf(), n2.is_leaf()) {
498                        (true, false) => cross_section.push(n1),
499                        (false, true) => cross_section.push(n2),
500                        // Nothing to do here, we are skipping both nodes
501                        (false, false) => {}
502                        // If two nodes are both leafs or concealed, but not
503                        // equal to each other it means out algorithm is broken
504                        _ => unreachable!(
505                            "two MerkleBlock's with equal commitment failed to merge.\nBlock #1: \
506                             {self:#?}\nBlock #2: {other:#?}\nFailed nodes:\n{n1:?}\n{n2:?}"
507                        ),
508                    }
509                    last_a = a.next();
510                    last_b = b.next();
511                }
512                Ordering::Less => {
513                    cross_section.push(n2);
514                    let mut buoy = MerkleBuoy::<u5>::new(n2_depth);
515                    let mut stop = false;
516                    last_b = None;
517                    cross_section.extend(b.by_ref().take_while(|n| {
518                        if stop {
519                            last_b = Some(*n);
520                            return false;
521                        }
522                        buoy.push(n.depth_or(self.depth));
523                        if buoy.level() <= n1_depth {
524                            stop = true
525                        }
526                        true
527                    }));
528                    last_a = a.next();
529                }
530                Ordering::Greater => {
531                    cross_section.push(n1);
532                    let mut buoy = MerkleBuoy::<u5>::new(n1_depth);
533                    let mut stop = false;
534                    last_a = None;
535                    cross_section.extend(a.by_ref().take_while(|n| {
536                        if stop {
537                            last_a = Some(*n);
538                            return false;
539                        }
540                        buoy.push(n.depth_or(self.depth));
541                        if buoy.level() <= n2_depth {
542                            stop = true
543                        }
544                        true
545                    }));
546                    last_b = b.next();
547                }
548            }
549        }
550        cross_section.extend(a);
551        cross_section.extend(b);
552
553        self.cross_section =
554            NonEmptyVec::try_from(cross_section).expect("tree width guarantees are broken");
555
556        assert_eq!(
557            self.cross_section
558                .iter()
559                .map(|n| self.depth.to_u8() - n.depth_or(self.depth).to_u8())
560                .map(|height| 2u32.pow(height as u32))
561                .sum::<u32>(),
562            self.width_limit(),
563            "LNPBP-4 merge-reveal procedure is broken; please report the below data to the LNP/BP \
564             Standards Association
565Original block: {orig:#?}
566Merged-in block: {other:#?}
567Failed merge: {self:#?}"
568        );
569        assert_eq!(
570            base_root,
571            self.commit_id(),
572            "LNPBP-4 merge-reveal procedure is broken; please report the below data to the LNP/BP \
573             Standards Association
574Original commitment id: {base_root}
575Changed commitment id: {}",
576            self.commit_id()
577        );
578
579        Ok(self.cross_section.len() as u16)
580    }
581
582    /// Converts the merkle block into a merkle proof for the inclusion of a
583    /// commitment under given `protocol_id`.
584    pub fn into_merkle_proof(
585        mut self,
586        protocol_id: ProtocolId,
587    ) -> Result<MerkleProof, LeafNotKnown> {
588        self.conceal_other(protocol_id)?;
589        let mut map = BTreeMap::<u5, MerkleHash>::new();
590        for node in &self.cross_section {
591            match node {
592                TreeNode::ConcealedNode { depth, hash } => {
593                    let inserted = map.insert(*depth, *hash).is_none();
594                    debug_assert!(inserted, "MerkleBlock conceal procedure is broken");
595                }
596                TreeNode::CommitmentLeaf { .. } => {}
597            }
598        }
599        debug_assert_eq!(
600            self.depth.to_u8() as usize,
601            map.len(),
602            "MerkleBlock conceal procedure is broken"
603        );
604        Ok(MerkleProof {
605            method: self.method,
606            pos: self.protocol_id_pos(protocol_id),
607            cofactor: self.cofactor,
608            path: Confined::try_from_iter(map.into_values())
609                .expect("tree width guarantees are broken"),
610        })
611    }
612
613    /// Constructs merkle proof for the inclusion of a commitment under the
614    /// given `protocol_id` for the current Merkle block.
615    pub fn to_merkle_proof(&self, protocol_id: ProtocolId) -> Result<MerkleProof, LeafNotKnown> {
616        self.clone().into_merkle_proof(protocol_id)
617    }
618
619    /// Computes position for a given `protocol_id` within the tree leaves.
620    pub fn protocol_id_pos(&self, protocol_id: ProtocolId) -> u32 {
621        protocol_id_pos(protocol_id, self.cofactor, self.depth)
622    }
623
624    /// Computes the maximum possible width of the merkle tree.
625    pub fn width_limit(&self) -> u32 { 2u32.pow(self.depth.to_u8() as u32) }
626
627    /// Computes the factored width of the merkle tree according to the formula
628    /// `2 ^ depth - cofactor`.
629    pub fn factored_width(&self) -> u32 { self.width_limit() - self.cofactor as u32 }
630
631    /// Get an iterator over the known protocol ids present in the MPC Merkle
632    /// block.
633    pub fn known_protocol_ids(&self) -> impl Iterator<Item = ProtocolId> + '_ {
634        self.cross_section.iter().filter_map(|item| match item {
635            TreeNode::ConcealedNode { .. } => None,
636            TreeNode::CommitmentLeaf { protocol_id, .. } => Some(*protocol_id),
637        })
638    }
639
640    /// Constructs [`MessageMap`] for revealed protocols and messages.
641    pub fn to_known_message_map(&self) -> MessageMap {
642        Confined::try_from_iter(
643            self.cross_section
644                .iter()
645                .copied()
646                .filter_map(|item| match item {
647                    TreeNode::ConcealedNode { .. } => None,
648                    TreeNode::CommitmentLeaf {
649                        protocol_id,
650                        message,
651                    } => Some((protocol_id, message)),
652                }),
653        )
654        .expect("same collection size")
655    }
656
657    /// Convert this MPC Merkle block into an iterator over items and proofs of
658    /// their inclusion.
659    pub fn into_known_proofs(self) -> impl Iterator<Item = (ProtocolId, MerkleProof)> {
660        self.known_protocol_ids()
661            .collect::<Vec<_>>()
662            .into_iter()
663            .map(move |id| {
664                let proof = self
665                    .to_merkle_proof(id)
666                    .expect("protocol ids must strictly match");
667                (id, proof)
668            })
669    }
670}
671
672impl Conceal for MerkleBlock {
673    type Concealed = MerkleConcealed;
674
675    /// Reduces merkle tree into merkle tree root.
676    fn conceal(&self) -> Self::Concealed {
677        let mut concealed = self.clone();
678        concealed
679            .conceal_except([])
680            .expect("broken internal MerkleBlock structure");
681        debug_assert_eq!(concealed.cross_section.len(), 1);
682        let Some(TreeNode::ConcealedNode {
683            depth: u5::ZERO,
684            hash,
685        }) = concealed.cross_section.first()
686        else {
687            panic!("broken MerkleBlock conceal procedure")
688        };
689        MerkleConcealed {
690            depth: self.depth,
691            cofactor: self.cofactor,
692            merkle_root: *hash,
693        }
694    }
695}
696
697/// A proof of the merkle commitment.
698#[derive(Getters, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
699#[derive(StrictType, StrictEncode, StrictDecode)]
700#[strict_type(lib = LIB_NAME_COMMIT_VERIFY)]
701#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
702pub struct MerkleProof {
703    /// Method used to construct MPC proof (hash function, merklization).
704    #[getter(as_copy)]
705    method: Method,
706
707    /// Position of the leaf in the tree.
708    ///
709    /// Used to determine chirality of the node hashing partners on each step
710    /// of the path.
711    #[getter(as_copy)]
712    pos: u32,
713
714    /// Cofactor used by the Merkle tree.
715    #[getter(as_copy)]
716    cofactor: u16,
717
718    /// Merkle proof path consisting of node hashing partners.
719    #[getter(skip)]
720    path: Confined<Vec<MerkleHash>, 0, 32>,
721}
722
723impl Proof for MerkleProof {
724    fn matches(&self, other: &Self) -> bool {
725        self.cofactor == other.cofactor && self.merkle_root() == other.merkle_root()
726    }
727}
728
729impl MerkleProof {
730    /// Computes the depth of the merkle tree.
731    pub fn depth(&self) -> u5 { u5::with(self.path.len() as u8) }
732
733    /// Computes the maximum width of the merkle tree.
734    pub fn width_limit(&self) -> u32 { 2u32.pow(self.depth().to_u8() as u32) }
735
736    /// Computes the factored width of the merkle tree according to the formula
737    /// `2 ^ depth - cofactor`.
738    pub fn factored_width(&self) -> u32 { self.width_limit() - self.cofactor as u32 }
739
740    /// Converts the proof into inner merkle path representation
741    pub fn into_path(self) -> Confined<Vec<MerkleHash>, 0, 32> { self.path }
742
743    /// Constructs the proof into inner merkle path representation
744    pub fn to_path(&self) -> Confined<Vec<MerkleHash>, 0, 32> { self.path.clone() }
745
746    /// Returns inner merkle path representation
747    pub fn as_path(&self) -> &[MerkleHash] { &self.path }
748
749    /// Returns the root of the merkle path.
750    ///
751    /// If the MPC proof contains only a single message returns None
752    pub fn merkle_root(&self) -> Option<MerkleHash> { self.path.first().copied() }
753
754    /// Convolves the proof with the `message` under the given `protocol_id`,
755    /// producing [`Commitment`].
756    pub fn convolve(
757        &self,
758        protocol_id: ProtocolId,
759        message: Message,
760    ) -> Result<Commitment, InvalidProof> {
761        let block = MerkleBlock::with(self, protocol_id, message)?;
762        Ok(block.commit_id())
763    }
764}
765
766#[cfg(test)]
767mod test {
768    #![cfg_attr(coverage_nightly, coverage(off))]
769
770    use super::*;
771    use crate::mpc::tree::test_helpers::{
772        make_det_messages, make_random_messages, make_random_tree,
773    };
774
775    #[test]
776    fn entropy() {
777        let msgs = make_random_messages(3);
778        let tree = make_random_tree(&msgs);
779        let mut block = MerkleBlock::from(&tree);
780
781        // Check we preserve entropy value
782        assert_eq!(Some(tree.entropy), block.entropy);
783        // Check if we remove entropy the commitment doesn't change
784        let cid1 = block.commit_id();
785        block.entropy = None;
786        let cid2 = block.commit_id();
787        assert_eq!(cid1, cid2);
788    }
789
790    #[test]
791    fn single_leaf_tree() {
792        let msgs = make_random_messages(1);
793        let tree = make_random_tree(&msgs);
794        let block = MerkleBlock::from(&tree);
795
796        let (pid, msg) = msgs.first_key_value().unwrap();
797        let leaf = Leaf::inhabited(*pid, *msg);
798        let cid1 = block.cross_section.first().unwrap().to_merkle_node();
799        let cid2 = leaf.commit_id();
800        assert_eq!(cid1, cid2);
801
802        assert_eq!(tree.conceal(), block.conceal());
803        assert_eq!(tree.root(), cid1);
804        assert_eq!(tree.commit_id(), block.commit_id())
805    }
806
807    #[test]
808    fn determin_tree() {
809        for size in 1..6 {
810            let msgs = make_det_messages(size);
811            let tree = make_random_tree(&msgs);
812            let block = MerkleBlock::from(&tree);
813
814            assert_eq!(tree.conceal(), block.conceal());
815            assert_eq!(tree.commit_id(), block.commit_id())
816        }
817    }
818
819    #[test]
820    fn sparse_tree() {
821        for size in 2..6 {
822            let msgs = make_random_messages(size);
823            let tree = make_random_tree(&msgs);
824            let block = MerkleBlock::from(&tree);
825
826            assert_eq!(tree.conceal(), block.conceal());
827            assert_eq!(tree.commit_id(), block.commit_id())
828        }
829    }
830
831    #[test]
832    fn merge_reveal() {
833        for size in 2..9 {
834            let msgs = make_random_messages(size);
835            let mpc_tree = make_random_tree(&msgs);
836            let mpc_block = MerkleBlock::from(mpc_tree.clone());
837
838            let proofs = msgs
839                .keys()
840                .map(|pid| mpc_block.to_merkle_proof(*pid).unwrap())
841                .collect::<Vec<_>>();
842
843            let mut iter = proofs.iter().zip(msgs.into_iter());
844            let (proof, (pid, msg)) = iter.next().unwrap();
845            let mut merged_block = MerkleBlock::with(proof, pid, msg).unwrap();
846            for (proof, (pid, msg)) in iter {
847                let block = MerkleBlock::with(proof, pid, msg).unwrap();
848                if let Err(err) = merged_block.merge_reveal(&block) {
849                    eprintln!("Error: {err}");
850                    eprintln!("Source tree: {mpc_tree:#?}");
851                    eprintln!("Source block: {mpc_block:#?}");
852                    eprintln!("Base block: {merged_block:#?}");
853                    eprintln!("Added proof: {proof:#?}");
854                    eprintln!("Added block: {block:#?}");
855                    panic!();
856                }
857            }
858
859            assert_eq!(merged_block.commit_id(), mpc_tree.commit_id());
860        }
861    }
862}