WAI Extension: Data Deletion

Mirrored from the canonical text at commit 0d3f0d7c ().

Status: Draft. Registers the record wai.data.deletion: what a service deleted of a subject’s records, and what it kept and why, so that the subject can check a deletion against the final export it holds rather than take it on the service’s word. A deletion record (§3) names the subject, the basis of the deletion and when it arose, when it was done, the subject’s final data export by its digest and the head of the subject’s audit chain. It states the subject’s records in classes the service names, each deleted or kept, each by its count and the RFC 6962 tree hash over its leaves, the sorted digests of its records (§4); a kept class states its reason, in words, and when it ends. It names the keys whose private halves were destroyed, and each other party that held any of it, asked to delete or under its own stated retention, citing by link hash the purges of a takedown where that party signed one, and when the last backup that may hold any of it expires. The leaves are served beside the record (§5). A verifier given the record, its leaves and the final export checks the signature, every class’s count and tree hash, no leaf in two classes, the times in order, that the export is the subject’s whole and made after the basis arose, that every record of it lies in exactly one class, that every leaf of a class the export holds is in it, and that the audit head is at or after the export’s checkpoint (§6). WAI decides no legal question and sets no rule on what a service must delete or may keep: it states what the service says it did, checkably. The reference implementation is the data_deletion module of wai-rs (feature data_deletion); the corpus is live-conformance/data-deletion/, and its second implementation is live-conformance/data_deletion_verify.py. Keywords MUST, MUST NOT, SHOULD, MAY are RFC 2119/8174.

Texts read for this revision: the WAI texts this one cites; RFC 6962 §2.1 (the Merkle tree hash); RFC 8259; RFC 8785; RFC 8032; FIPS 180-4.

1. Scope

In scope: the deletion record, its signature and its digest (§3); its classes and their tree hashes (§4); its leaves (§5); and what a verifier checks of it against the subject’s final export (§6).

Out of scope: when a service must delete and what it may keep, which law, contract or policy it reads, and what words it gives; how the subject asks and how the service learns who asks; how a deletion is done; and what a record of another text means. A class’s name, a kept class’s words and a holder’s identifier are the service’s, opaque to every verifier.

The deletion of a media object a party still holds, in answer to a notice or of the service’s own initiative, is takedown’s: each holder signs a purge of what it no longer holds. A deletion record does not replace one: it names a subject’s records (receipts, invoices, its audit chain, the rows a service keeps of it, blobs), states what was kept beside what was deleted, and cites a takedown’s purges where a holder signed one (§3.1, holders).

Relationship to the core spec: wai.data.deletion is a record (SPEC §5): a record a WAI tool emits and verifies. It names no payload format and is not dispatchable.

2. Terms and encodings

3. The deletion record

3.1 Members

A deletion record is a document of exactly these members:

memberformmeaning
kindstring"wai-data-deletion"
versioninteger1
subjecttokenwhose records
basisstringtermination (the subject’s account ended), request (a deletion was asked for) or retention (a retention period ended)
aroseinstantwhen the basis arose: the closing, the request, the period’s end
deleted_atinstantwhen the deletion was done
exporthashthe final export’s digest (data-export §3.4)
auditobject or nullexactly seq, at least 1, and head, a hash: the last entry of the subject’s audit chain when the deletion was done (audit-chain §3); null for a subject with none
deletedarray0 to 256 classes, in ascending order of class, each exactly class, a word, count, an integer of at least 1, and root, a hash (§4)
keptarray0 to 256 classes as deleted’s, each with reason, statute, published or record (§3.3), why, a string of 1 to 1024 bytes, and until, an instant, when keeping it ends
keysarray0 to 1024 objects of exactly use, a word, and key, a key, in ascending order of key: public keys whose private halves were destroyed (a buyer’s derived key, a room’s, a hosted channel’s), each with what it was for
holdersarray0 to 1024 objects of exactly holder, a token, action, until and purges, in ascending order of holder: each other party that held any of the subject’s records or objects; action asked (it was asked to delete them; until null) or retention (its stated retention applies; until the instant it ends); purges, 0 to 4096 hashes in ascending order, the link hashes of the takedown purges it signed for them (takedown §2, §5.5)
backups_clearinstantwhen the last backup that may hold any of the records expires
signerkeythe service’s key
sigsignature§3.2

