Proof System

The cryptographic layer for independently verifiable signature attestations, account-state proofs, and chain commitments. Sahyadri combines native transaction verification with asynchronous STARK generation and compact chain-commitment aggregation. The measured chain-aggregation result at 4444 leaves verifies in 1.5 milliseconds under the tested configuration.

1. Formal Definition

Sahyadri's proof system provides separate mechanisms for signature attestations, account-state verification, hash verification, and chain-commitment aggregation. Transaction signatures and state transitions are validated during block processing. Dedicated proof workers asynchronously generate signature-attestation STARK proofs after block acceptance. These proofs and commitments do not constitute a recursive proof of every block's complete validity.

Definition 1.1 (Block proof system)

  A block proof system is a triple (Prove, Verify, Aggregate):

    Prove(σ_prev, B, σ_new)          → π_block
    Verify(σ_prev, B, σ_new, π_block) → {⊤, ⊥}
    Aggregate(π_left, π_right)       → π_parent

  satisfying:

  Completeness:
    ∀ valid transitions (σ_prev → σ_new under B):
      Verify(σ_prev, B, σ_new, Prove(σ_prev, B, σ_new)) = ⊤

  Soundness:
    ∀ invalid transitions, ∀ π*:
      Pr[Verify(σ_prev, B, σ_new, π*) = ⊤] ≤ 2^-80 + negl(λ)

  Aggregation soundness:
    Verify-Aggregate(π_parent) = ⊤
      ⟺ Verify(π_left) = ⊤ ∧ Verify(π_right) = ⊤

Sahyadri's instantiation has four distinct proof types, each with its own AIR (Algebraic Intermediate Representation). They are not interchangeable — each proves a different statement, at a different constraint count, with a different proof size.

2. The Four Proof Types

Sizes and times measured on Core Ultra 5 (18 threads), release build. Constraint counts are approximate; exact counts vary with input widths.

Proof typeStatement provenConstraintsSizeVerify
Dilithium batchN ML-DSA-65 signatures valid~30,000/sig631-735 KB (N=2..8)35 ms
SMT state proofkey → value at committed root~5,000/path~2 KB typical<1 ms
Poseidon2 hash proofhash(preimage) = output~300/permute~1 KB~1 ms
Chain aggregationπ_{n-1} valid ∧ B_n valid~5,000/link~350 KB (extrapolated at 4444 leaves)1.5 ms

These components serve different purposes and should not be treated as interchangeable proofs. Signature batch proofs attest to configured ML-DSA-65 verification statements. SMT state proofs establish account inclusion or exclusion against a committed root. Poseidon2 hash verification checks hash computations. Chain aggregation links proof commitments; the current Path B result does not recursively establish the validity of every underlying batch proof.

3. What a Block Proof Attests

A block carries a proof that attests to three statements simultaneously. The three are not separate proofs; they are composed into one at the block level.

Statement proven per block B_n:

  (1) Signature validity
      ∀ tx ∈ B_n.transactions:
        Verify_ML-DSA-65(tx.signature, tx.pubkey, sighash(tx)) = ⊤

  (2) State transition correctness
      δ(B_n.parent_state, B_n) = B_n.resulting_state
      (δ is the pure transition function — see Account Model)

  (3) Hash computation correctness
      ∀ node in SMT path updated by B_n:
        H_leaf or H_branch was computed correctly

  The three statements are composed into one batch proof via
  recursive aggregation. The block header commits to:
    - account_commitment = resulting SMT root
    - chain_commitment = hash(parent_chain_commitment ‖ proof_hash)

  A verifier who checks the batch proof once obtains a guarantee
  of all three simultaneously.

4. Aggregation vs Compression

"Aggregation" is frequently misused to mean "signature compression." The distinction matters because the two have different costs and different guarantees.

Signature compression:

  Given N signatures σ_1, ..., σ_N, produce one signature σ_agg
  such that σ_agg attests to all N.

  Result:   |σ_agg| < |σ_1| + ... + |σ_N|
  Effect:   Wire savings per transaction
  Status:   Not implemented. Requires a signature scheme with
            aggregate verification (BLS, or a custom construction
            with pairing-based aggregation).

Proof aggregation (Sahyadri):

  Given N proofs π_1, ..., π_N, produce one proof π_agg
  such that π_agg attests to the validity of all N.

  Result:   |π_agg| bounded, but larger than any single signature
  Effect:   Verification cost is O(1), not O(N)
  Status:   Implemented and measured

  At 4444 blocks:
    Raw signature bytes:    4444 × 3309 B ≈ 14.7 MB
    Aggregated chain proof: ~200 KB
    Reduction:              ~18,000×

  The ~200 KB object is not a signature. It is a commitment
  structure that attests to the validity of a chain of proofs,
  each of which attests to the validity of signatures. The
  18,000× reduction is real, but it is at the proof level,
  not at the signature level.

