<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Ümit Aygül on Medium]]></title>
        <description><![CDATA[Stories by Ümit Aygül on Medium]]></description>
        <link>https://medium.com/@umitaygul?source=rss-6b1a45a6da2e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*j5M8MTUH9w_dI0bS</url>
            <title>Stories by Ümit Aygül on Medium</title>
            <link>https://medium.com/@umitaygul?source=rss-6b1a45a6da2e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 17:38:05 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@umitaygul/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[The Grand Comparison: Every ZKP System, Every Dimension — Article 8 of the ZKP Systems Series]]></title>
            <link>https://medium.com/@umitaygul/the-grand-comparison-every-zkp-system-every-dimension-article-8-of-the-zkp-systems-series-9b10dae918df?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/9b10dae918df</guid>
            <category><![CDATA[post-quantum-cryptography]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[web3]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Fri, 17 Apr 2026 08:02:20 GMT</pubDate>
            <atom:updated>2026-04-17T08:02:20.073Z</atom:updated>
            <content:encoded><![CDATA[<p>You’ve made it to the end of the series. Eight articles, 28 proof systems, four decades of cryptographic history compressed into a reading arc that took you from “what is a zero-knowledge proof” to “which systems survive a quantum computer.”</p><p>This final article is a reference document. It answers the question every engineer eventually asks: <em>given my constraints, which system should I use?</em></p><p>We’ll cover the full comparison table first, then a decision framework, then the systems worth watching in 2025 and beyond.</p><h3>The Complete Comparison Table</h3><p>Every system in this series, across every dimension that matters for a practical decision.</p><p><strong>Columns explained:</strong></p><ul><li><strong>Proof size</strong> — the size of the proof sent from prover to verifier</li><li><strong>Prover time</strong> — relative to Groth16 baseline (1.0x)</li><li><strong>Verifier time</strong> — how fast verification runs</li><li><strong>Trusted setup</strong> — None / Universal / Circuit-specific</li><li><strong>Transparent</strong> — no trusted setup of any kind</li><li><strong>Universal</strong> — one setup for any circuit</li><li><strong>PQ safe</strong> — post-quantum secure</li><li><strong>Paradigm</strong> — how you write programs for this system</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8dY6o8V3ntlI7YAZCQSvAw.png" /></figure><h3>The Decision Framework</h3><p>Rather than telling you which system to use, here is the decision tree every serious engineer should walk through.</p><h3>Step 1: Do you need post-quantum security?</h3><pre>Is your application&#39;s security horizon &gt; 10 years?<br>├── YES → eliminate all ECDLP-based systems<br>│         Remaining: Ligero, Aurora, Virgo, STARK, Zilch,<br>│                    Plonky2, Plonky3, SP1, Hyperbridge<br>└── NO  → all systems are available for current deployment<br>          (but plan a migration path)</pre><h3>Step 2: Can you tolerate a trusted setup?</h3><pre>Can you run or participate in a trusted setup ceremony?<br>├── YES → Groth16 and PLONK become available<br>│         (smallest proofs, fastest verification)<br>└── NO  → eliminate circuit-specific and universal-setup systems<br>          Remaining: transparent systems only</pre><h3>Step 3: What is your proof size budget?</h3><pre>Is the proof verified on-chain (L1 Ethereum)?<br>├── YES → proof size is critical (calldata costs)<br>│         Best: Groth16 (~200 B) if setup acceptable<br>│               PLONK (~800 B) if universal setup needed<br>│               Plonky3 recursion (~50 KB, but aggregated)<br>└── NO  → proof size is less critical<br>          STARK, Plonky2, SP1 all acceptable</pre><h3>Step 4: What is your programming model preference?</h3><pre># Decision map by developer profile<br>decision_map = {<br>    &quot;I want to write normal Rust&quot;: {<br>        &quot;system&quot;: &quot;SP1 or Risc0&quot;,<br>        &quot;note&quot;: &quot;No circuits needed - just write your program&quot;<br>    },<br>    &quot;I need max performance, willing to write circuits&quot;: {<br>        &quot;system&quot;: &quot;Plonky3 or Halo2&quot;,<br>        &quot;note&quot;: &quot;Custom gates, full control over constraint system&quot;<br>    },<br>    &quot;I&#39;m building on Ethereum, need on-chain verification&quot;: {<br>        &quot;system&quot;: &quot;Groth16 or PLONK (via snarkjs/circom)&quot;,<br>        &quot;note&quot;: &quot;Mature tooling, Solidity verifiers available&quot;<br>    },<br>    &quot;I need recursive proofs + no trusted setup&quot;: {<br>        &quot;system&quot;: &quot;Halo2 or Plonky2&quot;,<br>        &quot;note&quot;: &quot;Halo2 if not PQ concerned; Plonky2 if PQ matters&quot;<br>    },<br>    &quot;I&#39;m building a privacy coin or confidential transactions&quot;: {<br>        &quot;system&quot;: &quot;Bulletproofs (range proofs) or STARK&quot;,<br>        &quot;note&quot;: &quot;Bulletproofs for compact range proofs; STARK for PQ&quot;<br>    },<br>    &quot;I need the absolute smallest proof&quot;: {<br>        &quot;system&quot;: &quot;Groth16&quot;,<br>        &quot;note&quot;: &quot;200 bytes, unbeaten after 8 years - accept the ceremony&quot;<br>    }<br>}<br>for use_case, recommendation in decision_map.items():<br>    print(f&quot;Use case: {use_case}&quot;)<br>    print(f&quot;  → {recommendation[&#39;system&#39;]}&quot;)<br>    print(f&quot;  Note: {recommendation[&#39;note&#39;]}&quot;)<br>    print()</pre><h3>Step 5: Which ecosystem fits your stack?</h3><pre>Language / tooling preference:<br>├── Rust      → SP1, Risc0, Halo2 (halo2_proofs crate)<br>├── TypeScript/JS → snarkjs + circom (Groth16, PLONK)<br>├── Python    → py_ecc, arkworks bindings (research/prototyping)<br>├── Cairo     → zk-STARK (StarkNet ecosystem)<br>└── Leo       → Marlin / Aleo ecosystem</pre><h3>The Three Tiers for Production Today</h3><p>Based on maturity, tooling, and deployment track record, production systems fall into three tiers:</p><h3>Tier 1 — Battle-tested in production</h3><p><strong>Groth16</strong> — Zcash Sapling (2018–present), Tornado Cash, Polygon Hermez. Millions of proofs generated. Solidity verifiers audited multiple times. Use for: Ethereum applications where proof size is critical and you can run a ceremony.</p><p><strong>zk-STARK</strong> — StarkNet, StarkEx (dYdX, Sorare, Immutable X). Billions of dollars of transaction volume proved. Production Cairo tooling mature. Use for: large-scale L2 rollups, applications requiring PQ safety.</p><p><strong>Halo2</strong> — Zcash Orchard, Scroll, Taiko. Production zkEVMs running on mainnet. Use for: EVM-equivalent applications, recursive proof systems, no trusted setup required.</p><p><strong>PLONK</strong> — Aztec Network, multiple zkEVM variants. Universal setup eliminates per-circuit ceremony. Use for: applications with frequently changing circuits.</p><h3>Tier 2 — Production-ready, growing adoption</h3><p><strong>Plonky2</strong> — Powers several zkRollup aggregation layers. 100x faster recursion than prior systems. Use for: recursive proof aggregation, post-quantum requirements.</p><p><strong>Plonky3</strong> — SP1, Polygon AggLayer, Valida. Fastest prover available (2024). Use for: new projects where raw speed is the priority.</p><p><strong>SP1</strong> — Ethereum light client proofs in production (Succinct’s bridge). Use for: proving arbitrary Rust programs, applications where circuit writing is impractical.</p><p><strong>Bulletproofs</strong> — Monero, Grin. Range proofs only — not general-purpose. Use for: confidential transaction amounts in privacy coins.</p><h3>Tier 3 — Research / niche</h3><p><strong>Nova</strong> — Nexus zkVM, research projects. Excellent for IVC but not yet production-proven. Use for: incremental computations, research.</p><p><strong>Marlin</strong> — Aleo. Strong R1CS-native system but limited to that ecosystem.</p><p><strong>Ligero, Aurora, Virgo</strong> — Important historically and for PQ research, but limited production tooling. Use for: academic research, understanding PQ foundations.</p><h3>Proof Size vs Prover Speed: The Core Trade-off Visualized</h3><pre>Proof size (log scale, smaller = better)<br>    │<br>200B┤ ● Groth16                              ← smallest<br>    │<br>800B┤      ● PLONK<br>    │<br> 1KB┤          ● Marlin  ● Bulletproofs<br>    │<br>10KB┤               ● Halo2  ● Halo  ● Nova<br>    │<br>100KB┤                      ● Plonky2  ● Plonky3  ● Virgo  ● Aurora<br>    │<br>300KB┤                                  ● zk-STARK  ● Zilch<br>    │<br> 1MB┤                                                  ● SP1<br>    │<br>    └──────────────────────────────────────────────────────────<br>    faster prover ←──────────────────────────────→ slower prover<br>       0.2x          1x          5x          10x         20x<br>       (Plonky3)  (Groth16) (Bulletproofs) (Aurora)  (Sonic)<br><br>PQ-safe systems: Ligero, Aurora, Virgo, STARK, Zilch, Plonky2, Plonky3, SP1, Hyperbridge</pre><p>The top-left corner — tiny proof, fast prover — is where Groth16 lives alone. The post-quantum systems cluster in the bottom-right. The engineering progress from 2019 to 2024 is visible as PQ-safe systems move toward the top-left: Plonky3 is now in the same prover speed tier as Groth16 while maintaining PQ safety, at the cost of larger proofs.</p><h3>Benchmarks: The Same Circuit Across Systems</h3><p>To make the comparison concrete, here are approximate benchmarks for proving a <strong>Poseidon hash computation</strong> (a common ZK-friendly hash, ~1000 gates) across systems:</p><pre># Approximate benchmarks — 1000-gate Poseidon hash circuit<br># Hardware: modern server (32-core, 64GB RAM)<br># These are order-of-magnitude estimates, not precise measurements<br>benchmarks = {<br>    &quot;Groth16&quot;: {<br>        &quot;proof_size_bytes&quot;: 192,<br>        &quot;prover_ms&quot;: 50,<br>        &quot;verifier_ms&quot;: 2,<br>        &quot;trusted_setup&quot;: &quot;circuit-specific&quot;,<br>        &quot;pq_safe&quot;: False<br>    },<br>    &quot;PLONK (snarkjs)&quot;: {<br>        &quot;proof_size_bytes&quot;: 800,<br>        &quot;prover_ms&quot;: 100,<br>        &quot;verifier_ms&quot;: 5,<br>        &quot;trusted_setup&quot;: &quot;universal&quot;,<br>        &quot;pq_safe&quot;: False<br>    },<br>    &quot;Halo2&quot;: {<br>        &quot;proof_size_bytes&quot;: 5000,<br>        &quot;prover_ms&quot;: 150,<br>        &quot;verifier_ms&quot;: 10,<br>        &quot;trusted_setup&quot;: &quot;none&quot;,<br>        &quot;pq_safe&quot;: False<br>    },<br>    &quot;zk-STARK&quot;: {<br>        &quot;proof_size_bytes&quot;: 150_000,<br>        &quot;prover_ms&quot;: 250,<br>        &quot;verifier_ms&quot;: 30,<br>        &quot;trusted_setup&quot;: &quot;none&quot;,<br>        &quot;pq_safe&quot;: True<br>    },<br>    &quot;Plonky2&quot;: {<br>        &quot;proof_size_bytes&quot;: 80_000,<br>        &quot;prover_ms&quot;: 100,<br>        &quot;verifier_ms&quot;: 20,<br>        &quot;trusted_setup&quot;: &quot;none&quot;,<br>        &quot;pq_safe&quot;: True<br>    },<br>    &quot;Plonky3&quot;: {<br>        &quot;proof_size_bytes&quot;: 50_000,<br>        &quot;prover_ms&quot;: 10,   # Goldilocks/M31 field speed<br>        &quot;verifier_ms&quot;: 15,<br>        &quot;trusted_setup&quot;: &quot;none&quot;,<br>        &quot;pq_safe&quot;: True<br>    },<br>}<br>print(f&quot;{&#39;System&#39;:&lt;20} {&#39;Proof&#39;:&gt;10} {&#39;Prover&#39;:&gt;10} {&#39;Verifier&#39;:&gt;10} {&#39;Setup&#39;:&lt;20} {&#39;PQ&#39;}&quot;)<br>print(&quot;-&quot; * 80)<br>for name, b in benchmarks.items():<br>    pq = &quot;✓&quot; if b[&quot;pq_safe&quot;] else &quot;✗&quot;<br>    proof = f&quot;{b[&#39;proof_size_bytes&#39;]:,} B&quot;<br>    prover = f&quot;{b[&#39;prover_ms&#39;]} ms&quot;<br>    verifier = f&quot;{b[&#39;verifier_ms&#39;]} ms&quot;<br>    print(f&quot;{name:&lt;20} {proof:&gt;10} {prover:&gt;10} {verifier:&gt;10} {b[&#39;trusted_setup&#39;]:&lt;20} {pq}&quot;)</pre><p>The key takeaway: <strong>Plonky3 has effectively matched Groth16’s prover speed</strong> while being post-quantum safe and requiring no trusted setup. The remaining gap is proof size — 50 KB vs 192 bytes. Recursive aggregation closes most of this gap at scale.</p><h3>What’s Coming Next</h3><p>The ZKP field moves faster than almost any area of applied cryptography. Here are the directions most likely to produce significant new systems in 2025–2027:</p><p><strong>Lattice-based SNARKs</strong> — NIST standardized lattice-based signatures and key encapsulation in 2024. Lattice-based proof systems offer post-quantum security with potentially smaller proofs than FRI-based systems. Early constructions exist (Banquet, Ligero++), but none are production-ready.</p><p><strong>FRI + PLONK hybrids</strong> — Plonky2 showed this works. The next generation will optimize FRI parameters specifically for PLONK custom gates, potentially closing the gap with KZG-based proof sizes.</p><p><strong>zkML (ZK Machine Learning)</strong> — Proving that a neural network inference was computed correctly, without revealing the model weights. EZKL and similar projects are making this practical with Halo2 and PLONK backends. As models get larger, the demand for efficient ML proof systems will drive new constructions.</p><p><strong>On-chain STARK verification cost reduction</strong> — Current STARKs are expensive to verify on L1 Ethereum. EIP proposals for STARK-specific precompiles would reduce verification cost 10–100x. If adopted, this would make STARK proofs economical for a much wider class of applications.</p><p><strong>Post-quantum Halo2</strong> — Multiple teams are working on replacing Halo2’s IPA with a hash-based commitment scheme. Success would give the largest existing deployment base (Zcash, Scroll, Taiko) a migration path to post-quantum safety without rewriting circuits.</p><h3>How to Use This Series</h3><p>If you’re a <strong>developer</strong> building a ZK application: read Articles 0, 2, 3, and 6. Understand Groth16 (still the most common), PLONK (the most flexible), and SP1 (the easiest). Use the decision framework in this article.</p><p>If you’re a <strong>researcher</strong> entering the ZK space: read the full series in order. The progression from Pinocchio to Nova to Plonky3 is the most efficient path through the field’s history.</p><p>If you’re an <strong>engineer evaluating ZK for your product</strong>: read Article 0 (taxonomy), Article 7 (quantum), and this article. That’s all you need to make an informed system selection decision.</p><p>If you’re a <strong>cryptographer</strong> reviewing someone else’s work: Articles 2–5 give you the vocabulary to reason about any proof system’s security assumptions and trade-offs.</p><h3>The Series in One Sentence Per Article</h3><p><strong>Article 0</strong> — ZKP is a family of 28+ systems, not one thing; they differ on setup, universality, and quantum resistance.</p><p><strong>Article 1</strong> — Pinocchio (2013) made SNARKs practical by encoding computation as R1CS and verifying via QAP over elliptic curve pairings.</p><p><strong>Article 2</strong> — Groth16 (2016) compressed the proof to its theoretical minimum — 3 group elements — by baking the circuit into the setup.</p><p><strong>Article 3</strong> — Sonic, PLONK, and Marlin (2019) independently solved circuit-specific setup; PLONK won through extensibility, not performance.</p><p><strong>Article 4</strong> — Bulletproofs, Halo, and Halo2 eliminated trusted setup entirely; the cost is larger proofs and, critically, they remain vulnerable to quantum attacks.</p><p><strong>Article 5</strong> — Ligero, Aurora, Virgo, and zk-STARK replaced elliptic curves with hash functions, achieving post-quantum security at the cost of much larger proofs.</p><p><strong>Article 6</strong> — Nova’s folding schemes reduced recursion overhead from 100x to 15%; Plonky2 made recursive proofs 100x faster; SP1 made ZK proofs accessible to anyone who can write Rust.</p><p><strong>Article 7</strong> — Shor’s algorithm breaks all ECDLP-based systems; hash-based systems survive with parameter adjustments; no trusted setup ≠ post-quantum safe.</p><p><strong>Article 8 (this one)</strong> — When choosing a system: decide on PQ requirements first, then setup tolerance, then proof size budget, then programming model.</p><h3>Final Thought</h3><p>Zero-knowledge proofs are one of the most intellectually beautiful areas of computer science. The ability to convince someone of a truth without revealing why it is true sits at the intersection of philosophy, mathematics, and engineering in a way few technologies do.</p><p>But they are also increasingly practical. In 2013, Pinocchio proved you could verify a computation in 6 milliseconds. In 2024, SP1 proves arbitrary Rust programs, Plonky3 generates proofs faster than Groth16, and StarkNet processes millions of transactions per day with post-quantum security.</p><p>The gap between “theoretically possible” and “runs in production at scale” closed in eleven years. The gap between “current production systems” and “post-quantum safe production systems” is closing now.</p><p>If you’ve read this series from the beginning, you are now equipped to read any new proof system paper and understand where it sits in this landscape — what problem it solves, what trade-offs it accepts, and whether it will survive the quantum transition.</p><p>That’s the vocabulary the field requires. Use it well.</p><p><strong>End of Series</strong></p><p><em>Thank you for reading. If you found this series useful, the best way to support continued writing is to share it with someone who is trying to understand ZKP systems. The field needs more people who can reason clearly about these trade-offs.</em></p><p><strong>Full Series Index</strong></p><ul><li>Article 0: A Field Guide Before You Get Lost</li><li>Article 1: Pinocchio and the Procedural Era (2013–2018)</li><li>Article 2: Groth16 — Why Three Group Elements Is All You Need</li><li>Article 3: The Universal Setup Race — Sonic, PLONK, and Marlin</li><li>Article 4: No Trusted Setup — Bulletproofs, Halo, and Halo2</li><li>Article 5: Hash Functions All the Way Down — The Post-Quantum Systems</li><li>Article 6: Folding Schemes and the zkVM Era</li><li>Article 7: The Quantum Threat — Which Systems Survive</li><li>Article 8: The Grand Comparison (this article)</li></ul><p><strong>References</strong></p><ul><li>All papers cited in Articles 0–7</li><li>Thaler, J. — “Proofs, Arguments, and Zero-Knowledge” (textbook, 2022) — the definitive technical reference</li><li>ZKProof Community — <a href="https://zkproof.org/">https://zkproof.org</a> — standardization efforts</li><li>awesome-zero-knowledge-proofs — github.com/matter-labs/awesome-zero-knowledge-proofs</li><li>ZK Hack — zkhack.dev — hands-on learning resources</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9b10dae918df" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Quantum Threat: Which Proof Systems Survive and Which Don’t — Article 7 of the ZKP Systems…]]></title>
            <link>https://medium.com/@umitaygul/the-quantum-threat-which-proof-systems-survive-and-which-dont-article-7-of-the-zkp-systems-5d4f9ae4c4b8?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/5d4f9ae4c4b8</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[post-quantum-cryptography]]></category>
            <category><![CDATA[web3]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Fri, 17 Apr 2026 07:25:29 GMT</pubDate>
            <atom:updated>2026-04-17T07:25:29.161Z</atom:updated>
            <content:encoded><![CDATA[<h3>The Quantum Threat: Which Proof Systems Survive and Which Don’t — Article 7 of the ZKP Systems Series</h3><p>Every cryptographer working on zero-knowledge proofs carries the same quiet concern: somewhere in the next decade or two, a quantum computer will arrive that can break the mathematical problems our systems depend on. The question is not whether, but when — and whether the systems we build today will survive the transition.</p><p>This article is the most direct answer this series can give to that question.</p><p>We will go system by system, assumption by assumption, and be precise about what breaks, what survives, and what the migration path looks like. By the end, you will be able to look at any proof system — including ones published after this series — and immediately classify its quantum posture.</p><h3>The Two Quantum Algorithms That Matter</h3><p>Before evaluating systems, you need to know exactly which quantum algorithms are relevant. There are two.</p><h3>Shor’s Algorithm (1994)</h3><p>Shor’s algorithm efficiently solves the <strong>discrete logarithm problem</strong> and the <strong>integer factorization problem</strong> in polynomial time. On a sufficiently powerful quantum computer:</p><pre>def shors_attack_complexity(n_bits):<br>    &quot;&quot;&quot;<br>    Classical discrete log attack: O(2^(n/2)) — exponential<br>    Shor&#39;s algorithm:             O(n^3)      — polynomialFor 256-bit elliptic curve discrete log:<br>    Classical: 2^128 operations ≈ 10^38 - infeasible<br>    Shor&#39;s:    256^3 ≈ 16 million operations - trivial<br>    &quot;&quot;&quot;<br>    classical = 2 ** (n_bits // 2)<br>    quantum = n_bits ** 3<br>    print(f&quot;Field size: {n_bits} bits&quot;)<br>    print(f&quot;Classical attack: ~2^{n_bits//2} = {classical:.2e} operations&quot;)<br>    print(f&quot;Shor&#39;s attack:    ~{n_bits}^3   = {quantum:,} operations&quot;)<br>    print(f&quot;Quantum advantage: {classical/quantum:.2e}x speedup&quot;)<br>    print()<br>shors_attack_complexity(256)<br># Field size: 256 bits<br># Classical attack: ~2^128 = 3.40e+38 operations<br># Shor&#39;s attack:    ~256^3 = 16,777,216 operations<br># Quantum advantage: 2.03e+31x speedup<br></pre><p><strong>What Shor’s breaks:</strong></p><ul><li>Elliptic curve discrete logarithm (ECDLP) — the basis of KZG, IPA, Pedersen commitments</li><li>RSA / integer factorization</li><li>Diffie-Hellman key exchange</li><li>All pairing-based cryptography (Groth16, PLONK, Marlin verification equations)</li></ul><p><strong>What Shor’s does NOT break:</strong></p><ul><li>Hash functions (SHA-256, Keccak, Poseidon, Blake3)</li><li>Symmetric encryption (AES)</li><li>Lattice-based cryptography</li></ul><h3>Grover’s Algorithm (1996)</h3><p>Grover’s algorithm provides a <strong>quadratic speedup</strong> for unstructured search. Against an n-bit hash function:</p><pre>def grovers_impact(n_bits):<br>    &quot;&quot;&quot;<br>    Classical preimage attack: O(2^n)<br>    Grover&#39;s algorithm:        O(2^(n/2))Mitigation: double output size<br>    SHA-256: quantum cost = 2^128 - still completely infeasible<br>    SHA-512: quantum cost = 2^256 - astronomically infeasible<br>    &quot;&quot;&quot;<br>    classical = 2 ** n_bits<br>    quantum = 2 ** (n_bits // 2)<br>    speedup = classical // quantum<br>    print(f&quot;Hash output: {n_bits} bits&quot;)<br>    print(f&quot;Classical preimage: 2^{n_bits}&quot;)<br>    print(f&quot;Grover&#39;s attack:    2^{n_bits//2}&quot;)<br>    print(f&quot;Speedup factor:     2^{n_bits//2} = {quantum:.2e}x&quot;)<br>    print(f&quot;Still secure at 256-bit output: {&#39;Yes&#39; if n_bits//2 &gt;= 128 else &#39;No&#39;}&quot;)<br>    print()<br>grovers_impact(256)<br># Hash output: 256 bits<br># Classical preimage: 2^256<br># Grover&#39;s attack:    2^128<br># Speedup factor:     2^128 = 3.40e+38x<br># Still secure at 256-bit output: Yes<br># The key insight: Grover halves the security level<br># SHA-256 with 256-bit output → 128-bit quantum security<br># This is still infeasible - no known quantum computer<br># can perform 2^128 operations in any reasonable timeframe<br></pre><p><strong>What Grover’s weakens but doesn’t break:</strong></p><ul><li>Hash functions (security halved — manageable by doubling output size)</li><li>Symmetric encryption (AES-256 remains secure; AES-128 is borderline)</li></ul><p><strong>The critical difference:</strong> Shor’s provides an <em>exponential</em> speedup — it makes problems that are computationally infeasible become trivially easy. Grover’s provides only a <em>quadratic</em> speedup — security is weakened but remains computationally hard with appropriate parameter choices.</p><p>This asymmetry is why hash-based systems are post-quantum safe and elliptic curve systems are not.</p><h3>System-by-System Quantum Assessment</h3><h3>Groth16 — BROKEN</h3><p><strong>Quantum vulnerability:</strong> Critical <strong>Timeline to breakage:</strong> ~10–20 years (when large-scale quantum computers exist)</p><p>Groth16’s verification equation is:</p><pre>e(π_A, π_B) = e(α, β) · e(vk_input, γ) · e(π_C, δ)</pre><p>Every term here is an elliptic curve pairing. Breaking ECDLP on the BN254 or BLS12–381 curves allows an attacker to:</p><ol><li>Compute the toxic waste τ from the public parameters</li><li>Forge arbitrary proofs that pass verification for <em>any</em> statement</li></ol><p>There is no parameter upgrade. There is no migration path within the Groth16 framework. A quantum attacker who can break ECDLP can retroactively forge proofs for any past Groth16-verified system — including every Zcash Sapling transaction ever made.</p><p><strong>Systems affected:</strong> Zcash Sapling, Tornado Cash, Polygon Hermez (original), any application using snarkjs groth16.</p><p><strong>Migration path:</strong> Replace with STARK-based or Plonky2/Plonky3-based systems. Zcash has already begun this transition with Orchard (Halo2) and is evaluating further post-quantum options.</p><h3>PLONK — BROKEN</h3><p><strong>Quantum vulnerability:</strong> Critical</p><p>PLONK uses KZG polynomial commitments. The security of KZG reduces to ECDLP:</p><pre># KZG commitment: C = f(τ) · G<br># where G is the curve generator, τ is the toxic waste<br># A quantum attacker with Shor&#39;s algorithm can:<br># 1. Compute τ from the public SRS: [G, τG, τ²G, ..., τⁿG]<br>#    → solve discrete log: τ = dlog(τG, G)  [trivial with Shor&#39;s]<br># 2. Construct a fake polynomial f&#39;(x) ≠ f(x) such that<br>#    f&#39;(τ) = f(τ)  [now possible since τ is known]<br># 3. Submit f&#39; with the original commitment C - verification passes<br># Result: the verifier accepts a false statement<br># The &quot;binding&quot; property of KZG is completely broken</pre><p>This affects every PLONK variant: UltraPLONK, TurboPLONK, HyperPLONK, and every zkEVM built on PLONK (Scroll, Taiko’s PLONK mode, Aztec).</p><p><strong>Migration path:</strong> Replace KZG with FRI. This is exactly what Plonky2 and Plonky3 do — PLONK arithmetization with FRI commitment scheme. The constraint system survives; only the commitment scheme needs replacing.</p><h3>Marlin — BROKEN</h3><p><strong>Quantum vulnerability:</strong> Critical</p><p>Marlin also uses KZG. Same vulnerability as PLONK. Aleo’s production system (Marlin+) would need to migrate to a hash-based commitment scheme.</p><h3>Sonic — BROKEN</h3><p><strong>Quantum vulnerability:</strong> Critical</p><p>Sonic uses KZG. Mostly a research system now, but the same analysis applies.</p><h3>Bulletproofs — BROKEN</h3><p><strong>Quantum vulnerability:</strong> Critical</p><p>Bulletproofs does <em>not</em> use pairings or KZG — it uses Pedersen commitments and inner product arguments based on the <strong>discrete log assumption</strong> in elliptic curve groups. This is still ECDLP.</p><pre># Pedersen commitment: C = v·G + r·H<br># Hiding: given C, you can&#39;t find v (discrete log hardness)<br># Binding: you can&#39;t find v&#39; ≠ v with the same C (discrete log hardness)<br># Shor&#39;s algorithm breaks discrete log in elliptic curve groups<br># → Pedersen commitments become non-binding under quantum attack<br># → Bulletproofs range proofs become forgeable<br># A quantum attacker can find v from C = v·G + r·H<br># because Shor&#39;s solves: given P = k·G, find k</pre><p>This is important: Bulletproofs eliminated trusted setup, but it did NOT eliminate ECDLP. No trusted setup ≠ post-quantum safe. Monero’s confidential transactions would be fully exposed under a quantum attack.</p><p><strong>Migration path:</strong> Replace with hash-based range proofs. Several lattice-based and hash-based range proof constructions exist in the research literature but none are yet as compact as Bulletproofs.</p><h3>Halo and Halo2 — BROKEN</h3><p><strong>Quantum vulnerability:</strong> Critical</p><p>A common misconception: because Halo2 uses IPA (Inner Product Argument) instead of KZG, people assume it avoids the quantum problem. It does not.</p><p>IPA security reduces to the <strong>discrete log problem</strong> in elliptic curve groups — specifically the Pasta curves (Pallas and Vesta). Shor’s algorithm breaks discrete log on Pallas and Vesta exactly as efficiently as on BN254 or BLS12–381.</p><pre># IPA commitment: uses Pedersen multi-commitment<br># [f] = f_0·G_0 + f_1·G_1 + ... + f_n·G_n<br># Security: computing f_i from [f] requires solving discrete log<br># Shor&#39;s breaks this:<br># Given [f] and G_0..G_n, compute f_0..f_n via quantum discrete log<br># → the commitment is no longer binding<br># → Halo2 proofs become forgeable<br># This affects: Zcash Orchard, Scroll, Taiko (Halo2 mode), PSE projects</pre><p>Halo2 is <em>transparent</em> (no trusted setup) and <em>recursive</em> — important properties — but it is not post-quantum safe. These are orthogonal axes.</p><p><strong>Migration path:</strong> Replace IPA with a hash-based commitment scheme. This is a significant engineering effort. Zcash is actively researching post-quantum alternatives for Orchard.</p><h3>Ligero — SAFE ✓</h3><p><strong>Quantum vulnerability:</strong> Grover only (manageable)</p><p>Ligero’s security reduces entirely to the collision resistance of the hash function used for its commitments. Under quantum attack:</p><ul><li>Grover halves collision-finding complexity: SHA-256 (256-bit) → 128-bit quantum security</li><li>128 bits of quantum security is currently considered sufficient</li><li>No Shor-vulnerable component anywhere in the construction</li></ul><pre># Ligero commitment: Merkle tree of evaluations<br># commit(f) = MerkleRoot(SHA256(f(x_0)), SHA256(f(x_1)), ..., SHA256(f(x_n)))<br># Quantum attack on SHA-256:<br># Classical collision: O(2^128)<br># Grover&#39;s collision:  O(2^64) per pair - NOT enough to break commitments<br># (Breaking binding requires finding f&#39; ≠ f with same root - harder than collision)<br># Verdict: Ligero with SHA-256 provides ~128-bit post-quantum security<br># Upgrade to SHA-512 → ~256-bit post-quantum security</pre><p><strong>Caveat:</strong> The security proof uses the random oracle model — SHA-256 is modeled as a truly random function. Known attacks on SHA-256’s structure don’t apply to ZK usage, but this is an assumption, not a proof.</p><h3>Aurora — SAFE ✓</h3><p><strong>Quantum vulnerability:</strong> Grover only (manageable)</p><p>Aurora builds on Ligero’s hash-based foundation with Reed-Solomon codes and the IOP framework. Its security reduces to hash function collision resistance — no ECDLP anywhere.</p><p>The Reed-Solomon component is information-theoretic (not computational) — it’s secure even against computationally unbounded adversaries, quantum or classical.</p><h3>Virgo — SAFE ✓</h3><p><strong>Quantum vulnerability:</strong> Grover only (manageable)</p><p>Virgo uses hash-based polynomial commitments over its GKR-based sumcheck protocol. Same analysis as Aurora — security reduces to hash collision resistance.</p><h3>zk-STARK — SAFE ✓</h3><p><strong>Quantum vulnerability:</strong> Grover only (manageable)</p><p>STARKs are built entirely on FRI, which uses Merkle trees (SHA-256 or Keccak commitments) and Reed-Solomon codes. No elliptic curves. No pairings. No discrete log.</p><pre># STARK security assumptions:<br># 1. FRI soundness: Reed-Solomon proximity — information-theoretic<br># 2. Fiat-Shamir binding: hash function collision resistance<br># 3. Merkle tree binding: hash function collision resistance<br># Under quantum attack:<br># - Reed-Solomon: unaffected (information-theoretic)<br># - Hash collision resistance: 2^128 → 2^64 per Grover step<br>#   BUT: soundness errors multiply across FRI layers<br>#   Practical quantum attack requires &gt;&gt; 2^64 operations<br># StarkWare uses 252-bit field elements + 128-bit security parameter<br># Post-quantum estimate: ~100-bit security (conservative)<br># Mitigation: increase query count in FRI → easy parameter adjustment<br># Production STARKs (StarkNet) are considered post-quantum safe<br># with appropriate parameter choices<br>print(&quot;STARK post-quantum security: manageable with parameter adjustment&quot;)<br>print(&quot;No fundamental redesign required&quot;)</pre><h3>Nova — BROKEN</h3><p><strong>Quantum vulnerability:</strong> Critical</p><p>Nova uses Pedersen commitments for its folding scheme — ECDLP-based. Despite being transparent and not requiring a trusted setup, Nova is not post-quantum safe.</p><pre># Nova&#39;s relaxed R1CS commitment:<br># [W] = w_0·G_0 + w_1·G_1 + ... + w_n·G_n  (Pedersen multi-commitment)<br># Security: discrete log in elliptic curve groups<br># Shor&#39;s breaks this → Nova folding is not post-quantum safe<br># SuperNova, HyperNova (as currently implemented): same vulnerability<br># Exception: HyperNova variants using FRI commitments → post-quantum safe<br># This is active research territory as of 2024</pre><h3>Plonky2 — SAFE ✓</h3><p><strong>Quantum vulnerability:</strong> Grover only (manageable)</p><p>Plonky2 uses FRI over the Goldilocks field. No elliptic curves, no pairings, no discrete log. Security reduces to:</p><ol><li>FRI soundness (information-theoretic + hash)</li><li>Poseidon2 hash collision resistance (quantum-safe with 256-bit output)</li></ol><pre># Plonky2 field: Goldilocks = 2^64 - 2^32 + 1<br># This is NOT an elliptic curve — it&#39;s a prime field for polynomial arithmetic<br># No discrete log problem involved<br># Hash function: Poseidon2 (STARK-friendly hash, 256-bit output)<br># Quantum attack: Grover → 128-bit quantum security<br># Status: considered post-quantum safe<br># Note: &quot;Goldilocks&quot; refers to the prime field, not a curve<br># The field arithmetic has no quantum vulnerability<br>print(&quot;Plonky2: FRI + Poseidon2 → post-quantum safe&quot;)<br>print(&quot;No elliptic curves in the construction&quot;)</pre><h3>Plonky3 — SAFE ✓</h3><p><strong>Quantum vulnerability:</strong> Grover only (manageable)</p><p>Plonky3 inherits Plonky2’s post-quantum properties with additional flexibility. The Mersenne31 field is a prime field — not an elliptic curve — with no ECDLP-based assumptions.</p><p>The configurable hash functions (Poseidon2, Blake3, Keccak) all reduce to hash collision resistance under quantum attack.</p><h3>SP1 — SAFE ✓</h3><p><strong>Quantum vulnerability:</strong> Grover only (manageable)</p><p>SP1 uses Plonky3 as its proving backend. The RISC-V ISA being proved has no cryptographic assumptions — it’s just a computation model. Post-quantum security inherits from Plonky3.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/820/1*LYttkEQkobxvengT7oCgkA.png" /></figure><h3>The Migration Landscape</h3><p>The quantum threat creates a clear migration story:</p><p><strong>Immediate action needed (production systems):</strong></p><p>Systems with long-term security requirements — privacy protocols, identity systems, cross-chain bridges — should begin migration planning now. The cryptographic community’s estimate of 10–20 years to relevant quantum computers is not a guarantee; it’s a median estimate with significant uncertainty.</p><p><strong>The migration playbook:</strong></p><pre>KZG-based system (PLONK, Marlin, Groth16)<br>  → Replace KZG with FRI<br>  → Keep arithmetization (R1CS, PLONK gates)<br>  → Result: STARK-like system with same programming model<br>  → Example: PLONK + KZG → Plonky2 (PLONK + FRI)<br>IPA-based system (Halo2)<br>  → Replace IPA with hash-based commitment<br>  → Keep PLONK arithmetization and recursion<br>  → Result: post-quantum Halo2 variant<br>  → Active research: multiple teams working on this<br>Nova-based system<br>  → Replace Pedersen commitments with hash-based folding<br>  → HyperNova with FRI backend<br>  → Active research: not yet production-ready<br>Application layer:<br>  → Migrate to SP1 or Plonky3-based systems<br>  → No circuit rewriting required - just switch the prover</pre><p><strong>The good news:</strong> The arithmetization layer (R1CS, PLONK gates, AIR) is quantum-neutral. The vulnerability lives entirely in the <em>commitment scheme</em>. This means migrating from a quantum-vulnerable to a quantum-safe system is a commitment scheme swap, not a full redesign.</p><p><strong>The bad news:</strong> Proof sizes grow significantly. Groth16’s 200-byte proof becomes a Plonky2 proof of ~100KB–1MB. For on-chain verification, this is a real cost — more calldata, more gas. The field is actively working on reducing STARK proof sizes; recursive aggregation mitigates the problem at scale.</p><h3>“Harvest Now, Decrypt Later”</h3><p>There is one threat that is already active, not future: <strong>harvest now, decrypt later</strong> attacks.</p><p>An adversary today can record encrypted transactions or ZK proofs and store them. When quantum computers arrive, they decrypt the stored data. For privacy-sensitive ZK applications — Zcash shielded transactions, confidential DeFi, anonymous credentials — this means data generated <em>today</em> is at risk in the <em>future</em>.</p><pre># Harvest now, decrypt later — timeline example<br>class HarvestAttack:<br>    def __init__(self):<br>        self.harvested_proofs = []<br>    def harvest(self, groth16_proof, public_inputs):<br>        &quot;&quot;&quot;<br>        Store proof + public inputs today.<br>        The proof itself is public - no attack needed to collect it.<br>        &quot;&quot;&quot;<br>        self.harvested_proofs.append({<br>            &quot;proof&quot;: groth16_proof,   # 200 bytes, publicly visible<br>            &quot;inputs&quot;: public_inputs,  # public<br>            &quot;timestamp&quot;: &quot;2024&quot;<br>        })<br>        print(f&quot;Stored proof. Total harvested: {len(self.harvested_proofs)}&quot;)<br>    def decrypt_later(self, quantum_computer):<br>        &quot;&quot;&quot;<br>        In ~2035: use quantum computer to break ECDLP<br>        Recover the witness (private inputs) from old proofs.<br>        &quot;&quot;&quot;<br>        for stored in self.harvested_proofs:<br>            witness = quantum_computer.break_groth16(<br>                stored[&quot;proof&quot;],<br>                stored[&quot;inputs&quot;]<br>            )<br>            print(f&quot;Recovered private inputs from 2024 proof: {witness}&quot;)<br>            # This reveals: private transaction amounts, private keys,<br>            # identity attributes, anything proved with Groth16<br># For hash-based proofs: harvest now, decrypt later doesn&#39;t work<br># SHA-256 preimage is hard classically AND quantum - no future threat</pre><p>For applications where long-term privacy matters, this is an argument for migrating to hash-based systems <em>now</em>, not in 10 years.</p><h3>What to Remember from This Article</h3><ul><li><strong>Shor’s algorithm</strong> breaks ECDLP exponentially — this kills Groth16, PLONK, Marlin, Bulletproofs, Halo2, Nova</li><li><strong>Grover’s algorithm</strong> gives only a quadratic speedup on hash functions — manageable by doubling security parameters</li><li><strong>The vulnerability</strong> lives in the commitment scheme, not the arithmetization — migration is a commitment scheme swap</li><li><strong>Hash-based systems</strong> (STARK, Ligero, Aurora, Virgo, Plonky2, Plonky3, SP1) survive quantum attacks with parameter adjustments</li><li><strong>“Harvest now, decrypt later”</strong> is a current threat for long-lived privacy applications — don’t wait 10 years to migrate</li><li><strong>No trusted setup ≠ post-quantum safe</strong> — Halo2 and Nova prove this. Transparency and quantum resistance are independent properties</li><li><strong>The migration cost</strong> is real: proof sizes grow from ~200 bytes (Groth16) to ~100KB–1MB (STARK/Plonky2). Recursive aggregation is the engineering answer</li></ul><p>Next up: the full grand comparison — every system, every dimension, in one place.</p><p><em>Article 8: Grand Comparison — Proof Size, Speed, Setup, and PQ Status for All 28 Systems</em></p><p><strong>References</strong></p><ul><li>Shor, P. — “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” (SIAM 1997)</li><li>Grover, L. — “A Fast Quantum Mechanical Algorithm for Database Search” (STOC 1996)</li><li>NIST — “Post-Quantum Cryptography Standardization” (2024 final standards)</li><li>Bernstein, Lange — “Post-quantum cryptography” (Nature 2017)</li><li>Banegas et al. — “CTIDH: faster constant-time CSIDH” (2021) — class group alternatives</li><li>StarkWare — “A Cambrian Explosion of Crypto Proofs” (blog, 2021)</li><li>Zcash — “The Orchard Shielded Pool” (documentation, 2021)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5d4f9ae4c4b8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Folding Schemes and the zkVM Era: Nova, Plonky2, Plonky3, and SP1 — Article 6 of the ZKP Systems…]]></title>
            <link>https://medium.com/@umitaygul/folding-schemes-and-the-zkvm-era-nova-plonky2-plonky3-and-sp1-article-6-of-the-zkp-systems-c70502937a00?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/c70502937a00</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Wed, 15 Apr 2026 12:33:53 GMT</pubDate>
            <atom:updated>2026-04-15T12:33:53.269Z</atom:updated>
            <content:encoded><![CDATA[<h3>Folding Schemes and the zkVM Era: Nova, Plonky2, Plonky3, and SP1 — Article 6 of the ZKP Systems Series</h3><p>The systems in the previous five articles all share one assumption: you write a circuit. You express your computation as a set of arithmetic constraints, compile it, then prove it. The circuit is the fundamental unit of work.</p><p>This assumption held for a decade. Then two things happened simultaneously.</p><p>First, <strong>Nova</strong> (2021) introduced folding schemes — a technique that sidesteps SNARKs entirely for incremental computations, reducing recursion overhead to near zero.</p><p>Second, <strong>Plonky2</strong> (2022) combined PLONK’s arithmetization with FRI’s hash-based commitments, achieving recursive proof times 100x faster than anything before it — fast enough to prove arbitrary programs in real time.</p><p>Together, these breakthroughs enabled a new abstraction: the <strong>zkVM</strong> (zero-knowledge virtual machine). Instead of writing circuits, you write normal programs. The VM handles the circuit under the hood. SP1, Risc0, Nexus — these systems let you prove arbitrary Rust code without touching a constraint system.</p><p>We are watching the invention of the compiler, in real time.</p><h3>Nova (2021): Folding Schemes</h3><p><strong>Paper:</strong> “Nova: Recursive Zero-Knowledge Arguments from Folding Schemes” <strong>Authors:</strong> Kothapalli, Setty, Tzialla (Microsoft Research) <strong>Published:</strong> ePrint 2021, CRYPTO 2022</p><p>Nova’s contribution is conceptually simple and technically deep: it introduced <strong>folding schemes</strong> as a primitive for incrementally verifiable computation (IVC), and showed that folding is <em>strictly simpler</em> than SNARKs — yet sufficient for recursion.</p><h3>The Problem with Recursive SNARKs</h3><p>Before Nova, recursive proofs worked by proving “a SNARK verification is correct” inside another SNARK. This is expensive because SNARK verification involves elliptic curve operations, which are costly to express as arithmetic circuit constraints.</p><pre># Old approach: recursive SNARKs<br># Prove that &quot;the verification of proof_n passed&quot; inside circuit_{n+1}<br>def recursive_snark_step(prev_proof, new_computation, circuit):<br>    &quot;&quot;&quot;<br>    Cost: O(SNARK verifier size) extra gates per recursion step<br>    SNARK verifier ≈ 10,000–100,000 gates (elliptic curve ops in-circuit)<br>    → recursion overhead dominates the actual computation<br>    &quot;&quot;&quot;<br>    # This circuit must encode the full SNARK verifier<br>    verify_prev = encode_snark_verifier(prev_proof)    # ~50,000 gates<br>    compute_new = encode_computation(new_computation)  # actual work<br>    <br>    total_gates = len(verify_prev) + len(compute_new)<br>    overhead_ratio = len(verify_prev) / len(compute_new)<br>    <br>    print(f&quot;Recursion overhead: {overhead_ratio:.1f}x the actual computation&quot;)<br>    # Often 10x–100x overhead - recursion costs more than the computation</pre><h3>Folding: A Simpler Primitive</h3><p>Nova’s insight: you don’t need a full SNARK to accumulate correctness. You just need a <strong>folding scheme</strong> — a way to “fold” two instances of a relation into one, such that if the folded instance is satisfied, both originals were too.</p><p>The key operation is <strong>relaxed R1CS</strong>: a slight generalization of standard R1CS that allows the prover to accumulate an error term E which must be zero at the end:</p><pre>import numpy as np<br># Standard R1CS: Az ∘ Bz = Cz  (must hold exactly)<br># Relaxed R1CS:  Az ∘ Bz = u·Cz + E  (u=1, E=0 at the end)<br># The relaxation lets us fold two instances together cheaply<br>def fold_instances(instance1, instance2, r):<br>    &quot;&quot;&quot;<br>    Fold two relaxed R1CS instances into one.<br>    If folded instance is satisfying, both originals were satisfying.<br>    <br>    Cost: O(n) - just vector additions and scalar multiplications<br>    No SNARK verifier, no elliptic curve point additions in-circuit<br>    &quot;&quot;&quot;<br>    W1, E1, u1, x1 = instance1  # witness, error, scalar, public input<br>    W2, E2, u2, x2 = instance2<br>    # Cross term T = AW1 ∘ BW2 + AW2 ∘ BW1 - u1·CW2 - u2·CW1<br>    T = compute_cross_term(W1, W2, u1, u2)<br>    commitment_T = commit(T)  # Pedersen commitment to cross term<br>    # Verifier sends random challenge r (or Fiat-Shamir)<br>    # Fold: linear combination with weight r<br>    W_folded = W1 + r * W2<br>    E_folded = E1 + r * T + r**2 * E2<br>    u_folded = u1 + r * u2<br>    x_folded = x1 + r * x2<br>    return (W_folded, E_folded, u_folded, x_folded)<br># After n steps, verify just ONE relaxed R1CS instance<br># Overhead per step: O(n) field ops - roughly 10,000 multiplications<br># vs old approach: 50,000+ gates per step<br>print(&quot;Nova recursion overhead: ~2 scalar multiplications per step&quot;)<br>print(&quot;Old approach: ~50,000 curve point additions per step&quot;)</pre><p>The overhead per recursive step in Nova is dominated by committing to the cross term T — roughly 2 multi-scalar multiplications over the witness size. For a computation with 10,000 operations per step, the recursion overhead is about 15% — compared to 1000%+ with recursive SNARKs.</p><h3>Nova’s Curve Cycle</h3><p>Like Halo, Nova uses a cycle of elliptic curves. The primary curve handles the main computation; the secondary curve handles the commitment verification. Nova uses the <strong>Pasta curves</strong> (Pallas + Vesta) — the same cycle Halo2 uses.</p><p>At the end of the Nova accumulation, you run one final SNARK (typically Groth16 or Spartan) to compress the accumulated state into a succinct proof. The SNARK is run only once regardless of how many steps were accumulated.</p><pre>Nova IVC (n steps):<br>  Step 1: fold(instance_0, computation_1) → accumulated_1    [cheap]<br>  Step 2: fold(accumulated_1, computation_2) → accumulated_2  [cheap]<br>  ...<br>  Step n: fold(accumulated_{n-1}, computation_n) → accumulated_n [cheap]<br>  Final:  SNARK(accumulated_n) → succinct proof               [once]<br>Total cost: n × O(fold) + O(SNARK)<br>vs old:     n × O(SNARK)</pre><h3>Nova’s Descendants</h3><p>Nova’s folding idea spawned an entire family of systems:</p><ul><li><strong>SuperNova</strong> — extends Nova to prove programs with multiple different step functions (non-uniform IVC), enabling VM-style execution</li><li><strong>HyperNova</strong> — generalizes folding to the CCS constraint system, which unifies R1CS, PLONK, and AIR in one framework</li><li><strong>ProtoStar</strong> — folding for PLONK circuits, enabling arbitrary custom gates</li><li><strong>CycleFold</strong> — more efficient curve cycle handling, reducing overhead further</li></ul><p>All of these are active research areas as of 2024. The zkVM systems built on Nova (Nexus, Lurk) use SuperNova or HyperNova as their backbone.</p><h3>Plonky2 (2022): The Speed Breakthrough</h3><p><strong>Announcement:</strong> Polygon Zero blog, January 2022 <strong>Authors:</strong> Polygon Zero team (Mir Protocol acquisition)</p><p>Plonky2 asked a different question from Nova: not “how do we reduce recursion overhead?” but “how do we make the prover fast enough that recursion becomes practical at scale?”</p><p>The answer: combine PLONK’s arithmetization with FRI’s hash-based commitments, and optimize aggressively for modern CPU architecture.</p><h3>The Goldilocks Field</h3><p>Plonky2’s first key innovation is using the <strong>Goldilocks field</strong> — the prime field 𝔽_p where p = 2^64 - 2^32 + 1.</p><p>Why does this matter? Field arithmetic is at the heart of every ZK prover. The faster you can do field multiplication, the faster your prover. Goldilocks has a special structure:</p><pre># Goldilocks prime: p = 2^64 - 2^32 + 1<br>p = 2**64 - 2**32 + 1<br># Key property: reduction modulo p is extremely fast on 64-bit CPUs<br># Standard 64-bit multiplication: a * b → 128-bit result<br># Reduction modulo standard prime: requires slow division<br># Reduction modulo Goldilocks: just a few shifts and additions<br>def goldilocks_reduce(x_128bit):<br>    &quot;&quot;&quot;<br>    Reduce a 128-bit product modulo 2^64 - 2^32 + 1<br>    Without any division - just bit operations<br>    &quot;&quot;&quot;<br>    x_lo = x_128bit &amp; 0xFFFFFFFFFFFFFFFF   # low 64 bits<br>    x_hi = x_128bit &gt;&gt; 64                   # high 64 bits<br>    # Because p = 2^64 - 2^32 + 1:<br>    # 2^64 ≡ 2^32 - 1 (mod p)<br>    # 2^96 ≡ (2^32 - 1) * 2^32 (mod p)<br>    result = x_lo + (x_hi &amp; 0xFFFFFFFF) * (2**32 - 1) + (x_hi &gt;&gt; 32)<br>    return result % p<br># Benchmark comparison (approximate):<br># BN254 field multiplication:    ~100 ns<br># BLS12-381 field multiplication: ~120 ns<br># Goldilocks multiplication:       ~3 ns  - 30-40x faster<br>print(f&quot;Goldilocks prime: {p}&quot;)<br>print(f&quot;Fits in 64 bits: {p &lt; 2**64}&quot;)<br>print(&quot;Field multiplication: ~3ns on modern CPU (vs ~100ns for BN254)&quot;)</pre><h3>PLONK + FRI = Plonky2</h3><p>Plonky2 uses PLONK’s gate system (with custom gates) but replaces KZG polynomial commitments with FRI. This gives:</p><ul><li><strong>No trusted setup</strong> (FRI is transparent)</li><li><strong>Post-quantum security</strong> (FRI is hash-based)</li><li><strong>Custom gates</strong> (from PLONK) — arithmetic, range checks, Poseidon hash built-in</li><li><strong>Fast recursion</strong> via the Goldilocks field</li></ul><p>The recursive proof benchmark from the announcement: <strong>170ms on a MacBook Pro</strong> — 100x faster than prior alternatives. This was the number that made the ZK world take notice.</p><pre># Plonky2 circuit example (Rust)<br># Prove knowledge of x where x^2 + x = 30 (x = 5)<br>use plonky2::field::goldilocks_field::GoldilocksField;<br>use plonky2::plonk::circuit_builder::CircuitBuilder;<br>use plonky2::plonk::config::PoseidonGoldilocksConfig;<br>type F = GoldilocksField;<br>type C = PoseidonGoldilocksConfig;<br>const D: usize = 2;<br>fn build_circuit() -&gt; (CircuitData&lt;F, C, D&gt;, ProofWithPublicInputs&lt;F, C, D&gt;) {<br>    let config = CircuitConfig::standard_recursion_config();<br>    let mut builder = CircuitBuilder::&lt;F, D&gt;::new(config);<br>    // Private witness<br>    let x = builder.add_virtual_target();<br>    // Compute x^2<br>    let x_sq = builder.mul(x, x);<br>    // Compute x^2 + x<br>    let result = builder.add(x_sq, x);<br>    // Assert result == 30 (public)<br>    let thirty = builder.constant(F::from_canonical_u32(30));<br>    builder.connect(result, thirty);<br>    let circuit = builder.build::&lt;C&gt;();<br>    // Prove with x = 5<br>    let mut pw = PartialWitness::new();<br>    pw.set_target(x, F::from_canonical_u32(5));<br>    let proof = circuit.prove(pw).unwrap();<br>    (circuit, proof)<br>}</pre><h3>Plonky2 Recursion: The Key Application</h3><p>The headline use case for Plonky2 is <strong>recursive proof aggregation</strong> — taking many independent proofs and compressing them into one. This is exactly what a zkRollup needs: prove 10,000 transactions individually, then aggregate all proofs into one that the L1 verifies.</p><pre>Without fast recursion (old approach):<br>  Prove tx_1:  5 seconds<br>  Prove tx_2:  5 seconds<br>  ...<br>  Prove tx_10000: 5 seconds<br>  Aggregate all:  hours (recursive SNARK overhead)<br>  Total: ~14 hours for 10,000 transactions<br>With Plonky2:<br>  Prove tx_1..tx_10000: ~5 seconds each (parallel)<br>  Aggregate (binary tree of recursive proofs):<br>    Level 1: 5000 × 170ms = ~14 minutes<br>    Level 2: 2500 × 170ms = ~7 minutes<br>    ...<br>    Level 13: 1 × 170ms<br>  Total: ~30 minutes for 10,000 transactions, fully recursive</pre><h3>Plonky3 (2024): The Modular Toolkit</h3><p><strong>Repository:</strong> github.com/Plonky3/Plonky3 <strong>Authors:</strong> Polygon Zero team <strong>Released:</strong> 2024 (production-ready announcement July 2024)</p><p>Plonky2 was opinionated: one field (Goldilocks), one hash function (Poseidon2), one configuration. Plonky3 is its modular successor — a toolkit where every component is swappable.</p><h3>The Architecture</h3><pre>Plonky3 = configurable field<br>         + configurable hash function<br>         + configurable commitment scheme (FRI variants)<br>         + configurable arithmetization (PLONK / AIR / custom)</pre><p>This modularity matters because different applications have different performance bottlenecks:</p><pre>// Plonky3: configure for your use case<br>// Configuration 1: fastest on standard CPUs<br>// Uses Mersenne31 field (p = 2^31 - 1) + Poseidon2 hash<br>use p3_mersenne_31::Mersenne31;<br>use p3_poseidon2::Poseidon2;<br>type FastConfig = StarkConfig&lt;Mersenne31, Poseidon2&lt;Mersenne31, 8, 7&gt;&gt;;<br>// Configuration 2: smallest proofs<br>// Uses BabyBear field + Blake3 hash<br>use p3_baby_bear::BabyBear;<br>use p3_blake3::Blake3;<br>type SmallProofConfig = StarkConfig&lt;BabyBear, Blake3&gt;;<br>// Configuration 3: Ethereum-friendly (keccak-verifiable on L1)<br>// Uses Goldilocks field + Keccak hash<br>use p3_goldilocks::Goldilocks;<br>use p3_keccak::Keccak256;<br>type EthConfig = StarkConfig&lt;Goldilocks, Keccak256&gt;;<br>// Same circuit, different backends - swap without rewriting constraints</pre><h3>Mersenne31: The Fastest Field on Earth</h3><p>Plonky3 introduced the <strong>Mersenne31 field</strong> (p = 2^31 - 1) as an option. It&#39;s the fastest prime field for CPU arithmetic:</p><pre># Mersenne31: p = 2^31 - 1 = 2147483647<br># Why it&#39;s fast:<br># On 32-bit arithmetic: a * b fits in 64 bits<br># Reduction: x mod (2^31 - 1) = (x &gt;&gt; 31) + (x &amp; (2^31 - 1))<br># That&#39;s ONE shift and ONE addition - the absolute minimum<br>def mersenne31_reduce(x_64bit):<br>    p = 2**31 - 1<br>    return (x_64bit &gt;&gt; 31) + (x_64bit &amp; p)<br>    # Two operations. No division. Maximum CPU throughput.<br># Field multiplication throughput comparison:<br># BN254 (256-bit):     ~100 ns per multiplication<br># Goldilocks (64-bit): ~3 ns per multiplication<br># Mersenne31 (31-bit): ~1 ns per multiplication<br># → Mersenne31 is 100x faster than BN254 for raw field arithmetic</pre><p>The tradeoff: smaller field means larger polynomials for the same security level, requiring the Circle FFT (a variant of FFT designed for Mersenne31). StarkWare collaborated with Polygon Zero to develop the Circle FFT specifically for Plonky3.</p><h3>Plonky3 in Production</h3><p>Plonky3 is the backend for:</p><ul><li><strong>SP1</strong> (Succinct Labs) — prove arbitrary Rust programs</li><li><strong>Polygon AggLayer</strong> — aggregate proofs across Polygon chains</li><li><strong>Valida</strong> — a zkVM targeting minimal constraint overhead</li><li><strong>Risc0</strong> (partially) — uses Plonky3 for some proving paths</li></ul><p>The 5–10x speedup over Plonky2 means recursive aggregation that took 30 minutes now takes 3–6 minutes for the same workload.</p><h3>SP1 (2024): Prove Any Rust Program</h3><p><strong>Repository:</strong> github.com/succinctlabs/sp1 <strong>Authors:</strong> Succinct Labs <strong>Released:</strong> 2024</p><p>SP1 is the practical culmination of everything in this series. It’s a <strong>zkVM</strong> — a virtual machine whose execution can be proved using zero-knowledge proofs. You write normal Rust. You run it. SP1 produces a proof that the Rust program executed correctly with specific inputs and outputs.</p><p>No circuit. No constraint system. No R1CS. Just Rust.</p><h3>How a zkVM Works</h3><p>A zkVM works by defining a simple CPU architecture (in SP1’s case, RISC-V) and building a circuit that proves one CPU step:</p><pre>zkVM circuit = &quot;Given state S_i, executing instruction I produces state S_{i+1}&quot;<br>For a program with N instructions:<br>  Step 1:  S_0 → S_1   (proved by one circuit evaluation)<br>  Step 2:  S_1 → S_2   (proved by one circuit evaluation)<br>  ...<br>  Step N:  S_{N-1} → S_N (proved by one circuit evaluation)<br>Recursive aggregation: fold all N steps into one proof</pre><p>The single-step circuit is large (RISC-V has complex memory semantics), but with Nova-style folding and Plonky3’s fast prover, it becomes tractable.</p><h3>SP1 in Practice</h3><pre>// SP1 program: runs on the RISC-V zkVM<br>// This is normal Rust — no circuit, no constraints<br>// program/src/main.rs<br>use sp1_zkvm::io;<br>fn main() {<br>    // Read private inputs<br>    let x: u64 = io::read();<br>    let y: u64 = io::read();<br>    // Normal Rust computation<br>    let result = fibonacci(x);<br>    assert_eq!(result, y, &quot;Fibonacci computation incorrect&quot;);<br>    // Commit to public output<br>    io::commit(&amp;result);<br>}<br>fn fibonacci(n: u64) -&gt; u64 {<br>    if n &lt;= 1 { return n; }<br>    let mut a = 0u64;<br>    let mut b = 1u64;<br>    for _ in 2..=n {<br>        let c = a + b;<br>        a = b;<br>        b = c;<br>    }<br>    b<br>}</pre><pre>// Host program: generates and verifies the proof<br>use sp1_sdk::{ProverClient, SP1Stdin};<br>fn main() {<br>    // Compile the guest program to RISC-V ELF<br>    let elf = include_bytes!(&quot;../program/elf/riscv32im-succinct-zkvm-elf&quot;);<br>    let client = ProverClient::new();<br>    let mut stdin = SP1Stdin::new();<br>    // Private inputs: prove fibonacci(10) = 55<br>    stdin.write(&amp;10u64);  // n<br>    stdin.write(&amp;55u64);  // expected output<br>    // Generate proof - no circuit writing required<br>    let (pk, vk) = client.setup(elf);<br>    let proof = client.prove(&amp;pk, stdin).expect(&quot;Proof generation failed&quot;);<br>    println!(&quot;Proof generated successfully&quot;);<br>    println!(&quot;Public output: {:?}&quot;, proof.public_values);<br>    // Verify<br>    client.verify(&amp;proof, &amp;vk).expect(&quot;Verification failed&quot;);<br>    println!(&quot;Proof verified - fibonacci(10) = 55, proven in ZK&quot;);<br>}</pre><pre># Run it<br>cargo prove build   # compile Rust → RISC-V ELF<br>cargo prove run     # generate proof<br># Output:<br># Proof generated successfully<br># Public output: [55]<br># Proof verified - fibonacci(10) = 55, proven in ZK</pre><h3>SP1’s Performance Profile</h3><p>SP1’s performance depends on program complexity. For a SHA-256 hash:</p><ul><li><strong>Proof generation:</strong> ~2–5 seconds (on a standard server)</li><li><strong>Proof size:</strong> ~1–2 MB (STARK-based, large but manageable)</li><li><strong>Verification:</strong> ~50ms</li></ul><p>For more complex programs, SP1 supports <strong>distributed proving</strong> — splitting the execution trace across multiple machines and aggregating the proofs. This is how Succinct Labs proves Ethereum block headers in production for their light client bridge.</p><h3>The zkVM Landscape</h3><p>SP1 is one of several zkVMs that emerged in 2023–2024:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*w6zrq3cu5aPQAMJeh_mTvA.png" /></figure><h3>The Abstraction Stack, Completed</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*5Jox5SaABAC93P652rppMA.png" /></figure><h3>PQ Outlook</h3><p><strong>Nova: Not post-quantum safe.</strong> Nova’s folding scheme uses Pedersen commitments (ECDLP-based). The discrete log assumption is broken by Shor’s algorithm. However, Nova’s descendants using FRI-based commitments (like some HyperNova variants) can be made post-quantum safe.</p><p><strong>Plonky2: Post-quantum safe.</strong> FRI-based commitments, hash-based security. Goldilocks field arithmetic is not based on any quantum-vulnerable assumption. The system is plausibly post-quantum secure with 128-bit security against Grover’s algorithm.</p><p><strong>Plonky3: Post-quantum safe.</strong> Same argument as Plonky2. The modularity adds flexibility — you can configure Plonky3 with different hash functions to tune the security/performance trade-off.</p><p><strong>SP1: Post-quantum safe.</strong> SP1 uses Plonky3 as its proving backend. The security inherits from Plonky3’s FRI-based construction. The RISC-V ISA itself has no cryptographic assumptions.</p><h3>What to Remember from This Article</h3><ul><li><strong>Nova</strong> introduced folding schemes — a simpler primitive than SNARKs that reduces recursion overhead from 100x to ~15%, making incremental computation practical</li><li><strong>Plonky2</strong> combined PLONK + FRI + Goldilocks field to achieve 100x faster recursive proofs — 170ms on a laptop</li><li><strong>Plonky3</strong> made Plonky2’s architecture modular — swap fields and hash functions for your use case; Mersenne31 gives the fastest field arithmetic available</li><li><strong>SP1</strong> is the practical endpoint: prove arbitrary Rust programs without writing circuits — no R1CS, no constraints, just code</li><li><strong>The zkVM era</strong> is to ZK proofs what compilers were to assembly — most developers will write programs, not circuits</li><li><strong>PQ status</strong>: Nova is not PQ-safe (ECDLP); Plonky2, Plonky3, SP1 are plausibly PQ-safe (FRI/hash-based)</li></ul><p>Next: the quantum threat in full — which systems survive, which don’t, and what the migration path looks like.</p><p><em>Article 7: The Quantum Threat — Which Proof Systems Survive and Which Don’t</em></p><p><strong>References</strong></p><ul><li>Kothapalli, Setty, Tzialla — “Nova: Recursive Zero-Knowledge Arguments from Folding Schemes” (CRYPTO 2022)</li><li>Kothapalli, Setty — “SuperNova: Proving Universal Machine Executions without Universal Circuits” (ePrint 2022)</li><li>Polygon Zero — “Introducing Plonky2” (blog post, January 2022)</li><li>Polygon Labs — “Plonky3: Production-Ready” (blog post, July 2024)</li><li>Succinct Labs — SP1 documentation, github.com/succinctlabs/sp1</li><li>Ben-Sasson et al. — “Circle STARKs” (ePrint 2024) — Circle FFT for Mersenne31</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c70502937a00" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Hash Functions All the Way Down: What Makes a Proof Post-Quantum Safe?]]></title>
            <link>https://medium.com/@umitaygul/hash-functions-all-the-way-down-what-makes-a-proof-post-quantum-safe-d25504e0fc7d?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/d25504e0fc7d</guid>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[post-quantum-cryptography]]></category>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Tue, 14 Apr 2026 12:48:46 GMT</pubDate>
            <atom:updated>2026-04-14T12:48:46.160Z</atom:updated>
            <content:encoded><![CDATA[<h3>Hash Functions All the Way Down: What Makes a Proof Post-Quantum Safe? — Article 5 of the ZKP Systems Series</h3><p>Every system we’ve covered so far — Groth16, PLONK, Marlin, Bulletproofs, Halo2 — shares a common vulnerability. Somewhere in their design, they rely on the hardness of the <strong>elliptic curve discrete logarithm problem (ECDLP)</strong>. A sufficiently powerful quantum computer running Shor’s algorithm breaks ECDLP. And with it, every proof those systems ever generated becomes forgeable.</p><p>This is not a distant theoretical concern. NIST finalized its post-quantum cryptography standards in 2024. The cryptographic community’s consensus is that quantum computers capable of breaking 256-bit ECDLP are likely 10–20 years away — but “likely” and “10–20 years” are not reassurances you can build long-lived infrastructure on.</p><p>The four systems in this article took a different path. They asked: <em>what if we built proof systems using only cryptographic primitives that quantum computers cannot efficiently break?</em></p><p>The answer: <strong>hash functions.</strong></p><h3>Why Hash Functions Survive Quantum Attacks</h3><p>The best known quantum attack on hash functions is <strong>Grover’s algorithm</strong>, which provides a quadratic speedup for unstructured search. Against a hash function with n-bit output:</p><pre>import math<br>def quantum_attack_cost(n_bits):<br>    &quot;&quot;&quot;<br>    Classical attack: 2^n operations (birthday bound for collision)<br>    Quantum attack (Grover): 2^(n/2) operations<br>    Mitigation: double the output size<br>    SHA-256 (256-bit) → quantum cost: 2^128 - still infeasible<br>    SHA-512 (512-bit) → quantum cost: 2^256 - extremely infeasible<br>    &quot;&quot;&quot;<br>    classical_cost = 2 ** n_bits<br>    quantum_cost = 2 ** (n_bits / 2)<br>    print(f&quot;Hash output: {n_bits} bits&quot;)<br>    print(f&quot;Classical collision attack: 2^{n_bits} ≈ {classical_cost:.2e}&quot;)<br>    print(f&quot;Quantum (Grover) attack:    2^{n_bits//2} ≈ {quantum_cost:.2e}&quot;)<br>    print(f&quot;Quantum speedup: {classical_cost/quantum_cost:.0f}x&quot;)<br>    print()<br>quantum_attack_cost(256)<br># Hash output: 256 bits<br># Classical collision attack: 2^256 ≈ 1.16e+77<br># Quantum (Grover) attack:    2^128 ≈ 3.40e+38<br># Quantum speedup: 340282366920938463463374607431768211456x<br># But 2^128 is still completely infeasible - even for quantum computers<br># For comparison, all atoms in the observable universe: ~10^80</pre><p>Contrast this with ECDLP under Shor’s algorithm: a quantum computer reduces a 256-bit ECDLP from 2^128 operations (classical) to roughly 2^26 — a factor of 2^102 improvement. The gap between &quot;Grover cuts security in half&quot; and &quot;Shor renders security negligible&quot; is enormous.</p><p>The upshot: if you build a proof system whose security reduces entirely to the collision resistance of a hash function, you get a system that remains secure against quantum computers — just double your hash output size from 128 to 256 bits.</p><p>The four systems in this article do exactly this.</p><h3>Ligero (2017): The Quiet Pioneer</h3><p><strong>Paper:</strong> “Ligero: Lightweight Sublinear Arguments Without a Trusted Setup” <strong>Authors:</strong> Ames, Hazay, Ishai, Venkitasubramaniam <strong>Published:</strong> ACM CCS 2017</p><p>Ligero arrived two years before STARKs went public, one year before Bulletproofs — and it quietly solved the post-quantum problem first. It’s the least celebrated of the four systems here, but historically it deserves more attention.</p><h3>The MPC-in-the-Head Technique</h3><p>Ligero is based on a technique called <strong>MPC-in-the-head</strong> (Ishai, Kushilevitz, Ostrovsky, Sahai — 2007): the prover mentally simulates a multiparty computation among n virtual parties, each holding a share of the witness. The proof consists of revealing a few of these simulated party views, which the verifier checks for consistency.</p><p>The key insight: if the simulation is consistent, the witness must satisfy the circuit constraints. If the witness is wrong, the inconsistency shows up in at least one of the checked views.</p><pre># Conceptual: MPC-in-the-head for circuit satisfiability<br># Prover mentally runs n &quot;virtual parties&quot; each with a share of witness<br>import hashlib<br>import random<br>def mpc_in_head_sketch(witness, circuit, n_parties=4, n_checks=2):<br>    &quot;&quot;&quot;<br>    Step 1: Secret-share the witness among n virtual parties<br>    Step 2: Each party locally evaluates the circuit on their share<br>    Step 3: Commit to each party&#39;s view (using hash - no trusted setup!)<br>    Step 4: Verifier challenges: reveal k random party views<br>    Step 5: Verifier checks revealed views are consistent<br>    &quot;&quot;&quot;<br>    # Step 1: share witness (additive secret sharing over field)<br>    shares = secret_share(witness, n_parties)<br>    # Step 2 &amp; 3: each party evaluates and commits<br>    party_views = []<br>    commitments = []<br>    for i, share in enumerate(shares):<br>        view = evaluate_circuit_share(circuit, share, i, shares)<br>        party_views.append(view)<br>        # Hash commitment - no elliptic curves, no pairings, no trusted setup<br>        commitment = hashlib.sha256(<br>            str(view).encode()<br>        ).hexdigest()<br>        commitments.append(commitment)<br>    # Step 4: verifier picks random parties to inspect (Fiat-Shamir)<br>    challenge = hashlib.sha256(<br>        str(commitments).encode()<br>    ).hexdigest()<br>    indices_to_open = derive_indices(challenge, n_checks, n_parties)<br>    # Step 5: reveal chosen views - verifier checks consistency<br>    opened = [(i, party_views[i]) for i in indices_to_open]<br>    return commitments, opened<br># Security: if witness is wrong, inconsistency caught with prob (1 - k/n)<br># Make n large enough → soundness error negligible<br># Hash-based commitments → post-quantum secure</pre><h3>Ligero’s Properties</h3><p>Ligero’s proof size is O(√n) — sublinear but not logarithmic. For a circuit with 1 million gates, the proof is ~1000x smaller than the circuit (not 1,000,000x smaller like a SNARK). This makes it impractical for large circuits on-chain, but workable for applications where proof size is less critical than trust assumptions.</p><p>The system is:</p><ul><li><strong>Transparent</strong>: all randomness from the hash function</li><li><strong>Post-quantum safe</strong>: security reduces to collision resistance of SHA-256</li><li><strong>Universal</strong>: works for any arithmetic circuit without circuit-specific parameters</li><li><strong>Practically slower</strong> than pairing-based systems for small circuits</li></ul><p>Ligero’s lasting contribution was proving that hash-based SNARKs were <em>possible</em> before anyone else. Aurora and STARKs built directly on its foundations.</p><h3>Aurora (2019): Ligero Grown Up</h3><p><strong>Paper:</strong> “Aurora: Transparent Succinct Arguments for R1CS” <strong>Authors:</strong> Ben-Sasson, Chiesa, Riabzev, Spooner, Virza, Ward <strong>Published:</strong> EUROCRYPT 2019</p><p>Aurora is what happens when you take Ligero’s MPC-in-the-head idea and replace the inner code with something much more powerful: <strong>Reed-Solomon codes</strong> and the <strong>IOP (Interactive Oracle Proof)</strong> framework.</p><h3>Reed-Solomon Codes and Why They Matter</h3><p>A Reed-Solomon code encodes a message as the evaluations of a polynomial over a large domain. The key property: if you’re given evaluations at enough points, you can reconstruct the whole polynomial. And if a polynomial has degree d, it can have at most d roots — which means corrupting it is hard to hide.</p><pre># Reed-Solomon: encode a polynomial by its evaluations<br># This lets us test polynomial properties using random spot-checks<br>def rs_encode(coefficients, evaluation_domain):<br>    &quot;&quot;&quot;<br>    Encode polynomial f(x) = c₀ + c₁x + c₂x² + ...<br>    as its evaluations at all points in the domain.<br>    <br>    Key property: a degree-d polynomial evaluated at n &gt;&gt; d points<br>    has a very specific structure - easy to verify, hard to fake.<br>    &quot;&quot;&quot;<br>    evaluations = []<br>    for x in evaluation_domain:<br>        y = sum(c * (x**i) for i, c in enumerate(coefficients))<br>        evaluations.append(y)<br>    return evaluations<br># Example: encode f(x) = 1 + 2x + x²  over domain {0,1,2,3,4}<br>coefficients = [1, 2, 1]  # f(x) = x² + 2x + 1 = (x+1)²<br>domain = [0, 1, 2, 3, 4]<br>encoded = rs_encode(coefficients, domain)<br>print(&quot;RS encoding:&quot;, encoded)<br># [1, 4, 9, 16, 25]  - evaluations of (x+1)²<br># Aurora uses this to encode the witness and circuit constraints<br># Then uses FRI (Fast RS IOP of Proximity) to verify polynomial properties<br># All via hash functions - no elliptic curves</pre><h3>The IOP Framework</h3><p>Aurora uses the <strong>Interactive Oracle Proof (IOP)</strong> model: the prover sends oracles (functions the verifier can query at chosen points), and the verifier checks consistency by sampling a few values. Combined with the Fiat-Shamir heuristic (replacing verifier randomness with hash outputs), this becomes non-interactive.</p><p>Aurora’s key achievements over Ligero:</p><ul><li>Proof size: O(log² n) instead of O(√n) — much more practical for large circuits</li><li>Directly proves <strong>R1CS</strong> satisfiability — compatible with existing circuit toolchains</li><li>Maintains full post-quantum security via hash functions</li></ul><p>For a circuit with 1 million gates:</p><pre>Ligero proof:  ~1,000 KB    (O(√n))<br>Aurora proof:  ~200 KB      (O(log² n))<br>STARK proof:   ~100-300 KB  (O(log² n) with FRI)</pre><p>Still larger than pairing-based systems (~200 bytes for Groth16), but astronomically better than Ligero for large circuits.</p><h3>Virgo (2020): GKR Meets Post-Quantum</h3><p><strong>Paper:</strong> “Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof” <strong>Authors:</strong> Zhang, Xie, Zhang, Song <strong>Published:</strong> IEEE S&amp;P 2020</p><p>Virgo takes a different path to post-quantum security. Instead of the MPC-in-the-head / IOP route, it builds on the <strong>GKR protocol</strong> (Goldwasser, Kalai, Rothblum — 2008) — a sumcheck-based interactive proof for layered arithmetic circuits.</p><h3>The Sumcheck Protocol</h3><p>The sumcheck protocol is elegant: to prove that ∑ₓ f(x) = v (the sum of a multivariate polynomial over all inputs equals v), the prover and verifier engage in a logarithmic number of rounds, each reducing the claim to a simpler one.</p><pre>def sumcheck_round(f_partial, claimed_sum, round_idx):<br>    &quot;&quot;&quot;<br>    Each round: prover sends a univariate polynomial g(x_i)<br>    Verifier checks: g(0) + g(1) == claimed_sum (for this round)<br>    Then challenges a random r_i<br>    Next round&#39;s claim: g(r_i) over remaining variables<br>    <br>    After log(n) rounds: reduces to evaluating f at a single point<br>    That evaluation can be checked with a polynomial commitment<br>    &quot;&quot;&quot;<br>    # Prover sends g(x_i) — univariate restriction of f<br>    g = restrict_to_variable(f_partial, round_idx)<br>    # Verifier check<br>    assert g(0) + g(1) == claimed_sum, &quot;Sumcheck failed&quot;<br>    # Random challenge (hash-based in non-interactive version)<br>    r = random_field_element()<br>    new_claim = g(r)<br>    return restrict_further(f_partial, round_idx, r), new_claim</pre><p>Virgo uses sumcheck to prove circuit evaluation layer by layer, then uses a <strong>hash-based polynomial commitment scheme</strong> to bind the prover to their polynomial claims. The result:</p><ul><li>Post-quantum secure (hash-based commitments)</li><li>Transparent (no trusted setup)</li><li>Practically efficient — Virgo’s prover is linear time in circuit size</li><li>Proof size: O(log² n) — comparable to Aurora and STARK</li></ul><p>Virgo is an underrated system. It doesn’t have the brand recognition of STARKs or the production deployments of Halo2, but its linear prover time is genuinely impressive and its hash-based design is clean.</p><h3>zk-STARK (2019): The Industrial Option</h3><p><strong>Paper:</strong> “Scalable, transparent, and post-quantum secure computational integrity” <strong>Authors:</strong> Ben-Sasson, Bentov, Horesh, Riabzev <strong>Published:</strong> ePrint 2018, widely deployed from 2019</p><p>zk-STARK is the system that brought post-quantum ZK proofs into production at scale. It powers StarkNet, StarkEx (used by dYdX, Sorare, Immutable X), and is used internally by Polygon for its zkEVM. Understanding STARKs means understanding <strong>FRI</strong> — the Fast Reed-Solomon IOP of Proximity.</p><h3>FRI: The Heart of STARKs</h3><p>FRI is a protocol that proves a committed function is <em>close to</em> a low-degree polynomial, using a recursive folding technique and only hash functions:</p><pre>import hashlib<br>def fri_commit(evaluations, domain):<br>    &quot;&quot;&quot;<br>    FRI commitment: commit to a polynomial via its evaluations,<br>    using a Merkle tree - no elliptic curves, no pairings.<br>    &quot;&quot;&quot;<br>    # Build Merkle tree over evaluations<br>    leaves = [hashlib.sha256(str(e).encode()).digest() for e in evaluations]<br>    merkle_root = build_merkle_tree(leaves)<br>    return merkle_root  # commitment: just a hash<br>def fri_fold(evaluations, domain, beta):<br>    &quot;&quot;&quot;<br>    FRI folding step: reduce a degree-d polynomial over domain D<br>    to a degree-d/2 polynomial over domain D/2.<br>    <br>    f(x) = f_even(x²) + x · f_odd(x²)<br>    f_folded(x²) = f_even(x²) + β · f_odd(x²)<br>    <br>    Each fold: domain size halves, degree halves<br>    After log(d) folds: constant polynomial - easy to check<br>    &quot;&quot;&quot;<br>    n = len(evaluations)<br>    folded = []<br>    for i in range(n // 2):<br>        f_x  = evaluations[i]<br>        f_mx = evaluations[i + n // 2]  # f(-x) = f_even - x·f_odd<br>        # f_even = (f(x) + f(-x)) / 2<br>        # f_odd  = (f(x) - f(-x)) / (2x)<br>        f_even = (f_x + f_mx) / 2<br>        f_odd  = (f_x - f_mx) / (2 * domain[i])<br>        folded.append(f_even + beta * f_odd)<br>    return folded, [x**2 for x in domain[:n//2]]<br># After log(n) folds, what remains is a constant<br># Verifier checks a few random positions at each layer - Merkle proof per position<br># Total proof: O(log²(n)) hash values - no elliptic curves anywhere</pre><h3>STARK Proof Structure</h3><p>A STARK proof consists of:</p><ol><li><strong>Execution trace commitment</strong> — Merkle root of the computation’s intermediate states</li><li><strong>Constraint polynomial commitment</strong> — proves trace satisfies the program’s rules</li><li><strong>FRI proof</strong> — proves the constraint polynomial has low degree</li><li><strong>Merkle decommitments</strong> — authentication paths for queried positions</li></ol><pre>STARK proof size ≈ (security_parameter × log²(circuit_size)) × hash_size<br>For 128-bit security, 1M gate circuit: ≈ 100-300 KB</pre><p>This is 500–1500x larger than Groth16. But the verifier needs no trusted setup, no pairing operations, and the system resists quantum attacks.</p><h3>Cairo: Programming for STARKs</h3><p>StarkWare’s production STARK system uses <strong>Cairo</strong> — a language specifically designed to compile to STARK-provable execution traces:</p><pre>// Cairo — STARK-native language<br>// Prove you know x, y such that x² + y² = z<br>%builtins output<br>from starkware.cairo.common.math import assert_nn<br>func main(output_ptr : felt*) -&gt; (output_ptr : felt*):<br>    alloc_locals<br>    local x : felt = 3   # private witness<br>    local y : felt = 4   # private witness<br>    local z : felt = 25  # public output<br>    # Constraints: enforced by the STARK prover<br>    assert x * x + y * y = z<br>    # Write public output<br>    assert [output_ptr] = z<br>    return (output_ptr + 1)<br>end</pre><pre># Compile and prove with StarkWare toolchain<br>cairo-compile sum_of_squares.cairo --output sum_of_squares_compiled.json<br>cairo-run --program=sum_of_squares_compiled.json \<br>          --print_output --layout=small \<br>          --trace_file=trace.bin \<br>          --memory_file=memory.bin<br># Generate STARK proof<br>stark_prover --trace=trace.bin --memory=memory.bin --proof=proof.bin<br># Verify (fast - O(log²n) operations)<br>stark_verifier --proof=proof.bin --output=25<br># Verification: OK</pre><h3>STARK Scalability: The Prover Advantage</h3><p>STARKs have a property that pairing-based SNARKs don’t: <strong>quasi-linear prover time</strong>. The prover’s work scales as O(n log² n) where n is the computation size, and critically, the prover can be parallelized efficiently — no sequential dependencies in the FFT and FRI steps.</p><p>This is why StarkEx can prove millions of transactions per day. The prover is fast enough at scale that the larger proof size becomes acceptable.</p><pre>Groth16 prover:   O(n log n)  — sequential, hard to parallelize<br>PLONK prover:     O(n log n)  — somewhat parallelizable<br>STARK prover:     O(n log² n) — highly parallelizable<br>Plonky2 prover:   O(n log n)  — parallelizable + hardware optimized</pre><h3>The FRI Commitment vs KZG Commitment: The Core Trade-off</h3><p>Everything in this article comes down to one substitution: replacing KZG with FRI.</p><p>KZG is compact and fast to verify. FRI is large but quantum-resistant and needs no ceremony. Every design choice in Articles 2–4 vs Articles 5–6 ultimately traces back to this one substitution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*aEgPH62e6jzKZEw3KvQ5_Q.png" /></figure><h3>PQ Outlook</h3><p>All four systems in this article are <strong>plausibly post-quantum safe</strong> — the same designation they carry in the original taxonomy table.</p><p>“Plausibly” is the honest word here. Their security reduces to the collision resistance of hash functions, which is believed to be quantum-resistant. But:</p><ol><li>The security reductions assume the <strong>random oracle model</strong> — the hash function is modeled as a truly random function. Real hash functions (SHA-256, Keccak) are not random oracles, though no attacks are known.</li><li>Post-quantum security of the <em>proof system</em> doesn’t mean the <em>application</em> is quantum safe. If the data being proved (e.g., an ECDSA signature) uses quantum-vulnerable cryptography, the ZKP doesn’t help.</li><li>NIST has not formally standardized any ZK proof system. The post-quantum status of these systems is based on community consensus, not a formal standardization process.</li></ol><p>With those caveats, Ligero, Aurora, Virgo, and zk-STARK represent the state of the art in quantum-resistant ZK proofs available today.</p><h3>What to Remember from This Article</h3><ul><li><strong>The quantum vulnerability</strong> of all previous systems traces to ECDLP — Shor’s algorithm breaks it completely, Grover only halves hash security</li><li><strong>Ligero (2017)</strong> was the quiet pioneer — first hash-based SNARK, MPC-in-the-head technique, O(√n) proof size</li><li><strong>Aurora (2019)</strong> improved to O(log² n) using Reed-Solomon codes and the IOP framework</li><li><strong>Virgo (2020)</strong> used the GKR protocol with hash-based commitments — linear prover time</li><li><strong>zk-STARK (2019)</strong> brought PQ proofs to production scale via FRI and Cairo — powers StarkNet and dYdX</li><li><strong>The core trade-off</strong>: FRI (hash-based) vs KZG (pairing-based) — larger proofs, no setup, quantum-resistant vs tiny proofs, trusted setup, quantum-vulnerable</li><li><strong>Proof sizes</strong> are 500–1500x larger than Groth16 — the price of quantum resistance with current technology</li></ul><p>Next up: the systems that took these hash-based foundations and made them fast enough to prove arbitrary programs — without writing a single circuit.</p><p><em>Article 6: Nova, Plonky2, Plonky3, and SP1 — Folding Schemes and the zkVM Era</em></p><p><strong>References</strong></p><ul><li>Ames, Hazay, Ishai, Venkitasubramaniam — “Ligero: Lightweight Sublinear Arguments Without a Trusted Setup” (CCS 2017)</li><li>Ben-Sasson, Chiesa, Riabzev, Spooner, Virza, Ward — “Aurora: Transparent Succinct Arguments for R1CS” (EUROCRYPT 2019)</li><li>Zhang, Xie, Zhang, Song — “Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof” (IEEE S&amp;P 2020)</li><li>Ben-Sasson, Bentov, Horesh, Riabzev — “Scalable, transparent, and post-quantum secure computational integrity” (ePrint 2018)</li><li>Ishai, Kushilevitz, Ostrovsky, Sahai — “Zero-Knowledge from Secure Multiparty Computation” (STOC 2007)</li><li>StarkWare — “ethSTARK Documentation” (2021)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d25504e0fc7d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[No Trusted Setup: What Bulletproofs, Halo, and Halo2 Actually Cost You — Article 4 of the ZKP…]]></title>
            <link>https://medium.com/@umitaygul/no-trusted-setup-what-bulletproofs-halo-and-halo2-actually-cost-you-article-4-of-the-zkp-eb1266a0ebe1?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/eb1266a0ebe1</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Mon, 13 Apr 2026 07:56:03 GMT</pubDate>
            <atom:updated>2026-04-13T07:56:03.657Z</atom:updated>
            <content:encoded><![CDATA[<h3>No Trusted Setup: What Bulletproofs, Halo, and Halo2 Actually Cost You — Article 4 of the ZKP Systems Series</h3><p>By 2018, the question had shifted. Groth16 proved you could make SNARKs small. PLONK proved you could make the setup universal. But a harder question remained: <em>do you need a trusted setup at all?</em></p><p>The answer, it turned out, was no. But “no trusted setup” doesn’t mean “free.” Every system that eliminates the ceremony pays somewhere else — in proof size, in verification time, in prover complexity, or in the cryptographic assumptions it relies on.</p><p>This article covers three systems that each answered “no trusted setup” differently. Bulletproofs paid in verification time. Halo paid in prover complexity but unlocked something new: recursive proof composition. Halo2 combined Halo’s insight with PLONK’s arithmetization to produce the system that now powers Zcash, Scroll, and the Ethereum Foundation’s research stack.</p><h3>Why “No Trusted Setup” Is Hard</h3><p>To understand what these systems are fighting against, recall what a trusted setup gives you.</p><p>In KZG-based systems (Groth16, PLONK, Marlin), the setup encodes a secret value τ into elliptic curve points: [τ]₁, [τ²]₁, ..., [τⁿ]₁. The prover uses these to commit to polynomials. The verifier checks commitments against them. The whole system works because τ is unknown — you can&#39;t reverse-engineer the polynomial from its commitment.</p><p>The trusted setup <em>creates</em> this unknown τ. If you want to eliminate the setup, you need a different way to get the same property: a commitment scheme where the prover can&#39;t know the &quot;evaluation point&quot; used to check their polynomial.</p><p>Two approaches emerged:</p><p><strong>Discrete log based (no pairing):</strong> Use the hardness of the discrete log problem directly, without pairings. The commitment is binding because computing discrete logs is hard, not because a secret τ was destroyed.</p><p><strong>Hash based:</strong> Use collision-resistant hash functions. The “evaluation point” is derived from the proof transcript itself via the Fiat-Shamir heuristic — it’s public, but the prover can’t predict it before committing.</p><p>Bulletproofs took the first path. Halo and Halo2 refined it. STARKs and Plonky2 (Article 5) took the second.</p><h3>Bulletproofs (2018): Eliminating the Setup for Range Proofs</h3><p><strong>Paper:</strong> “Bulletproofs: Short Proofs for Confidential Transactions and More” <strong>Authors:</strong> Bünz, Bootle, Boneh, Poelstra, Wuille, Maxwell <strong>Published:</strong> IEEE S&amp;P 2018</p><p>Bulletproofs was built for a specific problem: <strong>range proofs</strong>. In a confidential transaction system like Monero, you commit to an amount without revealing it — but you need to prove the amount is non-negative (otherwise you could create money from thin air). A range proof proves 0 ≤ v &lt; 2ⁿ without revealing v.</p><p>Before Bulletproofs, range proofs required either a trusted setup or were prohibitively large. Bulletproofs achieved both: no trusted setup, and proofs of size O(log n) — just 674 bytes to prove a 64-bit range.</p><h3>The Inner Product Argument</h3><p>The technical core of Bulletproofs is an <strong>inner product argument</strong>: a protocol that proves the inner product of two committed vectors equals a claimed value, with proof size logarithmic in the vector length.</p><pre>import numpy as np<br># Inner product: &lt;a, b&gt; = sum(a[i] * b[i])<br>def inner_product(a, b):<br>    return sum(x * y for x, y in zip(a, b))<br># Example: prove &lt;a, b&gt; = 11 without revealing a or b<br>a = [1, 2, 3]<br>b = [1, 2, 2]<br>result = inner_product(a, b)<br>print(f&quot;&lt;a, b&gt; = {result}&quot;)  # &lt;a, b&gt; = 11<br># Bulletproofs reduces this proof to O(log n) size<br># via recursive halving of the vectors:<br># Round 1: split [1,2,3] into [1,2] and [3], similarly for b<br># Round 2: split again... after log(n) rounds, vectors have length 1<br># Each round adds 2 curve points to the proof<br># Total proof size: 2 * log2(n) curve points<br>n = len(a)<br>import math<br>proof_elements = 2 * math.ceil(math.log2(n))<br>print(f&quot;Proof size: {proof_elements} curve points for n={n}&quot;)<br># Proof size: 4 curve points for n=3</pre><p>A range proof for v ∈ [0, 2⁶⁴) decomposes into an inner product argument over the 64-bit binary representation of v. The prover commits to the bits, then proves they satisfy the range constraint via inner products.</p><h3>The Verification Cost Problem</h3><p>Here is Bulletproofs’ fundamental trade-off: <strong>verification time is linear in the circuit size</strong>.</p><p>For a range proof, this means verifying a single range proof takes O(n) operations where n is the bit length — acceptable. But for general arithmetic circuits with thousands of gates, linear verification time makes Bulletproofs impractical as a general-purpose SNARK.</p><pre>Groth16:      verify in O(1)  — 3 pairings, regardless of circuit size<br>PLONK:        verify in O(1)  — constant pairings, regardless of circuit size<br>Bulletproofs: verify in O(n)  — grows with circuit size</pre><p>For Monero’s use case — verifying that a transaction amount is in range — this is fine. Amounts are 64 bits. Verification is fast. But proving a full Ethereum transaction with 100,000 gates would require 100,000 verification operations. On-chain, that’s millions of gas.</p><p>This is why Bulletproofs found its niche in <strong>range proofs and confidential transactions</strong>, not general-purpose ZK applications.</p><h3>Bulletproofs in Practice: Monero</h3><p>Monero uses Bulletproofs (and its successor Bulletproofs+) for every confidential transaction. Here’s what that looks like at the application layer:</p><pre># Monero transaction structure (simplified)<br># The actual amount is hidden in a Pedersen commitment<br># The range proof proves amount ∈ [0, 2^64) without revealing it<br>class ConfidentialTransaction:<br>    def __init__(self, amount, blinding_factor):<br>        self.commitment = pedersen_commit(amount, blinding_factor)<br>        # C = amount * G + blinding * H<br>        # Verifier sees C but not amount or blinding_factor<br>        self.range_proof = bulletproof_range(<br>            value=amount,<br>            blinding=blinding_factor,<br>            n_bits=64<br>        )<br>        # Proof that 0 &lt;= amount &lt; 2^64<br>        # Size: ~674 bytes (vs ~6KB for older range proofs)<br>    def verify(self):<br>        return bulletproof_verify(<br>            commitment=self.commitment,<br>            proof=self.range_proof,<br>            n_bits=64<br>        )<br>        # O(64) operations - fast for 64-bit range</pre><p>Bulletproofs+ (2020) reduced proof sizes by a further 96 bytes and improved prover performance. Monero switched to Bulletproofs+ in 2022. Both variants remain the standard for blockchain range proofs.</p><h3>Halo (2019): Recursive Proof Composition Without a Trusted Setup</h3><p><strong>Paper:</strong> “Recursive Proof Composition without a Trusted Setup” <strong>Authors:</strong> Bowe, Grigg, Hopwood (Electric Coin Company) <strong>Published:</strong> ePrint 2019</p><p>Halo solved a problem that was thought to require either a trusted setup or pairing-friendly curves with expensive computation: <strong>recursive proof composition</strong>.</p><p>Recursive proof composition means: a proof that attests to the correctness of another proof. If you can prove “this proof is valid,” you can chain proofs arbitrarily deep — compressing unlimited computation into a single constant-size proof. This is the foundation of zkRollups: one proof summarizes a million transactions.</p><p>Before Halo, recursive composition required:</p><ol><li>A trusted setup (to get efficient SNARKs), or</li><li>Pairing-friendly <em>cycles</em> of elliptic curves, which are expensive to work with</li></ol><p>Halo achieved recursion using <strong>only</strong> the discrete log assumption over <em>ordinary</em> (non-pairing-friendly) elliptic curves. No trusted setup. No exotic curve cycles.</p><h3>The Key Insight: Deferred Verification</h3><p>Halo’s trick is <strong>accumulation</strong> — deferring the expensive part of verification to a later step.</p><p>In standard proof verification, you check everything immediately. In Halo, you accumulate verification checks across many proofs, then check them all at once at the end:</p><pre>Standard verification:<br>  Proof 1 → Verify completely → Accept/Reject<br>  Proof 2 → Verify completely → Accept/Reject<br>  ...<br>  Cost: O(n) total verification work for n proofs<br>Halo accumulation:<br>  Proof 1 → Accumulate check → (not yet verified)<br>  Proof 2 → Accumulate check → (not yet verified)<br>  ...<br>  Final step → Verify all accumulated checks at once<br>  Cost: O(1) amortized verification per proof + one final check</pre><p>The accumulation scheme works because the inner product argument at Halo’s core has a special structure: you can combine multiple opening proofs into a single “accumulated” proof, and checking the accumulated proof is no more expensive than checking one.</p><pre># Conceptual: Halo accumulation<br># Each proof contributes to an accumulator<br># The final check verifies all proofs simultaneously<br>class HaloAccumulator:<br>    def __init__(self):<br>        self.accumulated = initial_accumulator()<br>    def add_proof(self, proof, public_inputs):<br>        &quot;&quot;&quot;<br>        Absorb a new proof into the accumulator.<br>        Cheap: O(1) operations regardless of circuit size.<br>        The full verification is deferred.<br>        &quot;&quot;&quot;<br>        self.accumulated = accumulate(<br>            self.accumulated,<br>            proof,<br>            public_inputs<br>        )<br>        return self.accumulated  # new accumulator state<br>    def final_check(self):<br>        &quot;&quot;&quot;<br>        One expensive check that validates ALL accumulated proofs.<br>        Called once at the end, not per-proof.<br>        &quot;&quot;&quot;<br>        return verify_accumulator(self.accumulated)<br># Usage: verify 1000 proofs with amortized cost<br>acc = HaloAccumulator()<br>for proof, inputs in proofs:          # 1000 proofs<br>    acc.add_proof(proof, inputs)      # cheap: O(1) each<br>result = acc.final_check()            # expensive: once<br>print(f&quot;All 1000 proofs valid: {result}&quot;)</pre><h3>Curve Cycles: The Other Half of Halo</h3><p>Recursive proofs have a subtle problem: to verify a proof <em>inside</em> a circuit (so you can prove the verification was done correctly), the circuit arithmetic must match the curve arithmetic. But elliptic curve operations are expensive to express as circuit constraints over a <em>different</em> curve’s field.</p><p>Halo uses a <strong>cycle of elliptic curves</strong> — two curves where each curve’s base field is the other curve’s scalar field. This lets you switch between curves efficiently during recursive proof steps:</p><pre>Curve 1 (Pallas):  base field = Fp, scalar field = Fq<br>Curve 2 (Vesta):   base field = Fq, scalar field = Fp<br>Prove something on Pallas → the proof involves Fq arithmetic<br>Verify that proof in a Vesta circuit → Vesta&#39;s scalar field IS Fq<br>→ No expensive field emulation needed</pre><p>The Pasta curves (Pallas + Vesta) were specifically designed for Halo and are now the standard for recursive proof systems without pairings.</p><h3>Halo2 (2020): The Production System</h3><p><strong>Repository:</strong> github.com/zcash/halo2 <strong>Authors:</strong> Bowe, Hopwood, et al. (Electric Coin Company) <strong>Released:</strong> 2020, production deployment in Zcash Orchard (2021)</p><p>Halo proved the concept. Halo2 made it production-ready by combining two things:</p><ol><li><strong>Halo’s accumulation scheme</strong> — no trusted setup, recursive composition</li><li><strong>PLONK’s arithmetization</strong> — custom gates, lookup tables, efficient constraint systems</li></ol><p>The result: a system with no trusted setup, recursive proof composition, custom gates, and lookup tables. It’s the most feature-complete transparent SNARK deployed in production.</p><h3>Halo2’s Architecture</h3><pre>Halo2 = PLONK arithmetization<br>      + IPA (Inner Product Argument) polynomial commitment<br>      + Accumulation scheme for recursion<br>      + Pasta curve cycle (Pallas + Vesta)</pre><p>The polynomial commitment scheme is <strong>IPA</strong> (Inner Product Argument, the same technique as Bulletproofs) rather than KZG. This is what eliminates the trusted setup — IPA requires only a random group generator, which is public and verifiable.</p><p>The cost: IPA proofs are larger than KZG proofs for the same polynomial degree. A Halo2 proof is typically 3–10 KB, compared to ~800 bytes for KZG-based PLONK. But you get no trusted setup and recursive composition in exchange.</p><h3>Writing Circuits in Halo2</h3><p>Halo2 uses Rust and has a more complex API than circom — it’s designed for production engineers, not quick prototyping:</p><pre>use halo2_proofs::{<br>    circuit::{Layouter, SimpleFloorPlanner, Value},<br>    plonk::{Circuit, ConstraintSystem, Error},<br>    poly::Rotation,<br>};<br>// Define a circuit that proves knowledge of x where x^2 = y<br>#[derive(Default)]<br>struct SquareCircuit {<br>    x: Value&lt;Fp&gt;,  // private witness<br>}<br>impl Circuit&lt;Fp&gt; for SquareCircuit {<br>    type Config = SquareConfig;<br>    type FloorPlanner = SimpleFloorPlanner;<br>    fn configure(meta: &amp;mut ConstraintSystem&lt;Fp&gt;) -&gt; Self::Config {<br>        let x_col = meta.advice_column();  // private<br>        let y_col = meta.advice_column();  // private (intermediate)<br>        let instance = meta.instance_column(); // public output<br>        // Define the custom gate: y = x * x<br>        meta.create_gate(&quot;square&quot;, |meta| {<br>            let x = meta.query_advice(x_col, Rotation::cur());<br>            let y = meta.query_advice(y_col, Rotation::cur());<br>            // Constraint: x * x - y = 0<br>            vec![x.clone() * x - y]<br>        });<br>        SquareConfig { x_col, y_col, instance }<br>    }<br>    fn synthesize(<br>        &amp;self,<br>        config: Self::Config,<br>        mut layouter: impl Layouter&lt;Fp&gt;,<br>    ) -&gt; Result&lt;(), Error&gt; {<br>        layouter.assign_region(|| &quot;square&quot;, |mut region| {<br>            // Assign witness values<br>            let x_val = region.assign_advice(<br>                || &quot;x&quot;, config.x_col, 0, || self.x<br>            )?;<br>            let y_val = region.assign_advice(<br>                || &quot;y = x^2&quot;, config.y_col, 0,<br>                || self.x.map(|x| x * x)<br>            )?;<br>            Ok(())<br>        })<br>    }<br>}<br>// Generate and verify proof<br>fn main() {<br>    let circuit = SquareCircuit {<br>        x: Value::known(Fp::from(5)),  // x = 5, proving x^2 = 25<br>    };<br>    let public_inputs = vec![Fp::from(25)];  // y = 25<br>    // No trusted setup needed - just a random generator point<br>    let params = ParamsIPA::&lt;EqAffine&gt;::new(8);<br>    let vk = keygen_vk(&amp;params, &amp;circuit).unwrap();<br>    let pk = keygen_pk(&amp;params, vk.clone(), &amp;circuit).unwrap();<br>    // Prove<br>    let proof = create_proof(&amp;params, &amp;pk, &amp;[circuit], &amp;[&amp;[&amp;public_inputs]]);<br>    // Verify - no toxic waste, no ceremony<br>    verify_proof(&amp;params, &amp;vk, &amp;[&amp;[&amp;public_inputs]], &amp;proof);<br>    println!(&quot;Proof verified - no trusted setup required.&quot;);<br>}</pre><h3>Who Uses Halo2</h3><p>Halo2’s production deployment list is substantial:</p><ul><li><strong>Zcash Orchard</strong> — the current Zcash shielded pool, deployed 2021</li><li><strong>Scroll</strong> — Ethereum L2 zkEVM using Halo2 circuits</li><li><strong>Taiko</strong> — another Ethereum L2 with Halo2-based proving</li><li><strong>Ethereum Foundation PSE</strong> — Privacy and Scaling Explorations team uses Halo2 for research</li><li><strong>Polygon Miden</strong> — uses a Halo2-inspired architecture</li></ul><p>The ecosystem also spawned <strong>PSE’s fork of Halo2</strong> which adds KZG as an optional commitment scheme — giving you smaller proofs at the cost of reintroducing a trusted setup. Different applications make different trade-offs.</p><h3>The Three-Way Trade-off, Visualized</h3><p>These three systems represent three different positions on the same trade-off surface:</p><pre>No trusted setup<br>                           ↑<br>                    Halo / Halo2<br>                    (large proofs,<br>                     recursive composition)<br>                           |<br>    Bulletproofs ──────────┼────────── Groth16 / PLONK<br>    (range proofs,         |           (tiny proofs,<br>     linear verify)        |            fast verify,<br>                           |            requires setup)<br>                           ↓<br>                    Trusted setup required</pre><p>There is no system in the top-right corner: tiny proofs, fast verification, no trusted setup, post-quantum safe. Every system in this article makes a compromise. The next article covers the systems that reached toward that corner by abandoning elliptic curves entirely.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/860/1*WsSI_3q4jfsM1Cc4zFFOpw.png" /></figure><h3>PQ Outlook</h3><p><strong>Bulletproofs: Not post-quantum safe.</strong> The inner product argument relies on the hardness of the discrete logarithm problem in elliptic curve groups — broken by Shor’s algorithm. Monero’s confidential transactions would be exposed if a quantum computer could break ECDLP.</p><p><strong>Halo and Halo2: Not post-quantum safe.</strong> Despite using IPA instead of KZG, IPA also relies on ECDLP hardness. The Pasta curve cycle is not pairing-based, but it’s still elliptic curve based. Shor’s algorithm breaks the discrete log on Pallas and Vesta just as effectively as on any other curve.</p><p>The systems in this article are a significant step forward from KZG-based systems — they eliminate trusted setup risk and enable recursion — but they don’t address the quantum threat. For post-quantum recursive proofs, you need hash-based systems like STARKs and Plonky2, which is exactly where we go next.</p><h3>What to Remember from This Article</h3><ul><li><strong>Bulletproofs</strong> eliminated trusted setup for range proofs with O(log n) proof size — but verification scales linearly, limiting it to narrow use cases like Monero</li><li><strong>Halo</strong> achieved recursive proof composition without trusted setup or pairing-friendly curves, using accumulation and the Pasta curve cycle</li><li><strong>Halo2</strong> combined Halo’s accumulation with PLONK’s arithmetization — the most production-deployed transparent SNARK, powering Zcash Orchard, Scroll, and Taiko</li><li><strong>The cost of “no trusted setup”</strong> is always paid somewhere: larger proofs (Halo2), linear verification (Bulletproofs), or slower prover times</li><li><strong>None of these systems are post-quantum safe</strong> — they rely on ECDLP, which Shor’s algorithm breaks</li></ul><p>Next up: the systems that abandon elliptic curves entirely — and what you gain and lose when you do.</p><p><em>Article 5: Ligero, Aurora, Virgo, and zk-STARK — What Makes a Proof Post-Quantum Safe?</em></p><p><strong>References</strong></p><ul><li>Bünz, Bootle, Boneh, Poelstra, Wuille, Maxwell — “Bulletproofs: Short Proofs for Confidential Transactions and More” (IEEE S&amp;P 2018)</li><li>Bowe, Grigg, Hopwood — “Recursive Proof Composition without a Trusted Setup” (ePrint 2019)</li><li>Halo2 Book — <a href="https://zcash.github.io/halo2/">https://zcash.github.io/halo2/</a></li><li>Kudelski Security — “On the Security of Halo2 Proof System” (2024)</li><li>Bünz, Fisch, Szepieniec — “Transparent SNARKs from DARK Compilers” (EUROCRYPT 2020)</li><li>Bootle, Cerulli, Chaidos, Groth, Petit — “Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting” (EUROCRYPT 2016)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eb1266a0ebe1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Universal Setup Race: How Sonic, PLONK, and Marlin Solved Groth16’s Biggest Problem — Article 3…]]></title>
            <link>https://medium.com/@umitaygul/the-universal-setup-race-how-sonic-plonk-and-marlin-solved-groth16s-biggest-problem-article-3-2642075acce7?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/2642075acce7</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Mon, 13 Apr 2026 06:46:47 GMT</pubDate>
            <atom:updated>2026-04-13T06:46:47.560Z</atom:updated>
            <content:encoded><![CDATA[<h3>The Universal Setup Race: How Sonic, PLONK, and Marlin Solved Groth16’s Biggest Problem — Article 3 of the ZKP Systems Series</h3><p>In 2019, three independent research teams — working simultaneously, largely unaware of each other — published solutions to the same problem that had haunted SNARKs since Pinocchio: the circuit-specific trusted setup.</p><p>Sonic appeared in January. PLONK in August. Marlin in November.</p><p>All three eliminated the need to run a new trusted setup ceremony for every new circuit. All three were published within the same calendar year. And they did it through completely different approaches — which is why understanding all three, rather than just the winner, reveals something important about how proof system design actually works.</p><h3>The Problem, One More Time</h3><p>Groth16’s proving and verification keys are baked to one specific circuit. Change a single gate, and the keys are invalid — you need a new ceremony. For Zcash, that meant organizing hundreds of participants across multiple continents every time the protocol changed. For a smart contract platform where circuits might be updated monthly, it was simply impossible.</p><p>The dream was a <strong>universal setup</strong>: run the ceremony once, use the resulting parameters for any circuit, forever. The catch — and there’s always a catch in cryptography — is that universality costs something. The question was: how much?</p><h3>Sonic (2019): The Proof of Concept</h3><p><strong>Paper:</strong> “Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings” <strong>Authors:</strong> Maller, Bowe, Kohlweiss, Meiklejohn <strong>Published:</strong> January 2019, ACM CCS</p><p>Sonic was first. It proved that a universal, updatable trusted setup was <em>possible</em> — and that it didn’t require any fundamentally new cryptographic assumption. It used the same pairing-based machinery as Groth16, just restructured.</p><p>The key insight was separating the <strong>structured reference string (SRS)</strong> into two parts:</p><pre>Universal SRS = Powers of tau (reusable for any circuit)<br>               + Circuit-specific component (small, derived from universal SRS)</pre><p>The powers of tau — [τ¹]₁, [τ²]₁, …, [τⁿ]₁ — are circuit-agnostic. Once you have them, deriving parameters for a new circuit is cheap and doesn’t require a new ceremony. The toxic waste lives only in the universal part, generated once.</p><p><strong>Updatability</strong> was Sonic’s other contribution. Anyone can contribute additional randomness to the SRS after the fact, without invalidating existing proofs. If the original ceremony was compromised, a subsequent honest contributor fixes it. Formally: the SRS is secure as long as <em>at least one</em> contributor was honest, across the entire history of contributions.</p><pre>// Sonic (conceptually) — same circuit language, different backend<br>// The circuit itself is unchanged; the setup is what&#39;s universal<br>pragma circom 2.0.0;<br>template Square() {<br>    signal input x;<br>    signal input y;<br>    y === x * x;<br>}<br>component main {public [y]} = Square();<br>// With Groth16: run ceremony for THIS circuit specifically<br>// With Sonic:   use universal SRS, derive circuit params cheaply</pre><p><strong>The problem:</strong> Sonic’s prover was slow. Painfully slow. Roughly 20x slower than Groth16 for equivalent circuits. The proof size was also larger — around 1.5 KB versus Groth16’s 200 bytes. Sonic proved universality was achievable but left performance on the table.</p><p>The field had its proof of concept. Now it needed something practical.</p><h3>PLONK (2019): The System That Won</h3><p><strong>Paper:</strong> “PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge” <strong>Authors:</strong> Gabizon, Williamson, Ciobotaru <strong>Published:</strong> August 2019 (ePrint)</p><p>PLONK is, by any measure, the most influential SNARK of the 2019–2020 era. It’s the system that made zkEVMs practical, powers Aztec Network, underlies Halo2, and spawned a family of variants (UltraPLONK, TurboPLONK, HyperPLONK) that define the current landscape.</p><p>Its name is a tortured acronym — “Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge” — that the authors cheerfully admit was constructed after the fact to fit the word. What matters is what it does.</p><h3>PLONK’s Core Innovation: A New Arithmetization</h3><p>Pinocchio and Groth16 use <strong>R1CS</strong> (Rank-1 Constraint Systems) as their circuit representation. Every gate is one multiplication with two inputs and one output. This maps cleanly to QAPs.</p><p>PLONK introduced a different arithmetization based on <strong>gates</strong> with a more flexible structure:</p><pre>q_L · a + q_R · b + q_O · c + q_M · (a·b) + q_C = 0</pre><p>where a, b, c are wire values and q_L, q_R, q_O, q_M, q_C are <strong>selector polynomials</strong> that determine what kind of gate this is. By setting different selector values, one gate type handles addition, multiplication, or arbitrary linear combinations.</p><p>In circom (which compiles to PLONK-compatible representations via snarkjs):</p><pre>pragma circom 2.0.0;<br>// A slightly more complex example: prove you know x, y such that<br>// x² + y² = z, without revealing x or y<br>template SumOfSquares() {<br>    signal input x;<br>    signal input y;<br>    signal input z;<br>    signal x_sq;<br>    signal y_sq;<br>    // Gate 1: x_sq = x * x<br>    x_sq &lt;== x * x;<br>    // Gate 2: y_sq = y * y<br>    y_sq &lt;== y * y;<br>    // Gate 3: x_sq + y_sq = z (linear constraint - no multiplication needed)<br>    z === x_sq + y_sq;<br>}<br>component main {public [z]} = SumOfSquares();</pre><pre># Compile and setup with PLONK backend<br>circom sumofsquares.circom --wasm --r1cs<br># PLONK uses a universal SRS - this powers-of-tau file works for ANY circuit<br># (as long as the circuit has fewer gates than the SRS supports)<br>snarkjs plonk setup sumofsquares.r1cs pot12_final.ptau circuit_plonk.zkey<br>snarkjs zkey export verificationkey circuit_plonk.zkey vk_plonk.json<br># Generate witness: x=3, y=4, z=25 (3²+4²=25)<br>echo &#39;{&quot;x&quot;: &quot;3&quot;, &quot;y&quot;: &quot;4&quot;, &quot;z&quot;: &quot;25&quot;}&#39; &gt; input.json<br>node sumofsquares_js/generate_witness.js sumofsquares_js/sumofsquares.wasm input.json witness.wtns<br># Prove and verify<br>snarkjs plonk prove circuit_plonk.zkey witness.wtns proof_plonk.json public_plonk.json<br>snarkjs plonk verify vk_plonk.json public_plonk.json proof_plonk.json<br># snarkJS: OK!</pre><h3>The Permutation Argument</h3><p>PLONK’s other key innovation is how it enforces <strong>wire connectivity</strong> — the constraint that the output of one gate is the same value as the input of another gate that uses it.</p><p>In R1CS, this is handled implicitly by the witness vector. In PLONK, it requires an explicit <strong>permutation argument</strong>: a cryptographic proof that certain wire values are permutations of each other.</p><p>This sounds more expensive, but PLONK’s permutation argument is remarkably efficient — it adds only a constant number of group elements to the proof regardless of circuit size. The result: PLONK proofs are around 800 bytes, larger than Groth16 but manageable.</p><h3>Custom Gates: Where PLONK Becomes Powerful</h3><p>The most important feature of PLONK’s design is that the selector polynomials q_* can be <em>customized</em>. Instead of being limited to addition and multiplication, you can define new gate types that encode complex operations in a single gate.</p><p><strong>TurboPLONK</strong> (Aztec’s extension) added custom gates for elliptic curve operations, reducing the gate count for common cryptographic operations by 2–5x. <strong>UltraPLONK</strong> added lookup tables — a gate type that proves a value exists in a precomputed table, massively efficient for operations like range checks and bitwise operations.</p><pre>Standard PLONK:    SHA-256 hash ≈ 28,000 gates<br>UltraPLONK:        SHA-256 hash ≈ 8,000 gates  (with lookup tables)</pre><p>This extensibility is why PLONK won the adoption race. It wasn’t just a better system — it was a <em>platform</em> that kept getting better as teams added custom gates for their specific use cases.</p><h3>PLONK vs Groth16: The Practical Trade-off</h3><pre>Groth16:  200 bytes, 3 pairings, circuit-specific setup<br>PLONK:    800 bytes, 24 pairings, universal setup</pre><p>For a zkEVM proving millions of transactions, the universal setup is worth the 4x proof size increase many times over. You update the EVM opcode semantics? No new ceremony. You fix a bug in the circuit? No new ceremony. The engineering flexibility is transformative.</p><h3>Marlin (2020): The R1CS Champion</h3><p><strong>Paper:</strong> “Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS” <strong>Authors:</strong> Chiesa, Hu, Maller, Mishra, Spooner, Vesely <strong>Published:</strong> November 2019 (ePrint), EUROCRYPT 2020</p><p>PLONK changed the arithmetization. Marlin asked a different question: <em>can we keep R1CS — the representation everyone already knows — and still get universality?</em></p><p>The answer was yes, using a technique called <strong>algebraic holographic proofs (AHPs)</strong>. Where PLONK encodes constraints as polynomial identities over gates, Marlin encodes R1CS constraints as polynomial identities over the <em>constraint indices themselves</em>, evaluated using the <strong>sumcheck protocol</strong>.</p><p>The sumcheck protocol is a powerful tool from interactive proofs: it allows a prover to convince a verifier that the sum of a polynomial over a large domain equals a claimed value, in logarithmic rounds. Marlin uses it to efficiently prove that the R1CS constraint Az ∘ Bz = Cz holds — where A, B, C are the R1CS matrices and z is the witness.</p><pre># Conceptual: what Marlin is proving at its core<br># R1CS: for matrices A, B, C and witness vector z:<br># (A·z) ∘ (B·z) = C·z  where ∘ is element-wise multiplication<br>import numpy as np<br>def check_r1cs(A, B, C, z):<br>    &quot;&quot;&quot;<br>    Marlin proves this holds without revealing z.<br>    The sumcheck protocol makes this efficient for large circuits.<br>    &quot;&quot;&quot;<br>    Az = A @ z<br>    Bz = B @ z<br>    Cz = C @ z<br>    return np.allclose(Az * Bz, Cz)  # element-wise product<br># Example: x * x = x_squared<br># Witness z = [1, x, x_squared] = [1, 5, 25]<br>z = np.array([1, 5, 25])<br>A = np.array([[0, 1, 0]])   # picks x<br>B = np.array([[0, 1, 0]])   # picks x<br>C = np.array([[0, 0, 1]])   # picks x_squared<br>print(&quot;R1CS satisfied:&quot;, check_r1cs(A, B, C, z))<br># R1CS satisfied: True</pre><h3>Marlin vs Sonic: The 10x Claim</h3><p>The Marlin paper included benchmarks against Sonic showing roughly <strong>10x faster prover time</strong> for equivalent circuits. This was the headline result. The improvement came from:</p><ol><li>Marlin’s AHP requires fewer polynomial evaluations than Sonic’s linear-size polynomial approach</li><li>Marlin’s use of the sumcheck protocol is more cache-friendly and parallelizable</li><li>Marlin’s proof size (~1.2 KB) is smaller than Sonic’s (~1.5 KB)</li></ol><p>Against Groth16, Marlin is still slower — this is unavoidable given universality — but the gap narrowed significantly.</p><h3>Marlin in Production: Aleo</h3><p>The most prominent production deployment of Marlin is <strong>Aleo</strong> — a privacy-focused blockchain where every transaction is proved using Marlin (specifically, a variant called <strong>Marlin+</strong>). Aleo’s programming language Leo compiles down to R1CS, which maps directly onto Marlin’s native constraint format.</p><pre>// Leo (Aleo&#39;s language) — compiles to R1CS → Marlin proof<br>program token.aleo {<br>    record Token {<br>        owner: address,<br>        amount: u64,<br>    }<br>// Prove you own a token and can transfer it - without revealing the amount<br>    transition transfer(token: Token, receiver: address) -&gt; Token {<br>        return Token {<br>            owner: receiver,<br>            amount: token.amount,<br>        };<br>    }<br>}</pre><p>Every transition in Aleo is compiled to an R1CS circuit and proved with Marlin. The universal setup means Aleo can update its standard library circuits without running new ceremonies.</p><h3>Head-to-Head: Sonic vs PLONK vs Marlin</h3><p>The three systems solved the same problem with different tools. Here’s how they compare on the dimensions that matter:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/860/1*H2S8gTr9jGmc_dNr6tcbsQ.png" /></figure><p>The verdict from the market: <strong>PLONK won</strong>. Its custom gate system and constant-time verification gave it a flexibility advantage that mattered more than proof size or prover speed in most applications. Marlin found its niche in R1CS-native environments. Sonic is mostly a historical stepping stone.</p><p>But “PLONK won” understates what happened. PLONK became a <em>platform</em>. Halo2 — Zcash’s production system — is PLONK arithmetization with a different polynomial commitment scheme (IPA instead of KZG). HyperPLONK extends PLONK to multivariate polynomials. Plonky2 combines PLONK with FRI for post-quantum security. The ideas in PLONK proliferated.</p><h3>The KZG Commitment Scheme: The Engine Under All Three</h3><p>One thing Sonic, PLONK, and Marlin share: they all use the <strong>KZG polynomial commitment scheme</strong> (Kate, Zaverucha, Goldberg — 2010) as their cryptographic core.</p><p>A polynomial commitment scheme lets a prover commit to a polynomial f(x) and later prove that f(z) = y for a specific point z, without revealing the polynomial itself. KZG does this with a single group element commitment and a single group element proof:</p><pre># KZG commitment — conceptual<br># tau is the trusted setup parameter (toxic waste)<br># f is the polynomial we&#39;re committing to<br>def kzg_commit(f_coefficients, srs):<br>    &quot;&quot;&quot;<br>    Commit to polynomial f(x) = a₀ + a₁x + a₂x² + ...<br>    using the structured reference string [τ⁰]₁, [τ¹]₁, [τ²]₁, ...<br>    Result: a single elliptic curve point [f(τ)]₁<br>    &quot;&quot;&quot;<br>    commitment = sum(<br>        coeff * srs[i]  # scalar multiplication on curve<br>        for i, coeff in enumerate(f_coefficients)<br>    )<br>    return commitment  # one curve point, hiding f completely<br>def kzg_open(f_coefficients, z, srs):<br>    &quot;&quot;&quot;<br>    Prove that f(z) = y without revealing f.<br>    The quotient polynomial q(x) = (f(x) - f(z)) / (x - z)<br>    must exist if and only if f(z) = y (polynomial remainder theorem).<br>    &quot;&quot;&quot;<br>    y = evaluate_polynomial(f_coefficients, z)<br>    quotient = compute_quotient(f_coefficients, z, y)<br>    proof = commit(quotient, srs)  # one curve point<br>    return y, proof</pre><p>KZG’s security relies on the <strong>discrete log assumption</strong> in pairing-friendly groups. This is what makes all three systems in this article — Sonic, PLONK, Marlin — not post-quantum safe. The commitment scheme itself is the vulnerability.</p><p>When we reach Article 5 (post-quantum systems), we’ll see how replacing KZG with FRI (Fast Reed-Solomon IOP of Proximity) — a hash-based commitment scheme — is what makes STARKs and Plonky2 quantum-resistant.</p><h3>PQ Outlook</h3><p><strong>Sonic, PLONK, and Marlin are not post-quantum safe.</strong></p><p>All three rely on KZG polynomial commitments, which depend on the elliptic curve discrete logarithm assumption. A quantum computer running Shor’s algorithm would break KZG — and with it, the soundness of every system in this article.</p><p>The universal setup doesn’t help here. The issue isn’t the ceremony — it’s the underlying cryptographic primitive. Replacing KZG with a hash-based commitment scheme (like FRI) would give you a PLONK-style system with post-quantum security. This is exactly what <strong>Plonky2</strong> does: PLONK arithmetization + FRI commitment = universal, transparent, and post-quantum safe.</p><p>For production systems today: Sonic, PLONK, and Marlin are safe against classical adversaries for the foreseeable future. For systems with 20+ year security requirements, plan a migration path toward FRI-based or lattice-based backends.</p><h3>What to Remember from This Article</h3><ul><li><strong>Sonic</strong> proved universality was achievable — but was too slow to deploy widely</li><li><strong>PLONK</strong> won the adoption race through custom gates, lookup tables, and constant verification time — it’s now the most influential SNARK architecture</li><li><strong>Marlin</strong> kept R1CS and found its niche in R1CS-native ecosystems like Aleo</li><li><strong>KZG</strong> is the shared cryptographic core — and the shared post-quantum vulnerability</li><li>The real legacy of 2019: PLONK became a <em>platform</em>, not just a system — Halo2, Plonky2, and HyperPLONK all build on its foundations</li></ul><p>Next up: what happens when you want to go further — not just a universal setup, but <em>no setup at all</em>.</p><p><em>Article 4: Bulletproofs, Halo, and Halo2 — What “No Trusted Setup” Actually Costs You</em></p><p><strong>References</strong></p><ul><li>Maller, Bowe, Kohlweiss, Meiklejohn — “Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings” (CCS 2019)</li><li>Gabizon, Williamson, Ciobotaru — “PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge” (ePrint 2019)</li><li>Chiesa, Hu, Maller, Mishra, Spooner, Vesely — “Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS” (EUROCRYPT 2020)</li><li>Kate, Zaverucha, Goldberg — “Constant-Size Commitments to Polynomials and Their Applications” (ASIACRYPT 2010)</li><li>Williamson, Zac — “The PLONK paper” (Aztec blog, 2019)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2642075acce7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Groth16: Why Three Group Elements Is All You Need — Article 2 of the ZKP Systems Series]]></title>
            <link>https://medium.com/@umitaygul/groth16-why-three-group-elements-is-all-you-need-article-2-of-the-zkp-systems-series-cd2c0ea534c9?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/cd2c0ea534c9</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[groth16]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Wed, 08 Apr 2026 10:45:57 GMT</pubDate>
            <atom:updated>2026-04-13T06:35:41.596Z</atom:updated>
            <content:encoded><![CDATA[<p>In 2016, Jens Groth published a paper with a deceptively simple title: <em>“On the Size of Pairing-Based Non-interactive Arguments.”</em> The question it asked was almost philosophical: <em>what is the theoretical minimum size of a SNARK proof?</em></p><p>The answer: <strong>3 group elements.</strong></p><p>Two elements in G₁, one in G₂. On the BN254 curve, this compresses to roughly 128 bytes. With standard encoding, around 192–200 bytes. That’s smaller than most HTTP headers. That’s your cryptographic proof that an arbitrary computation executed correctly.</p><p>Eight years later, no pairing-based system has beaten it. Groth16 remains the gold standard for proof size and verification speed — and it powers Zcash, Tornado Cash, Polygon Hermez, and hundreds of production ZK applications. Understanding why it works the way it does is understanding the heart of classical SNARKs.</p><h3>What Pinocchio Left on the Table</h3><p>Recall from Article 1: Pinocchio generated proofs of ~288 bytes and required around 8 pairing operations for verification. For 2013, this was remarkable. But Groth looked at the verification equation and asked a sharper question: <em>how many pairings do we actually need?</em></p><p>A pairing operation is expensive — far more expensive than a scalar multiplication on an elliptic curve. Every pairing in the verification equation costs time and gas (if you’re verifying on Ethereum). Pinocchio’s 8 pairings were not the minimum. Groth proved the minimum is <strong>3</strong>.</p><p>His construction achieves this by being ruthlessly efficient about what information goes into the proof and how the verification equation is structured. The result is a proof that consists of exactly:</p><pre>π = (π_A ∈ G₁,  π_B ∈ G₂,  π_C ∈ G₁)</pre><p>Three points. That’s it. And the verification equation checks all of the QAP constraints in a single pairing product equation:</p><pre>e(π_A, π_B) = e(α, β) · e(∑ aᵢ·(βuᵢ+αvᵢ+wᵢ)/γ, γ) · e(π_C, δ)</pre><p>If you haven’t seen pairing notation before, don’t worry about the symbols. The key intuition is: the verifier checks one equation with 3 pairings, and that single check encodes the correctness of every single gate in your circuit. The compression from “one check per gate” (naïve) to “one check for all gates” (Groth16) is where the magic lives.</p><h3>The Groth16 Proof System — Step by Step</h3><p>Let’s trace exactly what happens when you generate and verify a Groth16 proof.</p><h3>Setup Phase (trusted, circuit-specific)</h3><p>The setup takes your circuit (as a QAP) and a secret value τ (the toxic waste) and produces:</p><ul><li><strong>Proving key (pk)</strong> — everything the prover needs, encoded in elliptic curve points</li><li><strong>Verification key (vk)</strong> — a compact set of curve points the verifier uses</li></ul><pre># Conceptual setup — real implementation uses elliptic curve arithmetic<br># tau is the toxic waste — must be destroyed after setup<br><br>def setup(qap, tau):<br>    # Evaluate QAP polynomials at tau, encode in curve points<br>    # [τ⁰]₁, [τ¹]₁, ..., [τⁿ]₁  - powers of tau in G1<br>    # [τ⁰]₂, [τ¹]₂, ..., [τⁿ]₂  - powers of tau in G2<br>    proving_key = encode_qap_at_tau(qap, tau)<br>    verification_key = compute_vk(qap, tau)<br>    # tau is destroyed here - if it leaks, fake proofs become possible<br>    del tau<br>    return proving_key, verification_key</pre><p>The toxic waste τ must be destroyed. If anyone learns it, they can construct a proof π that satisfies the verification equation for <em>any</em> statement, true or false. This is not a theoretical concern — it&#39;s the reason Zcash organized a multi-party computation ceremony involving hundreds of participants.</p><h3>Prove Phase</h3><p>Given the proving key and a witness (the private inputs), the prover computes three curve points:</p><pre>π_A = α + A(τ) + r·δ          (in G₁)<br>π_B = β + B(τ) + s·δ          (in G₂)  <br>π_C = (H(τ)·T(τ) + L(τ)) / δ + s·π_A + r·π_B - rs·δ   (in G₁)</pre><p>where r and s are fresh random values chosen by the prover (this is what makes the proof zero-knowledge — the randomness hides the witness).</p><p>In practice with snarkjs:</p><pre>import * as snarkjs from &quot;snarkjs&quot;;<br>import { readFileSync } from &quot;fs&quot;;<br>// input.json: { &quot;x&quot;: &quot;5&quot; }  - private witness<br>// circuit.wasm: compiled circuit<br>// circuit_final.zkey: proving key from trusted setup<br>const { proof, publicSignals } = await snarkjs.groth16.fullProve(<br>    JSON.parse(readFileSync(&quot;input.json&quot;)),<br>    &quot;circuit.wasm&quot;,<br>    &quot;circuit_final.zkey&quot;<br>);<br>console.log(&quot;Proof:&quot;, JSON.stringify(proof, null, 2));<br>// {<br>//   &quot;pi_a&quot;: [&quot;12345...&quot;, &quot;67890...&quot;, &quot;1&quot;],   ← π_A in G₁<br>//   &quot;pi_b&quot;: [[&quot;111...&quot;, &quot;222...&quot;],            ← π_B in G₂<br>//            [&quot;333...&quot;, &quot;444...&quot;], [&quot;1&quot;,&quot;0&quot;]],<br>//   &quot;pi_c&quot;: [&quot;555...&quot;, &quot;666...&quot;, &quot;1&quot;]         ← π_C in G₁<br>// }<br>console.log(&quot;Public signals:&quot;, publicSignals);<br>// [&quot;25&quot;]  ← y = x² = 25, the public output</pre><p>The proof is exactly 3 curve points. The public signals are the outputs the verifier is allowed to see.</p><h3>Verify Phase</h3><p>Verification checks the pairing equation using only the verification key and the proof — no witness required:</p><pre>const vKey = JSON.parse(readFileSync(&quot;verification_key.json&quot;));<br>const isValid = await snarkjs.groth16.verify(vKey, publicSignals, proof);<br>console.log(&quot;Valid:&quot;, isValid); // true<br>// What&#39;s happening under the hood:<br>// e(π_A, π_B) === e(α, β) · e(vk_input, γ) · e(π_C, δ)<br>// This is checked using the BN254 pairing - 3 operations total</pre><p>On modern hardware this takes under 2ms. On Ethereum, verifying a Groth16 proof costs approximately 200,000–250,000 gas — affordable for high-value transactions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*vcM6HiegnblER8k5U-dMaQ.png" /></figure><h3>The Trusted Setup Problem, Made Concrete</h3><p>Groth16’s setup is circuit-specific. This means: change one line of your circuit, do a new ceremony.</p><p>To understand why this is painful in practice, consider what Zcash went through:</p><p><strong>Sprout ceremony (2016):</strong> 6 participants, each ran the setup independently, destroyed their toxic waste. The catch: if even one of the 6 had been malicious and kept their share, they could forge Zcash transactions indefinitely.</p><p><strong>Sapling ceremony (2018):</strong> When Zcash upgraded to a more efficient circuit, they needed a completely new ceremony. This time, ~90 participants from around the world. It took months to coordinate.</p><p><strong>Orchard (2021):</strong> Zcash switched to Halo2 — partly to escape this ceremony requirement entirely.</p><p>The ceremony overhead is why Groth16 is best suited for <em>stable, long-lived circuits</em> — applications that don’t change often. For anything that needs to evolve rapidly, the circuit-specific setup is prohibitive.</p><h3>Why Groth16 Is Still Unbeaten on Proof Size</h3><p>Here is the fundamental tension in SNARK design:</p><p><strong>Universality costs size.</strong> PLONK, Marlin, and other universal systems do one setup for all circuits. But their proofs are larger — typically 9–15 curve points instead of 3. The extra points carry information about <em>which circuit</em> is being proved.</p><p><strong>Groth16 bakes the circuit into the setup.</strong> Because the proving and verification keys are tailored to one specific circuit, the proof itself needs to carry less information. The setup has already encoded everything circuit-specific.</p><p>This is the fundamental reason Groth16 proofs are smaller. It’s not a clever trick — it’s an unavoidable information-theoretic trade-off. Universal systems pay in proof size for what they gain in setup flexibility.</p><p>The numbers in practice:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/740/1*qNSZIC7JY5yH_OmP-xZYtw.png" /></figure><p>Groth16 wins on size and verification cost. It loses on setup flexibility and post-quantum security.</p><h3>Groth16 on Ethereum: A Real Verifier</h3><p>One of Groth16’s great practical advantages is that its verification equation maps cleanly onto the EVM’s ecPairing precompile. This makes on-chain verification genuinely affordable.</p><p>Here’s a real Solidity verifier (auto-generated by snarkjs):</p><pre>// SPDX-License-Identifier: MIT<br>pragma solidity ^0.8.0;<br>contract Groth16Verifier {<br>    // Verification key - hardcoded from the trusted setup<br>    uint256 constant alphax = 0x1234...;<br>    uint256 constant alphay = 0x5678...;<br>    // ... (vk elements)<br>    function verifyProof(<br>        uint[2] memory a,      // π_A<br>        uint[2][2] memory b,   // π_B<br>        uint[2] memory c,      // π_C<br>        uint[1] memory input   // public signals<br>    ) public view returns (bool) {<br>        // Checks: e(π_A, π_B) = e(α,β) · e(vk·input, γ) · e(π_C, δ)<br>        // Using EVM ecPairing precompile (address 0x08)<br>        return _pairingCheck(a, b, c, input);<br>    }<br>}</pre><p>The gas cost breakdown for Ethereum verification:</p><ul><li>ecPairing precompile: 45,000 base + 34,000 per pair × 3 pairs = <strong>147,000 gas</strong></li><li>Input encoding and scalar mul: ~50,000 gas</li><li><strong>Total: ~200,000 gas</strong> — roughly $0.50–2.00 at typical gas prices</li></ul><p>This is why Groth16 dominates privacy-preserving DeFi applications: the on-chain verification cost is practical.</p><h3>Building and Running a Full Groth16 Proof</h3><p>Here is a complete, runnable example from zero to verified proof:</p><pre># Prerequisites: node, snarkjs, circom<br># 1. Write the circuit<br>cat &gt; square.circom &lt;&lt; &#39;EOF&#39;<br>pragma circom 2.0.0;<br>template Square() {<br>    signal input x;<br>    signal input y;<br>    y === x * x;<br>}<br>component main {public [y]} = Square();<br>EOF<br># 2. Compile circuit to wasm + r1cs<br>circom square.circom --wasm --r1cs<br># 3. Download the Powers of Tau (pre-existing ceremony, reusable)<br>snarkjs powersoftau new bn128 12 pot12_0000.ptau<br>snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name=&quot;contributor&quot;<br>snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau<br># 4. Circuit-specific setup (this is the ceremony)<br>snarkjs groth16 setup square.r1cs pot12_final.ptau circuit_0000.zkey<br>snarkjs zkey contribute circuit_0000.zkey circuit_final.zkey --name=&quot;contributor&quot;<br>snarkjs zkey export verificationkey circuit_final.zkey verification_key.json<br># 5. Generate witness: x=5, y=25<br>echo &#39;{&quot;x&quot;: &quot;5&quot;, &quot;y&quot;: &quot;25&quot;}&#39; &gt; input.json<br>node square_js/generate_witness.js square_js/square.wasm input.json witness.wtns<br># 6. Generate proof<br>snarkjs groth16 prove circuit_final.zkey witness.wtns proof.json public.json<br># 7. Verify<br>snarkjs groth16 verify verification_key.json public.json proof.json<br># snarkJS: OK!<br># 8. Export Solidity verifier<br>snarkjs zkey export solidityverifier circuit_final.zkey verifier.sol</pre><p>The proof in proof.json will be around 800 bytes of JSON encoding 3 curve points. The underlying cryptographic data is ~200 bytes.</p><h3>The Generic Group Model: Groth16’s Security Assumption</h3><p>Groth16’s security is proven in the <strong>generic group model (GGM)</strong> — a model where the adversary can only perform group operations through an oracle, without exploiting any specific structure of the group.</p><p>This is a stronger assumption than “standard model” security, and it’s a legitimate point of criticism. The GGM means the security proof doesn’t account for potential algebraic structure in specific curve implementations that an adversary might exploit.</p><p>In practice, no attacks exploiting this gap have been found for Groth16 over BN254 or BLS12–381. But it’s worth knowing: Groth16’s security proof is not unconditional — it assumes the adversary cannot perform non-generic group operations.</p><p>More recent systems like PLONK use the <em>algebraic group model (AGM)</em>, a slightly weaker but cleaner assumption. This is one of several reasons researchers prefer newer systems for new designs, even though Groth16 remains practical.</p><h3>PQ Outlook</h3><p><strong>Groth16 is not post-quantum safe.</strong></p><p>The entire system rests on two assumptions:</p><ol><li><strong>Elliptic curve discrete logarithm (ECDLP)</strong> — broken by Shor’s algorithm</li><li><strong>Bilinear pairing hardness</strong> — also broken by quantum attacks on the underlying groups</li></ol><p>The verification equation e(π_A, π_B) = e(α, β) · ... cannot be made quantum-resistant without replacing pairings entirely. There is no &quot;parameter upgrade&quot; that saves Groth16 in a post-quantum world — it would require a complete redesign of the proof system.</p><p>NIST’s 2024 post-quantum standards include lattice-based and hash-based schemes, but no pairing replacement. For applications with long-term security requirements, Groth16 proofs generated today may need to be reverified under a PQ-safe system in the future.</p><p>The practical timeline: most cryptographers estimate 10–20 years before quantum computers capable of breaking 256-bit ECDLP exist at scale. Groth16 is safe for current deployment, but long-lived systems should plan migration paths toward hash-based alternatives like STARKs or Plonky2.</p><h3>What to Remember from This Article</h3><ul><li>Groth16 achieves the <strong>theoretical minimum</strong> for pairing-based SNARKs: 3 group elements</li><li>The <strong>circuit-specific setup</strong> is the price you pay for that minimum — universality always costs more bytes</li><li><strong>Verification is 3 pairings</strong> — fast enough for on-chain use at ~200,000 gas on Ethereum</li><li><strong>Security relies on ECDLP and pairings</strong> — not quantum-resistant</li><li>The system is mature, audited, and production-ready — use it for stable circuits where proof size and verification cost matter most</li></ul><p>Next up: the three systems that raced to solve the one thing Groth16 couldn’t — a setup you only have to run once.</p><p><em>Article 3: Sonic, PLONK, and Marlin — The Universal Setup Race (2019–2020)</em></p><p><strong>References</strong></p><ul><li>Groth — “On the Size of Pairing-Based Non-interactive Arguments” (EUROCRYPT 2016)</li><li>Bowe, Gabizon, Green — “A Multi-Party Protocol for Constructing the Public Parameters of the Pinocchio zk-SNARK” (2017)</li><li>Bellare, Fuchsbauer, Scafuro — “NIZKs with an Untrusted CRS” (2019)</li><li>Parno, Howell, Gentry, Raykova — “Pinocchio: Nearly Practical Verifiable Computation” (IEEE S&amp;P 2013)</li><li>snarkjs documentation — <a href="https://github.com/iden3/snarkjs">https://github.com/iden3/snarkjs</a></li><li>circom documentation — <a href="https://docs.circom.io/">https://docs.circom.io</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cd2c0ea534c9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Pinocchio and the Procedural Era: How the First Practical SNARKs Were Built — Article 1 of the ZKP…]]></title>
            <link>https://medium.com/@umitaygul/pinocchio-and-the-procedural-era-how-the-first-practical-snarks-were-built-article-1-of-the-zkp-aa62cfbcde72?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/aa62cfbcde72</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[pinocchio]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Tue, 07 Apr 2026 10:38:45 GMT</pubDate>
            <atom:updated>2026-04-07T10:38:45.535Z</atom:updated>
            <content:encoded><![CDATA[<h3>Pinocchio and the Procedural Era: How the First Practical SNARKs Were Built — Article 1 of the ZKP Systems Series</h3><p>Before 2013, zero-knowledge proofs existed in theory. Goldwasser, Micali, and Rackoff had proven they were possible back in 1985. But “possible in theory” and “runs on a laptop in under a second” are very different things. The gap between them took nearly three decades to close.</p><p>Pinocchio closed it.</p><p>This article covers the first wave of practical SNARKs — the systems built between 2013 and 2018 that proved the technology could work outside of a whiteboard. They are largely obsolete today, but understanding them is non-negotiable: every modern system is either a direct descendant or a deliberate reaction to what this era built.</p><h3>The Problem Pinocchio Had to Solve</h3><p>To build a SNARK, you need to answer a deceptively hard question: <em>how do you encode an arbitrary computation as something a cryptographic proof system can reason about?</em></p><p>A program is a sequence of operations — additions, multiplications, conditionals, memory reads. Cryptographic proof systems, on the other hand, work over mathematical structures: polynomials, elliptic curves, finite fields. Bridging these two worlds required two key ideas that Pinocchio introduced to practice.</p><h3>Step 1: Arithmetic Circuits</h3><p>The first idea is to represent computation as an <strong>arithmetic circuit</strong> — a directed acyclic graph where wires carry field elements and gates perform addition or multiplication.</p><p>Take a simple computation: y = x² + x + 1</p><p>As an arithmetic circuit:</p><pre>x ──┬──── [×] ──── x²<br>            │               │<br>            └──── [+] ──────┤<br>                            │<br>                 1 ──────── [+] ──── y</pre><p>Every program, no matter how complex, can be flattened into such a circuit. The circuit for SHA-256 has ~28,000 gates. The circuit for a full Ethereum transaction has millions. But the structure is always the same: wires and gates, nothing else.</p><h3>Step 2: Rank-1 Constraint Systems (R1CS)</h3><p>An arithmetic circuit can be further reduced to a <strong>Rank-1 Constraint System (R1CS)</strong> — a set of equations of the form:</p><pre>(a · s) * (b · s) = (c · s)</pre><p>where s is the witness vector (all the values in your circuit), and a, b, c are selector vectors that pick which wires participate in each constraint.</p><p>For our example y = x² + x + 1, the R1CS constraints are:</p><pre>Constraint 1: x * x = x²          →  (pick x) * (pick x) = (pick x²)<br>Constraint 2: x² + x + 1 = y      →  (pick 1) * (pick x²+x+1) = (pick y)</pre><p>In code, a simple R1CS constraint looks like this:</p><pre># R1CS representation for a * b = c<br># Each constraint is a triple of vectors (A, B, C)<br># The witness s must satisfy: (A·s) * (B·s) = C·s</pre><pre>import numpy as np</pre><pre># Witness: [1, x, x_squared, y] for x=3, y=x²=9<br>s = np.array([1, 3, 9, 9])</pre><pre># Constraint: x * x = x_squared<br>A = np.array([0, 1, 0, 0])  # picks x<br>B = np.array([0, 1, 0, 0])  # picks x<br>C = np.array([0, 0, 1, 0])  # picks x_squared</pre><pre>assert np.dot(A, s) * np.dot(B, s) == np.dot(C, s)<br>print(&quot;Constraint satisfied:&quot;, np.dot(A,s), &quot;*&quot;, np.dot(B,s), &quot;=&quot;, np.dot(C,s))<br># Output: Constraint satisfied: 3 * 3 = 9</pre><p>A full program becomes a list of such constraints. Satisfying all of them simultaneously proves the program executed correctly.</p><h3>Step 3: From R1CS to QAP</h3><p>R1CS is the right structure, but it’s not yet something you can build a succinct proof around. Pinocchio’s key insight — following earlier theoretical work by Gennaro, Gentry, Parno, and Raykova — was to convert R1CS into a <strong>Quadratic Arithmetic Program (QAP)</strong>.</p><p>The idea: represent each constraint as a polynomial, evaluated at a specific point. If you know the witness, you can construct a polynomial h(x) such that:</p><pre>A(x) · B(x) - C(x) = h(x) · t(x)</pre><p>where t(x) is a known target polynomial that has roots at every constraint point. If the prover can produce h(x), the verifier can check this equation — without seeing the witness — using <strong>elliptic curve pairings</strong>.</p><p>This is the mathematical core of Pinocchio, and of every pairing-based SNARK that followed. The prover encodes the witness into elliptic curve points (hiding it via the discrete log), and the verifier checks the QAP equation using pairings without ever seeing the raw values.</p><h3>Pinocchio in Practice</h3><p>The Pinocchio paper (Parno, Howell, Gentry, Raykova — IEEE S&amp;P 2013) was the first system to make this practical. Its key numbers:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*iRWFcWDkHdSGGRUWes4GRQ.png" /></figure><p>The bottleneck was the prover — it required expensive elliptic curve exponentiations for every gate in the circuit. A circuit with 10,000 gates took seconds to prove. Not fast, but for the first time, <em>feasible</em>.</p><p>The trusted setup was circuit-specific: a new ceremony for every new program. This was accepted as a necessary evil in 2013. It would become the central problem of the next decade.</p><h3>The Procedural Era Variants (2013–2018)</h3><p>Pinocchio opened a door. Several systems rushed through it, each solving a specific problem with the original design.</p><h3>TinyRAM (2013) and vnTinyRAM (2014)</h3><p>Pinocchio proved computations expressed as arithmetic circuits. But most programs aren’t written as circuits — they’re written as code that runs on a CPU, with memory, branches, and loops.</p><p><strong>TinyRAM</strong> attacked this directly. Instead of converting programs to circuits, it defined a simple CPU architecture (TinyRAM) and built a SNARK that proved execution of arbitrary programs on that CPU. Memory accesses, branches, loops — all handled natively.</p><p>The cost was significant overhead: proving a TinyRAM execution is much more expensive than proving an equivalent arithmetic circuit, because you’re also proving each memory operation is valid. But the programming model was far more natural.</p><p><strong>vnTinyRAM</strong> (2014) extended this with universality — one setup for any TinyRAM program of bounded size. This was the first attempt at what PLONK and Marlin would later solve properly.</p><h3>Geppetto (2015)</h3><p>Pinocchio proved one function at a time. <strong>Geppetto</strong> asked: what if you want to prove several functions share the same inputs or intermediate values?</p><p>The key contribution was <em>multi-function proofs</em> — a single proof that attests to the correct execution of multiple related computations simultaneously. Think proving that a hash was computed correctly AND that the result satisfies some predicate, in one proof.</p><p>Geppetto also introduced <em>verification key reuse</em> — a technique where different functions can share parts of the same trusted setup. This reduced ceremony overhead for programs with shared structure.</p><p>It was a clever optimization, but the underlying architecture was still circuit-specific and pairing-based. The paper’s ideas would be absorbed into later systems; Geppetto as a standalone system is rarely used today.</p><h3>Buffet (2015)</h3><p><strong>Buffet</strong> targeted a different inefficiency: Pinocchio’s prover was equally expensive for every gate, whether that gate appeared once or a million times. For programs with highly repetitive structure — like cryptographic hash functions or loops — this was wasteful.</p><p>Buffet introduced <em>proof composition for repetitive computations</em>: prove one iteration of a loop correctly, then compose proofs for repeated iterations cheaply. It was an early form of recursive proof composition, a technique that would become central to the field five years later with Halo.</p><p>The limitation: Buffet’s composition only worked for a specific class of repetitive programs, not arbitrary recursion. It was a narrow optimization rather than a general solution.</p><h3>ZoKrates and xJsnark: The Tooling Layer</h3><p>By 2018, the academic systems had proven the theory. What was missing was usability — something developers could actually pick up and build with.</p><p><strong>ZoKrates</strong> (2018, Jacob Eberhardt et al.) filled this gap. It’s a high-level programming language and toolchain that compiles down to arithmetic circuits and generates Groth16 proofs. Think of it as the GCC of the SNARK world.</p><p>Here’s the same x² = 25 proof from Article 0, written in ZoKrates:</p><pre># ZoKrates DSL — proof that we know x where x² = 25<br>def main(private field x, field y) -&gt; bool {<br>    assert(x * x == y);<br>    return true;<br>}</pre><p>Compare this to the raw circom version:</p><pre>// circom — same proof, lower level<br>pragma circom 2.0.0;</pre><pre>template Square() {<br>    signal input x;<br>    signal input y;<br>    y === x * x;<br>}<br>component main {public [y]} = Square();</pre><p>ZoKrates is more Python-like; circom is more hardware-description-language-like. ZoKrates handles more of the compilation automatically; circom gives you more control over the circuit structure.</p><p>The ZoKrates workflow:</p><pre># 1. Compile the program to a circuit<br>zokrates compile -i square.zok<br><br># 2. Run the trusted setup (Groth16)<br>zokrates setup<br><br># 3. Compute the witness (x=5, y=25)<br>zokrates compute-witness -a 5 25<br><br># 4. Generate the proof<br>zokrates generate-proof<br><br># 5. Verify<br>zokrates verify<br># Performing verification...<br># PASSED</pre><p>ZoKrates is still actively maintained and widely used for Ethereum-based ZK applications. Its integration with Solidity verifier contracts makes it practical for production smart contract development.</p><p><strong>xJsnark</strong> (2018, Jawurek, Kerschbaum, Lagendijk) took a different approach: a Java-based framework targeting developers already familiar with the JVM ecosystem. xJsnark emphasized <em>circuit optimization</em> — automatically applying techniques like common subexpression elimination and gate merging to reduce circuit size.</p><p>The performance gains were real but the adoption was limited. The Java ecosystem never became dominant in the ZK space, which gravitated toward Rust and TypeScript tooling. xJsnark’s circuit optimization ideas, however, influenced later compilers.</p><h3>What the Procedural Era Got Right (and Wrong)</h3><p>Looking back at 2013–2018 with the benefit of hindsight:</p><p><strong>What it got right:</strong></p><p>The <em>architecture</em> was correct. R1CS, QAP, pairing-based verification — these concepts are still at the core of Groth16, the most-used SNARK today. Pinocchio’s mathematical framework survived essentially intact.</p><p>The <em>separation of concerns</em> between circuit compilation and proof generation was the right abstraction. ZoKrates proved that developer-friendly tooling could sit on top of the cryptographic machinery.</p><p><strong>What it got wrong:</strong></p><p><strong>Circuit-specific trusted setup</strong> was the original sin of the era. Every new program required a new ceremony. In practice this meant ZK applications were nearly impossible to update or iterate on. Zcash’s Powers of Tau ceremony — required every time the Zcash circuit changed — took months to organize.</p><p><strong>Prover performance</strong> remained a serious obstacle. Proving a SHA-256 hash computation took seconds on 2018 hardware. This limited ZK to use cases where proofs were rare and large, not fast and frequent.</p><p><strong>No recursion.</strong> Pinocchio-era systems could not compose proofs. You couldn’t prove that a proof was valid. This meant you couldn’t build incrementally verifiable systems — the kind that would later enable zkRollups.</p><h3>The Bridge to What Came Next</h3><p>The procedural era established what a SNARK had to be. The next era — starting with Groth16 in 2016, then Sonic, PLONK, and Marlin in 2019 — took that foundation and attacked each of its weaknesses in turn.</p><p>Groth16 shrank the proof to 3 group elements. PLONK made the setup universal. Halo eliminated the setup entirely. Nova replaced SNARKs with folding schemes for recursion.</p><p>Every one of those breakthroughs was a direct response to a limitation first identified in Pinocchio.</p><h3>PQ Outlook</h3><p><strong>All systems in this article are not post-quantum safe.</strong></p><p>Pinocchio, TinyRAM, vnTinyRAM, Geppetto, Buffet, ZoKrates, and xJsnark all rely — either directly or via Groth16 — on the hardness of the <strong>elliptic curve discrete logarithm problem (ECDLP)</strong> and <strong>bilinear pairing assumptions</strong>. Both are broken by Shor’s algorithm on a sufficiently large quantum computer.</p><p>The pairing-based verification equation at the core of every QAP-based system:</p><pre>e(π_A, π_B) = e(α, β) · e(vk_x, γ) · e(π_C, δ)</pre><p>…depends entirely on the hardness of computing discrete logs in the pairing groups. A quantum computer would render this check trivially forgeable.</p><p>The procedural era systems have no path to post-quantum security without replacing their cryptographic core — which would mean redesigning them from scratch. In practice, this era’s systems will be retired as quantum threats materialize, replaced by hash-based systems like STARKs, Plonky2, and SP1.</p><h3>What to Remember from This Article</h3><ul><li><strong>R1CS</strong> is the universal intermediate representation — every SNARK starts here</li><li><strong>QAP</strong> converts R1CS into a polynomial divisibility check that pairings can verify</li><li><strong>Trusted setup</strong> was accepted as necessary in 2013; the rest of the decade was spent proving it wasn’t</li><li><strong>ZoKrates</strong> is the only system from this era still in active production use</li><li><strong>The prover performance problem</strong> — too slow for real-time applications — wasn’t solved until Plonky2 in 2022</li></ul><p>Next up: the system that took Pinocchio’s architecture and compressed the proof to its theoretical minimum.</p><p><em>Article 2: Groth16 — Why Three Group Elements Is All You Need</em></p><p><strong>References</strong></p><ul><li>Parno, Howell, Gentry, Raykova — “Pinocchio: Nearly Practical Verifiable Computation” (IEEE S&amp;P 2013)</li><li>Ben-Sasson, Chiesa, Genkin, Tromer, Virza — “SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge” (2013)</li><li>Gennaro, Gentry, Parno, Raykova — “Quadratic Span Programs and Succinct NIZKs without PCPs” (2013)</li><li>Costello, Fournet, Howell, Kohlweiss, Kreuter, Naehrig, Parno, Zahur — “Geppetto: Versatile Verifiable Computation” (IEEE S&amp;P 2015)</li><li>Eberhardt, Tai — “ZoKrates: Scalable Privacy-Preserving Off-Chain Computations” (IEEE Blockchain 2018)</li><li>Ahmed, Jawurek, Kerschbaum — “xJsnark: A Framework for Efficient Verifiable Computation” (IEEE S&amp;P 2018)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=aa62cfbcde72" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Zero-Knowledge Proofs: A Field Guide Before You Get Lost — Article 0 of the ZKP Systems Series]]></title>
            <link>https://medium.com/@umitaygul/zero-knowledge-proofs-a-field-guide-before-you-get-lost-article-0-of-the-zkp-systems-series-073c6b18fd32?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/073c6b18fd32</guid>
            <category><![CDATA[web3]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[computer-science]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Tue, 07 Apr 2026 10:23:06 GMT</pubDate>
            <atom:updated>2026-04-07T10:37:24.690Z</atom:updated>
            <content:encoded><![CDATA[<p>There is a moment in every cryptographer’s education where something clicks that feels almost philosophically impossible: <em>you can convince someone a statement is true without revealing why it’s true.</em></p><p>Not approximately. Not with some information leaked. With <strong>zero</strong> knowledge transferred beyond the fact of truth itself.</p><p>This is the foundation of zero-knowledge proofs (ZKPs) — and once you understand it, you realize the field is not one system but a sprawling family of over 28 distinct proof systems, each making different trade-offs between speed, proof size, trusted setup requirements, and quantum resistance.</p><p>This article is the map. The rest of this series is the territory.</p><h3>The Core Idea — Without the Math</h3><p>Imagine you’re colorblind and I claim I can distinguish red from green. You’re skeptical — how would you know I’m not just guessing?</p><p>Here’s a test: you hold one red ball and one green ball behind your back. Sometimes you swap them, sometimes you don’t. Each round, you bring them forward and ask me: <em>did you swap?</em></p><p>If I can’t actually see color, I’ll be right roughly 50% of the time — pure chance. But if I run this 30 times and answer correctly every time, the probability I’m guessing is (1/2)³⁰ ≈ 1 in a billion. You become statistically convinced I can distinguish colors, <strong>without me ever telling you which ball is which color.</strong></p><p>That’s a zero-knowledge proof. The prover convinces the verifier of a fact. The verifier learns nothing else.</p><h3>Three Properties Every ZKP Must Have</h3><p>Before comparing systems, you need the vocabulary. Every ZKP must satisfy three properties simultaneously:</p><p><strong>Completeness.</strong> If the statement is true and the prover is honest, the verifier will always be convinced. An honest prover never fails.</p><p><strong>Soundness.</strong> If the statement is false, no cheating prover can convince the verifier — except with negligible probability. Lying is computationally infeasible.</p><p><strong>Zero-Knowledge.</strong> The proof reveals nothing beyond the truth of the statement itself. Formally: a simulator with no knowledge of the witness can produce proofs indistinguishable from real ones.</p><p>These three properties are not optional. A system missing any one of them is not a ZKP. The entire 30-year research effort in this field is essentially: <em>how do we build systems that satisfy all three as efficiently as possible?</em></p><h3>The Vocabulary: SNARKs, STARKs, and Arguments</h3><p>You’ll encounter these terms constantly, so let’s be precise.</p><p><strong>zk-SNARK</strong> = Zero-Knowledge <strong>S</strong>uccinct <strong>N</strong>on-Interactive <strong>A</strong>rgument of <strong>K</strong>nowledge</p><p>Breaking it down:</p><ul><li><strong>Succinct</strong> — the proof is tiny (often &lt; 1 KB), and verification is fast regardless of how large the computation was</li><li><strong>Non-interactive</strong> — one message from prover to verifier, no back-and-forth required</li><li><strong>Argument</strong> — soundness holds only against computationally bounded provers (not information-theoretically). This is a weaker guarantee than a “proof”, but it’s sufficient for practice</li><li><strong>Knowledge</strong> — if you can produce a valid proof, you <em>must know</em> the witness. Formalized as <em>knowledge soundness</em>.</li></ul><p><strong>zk-STARK</strong> = Zero-Knowledge <strong>S</strong>calable <strong>T</strong>ransparent <strong>A</strong>rgument of <strong>K</strong>nowledge</p><p>The key differences from SNARKs:</p><ul><li><strong>Scalable</strong> — prover time scales quasi-linearly with computation size, making large computations more practical</li><li><strong>Transparent</strong> — no trusted setup required; all randomness is public</li></ul><p>STARKs trade larger proof sizes (~100 KB vs ~200 bytes for Groth16) for the elimination of trusted setup and post-quantum security. We’ll dedicate a full article to this trade-off.</p><h3>A Minimal Working Example</h3><p>Let’s make this concrete. The classic example: prove you know a value x such that x² = 25, without revealing that x = 5 (or -5).</p><p>Here’s what this looks like in <strong>circom</strong>, the most common circuit language for SNARKs:</p><pre>pragma circom 2.0.0;</pre><pre>template Square() {<br>    signal input x;      // private — the witness<br>    signal input y;      // public — the statement<br>    signal output valid;</pre><pre>    y === x * x;         // the constraint: y must equal x²<br>}</pre><pre>component main {public [y]} = Square();</pre><p>Compile this, run a trusted setup, and you get a proving key and verification key. Then:</p><pre># Generate a proof that you know x where x² = 25<br># x=5 is your private witness, y=25 is the public input<br>snarkjs groth16 fullprove input.json circuit.wasm circuit_final.zkey proof.json public.json</pre><pre># Verify — anyone can do this without knowing x<br>snarkjs groth16 verify verification_key.json public.json proof.json<br># Output: OK</pre><p>The verifier sees only y = 25 and a ~200-byte proof. They learn nothing about x. Yet they&#39;re cryptographically convinced you know it.</p><p>This is the pattern every system in this series follows — the details of <em>how</em> the proof is constructed and verified vary enormously between systems, but the structure is always the same.</p><h3>The Three Axes That Separate Every System</h3><p>This is the core insight that makes the taxonomy map above readable. Every proof system can be positioned on three axes:</p><h3>Axis 1: Trusted Setup (Transparent vs. Not)</h3><p>A trusted setup is a one-time ceremony that generates the proving and verification keys. The ceremony involves secret randomness — often called <strong>toxic waste</strong> — that must be destroyed afterward. If it leaks, an attacker can forge fake proofs that pass verification.</p><pre>Trusted setup required:    Groth16, PLONK, Marlin, Sonic<br>No trusted setup (transparent): STARKs, Bulletproofs, Halo, Ligero, Aurora</pre><p>The classic mitigation is a <strong>multi-party computation (MPC) ceremony</strong>: many participants each contribute randomness, and the toxic waste is only reconstructible if <em>every single participant</em> is malicious. Zcash’s Powers of Tau ceremony involved hundreds of participants. Still, the requirement exists.</p><p>Transparent systems eliminate this entirely by using only public randomness (e.g., hash functions). The trade-off is usually larger proofs or slower verification.</p><h3>Axis 2: Universal vs. Circuit-Specific</h3><p>Early systems (Pinocchio, Groth16) require a fresh trusted setup for every new circuit — every new program you want to prove. Change one line of code, run a new ceremony. This is impractical for anything that evolves.</p><p>Universal systems (PLONK, Marlin, Sonic) do one setup that works for <em>any</em> circuit up to a maximum size. The universality comes with a small overhead in proof size and prover time, but the engineering flexibility is transformative — it’s what made zkEVMs possible.</p><pre>Circuit-specific:  Groth16, Pinocchio, Geppetto<br>Universal:         PLONK, Marlin, Sonic, Halo2, Nova, SP1</pre><h3>Axis 3: Post-Quantum Security</h3><p>This axis is becoming the most important one.</p><p>Classical SNARKs rely on the <strong>hardness of the elliptic curve discrete logarithm problem (ECDLP)</strong>. A sufficiently large quantum computer running <strong>Shor’s algorithm</strong> breaks ECDLP in polynomial time. Every pairing-based SNARK — Groth16, PLONK, Marlin, Bulletproofs — would be broken.</p><p>Post-quantum safe systems rely only on <strong>collision-resistant hash functions</strong>, which are believed to resist quantum attacks (Grover’s algorithm gives only a quadratic speedup, manageable by doubling security parameters).</p><pre># Intuition: why hash-based proofs are quantum-resistant<br># A classical attacker needs O(2^n) to find a hash collision<br># A quantum attacker (Grover) needs O(2^(n/2))<br># Solution: use n=256-bit hashes → quantum attacker needs O(2^128) — still infeasible</pre><pre>import hashlib<br># This is the kind of operation PQ-safe systems build on:<br>data = b&quot;zkp_commitment_to_witness&quot;<br>commitment = hashlib.sha256(data).hexdigest()<br>print(commitment)<br># No quantum algorithm breaks this efficiently</pre><p>PQ-safe systems: <strong>zk-STARK, Ligero, Aurora, Virgo, Zilch, Plonky2, Plonky3, SP1, Hyperbridge</strong></p><p>Not PQ-safe: <strong>Groth16, PLONK, Marlin, Sonic, Bulletproofs, Halo, Halo2, Nova</strong></p><p>NIST finalized its post-quantum cryptography standards in 2024. Notably, <strong>no drop-in replacement for elliptic curve pairings</strong> was standardized — systems relying on them would need fundamental redesigns.</p><h3>The Programming Paradigm Column</h3><p>One often-overlooked dimension: <em>how do you write programs for these systems?</em></p><p>Paradigm Examples What it means Procedural Pinocchio, ZoKrates, xJsnark Write code in a high-level language; a compiler converts to circuits Arithmetic Circuits PLONK, Marlin, Groth16, Bulletproofs Work at the gate level directly — more control, steeper curve Assembly vRAM, zk-STARK Machine-level, maximum generality Object-Oriented Zilch OOP paradigm applied to STARK circuits Rust / General VM SP1, Risc0 Prove arbitrary programs — no circuit writing at all</p><p>The progression here mirrors the history of programming languages: from assembly to high-level code. The zkVM era (SP1, Risc0) is analogous to the invention of compilers — you write normal Rust, the system handles the circuit under the hood.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sydDASyJbrS0qbxttSk1-Q.png" /></figure><h3>The Evolution in Four Waves</h3><p>With the taxonomy map as reference, the field’s history becomes a clear narrative:</p><p><strong>Wave 1 — Proving It’s Possible (2013–2015)</strong> Pinocchio (2013) is the Ur-SNARK — the paper that demonstrated practical zero-knowledge proofs for general computations. TinyRAM, Geppetto, and Buffet followed with optimizations. All circuit-specific, all requiring trusted setups, all procedural. The question was <em>can we do this at all?</em></p><p><strong>Wave 2 — The Transparency Breakthrough (2017–2018)</strong> Ligero (2017) quietly introduced the first post-quantum-safe practical SNARK — hash-based, no trusted setup. Bulletproofs eliminated trusted setup for range proofs (now used in Monero). The question shifted to <em>do we have to trust a ceremony?</em></p><p><strong>Wave 3 — The Universality Race (2019–2020)</strong> Sonic, PLONK, and Marlin all solved circuit-specific setup within a 12-month window. zk-STARKs went public. Halo introduced recursive proof composition without a trusted setup. Groth16 remained fastest for small circuits; PLONK won the flexibility race. The question became <em>how do we scale to arbitrary programs?</em></p><p><strong>Wave 4 — The zkVM Era (2021–present)</strong> Nova introduced folding schemes — a new primitive that avoids SNARKs entirely for incremental computation. Plonky2 hit 100x faster recursion. Plonky3 made it modular. SP1 let you prove arbitrary Rust programs. The question is now <em>how do we make ZK as easy as normal programming?</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*SAddHMS2g75uvPhyQ4-62A.png" /></figure><h3>PQ Outlook — A Template for Every Article</h3><p>Each article in this series ends with this assessment. Establishing the template here:</p><blockquote><strong><em>Post-quantum status:</em></strong><em> Classical SNARKs based on elliptic curve pairings (Groth16, PLONK, Marlin) rely on the hardness of the elliptic curve discrete logarithm problem — broken by Shor’s algorithm on a large quantum computer. Hash-based systems (STARKs, Ligero, Aurora, Plonky2, SP1) rely only on collision resistance — believed quantum-resistant. As of 2024, NIST has not standardized a pairing replacement, meaning pairing-based systems face a fundamental redesign challenge in a post-quantum world.</em></blockquote><h3>What You Should Take Away From This Article</h3><p>The 28 systems in this series are not competing answers to the same question. They’re answers to different questions asked at different moments in the field’s history. Understanding which question each system was answering is the key to understanding why it was designed the way it was.</p><p>By the end of this series, you’ll be able to look at any new proof system announcement and immediately understand: <em>What setup does it require? Is it universal? Does it survive a quantum computer? What’s the prover/verifier trade-off?</em></p><p>That’s the vocabulary. Next up: <strong>the system that started it all.</strong></p><p><em>Article 1: Pinocchio and the Procedural Era — How the First Practical SNARKs Were Built (2013–2018)</em></p><p><strong>References</strong></p><ul><li>Goldwasser, Micali, Rackoff — “The Knowledge Complexity of Interactive Proof Systems” (1985)</li><li>Groth, Sahai — “Efficient Non-interactive Proof Systems for Bilinear Groups” (2008)</li><li>Ben-Sasson et al. — “Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture” (2014)</li><li>Parno et al. — “Pinocchio: Nearly Practical Verifiable Computation” (2013)</li><li>Groth — “On the Size of Pairing-Based Non-interactive Arguments” (2016)</li><li>Bowe, Grigg, Hopwood — “Recursive Proof Composition without a Trusted Setup” (2019)</li><li>Kothapalli, Setty, Tzialla — “Nova: Recursive Zero-Knowledge Arguments from Folding Schemes” (2021)</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=073c6b18fd32" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[BIP 360 and the Quantum Threat to Bitcoin: A Cryptographic Deep Dive]]></title>
            <link>https://medium.com/@umitaygul/bip-360-and-the-quantum-threat-to-bitcoin-a-cryptographic-deep-dive-a551a9214df2?source=rss-6b1a45a6da2e------2</link>
            <guid isPermaLink="false">https://medium.com/p/a551a9214df2</guid>
            <category><![CDATA[bitcoin-news]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[post-quantum-cryptography]]></category>
            <category><![CDATA[quantum-computing]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <dc:creator><![CDATA[Ümit Aygül]]></dc:creator>
            <pubDate>Thu, 02 Apr 2026 05:52:25 GMT</pubDate>
            <atom:updated>2026-04-02T05:52:25.845Z</atom:updated>
            <content:encoded><![CDATA[<p><em>How Pay-to-Merkle-Root fixes the elliptic curve exposure that Taproot silently introduced</em></p><h3>Why This Matters Now</h3><p>Bitcoin’s security has always rested on one assumption: that deriving a private key from a public key is computationally infeasible. For classical computers, this holds. For quantum computers running Shor’s algorithm, it does not.</p><p>Two recent developments from Google make the timeline feel considerably less abstract.</p><p><strong>October 2025 — Quantum Echoes.</strong> Google’s Willow chip ran the <em>Quantum Echoes</em> algorithm — an Out-of-Time-Order Correlator (OTOC) measurement for studying information scrambling in entangled quantum systems — 13,000× faster than the fastest classical supercomputer. This is significant not because OTOCs threaten Bitcoin directly, but because it is the first <em>verifiable</em> demonstration of practical quantum advantage on a real-world physics problem. The hardware is maturing faster than the roadmaps suggested.</p><p><strong>March 30, 2026 — Shor’s algorithm whitepaper.</strong> This one hits closer to home. Google Quantum AI published a whitepaper showing that optimized circuit compilation techniques reduce the resources needed to solve the 256-bit ECDLP to roughly <strong>1,200 logical qubits</strong> and <strong>fewer than 500,000 physical qubits</strong> — an order-of-magnitude reduction from prior estimates. On a sufficiently advanced system, the attack completes in minutes.</p><p>The disclosure methodology itself is telling: rather than publishing the full circuit (which would function as a public attack blueprint), Google validated the resource estimates using a <strong>zero-knowledge proof</strong> — proving the result is correct without revealing the underlying technique. That a major research lab is already thinking in terms of responsible cryptanalysis disclosure is a signal about where the field is heading.</p><p>For context on the two attack models this implies:</p><ul><li><strong>At-rest attacks</strong> target wallets with persistently exposed public keys — address reuse, P2PK outputs, and crucially, all Taproot outputs whose tweaked public key sits in the UTXO set from creation. A slower quantum architecture (ion trap, neutral atom) with days to work has enough time.</li><li><strong>On-spend attacks</strong> target keys revealed during mempool broadcast. Bitcoin’s ~10-minute block window is the adversary’s deadline. Google’s paper notes that fast architectures (superconducting, photonic) could complete the ECDLP computation within that window.</li></ul><p>Google’s own researcher Craig Gidney put a number on it: roughly 10% probability of Q-Day before 2030. That’s not panic territory — but a 10% chance of total key compromise on a $1T+ asset class is not a tail risk you ignore. Google has moved its internal PQC transition deadline to 2029 accordingly.</p><p>BIP 360 — merged into the official Bitcoin Improvement Proposal repository in February 2026 — introduces <strong>Pay-to-Merkle-Root (P2MR)</strong>, a new output type designed to eliminate the most direct quantum attack surface on the network today: the persistent elliptic curve point that Taproot writes on-chain at output creation. To understand <em>why</em> it works, you need to understand what it replaces and exactly where the vulnerability lives.</p><p>This article assumes familiarity with elliptic curve cryptography, Bitcoin’s UTXO model, and basic Taproot mechanics.</p><h3>Part 1: The Cryptographic Foundation Bitcoin Relies On</h3><p>Bitcoin uses <strong>secp256k1</strong>, a specific elliptic curve defined over a prime field:</p><pre>y² = x³ + 7  (mod p)<br>p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F</pre><p>Key generation works as follows:</p><pre># Private key: random scalar<br>k = secrets.randbelow(n)   # n is the curve order</pre><pre># Public key: scalar multiplication on the curve<br>P = k * G                  # G is the generator point</pre><p>The security claim: given P and G, recovering k requires solving the <strong>Elliptic Curve Discrete Logarithm Problem (ECDLP)</strong>. On a classical computer, the best known algorithms (Pollard&#39;s rho, baby-step giant-step) run in O(√n) time — roughly 2^128 operations for secp256k1. Infeasible.</p><h3>What Shor’s Algorithm Does</h3><p>Shor’s algorithm, running on a sufficiently powerful quantum computer, solves the discrete logarithm problem in <strong>polynomial time</strong>:</p><pre>T(Shor) = O((log n)³)</pre><p>For secp256k1 with n ≈ 2^256, that&#39;s roughly O(256³) ≈ 16.7 million quantum operations — orders of magnitude faster than any classical approach. The algorithm works by:</p><ol><li>Converting the ECDLP into a <strong>period-finding problem</strong></li><li>Using the <strong>Quantum Fourier Transform (QFT)</strong> to find that period efficiently</li><li>Using continued fractions to extract the private key k</li></ol><p>The implication: <strong>any on-chain elliptic curve point is a target.</strong> If a public key P is visible on the blockchain, a quantum adversary can compute k = P / G and spend those funds.</p><p>The question then becomes: <em>when does Bitcoin put public keys on-chain?</em></p><h3>Part 2: How Bitcoin Locks and Unlocks Funds</h3><p>Every Bitcoin output is locked with a <strong>scriptPubKey</strong> (locking script). To spend it, you provide a <strong>witness</strong> (unlocking data) that satisfies the script.</p><h3>P2PKH (Legacy)</h3><p>Locking script:</p><pre>OP_DUP OP_HASH160 &lt;hash160(P)&gt; OP_EQUALVERIFY OP_CHECKSIG</pre><p>Spending witness:</p><pre>&lt;sig&gt; &lt;P&gt;</pre><p>Here P (the public key) only appears <strong>at spend time</strong>. The locking script commits to hash160(P), not P itself. The exposure window is short — only the mempool broadcast period before confirmation.</p><h3>P2WPKH (SegWit v0)</h3><p>Same structure, just moved into the witness field. Still: public key only revealed at spend time.</p><h3>P2TR (Taproot, SegWit v1)</h3><p>This is where things change fundamentally.</p><h3>Part 3: The Taproot Commitment Scheme and Its Quantum Flaw</h3><p>Taproot (BIP 341) introduces a dual-path spending structure. A Taproot output commits to:</p><pre>Q = P + t·G</pre><p>where:</p><pre>t = hash_taptweak(P || merkle_root)</pre><p>Q is the <strong>tweaked public key</strong> — a linear combination of the internal key P, the hash-derived scalar t, and the generator G. This Q value is <strong>written directly into the locking script</strong> when the output is created:</p><pre>scriptPubKey: OP_1 &lt;Q&gt;   (32 bytes, x-only encoding)</pre><p>So from the moment the output is created — before any spending ever occurs — a 32-byte elliptic curve point sits on-chain in every full node’s UTXO set. <strong>This is the long-exposure vulnerability.</strong></p><h3>Keypath Spend</h3><p>To spend via keypath, the holder computes the tweaked private key:</p><pre>q = k + t   (mod n)</pre><p>and produces a Schnorr signature:</p><pre># Schnorr signing (BIP 340)<br>r = k_nonce * G          # nonce point<br>e = hash(R || Q || msg)  # challenge<br>s = k_nonce + e * q      # signature scalar</pre><pre>signature = (R.x, s)     # 64 bytes</pre><p>The witness is just:</p><pre>&lt;64-byte Schnorr signature&gt;</pre><p>Elegant and compact. But notice: the verifier only needs Q (already on-chain) and the signature. No additional public key disclosure is needed at spend time — because Q was already there from day one.</p><h3>Script Path Spend</h3><p>For script path, the witness is:</p><pre>&lt;script_inputs&gt; &lt;leaf_script&gt; &lt;control_block&gt;</pre><p>The control block contains the internal key P and the Merkle proof path. This reveals P at spend time, but by then the transaction is being confirmed — the exposure window is minimal.</p><p>The problem is the <strong>keypath path</strong>: Q on-chain from the start, valid elliptic curve point, persistent in the UTXO set indefinitely.</p><h3>The Tweak Doesn’t Help</h3><p>A common misconception: “but Q is tweaked — it&#39;s not the <em>real</em> public key.&quot; This doesn&#39;t matter cryptographically.</p><p>Q = P + t·G is still an elliptic curve point. Shor&#39;s algorithm doesn&#39;t care whether it was generated &quot;cleanly&quot; or as a tweak:</p><pre>Given Q and G, find q such that Q = q·G</pre><p>This is the same ECDLP regardless of how q was constructed. Once you have q = k + t, and since t is deterministically derivable from the public script commitment, recovering k is trivial:</p><pre>k = q - t   (mod n)</pre><h3>Part 4: P2MR — Removing the Elliptic Curve Point Entirely</h3><p>P2MR (BIP 360) makes one structural change: <strong>the locking script commits only to the Merkle root, not to any public key.</strong></p><pre>scriptPubKey: OP_2 &lt;merkle_root&gt;   (32 bytes)</pre><p>merkle_root is a SHA-256 hash — the root of the Tapscript tree. It is <strong>not</strong> an elliptic curve point. Shor&#39;s algorithm is inapplicable.</p><h3>The Merkle Tree Structure</h3><p>The script tree is a binary Merkle tree of <strong>tapleaves</strong>. Each leaf is:</p><pre>leaf_hash = hash_tapleaf(version || script)</pre><p>Internal nodes:</p><pre>def tapbranch(left, right):<br>    a, b = sorted([left, right])  # lexicographic ordering<br>    return hash_tapbranch(a || b)</pre><p>Root:</p><pre>merkle_root = tapbranch(tapbranch(leaf_A, leaf_B), leaf_C)</pre><p>This root is what gets written on-chain. No elliptic curve involved at this stage.</p><h3>Spending a P2MR Output</h3><p>To spend, you must reveal:</p><pre>witness:<br>  &lt;script_inputs&gt;       # data satisfying the leaf script<br>  &lt;leaf_script&gt;         # the actual script being executed<br>  &lt;control_block&gt;       # Merkle proof: path from leaf to root</pre><p>The control_block structure:</p><pre>control_block = leaf_version || merkle_proof_path</pre><p>Verification:</p><pre>def verify_p2mr(scriptPubKey, witness):<br>    leaf_script = witness[-2]<br>    control_block = witness[-1]<br>    <br>    # Recompute the leaf hash<br>    leaf_hash = hash_tapleaf(control_block[0] || leaf_script)<br>    <br>    # Walk up the Merkle tree<br>    computed_root = leaf_hash<br>    for sibling in merkle_proof_path(control_block):<br>        computed_root = tapbranch(computed_root, sibling)<br>    <br>    # Compare against on-chain commitment<br>    assert computed_root == scriptPubKey[2:]  # strip OP_2 prefix<br>    <br>    # Execute the leaf script with remaining witness items<br>    execute(leaf_script, witness[:-2])</pre><p><strong>At no point is an elliptic curve public key committed on-chain.</strong> Public keys may appear <em>inside</em> leaf scripts (e.g., OP_CHECKSIG &lt;P&gt;), but they are only revealed at spend time — the same short-exposure window as P2PKH.</p><h3>What About the Scripts Inside?</h3><p>The leaf scripts still use ECDSA/Schnorr today. P2MR does <strong>not</strong> add post-quantum signatures — it only eliminates the <em>persistent</em> public key exposure. The long-exposure threat is mitigated; the short-exposure threat (quantum computer attacking a key in the mempool window) remains.</p><p>This is intentional and acknowledged in the BIP. Post-quantum signatures (ML-DSA / Dilithium, SLH-DSA / SPHINCS+) are planned as follow-on proposals. P2MR creates the structural foundation they’ll slot into.</p><h3>Part 5: The Hash Function Argument</h3><p>Why is merkle_root safer than Q against quantum attacks?</p><p>Hash functions like SHA-256 are <strong>not</strong> vulnerable to Shor’s algorithm. Shor requires a group structure (integers mod n, or elliptic curve points) to exploit periodicity via QFT. Hash functions have no such algebraic structure.</p><p>The relevant quantum attack on hash functions is <strong>Grover’s algorithm</strong>, which provides a quadratic speedup for preimage search:</p><pre>Classical preimage: O(2^256)<br>Grover preimage:    O(2^128)</pre><p>128-bit quantum security is considered sufficient for the foreseeable future (NIST PQC standards accept 128-bit quantum security as Level 1). Shor drops ECDLP security from 128 bits classical to effectively 0 — that’s the asymmetry that makes the difference.</p><pre>Classical         Quantum (Shor/Grover)<br>ECDLP (256-bit):  ~2^128 ops        ~poly(256) ops     ← catastrophic<br>SHA-256 preimage: ~2^256 ops        ~2^128 ops         ← manageable</pre><h3>Part 6: What P2MR Doesn’t Solve</h3><p>Being precise about the threat model matters:</p><p><strong>Addressed by P2MR:</strong></p><ul><li>Long-exposure attack on Taproot’s keypath (persistent Q on-chain)</li><li>Reduction of EC points in the long-lived UTXO set</li></ul><p><strong>Not addressed by P2MR:</strong></p><ul><li>Short-exposure attack during mempool window (leaf scripts still use ECDSA/Schnorr)</li><li>Existing P2PK outputs (~1.7M BTC) — those have raw public keys on-chain already</li><li>P2PKH/P2WPKH addresses where the same address has been used to receive multiple times (public key revealed on first spend, subsequent inputs are exposed)</li><li>Coins that never move to P2MR — opt-in migration only</li></ul><p><strong>The “harvest now, decrypt later” concern:</strong><br> An adversary can record the entire blockchain today and decrypt exposed keys once they have a capable quantum computer. P2MR only helps for <strong>new outputs</strong> created after adoption.</p><h3>Part 7: The Road Ahead</h3><p>BIP 360 is explicitly designed as Step 1 of a multi-phase quantum hardening:</p><pre>Phase 1 (BIP 360):  Eliminate persistent EC points → P2MR output type<br>Phase 2 (future):   Post-quantum leaf scripts → ML-DSA (Dilithium) opcodes<br>Phase 3 (future):   Address dormant/vulnerable coin policy → separate BIP</pre><p>Dilithium (ML-DSA, NIST FIPS 204) is the likely candidate for Phase 2. It’s a lattice-based scheme where security relies on the <strong>Module Learning With Errors (MLWE)</strong> problem — no group structure exploitable by Shor. Signature sizes are substantially larger (~2.4KB vs 64 bytes for Schnorr), which is why the BIP 360 testnet implementation restores the SegWit witness discount.</p><h3>Summary</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6qR3TVGLwO-W8_s7uoKQWA.png" /></figure><p>The core insight of BIP 360 is simple but consequential: <strong>Taproot’s keypath optimization — writing a tweaked EC point directly into the UTXO set — transformed a short-exposure problem into a long-exposure one.</strong> P2MR reverts that decision, at the cost of slightly larger witnesses, and establishes the structural prerequisite for full post-quantum Bitcoin.</p><p><em>References:</em></p><ul><li><em>BIP 341 (Taproot): Spending Conditions</em></li><li><em>BIP 342 (Tapscript)</em></li><li><em>BIP 340 (Schnorr Signatures)</em></li><li><em>BIP 360: Pay-to-Merkle-Root — Hunter Beast, Ethan Heilman, Isabel Foxen Duke</em></li><li><em>NIST FIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA)</em></li><li><em>Shor, P.W. (1994). Algorithms for quantum computation: discrete logarithms and factoring</em></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a551a9214df2" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>