niko_trust/pkg/verify/verify.go

// Package verify is the local trust evaluator. It takes signed TCE objects
// (claims, approval requests, approval responses, revocations) that a consumer
// has already fetched from a relay, verifies their signatures, and decides
// whether a subject holds a given attribute at a given time.
//
// The relay answers "who said what" (INV-5); this package answers "should I
// believe it". It never talks to the network and never holds a key. Every
// decision is reproducible from the objects fed in plus an explicit clock.
package verify

import (
	"crypto/subtle"
	"fmt"
	"sort"
	"sync"

	"git.n1ko.dev/Niko/niko_trust/pkg/address"
	"git.n1ko.dev/Niko/niko_trust/pkg/identity"
	"git.n1ko.dev/Niko/niko_trust/pkg/protocol"
	"git.n1ko.dev/Niko/niko_trust/pkg/tce"
	"git.n1ko.dev/Niko/niko_trust/pkg/transport"
)

// Graph holds the verified objects under evaluation.
type Graph struct {
	mu sync.Mutex

	claims      map[string]*protocol.Claim              // claim object id -> claim
	claimEnv    map[string]*transport.Envelope          // claim object id -> envelope
	delegations map[string]*protocol.DelegationClaim    // delegation id -> grant
	delegEnv    map[string]*transport.Envelope          // delegation id -> envelope
	rotRequests map[string]*protocol.KeyRotationRequest // request id -> request
	rotConfirms map[string][]*rotationConfirm           // request id -> confirms
	rotEnv      map[string]*transport.Envelope          // request/confirm id -> envelope
	revocations map[string][]*protocol.Revocation       // target claim id -> revocations
	requests    map[string]*protocol.ApprovalRequest
	requestEnv  map[string]*transport.Envelope
	responses   map[string]*protocol.ApprovalResponse
	responseEnv map[string]*transport.Envelope
}

// rotationConfirm pairs a stored confirm with the content id it was filed
// under, so ties between competing consents resolve deterministically.
type rotationConfirm struct {
	id  string
	c   *protocol.KeyRotationConfirm
	env *transport.Envelope
}

// NewGraph returns an empty graph.
func NewGraph() *Graph {
	return &Graph{
		claims:      make(map[string]*protocol.Claim),
		claimEnv:    make(map[string]*transport.Envelope),
		delegations: make(map[string]*protocol.DelegationClaim),
		delegEnv:    make(map[string]*transport.Envelope),
		rotRequests: make(map[string]*protocol.KeyRotationRequest),
		rotConfirms: make(map[string][]*rotationConfirm),
		rotEnv:      make(map[string]*transport.Envelope),
		revocations: make(map[string][]*protocol.Revocation),
		requests:    make(map[string]*protocol.ApprovalRequest),
		requestEnv:  make(map[string]*transport.Envelope),
		responses:   make(map[string]*protocol.ApprovalResponse),
		responseEnv: make(map[string]*transport.Envelope),
	}
}

// Add verifies and ingests one envelope. Verification is the signature over the
// exact TCE bytes; a failing object is rejected. The caller is expected to feed
// every object it retrieved, including ones it will later decide are irrelevant.
func (g *Graph) Add(env *transport.Envelope) error {
	if _, err := env.Verify(); err != nil {
		return fmt.Errorf("verify: %w", err)
	}
	_, obj, err := transport.DecodeObject(env.TCE)
	if err != nil {
		return fmt.Errorf("decode: %w", err)
	}
	id := env.ContentID()
	g.mu.Lock()
	defer g.mu.Unlock()
	switch o := obj.(type) {
	case *protocol.Claim:
		g.claims[id] = o
		g.claimEnv[id] = env
	case *protocol.DelegationClaim:
		g.delegations[id] = o
		g.delegEnv[id] = env
	case *protocol.KeyRotationRequest:
		g.rotRequests[id] = o
		g.rotEnv[id] = env
	case *protocol.KeyRotationConfirm:
		g.rotConfirms[o.RotationHash.String()] = append(
			g.rotConfirms[o.RotationHash.String()],
			&rotationConfirm{id: id, c: o, env: env})
	case *protocol.Revocation:
		g.revocations[o.ClaimID.String()] = append(g.revocations[o.ClaimID.String()], o)
	case *protocol.ApprovalRequest:
		g.requests[id] = o
		g.requestEnv[id] = env
	case *protocol.ApprovalResponse:
		g.responses[id] = o
		g.responseEnv[id] = env
	}
	return nil
}

