Support for inclusion/consistency proofs and checkpoint/STH verification.

[vembacher]

Summary

I would like to see support for inclusion/consistency proofs and checkpoints/STH.

Also related: #274

Reasoning

• inclusion proofs: enable stricter bundle/log entry verification compared to only verifying the SET
• consistency proofs: enable monitor implementations
• checkpoints/STH: these are included along the other two, and should also be verified

Implementation

I'm willing to implement this feature, I have already implemented it in another (non-public) crate so I can just port it to this crate.
However, I want to discuss some minor details on how to do it first:

1. Add the basic implementation to the crypto module that is not be part of the public API.
2. Add methods to the related Rekor data structures to verify them, this would be part of the public API .
3. For now I would not add their verification to the Cosign module directly to avoid breaking changes here.
4. Is there a specification for the checkpoint/STH format?

[haydentherapper]

Checkpoint format comes from https://github.com/sigstore/rekor/blob/main/pkg/util/checkpoint.go. It's Go's SumbDB note format (https://pkg.go.dev/golang.org/x/mod/sumdb/note) with a timestamp in OtherContent.

[vembacher]

Checkpoint format comes from https://github.com/sigstore/rekor/blob/main/pkg/util/checkpoint.go. It's Go's SumbDB note format (https://pkg.go.dev/golang.org/x/mod/sumdb/note) with a timestamp in OtherContent.

Thanks! I was not sure if there was another specification I did not find. I used the Go code as the reference implementation.

[gaetanww]

I'm also interested in supporting inclusion proofs, do you need help to get this over the line?

[haydentherapper]

cc @woodruffw @jleightcap - I think y'all have begun looking at supporting inclusion proof?

[tnytown]

Speaking for the @trailofbits delegation: I don't think we've gotten around to integrating inclusion proofs yet. I was planning on taking a look at the implementation in #285 once the dust settles on bundles (#326 and #311).

[gaetanww]

I tried the implementation in #285 today and there's a problem with it, see my comment. Happy to add a commit if you agree with the fix.