Chapter 4: Blockchain & Immutable Systems

The Blockchain Paradox

Blockchain technology presents a fundamental paradox for the right to be forgotten. Blockchains are designed to be immutable—once data is written to the blockchain, it cannot be altered or deleted. This immutability is precisely what makes blockchains valuable for applications like cryptocurrency, supply chain tracking, and digital identity. Yet privacy regulations require that personal data can be deleted upon request. How can these seemingly incompatible requirements be reconciled?

The tension between blockchain immutability and data protection law has sparked intense debate among technologists, lawyers, and regulators. Some argue that blockchains are fundamentally incompatible with GDPR and similar regulations. Others propose innovative technical solutions that preserve the benefits of blockchain while enabling compliance with deletion requirements. This chapter explores the challenges and emerging solutions for implementing the right to be forgotten in blockchain systems.

Understanding Blockchain Immutability

To understand the challenge, we must first understand why blockchains are immutable. A blockchain is a distributed ledger where data is organized into blocks that are cryptographically linked together. Each block contains:

• Transaction data
• A timestamp
• A cryptographic hash of the previous block
• A nonce (for proof-of-work systems)

This structure creates a chain where modifying any historical block would change its hash, breaking the chain and making the alteration evident to all participants. The distributed nature of blockchains—with copies of the ledger maintained by many nodes—makes it practically impossible to alter history without detection and consensus from the network majority.

For public blockchains like Bitcoin and Ethereum, there may be tens of thousands of independent nodes maintaining copies of the complete blockchain. Coordinating deletion across all these independent parties is not only technically infeasible but would undermine the trust model that makes blockchains valuable.

Personal Data on Blockchains

Before addressing solutions, we must identify what constitutes personal data on blockchains. GDPR defines personal data broadly as any information relating to an identified or identifiable natural person. In blockchain contexts, this can include:

• Direct Identifiers: Names, email addresses, phone numbers stored on-chain
• Pseudonymous Identifiers: Wallet addresses, public keys (potentially identifiable through linking with off-chain data)
• Transaction Metadata: Patterns of transactions that could identify individuals
• Smart Contract Data: Personal information embedded in smart contract state or events
• Hashes of Personal Data: Even cryptographic hashes may be considered personal data if they can be linked to individuals

The European Union Blockchain Observatory & Forum and various Data Protection Authorities have provided guidance that wallet addresses and transaction data can constitute personal data when they can be linked to identifiable individuals, even if they are pseudonymous rather than directly identifying.

Solution 1: Encryption with Key Destruction

The most widely accepted solution for reconciling blockchain immutability with deletion rights is to encrypt personal data before storing it on-chain, then destroy the encryption keys when deletion is required. This approach provides "cryptographic erasure"—the data technically remains on the blockchain, but it has been rendered permanently inaccessible and unreadable.

How Cryptographic Erasure Works

// Encrypt data before blockchain storage
function storePersonalData(data: PersonalData): BlockchainRecord {
    // Generate unique encryption key for this data
    const encryptionKey = generateSecureKey();

    // Encrypt personal data
    const encryptedData = encrypt(data, encryptionKey);

    // Store encrypted data on blockchain
    const txHash = blockchain.store(encryptedData);

    // Store encryption key securely off-chain with reference to data
    keyManagementSystem.store(data.userId, {
        dataHash: txHash,
        encryptionKey: encryptionKey,
        createdAt: Date.now()
    });

    return { txHash, encrypted: true };
}

// Delete data by destroying encryption key
async function deletePersonalData(userId: string): Promise {
    // Retrieve encryption keys for user
    const keys = await keyManagementSystem.getUserKeys(userId);

    // Provably destroy all keys
    const destructionProofs = [];
    for (const keyRecord of keys) {
        const proof = await securelyDestroyKey(keyRecord.encryptionKey);
        destructionProofs.push({
            keyId: keyRecord.keyId,
            dataHash: keyRecord.dataHash,
            destructionMethod: proof.method,
            timestamp: proof.timestamp,
            witness: proof.witness
        });
    }

    // Generate deletion certificate
    return {
        userId: userId,
        keysDestroyed: destructionProofs.length,
        method: 'cryptographic_erasure',
        proofs: destructionProofs,
        irreversible: true,
        certificateHash: hashCertificate(destructionProofs)
    };
}