// Policy describes the question put to the evaluator.
type Policy struct {
	// Subject is the address the claim must be about.
	Subject address.Address
	// Predicate is the claim key whose presence/truth is required.
	Predicate string
	// Approvers, if non-empty, requires an allowance from one of these
	// addresses binding to a request sent by the claim's issuer. When empty,
	// no approval is required.
	Approvers []address.Address
	// Threshold is how many distinct approvers must have allowed (k-of-n).
	// Zero means "any one" (k = 1).
	Threshold int
	// TrustedIssuers restricts which issuers may satisfy the policy. Empty
	// means "any issuer the caller fed into the graph", preserving the
	// original model where anchoring is fully out of band. A non-empty set
	// is a pure filter: claims from other issuers are ignored, never
	// treated as negative evidence.
	TrustedIssuers []address.Address
	// MaxDepth caps delegation chain hops when TrustedIssuers is set. Zero
	// means the built-in default (3). It also bounds key-rotation chains.
	MaxDepth int
	// RotationMaxAge is how many seconds old a key-rotation confirm may be
	// at the evaluation instant and still count. Zero disables the check:
	// a confirmed rotation never goes stale. The bound exists because a
	// stolen predecessor key could otherwise rotate silently forever.
	RotationMaxAge uint64
	// Now is the evaluation time.
	Now uint64
}

// Result is the evaluator's decision.
type Result struct {
	Trusted       bool
	Claim         *protocol.Claim
	Issuer        address.Address
	ApprovedBy    address.Address   // first approver that allowed (if any)
	ApprovedByAll []address.Address // all approvers that allowed
	Revoked       bool
	// Chain is the delegation path issuer → … → trusted root when the
	// claim's authority came from one; nil for direct issuance. It is
	// audit evidence, not an authorization statement by itself.
	Chain []address.Address
	// RotationChain is the key-succession path issuer → … → root when the
	// claim's issuer reached a trusted root through confirmed rotations.
	// Also audit evidence only.
	RotationChain []address.Address
	Reason        string
}

// Evaluate decides whether, under the policy, the subject holds the predicate.
func (g *Graph) Evaluate(p Policy) Result {
	g.mu.Lock()
	defer g.mu.Unlock()

	// Collect every structurally valid candidate, then decide trust per
	// candidate in a deterministic order: highest serial first, ties broken
	// by content ID. Determinism matters now that acceptance may require a
	// delegation walk — map iteration order must never leak into decisions.
	type candidate struct {
		id string
		c  *protocol.Claim
	}
	var candidates []candidate
	for id, c := range g.claims {
		if transport.AddrOf(c.Subject) != p.Subject.String() {
			continue
		}
		v, ok := c.Claims[p.Predicate]
		if !ok || !valueTruthy(v) {
			continue
		}
		if protocol.ValidateCurrent(c.CreatedAt, c.ExpiresAt, p.Now) != nil {
			continue
		}
		candidates = append(candidates, candidate{id, c})
	}
	sort.Slice(candidates, func(i, j int) bool {
		a, b := candidates[i], candidates[j]
		if a.c.Serial != b.c.Serial {
			return a.c.Serial > b.c.Serial
		}
		return a.id < b.id
	})

	for _, cand := range candidates {
		issuer := mustAddr(cand.c.Issuer)

		// Trust anchoring: an empty filter keeps the original model (the
		// caller fed only objects it cares about). A non-empty filter is
		// satisfied either directly or through a delegation chain from a
		// trusted root down to the claim's actual issuer.
		var chain, rotChain []address.Address
		if len(p.TrustedIssuers) > 0 && !addrInAddr(issuer, p.TrustedIssuers) {
			resolved, ok := g.resolveDelegationChain(cand.c.Issuer, p)
			if !ok {
				rotChain, ok = g.resolveRotationChain(cand.c.Issuer, p)
			}
			if !ok {
				continue // this issuer cannot speak; try the next claim
			}
			chain = resolved
		}

		// Revocation: a verified revocation must be signed by the claim's
		// issuer and target this exact claim.
		for _, rev := range g.revocations[cand.id] {
			if protocol.VerifyRevocationOf(rev, cand.c) == nil {
				return Result{Claim: cand.c, Issuer: issuer, Chain: chain,
					RotationChain: rotChain,
					Revoked:       true, Reason: "revoked: " + rev.Reason}
			}
		}

		// Optional approval requirement.
		if len(p.Approvers) > 0 {
			first, all, ok := g.findApproval(cand.c, cand.id, p)
			if !ok {
				return Result{Claim: cand.c, Issuer: issuer, Chain: chain,
					RotationChain: rotChain,
					Reason:        "no valid approval from required approvers"}
			}
			return Result{Trusted: true, Claim: cand.c, Issuer: issuer, Chain: chain,
				RotationChain: rotChain, ApprovedBy: first, ApprovedByAll: all}
		}

		return Result{Trusted: true, Claim: cand.c, Issuer: issuer, Chain: chain,
			RotationChain: rotChain}
	}
	return Result{Reason: "no active claim for predicate"}
}

