How to prove false statements: Practical attacks on Fiat-Shamir

Original Article ↗ Hacker News Discussion ↗

Impact on Bitcoin, Ethereum, and Crypto Systems

  • Several commenters say the attack does not let you fake Bitcoin or base-layer Ethereum transactions; Schnorr signatures and basic consensus are not obviously threatened.
  • The concern is mainly for zero-knowledge (ZK) systems and rollups, especially some newer Ethereum L2s and bridges that use GKR-based proofs.
  • ZK-based protocols on top of blockchains are seen as experimental; this work reinforces that risk.
  • Some argue major blockchains are effectively massive bug bounties: a simple catastrophic break would likely already have been exploited, but targeted protocol-level flaws (e.g., in bridges) remain realistic.

Fiat–Shamir, Zero-Knowledge, and the Random Oracle Model

  • Multiple explanations: interactive zero-knowledge proofs rely on random challenges; Fiat–Shamir replaces interaction with hashes interpreted as “random oracles.”
  • Historically, known breaks of Fiat–Shamir were contrived toy protocols; this paper is notable because it targets a real protocol (GKR).
  • The attack shows one can construct a statement/program so that, with Fiat–Shamir, a verifier accepts false statements, even though the interactive version is sound.

Debate: Are Hashes “Randomness”?

  • One camp insists hashes should only be integrity labels; treating them as randomness is a misuse and this paper is a predictable failure mode.
  • Others counter that cryptographic hashes are explicitly designed to behave like pseudorandom functions and underpin CSPRNGs, signatures, key derivation, etc.
  • Long subthread clarifies:
    • Hashes are deterministic and don’t create entropy, but can scramble existing entropy into outputs that are indistinguishable from random for many purposes.
    • Modern CSPRNGs and signature schemes routinely rely on this property; rejecting hashes as randomness implies rejecting much of modern crypto.

Understanding the Attack’s Core Idea

  • The malicious “program” is functionally identical on all normal inputs but is crafted to exploit how Fiat–Shamir hashes the statement/program to derive challenges.
  • By embedding knowledge of the hash-function behavior for the protocol’s specific inputs, the prover can fabricate accepting proofs for claims that are actually false.
  • Commenters stress: the novelty is not just “if you use a malicious program, you’re in trouble,” but that a relatively simple, efficient construction breaks a widely trusted heuristic.

Reception of the Quanta Article and Communication Issues

  • Several readers found the original paper clearer than the Quanta piece, criticizing the article as sensational (“prove lies”) and light on technical detail.
  • Some defend Quanta as a generally good pop-science outlet that sometimes overhypes to reach lay readers.
  • The homework-grading analogy is seen as imperfect but useful; it spawns a side discussion on probability vs certainty in proofs and in education.

Truth, Lies, and Philosophy Side-Thread

  • Extended digression on what constitutes a “lie” and different theories of truth (correspondence, coherence, consensus, pragmatic).
  • Others note this is largely orthogonal: in cryptography, “false statement” has a precise, mathematical meaning, and that’s what the paper addresses.