#ULDA Manifest v1

Status: Final version (initial release)
Purpose: Defines terminology, required behaviors, and minimal format for the ULDA-S and ULDA-X protocols, along with the base wire representation.

#0. Summary

ULDA is a family of one-time linear step signatures for verifying data lineage across generations.
Each new step proves descent from the previous one by validating the overlap of “ladders” — triangular matrices of hash values.

Out of scope (MUST NOT): encryption, PKI, consensus, KDF, or key management — these are handled externally.

#1. Families and Modes

• ULDA-S (Skippable) — allows skips up to N−1 generations; verification uses multi-step diagonal hashing.
• ULDA-X (Strict) — disallows skips; verification relies on strict cross-linked overlaps (one-step shift).

Both publish an N-height ladder with identical serialization.
Only the computation rule and skip tolerance differ.

#2. Stateless Verification

Verification is state-light:
The verifier keeps only the latest valid ladder.
Upon a successful check, the previous ladder is replaced.
No private keys or secrets are required during verification.

Retries, replays, and idempotence are handled by the transport layer (age counters, time-boxes, etc.).

#3. Terminology

• Hash function f — a cryptographic one-way function (default: SHA-256).
• Height N — ladder size (N ≥ 2, default N = 5).
• Age k — generation number (u32 or u64).
• Origin (originₖ) — random bytes from which the base blocks tₖ…tₖ₊ₙ₋₁ are derived.
• Generator G — deterministic PRF/KDF expanding originₖ into N “raw” blocks.
• Rolling-origin (MUST) — new origin per step; prior origins are discarded for post-compromise security.

#4. Ladder Construction

Let tₖ … tₖ₊ₙ₋₁ be raw blocks (level F⁰).

• ULDA-S: Fᵈᵢ = fᵈ(tₖ₊ᵢ) for all d ≤ i < N.
• ULDA-X: F⁰ᵢ = tₖ₊ᵢ; Fᵈᵢ = f(F^{d−1}_{i−1} || F^{d−1}_ᵢ).

The resulting step Sₖ is a triangular matrix Fᵈᵢ of height N.

#5. Verification Rules

Let Sₖ be the current valid step; P be the new proposal.

#5.1 No skip (S and X)

∀ d ∈ [0, N−1], i ∈ [d, N−2]:
    P[d][i] == Sₖ[d][i+1]

#5.2 Skip g (S only)

∀ d ∈ [0, N−g−1], i ∈ [d, N−g−1]:
    apply_f_diagonal(P[d][i], g) == Sₖ[d][i+g]

Skips g ≥ N are invalid. ULDA-X forbids skipping entirely.

#6. Packaging — ULDAPack-Min v1

A minimal binary container with no extensions.

Invariants:
Age increases monotonically; identical (height, age) pairs must never repeat.

#7. Security & Cost

• One-time monotonicity — each Sₖ is single-use; replays are rejected.
• Computation cost: generation ≈ N(N−1)/2 hashes; verification ≈ N−1.
• Post-compromise recovery: achieved via Rolling-origin (new entropy per step).

#8. Default Profiles

Recommended additional hash functions: SHA-512/256, BLAKE2b-256, SHA3-256.

#9. Operational Notes

• Resynchronization: a valid next step (or skip ≤ N−1 for S) is sufficient to recover sync.
• Multi-client mode: multiple nodes may extend the same chain; transport must decide who publishes next.

#10. Conformance

A compliant implementation MUST:

• Implement at least one base profile from §8.
• Support the ULDAPack-Min v1 structure.
• Enforce verification rules from §5 (skip limits, monotonic age).

Test vectors for N=5 (S and X) are published in the ULDA Spec repository.