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 type | Statement proven | Constraints | Size | Verify |
|---|---|---|---|---|
| Dilithium batch | N ML-DSA-65 signatures valid | ~30,000/sig | 631-735 KB (N=2..8) | 35 ms |
| SMT state proof | key → value at committed root | ~5,000/path | ~2 KB typical | <1 ms |
| Poseidon2 hash proof | hash(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
| Operation | Time | Space | Notes |
|---|---|---|---|
| Signature batch prove | O(N) | O(N) | Dominated by sig verification |
| Signature batch verify | O(1) in N | O(1) | 35 ms constant |
| Chain aggregation step | O(1) | O(1) | One recursive verifier |
| Chain proof verify | O(1) in n | O(1) | 1.5 ms constant |
| SMT state proof prove | O(depth) | O(depth) | Poseidon2 walk |
| SMT state proof verify | O(depth) | O(depth) | <1 ms at typical depth |
| Full chain build (4444 blocks) | 603 s | ~16 GB peak | 16-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.