Implementing NOT: what should a validator do when its copy of the far node TEL might be stale?

[dhh1128]

@SmithSamuelM

I wrote the following comment but decided I needed to go back and read the spec more carefully. Once I did that, part of my question got answered, and part did not. So, maybe skim my first comment and then focus more on my follow-up comment.

---

After today's reminder in a maintainers call that the NOT operator is still not really implemented, I'm looking at implementing it (#1554), and I've run into a design question I don't think I should answer on my own.

(NOT is in the spec's normative operator table, but keripy has never implemented it. Until #1552 it was fail-open: an edge saying "this node must be invalid" fell through to the default inference and got validated normally, which is the opposite of what it asks for. #1552 made it fail closed with a diagnosable error. That's better, but it isn't an implementation.)

The first thing I ran into is that keripy can only prove one kind of invalidity. If a far node's signature is bad, or it fails its schema, or its own chain is broken, it never gets saved, so it looks the same as a credential that simply hasn't arrived. The one form of invalidity that leaves a positive, signed trace is revocation. I'm ambivalent about this. Maybe the rule has to be something like: a NOT edge is satisfied only when the far node is in the database and its TEL says revoked, and everything else counts as "I don't know yet" rather than "invalid"? Treating absence as invalidity seems fail-open to me, and fail-open in favor of whoever gets to choose what to disclose, which is worse. But maybe NOT was intended to cover all the cases.

Setting that aside, here's the more interesting part I'm stuck on.

Suppose Alice holds a credential N with an edge {"n": F, "o": ["NOT"]}, so N is valid only while F is invalid. Say F is a suspension notice naming Alice, and N asserts she is in good standing. Alice received a copy of F in March, when it was issued. In June, F's issuer revoked it. In August, Alice presents N to Bob.

sendArtifacts (src/keri/vdr/credentialing.py:1054) replays the whole TEL of every source credential, so Alice pushes whatever TEL she has for F. That is her March snapshot, with only the iss event in it. Bob's vcState (src/keri/vdr/eventing.py:1209) decides the state by counting the TEL events he holds — one event is iss, two is rev — so he concludes F is still valid and the NOT edge fails. The revocation is real, signed, and sitting on F's registry backers. Nobody in the exchange asked for it, and nobody was cheating; Alice has little reason to poll a registry that isn't hers.

The staleness runs in the opposite direction from the other operators, which is what bothers me. For I2I, a stale TEL means accepting a chain whose parent was revoked, which is fail-open, and roughly the concern in #600. For NOT, a stale TEL means rejecting a credential whose condition is actually met. NOT also seems to be the one operator whose whole subject is a fact that changes after issuance, so its edges will spend most of their lives in exactly this state.

There is already a freshness mechanism for far nodes at src/keri/vdr/verifying.py:229-235: if the far node's TEL event is older than CredentialExpiry, escrow the near credential and cue a tels query. As far as I can tell it never fires. The default is 36000000000 seconds, about 1141 years (verifying.py:49), and none of the places that construct a Verifier passes anything else.

So my question is what a validator should do when it meets a NOT edge and its copy of the far node's TEL says issued. I can think of three answers.

It could escrow the near credential and cue a tels query, go ask the far node's registry, and admit the credential on a later pass if a rev event comes back. Alice gets the right answer. The cost is an escrow slot held for an hour when F really is valid, and an hour of missing-chain retries in the log instead of a prompt verdict.

It could reject right away. That is simple and fast, but then the verdict depends on how old the validator's cache happens to be, and Alice has no way to recover during that session.

It could reject right away and cue the query anyway, so this presentation fails but a later one is decided on fresh data. That spends a round trip of Alice's time instead of an escrow slot.

I lean toward the first, because it seems to me that "issued" in this situation doesn't mean "I have data that says no", it means "I haven't looked recently", and escrow is what keripy already uses for that. I am not confident, though. The counterargument I can't dismiss is that the cue only becomes a query if something is draining verifier.cues, which agents and witnesses do but a bare kli run may not, so in that case the first answer degrades into an hour of silence followed by the same rejection.

I would also be glad to be told I have the underlying rule wrong, and that NOT should be satisfiable by something weaker than proof of revocation. And if anyone has a concrete use case for NOT they have thought through, I would like to hear it. I have been reasoning from examples I made up, which is not a great foundation for a validation rule.

[dhh1128]

I went back and read the spec more carefully after posting this, and it moves my question rather than answering it, so let me correct the framing.

Line 1112 of spec-body.md says the part I was treating as a protocol question is not one: "ACDCs in a provenance chain or branch that have expiration dates or are dynamically revocable add a timeliness property to the validation logic in the event that the chain was unbroken at issuance but becomes broken later. The timeliness logic is EGF-dependent." That is the situation I described, in mirror image — a chain that is good at issuance and breaks later, rather than one broken at issuance that becomes good later — and the spec hands it to the ecosystem governance framework. So I think the three answers I offered are probably a policy setting rather than something keripy should pick once for everyone. CredentialExpiry looks like it was meant to be that setting, and it is effectively off.

The same paragraph makes me think our current behavior is also a policy choice presented as protocol. Line 1114 is all MAY: "When any node in a provenance chain is invalid, an Edge pointing to that node MAY also be invalid. If a node has an invalid Edge, then the node MAY also be invalid." The MUST that follows is scoped to "typically, in a given EGF". We raise RevokedChainError unconditionally on a revoked far node, which is one reasonable EGF rule out of several the spec allows.

I also think my Alice and Bob story was a keripy gap rather than a spec gap, and I should have caught that before posting. Line 1693 says a Validator queries its own TEL Observer at a point of validation, not the Registrar and not the Discloser, and the Observer stays current by polling or subscribing to the Registrar. Bob deciding from Alice's March snapshot is not what the spec describes. As far as I can tell keripy has no Observer component at all, so the freshness architecture that the rest of this rests on is not built yet. That seems like the more important gap, and it is a lot bigger than NOT.

One thing to maybe flag for anyone writing an EGF: line 1695 suggests timed grace periods on revocation, where a revocation does not take effect until some interval after the state update, as a way to let caches catch up. Under NOT that inverts. A grace period is a window in which a revoked far node still reads as valid, so it delays the point at which a NOT edge can be satisfied. An ecosystem that adopts grace periods for the usual reason has quietly made a decision about NOT as well.

What I still cannot find is a definition of "invalid" anywhere in the spec. NOT is also not the only operator that needs one: the m-ary table at lines 1103-1106 has NAND ("valid only if not all members are valid") and NOR ("valid only if all members are invalid"), so three operators turn on the word. If the absence of a far node counts as invalid, all three become satisfiable by withholding, which seems wrong to me.

So my question is really two questions now.

1. Should the timeliness behavior be an EGF-configurable policy in keripy rather than a fixed choice, and is that what CredentialExpiry was originally for?

2. And would it be worth adding a sentence to the spec saying what a Validator may treat as invalid, covering NOT, NAND and NOR together?

One smaller thing I am unsure about. Line 1112 says the default provenance logic applies "at least at the time of issuance", which reads to me like evaluation at issuance time, while the Observer section is explicit that validation happens at a point of validation. I might be misreading it, but those seem to pull in different directions for an operator whose truth value can change after issuance.