Introduction

Imagine you finish a billion-step computation and a stranger asks: "Did you really run that correctly?" You could hand over all the inputs and let them rerun it โ€” but that takes another billion steps and exposes every secret input. What if you could hand them a short proof instead, something they could check in seconds, that reveals absolutely nothing beyond the single fact: yes, the computation was done correctly?

That is the promise of a zero-knowledge proof. And zk-STARKs โ€” Scalable Transparent ARguments of Knowledge โ€” are a family of such proofs invented by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev and published in 2018. They have three remarkable properties that set them apart:

  1. Scalable โ€” the proof is tiny (logarithmic in the computation size) and verification is fast even when the underlying computation has trillions of steps.
  2. Transparent โ€” no trusted setup is required. Earlier systems like zk-SNARKs need a one-time ceremony where participants generate "toxic waste" that must be destroyed; if anyone keeps a copy, they can forge proofs. STARKs skip this entirely, using only public randomness.
  3. Post-quantum secure โ€” STARKs rely on hash functions (collision resistance) rather than on discrete logarithms or elliptic curves. The latter are broken by Shor's algorithm; hash functions are not.

The cost? STARK proofs are larger than SNARK proofs โ€” roughly kilobytes versus hundreds of bytes. But as blockchains push toward millions of transactions and quantum computers loom on the horizon, that trade-off is increasingly worth making.

Try It: Polynomial Commitments

The key insight of STARKs is that any computation trace can be encoded as a low-degree polynomial. The prover commits to this polynomial by evaluating it at many random points; the verifier spot-checks a few of those evaluations and runs a low-degree test (FRI). If the polynomial passes, the verifier is convinced the computation was honest โ€” without seeing the inputs.

<p class="hint">A zk-STARK encodes a computation as a low-degree polynomial. The prover evaluates it at random points; the verifier checks a few and runs a low-degree test. A cheating prover cannot fake this without the polynomial shooting to a high degree.</p>
<div class="controls">
  <button id="btn-honest" type="button">Honest prover</button>
  <button id="btn-cheat" type="button" class="ghost">Cheating prover</button>
  <button id="btn-verify" type="button" class="ghost">Verify</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<canvas id="chart" width="560" height="240"></canvas>
