ProofedMesh/services/verification-service/internal/tlog/proof.go

package tlog

import (
	"crypto/sha256"
	"encoding/hex"
	"errors"
	"fmt"
	"strings"

	"basicstack.de/proofedmesh/services/verification-service/internal/canonical"
	"basicstack.de/proofedmesh/services/verification-service/internal/dsse"
)

// RFC 6962 §2.1 Merkle tree hashing. Must stay byte-identical with
// services/transparency-log/pkg/backend/merkle.go so a proof produced
// there verifies here.
//
//	leaf hash  = SHA-256(0x00 || data)
//	node hash  = SHA-256(0x01 || left || right)

// ErrInclusionProofInvalid is returned when the inclusion proof fails to
// reproduce the signed tree root.
var ErrInclusionProofInvalid = errors.New("tlog: inclusion proof does not match tree_root_hash")

// ErrInclusionProofMalformed is returned when the proof fields are
// internally inconsistent (negative sizes, bad hex, log_index out of
// range for the stated tree_size, etc.) and we cannot even attempt to
// recompute the root.
var ErrInclusionProofMalformed = errors.New("tlog: inclusion proof is malformed")

// VerifyEntry checks that:
//
//  1. The DSSE envelope's canonical hash equals the Entry.ContentHash
//     (so no bit of the envelope moved between what the signer stored
//     and what the TLog hands back).
//  2. The inclusion proof closes against the signed tree root using the
//     RFC 6962 leaf-hashing scheme shared with the transparency-log
//     backend.
func VerifyEntry(e Entry) error {
	// (1) Envelope -> content hash equality.
	gotHash, err := envelopeContentHash(e.Envelope)
	if err != nil {
		return fmt.Errorf("%w: hash envelope: %v", ErrInclusionProofMalformed, err)
	}
	if gotHash != e.ContentHash {
		return fmt.Errorf("%w: envelope hash %q != entry.content_hash %q",
			ErrInclusionProofMalformed, gotHash, e.ContentHash)
	}

	// (2) Reconstruct the leaf hash from the envelope, then walk the
	// audit path up to the stated tree root.
	leafBytes, err := canonical.Marshal(e.Envelope)
	if err != nil {
		return fmt.Errorf("%w: canonicalise envelope: %v", ErrInclusionProofMalformed, err)
	}
	leaf := leafHash(leafBytes)

	root, err := decodeHashField(e.InclusionProof.TreeRootHash)
	if err != nil {
		return fmt.Errorf("%w: tree_root_hash: %v", ErrInclusionProofMalformed, err)
	}

	computed, err := rootFromAuditPath(leaf, e.LogIndex, e.InclusionProof.TreeSize, e.InclusionProof.Hashes)
	if err != nil {
		return err
	}
	if !equalBytes(computed, root) {
		return ErrInclusionProofInvalid
	}
	return nil
}

// envelopeContentHash recomputes the sha256:<hex> hash of env's canonical
// JSON. Mirrors transparency-log/pkg/backend.EnvelopeContentHash.
func envelopeContentHash(env dsse.Envelope) (string, error) {
	b, err := canonical.Marshal(env)
	if err != nil {
		return "", err
	}
	return "sha256:" + canonical.SHA256Hex(b), nil
}

// rootFromAuditPath implements the RFC 6962 §2.1.1 inclusion proof
// verifier. index is the zero-based leaf position; size is the total
// number of leaves at the time the proof was issued; hashes is the
// audit path from the leaf towards the root. The computed root is
// returned so the caller can compare it against the signed root.
func rootFromAuditPath(leaf []byte, index, size int64, hashes []string) ([]byte, error) {
	if size <= 0 {
		return nil, fmt.Errorf("%w: tree_size %d must be positive", ErrInclusionProofMalformed, size)
	}
	if index < 0 || index >= size {
		return nil, fmt.Errorf("%w: log_index %d out of range for tree_size %d",
			ErrInclusionProofMalformed, index, size)
	}
	raw := make([][]byte, 0, len(hashes))
	for i, h := range hashes {
		b, err := decodeHashField(h)
		if err != nil {
			return nil, fmt.Errorf("%w: hashes[%d]: %v", ErrInclusionProofMalformed, i, err)
		}
		raw = append(raw, b)
	}

	// RFC 6962 iterative verifier.
	fn, sn := index, size-1
	h := append([]byte(nil), leaf...)
	for _, p := range raw {
		if sn == 0 {
			// We ran out of layers but still have proof bytes — malformed.
			return nil, fmt.Errorf("%w: audit path longer than tree depth", ErrInclusionProofMalformed)
		}
		if fn%2 == 1 || fn == sn {
			h = nodeHash(p, h)
			for fn%2 == 0 {
				fn >>= 1
				sn >>= 1
			}
		} else {
			h = nodeHash(h, p)
		}
		fn >>= 1
		sn >>= 1
	}
	if sn != 0 {
		return nil, fmt.Errorf("%w: audit path shorter than tree depth", ErrInclusionProofMalformed)
	}
	return h, nil
}

func leafHash(data []byte) []byte {
	h := sha256.New()
	h.Write([]byte{0x00})
	h.Write(data)
	return h.Sum(nil)
}

func nodeHash(left, right []byte) []byte {
	h := sha256.New()
	h.Write([]byte{0x01})
	h.Write(left)
	h.Write(right)
	return h.Sum(nil)
}

// decodeHashField decodes a hash that may be prefixed with "sha256:" or
// bare hex. The transparency-log backend ships prefixed form; be lenient.
func decodeHashField(s string) ([]byte, error) {
	s = strings.TrimPrefix(s, "sha256:")
	if len(s) != 64 {
		return nil, fmt.Errorf("expected 64 hex chars, got %d", len(s))
	}
	return hex.DecodeString(s)
}

func equalBytes(a, b []byte) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}