ACE-GF-based Attestation Relay for PQC - Lightweight Mempool Propagation Without On-Path Proofs

The paper introduces AR-ACE, a lightweight mempool propagation protocol for post-quantum blockchains that eliminates on-path validity proofs by having relay nodes forward only objects with compact attestations, thereby achieving an order-of-magnitude bandwidth reduction while shifting proof verification entirely to the builder.

The Gist

🚀 The Big Problem: The "Heavy Luggage" Crisis

Imagine a massive, high-speed train system (the Blockchain) that needs to move millions of packages (transactions) every second.

In the future, to make this system safe from quantum computers, every package needs a giant, heavy, iron-clad security seal (a STARK proof). This seal is huge—about the size of a small house (128 KB).

The Old Way (Recursive STARKs):
Currently, the plan was for every train station (node) to check every package, attach a giant iron seal to it, and then create a new giant master seal that says, "I checked all the packages on my train."

• The Result: The train tracks get clogged with heavy iron seals. The stations are exhausted trying to forge these seals. It works, but it's slow, expensive, and the tracks are jammed with "proofs" instead of actual packages.

💡 The Big Idea: "Proof-Off-Path"

The authors of this paper ask a simple question: "Do we really need to carry the heavy iron seal all the way to the final destination?"

They propose a new system called AR-ACE. Instead of carrying the heavy seal, the train stations only carry a tiny, lightweight postcard (an Attestation).

• The Postcard: It's a tiny note that says, "I, [Station Name], swear this package looks legitimate and belongs in the system." It's small (like a few bytes).
• The Heavy Seal: The giant iron seal is only created at the very end, by the Builder (the final station that loads the train onto the main track).

🎭 The Characters in Our Story

1. The Submitter (The Sender):

   • Role: They drop off a package.
   • Action: They attach a tiny postcard signed with their ID. They don't need to prove the package is perfect yet; they just need to prove they are allowed to send it.

