Proof of Process: VDF Proof Aggregation Extension

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 10 August 2026.¶

Copyright Notice

Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.¶

Table of Contents

1. Introduction

This document defines optional mechanisms for aggregating VDF proofs to reduce verification cost. Aggregation enables O(1) or O(log n) verification of entire checkpoint chains that would otherwise require O(n) sequential VDF recomputation.¶

This extension is defined as a companion to the main Proof of Process specification [I-D.condrey-rats-pop].¶

2. Motivation

The iterated-sha256 VDF provides strong temporal guarantees but requires verifiers to recompute the entire hash chain. For a document with 1000 checkpoints, each with 10 million iterations, full verification requires 10 billion hash operations.¶

While this verification cost is acceptable for high-stakes scenarios, it creates barriers to adoption:¶

• Publishers processing thousands of submissions cannot afford O(n) verification per document.¶
• Mobile devices and web browsers may lack computational resources for full verification.¶
• Real-time verification scenarios require sub-second response.¶

VDF aggregation addresses these challenges by providing efficiently-verifiable proofs that attest to the correctness of the underlying VDF chain.¶

3. Aggregation Proof Structure

The VDF aggregate proof is an optional extension to the vdf-proof structure, identified by integer key 9.¶

; VDF aggregate proof extension
; Key 9 in vdf-proof (optional)
vdf-aggregate-proof = {
    1 => uint,                       ; checkpoints-covered
    2 => aggregation-method,         ; method
    3 => bstr,                       ; aggregate-proof
    ? 4 => aggregate-metadata,       ; metadata
}

aggregation-method = &(
    merkle-vdf-tree: 1,              ; Merkle tree over VDF outputs
    snark-groth16: 16,               ; Groth16 SNARK proof
    snark-plonk: 17,                 ; PLONK SNARK proof
    stark: 18,                       ; STARK proof
    recursive-snark: 19,             ; Recursive SNARK composition
)

aggregate-metadata = {
    ? 1 => tstr,                     ; prover-version
    ? 2 => uint,                     ; proof-generation-time-ms
    ? 3 => uint,                     ; proof-size-bytes
    ? 4 => tstr,                     ; verification-key-id
    ? 5 => bstr,                     ; verification-key
}

4. Merkle VDF Tree Aggregation

The simplest aggregation method constructs a Merkle tree over VDF inputs and outputs, enabling selective verification with O(log n) proof size.¶

For N checkpoints with VDF proofs:

Leaf{i} = H(VDF_input{i} || VDF_output{i} || iterations{i})

Internal nodes computed as standard Merkle tree:
  Node{parent} = H(Node{left} || Node{right})

Root = final tree root

Aggregate proof contains:
  - Root hash
  - Total iterations across all checkpoints
  - Optional: Merkle proofs for sampled checkpoints

; Merkle VDF tree proof structure
merkle-vdf-proof = {
    1 => hash-value,                 ; root-hash
    2 => uint,                       ; total-iterations
    3 => uint,                       ; checkpoint-count
    ? 4 => [+ merkle-sample],        ; sampled-proofs
    ? 5 => cose-signature,           ; aggregator-signature
}

merkle-sample = {
    1 => uint,                       ; checkpoint-index
    2 => [+ hash-value],             ; merkle-path
    3 => bool,                       ; vdf-verified (by aggregator)
}

5. SNARK-Based Aggregation

For constant-time verification, SNARK (Succinct Non-interactive ARgument of Knowledge) proofs can attest to the correctness of the entire VDF chain.¶

Public inputs:
  - VDF_input{0} (genesis input)
  - VDF_output{N-1} (final output)
  - total_iterations
  - checkpoint_count

Private inputs:
  - All intermediate VDF_input{i} and VDF_output{i}
  - All iteration counts per checkpoint

Circuit constraints:
  For each checkpoint i in 0..N-1:
    (1) VDF_output{i} = SHA256^iterations{i}(VDF_input{i})
    (2) VDF_input{i+1} = H(VDF_output{i} || content-hash{i+1} || ...)
    (3) sum(iterations{i}) = total_iterations

def verify_snark_aggregate(
    proof: bytes,
    vdf_input_genesis: bytes,
    vdf_output_final: bytes,
    total_iterations: int,
    checkpoint_count: int,
    verification_key: bytes
) -> bool:
    public_inputs = encode_public_inputs(
        vdf_input_genesis,
        vdf_output_final,
        total_iterations,
        checkpoint_count
    )
    return snark_verify(verification_key, public_inputs, proof)

; SNARK proof structure
snark-vdf-proof = {
    1 => snark-scheme,               ; scheme
    2 => bstr,                       ; proof-bytes
    3 => bstr,                       ; verification-key-id
    4 => [+ bstr],                   ; public-inputs (encoded)
    ? 5 => tstr,                     ; circuit-version
    ? 6 => bstr,                     ; setup-ceremony-hash
}

snark-scheme = &(
    groth16-bn254: 1,                ; Groth16 on BN254 curve
    groth16-bls12-381: 2,            ; Groth16 on BLS12-381
    plonk-bn254: 3,                  ; PLONK on BN254
    plonk-bls12-381: 4,              ; PLONK on BLS12-381
)

6. Verification Mode Selection

Verifiers SHOULD select verification modes based on the assurance level required by the Relying Party:¶

Attestation Results MUST document which verification mode was used and any associated trust assumptions.¶

7. Aggregation Proof Example

vdf-proof = {
  1: 1,
  2: {1: 1, 2: 8500000},
  3: h'genesis-input...',
  4: h'final-output...',
  5: h'',
  6: 3600.0,
  7: 30600000000,
  8: { ... },

  9: {
    1: 150,
    2: 1,
    3: h'merkle-proof-bytes...',
    4: {
      1: "witnessd-aggregator-1.0",
      2: 45000,
      3: 2048,
    }
  }
}

8. Security Considerations

VDF aggregation introduces security trade-offs:¶

• Merkle aggregation: Security equivalent to underlying hash function. No additional cryptographic assumptions. Sampled verification provides probabilistic (not cryptographic) assurance proportional to sample size.¶
• SNARK aggregation: Security depends on discrete logarithm hardness in pairing-friendly groups. Groth16 requires trusted setup; PLONK uses universal setup. Post-quantum security is NOT provided.¶
• Aggregator trust: Signed aggregates require trust in the aggregation service. Verifiers SHOULD verify aggregator identity through established PKI.¶

Full security considerations for the Proof of Process format are specified in [I-D.condrey-rats-pop].¶

9. IANA Considerations

This document has no IANA actions. The aggregation extension uses key 9 within the vdf-proof structure as defined in the main architecture document.¶

Author's Address