Psy Network: Global User Tree Aggregation (GUTA)

Once users have locally processed their transactions and generated "End Cap" proofs via their User Proving Sessions (UPS), these proofs are submitted to the Psy network. The Global User Tree Aggregation (GUTA) is the sophisticated, multi-layered Zero-Knowledge Proof (ZKP) process by which the network securely and scalably integrates these potentially millions of individual user state changes into a single, verifiable update to the Global User Tree (GUSR) and, ultimately, the entire blockchain state.

This document details the GUTA process, primarily occurring within Realms and then further aggregated by Coordinators, all powered by decentralized Proof Miners.

Overview of GUTA

The core purpose of GUTA is to:

1. Verify User End Cap Proofs: Ensure each submitted End Cap proof is valid, was generated by the correct circuit, is based on a valid historical blockchain state, and is properly authorized.
2. Prove GUSR State Transitions: For each valid End Cap proof (or pair of proofs), prove the correct state transition of the corresponding leaf (or Nearest Common Ancestor - NCA - node) in the GUSR. The GUSR stores ULEAF data for all users, including their UCON root, balance, and nonce.
3. Recursive Aggregation: Combine these individual GUSR transition proofs hierarchically using ZKPs. This means proofs for smaller GUSR subtrees are aggregated into proofs for larger subtrees, eventually culminating in a proof for the entire GUSR update.
4. Maintain Consistency: Ensure all aggregated proofs are consistent with the same global checkpoint (CHKP root) and adhere to protocol-defined circuit whitelists.
5. Collect Statistics: Aggregate statistics (like fees, transaction counts) from user sessions.

GUTA is essential for Psy's horizontal scalability. It allows the network to process a massive number of user updates in parallel and then efficiently prove their collective impact.

Phase 1: Realm-Level GUTA - Ingestion and Initial Aggregation

Realms are responsible for specific segments (shards) of the GUSR. They act as the entry point for user End Cap proofs and perform the initial layers of GUTA.

Step 1: End Cap Proof Ingestion and Verification (GUTA Entry Point)

• Action: A Realm receives an End Cap proof (and its public inputs: end_cap_result_hash, guta_stats_hash, plus the underlying end_cap_result and guta_stats data) from a user within its assigned User ID range.
• Circuits (Orchestrated by Realm, executed by Proof Miners):
  • GUTAVerifySingleEndCapCircuit: Used if a Realm is processing a single End Cap proof, perhaps as a leaf in an aggregation tree or if only one user in a subtree was active.
  • GUTAVerifyTwoEndCapCircuit: The more common base case for aggregation, processing a pair of End Cap proofs.