Every class is named once, in deleted or in kept. A class holds at least one record; a service that deleted nothing of a kind states no class for it.

3.2 Signature and digest

A record’s sig is Ed25519 (RFC 8032) by signer over the 17 bytes wai:data-deletion (ASCII) and 0x01, followed by the canonical form of the record without sig. It is verified strictly, as SPEC §7 Signatures requires: bad_key, bad_signature; a verifier given the keys it holds for the service refuses any other signer (signer_unknown). A record’s digest, which names it (receipt-ledger §5.2, record kind 37, and §5), is the digest of the whole record, sig included.

3.3 What is kept, and why

A kept class’s reason is one of three, and its why says it in the service’s words:

Every kept class ends: until is after deleted_at. A class kept with no end is not a deletion, and is not stated as one.

4. Classes and their tree hashes

A class’s records are named by their leaves: for a record the final export held, its record line’s digest (data-export §3.4), so that the subject checks the class against the export it holds; for anything else (a blob, a row no export carries, a record made after the final export, such as the audit entries of the deletion itself), SHA-256 over its bytes, a document’s canonical form. A class’s leaves are its records’ leaves in ascending order, none twice.

Its count is the number of its leaves, and its root is the Merkle tree hash of RFC 6962 §2.1 over them, each leaf’s 32 bytes the input of one leaf: the hash of one leaf is SHA-256 over 0x00 and the leaf, and the hash of n > 1 leaves is SHA-256 over 0x01, the hash of the first k leaves and the hash of the rest, k the largest power of two less than n. A node is never paired with itself.

A record made after the final export is a class of its own (§6.2 step 5 reads why): a class of records the export holds holds them all.

5. The leaves

The service serves a record’s leaves beside it: a document of exactly these members:

memberformmeaning
kindstring"wai-data-deletion-leaves"
versioninteger1
deletionhashthe record’s digest (§3.2)
classesarrayone object for each class of the record, deleted’s then kept’s, each in its list’s order, of exactly class, its name, and leaves, its leaves as hashes, in ascending order, none twice

The leaves are digests only: they name nothing a reader does not already hold. They are also the list of what a restored backup is held to: a record restored whose digest is a leaf of a deleted class is deleted again.

6. Verification

6.1 Inputs

A verifier is given a record’s text, its leaves’ text, the final export’s text, and either the keys it holds for the service or none.

6.2 Steps

It runs these steps and stops at the first refusal, which it reports with its reason and where: at, a list: record, leaves and the index of the class (and of a leaf in it), or export and, for the export’s own refusals, data-export §6.2’s place within it.

  1. The record, at record: a text that is not a document, a kind other than "wai-data-deletion", or a record not of §3.1’s members and forms, is deletion_malformed; a version that is an integer other than 1 is deletion_unknown_version (before the members are read); then its signature and signer (§3.2). Then, in order: arose, deleted_at and backups_clear not in that order, each at or after the one before (deletion_times_invalid); a class named twice in deleted and kept together (deletion_class_repeated); a kept class whose until is not after deleted_at (deletion_kept_ended).
  2. The leaves, at leaves: a text that is not a document, a kind other than "wai-data-deletion-leaves", or leaves not of §5’s members and forms, is deletion_malformed; a version other than 1, deletion_unknown_version; a deletion that is not the record’s digest, or classes that are not the record’s, by name and in its order (deletion_leaves_mismatch). Then each class in turn, at leaves and its index: its number of leaves not its count (deletion_count_mismatch); their tree hash (§4) not its root (deletion_root_mismatch); a leaf an earlier class holds (deletion_leaf_repeated).
  3. The final export, at export: it verifies under data-export §6 with the keys the verifier holds, its reason at export and the place within it; its digest is not the record’s export, or its account not the record’s subject (deletion_export_mismatch); it is of a part, not the whole (deletion_export_partial); it was made before the basis arose (deletion_export_early).
  4. Every record of the export, in order, at export and its line: its record line’s digest is a leaf of no class (deletion_record_unaccounted). The export’s header and trailer, and the audit checkpoint the trailer carries, are its frame, not its records: they are in no class.
  5. Every leaf of a class the export holds: a class with a leaf the export holds, that has a leaf the export does not hold, at leaves, the class’s index and the leaf’s (deletion_leaf_not_exported). So an export made early, or of part of the subject’s records, does not pass as final, and a record made after the final export is in a class of its own (§4).
  6. The audit head, at record and audit, when the export carries an audit chain: the record’s audit is null, or its seq below the export’s checkpoint’s (deletion_audit_behind); its seq the checkpoint’s and its head not the checkpoint’s (deletion_audit_mismatch). A head after the checkpoint is the chain grown after the export, the entries of the deletion among them, which the record’s classes name by their bytes (§4).