Key Destruction Protocols

For cryptographic erasure to be credible, key destruction must be provable and irreversible. Several approaches exist:

• Secure Key Deletion: Use hardware security modules (HSMs) that can provably destroy keys
• Threshold Cryptography: Split keys across multiple parties; destroy sufficient shares to make reconstruction impossible
• Blockchain-Based Destruction: Record key destruction on a separate blockchain to create an immutable audit trail
• Witness-Based Destruction: Have trusted third parties witness and attest to key destruction

Solution 2: Off-Chain Data Storage

Instead of storing personal data directly on the blockchain, store only references or hashes while keeping the actual personal data off-chain in traditional databases that support deletion. The blockchain records proof of data existence and integrity without containing the data itself.

Hash-and-Store Architecture

// Store personal data off-chain with blockchain reference
class OffChainDataManager {
    async storeWithBlockchainProof(data: PersonalData): Promise {
        // Calculate hash of personal data
        const dataHash = sha256(JSON.stringify(data));

        // Store data in traditional database
        const offChainId = await this.database.insert({
            userId: data.userId,
            data: data,
            dataHash: dataHash,
            createdAt: new Date()
        });

        // Store only the hash on blockchain
        const blockchainTx = await this.blockchain.storeHash({
            dataHash: dataHash,
            offChainReference: offChainId,
            timestamp: Date.now()
        });

        return {
            offChainId: offChainId,
            blockchainTxHash: blockchainTx.hash,
            dataHash: dataHash
        };
    }

    async deleteWithVerification(userId: string): Promise {
        // Delete data from off-chain database
        const deletedRecords = await this.database.delete({ userId: userId });

        // Generate proof of deletion
        const deletionProof = {
            userId: userId,
            recordsDeleted: deletedRecords.length,
            deletionTimestamp: new Date(),
            verificationHash: this.generateVerificationHash(deletedRecords)
        };

        // Optionally record deletion event on blockchain
        await this.blockchain.recordDeletion({
            userId: hashUserId(userId), // Pseudonymized
            recordCount: deletedRecords.length,
            deletionProof: deletionProof.verificationHash
        });

        return deletionProof;
    }
}

IPFS and Distributed Storage

For decentralized applications, personal data can be stored on IPFS (InterPlanetary File System) or similar distributed storage with encryption, while the blockchain stores only content identifiers (CIDs). Deletion involves removing files from IPFS nodes and destroying encryption keys.

Solution 3: Permissioned Blockchains with Admin Functions

Private or consortium blockchains can include administrative functions that allow authorized parties to modify or delete data in specific circumstances. While this reduces some decentralization benefits, it provides greater compliance flexibility.

Chameleon Hashes and Redactable Blockchains

Research into "redactable blockchains" uses chameleon hash functions—cryptographic hashes that can be modified by parties holding a secret trapdoor key. This enables selective editing of blockchain content while maintaining verifiability. Key holders (e.g., data protection officers) could redact personal data when required by law.

// Conceptual implementation of redactable blockchain
class RedactableBlockchain {
    private trapdoorKey: TrapdoorKey;

    async addBlock(data: BlockData): Promise {
        // Create chameleon hash of previous block
        const prevHash = this.chameleonHash(
            this.chain[this.chain.length - 1],
            this.generateRandomness()
        );

        const block = {
            data: data,
            previousHash: prevHash,
            timestamp: Date.now(),
            nonce: this.mineBlock(data)
        };

        this.chain.push(block);
        return block;
    }

