Redactable blockchain.

Lecture 23 moved from two parties to $n$ and from garbling (evaluating a circuit in encrypted form) to algebra. A $t$-out-of-$n$ secret sharing scheme splits a secret so that $t+1$ parties recover it and $t$ learn nothing; Shamir's construction achieves this by placing the secret at $p(0)$ for a random polynomial of degree at most $t$ and handing party $i$ the value $p(i)$, with privacy that is information-theoretic, independent of any computational assumption. Because sharing is linear, additions and multiplications by public constants are computed locally with no communication. Multiplication is not linear: local products encode the right value but as a degree-$2t$ polynomial, so each party re-shares its product share and everyone takes the same Lagrange combination, restoring the invariant at the cost of one round per multiplicative layer. With an honest majority the honest parties alone can reconstruct, which is what finally yields fairness and guaranteed output delivery, and the GMW (Goldreich-Micali-Wigderson) compiler lifts the protocol to malicious security (security against parties that deviate from the protocol) using zero-knowledge proofs (which reveal nothing beyond the truth of the statement).

This applications lecture is where the three parts of the course meet. The chain structure comes from Chapter 6: blocks linked by collision-resistant hash pointers, transactions committed through a Merkle tree (a tree of hashes that commits to every transaction in the block), making the entire structure append-only by construction. The collision resistance itself comes from Chapter 1, and the group-based trapdoor construction from Chapter 2. The distributed use of the trapdoor comes from the previous lecture.

The motivation is legal and operational, so the cryptography serves it. Hard forks (community-agreed changes to a chain's rules) are already used to repair human error, and the DAO (Decentralized Autonomous Organization) fork on Ethereum reversed a $60 million theft. The GDPR (General Data Protection Regulation)'s right to be forgotten collides with an append-only ledger, with fines up to 4% of annual revenue; the Open Data Institute observes that immutable storage may be incompatible with legislation requiring changes to the official truth. Metadata alone can be revealing. The European Union Agency for Cybersecurity (ENISA) asks for standard methods of removing data from a ledger; The European Securities and Markets Authority (ESMA) notes that immutability is ill-suited to securities markets, where operational errors sometimes require cancelling a transaction.

The construction is a chameleon hash: collision resistant to holders of the public hash key, but efficiently invertible for anyone with a trapdoor, so a block can be edited and the pointer to it repaired. The naive discrete-log (discrete logarithm) construction is exhibited and then broken: a single published collision solves for the trapdoor. This failure motivates enhanced collision resistance, where a collision oracle does not help produce a fresh collision. Two governance answers follow. In the permissioned design (run by a fixed set of known authorities) of Ateniese, Magri, Venturi and Andrade the trapdoor is secret-shared among authorities, none of whom holds it, and collisions are computed by a Multi-Party Computation (MPC) protocol. Each redaction leaves a visible audit record. In the permissionless design (open to anyone, like Bitcoin) of Deuber, Magri and Thyagarajan there is no trapdoor at all: blocks carry two links, miners vote for a candidate redaction over an epoch (a fixed span of blocks), and validation checks both links plus the approval. Both designs give up immutability; what each settles is who may rewrite history and how visibly.

1. Motivation and the regulatory record: the applications that need an editable ledger, the GDPR (General Data Protection Regulation) case and the ODI (Open Data Institute), ENISA (European Union Agency for Cybersecurity) and ESMA (European Securities and Markets Authority) findings, in the order the slides give them.
2. Chameleon hashing: the definition, the group construction and the proof that one collision exposes the trapdoor. This section pairs with Chapter 1 on collision resistance and Chapter 2 on the discrete-logarithm setting.
3. Enhanced collision resistance and the redaction record: the security notion that makes the scheme usable, and why removal is never silent.
4. Who holds the trapdoor: back to secret sharing and threshold cryptography (splitting a key among parties so no one holds it alone) for one paragraph; the trapdoor is shared and used only through a distributed protocol.
5. The permissionless variant (open for anyone to join): two links per block, the candidate pool (proposed redactions), epoch-long (a fixed span of blocks) voting with a stated policy, the validation rules and the Bitcoin integration where the redacted transaction is replaced by its own hash inside the Merkle tree (the hash tree that commits to the block's transactions).

• Show that the textbook chameleon hash (a public hash whose secret trapdoor lets its holder find collisions) leaks its trapdoor after a single redaction: two lines of modular algebra plus the property that repairs it.
• Why $t$ shares reveal nothing: the guarantee the authorities are relying on when they hold the trapdoor between them.
• Multiplication and degree reduction (the step that brings product shares back to the original degree): the cost of computing a collision without reconstructing the trapdoor.