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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

// Copyright (C) 2019-2020 Aleo Systems Inc.
// This file is part of the snarkVM library.

// The snarkVM library is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// The snarkVM library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with the snarkVM library. If not, see <https://www.gnu.org/licenses/>.

use crate::commitment_tree::CommitmentMerklePath;
use snarkvm_errors::algorithms::MerkleError;
use snarkvm_models::algorithms::{CommitmentScheme, CRH};
use snarkvm_utilities::{to_bytes, ToBytes};

#[derive(Derivative)]
#[derivative(
    Clone(bound = "C: CommitmentScheme, H: CRH"),
    PartialEq(bound = "C: CommitmentScheme, H: CRH"),
    Eq(bound = "C: CommitmentScheme, H: CRH")
)]
pub struct CommitmentMerkleTree<C: CommitmentScheme, H: CRH> {
    /// The computed root of the full Merkle tree.
    root: <H as CRH>::Output,

    /// The internal hashes of the commitment Merkle tree
    inner_hashes: (<H as CRH>::Output, <H as CRH>::Output),

    /// The leaves of the commitment Merkle tree
    leaves: [<C as CommitmentScheme>::Output; 4],

    /// The CRH parameters used to construct the Merkle tree
    #[derivative(PartialEq = "ignore")]
    parameters: H,
}

impl<C: CommitmentScheme, H: CRH> CommitmentMerkleTree<C, H> {
    /// Construct a new commitment Merkle tree.
    pub fn new(parameters: H, leaves: &[<C as CommitmentScheme>::Output; 4]) -> Result<Self, MerkleError> {
        let input_1 = to_bytes![leaves[0], leaves[1]]?;
        let inner_hash1 = H::hash(&parameters, &input_1)?;

        let input_2 = to_bytes![leaves[2], leaves[3]]?;
        let inner_hash2 = H::hash(&parameters, &input_2)?;

        let root = H::hash(&parameters, &to_bytes![inner_hash1, inner_hash2]?)?;

        Ok(Self {
            root,
            inner_hashes: (inner_hash1, inner_hash2),
            leaves: leaves.clone(),
            parameters,
        })
    }

    #[inline]
    pub fn root(&self) -> <H as CRH>::Output {
        self.root.clone()
    }

    #[inline]
    pub fn inner_hashes(&self) -> (<H as CRH>::Output, <H as CRH>::Output) {
        self.inner_hashes.clone()
    }

    #[inline]
    pub fn leaves(&self) -> [<C as CommitmentScheme>::Output; 4] {
        self.leaves.clone()
    }

    pub fn generate_proof(
        &self,
        leaf: &<C as CommitmentScheme>::Output,
    ) -> Result<CommitmentMerklePath<C, H>, MerkleError> {
        let leaf_index = match self.leaves.iter().position(|l| l == leaf) {
            Some(index) => index,
            _ => return Err(MerkleError::InvalidLeaf),
        };

        let sibling_index = sibling(leaf_index);

        let leaf = leaf.clone();
        let sibling = self.leaves[sibling_index].clone();

        let leaves = match is_left_child(leaf_index) {
            true => (leaf, sibling),
            false => (sibling, leaf),
        };

        let inner_hashes = self.inner_hashes.clone();

        Ok(CommitmentMerklePath { leaves, inner_hashes })
    }
}

/// Returns the index of the sibling leaf, given an index.
#[inline]
fn sibling(index: usize) -> usize {
    assert!(index < 4);
    match index {
        0 => 1,
        1 => 0,
        2 => 3,
        3 => 2,
        _ => unreachable!(),
    }
}

/// Returns true iff the given index represents a left child.
#[inline]
fn is_left_child(index: usize) -> bool {
    index % 2 == 0
}