<div id="status" class="status"></div>
<div id="details" class="details"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .75rem; line-height: 1.45; }
.controls { display: flex; gap: .45rem; flex-wrap: wrap; margin-bottom: .65rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
canvas { display: block; width: 100%; max-width: 560px; height: auto;
         border: 1px solid #dce3ea; border-radius: 8px; background: #f8fafc; }
.status { font-size: .97rem; font-weight: 600; min-height: 1.5em;
          margin: .55rem 0 .3rem; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.details { font-size: .82rem; color: #555; line-height: 1.5; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// โ”€โ”€ Finite-field arithmetic mod a small prime โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// We work in GF(p) with p = 97 for clarity. A real STARK uses a ~256-bit prime.
const P = 97;
const modP = x => ((x % P) + P) % P;
const addF  = (a, b) => modP(a + b);
const mulF  = (a, b) => modP(a * b);

// Evaluate a polynomial (array of coefficients, lowest degree first) at x in GF(P).
function evalPolyGF(coeffs, x) {
  let result = 0, xp = 1;
  for (const c of coeffs) { result = addF(result, mulF(c, xp)); xp = mulF(xp, x); }
  return result;
}

// Evaluate polynomial over real numbers (for display only).
function evalPolyReal(coeffs, x) {
  let result = 0, xp = 1;
  for (const c of coeffs) { result += c * xp; xp *= x; }
  return result;
}

// Degree of a polynomial (ignoring leading zeros).
function degree(coeffs) {
  let d = coeffs.length - 1;
  while (d > 0 && coeffs[d] === 0) d--;
  return d;
}

function modpow(base, exp, m) {
  let result = 1; base %= m;
  while (exp > 0) {
    if (exp & 1) result = result * base % m;
    base = base * base % m; exp >>= 1;
  }
  return result;
}
const modInv = (a, p) => modpow(a, p - 2, p);

// Lagrange interpolation in GF(P): recover polynomial coefficients from (xs, ys).
function lagrangeCoeffs(xs, ys) {
  const n = xs.length;
  const result = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    let basis = [1], denom = 1;
    for (let j = 0; j < n; j++) {
      if (j === i) continue;
      const factor = [modP(-xs[j]), 1]; // (x - xs[j])
      const next = new Array(basis.length + 1).fill(0);
      for (let a = 0; a < basis.length; a++) {
        next[a]   = addF(next[a],   mulF(basis[a], factor[0]));
        next[a+1] = addF(next[a+1], mulF(basis[a], factor[1]));
      }
      basis = next;
      denom = mulF(denom, modP(xs[i] - xs[j]));
    }
    const scale = mulF(ys[i], modInv(denom, P));
    for (let k = 0; k < basis.length; k++) {
      result[k] = addF(result[k], mulF(basis[k], scale));
    }
  }
  return result;
}

// โ”€โ”€ Polynomial scenario โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Honest: f(x) = xยณ + 2xยฒ + 3x + 5  (degree 3)
// Real values: f(1)=11, f(2)=27, f(3)=59, f(4)=113
// GF(97) values: f(1)=11, f(2)=27, f(3)=59, f(4)=16  (113 mod 97 = 16)
//
// Cheating: prover claims f(2)=60 instead of 27 (tampered output).
// Real display for cheat: (1,11),(2,60),(3,59),(4,113)
// GF(97) cheat evals: [11, 60, 59, 16]
const HONEST_COEFFS = [5, 3, 2, 1]; // 5 + 3x + 2xยฒ + xยณ
const EVAL_POINTS   = [1, 2, 3, 4];
// Real (non-modular) honest values for canvas display
const HONEST_REAL   = EVAL_POINTS.map(x => evalPolyReal(HONEST_COEFFS, x)); // [11,27,59,113]
// GF(97) honest evaluations for cryptographic operations
const HONEST_GF     = EVAL_POINTS.map(x => evalPolyGF(HONEST_COEFFS, x));   // [11,27,59,16]
// Cheat: tamper f(2) from 27 to 60
const CHEAT_REAL    = [11, 60, 59, 113];
const CHEAT_GF      = [11, 60, 59, 16];

// โ”€โ”€ Canvas drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const canvas = document.getElementById('chart');
const ctx    = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
// Domain x in [0.5, 4.5], range y in [0, 130]
const toCanX = x => 45 + (x - 0.5) / 4.0 * (W - 55);
const toCanY = y => H - 22 - (y / 130) * (H - 32);

function drawAxes() {
  ctx.clearRect(0, 0, W, H);
  ctx.fillStyle = '#f8fafc'; ctx.fillRect(0, 0, W, H);
  ctx.strokeStyle = '#dce3ea'; ctx.lineWidth = 1;
  for (let y = 0; y <= 130; y += 20) {
    const cy = toCanY(y);
    ctx.beginPath(); ctx.moveTo(45, cy); ctx.lineTo(W - 8, cy); ctx.stroke();
    ctx.fillStyle = '#aaa'; ctx.font = '10px system-ui';
    ctx.fillText(y, 2, cy + 4);
  }
  for (let x = 1; x <= 4; x++) {
    const cx = toCanX(x);
    ctx.beginPath(); ctx.strokeStyle = '#dce3ea'; ctx.moveTo(cx, 10); ctx.lineTo(cx, H - 22); ctx.stroke();
    ctx.fillStyle = '#aaa'; ctx.font = '10px system-ui';
    ctx.fillText('x=' + x, cx - 10, H - 8);
  }
  ctx.strokeStyle = '#999'; ctx.lineWidth = 1.5;
  ctx.beginPath(); ctx.moveTo(45, H - 22); ctx.lineTo(W - 8, H - 22); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(45, H - 22); ctx.lineTo(45, 10); ctx.stroke();
}

function drawCurveFn(fn, color, dashed) {
  ctx.beginPath(); ctx.strokeStyle = color; ctx.lineWidth = 2.2;
  ctx.setLineDash(dashed ? [5, 3] : []);
  let first = true;
  for (let xf = 0.5; xf <= 4.5; xf += 0.04) {
    const v = fn(xf);
    const cx = toCanX(xf), cy = toCanY(v);
    if (cy < 0 || cy > H + 20) { first = true; continue; }
    if (first) { ctx.moveTo(cx, cy); first = false; } else ctx.lineTo(cx, cy);
  }
  ctx.stroke(); ctx.setLineDash([]);
}

function drawPoints(xs, ys, color, showLabel) {
  for (let i = 0; i < xs.length; i++) {
    const cx = toCanX(xs[i]), cy = toCanY(ys[i]);
    ctx.beginPath(); ctx.arc(cx, cy, 5.5, 0, Math.PI * 2);
    ctx.fillStyle = color; ctx.fill();
    ctx.strokeStyle = '#fff'; ctx.lineWidth = 1.5; ctx.stroke();
    if (showLabel) {
      ctx.fillStyle = color; ctx.font = 'bold 11px system-ui';
      const label = '(' + xs[i] + ', ' + ys[i] + ')';
      const lx = cx + (xs[i] <= 2 ? 8 : -ctx.measureText(label).width - 8);
      ctx.fillText(label, lx, cy - 6);
    }
  }
}

// Real-number Lagrange for display curve
function lagrangeRealFn(xs, ys) {
  const n = xs.length;
  return xval => {
    let sum = 0;
    for (let i = 0; i < n; i++) {
      let L = 1;
      for (let j = 0; j < n; j++) {
        if (j !== i) L *= (xval - xs[j]) / (xs[i] - xs[j]);
      }
      sum += ys[i] * L;
    }
    return sum;
  };
}

// โ”€โ”€ State โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let currentMode = null;

function reset() {
  currentMode = null;
  drawAxes();
  setStatus('', '');
  document.getElementById('details').textContent = '';
  document.getElementById('btn-verify').disabled = true;
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + (cls || '');
}

// โ”€โ”€ Honest prover โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
document.getElementById('btn-honest').addEventListener('click', () => {
  currentMode = 'honest';
  drawAxes();
  drawCurveFn(x => evalPolyReal(HONEST_COEFFS, x), '#1d88e5', false);
  drawPoints(EVAL_POINTS, HONEST_REAL, '#1d88e5', true);
  setStatus('Honest prover: degree-3 polynomial committed at 4 points.', 'info');
  document.getElementById('details').textContent =
    'f(x) = xยณ + 2xยฒ + 3x + 5 โ€” a degree-3 polynomial (low degree). The prover evaluates it at x = 1, 2, 3, 4 and sends those values to the verifier. Press Verify to run the low-degree spot-check.';
  document.getElementById('btn-verify').disabled = false;
});

// โ”€โ”€ Cheating prover โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
document.getElementById('btn-cheat').addEventListener('click', () => {
  currentMode = 'cheat';
  drawAxes();
  // Faint honest curve
  drawCurveFn(x => evalPolyReal(HONEST_COEFFS, x), '#aac4e0', true);
  // Cheat curve via real Lagrange through tampered points
  const cheatFn = lagrangeRealFn(EVAL_POINTS, CHEAT_REAL);
  drawCurveFn(cheatFn, '#e63946', false);
  drawPoints(EVAL_POINTS, CHEAT_REAL, '#e63946', true);
  setStatus('Cheating prover: tampered evaluation at x=2 (27 โ†’ 60).', 'bad');
  document.getElementById('details').textContent =
    'The cheating prover changed f(2) from 27 to 60. The unique degree-3 polynomial through these tampered points differs from the honest one everywhere else. Press Verify to see if a spot-check at a fresh point (x=5) catches the lie.';
  document.getElementById('btn-verify').disabled = false;
});

// โ”€โ”€ Verify (low-degree spot-check) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
document.getElementById('btn-verify').addEventListener('click', () => {
  if (!currentMode) return;
  // Recover polynomial in GF(97) from committed evaluations
  const gfEvals = currentMode === 'honest' ? HONEST_GF : CHEAT_GF;
  const coeffs  = lagrangeCoeffs(EVAL_POINTS, gfEvals);
  const deg     = degree(coeffs);
  // Spot-check at x=5 (not in the original evaluation set)
  const predicted   = evalPolyGF(coeffs, 5);
  const trueHonest  = evalPolyGF(HONEST_COEFFS, 5); // f(5) = 195 mod 97 = 1

  let verdict, cls, detail;
  if (currentMode === 'honest') {
    verdict = fmt('โœ“  Degree test: degree = %deg% โ‰ค 3. Spot-check at x=5: %predicted% = correct (%trueHonest%). Proof accepted!', { deg: deg, predicted: predicted, trueHonest: trueHonest });
    cls = 'ok';
    detail = fmt('The proverโ€™s polynomial has degree 3 (low). The spot-check at x=5 matches the honest computation (f(5) = 195 mod 97 = 1). In a real FRI protocol dozens of such checks are done with cryptographic randomness โ€” each check the prover cannot predict in advance.%predicted%%trueHonest%', { predicted: predicted, trueHonest: trueHonest });
  } else {
    verdict = fmt('โœ—  Spot-check at x=5: prover predicted %predicted%, honest value is %trueHonest%. Proof REJECTED!', { predicted: predicted, trueHonest: trueHonest });
    cls = 'bad';
    detail = fmt('The cheating prover tampered with f(2). The recovered polynomial gives a different answer at x=5 (%predicted% โ‰  %trueHonest%). A single random spot-check exposes the fraud. In a real STARK, the prover cannot know which points the verifier will query โ€” making any tampering detectable with overwhelming probability.', { predicted: predicted, trueHonest: trueHonest });
  }
  setStatus(verdict, cls);
  document.getElementById('details').textContent = detail;
});

document.getElementById('btn-reset').addEventListener('click', reset);

// Init
reset();
Result
Console

Click Honest prover to encode a correct computation as a degree-3 polynomial and sample it at four points. Click Cheating prover to see what happens when someone tampers with one output: the recovered polynomial shifts, and a spot-check at a fresh point catches the lie. The Verify button runs this spot-check โ€” exactly what FRI does in a real STARK.

The Real Complexity

How hard is it to build โ€” and break โ€” a zk-STARK?

  • Security assumption: collision-resistant hash functions. No one has found an efficient algorithm to break SHA-256 or similar; this assumption is believed to hold even against quantum adversaries. By contrast, zk-SNARKs typically rely on the hardness of the discrete logarithm, which Shor's algorithm can solve in polynomial time on a quantum computer.
  • Proof size: O(logโก2n)O(\log ^{2} n), where n is the number of steps in the computation. A SNARK proof is only O(1)O(1) โ€” a fixed constant size โ€” but requires a trusted setup. The logarithmic overhead of STARKs is acceptable at the scales where they are deployed.
  • Verification time: O(logโก2n)O(\log ^{2} n) โ€” fast. The verifier does not re-execute the computation; it only checks a handful of polynomial evaluations.
  • Prover time: O(nlogโกn)O(n \log n) โ€” significantly more work than just running the computation. This is where most STARK engineering effort goes: FFTs over large finite fields, Merkle trees, and Reed-Solomon encodings.
  • The trusted setup problem: zk-SNARKs were introduced around 2012 by Groth, Sahai, and others. Their "common reference string" must be generated in a secure multi-party computation; if any one party is corrupt, all proofs from that system can be forged. STARKs eliminate this entirely โ€” their only "setup" is agreeing on a public hash function.
  • Status: zk-STARKs are a solved, deployed technology (not open or conjectured). The security proof reduces STARK soundness to the collision resistance of the underlying hash. The FRI (Fast Reed-Solomon Interactive Oracle Proof) protocol at their core was analyzed rigorously by Ben-Sasson et al. in 2018.

The bottom line: STARKs trade a somewhat larger proof for the elimination of all trusted parties and resistance to quantum attacks โ€” a bargain that gets better as quantum hardware matures.

Where It Matters

zk-STARKs started as a theoretical breakthrough and have become production infrastructure in under a decade:

  • Blockchain scaling (zkRollups): StarkWare's StarkNet and StarkEx use STARKs to bundle thousands of Ethereum transactions into a single on-chain proof. Dydx processed over $1 trillion in derivatives volume on STARK-backed infrastructure. The proof verifies that all those trades followed the rules โ€” without posting each one to the chain.
  • Verifiable AI inference: proving that a specific neural network model produced a specific output, without revealing the model weights or the input. Companies are beginning to use STARKs here because the computation trace of a transformer forward pass can be arithmetized and proven.
  • Transparent voting: a zk-STARK can prove that a tally was computed correctly over encrypted ballots without a trusted tallying authority and without revealing individual votes.
  • Post-quantum identity: as quantum computers approach, credential systems based on elliptic-curve signatures face replacement. STARK-based schemes (such as those using lattice-based or hash-based signatures inside a STARK) remain secure.
  • The broader zero-knowledge ecosystem: STARKs sit alongside zk-SNARKs and other proof systems. Each trades different parameters โ€” proof size, setup assumptions, quantum resistance โ€” and the field is evolving rapidly toward recursive proofs (a STARK that verifies another STARK) for constant-time verification of unlimited computation.

The unifying theme is verifiable trust without a trusted party โ€” one of the most powerful ideas in modern cryptography.

Conclusion

zk-STARKs answer a question that would have seemed impossible a generation ago: how do you convince a stranger that a trillion-step computation was done honestly, in seconds, with no secrets and no trusted intermediary? The answer is a short list of polynomial evaluations and a hash-function-based consistency check.

The deeper lesson is about the geometry of trust. Classical cryptography lets two parties share a secret. Zero-knowledge proofs let one party convince another of a fact without sharing anything else. STARKs do this at scale, transparently, and in a world where quantum computers are becoming real.

The next time you hear that a blockchain processed a million transactions in a single proof, or that an AI company can prove its model gave a particular answer without revealing the model โ€” that is a STARK (or something very like it) at work. The mathematics of polynomials and hash functions is quietly underpinning a new kind of verifiable trust that requires no leap of faith at all.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/zk-starks/Content licensed under CC BY-NC 4.0.