ChainMmr does not guarantee it tracks valid block headers

[PhilippGackstatter]

A ChainMmr is a wrapper around a PartialMmr and a map of BlockHeaders. The way we use it is to usually check whether the mmr's hashed peaks equals the reference block of a tx/batch/block and then "verify" that some block is tracked by checking whether the map of headers contains the block number.
It is not documented on ChainMmr whether it is supposed to guarantee that it only contains headers which are in the MMR, but the way we use it strongly suggest it does. However in that case, I would expect this test to pass, i.e. ChainMmr::new to return an error:

#[test]
fn chain_mmr_new_on_invalid_header_fails() {
    let block_header0 = int_to_block_header(0);
    let block_header1 = int_to_block_header(1);
    let block_header2 = int_to_block_header(2);

    let mut mmr = Mmr::default();
    mmr.add(block_header0.hash());
    mmr.add(block_header1.hash());
    mmr.add(block_header2.hash());

    let mut partial_mmr = PartialMmr::from_peaks(mmr.peaks());
    for i in 0..3 {
        partial_mmr
            .track(i, mmr.get(i).unwrap(), &mmr.open(i).unwrap().merkle_path)
            .unwrap();
    }

    let fake_block_header2 = BlockHeader::mock(2, None, None, &[], Digest::default());

    assert_ne!(block_header2.hash(), fake_block_header2.hash());

    // Construct a ChainMmr with an invalid block header.
    let _error =
        ChainMmr::new(partial_mmr, vec![block_header0, block_header1, fake_block_header2])
            .unwrap_err();
}

However it doesn't and instead returns Ok(ChainMmr). In new, we only check whether the passed header's block number is tracked in the mmr, not whether the tracked header's hash matches the passed one. So this allows passing an incorrect block header whose number matches an actually tracked header's number.

The question is, is this intended? Probably not the way we use it.

I think ChainMmr should guarantee that it only contains valid headers, but the fix is not straightforward, afaict, because PartialMmr doesn't allow for the hash equality check because it does not track the leaves, only authentication paths.

I would suggest to:

Document what ChainMmr guarantees (and/or what it doesn't).

Revisit how ChainMmr is constructed. Maybe new should return an empty data structure and the type should expose an fn track(&mut self, header_witness: BlockHeaderWitness) method with BlockHeaderWitness { header: BlockHeader, mmr_proof: MmrProof }. In that method, we add the header's hash to the MMR at the header's block num with the given merkle path from the proof. That way, it would be impossible for an invalid block header to end up in the ChainMmr without the hashed peaks also being different.

Or maybe we want a new function to take an impl Iterator<BlockHeaderWitness> in case we ever want to parallelize something.

This might need some more investigation overall, and if we work on this, we should verify that the ChainMmr can be built easily in get_batch_inputs and get_block_inputs in miden-node.

Finally, I assume this is not an issue for overall correctness, because the MASM code must ultimately be correct and the way the MMR works there does not depend on ChainMmr correctness. I think if an invalid block header was in the advice provider, it would be detected there, but may be good to double check.

[bobbinth]

Yes, for correctness this shouldn't be an issue but it would be good to catch errors before we get to executing MASM as by the time we get there, reverting things may become quite expensive. So, I agree that ChainMmr should provide this guarantee.

We could probably have two different ways of constructing ChainMmr:

• "untrusted" constructor which verifies that the block headers actually match the expected leaves. We should be able to do it by computing openings for each block header and making sure the root matches the expected peak. The main overhead here would be a bunch of hashes.
• "trusted" constructor which would assume that the provided data is fine, and thus, would avoid doing a bunch of hashes (I think that's kind of what we have now).

[varun-doshi]

I'd like to give this a shot if available

[varun-doshi]

pub fn track(&mut self, header_witness: BlockHeaderWitness) -> Result<(), ChainMmrError> {
        let path = header_witness.mmr_proof.merkle_path.clone();
        let peak_index = header_witness.mmr_proof.peak_index() as u64;
        let header_hash = header_witness.header.hash();
        let root = header_witness
            .mmr_proof
            .merkle_path
            .compute_root(header_witness.mmr_proof.relative_pos() as u64, header_hash)
            .unwrap();

        if path.verify(peak_index, header_hash, &root).is_ok() {
            self.partial_mmr_mut()
                .track(header_witness.mmr_proof.relative_pos(), header_hash, &path)
                .unwrap();
            self.blocks.insert(header_witness.header.block_num(), header_witness.header);
        }
        Ok(())
    }

Is this close to something we want here? I'm not sure if I've got the right values for the verify function. Please correct me if I'm wrong
cc: @PhilippGackstatter @bobbinth

[PhilippGackstatter]

Thanks @varun-doshi for offering to take this issue. I think this issue may not be a good fit due to the dependency of this API with miden-node, i.e. we have to design this API in concert with how it is used in miden-node.

If you'd like to drive #1145 instead, that'd be a big help too!