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

//! Transparent merkle inclusion proofs defined generically for trees of any height.
//!
//! These are wrapped in mode specific domain types by the exposed crate API to make it more
//! comprehensible.

use std::fmt::Debug;

use crate::prelude::*;

/// A proof of inclusion for a single [`Commitment`](crate::Commitment) commitment in a tree.
#[derive(Derivative)]
#[derivative(
    Debug(bound = "<Tree::Height as path::Path>::Path: Debug"),
    Clone(bound = "<Tree::Height as path::Path>::Path: Clone"),
    PartialEq(bound = "<Tree::Height as path::Path>::Path: PartialEq"),
    Eq(bound = "<Tree::Height as path::Path>::Path: Eq")
)]
pub struct Proof<Tree: Height> {
    pub(crate) position: u64,
    pub(crate) auth_path: AuthPath<Tree>,
    pub(crate) leaf: StateCommitment,
}

impl<Tree: Height> Proof<Tree> {
    /// Verify a [`Proof`] of inclusion against the root [`struct@Hash`] of a tree.
    ///
    /// Returns [`VerifyError`] if the proof is invalid.
    pub fn verify(&self, root: Hash) -> Result<(), VerifyError> {
        if root == self.root() {
            Ok(())
        } else {
            Err(VerifyError { root })
        }
    }

    /// Get the root of the tree from which the proof was generated.
    pub fn root(&self) -> Hash {
        Tree::Height::root(&self.auth_path, self.position, Hash::of(self.leaf))
    }

    /// Get the index of the item this proof claims to witness.
    pub fn index(&self) -> u64 {
        self.position
    }

    /// Get the [`AuthPath`] of this proof, representing the path from the root to the leaf of the
    /// tree that proves the leaf was included in the tree.
    pub fn auth_path(&self) -> &AuthPath<Tree> {
        &self.auth_path
    }
}

/// A proof of inclusion did not verify against the provided root hash.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
#[error("invalid inclusion proof for root hash {root:?}")]
pub struct VerifyError {
    root: Hash,
}

impl VerifyError {
    /// Get the root hash against which the proof failed to verify.
    pub fn root(&self) -> Hash {
        self.root
    }
}

/// When deserializing a proof, it was malformed.
#[derive(Debug, Clone, Copy, Eq, PartialEq, Error)]
#[error("could not decode proof")]
pub struct ProofDecodeError;

use decaf377::{FieldExt, Fq};
use penumbra_proto::penumbra::crypto::tct::v1 as pb;

impl<Tree: Height> From<Proof<Tree>> for pb::StateCommitmentProof
where
    Vec<pb::MerklePathChunk>: From<AuthPath<Tree>>,
{
    fn from(proof: Proof<Tree>) -> Self {
        Self {
            position: proof.position,
            auth_path: proof.auth_path.into(),
            note_commitment: Some(proof.leaf.into()),
        }
    }
}

impl<Tree: Height> TryFrom<pb::StateCommitmentProof> for Proof<Tree>
where
    AuthPath<Tree>: TryFrom<Vec<pb::MerklePathChunk>>,
{
    type Error = ProofDecodeError;

    fn try_from(proof: pb::StateCommitmentProof) -> Result<Self, Self::Error> {
        let position = proof.position;
        let auth_path = proof.auth_path.try_into().map_err(|_| ProofDecodeError)?;
        let leaf = StateCommitment(
            Fq::from_bytes(
                proof
                    .note_commitment
                    .ok_or(ProofDecodeError)?
                    .inner
                    .try_into()
                    .map_err(|_| ProofDecodeError)?,
            )
            .map_err(|_| ProofDecodeError)?,
        );

        Ok(Self {
            position,
            auth_path,
            leaf,
        })
    }
}