    async redactData(blockIndex: number, newData: BlockData): Promise {
        if (!this.isAuthorized(this.currentUser)) {
            throw new Error('Unauthorized redaction attempt');
        }

        const block = this.chain[blockIndex];

        // Find collision using trapdoor to maintain hash consistency
        const newRandomness = this.findCollision(
            block.data,
            newData,
            this.trapdoorKey
        );

        // Update block while maintaining hash chain
        this.chain[blockIndex].data = newData;
        this.chain[blockIndex].randomness = newRandomness;

        // Log redaction for audit
        await this.auditLog.record({
            action: 'redaction',
            blockIndex: blockIndex,
            timestamp: Date.now(),
            authorizedBy: this.currentUser,
            reason: 'GDPR_Article_17'
        });
    }
}

Solution 4: Zero-Knowledge Proofs

Zero-knowledge proofs (ZKPs) allow verification of facts about data without revealing the data itself. For example, a blockchain could verify that a person is over 18 without storing their birthdate, or confirm creditworthiness without recording financial details. This minimizes personal data on-chain, reducing deletion obligations.

zk-SNARKs for Privacy-Preserving Verification

zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) enable complex verifications with minimal on-chain data. For instance, identity verification could occur entirely off-chain, with only a cryptographic proof recorded on the blockchain. When deletion is needed, only the proof (which contains no personal data) remains.

Smart Contract Considerations

Smart contracts on platforms like Ethereum present special challenges. Contract code and state are immutable once deployed. Strategies for managing personal data in smart contracts include:

• Avoid Storing Personal Data: Design contracts to reference external data rather than storing it on-chain
• Use Encrypted References: Store only encrypted identifiers with keys managed off-chain
• Implement Access Controls: Add functions that can disable access to personal data
• Upgradeable Contracts: Use proxy patterns allowing data migration to new contract versions

// Privacy-respecting smart contract pattern
contract PersonalDataReference {
    // Store only encrypted reference, not actual data
    mapping(address => bytes32) private encryptedReferences;

    // Track active status
    mapping(address => bool) private activeReferences;

    // Store reference to off-chain data
    function storeReference(bytes32 encryptedRef) external {
        encryptedReferences[msg.sender] = encryptedRef;
        activeReferences[msg.sender] = true;
    }

    // "Delete" by marking inactive and overwriting
    function deleteReference() external {
        require(activeReferences[msg.sender], "No active reference");

        // Mark as inactive
        activeReferences[msg.sender] = false;

        // Overwrite with random data (best effort erasure)
        encryptedReferences[msg.sender] = keccak256(
            abi.encodePacked(block.timestamp, msg.sender)
        );

        emit ReferenceDeleted(msg.sender, block.timestamp);
    }

    // Verify reference exists without revealing it
    function verifyReference() external view returns (bool) {
        return activeReferences[msg.sender];
    }
}

Regulatory Guidance and Compliance

Regulatory authorities have begun providing guidance on blockchain and GDPR compatibility:

• French CNIL: Published guidance stating that using encryption with provable key destruction can constitute effective erasure
• European Data Protection Board: Emphasized that organizations using blockchain must ensure GDPR compliance, suggesting off-chain storage and encryption
• UK ICO: Issued guidance on blockchain and data protection, recommending minimization of personal data on-chain

Best Practices for Blockchain Projects

1. Data Minimization: Store minimal personal data on-chain; use references and hashes instead
2. Encryption by Default: Encrypt all personal data before blockchain storage
3. Off-Chain Storage: Keep personal data in traditional databases; use blockchain only for integrity verification
4. Key Management: Implement robust key management with provable destruction capabilities
5. Permissioned Chains: Consider private blockchains for use cases requiring data deletion
6. Privacy by Design: Incorporate privacy considerations from the earliest design stages
7. Alternative Technologies: Evaluate whether blockchain is truly necessary or if traditional databases would better serve the use case