Post 9 — Determinism and Tie-Breaks

The Problem Statement

Our authorization model from Posts 1-8 is powerful and flexible, but there's a critical requirement we haven't fully addressed: determinism. In distributed systems, multiple authorization services might evaluate the same Check request independently. They must produce identical results, or the system becomes unpredictable and unreliable.

Without deterministic evaluation, we risk:

Inconsistent decisions: Service A grants access, Service B denies it
Audit failures: Can't reproduce authorization decisions for compliance
Cache invalidation bugs: Cached results don't match fresh evaluations
Race conditions: Concurrent requests get different answers

Real-world examples from production systems:

Looking at how distributed authorization systems ensure consistency reveals critical requirements:

Google Zanzibar: Deterministic evaluation across globally distributed replicas
AWS IAM: Policy evaluation must be consistent across all regions
Auth0 FGA: Multiple authorization servers must agree on decisions
Ory Keto: Distributed permission checks require deterministic semantics

Common patterns that require determinism:

Distributed authorization: Multiple services evaluate same request
Caching: Cached results must match fresh evaluations
Audit compliance: Must reproduce historical decisions exactly
Testing: Same inputs must always produce same outputs

What we can't guarantee today:
"Two authorization services evaluating the same Check request must always return the same result."

Our current model has ambiguities:

❌ Multiple tuples could grant access — which one wins?
❌ Different caveats return REQUIRES_CONTEXT — which missing params to report?
❌ Schema evolution changes tuple order — does evaluation order matter?
❌ Tri-state logic combinations — how to break ties?

The core problem: We need deterministic tie-breaking rules that ensure two evaluators always converge on the same answer, regardless of implementation details or evaluation order.

Human Rule

❝

"Same inputs → same outputs."

Two authorization services evaluating the same Check request must always return the same result, regardless of implementation details, evaluation order, or database tuple ordering.

Why Current Models Don't Work

Let's try to ensure deterministic evaluation using our existing tools from Posts 1-8.

What We Have So Far (Post 1-8 Recap)

From previous posts, we have:

From Post 5: Tri-state caveat evaluation:

type CaveatEvalResult int32
const (
    CAV_FALSE            CaveatEvalResult = iota  // Condition failed
    CAV_TRUE                                      // Condition passed
    CAV_REQUIRES_CONTEXT                          // Need more parameters
)

From Post 7: Boolean algebra with short-circuit evaluation:

// AND: Stop at first FALSE
// OR: Stop at first TRUE
// NOT: Negate result

From Post 4: Graph traversal with multiple paths:

// Multiple tuples could grant access:
// - Direct tuple: user:alice → document:1#viewer
// - Via role: user:alice → role:admin#member → document:1#viewer
// - Via group: user:alice → group:staff#member → document:1#viewer

What's missing: No rules for which result to return when multiple paths exist!

Approach 1: Return First Result (Non-Deterministic)

// Attempt: Return the first result found

func Check(resource, subject, context) bool {
    tuples := FindTuples(resource, subject)
    
    for tuple := range tuples {
        result := EvaluateTuple(tuple, context)
        if result.Granted {
            return true  // ← Return first granted result
        }
    }
    
    return false
}

Problems:

❌ Order-dependent: Result depends on tuple iteration order
❌ Database-dependent: Different databases return tuples in different orders
❌ Non-reproducible: Same request might get different results
❌ Cache inconsistency: Cached result might not match fresh evaluation

Example failure:

// Database A returns tuples in order: [tuple1, tuple2, tuple3]
// Database B returns tuples in order: [tuple3, tuple2, tuple1]

// If tuple1 grants access but tuple3 denies:
// Database A: TRUE (found tuple1 first)
// Database B: FALSE (found tuple3 first, stopped early)
// → INCONSISTENT! ❌

Approach 2: Evaluate All, Return Any TRUE (Ambiguous)

// Attempt: Evaluate all tuples, return TRUE if any grants access

func Check(resource, subject, context) bool {
    tuples := FindTuples(resource, subject)
    
    for tuple := range tuples {
        result := EvaluateTuple(tuple, context)
        if result.Granted {
            return true  // ← Any TRUE wins
        }
    }
    
    return false
}

Problems:

❌ Missing params ambiguity: Which REQUIRES_CONTEXT to return?
❌ Audit trail unclear: Which tuple granted access?
❌ No tie-break for partial results: Multiple REQUIRES_CONTEXT with different missing params

Example failure:

// Tuple 1: REQUIRES_CONTEXT (missing: ["user.department"])
// Tuple 2: REQUIRES_CONTEXT (missing: ["user.clearance_level", "user.is_suspended"])
// Tuple 3: FALSE

// Which missing params should we report?
// Option A: ["user.department"] (fewer params)
// Option B: ["user.clearance_level", "user.is_suspended"]
// → AMBIGUOUS! ❌

Approach 3: Canonical Ordering (Incomplete)

// Attempt: Sort tuples by some canonical order

func Check(resource, subject, context) bool {
    tuples := FindTuples(resource, subject)
    
    // Sort by... what?
    sort.Slice(tuples, func(i, j int) bool {
        // ??? How to compare tuples deterministically?
        return tuples[i].Subject.Signature() < tuples[j].Subject.Signature()
    })
    
    for tuple := range tuples {
        result := EvaluateTuple(tuple, context)
        if result.Granted {
            return true
        }
    }
    
    return false
}

Problems:

❌ Signature collisions: Different subjects might have same signature
❌ Incomplete ordering: What if signatures are equal?
❌ Doesn't handle tri-state: Still ambiguous for REQUIRES_CONTEXT results
❌ Performance: Sorting adds overhead

Conclusion: We need comprehensive deterministic rules that cover all cases: tuple ordering, result prioritization, and tie-breaking for partial results.

The Solution: Deterministic Evaluation Semantics

We define a complete set of rules that ensure deterministic evaluation across all scenarios.

Part 1: Canonical Subject Signatures

