13 Merkle Tree Revocation

Definition 25

✓

This chapter covers merkle tree revocation aspects of AMATELUS.

13.1 Abstract

This chapter defines the detailed specification of Merkle Tree-based revocation verification flow in the AMATELUS protocol. Unlike W3C Bitstring Status List which reveals credential identification information, the Merkle Tree approach preserves zero-knowledge properties.

13.2 Background and Motivation

13.2.1 Problem with Bitstring Status List

W3C Bitstring Status List requires public disclosure of statusListIndex, creating a fundamental contradiction with Zero-Knowledge Proofs:

Traditional approach (Bitstring Status List):
  Holder -> statusListIndex -> Issuer

  Problems:
  - statusListIndex disclosure = credential identification
  - ZKP zero-knowledge property collapses
  - Privacy protection impossible

13.2.2 Design Goals

This specification achieves:

Zero-Knowledge Preservation: Specific credential presentation never identified
Revocation Safety: Revoked VCs cannot generate ZKPs
Scalability: O(log N) computation (N = active VC count)
Disaster Availability: Revocation check skippable offline
W3C VC Compatibility: Implemented as credentialStatus extension
Personal Issuer Support: Non-server-managing issuers can operate

13.2.3 Personal Issuer Challenge and Solution

Challenge

Merkle Tree revocation requires issuers to operate centralized web servers (for Merkle Root publication):

Problems:
  - Personal issuers may not maintain 24/7 HTTP servers
  - Server management costs (domain, SSL, infrastructure)
  - Difficulty guaranteeing constant availability

Solution: revocationEnabled Flag

Design Principle:

Issuers include revocation capability at issuance time
  down arrow
Holders input this flag during ZKP generation
  down arrow
Verifiers can mathematically determine revocation status

Implementation:

Issuer includes revocationEnabled: true/false in claims at issuance
This flag is under issuer signature (tamper-proof)
ZKP circuit verifies:
- revocationEnabled = true requires Merkle proof verification
- revocationEnabled = false skips Merkle proof verification
Verifier receives revocationEnabled in public ZKP inputs

Benefits:

Personal issuers require no server management (revocationEnabled = false)
Verifiers mathematically confirm revocation status (Holder cannot hide)
Organizational issuers provide high trust (revocationEnabled = true)

13.3 Architecture Overview

13.3.1 Overall Flow

┌─────────────────────┐
│   Issuer            │
│                     │
│  1. Issue VC        │
│  2. Manage Active List│
│     [H(VC_1), H(VC_2), ...] │
│  3. Generate Merkle Root │
│     root = H(...)   │
│  4. Publish Root (signed) │
└──────────┬──────────┘
           │
           │ Merkle Root + Signature
           │ (updated hourly)
           down arrow
┌─────────────────────┐
│   Holder            │
│                     │
│  1. Fetch Merkle Root │
│  2. Generate Merkle Proof │
│     proof = [h_1, h_2, ...] │
│  3. Generate ZKP    │
│     - VC content (secret) │
│     - Merkle proof (secret) │
│     - Merkle Root (public) │
└──────────┬──────────┘
           │
           │ ZKP + Merkle Root
           │
           down arrow
┌─────────────────────┐
│   Verifier          │
│                     │
│  1. Verify Merkle Root │
│     - Check issuer signature │
│  2. Verify timestamp │
│     - Check validUntil (issuer-signed) │
│     - Check version │
│  3. Verify ZKP      │
│     - Verify Merkle proof in circuit │
│     - VC in Active List? -> OK │
│     - VC not in list? -> NG │
└─────────────────────┘

13.3.2 Data Structures

Merkle Revocation List

Information managed by issuer:

structure MerkleRevocationList where
  activeVCHashes : List Hash
  merkleRoot : Hash
  updatedAt : Timestamp
  validUntil : Timestamp
  version : Nat
  issuerSignature : Signature

Merkle Proof

Inclusion proof generated by holder:

structure MerkleProof where
  leafIndex : Nat
  siblingHashes : List Hash
  treeDepth : Nat

ZKP Inputs with Revocation

Secret Inputs:

structure ZKPSecretInputWithRevocation where
  vcContent : String
  issuerSignature : Signature
  merkleProof : Option MerkleProof
  additionalSecrets : List (String * String)

Public Inputs:

structure ZKPPublicInputWithRevocation where
  revocationEnabled : Bool
  merkleRoot : Option Hash
  merkleRootVersion : Option Nat
  publicAttributes : List (String * String)
  verifierNonce : Nonce
  holderNonce : Nonce

13.4 Merkle Tree Construction

13.4.1 Hash Function

SHA-256: Merkle Tree construction (ZKP circuit compatible)
SHA3-512: Other purposes (quantum safe)

13.4.2 Tree Construction Algorithm

Input: activeVCHashes = [h_1, h_2, ..., h_n]
Output: merkleRoot

Algorithm:
  1. Padding (adjust to power of 2)
     if n not power of 2:
       pad with H("") until next power of 2

  2. Level 0 (leaves)
     leaves = activeVCHashes + padding

  3. Upward computation
     while len(leaves) > 1:
       new_level = []
       for i in range(0, len(leaves), 2):
         parent = SHA-256(leaves[i] || leaves[i+1])
         new_level.append(parent)
       leaves = new_level

  4. Return root
     return leaves[0]

13.4.3 Merkle Proof Generation

Input:
  - vcHash (VC to prove)
  - activeVCHashes (all active VCs)
  - merkleRoot (for verification)

Output: MerkleProof

Algorithm:
  1. Find VC position
     leafIndex = activeVCHashes.indexOf(vcHash)
     if leafIndex == -1: return None

  2. Collect proof path
     siblingHashes = []
     currentIndex = leafIndex
     currentLevel = activeVCHashes + padding

     while len(currentLevel) > 1:
       siblingIndex = currentIndex XOR 1
       siblingHashes.append(currentLevel[siblingIndex])
       currentIndex = currentIndex / 2
       currentLevel = computeParentLevel(currentLevel)

  3. Return proof
     return MerkleProof {
       leafIndex,
       siblingHashes,
       treeDepth = log_2(len(activeVCHashes))
     }

13.4.4 Merkle Proof Verification

Input:
  - vcHash (VC to verify)
  - proof (MerkleProof)
  - merkleRoot (expected root)

Output: Bool

Algorithm:
  1. Start from leaf
     currentHash = vcHash
     currentIndex = proof.leafIndex

  2. Compute to root
     for siblingHash in proof.siblingHashes:
       if currentIndex % 2 == 0:
         currentHash = SHA-256(currentHash || siblingHash)
       else:
         currentHash = SHA-256(siblingHash || currentHash)
       currentIndex = currentIndex / 2

  3. Compare with root
     return currentHash == merkleRoot

13.5 ZKP Circuit Integration

13.5.1 Circuit Constraints

Public Inputs:

- revocation_enabled (enablement flag from VC claim)
- merkle_root (latest, if revocation_enabled = true)
- merkle_root_version (version, if revocation_enabled = true)
- claimed_attributes (age >= 20, etc.)
- verifier_nonce
- holder_nonce

Private Inputs:

- vc_full (complete VC content)
- issuer_signature (VC signature from issuer)
- merkle_proof.leafIndex (if revocation_enabled = true)
- merkle_proof.siblingHashes (if revocation_enabled = true)
- merkle_proof.treeDepth (if revocation_enabled = true)

Constraints:

Verify issuer signature
Extract and match revocationEnabled flag from VC
Compute VC hash: vc_hash = SHA-256(Canonicalize(vc_full))
If revocation_enabled = true: Verify Merkle proof matches merkle_root
If revocation_enabled = false: Skip Merkle proof verification
Verify selective attribute disclosure
Verify nonce binding: nonce_combined = SHA-256(holder_nonce || verifier_nonce)

