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

// Copyright (C) 2019-2021 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::{
    errors::MerkleError,
    traits::{CommitmentScheme, CRH},
};
use snarkvm_utilities::{to_bytes, FromBytes, ToBytes};
use std::io::{Read, Result as IoResult, Write};

#[derive(Derivative)]
#[derivative(
    Clone(bound = "C: CommitmentScheme, H: CRH"),
    PartialEq(bound = "C: CommitmentScheme, H: CRH"),
    Eq(bound = "C: CommitmentScheme, H: CRH")
)]
pub struct CommitmentMerklePath<C: CommitmentScheme, H: CRH> {
    pub leaves: (<C as CommitmentScheme>::Output, <C as CommitmentScheme>::Output),
    pub inner_hashes: (<H as CRH>::Output, <H as CRH>::Output),
}

impl<C: CommitmentScheme, H: CRH> CommitmentMerklePath<C, H> {
    pub fn verify(
        &self,
        parameters: &H,
        root_hash: &<H as CRH>::Output,
        leaf: &<C as CommitmentScheme>::Output,
    ) -> Result<bool, MerkleError> {
        // Check if the leaf is included in the path
        if leaf != &self.leaves.0 && leaf != &self.leaves.1 {
            return Ok(false);
        };

        // Check that the inner hash is included in the path
        let inner_hash = hash_inner_node(parameters, &self.leaves.0, &self.leaves.1)?;

        if inner_hash != self.inner_hashes.0 && inner_hash != self.inner_hashes.1 {
            return Ok(false);
        };

        // Check that the root hash is valid.
        let root = hash_inner_node(parameters, &self.inner_hashes.0, &self.inner_hashes.1)?;

        if &root != root_hash {
            return Ok(false);
        }

        Ok(true)
    }
}

/// Returns the output hash, given a left and right hash value.
fn hash_inner_node<H: CRH, L: ToBytes>(crh: &H, left: &L, right: &L) -> Result<<H as CRH>::Output, MerkleError> {
    let input = to_bytes![left, right]?;
    Ok(crh.hash(&input)?)
}

impl<C: CommitmentScheme, H: CRH> ToBytes for CommitmentMerklePath<C, H> {
    #[inline]
    fn write<W: Write>(&self, mut writer: W) -> IoResult<()> {
        self.leaves.0.write(&mut writer)?;
        self.leaves.1.write(&mut writer)?;
        self.inner_hashes.0.write(&mut writer)?;
        self.inner_hashes.1.write(&mut writer)
    }
}

impl<C: CommitmentScheme, H: CRH> FromBytes for CommitmentMerklePath<C, H> {
    #[inline]
    fn read<R: Read>(mut reader: R) -> IoResult<Self> {
        let leaves = (C::Output::read(&mut reader)?, C::Output::read(&mut reader)?);
        let inner_hashes = (H::Output::read(&mut reader)?, H::Output::read(&mut reader)?);

        Ok(Self { leaves, inner_hashes })
    }
}