Every subject must have a unique, deterministic signature that serves as a stable identifier.

Subject signature format:

type Subject interface {
    Signature() string  // Canonical, deterministic representation
}

// DirectSubject signature
func (s *DirectSubject) Signature() string {
    if s.Caveat == nil {
        return fmt.Sprintf("%s:%s", s.Object.Namespace, s.Object.ObjectID)
    }
    return fmt.Sprintf("%s:%s[%s]", s.Object.Namespace, s.Object.ObjectID, s.Caveat.Signature())
}

// SubjectSet signature
func (s *SubjectSet) Signature() string {
    if s.Caveat == nil {
        return fmt.Sprintf("%s:%s#%s", s.Object.Namespace, s.Object.ObjectID, s.Relation)
    }
    return fmt.Sprintf("%s:%s#%s[%s]", s.Object.Namespace, s.Object.ObjectID, s.Relation, s.Caveat.Signature())
}

// WildcardSubject signature
func (s *WildcardSubject) Signature() string {
    if s.Caveat == nil {
        return fmt.Sprintf("%s:*", s.SubjectNamespace)
    }
    return fmt.Sprintf("%s:*[%s]", s.SubjectNamespace, s.Caveat.Signature())
}

Caveat signature (deterministic):

func (c *ContextualizedCaveat) Signature() string {
    if c == nil {
        return ""
    }
    
    // Sort context keys for determinism
    keys := make([]string, 0, len(c.Context.Values))
    for k := range c.Context.Values {
        keys = append(keys, k)
    }
    sort.Strings(keys)
    
    // Build signature: caveat_name{key1=val1,key2=val2}
    parts := []string{c.CaveatName}
    if len(keys) > 0 {
        contextParts := make([]string, len(keys))
        for i, k := range keys {
            contextParts[i] = fmt.Sprintf("%s=%v", k, c.Context.Values[k])
        }
        parts = append(parts, "{"+strings.Join(contextParts, ",")+"}")
    }
    
    return strings.Join(parts, "")
}

Examples:

// DirectSubject without caveat
user:alice → "user:alice"

// DirectSubject with caveat
user:alice[business_hours] → "user:alice[business_hours]"

// DirectSubject with caveat + context
user:alice[ip_restriction{allowed_ips=[10.0.0.1]}] → "user:alice[ip_restriction{allowed_ips=[10.0.0.1]}]"

// SubjectSet
role:admin#member → "role:admin#member"

// WildcardSubject
user:* → "user:*"
user:*[department_match] → "user:*[department_match]"

Key properties:

✅ Unique: Different subjects have different signatures
✅ Deterministic: Same subject always produces same signature
✅ Sortable: Lexicographic ordering is well-defined
✅ Stable: Signature doesn't change across evaluations

Part 2: Result Prioritization Rules

When multiple evaluation paths exist, we prioritize results in this order:

Priority 1: TRUE (Access Granted)

If ANY path returns TRUE → return TRUE

Priority 2: REQUIRES_CONTEXT (Partial Information)

If NO path returns TRUE and ANY path returns REQUIRES_CONTEXT → return REQUIRES_CONTEXT

Priority 3: FALSE (Access Denied)

If ALL paths return FALSE → return FALSE

Rationale:

TRUE wins: If access can be granted, grant it (union semantics)
REQUIRES_CONTEXT is informative: Tell caller what's needed
FALSE is default: Deny access if no path succeeds

Algorithm:

ALGORITHM: SelectBestResult(results)

INPUT: List of EvaluationResult from different paths

OUTPUT: Single EvaluationResult to return

STEPS:
1. Separate results by type:
   granted = results where CaveatResult == CAV_TRUE
   partial = results where CaveatResult == CAV_REQUIRES_CONTEXT
   denied  = results where CaveatResult == CAV_FALSE

2. IF granted is not empty:
     RETURN SelectBestGranted(granted)  // See Part 3

3. IF partial is not empty:
     RETURN SelectBestPartial(partial)  // See Part 4

4. ELSE:
     RETURN SelectBestDenied(denied)    // See Part 5

Part 3: Tie-Breaking for TRUE Results

When multiple paths grant access, we need a deterministic tie-break to choose which one to return (for audit purposes).

Rule: Choose the result with the lexicographically smallest subject signature.

ALGORITHM: SelectBestGranted(grantedResults)

INPUT: List of results where CaveatResult == CAV_TRUE

OUTPUT: Single result with smallest subject signature

STEPS:
1. Sort results by subject signature (lexicographic order)
2. RETURN first result (smallest signature)

Example:

// Three paths grant access:
// Path A: user:alice → document:1#viewer (signature: "user:alice")
// Path B: role:admin#member → document:1#viewer (signature: "role:admin#member")
// Path C: user:bob → document:1#viewer (signature: "user:bob")

// Lexicographic order: "role:admin#member" < "user:alice" < "user:bob"
// Winner: Path B (role:admin#member)

Rationale:

✅ Deterministic: Lexicographic order is well-defined
✅ Stable: Same paths always produce same winner
✅ Auditable: Can trace which path granted access
✅ Simple: No complex tie-breaking logic

Part 4: Tie-Breaking for REQUIRES_CONTEXT Results

When multiple paths return REQUIRES_CONTEXT, we choose the one with the fewest missing parameters (minimal missing-set tie-break).

Rule: Choose the result with the smallest set of missing parameters.

ALGORITHM: SelectBestPartial(partialResults)

INPUT: List of results where CaveatResult == CAV_REQUIRES_CONTEXT

OUTPUT: Single result with fewest missing parameters

STEPS:
1. For each result, count missing parameters
2. Sort by missing parameter count (ascending)
3. IF multiple results have same count:
     a. Sort missing parameter names lexicographically
     b. Compare missing sets lexicographically
4. RETURN first result (fewest missing params, or lexicographically smallest set)

Example 1: Different counts