Sahyadri does not compress signatures. It aggregates proofs. A block of 8 transactions produces a 735 KB batch proof — the size of the batch proof is bounded by the AIR complexity, not by the number of signatures. A truly compressed signature would be ~128 B regardless of N; Sahyadri's batch proof is not that.

5. Batch Proving

Batch proving composes N signature proofs into one via a binary tree. Pairs of proofs are aggregated, then pairs of results, and so on. N proofs require ⌈log₂ N⌉ aggregation levels.

Batch-Prove: (Signature × Message × PubKey)^N → π_batch

  Measured (Core Ultra 5, 18 threads, release build):

    N = 2:  |π| = 631 KB,  prove 22 s,  verify 35 ms
    N = 4:  |π| = 710 KB,  prove 44 s,  verify 35 ms
    N = 8:  |π| = 735 KB,  prove 31 s (parallel),  verify 35 ms

  Growth (measured range N = 2..8):
    Size:    sub-linear; asymptotes near ~750 KB
    Verify:  constant (35 ms, independent of N)
    Prove:   linear in N (dominated by signature verification cost)

  Extrapolation beyond N = 8 (not measured):
    The pattern suggests 1000 signatures would produce a batch
    proof in the 750-800 KB range, with the same 35 ms verify.
    This is an extrapolation, not a measurement — batches at
    this size have not been benchmarked on the release build.

The measured batch-proof verification time is approximately 35 ms for the tested configurations with N = 2..8 signatures. This result does not establish the same verification time for arbitrary batch sizes. Larger batches require separate benchmarking before making claims about their verification cost or throughput.

6. Chain Aggregation (O(1) Verification)

Chain aggregation links successive chain commitments and batch-proof hashes. The current Path B construction does not recursively verify the full contents of each underlying batch proof. Its measured verification cost remains constant with respect to the number of covered leaves in the tested configuration.

Chain commitment aggregation:

  C_1 = Hash(
          genesis_commitment,
          hash(batch_proof(block_1))
        )

  C_n = Hash(
          C_(n-1),
          hash(batch_proof(block_n))
        )

  The commitment structure links the previous commitment
  to the current block's batch-proof hash.

  Current Path B:
    Binds public values and commitments.
    Does not recursively verify the full batch-proof contents.

  Measured at 4444 leaves (16-core consumer CPU with AVX2):

    Aggregated result = ~200 KB
    T_verify          = 1.5 ms
    T_build           = 603 s

  O(1) applies to verification with respect to covered chain
  length under the tested configuration. Proof construction
  and aggregation are computationally expensive.

The ~200 KB result is an aggregated commitment structure, not a recursively verified proof of every underlying STARK. Verification takes approximately 1.5 ms at the measured 4444-leaf scale. This demonstrates compact verification without replaying all covered leaves; it does not establish that every child batch proof was recursively verified during aggregation.

7. Trust Set

A verifier who checks a proof trusts the following primitives. Nothing else.

Native signature verification relies on:

  - ML-DSA-65 signature security
  - Correct implementation of the signature verifier

STARK batch-proof verification relies on:

  - FRI commitment scheme
  - Poseidon2 collision resistance
  - Goldilocks field arithmetic
  - Fiat-Shamir security assumptions

SMT state-proof verification relies on:

  - The account_commitment being authenticated
  - Correct Poseidon2-based root reconstruction

Chain aggregation relies on:

  - The configured commitment and hash construction
  - Correct verification of the aggregated result
  - The documented Path B assumptions

Path B limitation:

  The chain aggregation does not recursively re-verify the
  full contents of every underlying batch proof.

  A chain commitment alone must not be interpreted as proof
  that every underlying signature-attestation statement was
  recursively verified.

8. Path A vs Path B

The current proof aggregation uses Path B soundness. This is a protocol-level choice, not a property of the STARK system. It is documented because it affects what claims are valid.

Path A (full adversarial soundness):

  Approach: Verify the entire Merkle path in-circuit.
  Effect:   A malicious prover cannot lie about inclusion.
  Cost:     ~19 minutes per Merkle path at 4444 scale.
  Status:   Non-viable. Documented as a dead-end.

Path B (public-value binding, current):

  Approach: Verify only the sumcheck + fold chain in-circuit.
            Merkle verified natively outside the proof, during
            child-proof generation. Commitment binding via
            witness-trace consistency.
  Effect:   Sound against honest-prover attacks. Forgery
            requires breaking Fiat-Shamir.
  Cost:     ~298 ms per composition.
  Status:   Testnet-grade. Implemented and running.

A'2 (delegated Merkle, under research):

  Approach: Split a compact MerkleVerifierAir off the main circuit.
            Batch-verify 8 Merkle paths per proof.
  Target:   ~5-10× constraint reduction → 2-4 min per Merkle path.
  Status:   Not started. 2-3 week research spike.