// defaultMaxDepth bounds delegation chains when the policy does not say.
const defaultMaxDepth = 3

// resolveDelegationChain searches for a path of active, unrevoked, covering
// delegations from the claim's issuer up to any trusted root, honouring each
// link's own re-delegation budget. It returns the chain ordered issuer → …
// → root (inclusive of both ends).
func (g *Graph) resolveDelegationChain(issuerPub []byte, p Policy) ([]address.Address, bool) {
	maxDepth := p.MaxDepth
	if maxDepth <= 0 {
		maxDepth = defaultMaxDepth
	}

	origin := append([]byte(nil), issuerPub...)
	current := append([]byte(nil), issuerPub...)
	chain := []address.Address{mustAddr(origin)}

	for hop := 1; hop <= maxDepth; hop++ {
		// Pick the strongest grant to current: highest serial, then lowest
		// content id, so the outcome never depends on map order.
		bestID := ""
		var best *protocol.DelegationClaim
		for id, d := range g.delegations {
			if subtle.ConstantTimeCompare(d.Grantee, current) != 1 {
				continue
			}
			if !d.Covers(p.Predicate) {
				continue
			}
			if protocol.DelegationStatusAt(d, p.Now) != protocol.StatusActive {
				continue
			}
			// The granter revokes its own grant by object id.
			withdrawn := false
			for _, rev := range g.revocations[id] {
				if protocol.VerifyRevocationOfDelegation(rev, d) == nil {
					withdrawn = true
					break
				}
			}
			if withdrawn {
				continue
			}
			if best == nil || d.Serial > best.Serial ||
				(d.Serial == best.Serial && id < bestID) {
				best, bestID = d, id
			}
		}
		if best == nil {
			return nil, false
		}
		root := mustAddr(best.Granter)
		chain = append(chain, root)
		if addrInAddr(root, p.TrustedIssuers) {
			// Every link must have allowed the hops that sit below it:
			// link i of k needs MaxDepth >= k-i.
			k := len(chain) - 1
			links := g.collectLinks(origin, p, k)
			if len(links) != k {
				return nil, false
			}
			// Link i has k-1-i hops strictly below it; each must fit in
			// that link's own budget.
			for i, d := range links {
				if uint64(k-1-i) > d.MaxDepth {
					return nil, false
				}
			}
			return chain, true
		}
		current = best.Granter
	}
	return nil, false
}

// collectLinks replays the chosen chain deterministically, returning the
// delegation objects in issuer→root order for depth-budget checking.
func (g *Graph) collectLinks(issuerPub []byte, p Policy, maxHops int) []*protocol.DelegationClaim {
	current := append([]byte(nil), issuerPub...)
	var links []*protocol.DelegationClaim
	for hop := 0; hop < maxHops; hop++ {
		bestID := ""
		var best *protocol.DelegationClaim
		for id, d := range g.delegations {
			if subtle.ConstantTimeCompare(d.Grantee, current) != 1 || !d.Covers(p.Predicate) {
				continue
			}
			if protocol.DelegationStatusAt(d, p.Now) != protocol.StatusActive {
				continue
			}
			withdrawn := false
			for _, rev := range g.revocations[id] {
				if protocol.VerifyRevocationOfDelegation(rev, d) == nil {
					withdrawn = true
					break
				}
			}
			if withdrawn {
				continue
			}
			if best == nil || d.Serial > best.Serial ||
				(d.Serial == best.Serial && id < bestID) {
				best, bestID = d, id
			}
		}
		if best == nil {
			return nil
		}
		links = append(links, best)
		if addrInAddr(mustAddr(best.Granter), p.TrustedIssuers) {
			return links
		}
		current = best.Granter
	}
	return nil
}

