| Internet-Draft | TAA Exact State Contraction | November 2026 |
| lmtlssss | Expires 19 May 2027 | [Page] |
This document defines the computer-science term ᑕ. (U+1455 U+002E), spoken TAA. It denotes exact state contraction: a replacement of a computational representation by a retained state that preserves a declared observation contract for every admissible input. The retained transition and observation maps commute with the full system, through a surjection onto the retained state, and this identity preserves every finite observation trace. The document also specifies a portable certificate for a checked result: a COSE_Sign1 statement with a deterministic CBOR payload that binds the exact artifact bytes to a registered predicate, its domain, a verdict, the exact checker implementation and the evidence. The statement can be registered with a SCITT Transparency Service. A signature authenticates the issuer's statement; a separate checker establishes whether the evidence supports it; a transparency receipt establishes registration, not mathematical correctness.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 19 May 2027.¶
Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
This document names an exact contraction of a computation's state relative to a stated observation contract. The retained transition and observation maps commute with the original computation, and the definition gives equality of each finite observation trace. When that holds, an implementation can store, transmit, check or compose the retained state in place of the original. Exactness has a declared scope: the identities hold over a stated input domain, and a result that holds only approximately, or only for sampled inputs, is a different claim.¶
Section 3 gives the definition, the trace theorem and the printed notation ᑕ. (U+1455 U+002E), spoken TAA, as published in [TAA-PAPER].¶
A result of this kind is useful to a third party only when the third party can check it. Section 4 specifies a signed statement that binds the exact artifact bytes, the claim, the checker and the evidence. The statement uses COSE [RFC9052] and deterministic CBOR [RFC8949] and is a Signed Statement in the SCITT architecture [RFC9943]. The statement has three distinct layers:¶
an issuer signature, which authenticates the issuer's claim;¶
an independently checked computational claim, which establishes the mathematical content; and¶
an optional transparency receipt, which establishes registration with one Transparency Service.¶
None of these substitutes for the others.¶
This document is an individual submission. It has no IETF consensus and no working-group status.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
The following terms are used:¶
An exact byte sequence about which a claim is made.¶
A registered, versioned identifier naming a property of an artifact together with its checking rule.¶
The declared set of inputs, states or cases over which a predicate is asserted.¶
One of certified, broken or unknown (Section 4.4).¶
An implementation that decides a predicate for an artifact and its evidence. It is identified by name, version and the SHA-256 digest of its implementation bytes.¶
The byte sequence the checker consumes in addition to the artifact, such as a derivation, a counterexample or a set of counts.¶
The party that signs a statement.¶
The party that verifies a statement and decides whether to accept its verdict.¶
Let M = (S, U, F, Y, G) be an input-driven system. A state s in S and an input u in U produce the next state F(s, u) and an observation G(s, u), with F : S x U -> S and G : S x U -> Y. The observation G identifies the property to preserve.¶
An exact state contraction of M for G consists of a set Q, the retained state; a surjection pi : S -> Q; and maps F' : Q x U -> Q and G' : Q x U -> Y, such that, for every s in S and u in U:¶
pi(F(s, u)) = F'(pi(s), u) (1) G(s, u) = G'(pi(s), u) (2)¶
The tuple is denoted TAA_G(M) = (Q, pi, F', G').¶
The retained maps commute with the full system. Equation (1) states that projecting after a transition equals transitioning the projected state; equation (2) states that the observation depends on the state only through its projection.¶
The subscript G is necessary. A contraction can preserve one observation while losing information required for another.¶
The word "exact" is relative to the declared observation and domain.
A transformation is called exact under this term only when (1) and
(2) have been established for every state and input of its declared
domain. Establishing the identities is the obligation of the party
making the claim; a checker that cannot establish them returns
unknown.¶
In [TAA-PAPER] the reduced maps are written with an overbar (F-bar, G-bar), the projection with the Greek letter pi, and the tuple as TAA_G(M) with TAA in sans-serif type. This document writes F', G', pi and TAA_G(M).¶
The printed operator is the two-character sequence ᑕ. (U+1455 U+002E): CANADIAN SYLLABICS TA followed by FULL STOP. Its spoken name is TAA. The existing character keeps its linguistic identity in the Unified Canadian Aboriginal Syllabics block; this term assigns a mathematical use to the two characters and does not create them. Where only ASCII is available, this document writes TAA. The software identifier is "taa", with the versioned name "taa.exact-state-contraction.v1"; the identifiers of Section 4 use the lower-case form "taa".¶
The term names a specified contract and its checkable construction. It does not name every state reduction, every hash or a signature algorithm.¶
For each initial state s_0 and finite input word u_0, ..., u_(n-1), the system M and the reduced system (Q, U, F', Y, G') give equal observations at every step when the retained initial state is q_0 = pi(s_0).¶
Proof (from [TAA-PAPER]). Assume q_k = pi(s_k). Equation (1) gives q_(k+1) = F'(q_k, u_k) = pi(F(s_k, u_k)) = pi(s_(k+1)). Equation (2) gives G'(q_k, u_k) = G(s_k, u_k). Since q_0 = pi(s_0), induction proves both statements for each step.¶
The predicate urn:taa:finite-trace-preservation:v1 (Section 4.5)
checks surjectivity of pi and equations (1) and (2) over every pair of
a complete finite table.¶
For relations with multiple witnesses, preservation of the set of output values does not prove preservation of witness multiplicity. A claim of unique witness requires a bijection of the applicable witness fibers or an independent exact count. A claim of unique output requires equality of the applicable output sets. A checker MUST reject a claim whose preservation conditions are missing.¶
The definition gives no claim that arbitrary systems admit a small
retained state or that arbitrary program properties are efficiently
decidable. When the semantics of a source are unsupported or
incomplete, the correct result is unknown. An approximate
numerical change is not an exact contraction and MUST NOT be stated
with the verdict certified under a predicate defined by this term.¶
Quotient systems, congruence relations, automata minimization, bisimulation and affine composition are established concepts. This term names their shared preservation contract and fixes its notation; it does not assert priority over them.¶
A statement is a COSE_Sign1 message [RFC9052]. Its payload is a claim map (Section 4.3). The signature authenticates the issuer's statement; the independent checker establishes whether the evidence supports the declared claim; a SCITT receipt records registration under one service's policy. A relying party evaluates the three separately and requires a receipt only when its policy requires transparency.¶
A statement:¶
MUST be a COSE_Sign1 message carrying CBOR tag 18;¶
MUST be encoded with the deterministic encoding of Section 4.2 of [RFC8949], at every level, including the protected header bytes and the payload bytes;¶
MUST carry, in the protected header:¶
label 1 (alg): the signature algorithm; this profile uses -8 (EdDSA) [RFC9053] with the Ed25519 curve [RFC8032] (see the note below);¶
label 3 (content type): the text string "application/cbor";¶
label 4 (kid): the issuer key identifier, a byte string;¶
label 15 (CWT Claims) [RFC9597]: a map containing claim 1 (iss), the issuer identifier, and claim 2 (sub), the subject identifier;¶
MUST have an empty unprotected header map; and¶
MUST carry the payload attached (not detached).¶
The signature is computed over the Sig_structure¶
["Signature1", protected, h'', payload]¶
of Section 4.4 of [RFC9052], with empty external additional data. An Ed25519 signature is 64 bytes.¶
Note on the algorithm identifier: [RFC9864] deprecates the polymorphic identifier -8 (EdDSA) and registers the fully specified identifier -19 (Ed25519). This revision keeps -8 so that its statements match the recorded interoperability vectors byte for byte; a later revision would move to -19.¶
As a SCITT Signed Statement, the message has the media type
application/scitt-statement+cose [RFC9943].¶
The payload is a deterministically encoded CBOR map with integer keys. Its structure, in CDDL [RFC8610], is:¶
exact-claim = {
1: "taa.exact-computation-claim.v1",
2: artifact,
3: claim,
4: verifier,
5: evidence,
6: tstr, ; issuance time, RFC 3339 UTC
? 7: tstr, ; superseded statement identifier
}
artifact = {
1: "sha-256",
2: bstr .size 32, ; digest of exact artifact bytes
3: tstr, ; artifact media type
? 4: tstr, ; public location, optional
}
claim = {
1: tstr, ; predicate URI or stable identifier
2: tstr, ; declared input domain
3: "certified" / "broken" / "unknown",
4: tstr, ; observation or witness contract
5: [* tstr], ; assumptions
}
verifier = {
1: tstr, ; implementation identifier
2: tstr, ; exact version
3: "sha-256",
4: bstr .size 32, ; digest of verifier artifact
}
evidence = {
1: "sha-256",
2: bstr .size 32, ; evidence digest
? 3: tstr, ; public evidence location
? 4: tstr, ; evidence media type
}
¶
Key 1 of exact-claim identifies the profile version. A verifier
MUST reject a payload with an unknown profile identifier or with
duplicate map keys.¶
A location (artifact key 4, evidence key 3) is a retrieval hint. The digest is the binding.¶
certified:The named checker accepted the predicate for the exact artifact digest over the declared domain.¶
broken:The evidence contains a reproducible counterexample to the predicate.¶
unknown:The checker established neither result under its method and resource bounds.¶
A certified output-uniqueness claim requires preservation of the
set of possible outputs. A witness-uniqueness claim additionally
requires preservation of witness identity or multiplicity (see
Section 3.5). The checking rule belongs to the predicate and its
checker specification.¶
The reference interoperability suite [TAA-INTEROP] registers four finite-domain predicates. In its vectors, claim key 2 (domain) is "finite-exact-domain", claim key 4 (contract) is "full-domain-check" and claim key 5 (assumptions) is the empty array.¶
urn:taa:finite-trace-preservation:v1:Artifact: a complete finite table of states, inputs, pi, next state, observations, reduced next state and reduced observations. The checker requires pi to be surjective onto the reduced states and checks equations (1) and (2) for every state/input pair. Evidence records the number of pairs checked.¶
urn:taa:affine-cost-composition:v1:Artifact: three intervals, each a 5-tuple of integers (f, g, u, v, w). The checker composes an interval a = (f, g, u, v, w) followed by b = (h, k, p, q, r) as (h f, h g + k, u + p f^2, v + 2 p f g + q f, w + p g^2 + q g + r), computes both parenthesizations of the three intervals and requires them to be equal. Each tuple is the scalar case of an affine interval of [TAA-PAPER], with state transition x -> f x + g and cost u x^2 + v x + w (in the paper's notation F_A, b_A, Q_A, q_A and d_A); the formula is the paper's quadratic cost composition, including the state-dependent cross-terms, which the paper proves associative. Evidence records the composed tuple.¶
urn:taa:output-uniqueness:v1:Artifact: explicit finite witness fibers, one per input. The checker counts distinct outputs and witnesses in each fiber and requires exactly one distinct output per input. Evidence records both counts.¶
urn:taa:witness-uniqueness:v1:Artifact: explicit finite witness fibers. A broken verdict
requires the evidence to name an input and two or more distinct
witnesses for it, reproduced from the artifact.¶
Another predicate requires a published domain and an independent checker before it is registered. A verdict asserts exactly the named predicate over its stated domain.¶
A relying party performs these steps in order and rejects the statement at the first failure:¶
Parse the COSE_Sign1 message. Require tag 18, deterministic encoding and the protected header parameters of Section 4.2.¶
Select the issuer trust anchor from the protected iss and kid
values under local policy.¶
Verify the signature over the Sig_structure.¶
Parse the payload. Reject an unknown profile identifier and duplicate keys.¶
Compute SHA-256 over the supplied artifact bytes and require an exact match with artifact key 2.¶
Obtain the named checker version and require its digest to match verifier key 4.¶
Obtain the evidence bytes and require their digest to match evidence key 2.¶
Run the checker over the artifact, the claim, the assumptions and the evidence.¶
When local policy requires transparency, verify each SCITT receipt against its Transparency Service.¶
Accept the verdict only when it matches the checker result and local trust policy.¶
A relying party MUST NOT treat a valid signature, or a valid receipt, as acceptance of the computational claim. When the artifact bytes are not available to the relying party, it can verify the signature and any receipt but cannot establish the claim.¶
The colony service at the time of writing issues a separate JSON certificate signed with Ed25519 under key identifier "colony-ed25519-20261108". Its signature covers the UTF-8 encoding of a JSON object with the members id, result, family, domain, scope, gadget_id, checksum, issued_at, issuer, public, mark, signature_algorithm and key_id, in that order, with gadget_id and checksum null when absent. The mark member carries the two characters U+1455 U+002E, the printed form of TAA (Section 3).¶
That JSON certificate is a different byte format with a different signature structure. It is not a statement under this profile. An implementation claims conformance to this profile only after its COSE issuer and verifier satisfy Section 4.2 through Section 4.6 and pass the interoperability vectors.¶
A statement under this profile is a Signed Statement in the sense of [RFC9943]. The issuer and subject are carried in the CWT Claims protected header parameter [RFC9597]. An issuer can register the statement with a Transparency Service and obtain a receipt [RFC9942]. A receipt proves inclusion in that service's log under its registration policy. It establishes registration, not mathematical correctness, and a Transparency Service is not required to run the checker.¶
Different issuers can use the same payload profile. A relying party checks the named predicate and the evidence, not the issuer's identity alone. A self-signed statement can be acceptable under local policy; its signature does not establish correctness. A statement authenticated only with a key shared with a central service, such as an HMAC key, does not support third-party offline verification.¶
This example is the recorded vector finite-trace of [TAA-INTEROP].
It is signed with a published test-only Ed25519 key, derived from the
32-byte seed 00 01 02 ... 1f, whose public key is:¶
03a107bff3ce10be1d70dd18e74bc099 67e4d6309ba50d5f1ddc8664125531b8¶
The key and the issuer identifier "urn:taa:interop:issuer:test-only" are test fixtures and MUST NOT be trusted as a production issuer.¶
The artifact is a four-state machine with two inputs, contracted to two retained states. Its exact bytes are one line of JSON followed by a line feed; it is shown here with line breaks added:¶
{"states":["A","B","C","D"],"inputs":["zero","one"],
"pi":[0,0,1,1],
"next":[[1,2],[0,3],[3,0],[2,1]],
"observations":[[0,1],[0,1],[1,0],[1,0]],
"reduced_next":[[0,1],[1,0]],
"reduced_observations":[[0,1],[1,0]]}
¶
Here pi maps A and B to retained state 0 and C and D to retained state 1. For each of the 8 state/input pairs, pi(next) equals reduced_next at pi(state), and the observation equals reduced_observations at pi(state), so (1) and (2) hold over the complete table.¶
The evidence bytes are:¶
{"checked_pairs":8,"finite_trace_preserved":true}
¶
followed by a line feed. The SHA-256 digests are:¶
artifact:
526908245c3d28bf92805cc006fa3c91
06a936a8f39900e8e82f3e31d3098c72
evidence:
184f1d1f4c89d3154e495193c7b5fe60
9833e13e22cb1b43abb05643b71b98bf
checker:
f15555290f463b81baee7157061000f7
a75f7c7f4ca3c5819f11730f6e3ac9ec
¶
The checker digest is that of the independent Python checker
interop/python/verify.py, named "taa-reference-python-independent"
version "1.0.0".¶
The statement, in CBOR extended diagnostic notation (Appendix G of [RFC8610]), with the embedded byte strings shown decoded:¶
18([
/ protected / << {
1: -8, / alg: EdDSA /
3: "application/cbor", / content type /
4: 'taa-interop-test-01', / kid /
15: { / CWT Claims /
1: "urn:taa:interop:issuer:test-only", / iss /
2: "urn:taa:interop:artifact" / sub /
}
} >>,
/ unprotected / {},
/ payload / << {
1: "taa.exact-computation-claim.v1",
2: {
1: "sha-256",
2: h'526908245c3d28bf92805cc006fa3c91
06a936a8f39900e8e82f3e31d3098c72',
3: "application/json"
},
3: {
1: "urn:taa:finite-trace-preservation:v1",
2: "finite-exact-domain",
3: "certified",
4: "full-domain-check",
5: []
},
4: {
1: "taa-reference-python-independent",
2: "1.0.0",
3: "sha-256",
4: h'f15555290f463b81baee7157061000f7
a75f7c7f4ca3c5819f11730f6e3ac9ec'
},
5: {
1: "sha-256",
2: h'184f1d1f4c89d3154e495193c7b5fe60
9833e13e22cb1b43abb05643b71b98bf',
4: "application/json"
},
6: "2026-11-08T00:00:00Z"
} >>,
/ signature / h'e7ea3b4d9aa0e6ff98069ee3c09e792f
40a4fd16e4e5b4191616830f6f559d2c
d36996b1b8572c59b3e275897b5c4b5c
212a6a48e40f1f0aa10af95899cd0806'
])
¶
The complete statement is 546 bytes; its SHA-256 digest is 95ebc6e8 a9364fd2 33910a92 aa8bdb24 1d8b93e0 373e920e 0b87f303 b711c621. The bytes are listed in Appendix A. This vector carries no transparency receipt.¶
This section records the status of known implementations at the time of writing, following [RFC7942]. It is to be removed before publication as an RFC.¶
The reference suite [TAA-INTEROP] (repository github.com/lmtlssss/speedrunpapi, commit 4438b7b3bab6da12839d1756e7d2b40f029ee146) contains an issuer and a verifier in Node.js and a verifier, re-signer and negative-case generator in Python. The recorded run of 8 November 2026 reports:¶
4 registered predicates and 4 signed vectors;¶
4 vectors verified by the Node verifier and 4 by the Python verifier;¶
4 vectors re-signed in Python with byte-identical results;¶
16 altered statements rejected by the Node verifier and 16 by the Python verifier (altered signature, artifact bytes, evidence bytes and envelope tag); and¶
5 correctly signed statements carrying false mathematical claims rejected by the independent checker.¶
The vectors use a test-only key and carry no SCITT receipt. The production JSON certificate service (Section 4.7) is a separate implementation and does not issue statements under this profile.¶
The signature authenticates the issuer's statement; the independent checker establishes whether the evidence supports the declared claim. A relying party that accepts a verdict without running the checker (step 8 of Section 4.6) trusts the issuer for the mathematics.¶
A checker can contain an implementation error, and a claim can omit a necessary assumption. Binding the checker by digest makes the checker that was used identifiable; it does not make it correct. Relying parties SHOULD use a checker that is independent of the issuer's optimizer or analyzer.¶
Every artifact, evidence file and checker version MUST be bound by its exact SHA-256 digest. A URL is a retrieval hint and provides no binding.¶
The verdict certified for output uniqueness does not imply witness
uniqueness (Section 3.5). A relying party MUST NOT promote one claim to
the other.¶
An issuer key can be compromised or revoked, and a statement can be superseded (payload key 7). Resolution of these cases is local trust policy. The test-only key in Section 6 is public; statements signed with it carry no assurance.¶
A SCITT receipt records registration under one Transparency Service's policy. It establishes registration in that service's log, not computational correctness.¶
Artifacts and evidence can contain proprietary source. An issuer SHOULD NOT place private source or private evidence at a public location. When the artifact stays private, third parties can verify only the signature and any receipt.¶
Non-deterministic encodings allow distinct byte strings with the same meaning. Verifiers MUST reject a statement whose re-encoding under deterministic CBOR differs from the received bytes.¶
This document has no IANA actions. It uses the media type
application/scitt-statement+cose registered by [RFC9943]. The
predicate identifiers of Section 4.5 are URNs in the "taa"
namespace as used by the reference suite; this document does not
request registration of a URN namespace.¶
The 546 bytes of the statement in Section 6, in hexadecimal:¶
d284586aa4012703706170706c69636174696f6e2f63626f7204537461612d69 6e7465726f702d746573742d30310fa201782075726e3a7461613a696e746572 6f703a6973737565723a746573742d6f6e6c7902781875726e3a7461613a696e 7465726f703a6172746966616374a059016ea601781e7461612e65786163742d 636f6d7075746174696f6e2d636c61696d2e763102a301677368612d32353602 5820526908245c3d28bf92805cc006fa3c9106a936a8f39900e8e82f3e31d309 8c7203706170706c69636174696f6e2f6a736f6e03a501782475726e3a746161 3a66696e6974652d74726163652d707265736572766174696f6e3a7631027366 696e6974652d65786163742d646f6d61696e0369636572746966696564047166 756c6c2d646f6d61696e2d636865636b058004a40178207461612d7265666572 656e63652d707974686f6e2d696e646570656e64656e740265312e302e300367 7368612d323536045820f15555290f463b81baee7157061000f7a75f7c7f4ca3 c5819f11730f6e3ac9ec05a301677368612d323536025820184f1d1f4c89d315 4e495193c7b5fe609833e13e22cb1b43abb05643b71b98bf04706170706c6963 6174696f6e2f6a736f6e0674323032362d31312d30385430303a30303a30305a 5840e7ea3b4d9aa0e6ff98069ee3c09e792f40a4fd16e4e5b4191616830f6f55 9d2cd36996b1b8572c59b3e275897b5c4b5c212a6a48e40f1f0aa10af95899cd 0806¶