Implement `calculate_non_existence_root` in Rust

[ethanfrey]

Can you please be more explicit?

I know that we generate these roots in test code and verify them properly. There is likely a specific usage you have in mind that the library does not cover, so please document the code you are trying to write and what api it needs. (and enough code so I can comment if there is an alternate approach)

[shravanshetty1]

@ethanfrey I apologise, I renamed the issue so it would be less confusing, heres some context on why it could be useful. I referred to ibc-go and was able to create a verify membership function

pub fn verify_membership(
    proofs: Vec<ics23::CommitmentProof>,
    root: &[u8],
    key: &[u8],
    value: &[u8],
) -> Result<()> {
    let specs = get_cosmos_specs();
    let path = get_default_path(key);
    validate_membership_args(specs.clone(), proofs.clone(), root, path.clone())?;
    ensure!(
        !value.is_empty() && value.len() != 0,
        "value cannot be empty"
    );

    let mut value = value.to_vec();
    for i in 0..proofs.len() {
        let key = path[i];
        let subroot = ics23::calculate_existence_root(
            super::helpers::get_exist_proof(&proofs[i], key).ok_or(anyhow!(
                "could not convert commitment proof to existence proof"
            ))?,
        )?;
        if !ics23::verify_membership(&proofs[i], &specs[i], &subroot, key, value.as_slice()) {
            bail!("failed to verify proof at index {}", i)
        }
        value = subroot
    }

    let given_root = hex::encode_upper(root);
    let calculated_root = hex::encode_upper(value);

    ensure!(
        given_root == calculated_root,
        format!(
            "given root did not much calculated root - given {} calculated {}",
            given_root, calculated_root
        )
    );

    Ok(())
}

pub fn verify_non_membership(
    proofs: Vec<ics23::CommitmentProof>,
    root: &[u8],
    key: &[u8],
) -> Result<()> {
    let specs = get_cosmos_specs();
    let path = get_default_path(key);
    validate_membership_args(specs.clone(), proofs.clone(), root, path.clone())?;

    // TODO

    Ok(())
}

However I cannot seem to implement verify non membership as in ibc-go since I would need to calculate the root of the non_existence proof. Currently the ics23::calculate_existence_root calculates the root for existence proofs, there is no such function for non existence proof in the rust library, however in the go library it exists.

Here is the go code I am referring to - https://github.com/cosmos/ibc-go/blob/74182d8d45bca3504ed0190e9cdedb1a8ba45973/modules/core/23-commitment/types/merkle.go#L132.

If there is a simple way to solve this please let me know! Thanks in advance!

[shravanshetty1]

ics 23 go library implementation - https://github.com/confio/ics23/blob/5a0206f31ac5ccb40757e98a3c86e7beff95793b/go/proof.go#L48

[ethanfrey]

Thank you for the explanation.

I can look more in depth on Monday but a quick response is that a non existence proof contains 1 or 2 existence proof (1 if it is on the edge of the tree). Both of those have the same root.

You could look at the contents of the non existence proof and return the root of left or right, whichever exists (neither existing means empty tree, which we do not support and consider invalid, so it can error)

[ethanfrey]

Happy for a PR if you add a test case or two