// Three paths return REQUIRES_CONTEXT:
// Path A: missing ["user.department", "user.clearance_level"]  (count: 2)
// Path B: missing ["user.is_suspended"]                        (count: 1)
// Path C: missing ["user.department", "user.is_suspended", "user.employment_type"]  (count: 3)

// Winner: Path B (fewest missing params)

Example 2: Same count, lexicographic tie-break

// Two paths return REQUIRES_CONTEXT with same count:
// Path A: missing ["user.clearance_level"]
// Path B: missing ["user.department"]

// Lexicographic order: "clearance_level" < "department"
// Winner: Path A

Example 3: Same count, multiple params

// Two paths return REQUIRES_CONTEXT:
// Path A: missing ["user.clearance_level", "user.is_suspended"]
// Path B: missing ["user.department", "user.employment_type"]

// Sort each set: ["clearance_level", "is_suspended"] vs ["department", "employment_type"]
// Compare lexicographically: "clearance_level" < "department"
// Winner: Path A

Rationale:

✅ User-friendly: Ask for minimal information
✅ Efficient: Fewer parameters to fetch
✅ Deterministic: Count + lexicographic order is well-defined
✅ Practical: Helps caller find "cheapest" path to access

Part 5: Tie-Breaking for FALSE Results

When all paths deny access, we still need a deterministic choice (for audit purposes).

Rule: Choose the result with the lexicographically smallest subject signature.

ALGORITHM: SelectBestDenied(deniedResults)

INPUT: List of results where CaveatResult == CAV_FALSE

OUTPUT: Single result with smallest subject signature

STEPS:
1. Sort results by subject signature (lexicographic order)
2. RETURN first result (smallest signature)

Rationale:

✅ Deterministic: Same as TRUE tie-break
✅ Consistent: Same ordering rule across all result types
✅ Auditable: Can trace which path was checked

Part 6: Schema-Defined Evaluation Order

For operations that combine multiple children (UNION, INTERSECTION, EXCLUSION), evaluation order must be deterministic.

Rule: Evaluate children in schema definition order (left-to-right).

// Schema defines order
&UnionExpression{
    Children: []SubjectsComputationExpression{
        &DirectExpression{},              // ← Evaluated FIRST
        &ComputedSubjectsExpression{...}, // ← Evaluated SECOND
        &EdgeExpression{...},             // ← Evaluated THIRD
    },
}

// Evaluation MUST follow this order
func EvaluateUnion(expr *UnionExpression, ...) {
    for i, child := range expr.Children {
        result := EvaluateChild(child, ...)  // ← Left-to-right order
        // ...
    }
}

Important: Implementations MUST NOT reorder children for optimization.

Rationale:

✅ Deterministic: Schema defines canonical order
✅ Predictable: Same schema always evaluates in same order
✅ Testable: Can verify evaluation order in tests
✅ Auditable: Evaluation trace matches schema structure

Trade-off: Can't optimize by reordering (e.g., evaluating cheaper children first), but determinism is more important than performance.

Part 7: Signature Stability Guarantees

Subject signatures must remain stable across schema evolution to prevent cache invalidation storms.

Stability rules:

Schema changes don't affect signatures
- Adding RequiredCaveat → signature unchanged
- Removing relation → signature unchanged (for other relations)
- Renaming caveat → signature changes (breaking change)
Caveat context order is deterministic
- Context keys sorted lexicographically (line 250)
- Same context always produces same signature
Signature format is versioned
- Current format: namespace:objectID#relation[caveat{k1=v1,k2=v2}]
- Future formats must be backward-compatible or require migration

Example:

// Schema v1: No RequiredCaveat
subject := &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}}
sig1 := subject.Signature()  // "user:alice"

// Schema v2: Add RequiredCaveat to document#viewer
// Subject signature UNCHANGED
sig2 := subject.Signature()  // "user:alice" (same!)

// Cache remains valid ✅

Why this matters:

In production systems with millions of cached authorization decisions, schema evolution is common (adding new relations, new caveats, new constraints). If subject signatures changed with every schema update, we'd invalidate all caches simultaneously, causing:

Cache stampede: All clients re-evaluate permissions at once
Database overload: Sudden spike in tuple lookups
Latency spike: Authorization checks become slow
Cascading failures: Downstream services timeout

Signature stability ensures graceful schema evolution — caches remain valid, performance stays consistent, and deployments are safe.

Real-World Example: Multi-Tenant SaaS Platform

Let's build a complete example for a multi-tenant SaaS platform with multiple authorization paths.

Requirements

Access Policy:

"Users can access documents if:

They are direct viewers (highest priority)
They are members of a viewer group (medium priority)
They are in the same organization with wildcard access (lowest priority)"

Schema Definition

// Document namespace
documentNS := &NamespaceDefinition{
    Name: "document",
    Relations: map[string]*NamespaceRelationDefinition{
        "viewer": {
            Name: "viewer",
            SubjectsComputationExpression: &UnionExpression{
                Children: []SubjectsComputationExpression{
                    // Path 1: Direct viewers
                    &DirectExpression{},
                    // Path 2: Viewer groups
                    &ComputedSubjectsExpression{ComputedRelation: "viewer_group"},
                    // Path 3: Organization wildcard
                    &DirectExpression{},  // Allows wildcard subjects
                },
            },
            SubjectConstraints: &SubjectConstraints{
                AllowedSubjectTypes: []AllowedSubjectType{
                    &AllowedDirectSubject{Namespace: "user"},
                    &AllowedSubjectSet{Namespace: "group", Relation: "member"},
                    &AllowedWildcardSubject{
                        Namespace:      "user",
                        RequiredCaveat: "same_organization",
                    },
                },
            },
        },
        "viewer_group": {
            Name: "viewer_group",
            SubjectsComputationExpression: &DirectExpression{},
        },
    },
}

