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

light_client/consensus/
header.rs