6.3 Outcome

A record that passes is accepted, with its digest, its subject, the number of records it deleted and of those it kept (the sums of its classes’ counts), the number of the export’s records it accounts for, the export’s digest and its signer.

What acceptance establishes: given the service’s key, the service states that it deleted every record of the deleted classes and kept those of the kept classes until their ends, each named by a leaf the subject can hold against what it holds; and every record the subject was handed in its final export is in that statement, once. What it does not: that the bytes are gone. No verifier can see a deletion; the record turns “we deleted it” into a statement that is signed, complete against the export, and contradicted by any copy that turns up later.

7. Reasons

codewhere
deletion_malformed§6.2 steps 1 and 2
deletion_unknown_version§6.2 steps 1 and 2
bad_key§3.2, §6.2 step 1
bad_signature§3.2, §6.2 step 1
signer_unknown§3.2, §6.2 step 1
deletion_times_invalid§6.2 step 1
deletion_class_repeated§3.1, §6.2 step 1
deletion_kept_ended§3.3, §6.2 step 1
deletion_leaves_mismatch§5, §6.2 step 2
deletion_count_mismatch§4, §6.2 step 2
deletion_root_mismatch§4, §6.2 step 2
deletion_leaf_repeated§6.2 step 2
deletion_export_mismatch§6.2 step 3
deletion_export_partial§6.2 step 3
deletion_export_early§6.2 step 3
deletion_record_unaccounted§6.2 step 4
deletion_leaf_not_exported§6.2 step 5
deletion_audit_behind§6.2 step 6
deletion_audit_mismatch§6.2 step 6

A final export that does not verify is refused with data-export §7’s codes, and its chain with audit-chain §8’s, as §6.2 step 3 states.

8. Conformance

The reference implementation is the data_deletion module of wai-rs (feature data_deletion): verify (§6), tree_hash (§4), and the writer a service uses (Deletion, its record and leaves). The corpus is live-conformance/data-deletion/, written by wai_data_deletion_vectors gen from fixed seeds: deletions, each with its record, its leaves, the final export, the keys a verifier holds (or none) and its outcome; accepted ones among them (an account closed and deleted with classes kept under each reason, an audit head at the export’s checkpoint and one after it, a subject with no audit chain, nothing kept, no key and no holder, keys not given), and one refused case for each rule of §3 to §6. Its exported records other than audit entries, and its blobs, are synthetic stand-ins, as data-export’s corpus has them. tests/data_deletion.rs requires the file to regenerate byte for byte, every case to get its stated outcome, and §7 to list exactly the codes the reference reports. live-conformance/data_deletion_verify.py is the second implementation, written from this text and sharing no code with wai-rs: it reads the export with data_export_verify.py, documents with route_record_verify.py and signatures with the shared _ed25519.py, computes RFC 6962’s tree hash itself, requires every stated outcome, mutates copies of the corpus and requires each to fail, and drops each of its own checks in turn and requires the corpus to catch it.

9. Security and privacy considerations