light_client/consensus/
header.rs

1//! Types for fetching and verifying headers from an untrusted provider.
2
3use anyhow::{Context, Result, anyhow, ensure};
4use committable::Committable;
5use espresso_types::{BlockMerkleTree, Header};
6use jf_merkle_tree_compat::MerkleTreeScheme;
7use serde::{Deserialize, Serialize};
8
9/// A proof that a header is finalized, relative to some known-finalized leaf.
10#[derive(Clone, Debug, PartialEq, Eq, Deserialize, Serialize)]
11pub struct HeaderProof {
12    header: Header,
13    proof: <BlockMerkleTree as MerkleTreeScheme>::MembershipProof,
14}
15
16impl HeaderProof {
17    /// Construct a [`HeaderProof`] from the header itself and a Merkle inclusion proof.
18    pub fn new(
19        header: Header,
20        proof: <BlockMerkleTree as MerkleTreeScheme>::MembershipProof,
21    ) -> Self {
22        Self { header, proof }
23    }
24
25    /// Inspect the header without verifying it.
26    pub fn header(&self) -> &Header {
27        &self.header
28    }
29
30    /// Inspect the Merkle inclusion proof without verifying it.
31    pub fn proof(&self) -> &<BlockMerkleTree as MerkleTreeScheme>::MembershipProof {
32        &self.proof
33    }
34
35    /// Verify a [`HeaderProof`] and get the verified header if valid.
36    pub fn verify(self, root: <BlockMerkleTree as MerkleTreeScheme>::Commitment) -> Result<Header> {
37        self.verify_proof(root)?;
38        Ok(self.header)
39    }
40
41    /// Verify a [`HeaderProof`] and get a reference to the verified header if valid.
42    ///
43    /// This is the same as [`verify`](Self::verify), but returns the result as a reference rather
44    /// than consuming `self`.
45    pub fn verify_ref(
46        &self,
47        root: <BlockMerkleTree as MerkleTreeScheme>::Commitment,
48    ) -> Result<&Header> {
49        self.verify_proof(root)?;
50        Ok(&self.header)
51    }
52
53    fn verify_proof(&self, root: <BlockMerkleTree as MerkleTreeScheme>::Commitment) -> Result<()> {
54        // Check that the proof is actually for the correct header, before verifying the proof
55        // (which is slightly more expensive).
56        ensure!(
57            self.proof.elem() == Some(&self.header.commit()),
58            "proof is not for the correct header"
59        );
60        ensure!(
61            self.proof.index() == &self.header.height(),
62            "proof is not for the correct height"
63        );
64
65        BlockMerkleTree::verify(root, self.header.height(), &self.proof)
66            .context("malformed proof")?
67            .map_err(|()| {
68                anyhow!(
69                    "incorrect proof for element {} relative to {root}",
70                    self.header.height()
71                )
72            })?;
73        Ok(())
74    }
75}
76
77#[cfg(test)]
78mod test {
79    use espresso_types::BLOCK_MERKLE_TREE_HEIGHT;
80    use jf_merkle_tree_compat::{AppendableMerkleTreeScheme, prelude::SHA3MerkleTree};
81    use pretty_assertions::assert_eq;
82    use versions::EPOCH_VERSION;
83
84    use super::*;
85    use crate::testing::leaf_chain;
86
87    #[tokio::test]
88    #[test_log::test]
89    async fn test_header_proof_valid() {
90        let leaves = leaf_chain(0..=3, EPOCH_VERSION).await;
91
92        // Use an appendable `MerkleTree` rather than a `BlockMerkleTree` (which is a
93        // `LightweightMerkleTree`) so we can look up paths for previously inserted elements.
94        let mut mt = SHA3MerkleTree::new(BLOCK_MERKLE_TREE_HEIGHT);
95        for (root, leaf) in leaves.iter().enumerate() {
96            for (height, expected) in leaves.iter().enumerate().take(root) {
97                let proof = mt.lookup(height as u64).expect_ok().unwrap().1;
98                let header = expected.header();
99                let proof = HeaderProof::new(header.clone(), proof);
100                assert_eq!(proof.verify_ref(mt.commitment()).unwrap(), header);
101                assert_eq!(proof.verify(mt.commitment()).unwrap(), *header);
102            }
103            mt.push(leaf.block_hash()).unwrap();
104        }
105    }
106
107    #[tokio::test]
108    #[test_log::test]
109    async fn test_header_proof_invalid_wrong_path() {
110        let leaves = leaf_chain(0..=1, EPOCH_VERSION).await;
111        let mt = BlockMerkleTree::from_elems(
112            Some(BLOCK_MERKLE_TREE_HEIGHT),
113            [leaves[0].block_hash(), leaves[1].block_hash()],
114        )
115        .unwrap();
116        let proof = HeaderProof::new(
117            leaves[0].header().clone(),
118            mt.lookup(1).expect_ok().unwrap().1,
119        );
120        let err = proof.verify(mt.commitment()).unwrap_err();
121        assert!(
122            err.to_string()
123                .contains("proof is not for the correct header"),
124            "{err:#}"
125        );
126    }
127
128    #[tokio::test]
129    #[test_log::test]
130    async fn test_header_proof_invalid_wrong_height() {
131        let leaf = leaf_chain(0..1, EPOCH_VERSION).await.remove(0);
132        let mts = [0, 1]
133            .into_iter()
134            .map(|height_diff| {
135                BlockMerkleTree::from_elems(
136                    Some(BLOCK_MERKLE_TREE_HEIGHT + height_diff),
137                    [leaf.block_hash()],
138                )
139                .unwrap()
140            })
141            .collect::<Vec<_>>();
142        let proof = HeaderProof::new(
143            leaf.header().clone(),
144            mts[0].lookup(0).expect_ok().unwrap().1,
145        );
146        let err = proof.verify(mts[1].commitment()).unwrap_err();
147        assert!(err.to_string().contains("malformed proof"), "{err:#}");
148    }
149}
light_client/consensus/header.rs

light_client/consensus/
header.rs
