Assessment of Soundness for the NMT Partial Namespace Absence Proof

[staheri14]

Problem

In the following issue #110, a new type of namespace absence proof has been identified and discussed namely, partial absence proof. This modified version of the full absence proof differs in that it provides the inclusion proof of one of the ancestors of the leafHash to the tree root, rather than the inclusion proof of the leafHash itself (where the leafHash is the leaf of the tree with the smallest namespace ID larger than the queried namespace ID). If valid, these proofs are more bandwidth-efficient than full proofs due to their shorter size. However, it is important to assess their soundness carefully, as they deviate from the original absence proof described in the LazyLedger paper.

Acceptance Criteria

• Identify the correct way that a partial absence proof should be constructed. While a high level idea is outlined in Vulnerability in VerifyNamespace: Partial Absence Proofs  #110 (comment), modifications may be necessary to ensure the proof construction meets the soundness property based on the formal proof (item below).
• Provide a formal proof in order to demonstrate the soundness of partial absence proof. The soundness property ensures that even if an adversary provides a partial absence proof, they should not be able to persuade a verifier that a namespace ID is absent from the NMT if it is actually present. Therefore, the formal proof should demonstrate that the verifier will only accept a partial absence proof as valid if and only if the namespace ID is genuinely absent from the NMT.

[staheri14]

My findings concerning the partial absence proof are documented in the linked notion page. Please be aware that it's subject to further revisions. However, the existing content should provide ample insight into the logic behind the proof. Please let me know if you have any questions.
cc: @liamsi @evan-forbes

[evan-forbes]

that document is awesome! we should definitely keep that analysis somewhere, at least in this issue, but perferably keep it in the docs somewhere. Could also be a forum post!

[staheri14]

that document is awesome! we should definitely keep that analysis somewhere, at least in this issue, but perferably keep it in the docs somewhere. Could also be a forum post!

Thanks for your feedback @evan-forbes! I'll publish it as a forum post, and will also add the content as a doc to this repo.

[staheri14]

The content of the NMT soundness analysis is being published on the Celestia forum (post), so going to mark this issue as completed.