13.6 Issuer Operations

13.6.1 VC Issuance

With Revocation Enabled

For organizational issuers with server infrastructure:

Generate VC with revocationEnabled: true
Compute VC hash
Add to Active List
Generate Merkle Root
Publish signed Merkle Root with validUntil
Send VC + Merkle Proof to Holder

With Revocation Disabled

For personal issuers without servers:

Generate VC with revocationEnabled: false
Skip all Merkle operations
Send VC to Holder only

13.6.2 VC Revocation

For revocationEnabled = true credentials:

Receive revocation request from Holder
Compute VC hash
Remove from Active List
Generate new Merkle Root
Publish signed with new version
Log revocation for audit

For revocationEnabled = false credentials:

No revocation mechanism exists
Request holder to discard credential
Or issue replacement with revocationEnabled = true

13.6.3 Periodic Merkle Root Updates

Execute hourly (Cron Job):

Load current Active List
Recompute Merkle Root
Increment version number
Set validUntil = now() + 1 hour
Sign: issuerSignature = Sign(merkleRoot || version || validUntil)
Publish

13.7 Holder Operations

13.7.1 ZKP Generation with Revocation

When revocationEnabled = true

Extract revocationEnabled flag from VC
Fetch latest Merkle Root (verify issuer signature)
Verify Merkle Root expiration (validUntil)
Verify Merkle Proof locally
Generate holder nonce
Prepare ZKP secret inputs (include Merkle Proof)
Prepare ZKP public inputs (include merkleRoot, merkleRootVersion)
Generate ZKP
Return ZKP + revocationEnabled flag + merkleRoot + version + nonce

When revocationEnabled = false

Extract revocationEnabled flag from VC
Skip Merkle Root fetch
Skip Merkle Proof generation
Generate holder nonce
Prepare ZKP secret inputs (no Merkle Proof)
Prepare ZKP public inputs (no merkleRoot, merkleRootVersion)
Generate ZKP
Return ZKP + revocationEnabled flag + nonce

13.8 Verifier Operations

13.8.1 ZKP Verification with Revocation

When revocationEnabled = true

Fetch latest Merkle Root from issuer
Verify issuer signature on Merkle Root
Fetch historical Merkle Root (by version) used by holder
Verify issuer signature on historical root
Verify timestamp: now() <= validUntil
Verify version lag (e.g., MAX_VERSION_LAG = 5)
Verify Merkle Root matches
Verify ZKP with public inputs (revocationEnabled = true, merkleRoot, merkleRootVersion)
Verify nonce uniqueness (prevent replay)
Accept if all checks pass

When revocationEnabled = false

Check verifier policy (accept non-revocable VCs?)
If rejected by policy, return False
Verify ZKP with public inputs (revocationEnabled = false, no merkleRoot)
Verify nonce uniqueness
Log warning (revocation check skipped)
Accept if policy allows

13.8.2 Offline Verification Mode

During disasters when issuer server unavailable:

Use cached issuer public key
Verify ZKP without revocation check
Log warning (offline mode)
Accept if previous successful verification logged

13.9 W3C VC Integration

13.9.1 credentialStatus Extension

With Revocation Enabled

{
  "@context": [
    "https://www.w3.org/ns/credentials/v2",
    "https://amatelus.example/context/revocation/v1"
  ],
  "credentialStatus": {
    "id": "https://issuer.example/status/merkle/v1",
    "type": "MerkleTreeRevocationList2024",
    "merkleRootEndpoint": "https://issuer.example/api/merkle-root",
    "merkleProofEndpoint": "https://issuer.example/api/merkle-proof",
    "vcHash": "0x1234567890abcdef..."
  },
  "credentialSubject": {
    "revocationEnabled": true,
    ...
  }
}

With Revocation Disabled

{
  "@context": [
    "https://www.w3.org/ns/credentials/v2"
  ],
  "credentialSubject": {
    "revocationEnabled": false,
    ...
  }
  // no credentialStatus field
}

