1#![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#[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#[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 pub protocol_id: ProtocolId,
66 pub expected: u32,
68 pub actual: u32,
70 pub width: u32,
72}
73
74#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug, Display, Error, From)]
76pub enum MergeError {
77 #[from]
81 #[display(inner)]
82 InvalidProof(InvalidProof),
83
84 #[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 base_root: Commitment,
92 merged_root: Commitment,
94 },
95}
96
97#[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 ConcealedNode {
109 depth: u5,
111 hash: MerkleHash,
113 },
114 CommitmentLeaf {
116 protocol_id: ProtocolId,
118 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#[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 depth: u5,
164
165 cofactor: u16,
168
169 merkle_root: MerkleHash,
171}
172
173impl Conceal for MerkleConcealed {
174 type Concealed = Self;
175
176 fn conceal(&self) -> Self::Concealed { *self }
177}
178
179#[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 #[getter(as_copy)]
189 method: Method,
190
191 #[getter(as_copy)]
193 depth: u5,
194
195 #[getter(as_copy)]
198 cofactor: u16,
199
200 #[getter(skip)]
202 cross_section: NonEmptyVec<TreeNode, U32MAX>,
203
204 #[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 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 pub fn conceal_other(&mut self, protocol: ProtocolId) -> Result<(), LeafNotKnown> {
326 self.conceal_except([protocol])?;
327 Ok(())
328 }
329
330 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 for node in &mut self.cross_section {
355 match node {
356 TreeNode::ConcealedNode { .. } => {
357 }
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 (
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 (
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 (TreeNode::CommitmentLeaf { .. }, Some(TreeNode::CommitmentLeaf { .. })) => {
423 offset += 2;
424 pos += 1;
425 }
426 (
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 (
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 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 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 (false, false) => {}
502 _ => 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 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 pub fn to_merkle_proof(&self, protocol_id: ProtocolId) -> Result<MerkleProof, LeafNotKnown> {
616 self.clone().into_merkle_proof(protocol_id)
617 }
618
619 pub fn protocol_id_pos(&self, protocol_id: ProtocolId) -> u32 {
621 protocol_id_pos(protocol_id, self.cofactor, self.depth)
622 }
623
624 pub fn width_limit(&self) -> u32 { 2u32.pow(self.depth.to_u8() as u32) }
626
627 pub fn factored_width(&self) -> u32 { self.width_limit() - self.cofactor as u32 }
630
631 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 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 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 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#[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 #[getter(as_copy)]
705 method: Method,
706
707 #[getter(as_copy)]
712 pos: u32,
713
714 #[getter(as_copy)]
716 cofactor: u16,
717
718 #[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 pub fn depth(&self) -> u5 { u5::with(self.path.len() as u8) }
732
733 pub fn width_limit(&self) -> u32 { 2u32.pow(self.depth().to_u8() as u32) }
735
736 pub fn factored_width(&self) -> u32 { self.width_limit() - self.cofactor as u32 }
739
740 pub fn into_path(self) -> Confined<Vec<MerkleHash>, 0, 32> { self.path }
742
743 pub fn to_path(&self) -> Confined<Vec<MerkleHash>, 0, 32> { self.path.clone() }
745
746 pub fn as_path(&self) -> &[MerkleHash] { &self.path }
748
749 pub fn merkle_root(&self) -> Option<MerkleHash> { self.path.first().copied() }
753
754 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 assert_eq!(Some(tree.entropy), block.entropy);
783 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}