• Inputs/Witnesses (provided by Realm to Proof Miners):
  • The End Cap proof object(s) (proof_target) and its verifier data.
  • The claimed end_cap_result and guta_stats data corresponding to the End Cap proof(s).
  • checkpoint_historical_merkle_proof: A Merkle proof demonstrating that the checkpoint_tree_root_hash claimed in the user's end_cap_result was a valid, historical CHKP root on the Psy chain. This proof is anchored to the current block's target CHKP root (which itself is derived from the previous block's finalized CHKP root).
  • (For GUTAVerifyTwoEndCapCircuit): An UpdateNearestCommonAncestorProof witness, which is a Merkle proof detailing how the two individual user ULEAF transitions combine at their NCA in the GUSR.
  • known_end_cap_fingerprint_hash: A constant representing the fingerprint of the valid UPSStandardEndCapCircuit.
  • guta_circuit_whitelist_root_hash: The root of the Merkle tree whitelisting valid GUTA aggregation circuits (public input to the GUTA circuit).
• What it Proves:
  1. End Cap Proof Validity: Each input End Cap proof is a valid ZK proof and was generated by the circuit with known_end_cap_fingerprint_hash.
  2. Public Input Matching: The public inputs of the End Cap proof(s) correctly match the provided end_cap_result and guta_stats data.
  3. Historical Anchor: The checkpoint_tree_root_hash referenced in the user's end_cap_result is validated against the checkpoint_historical_merkle_proof. This ensures the UPS was based on a legitimate past state. The current_root of this historical proof becomes the checkpoint_tree_root for the output GUTA header.
  4. GUSR State Transition (via end_cap_result):
     • For GUTAVerifySingleEndCapCircuit: The end_cap_result (containing start_user_leaf_hash, end_user_leaf_hash, user_id) defines a direct transition for a single ULEAF in the GUSR.
     • For GUTAVerifyTwoEndCapCircuit: The UpdateNearestCommonAncestorProofOptGadget verifies that the two individual ULEAF transitions (derived from the two end_cap_results) correctly combine to produce the claimed state transition at their NCA node in the GUSR.
  5. Statistics Aggregation: (For GUTAVerifyTwoEndCapCircuit): GUTAStatsGadget.combine_with correctly sums the guta_stats from the two input End Caps.
• Output: A ZK proof for this GUTA step, and a GlobalUserTreeAggregatorHeaderGadget. This header contains:
  • guta_circuit_whitelist_root_hash (carried forward).
  • checkpoint_tree_root (derived from checkpoint_historical_merkle_proof.current_root).
  • state_transition: A SubTreeNodeStateTransitionGadget describing the proven change to the GUSR (e.g., old_node_value -> new_node_value at a specific index and level in GUSR).
  • stats: The (potentially aggregated) GUTAStatsGadget.
• Significance: This is the secure gateway for user data into the network's aggregation pipeline. It rigorously validates individual user sessions before they are combined.

Step 2: Recursive GUTA Aggregation within the Realm

• Action: The Realm continues to orchestrate the aggregation of GlobalUserTreeAggregatorHeaders produced in Step 1 or previous aggregation steps within its GUSR segment. This forms a binary tree of proofs.
• Circuits (Orchestrated by Realm, executed by Proof Miners):
  • GUTAVerifyTwoGUTACircuit: Takes two GUTA proofs (and their headers) from a lower level and aggregates them.
  • GUTAVerifyLeftGUTARightEndCapCircuit / GUTAVerifyLeftEndCapRightGUTACircuit: Aggregates an existing GUTA proof with a newly processed End Cap proof (from Step 1).
  • GUTAVerifyGUTAToCapCircuit: If a subtree has only one branch of activity, this circuit uses a "line proof" (GUTAHeaderLineProofGadget internally) to efficiently propagate a GUTA proof upwards to the Realm's GUSR segment root without needing an NCA merge.
  • GUTANoChangeCircuit: If an entire subtree within the Realm's segment had no user activity, this circuit generates a "no change" GUTA header. It verifies a checkpoint proof to get the current checkpoint_tree_root and the GUSR root from that checkpoint, then asserts that the GUSR root for its segment remains unchanged, outputting a GUTA header with a no-op transition but the updated checkpoint_tree_root. This ensures all parts of the aggregation tree are synchronized to the same global checkpoint.
• Inputs/Witnesses (General for aggregation circuits like GUTAVerifyTwoGUTACircuit):
  • Two input GUTA proofs (or one GUTA and one End Cap proof) and their respective verifier data.
  • The GlobalUserTreeAggregatorHeaderGadget witnesses corresponding to each input proof.
  • A guta_whitelist_merkle_proof for each input GUTA proof, showing its generating circuit is in the GUTA whitelist.
  • An UpdateNearestCommonAncestorProof witness if merging two branches.
  • Sibling hashes for line proofs if using GUTAVerifyGUTAToCapCircuit.
• What it Proves (General for GUTAVerifyTwoGUTACircuit):
  1. Input Proof Validity: Both input proofs (Type A and Type B) are valid ZK proofs.
  2. Whitelist Adherence:
     • If an input is a GUTA proof, its generating circuit is in the guta_circuit_whitelist_root_hash (verified using VerifyGUTAProofGadget which checks the whitelist proof).
     • If an input is an End Cap proof, its generating circuit has the known_end_cap_fingerprint_hash (verified using VerifyEndCapProofGadget).
  3. Contextual Consistency:
     • Both input proofs' headers reference the exact same checkpoint_tree_root.
     • Both input proofs' headers reference the exact same guta_circuit_whitelist_root_hash.
  4. Public Input Matching: The public inputs of each input proof correctly match their claimed GUTA/EndCap headers.
  5. NCA State Transition: The TwoNCAStateTransitionGadget correctly verifies the UpdateNearestCommonAncestorProof witness, combining the state_transitions from the two input headers into a new state_transition for their parent NCA node in the GUSR.
  6. Statistics Summation: GUTAStatsGadget.combine_with correctly sums the stats from the two input headers.
• Output: A new, higher-level GUTA ZK proof and its GlobalUserTreeAggregatorHeaderGadget.
• Significance: This recursive process efficiently scales the verification. Instead of verifying all End Caps individually at higher levels, the network only needs to verify the aggregated GUTA proofs, which represent progressively larger segments of the GUSR.

This recursive aggregation (Steps 1 & 2) continues until the Realm produces a single GUTA proof and header that represents the net state transition for the entire root of its assigned GUSR segment for the current block.

Phase 2: Coordinator-Level GUTA - Aggregating Realms

Coordinators take the final GUTA proofs from all active Realms and aggregate them further to get a proof for the entire global GUSR tree.

Step 3: Aggregating Realm GUTA Proofs

• Action: A Coordinator node receives the final GUTA proofs (and their headers) from multiple Realms.
• Circuits (Orchestrated by Coordinator, executed by Proof Miners):
  • Primarily GUTAVerifyTwoGUTACircuit (to merge GUTA proofs from two different Realms or two aggregated sets of Realms).
  • GUTAVerifyGUTAToCapCircuit (to propagate a single Realm's GUTA proof or an already aggregated GUTA proof up to the global GUSR root if it's the only activity in a larger branch).
  • GUTANoChangeCircuit might be used if an entire large section of the GUSR spanning multiple Realms had no activity.
• Process: This is structurally identical to the recursive aggregation within a Realm (Step 2 above), but the "leaves" of this aggregation level are the root GUTA proofs from each Realm. The NCA logic now applies to nodes higher up in the GUSR tree, potentially merging transitions from different Realm segments.
• Output: A single GUTA ZK proof and its GlobalUserTreeAggregatorHeaderGadget that represents the net state transition for the root of the entire Global User Tree (GUSR) for the current block. This header will contain the total aggregated GUTAStats from all user activity in the block.

Integration with Other Global State Changes

The GUTA process specifically handles updates to the GUSR. Other global trees like GCON (Global Contract Tree, for new contract deployments) and URT (User Registration Tree, for new user registrations) are updated by separate, dedicated batch append circuits orchestrated by the Coordinator:

• User Registrations: BatchAppendUserRegistrationTreeCircuit generates a proof for appending new user registrations to URT.
• Contract Deployments: BatchDeployContractsCircuit generates a proof for appending new contract definitions to GCON.

These proofs, along with the final GUTA proof for GUSR changes, are then fed into the "Part 1" Aggregation circuit.

VerifyAggUserRegistartionDeployContractsGUTACircuit (Part 1 Aggregation)

• Action: The Coordinator orchestrates this crucial aggregation step.
• Circuit (Executed by Proof Miners): VerifyAggUserRegistartionDeployContractsGUTACircuit.
• Inputs:
  • The final aggregated GUTA proof (for GUSR changes).
  • The aggregated User Registration proof (for URT changes).
  • The aggregated Contract Deployment proof (for GCON changes).
• What it Proves:
  • All three input proofs are valid and were generated by their respective whitelisted circuits.
  • Crucially, all three input proofs (and the operations they represent) are based on the same consistent checkpoint_tree_root context (i.e., they all started from the same previous block's finalized state).
• Output: A "Part 1" ZK proof and a VerifyAggUserRegistartionDeployContractsGUTAHeader. This header summarizes the new root hashes for GUSR, URT, and GCON, and carries forward the total GUTAStats.

This "Part 1" proof is then one of the main inputs to the PsyCheckpointStateTransitionCircuit, which generates the final block proof, as detailed in the "End-to-End Block Production Journey" document.

Security and Efficiency of GUTA

• Security:
  • ZK Proof Soundness: Mathematical guarantee against invalid state transitions.
  • Circuit Whitelisting: Only authorized GUTA and End Cap circuits can contribute to the aggregation, enforced by Merkle proofs against guta_circuit_whitelist_root_hash and checks against known_end_cap_fingerprint_hash.
  • Recursive Verification: Each layer cryptographically verifies the layer below.
  • Checkpoint Anchoring: All GUTA operations are tied to a specific checkpoint_tree_root, ensuring consistency with global state.
• Efficiency:
  • Parallelism: End Cap proofs can be processed and aggregated in parallel across different Realms and even within subtrees of a Realm. Proof Miners can work on different aggregation jobs concurrently.
  • Logarithmic Scaling: The tree-like aggregation structure means the number of sequential aggregation steps grows logarithmically with the number of users/proofs, contributing to Psy's O(log(n)) block times.
  • Proof Compression: Millions of user transactions are ultimately represented by a few aggregated proofs leading into the final block proof.

GUTA is a sophisticated ZKP engineering feat that allows Psy to securely scale user state management to levels previously unattainable in blockchain systems, forming the backbone of its high-throughput capabilities.