13.10 Security Analysis

13.10.1 Zero-Knowledge Guarantee

Method	VC Identifiable?	Information Leaked	ZK Property
Bitstring Status List	Yes	statusListIndex	No
Merkle Tree	No	merkleRoot only	Yes

Proof: Verifier receives only merkleRoot (hash of all active VCs). No information identifies specific VC. Merkle proof path remains secret in ZKP circuit.

13.10.2 Revocation Safety

Theorem (Formal Verification): When VC is revoked:

activeVCHashes no longer contains vc_hash
New merkleRoot generated without vc_hash
Holder attempts ZKP generation with revoked VC
Merkle proof verification fails in ZKP circuit
ZKP generation fails
Mathematical guarantee: revoked VCs cannot generate valid ZKPs

13.10.3 Timestamp Forgery Resistance

Problem: ZKP circuit cannot safely verify timestamps (holder controls time input)

Solution: Verifier-side verification with issuer signature

issuerSignature = Sign(merkleRoot || version || validUntil)

Verifier verification:
  1. Verify(issuerSignature, issuer_pubkey) = True
  2. now() <= validUntil

Guarantee:
  - Holder cannot forge timestamp (requires issuer private key)
  - Old merkleRoot (before revocation) cannot be used
  - Dilithium2 signature forgery requires 2^128 operations

13.10.4 Replay Attack Resistance

Dual-Nonce Mechanism:

nonce_combined = SHA-256(holder_nonce || verifier_nonce)

Protection:
- If holder's nonce generation bugs: verifier's nonce randomness protects
- If verifier's nonce generation bugs: holder's nonce randomness protects
- Replay: old nonces recorded, duplicates rejected

13.11 Computational Complexity

Operation	Complexity	Example (N=1M)
Merkle Tree Construction	O(N)	1M hash operations
Merkle Proof Generation	O(log N)	20 hash operations
Merkle Proof Verification	O(log N)	20 hash operations
ZKP Circuit Verification	O(log N)	20 SHA-256 ops

Scalability: 100 million active VCs produces Merkle proof depth = 27, requiring 27 SHA-256 computations in ZKP circuit (practical).

13.12 Implementation Checklist

13.12.1 Issuer Requirements

Active VC list database design
Merkle Tree library (SHA-256)
Hourly update Cron Job
API Endpoints: GET /api/merkle-root, GET /api/merkle-proof, POST /api/revoke
Issuer private key management (HSM recommended)
Revocation audit logging
Store multiple Merkle Root versions (latest 5+)

13.12.2 Holder Requirements

Merkle Root fetch logic
Merkle proof generation/verification
ZKP circuit integration (SHA-256, issuer signature verification, attribute extraction)
Background precomputation management
Offline mode support
Error handling (revocation notification)

13.12.3 Verifier Requirements

Issuer public key retrieval and verification
Merkle Root fetch and signature verification
ZKP verification library
Nonce management (replay prevention)
Timestamp verification
Offline mode support (optional)
Audit logging

13.13 Conclusion

This Merkle Tree revocation mechanism solves the fundamental contradiction between Verifiable Credentials’ privacy requirements and revocation safety:

Zero-Knowledge Preservation: Unlike Bitstring Status List
Revocation Guarantee: Mathematical certainty that revoked VCs cannot generate ZKPs
Timestamp Security: Issuer signature prevents Holder timestamp forgery
Scalability: O(log N) logarithmic complexity
Personal Issuer Support: No server infrastructure required (revocationEnabled = false)
Disaster Tolerance: Offline verification possible
W3C Compatible: Standard credentialStatus extension

The core innovation is the revocationEnabled flag, which enables: - Mathematical determination of revocation capability - Support for personal issuers (no server required) - Verifier policy enforcement (accept or reject non-revocable credentials) - Complete accountability (Holder cannot hide revocation status from Verifier)