InclusionProofV2.Verify omits the f_SH(sid) shard binding: a leaf certified by the wrong shard verifies

[MastaP]

InclusionProofV2.Verify never binds the state ID to the shard that certified it, so a leaf certified by the wrong shard verifies as valid. In a multi-shard deployment this is cross-shard double-spend exposure.

Found while auditing the implementation against the yellowpaper. The RSMT core itself conforms byte-for-byte; this is a missing check in the public proof verifier.

What the spec requires

platform.tex types VerifyInclusionProof as IP × CD × UB → bool — the partition description CD_β, carrying the network id α and the sharding scheme SH, is an input. Before any tree check it mandates:

ensure(UC.C^r.α = T.α)
ensure(CD_β.α = T.α ∧ H(CD_β) = UC.C^uni.dhash)
σ ← UC.C^shard.σ
ensure(σ ∈ CD_β.SH)
ensure(f_{CD_β.SH}(sid) = σ)      // Proof comes from the right shard

f_SH derives the expected shard from the key itself. The paper explicitly forecloses delegating this to certificate verification:

VerifyUnicityCert "does not, by itself, prove that a particular state identifier belongs to the shard named in C^shard; that binding is checked by the proof verification functions below."

What the code does

pkg/api/types.go InclusionProofV2.Verify implements the tree and certificate steps faithfully but not the binding. VerifierContext replaces CD_β with a caller-supplied PartitionID + ExpectedShardID (types.go:378-383), and the only shard test is inside uc.Verify(..., vctx.ExpectedShardID, ...) at types.go:452, which reaches bft-go-base types/shard_certificate.go and does cert.Shard.Equal(shardID) — equality with the caller's own value, never f_SH(sid) = σ.

The network id is also unchecked: UnicitySeal.Verify never compares seal.NetworkID against tb.GetNetworkID(), so a UC sealed for testnet verifies against a mainnet trust base.

Impact

Reproduced during the audit: in a two-shard scheme, a leaf with sid = 0x1111… (which routes to shard "0") committed in shard 1's SMT, under shard 1's fully signed UC, returns nil from Verify. Shard B can certify a spend of a state owned by shard A and verifiers accept it. Uniqueness is enforced per-tree, so nothing else catches it.

Two things make this worse in practice:

• test/integration/bft_sharding_e2e_test.go:141-151 derives ExpectedShardID from which endpoint served the proof — exactly the pattern that accepts a foreign-shard leaf. Anything modelled on it inherits the hole.
• docs/inclusion-proof-wire.md previously told integrators to "derive ExpectedShardID from configuration". That is not the specified check and does not close the gap — the spec derives the expected shard from the key, not from deployment config. (Corrected in fix(api): bind inclusion proofs to the certified shard and network; return referenceTime on block records #182.)

Note there are currently no non-test callers of InclusionProofV2.Verify; production paths go through internal/proofverify/local.go, which by its own contract does no shard binding, no network check and no UC verification. So the present blast radius is external consumers of pkg/api, not this service's own hot path — but this is the verifier we publish for other implementations to use.

Suggested fix

f_SH already exists in-repo and is applied correctly at admission — internal/signing/certification_request_validator.go:194 (bftShardID.Comparator()) and :202 (api.MatchesShardPrefixFromHex). The verifier needs the same thing:

1. VerifierContext carries the sharding scheme (or the full partition descriptor) instead of a caller-chosen ExpectedShardID.
2. Verify computes σ_expected = f_SH(v2.StateID) itself and requires σ_expected = UC.C^shard.σ, plus σ ∈ SH.
3. Add the network check UC.C^r.α = T.α.
4. Update the e2e test to stop deriving the expected shard from the serving endpoint.

This is a breaking change to a public API, which is why it is filed rather than patched inline.

Partly out of scope: H(CD_β) = UC.C^uni.dhash cannot be done here — the bft-go-base UnicityTreeCertificate has no dhash field on the wire, so platform.tex's leaf format x_i ← H(IH[C_i] ‖ H(CD[C_i])) is missing from the UC encoding itself. That half is BFT-Core-owned. The α check and the f_SH binding are squarely this repo's.

Related

Same audit also found: parent mode certifies a non-canonical RSMT root (empty subtrees committed as all-zero digests rather than compressed, so IR.h is not reproducible externally); one of eight predicate types implemented with τ never reaching the validator; the state-ID preimage inlining a tagged predicate where appendix-token.tex specifies a byte string; and non-inclusion certificates unimplemented with the wire field order inverted relative to appendix-hashtrees.tex. Happy to file those separately.

[ristik]

Perhaps it makes sense to just gain parity with the SDK-s; that's good enough and avoids breaking changes:

The Go verifier accepts a proof when:

• the leaf is valid under the UC’s SMT root,
• the UC is valid for the caller-supplied ExpectedShardID,
• but that certified shard does not contain the leaf’s state ID.

VerifierContext does not need a complete sharding scheme or partition descriptor to match SDK behavior. After decoding the UC, Go can perform:

     shardID := uc.ShardTreeCertificate.Shard
     if !shardID.Comparator()(key) {
         return errors.New("state ID does not belong to certified shard")
     }

     if uc.UnicitySeal.NetworkID != vctx.TrustBase.GetNetworkID() {
         return errors.New("unicity seal network does not match trust base")
     }

[MastaP]

Agreed — your approach is better than what I proposed, and I was wrong to reach for the partition descriptor.

I derived the fix from platform.tex, which takes CD_β as an input to VerifyInclusionProof and checks f_{CD_β.SH}(sid) = σ. Reading it that literally, I concluded VerifierContext had to carry the sharding scheme, which meant a public API break. But σ is already in hand — the UC names the shard it certifies — so uc.ShardTreeCertificate.Shard.Comparator()(key) gives the same binding without any new input. For a prefix-based scheme that is f_SH(sid) = σ, since f_SH is defined as the unique prefix match. The only piece it does not cover is σ ∈ CD_β.SH, and a validly signed UC for a shard outside the scheme is a different problem.

Verified c767749 locally: builds and vets clean, ./pkg/api passes. Mutation-checked the new test — deleting the shard-binding block makes TestInclusionProofV2Verify_StateIDMustBelongToCertifiedShard fail, so it genuinely guards the hole rather than passing vacuously.

The commit also goes past what #185 proposed, and those additions look right to me: binding stateId to the certification data via CreateStateID(), and requiring owner predicate, source state hash and witness to match between proof and request. Previously only transactionHash and expiresAt were compared, so a proof could carry different certification data than the request it was checked against and still pass. That is arguably the more general bug.

Closing this in favour of #185. I have also removed the "derive ExpectedShardID from configuration" advice from docs/inclusion-proof-wire.md — that was mine, and it presented the gap as a caller responsibility when it was a missing check.