zk-STARK

The foundational concept from which zk-STARKs derive. A ZKP is a cryptographic method where a prover can convince a verifier that a statement is true without revealing any information beyond the validity of the statement itself.

• Completeness: An honest prover can always convince an honest verifier.
• Soundness: A malicious prover cannot convince an honest verifier of a false statement.
• Zero-Knowledge: The verifier learns nothing about the secret witness.

zk-STARKs are a specific instantiation of a ZKP that adds scalability and transparency to these core properties.

The core building block that replaces the elliptic curve cryptography used in zk-SNARKs. A hash function is a one-way mathematical algorithm mapping arbitrary data to a fixed-size output.

zk-STARKs rely exclusively on collision-resistant hash functions like SHA-256 or Rescue-Prime. This design choice:

• Eliminates the need for a trusted setup ceremony.
• Provides post-quantum security, as hash functions are believed to be resistant to attacks by quantum computers.
• Simplifies cryptographic assumptions to the minimal, well-studied security of symmetric primitives.

The cryptographic technique that transforms the interactive zk-STARK protocol into a non-interactive one suitable for real-world deployment.

In an interactive proof, the verifier sends random challenges to the prover. The Fiat-Shamir heuristic replaces the live verifier with a cryptographic hash function applied to the protocol transcript. The prover computes the challenge by hashing its own prior messages, making the proof a single, self-contained object that anyone can verify non-interactively.

This is what makes zk-STARKs practical for blockchain and attestation use cases.

A fundamental data structure used extensively within the zk-STARK prover to commit to large computational traces efficiently.

A Merkle tree organizes data into leaf nodes, each hashed, with parent nodes formed by hashing their children, culminating in a single Merkle root. This root acts as a cryptographic commitment to the entire dataset.

In a STARK, the prover commits to the execution trace using a Merkle tree. During verification, the prover only needs to reveal Merkle authentication paths for a few randomly selected positions, enabling logarithmic proof sizes relative to the computation size.

The predecessor and sibling technology to zk-STARKs, offering a contrast in design trade-offs. zk-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.

Key differences from zk-STARKs:

• Trusted Setup: SNARKs require a multi-party computation ceremony to generate a common reference string. If compromised, false proofs can be forged.
• Cryptographic Assumptions: SNARKs rely on elliptic curve pairings, which are vulnerable to quantum computing attacks.
• Proof Size: SNARK proofs are typically smaller (hundreds of bytes) than STARK proofs (tens to hundreds of kilobytes).
• Prover Speed: STARK provers are generally faster for large computations.

A class of cryptographic signature algorithms designed to resist attacks from large-scale quantum computers, directly relevant to zk-STARK's security model.

Traditional signature schemes like ECDSA rely on the discrete logarithm problem, which Shor's algorithm can solve efficiently on a quantum computer. Post-quantum signatures are based on mathematical problems believed to be hard for both classical and quantum adversaries, such as:

• Lattice-based cryptography (e.g., CRYSTALS-Dilithium)
• Hash-based signatures (e.g., SPHINCS+)

Because zk-STARKs rely only on hash functions, their security is directly reducible to the post-quantum security of the underlying hash function, making them inherently quantum-resistant without modification.