2. The Relay Nodes (The Train Stations):

   • Role: They pass packages from one station to the next.
   • Action: They look at the postcard. Is the signature valid? Is the sender allowed? If yes, they pass the package along.
   • Crucial Change: They do not check if the package is actually valid (e.g., they don't check if the math inside is correct). They don't carry the heavy iron seal. They just trust the postcard to keep the flow moving.

3. The Builder (The Final Station):

   • Role: The one who actually loads the train and sends it to the world.
   • Action: They collect all the packages that arrived with valid postcards. Then, they do the heavy lifting: they check every single package for real, and they create one single, giant master seal for the whole batch.
   • Result: The world only sees one big seal for thousands of packages, not thousands of seals.

⚖️ Why is this a Game Changer?

1. Bandwidth Savings (The Highway Analogy)
Imagine a highway.

• Old Way: Every car carries a 10-ton safe in the trunk. The highway is clogged; traffic moves at 1 mph.
• AR-ACE: Every car carries a tiny receipt in the glovebox. The highway is empty; traffic moves at 100 mph.
• The Math: The paper shows this reduces the "proof traffic" by 10 times or more. The network stops choking on heavy data.

2. Spam Protection (The Toll Booth)
You might ask: "If the stations don't check the packages, won't spammers flood the system with junk?"

• The Fix: The "Postcard" isn't free to make. It requires a small fee, a bond (money locked up), or a specific identity. If a spammer tries to flood the network, they have to pay for thousands of postcards. It becomes too expensive to spam. The stations just check if the postcard is paid for and valid, then pass it on.

3. The "ACE-GF" Superpower (The Master Key)
The paper suggests using a special technology called ACE-GF to make these postcards.

• The Analogy: Imagine you have one Master Key for your house (your identity).
  • You use one part of the key to unlock your front door (on-chain authorization).
  • You use a different, isolated part of the same key to sign your postcards (relay attestation).
• Why it's cool: You don't need to manage two different keys. If the "postcard key" gets hacked, your "front door" is still safe. It's one identity, one backup, but perfectly separated duties.

🏁 The Conclusion

AR-ACE is like changing the rules of a relay race.

• Before: Every runner had to carry a heavy, fragile vase (the proof) all the way to the finish line. If they dropped it, the race stopped.
• Now: Every runner carries a small, durable baton (the attestation). They just need to prove they are a legitimate runner. Only the person crossing the finish line (the Builder) has to inspect the vase to make sure it's real.

The Result: The race is faster, the runners are less tired, and the system is ready for the future (Post-Quantum) without breaking under the weight of its own security.

Technical Summary

Here is a detailed technical summary of the paper "AR-ACE: ACE-GF-based Attestation Relay for PQC—Lightweight Mempool Propagation Without On-Path Proofs."

1. Problem Statement

In post-quantum (PQC) blockchain environments, the propagation of valid objects (e.g., blob roots, transaction batches, signature aggregates) faces a critical bandwidth bottleneck.

• The Cost of Proofs: Validity in a PQC setting often relies on STARKs, which are large (approx. 128 KB per proof).
• The Bandwidth Explosion: If every object is propagated with its full validity proof, network bandwidth scales linearly with the number of objects ($O(N \times 128\text{KB})$), quickly becoming prohibitive.
• Limitations of Recursive STARKs: Previous solutions (e.g., Buterin's recursive STARKs) aggregate proofs so each node sends only one proof per tick. While this caps proof bandwidth, it still requires every relay node to generate, hold, and forward these heavy proofs, maintaining a significant computational and bandwidth overhead on the propagation path.

Core Question: Is it necessary to carry full validity proofs on the propagation path at all? The authors argue that relay nodes only need to ensure an object is eligible for relay, not that it is fully valid. Full validity can be deferred to the final verifier (the block builder).

2. Methodology: AR-ACE Design

The paper proposes AR-ACE (ACE-GF-based Attestation Relay for PQC), a "proof-off-path" propagation architecture.

A. Core Mechanism

Instead of forwarding objects with full validity proofs, the network forwards objects accompanied by compact attestations.

• Attestation Credential: A lightweight cryptographic binding (e.g., a signature or commitment) linking the object hash (objHash), a domain separator, and a nonce to an identity.
• Role Separation:
  • Submitters: Generate objects and sign them with an attestation key.
  • Relay Nodes: Verify only the attestation (checking signature validity, key eligibility, and replay protection). They do not verify the object's full validity (e.g., erasure coding or complex signature aggregation) and do not generate or forward STARKs.
  • Builder: Collects objects and attestations, selects a set to include, and generates a single aggregated validity proof (e.g., a recursive STARK) over the entire set. This proof is published with the block.

B. Instantiation with ACE-GF

While the architecture is generic, the paper highlights ACE-GF (a post-quantum identity framework) as the preferred instantiation:

• Unified Identity: The same Root Entropy Value (REV) used for on-chain authorization derives a dedicated, context-isolated attestation key for the mempool.
• Context Isolation: The relay key is derived under a specific context (Ctxrelay), ensuring that a compromised relay key does not expose the user's signing or authorization keys.
• PQC Readiness: The system can utilize PQC signatures (e.g., ML-DSA) for attestations, keeping the entire pipeline post-quantum secure without requiring separate identity management.

C. Protocol Flow

1. Submission: Submitter sends (Object, Attestation) to the network.
2. Relay: Nodes verify the attestation signature and check against quotas/denylists. If valid, they forward (Object, Attestation). No STARKs are generated.
3. Inclusion: The builder selects objects, verifies their validity via a single aggregated proof $\Pi$, and publishes the block.

3. Key Contributions

1. Proof-Off-Path Architecture: A novel design where validity proofs are entirely removed from the relay path, shifting the heavy cryptographic burden solely to the block builder.
2. Bandwidth Efficiency: Demonstrates an order-of-magnitude reduction in proof-related relay bandwidth compared to recursive STARK propagation.
3. Formal Security Model: Defines three security games to validate the system:
   • Attestation Forgery: Ensures attackers cannot forge valid attestations.
   • Replay/Cross-Domain: Ensures attestations cannot be reused for different objects or domains.
   • Admission Bypass: Ensures policy violations (e.g., quota breaches) are enforced.
4. ACE-GF Integration: Provides a blueprint for integrating AR-ACE with ACE-GF to achieve unified identity, context isolation, and PQC consistency.
5. Analytical Comparison: Provides a structural bandwidth and CPU analysis showing that AR-ACE eliminates proof traffic on the path, reducing relay node CPU load significantly (provided heavy verification costs exceed light attestation costs by a specific threshold).

4. Results and Performance Analysis

• Bandwidth Reduction:
  • Recursive STARK Approach: Requires $\approx 128\text{KB} \times \text{degree}$ per tick per node (e.g., ~2 MB/s for a standard node).
  • AR-ACE Approach: Zero proof traffic on the path. Only objects and small attestations (64–256 bytes for classical, ~2.5 KB for PQC) are transmitted.
  • Result: An order-of-magnitude reduction in proof-related bandwidth.
• CPU Efficiency:
  • Relay nodes perform lightweight signature verification ($cl$) rather than heavy STARK generation/verification ($ch$).
  • The paper calculates that if the ratio of heavy-to-light verification cost ($ch/cl$) exceeds ~41.67, AR-ACE yields significant relay-side CPU savings.
• Security: Theoretical proofs confirm that under standard assumptions (EUF-CMA signatures, collision-resistant hashing), the probability of forgery or admission bypass is negligible.

5. Significance

• Scalability for Post-Quantum Blockchains: AR-ACE solves the fundamental scalability issue of PQC mempools, where large proof sizes would otherwise render high-throughput networks infeasible.
• Decoupling Propagation from Verification: By separating "eligibility" (relay) from "validity" (builder), the system optimizes the network for speed and bandwidth while maintaining strong security guarantees at the consensus layer.
• Identity Coherence: The integration with ACE-GF offers a streamlined user experience, unifying on-chain authorization and off-chain relay identity under a single root, while maintaining strict security isolation.
• Future-Proofing: The design is agnostic to the specific validity predicate (erasure coding, signatures) and supports hybrid or full-PQC modes, making it adaptable to evolving cryptographic standards.

In conclusion, AR-ACE represents a paradigm shift in mempool design, moving from "proof-carrying" to "attestation-carrying" propagation, enabling efficient, secure, and post-quantum-ready blockchain networks.