1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

use crate::{Commitment, Error, Index, Node, Result};
use itertools::Itertools;
use std::{collections::VecDeque, prelude::v1::*};
use zkp_error_utils::require;
use zkp_hash::{Hash, Hashable};

// Note: we can merge and split proofs. Based on indices we can
// compute which values are redundant.
#[derive(Clone)]
#[cfg_attr(feature = "std", derive(Debug))]
pub struct Proof {
    commitment: Commitment,
    indices:    Vec<usize>,
    hashes:     Vec<Hash>,
}

impl Proof {
    pub fn from_hashes(
        commitment: &Commitment,
        indices: &[usize],
        hashes: &[Hash],
    ) -> Result<Self> {
        // Validate indices using `sort_indices`
        let _ = commitment.sort_indices(indices)?;
        require!(
            hashes.len() == commitment.proof_size(indices)?,
            Error::NotEnoughHashes
        );
        Ok(Self {
            commitment: commitment.clone(),
            indices:    indices.to_vec(),
            hashes:     hashes.to_vec(),
        })
    }

    pub fn hashes(&self) -> &[Hash] {
        &self.hashes
    }

    pub fn verify<Leaf: Hashable>(&self, leafs: &[(usize, Leaf)]) -> Result<()> {
        // TODO: Pass leafs by reference?
        // TODO: Check if the indices line up.

        // Construct the leaf nodes
        let mut nodes = leafs
            .iter()
            .map(|(index, leaf)| {
                (Index::from_size_offset(self.commitment.size(), *index)
                    .map(|index| (index, leaf.hash())))
            })
            .collect::<Result<Vec<_>>>()?;
        nodes.sort_unstable_by_key(|(index, _)| *index);
        // OPT: `tuple_windows` copies the hashes
        require!(
            nodes
                .iter()
                .tuple_windows()
                .all(|(a, b)| a.0 != b.0 || a.1 == b.1),
            Error::DuplicateLeafMismatch
        );
        nodes.dedup_by_key(|(index, _)| *index);
        let mut nodes: VecDeque<(Index, Hash)> = nodes.into_iter().collect();

        // Create a mutable closure to pop hashes from the list
        let mut hashes_iter = self.hashes.iter();
        let mut pop = move || hashes_iter.next().ok_or(Error::NotEnoughHashes);

        // Reconstruct the root
        while let Some((current, hash)) = nodes.pop_front() {
            if let Some(parent) = current.parent() {
                // Reconstruct the parent node
                let node = if current.is_left() {
                    if let Some((next, next_hash)) = nodes.front() {
                        // TODO: Find a better way to satisfy the borrow checker.
                        let next_hash = next_hash.clone();
                        if current.sibling().unwrap() == *next {
                            // Merge left with next
                            let _ = nodes.pop_front();
                            Node(&hash, &next_hash).hash()
                        } else {
                            // Left not merged with next
                            // TODO: Find a way to merge this branch with the next.
                            Node(&hash, pop()?).hash()
                        }
                    } else {
                        // Left not merged with next
                        Node(&hash, pop()?).hash()
                    }
                } else {
                    // Right not merged with previous (or we would have skipped)
                    Node(pop()?, &hash).hash()
                };
                // Queue the new parent node for the next iteration
                nodes.push_back((parent, node))
            } else {
                // Root node has no parent, we are done
                require!(hash == *self.commitment.hash(), Error::RootHashMismatch);
            }
        }
        Ok(())
    }
}