// Caveat: same organization
sameOrg := &CaveatDefinition{
    Name: "same_organization",
    Parameters: []CaveatParameter{
        &ScalarParameter{Name: "user.organization_id", Type: CAV_T_STRING},
        &ScalarParameter{Name: "document.organization_id", Type: CAV_T_STRING},
    },
    Expression: &BooleanExpr{
        Op: BOOL_PREDICATE,
        Pred: &Predicate{
            Left:  &IdentifierExpr{Name: "user.organization_id"},
            Op:    CMP_EQ,
            Right: &IdentifierExpr{Name: "document.organization_id"},
        },
    },
}

Tuple Setup

// Path 1: Alice is direct viewer
tuple1 := &RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "document", ObjectID: "doc-123", Relation: "viewer"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}},
}

// Path 2: Bob is member of viewer group
tuple2 := &RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "document", ObjectID: "doc-123", Relation: "viewer_group"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "group", ObjectID: "engineering"}},
}
tuple3 := &RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "group", ObjectID: "engineering", Relation: "member"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "bob"}},
}

// Path 3: Wildcard for organization
tuple4 := &RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "document", ObjectID: "doc-123", Relation: "viewer"},
    Subject: &WildcardSubject{
        SubjectNamespace: "user",
        Caveat: &ContextualizedCaveat{
            CaveatName: "same_organization",
            Context: &CaveatContext{
                Values: map[string]any{
                    "document.organization_id": "org-acme",
                },
            },
        },
    },
}

Evaluation Scenarios

Scenario 1: Alice (direct viewer) — TRUE wins