9. Complexity

OperationTimeSpaceNotes
Signature batch proveO(N)O(N)Dominated by sig verification
Signature batch verifyO(1) in NO(1)35 ms constant
Chain aggregation stepO(1)O(1)One recursive verifier
Chain proof verifyO(1) in nO(1)1.5 ms constant
SMT state proof proveO(depth)O(depth)Poseidon2 walk
SMT state proof verifyO(depth)O(depth)<1 ms at typical depth
Full chain build (4444 blocks)603 s~16 GB peak16-core with AVX2

10. Limitations

Limitation 10.1: Not a privacy system

  Standard STARKs are not zero-knowledge. Sahyadri's proofs
  are transparent — they reveal the execution trace.

  Transaction data (amounts, senders, recipients, public keys)
  remains public on-chain. Zero-knowledge variants exist and
  could be added at a later phase, but they are not part of
  the current design.

Limitation 10.2: Path B soundness tier

  Sound against honest-prover attacks. Full adversarial
  soundness (Path A) is non-viable at current scale. The
  trade-off is documented in Section 8 and in proof-aggregation.

Limitation 10.3: Batch proof is not tiny

  The batch proof is 631-735 KB. Groth16 batch proofs are
  ~200-500 B. This is roughly 3× larger. The trade-off buys
  transparency and post-quantum security — both impossible to
  achieve with pairing-based systems.

Limitation 10.4: Chain proof is not a signature

  The ~200 KB chain proof does not aggregate signatures. It
  attests to a chain of block proofs. The distinction is
  detailed in Section 4.

Limitation 10.5: Not for arbitrary computation

  Sahyadri proves the validity of blocks. It does not prove
  arbitrary external computation. A ZK smart-contract platform
  would require a different circuit design, which is not part
  of the current protocol.

Limitation 10.6: Proving time is significant

  Generating a batch proof takes 22-31 s on commodity hardware
  at N=2..8. This is acceptable for a background worker, but
  would block block production if run synchronously.

  Sahyadri mitigates via a dedicated proof worker thread
  running in parallel with mining. Hashrate preservation is
  measured at 89-99% depending on thread allocation.

Limitation 10.7: Reorg invalidates downstream proofs

  A reorg at depth d invalidates the chain proofs for all
  blocks at depths > d. The chain proof must be rebuilt from
  the reorg point forward. This is a consequence of the
  commitment chain — every proof commits to its parent.

  In practice, reorg depth is small (< 5 blocks typically),
  so the rebuild cost is bounded by the depth.

11. Where Proofs Are Used

Four distinct applications, each using a different combination of the four proof types.

Application 1: Block validation

  Consensus and deterministic state-transition checks validate
  blocks during block processing.

  Native ML-DSA-65 verification checks transaction signatures.

  After block acceptance, proof workers asynchronously generate
  signature batch STARK proofs.

  These proofs are not required to be carried by every block
  for block acceptance.

Application 2: Chain verification

  Blocks contain the protocol's chain commitment.

  Chain aggregation links successive commitments and batch-proof
  hashes. The measured aggregated result is approximately 200 KB
  at 4444 leaves and verifies in 1.5 ms.

  Current Path B does not recursively verify every underlying
  batch proof.

Application 3: Light-client state queries

  A light client verifies an account inclusion or exclusion
  proof against an authenticated account_commitment.

  Typical state proof size: ~2 KB.
  Measured verification: < 1 ms.

  This is separate from chain-commitment verification.

Application 4: Cross-chain verification

  A verifier may use an authenticated chain-aggregation result
  or an account-state proof, depending on the statement it needs
  to verify.

  These mechanisms have different guarantees. A state proof
  establishes account data against a committed root; a chain
  commitment links proof outputs but does not recursively
  establish the validity of every underlying batch proof.

12. Summary

Sahyadri's proof system combines native ML-DSA-65 signature verification, asynchronous signature-attestation STARK proofs, SMT account-state proofs, Poseidon2 hash verification, and chain-commitment aggregation. These are distinct components with different verification responsibilities.

Measured results include 631–735 KB signature batch proofs with approximately 35 ms verification for N = 2..8 signatures, typical ~2 KB state proofs with verification below 1 ms, and an approximately 200 KB chain-aggregation result verifying in 1.5 ms at 4444 leaves. Chain aggregation took 603 seconds at that scale on a 16-core CPU.

Sahyadri aggregates proof commitments, not ML-DSA signatures. The chain-aggregation result is a commitment structure, not a recursively verified proof of every underlying batch STARK. Its O(1) verification claim applies to the measured verification operation with respect to covered chain length, not to proof generation or aggregation.

The current implementation uses Path B. It binds public values and proof commitments but does not recursively verify the full validity of every child batch proof. The stronger Path A construction remains a separate research direction. This limitation is documented in Section 8 and in proof-aggregation.