// findApproval collects every valid Allow response from the required approvers,
// bound to a request sent by the claim's issuer with Action == predicate and
// fully verified including the request/response binding and timing window. An
// approval is treated as withdrawn if there is a revocation whose target is the
// response's object id, signed by the responder (the approver revoking their
// own decision). It returns the approving addresses; the caller checks the
// count against the threshold (k-of-n).
func (g *Graph) findApproval(claim *protocol.Claim, claimID string, p Policy) (address.Address, []address.Address, bool) {
	approved := make([]address.Address, 0)
	for rid, resp := range g.responses {
		if resp.Decision != protocol.Allow {
			continue
		}
		respAddr := transport.AddrOf(resp.Responder)
		if !addrIn(respAddr, p.Approvers) || addrIn(respAddr, approved) {
			continue
		}
		reqID := resp.RequestHash.String()
		reqEnv, ok := g.requestEnv[reqID]
		if !ok {
			continue
		}
		req, ok := g.requests[reqID]
		if !ok {
			continue
		}
		// The request must come from the claim's issuer and name the predicate.
		if transport.AddrOf(req.Sender) != transport.AddrOf(claim.Issuer) {
			continue
		}
		if req.Action != p.Predicate {
			continue
		}
		respEnv, ok := g.responseEnv[rid]
		if !ok {
			continue
		}
		if _, err := protocol.VerifyApprovalResponse(reqEnv.TCE, reqEnv.Signature, respEnv.TCE, respEnv.Signature); err != nil {
			continue
		}
		// Withdrawal: a revocation targeting this response, signed by the responder.
		respID := respEnv.ContentID()
		withdrawn := false
		for _, rev := range g.revocations[respID] {
			if rev.ClaimID.String() == respID && subtle.ConstantTimeCompare(rev.Issuer, resp.Responder) == 1 {
				withdrawn = true
				break
			}
		}
		if withdrawn {
			continue
		}
		approved = append(approved, addrToAddress(respAddr))
	}
	need := p.Threshold
	if need <= 0 {
		need = 1
	}
	if len(approved) >= need {
		return approved[0], approved, true
	}
	_ = claimID
	return address.Address{}, nil, false
}

func valueTruthy(v tce.Value) bool {
	if vt, ok := v.Bool(); ok {
		return vt
	}
	return true // non-boolean present values are treated as asserted
}

func addrIn(a string, set []address.Address) bool {
	for _, s := range set {
		if s.String() == a {
			return true
		}
	}
	return false
}

func addrInAddr(a address.Address, set []address.Address) bool {
	for _, s := range set {
		if s.Equal(a) {
			return true
		}
	}
	return false
}

func addrToAddress(s string) address.Address {
	a, _ := address.Parse(s)
	return a
}

func mustAddr(pub []byte) address.Address {
	id, err := identity.FromPubKey(pub)
	if err != nil {
		return address.Address{}
	}
	return id.Address()
}

// defaultMaxRotations bounds key-succession chains when the policy is silent.
const defaultMaxRotations = 4

// resolveRotationChain searches for a sequence of confirmed rotations from
// the claim's issuer up to a trusted root. Every link must be fully verified
// (both signatures plus the hash binding), inside its request window, fresh
// under Policy.RotationMaxAge when set, and unambiguous — competing confirms
// for one request make that link unusable rather than picking a winner.
func (g *Graph) resolveRotationChain(issuerPub []byte, p Policy) ([]address.Address, bool) {
	maxHops := p.MaxDepth
	if maxHops <= 0 {
		maxHops = defaultMaxRotations
	}

	current := append([]byte(nil), issuerPub...)
	chain := []address.Address{mustAddr(current)}

	for hop := 0; hop < maxHops; hop++ {
		reqID := g.findConfirmedRequest(current, p)
		if reqID == "" {
			return nil, false
		}
		req := g.rotRequests[reqID]
		root := mustAddr(req.Predecessor)
		chain = append(chain, root)
		if addrInAddr(root, p.TrustedIssuers) {
			return chain, true
		}
		current = append([]byte(nil), req.Predecessor...)
	}
	return nil, false
}

// findConfirmedRequest returns the id of the newest valid request whose
// successor is current, or "" when none qualifies. Freshness under
// Policy.RotationMaxAge is enforced on the confirm's own timestamp.
func (g *Graph) findConfirmedRequest(successorPub []byte, p Policy) string {
	bestReqID := ""
	var bestConf *rotationConfirm
	for reqID, req := range g.rotRequests {
		if subtle.ConstantTimeCompare(req.Successor, successorPub) != 1 {
			continue
		}
		confirms := g.rotConfirms[reqID]
		if len(confirms) != 1 {
			continue // no consent, or equivocation: unusable either way
		}
		conf := confirms[0]

		// Full binding check against stored bytes.
		reqEnv := g.rotEnv[reqID]
		if _, err := protocol.VerifyKeyRotationConfirm(
			reqEnv.TCE, reqEnv.Signature, conf.env.TCE, conf.env.Signature); err != nil {
			continue
		}
		if !protocol.RotationWindowOK(req, conf.c) {
			continue
		}
		if p.RotationMaxAge > 0 {
			if conf.c.CreatedAt > p.Now && conf.c.CreatedAt-p.Now > protocol.MaxClockSkew {
				continue // dated too far in the future: hostile clock
			}
			if p.Now > conf.c.CreatedAt && p.Now-conf.c.CreatedAt > p.RotationMaxAge+protocol.MaxClockSkew {
				continue // stale: the link no longer counts as recent consent
			}
		}
		if bestConf == nil || conf.id < bestConf.id {
			// Newest request wins on ties of confirm ids; requests carry no
			// serial, so content order is the deterministic fallback.
			bestReqID, bestConf = reqID, conf
		}
	}
	return bestReqID
}