ctx := NewCaveatContext()
result := Check(document:doc-123#viewer, user:alice, ctx)

// Evaluation:
// Path 1 (direct): user:alice → TRUE ✅
// Path 2 (group): user:alice not in group → FALSE
// Path 3 (wildcard): user:alice matches user:* → REQUIRES_CONTEXT (missing org_id)

// Results:
// - TRUE: [Path 1]
// - REQUIRES_CONTEXT: [Path 3]
// - FALSE: [Path 2]

// Winner: Path 1 (TRUE has highest priority)
// Result: TRUE ✅

Scenario 2: Bob (via group) — TRUE wins

ctx := NewCaveatContext()
result := Check(document:doc-123#viewer, user:bob, ctx)

// Evaluation:
// Path 1 (direct): user:bob not direct viewer → FALSE
// Path 2 (group): user:bob → group:engineering#member → TRUE ✅
// Path 3 (wildcard): user:bob matches user:* → REQUIRES_CONTEXT (missing org_id)

// Results:
// - TRUE: [Path 2]
// - REQUIRES_CONTEXT: [Path 3]
// - FALSE: [Path 1]

// Winner: Path 2 (TRUE has highest priority)
// Result: TRUE ✅

Scenario 3: Charlie (wildcard only) — REQUIRES_CONTEXT

ctx := NewCaveatContext()
result := Check(document:doc-123#viewer, user:charlie, ctx)

// Evaluation:
// Path 1 (direct): user:charlie not direct viewer → FALSE
// Path 2 (group): user:charlie not in group → FALSE
// Path 3 (wildcard): user:charlie matches user:* → REQUIRES_CONTEXT (missing org_id)

// Results:
// - TRUE: []
// - REQUIRES_CONTEXT: [Path 3]
// - FALSE: [Path 1, Path 2]

// Winner: Path 3 (REQUIRES_CONTEXT has priority over FALSE)
// Result: REQUIRES_CONTEXT
// Missing: ["user.organization_id"]

Scenario 4: Charlie with org_id — TRUE or FALSE

// Case A: Same organization
ctx := NewCaveatContext()
ctx.SetValue("user.organization_id", "org-acme")
result := Check(document:doc-123#viewer, user:charlie, ctx)

// Path 3 (wildcard): same_organization → TRUE ✅
// Result: TRUE ✅

// Case B: Different organization
ctx.SetValue("user.organization_id", "org-other")
result := Check(document:doc-123#viewer, user:charlie, ctx)

// Path 3 (wildcard): same_organization → FALSE ❌
// Result: FALSE ❌

Scenario 5: Multiple TRUE paths — Deterministic tie-break

// Setup: Alice is BOTH direct viewer AND in group
tuple5 := &RelationTuple{
    Resource: &ObjectAndRelation{Namespace: "group", ObjectID: "engineering", Relation: "member"},
    Subject:  &DirectSubject{Object: &ObjectRef{Namespace: "user", ObjectID: "alice"}},
}

ctx := NewCaveatContext()
result := Check(document:doc-123#viewer, user:alice, ctx)

// Evaluation:
// Path 1 (direct): user:alice → TRUE (signature: "user:alice")
// Path 2 (group): user:alice → group:engineering#member → TRUE (signature: "group:engineering#member")

// Results:
// - TRUE: [Path 1 (user:alice), Path 2 (group:engineering#member)]

// Tie-break: Lexicographic order
// "group:engineering#member" < "user:alice"
// Winner: Path 2 (group:engineering#member)

// Result: TRUE ✅
// Audit: Access granted via group:engineering#member

Design Decisions

Decision 1: Union Semantics (TRUE Wins)

Question: Should we use union (any TRUE wins) or intersection (all must be TRUE)?

Answer: Union semantics — any path granting access is sufficient.

Rationale:

Union (chosen):

If ANY path returns TRUE → grant access

Benefits:

✅ Flexible: Multiple ways to grant access
✅ User-friendly: Don't need all paths to succeed
✅ Matches intuition: "Alice can access if she's a viewer OR in a viewer group"
✅ Aligns with UNION expression: Schema semantics match evaluation semantics

Intersection (rejected):

If ALL paths return TRUE → grant access

Problems:

❌ Too restrictive: Would require satisfying all paths simultaneously
❌ Confusing: "Alice must be a direct viewer AND in a group" doesn't make sense
❌ Breaks schema semantics: UNION expression would behave like INTERSECTION

Note: For actual intersection semantics, use IntersectionExpression in schema.

Decision 2: Minimal Missing-Set Tie-Break

Question: When multiple paths return REQUIRES_CONTEXT, which one to return?

Answer: Prefer fewest missing parameters — minimize caller burden.

Rationale:

Minimal missing-set (chosen):

Choose path with fewest missing parameters

Benefits:

✅ User-friendly: Ask for minimal information
✅ Efficient: Fewer parameters to fetch from external systems
✅ Practical: Helps caller find "cheapest" path to access
✅ Deterministic: Count + lexicographic order is well-defined

Alternative: First path (rejected):

Return first REQUIRES_CONTEXT encountered

Problems:

❌ Order-dependent: Result depends on evaluation order
❌ Suboptimal: Might ask for more params than necessary
❌ Less helpful: Doesn't guide caller to best path

Alternative: All missing params (rejected):

Return union of all missing parameters

Problems:

❌ Overly conservative: Asks for params that might not be needed
❌ Confusing: Caller doesn't know which params are for which path
❌ Inefficient: Might fetch unnecessary data

Decision 3: Lexicographic Tie-Breaking

Question: How to break ties when multiple results have same priority?

Answer: Lexicographic order on subject signatures — simple and deterministic.

Rationale:

Lexicographic (chosen):

Sort by subject signature (string comparison)

Benefits:

✅ Deterministic: String comparison is well-defined
✅ Simple: No complex tie-breaking logic
✅ Stable: Same subjects always sort in same order
✅ Language-agnostic: Works in any programming language

Alternative: Tuple creation time (rejected):

Sort by tuple creation timestamp

Problems:

❌ Not snapshot-isolated: Different snapshots might have different timestamps
❌ Clock skew: Distributed systems have clock synchronization issues
❌ Not reproducible: Historical evaluations can't be reproduced

Alternative: Random (rejected):

Choose random result

Problems:

❌ Non-deterministic: Different evaluators get different results
❌ Not reproducible: Can't reproduce authorization decisions
❌ Breaks caching: Cached result doesn't match fresh evaluation

Edge Cases and Safety

Edge Case 1: Signature Collisions

Problem: What if two different subjects have the same signature?

Solution: This is a schema validation error — signatures must be unique.

Prevention:

func ValidateSubjectUniqueness(tuples []*RelationTuple) error {
    seen := make(map[string]bool)
    for _, tuple := range tuples {
        sig := tuple.Subject.Signature()
        if seen[sig] {
            return fmt.Errorf("duplicate subject signature: %s", sig)
        }
        seen[sig] = true
    }
    return nil
}

Note: In practice, signature collisions are extremely rare because signatures include namespace, object ID, relation, and caveat details.

Edge Case 2: Empty Result Set

Problem: What if no tuples match the query?

Solution: Return FALSE (deny access).

func Check(resource, subject, context) bool {
    tuples := FindTuples(resource, subject)

    if len(tuples) == 0 {
        return FALSE  // No tuples → deny access
    }

    // ... evaluate tuples
}

Rationale:

✅ Fail-safe: No evidence of access → deny
✅ Explicit grant: Access must be explicitly granted
✅ Secure default: Better to deny than accidentally grant

Edge Case 3: All Paths Return REQUIRES_CONTEXT

Problem: What if all paths need more parameters?

Solution: Return the path with fewest missing parameters.

// All paths return REQUIRES_CONTEXT:
// Path A: missing ["user.department"]
// Path B: missing ["user.clearance_level", "user.is_suspended"]
// Path C: missing ["user.organization_id"]

// Winner: Path A or C (both have 1 missing param)
// Tie-break: Lexicographic order on param names
// "department" < "organization_id"
// Winner: Path A

// Result: REQUIRES_CONTEXT
// Missing: ["user.department"]

Edge Case 4: Caveat Context Conflicts

Problem: What if different paths pre-bind the same parameter to different values?

Solution: Each path has its own context; no conflict.

// Path 1: Pre-binds document.classification = "public"
// Path 2: Pre-binds document.classification = "confidential"

// These are DIFFERENT paths with DIFFERENT contexts
// No conflict — each path is evaluated independently

Note: Context merging only happens when combining schema caveat + tuple caveat (Post 8), not across different paths.

Edge Case 5: Signature Length Limits

Problem: Caveat context could be arbitrarily large, making signatures megabytes long.

Example:

// IP allowlist with 10,000 IPs
user:alice[ip_restriction{allowed_ips=[1.1.1.1, 1.1.1.2, ..., 10.0.0.0]}]

// Signature could be 500KB+!
// → Performance degradation (string comparison, storage, network)
// → Memory pressure (caching millions of signatures)

Solution: Limit signature length and hash long contexts.

Implementation:

const MaxSignatureLength = 4096  // 4KB

func (c *ContextualizedCaveat) Signature() string {
    sig := c.computeSignature()

    if len(sig) > MaxSignatureLength {
        // Hash long signatures
        hash := sha256.Sum256([]byte(sig))
        return fmt.Sprintf("%s{hash:%x}", c.CaveatName, hash[:16])
    }

    return sig
}

func (c *ContextualizedCaveat) computeSignature() string {
    if c == nil {
        return ""
    }

    // Sort context keys for determinism
    keys := make([]string, 0, len(c.Context.Values))
    for k := range c.Context.Values {
        keys = append(keys, k)
    }
    sort.Strings(keys)

    // Build signature: caveat_name{key1=val1,key2=val2}
    parts := []string{c.CaveatName}
    if len(keys) > 0 {
        contextParts := make([]string, len(keys))
        for i, k := range keys {
            contextParts[i] = fmt.Sprintf("%s=%v", k, c.Context.Values[k])
        }
        parts = append(parts, "{"+strings.Join(contextParts, ",")+"}")
    }

    return strings.Join(parts, "")
}

Trade-off: Hashing reduces readability but prevents performance degradation.

Collision risk: With SHA-256 truncated to 128 bits, collision probability is negligible:

1 million tuples: ~10^-20 probability
1 billion tuples: ~10^-14 probability
Birthday paradox applies, but still astronomically unlikely

When to use hashing:

IP allowlists with 100+ entries
Large JSON metadata objects
Complex nested context structures

When NOT to use hashing:

Simple contexts (1-5 parameters)
Human-readable audit trails (prefer full signature)

Edge Case 6: Lexicographic Ordering Across Languages

Problem: Different programming languages might sort strings differently.

Example:

// UTF-8 byte-order comparison (correct)
"user:alice" < "user:älice"  // 0x61 < 0xC3 (UTF-8 bytes)

// Locale-specific collation (wrong)
// German locale: "ä" sorts after "a" but before "b"
// Swedish locale: "ä" sorts after "z"
// → Different languages get different results! ❌

Solution: Use UTF-8 byte-order comparison (not locale-specific collation).

Implementation requirements:

// Go: Use standard string comparison (already byte-order)
"user:alice" < "user:älice"  // ✅ Correct

// Python: Use standard string comparison (already byte-order)
"user:alice" < "user:älice"  # ✅ Correct

// JavaScript: Use standard string comparison (already byte-order)
"user:alice" < "user:älice"  // ✅ Correct

// Rust: Use standard string comparison (already byte-order)
"user:alice" < "user:älice"  // ✅ Correct

What to avoid:

// ❌ Don't use locale-aware collation
import "golang.org/x/text/collate"
collator := collate.New(language.German)
collator.CompareString("user:alice", "user:älice")  // ❌ Wrong!

// ❌ Don't use case-insensitive comparison
strings.ToLower("user:Alice") == strings.ToLower("user:alice")  // ❌ Wrong!

Why this matters:

In distributed systems with multi-language implementations (Go backend, Python SDK, JavaScript frontend), all implementations must agree on ordering. Using locale-specific collation would break determinism across language boundaries.

Edge Case 7: Signature Computation Failure

Problem: What if caveat context contains non-serializable values?

Example:

// Function pointer in context
ctx.Values["user.callback"] = func() { ... }

// Signature() panics? Returns error? Skips this path?

Solution: Fail-safe default — treat non-serializable context as FALSE.

Implementation:

func (c *ContextualizedCaveat) Signature() string {
    defer func() {
        if r := recover(); r != nil {
            // Panic during signature computation → return error signature
            log.Errorf("Signature computation failed: %v", r)
        }
    }()

    // Attempt to compute signature
    return c.computeSignature()
}

func formatValue(v any) (string, error) {
    switch val := v.(type) {
    case string, int, int64, float64, bool:
        return fmt.Sprintf("%v", val), nil
    case []any, map[string]any:
        // Serialize complex types as JSON
        bytes, err := json.Marshal(val)
        if err != nil {
            return "", fmt.Errorf("failed to serialize: %w", err)
        }
        return string(bytes), nil
    default:
        // Non-serializable type
        return "", fmt.Errorf("unsupported type: %T", val)
    }
}

Rationale:

✅ Fail-safe: Non-serializable context → deny access (secure default)
✅ Debuggable: Log error for investigation
✅ Deterministic: Same non-serializable value always fails the same way

Implementation Notes

Performance Considerations

1. Early Termination on TRUE

Once we find a TRUE result, we can stop evaluating other paths:

func Check(resource, subject, context) bool {
    tuples := FindTuples(resource, subject)

    for tuple := range tuples {
        result := EvaluateTuple(tuple, context)
        if result.CaveatResult == CAV_TRUE {
            return TRUE  // ← Early termination
        }
    }

    // ... continue with REQUIRES_CONTEXT and FALSE
}

2. Lazy Evaluation

Don't evaluate all paths if we can determine the result early:

// If we find TRUE, stop immediately
// If we find REQUIRES_CONTEXT, continue (might find TRUE later)
// Only evaluate all paths if all return FALSE

3. Signature Caching

Cache subject signatures to avoid recomputing:

type CachedSubject struct {
    Subject   Subject
    Signature string  // Cached
}

func (s *CachedSubject) GetSignature() string {
    if s.Signature == "" {
        s.Signature = s.Subject.Signature()
    }
    return s.Signature
}

Testing Strategies

1. Determinism Tests

Verify that same inputs always produce same outputs:

func TestDeterminism_SameInputsSameOutputs(t *testing.T) {
    // Run check 100 times with same inputs
    for i := 0; i < 100; i++ {
        result := Check(document:1#viewer, user:alice, ctx)
        assert.Equal(t, expectedResult, result)
    }
}

2. Tie-Break Tests

Verify tie-breaking rules:

func TestTieBreak_LexicographicOrder(t *testing.T) {
    // Create tuples with different subject signatures
    tuple1 := &RelationTuple{Subject: user:alice}    // "user:alice"
    tuple2 := &RelationTuple{Subject: user:bob}      // "user:bob"
    tuple3 := &RelationTuple{Subject: role:admin#member}  // "role:admin#member"

    // All grant access
    // Expected winner: "role:admin#member" (lexicographically smallest)
    result := Check(document:1#viewer, ...)
    assert.Equal(t, "role:admin#member", result.WinningPath)
}

3. Minimal Missing-Set Tests

Verify that we choose path with fewest missing params:

func TestMinimalMissingSet_FewestParams(t *testing.T) {
    // Path A: missing 2 params
    // Path B: missing 1 param
    // Path C: missing 3 params

    result := Check(document:1#viewer, user:alice, ctx)
    assert.Equal(t, CAV_REQUIRES_CONTEXT, result.CaveatResult)
    assert.Equal(t, 1, len(result.MissingParams))  // Path B wins
}

4. Property-Based Tests

Verify invariants hold across random inputs:

func TestProperty_DeterminismAcrossEvaluators(t *testing.T) {
    // Property: Two independent evaluators always agree
    for i := 0; i < 1000; i++ {
        // Generate random tuples, context, query
        tuples := GenerateRandomTuples()
        ctx := GenerateRandomContext()
        query := GenerateRandomQuery()

        // Evaluate on two independent evaluators
        evaluator1 := NewEvaluator(tuples)
        evaluator2 := NewEvaluator(tuples)

        result1 := evaluator1.Check(query, ctx)
        result2 := evaluator2.Check(query, ctx)

        // Must be identical
        assert.Equal(t, result1.CaveatResult, result2.CaveatResult)
        assert.Equal(t, result1.WinningPath, result2.WinningPath)
        assert.Equal(t, result1.MissingParams, result2.MissingParams)
    }
}

func TestProperty_SignatureStability(t *testing.T) {
    // Property: Signatures don't change across schema versions
    subject := &DirectSubject{
        Object: &ObjectRef{Namespace: "user", ObjectID: "alice"},
    }

    // Compute signature with schema v1
    sig1 := subject.Signature()

    // Upgrade schema to v2 (add RequiredCaveat to some relation)
    schema.AddRequiredCaveat("document", "viewer", "business_hours")

    // Subject signature must be unchanged
    sig2 := subject.Signature()
    assert.Equal(t, sig1, sig2, "Signature changed after schema evolution")
}

func TestProperty_NoSignatureCollisions(t *testing.T) {
    // Property: No collisions in realistic workload
    signatures := make(map[string]bool)

    for i := 0; i < 1_000_000; i++ {
        tuple := GenerateRandomTuple()
        sig := tuple.Subject.Signature()

        if signatures[sig] {
            t.Fatalf("Collision detected at iteration %d: %s", i, sig)
        }
        signatures[sig] = true
    }

    t.Logf("Generated %d unique signatures without collisions", len(signatures))
}

Cross-Language Compatibility

Challenge: Go, Python, Rust, JavaScript implementations must produce identical signatures.

Requirements:

1. UTF-8 byte-order comparison (not locale-specific collation)

// Correct: Byte-order comparison
"user:alice" < "user:älice"  // 0x61 < 0xC3 (UTF-8 bytes)

// Wrong: Locale-specific collation
// Some locales might sort "ä" before "a"

2. IEEE 754 float formatting

// Context value: 3.14159
// All languages must format as: "3.14159"
// NOT: "3.14" (truncated)
// NOT: "3.141590" (extra zeros)

// Use consistent precision (e.g., 6 decimal places)
fmt.Sprintf("%.6f", 3.14159)  // "3.141590"

3. Boolean formatting

// Context value: true
// All languages must format as: "true" (lowercase)
// NOT: "True" (Python default)
// NOT: "TRUE" (uppercase)

4. Null/nil handling

// Context value: nil
// All languages must format as: "null"
// NOT: "nil" (Go)
// NOT: "None" (Python)
// NOT: "" (empty string)

5. Reference test vectors

Provide canonical test cases for cross-language validation:

var SignatureTestVectors = []struct {
    Name              string
    Subject           Subject
    ExpectedSignature string
}{
    {
        Name: "DirectSubject without caveat",
        Subject: &DirectSubject{
            Object: &ObjectRef{Namespace: "user", ObjectID: "alice"},
        },
        ExpectedSignature: "user:alice",
    },
    {
        Name: "DirectSubject with caveat (no context)",
        Subject: &DirectSubject{
            Object: &ObjectRef{Namespace: "user", ObjectID: "alice"},
            Caveat: &ContextualizedCaveat{CaveatName: "business_hours"},
        },
        ExpectedSignature: "user:alice[business_hours]",
    },
    {
        Name: "DirectSubject with caveat (sorted context)",
        Subject: &DirectSubject{
            Object: &ObjectRef{Namespace: "user", ObjectID: "alice"},
            Caveat: &ContextualizedCaveat{
                CaveatName: "ip_restriction",
                Context: &CaveatContext{
                    Values: map[string]any{
                        "allowed_ips": []string{"10.0.0.1", "10.0.0.2"},
                        "region":      "us-west",
                    },
                },
            },
        },
        // Keys sorted: "allowed_ips" < "region"
        ExpectedSignature: `user:alice[ip_restriction{allowed_ips=["10.0.0.1","10.0.0.2"],region=us-west}]`,
    },
    {
        Name: "SubjectSet",
        Subject: &SubjectSet{
            Object:   &ObjectRef{Namespace: "role", ObjectID: "admin"},
            Relation: "member",
        },
        ExpectedSignature: "role:admin#member",
    },
    {
        Name: "WildcardSubject",
        Subject: &WildcardSubject{
            SubjectNamespace: "user",
        },
        ExpectedSignature: "user:*",
    },
    {
        Name: "WildcardSubject with caveat",
        Subject: &WildcardSubject{
            SubjectNamespace: "user",
            Caveat: &ContextualizedCaveat{
                CaveatName: "same_organization",
                Context: &CaveatContext{
                    Values: map[string]any{
                        "document.organization_id": "org-acme",
                    },
                },
            },
        },
        ExpectedSignature: "user:*[same_organization{document.organization_id=org-acme}]",
    },
}

Recommendation:

Publish reference implementation in Go
Provide test vectors as JSON for other languages
Require all implementations to pass test vectors before release

Example test vector file (signature_test_vectors.json):

[
  {
    "name": "DirectSubject without caveat",
    "subject": {
      "type": "DirectSubject",
      "namespace": "user",
      "object_id": "alice"
    },
    "expected_signature": "user:alice"
  },
  {
    "name": "DirectSubject with caveat (sorted context)",
    "subject": {
      "type": "DirectSubject",
      "namespace": "user",
      "object_id": "alice",
      "caveat": {
        "name": "ip_restriction",
        "context": {
          "allowed_ips": ["10.0.0.1", "10.0.0.2"],
          "region": "us-west"
        }
      }
    },
    "expected_signature": "user:alice[ip_restriction{allowed_ips=[\"10.0.0.1\",\"10.0.0.2\"],region=us-west}]"
  }
]

Audit Trail Format

What to log for audit purposes:

Every authorization decision should produce an audit entry with:

type AuditEntry struct {
    // Request metadata
    Timestamp      time.Time         `json:"timestamp"`
    RequestID      string            `json:"request_id"`

    // Authorization query
    Resource       ObjectAndRelation `json:"resource"`
    Subject        ObjectRef         `json:"subject"`
    Context        map[string]any    `json:"context"`

    // Decision
    Decision       CaveatEvalResult  `json:"decision"`  // TRUE, FALSE, REQUIRES_CONTEXT
    WinningPath    string            `json:"winning_path"`  // Subject signature

    // Debugging information
    AllPaths       []PathResult      `json:"all_paths"`
    MissingParams  []string          `json:"missing_params,omitempty"`
    EvaluationTime time.Duration     `json:"evaluation_time_ms"`

    // Compliance metadata
    SchemaVersion  string            `json:"schema_version"`
    EvaluatorID    string            `json:"evaluator_id"`
}

type PathResult struct {
    SubjectSignature string           `json:"subject_signature"`
    Result           CaveatEvalResult `json:"result"`
    MissingParams    []string         `json:"missing_params,omitempty"`
}

Example audit log:

{
  "timestamp": "2024-01-15T10:30:00Z",
  "request_id": "req-abc123",
  "resource": {
    "namespace": "document",
    "object_id": "doc-123",
    "relation": "viewer"
  },
  "subject": {
    "namespace": "user",
    "object_id": "alice"
  },
  "context": {
    "user.organization_id": "org-acme"
  },
  "decision": "TRUE",
  "winning_path": "user:alice",
  "all_paths": [
    {
      "subject_signature": "user:alice",
      "result": "TRUE"
    },
    {
      "subject_signature": "group:engineering#member",
      "result": "FALSE"
    },
    {
      "subject_signature": "user:*[same_organization{document.organization_id=org-acme}]",
      "result": "TRUE"
    }
  ],
  "evaluation_time_ms": 12,
  "schema_version": "v2.3.1",
  "evaluator_id": "auth-service-us-west-1a"
}

Why this matters:

Compliance: HIPAA, SOC2, GDPR require audit trails
Debugging: Reproduce authorization decisions exactly
Security: Detect unauthorized access attempts
Performance: Identify slow evaluation paths

Real-World Context

Which Companies Face This Problem?

1. Distributed Authorization Systems

Google Zanzibar: Globally distributed, must be deterministic
Auth0 FGA: Multiple authorization servers must agree
Ory Keto: Distributed permission checks

2. Compliance and Audit

Stripe: Must reproduce authorization decisions for audits
Square: Compliance requires deterministic evaluation
Plaid: Financial regulations require reproducible decisions

3. Caching and Performance

GitHub: Caches permission checks, must match fresh evaluations
GitLab: Distributed caching requires determinism
Bitbucket: Permission caching across data centers

4. Testing and Verification

AWS IAM: Policy simulator must match production evaluation
Azure RBAC: Test environments must match production
GCP IAM: Deterministic evaluation enables testing

Takeaways

Determinism requires comprehensive rules — Subject signatures, result prioritization, and tie-breaking must all be well-defined to ensure two evaluators always agree.
Union semantics with minimal missing-set — Any TRUE wins (union), but when all return REQUIRES_CONTEXT, prefer fewest missing parameters (user-friendly).
Lexicographic ordering is simple and stable — Subject signatures provide a deterministic, language-agnostic way to break ties across all result types.
Signature stability enables graceful evolution — Signatures must remain unchanged across schema updates to prevent cache invalidation storms and maintain system performance.

Why it matters: Deterministic evaluation is the foundation for distributed authorization, caching, audit compliance, and multi-language implementations. Without it, the system becomes unpredictable and unreliable.

Next → Post 10: Unknowns, Duplicates, and Fail-Safe Defaults

We now have deterministic evaluation, but production systems face additional challenges: What happens when things go wrong?

In real-world deployments, we encounter:

Unknown caveats (schema evolution, deployment skew)
Duplicate tuples (concurrent writes, eventual consistency)
Resource exhaustion (deep graphs, DoS attacks)
Cycles (misconfigured schemas, data corruption)

Post 10 tackles the safety problem: fail-safe defaults, budget limits, and graceful degradation that keep the system secure even when things break.

Preview:

// Unknown caveat → FALSE (fail-safe)
// Duplicate tuples → UNION (permissive)
// Budget exceeded → FALSE (DoS protection)
// Cycle detected → FALSE (safety)

Post 9 — Determinism and Tie-Breaks

The Problem Statement

Human Rule

Why Current Models Don't Work

What We Have So Far (Post 1-8 Recap)

Approach 2: Evaluate All, Return Any TRUE (Ambiguous)

Approach 3: Canonical Ordering (Incomplete)

The Solution: Deterministic Evaluation Semantics

Part 1: Canonical Subject Signatures

Part 2: Result Prioritization Rules

Part 3: Tie-Breaking for TRUE Results

Part 4: Tie-Breaking for REQUIRES_CONTEXT Results

Part 5: Tie-Breaking for FALSE Results

Part 6: Schema-Defined Evaluation Order

Part 7: Signature Stability Guarantees

Real-World Example: Multi-Tenant SaaS Platform

Requirements

Schema Definition

Tuple Setup

Evaluation Scenarios

Design Decisions

Decision 1: Union Semantics (TRUE Wins)

Decision 2: Minimal Missing-Set Tie-Break

Decision 3: Lexicographic Tie-Breaking

Edge Cases and Safety

Edge Case 1: Signature Collisions

Edge Case 2: Empty Result Set

Edge Case 3: All Paths Return REQUIRES_CONTEXT

Edge Case 4: Caveat Context Conflicts

Edge Case 5: Signature Length Limits

Edge Case 6: Lexicographic Ordering Across Languages

Edge Case 7: Signature Computation Failure

Implementation Notes

Performance Considerations

Testing Strategies

Cross-Language Compatibility

Audit Trail Format

Real-World Context

Which Companies Face This Problem?

Takeaways

Next → Post 10: Unknowns, Duplicates, and Fail-Safe Defaults

Keep Reading

Sub-Microseconds

Home