# Expert-Activation Signatures (EAS)

## Scope and notation

Let a sparse mixture-of-experts model have model identifier `model_id`,
`M` experts, deterministic routing parameters `model_params`, and a public
routing transcript commitment. For an input `x`, let

`S(x) = { i in [0,M) : the published routing circuit selects expert i }`.

An EAS is the tuple

`(model_id, input_hash, S, commitment_c, proof_pi)`

where `input_hash = H(encode(x))`, `S` is a canonical strictly increasing
list of selected expert indices, `commitment_c` commits to the complete
routing transcript, and `proof_pi` proves that `S` is exactly the set selected
by the committed model execution on `input_hash`.

`encode` and all serialization are domain-separated and canonical. The
signature covers the hash of the complete tuple, not a malleable text form.

## Algorithms

`Sign(model_id, x, model_params, sk)` executes the specified routing circuit.
It records every gate input, score, tie-break, capacity decision, token
position, and selected expert. It computes `input_hash`, canonical `S`, and a
Merkle root `commitment_c` over leaves

`H("EAS/route-leaf/v1" || token_index || expert_index || decision_bits || score_digest)`.

It then proves, in zero knowledge, the statement below and returns the tuple
plus a signature `sigma = Sign_sk(H("EAS/v1" || encode(tuple)))`.

`Verify(eas, sigma, pk, model_params, policy)` checks the signature, model
identifier, input hash format, sorted uniqueness of `S`, policy limits, and
the proof. It accepts only if the proof verifies against the supplied public
model parameters and `commitment_c`.

The proof statement is:

```
public: model_id, input_hash, S, commitment_c, model_params_hash
private: x, routing transcript T, witness randomness
assert H(encode(x)) = input_hash
assert execute(model_id, model_params, x) = T
assert merkle_root(T.leaves) = commitment_c
assert selected_indices(T) = S
```

## Correctness

For honest `Sign`, completeness follows from the correctness of the routing
circuit, the Merkle construction, and the proof system. Under collision
resistance of `H` and soundness of the proof system, `Verify` returns true only
when `S` is exactly the set of selected experts in the committed execution:

`Verify(...) = true  iff  S = S(x)`

for a valid signature and the published model parameters. A verifier must
reject if the model parameter hash is not the expected one, if the circuit
version is unknown, or if the policy's maximum token/expert counts are
exceeded. This prevents a proof for one router from being replayed as another.

## Privacy

The proof is zero knowledge for the witness `(x,T)`. It reveals `S`,
`input_hash`, the model identifier, and `commitment_c`, as required by the
tuple, but reveals no witness values or expert outputs. In particular, for any
two witnesses with the same public tuple, the proof distributions are
computationally indistinguishable; therefore outputs, scores, and intermediate
states of experts not in `S` are not disclosed beyond what follows from `S`
and the public model/policy. This does not claim that `S` itself is private.
Side channels such as proof size, timing, and externally observable model
execution are outside the cryptographic statement and must be padded or
isolated when they matter.

## Construction

Use a transparent Merkle commitment for the transcript and a succinct
zero-knowledge argument (for example, a PLONK-family SNARK over a fixed field)
for the routing circuit. The circuit recomputes hashes, scores, comparisons,
capacity constraints, tie-breaking, and the Merkle root. Domain-separated
hashes are modeled as collision resistant; the signature is EUF-CMA secure;
the proof system is complete, computationally sound, and zero knowledge under
its published assumptions. If a universal setup is used, the deployment must
publish the ceremony transcript and circuit verification key; a transparent
STARK-style proof can remove trusted-setup assumptions at a larger proof cost.

## Efficiency and limits

With a sparse proof circuit and Merkle authentication paths, public verification
per selected expert is `O(poly(log M))`, so total verification is
`O(|S| * poly(log M))` plus fixed model-policy checks. Prover cost is linear in
the executed transcript and is intentionally not hidden by the verifier bound.
The exact bound assumes the routing circuit exposes a bounded sparse witness;
dense recomputation or a variable-size policy would invalidate the stated
bound and must be rejected by `Verify`.

## Versioning and failure handling

The domain string `EAS/v1`, circuit identifier, model parameter hash, and
canonical encoding are mandatory. A changed router, quantizer, tie-break rule,
or capacity policy requires a new circuit/model identifier. Verifiers reject
unknown versions, malformed indices, duplicate indices, invalid signatures,
stale policy epochs, and proofs whose commitment or model hash does not match
the tuple.