teddav

@teddav

https://teddav.github.io https://x.com/0xteddav

Joined on Feb 7, 2024

  • From 0 to Bi(ge)nius: field extensions Thanks a lot to Oba, Nuliel, Hyunmin, Nico and Jim for the review ❤️Feel free to DM me on Twitter: @0xteddav if you find mistakes in this article or if you have any question. Binius is a new way to build SNARKs by Benjamin Diamond and Jim Posen (from Irreducible). It uses “towers of binary fields” (yes, it sounds complicated but it should become obvious by the end of this article) and a variation of the Hyperplonk IOP over binary fields, combined with the Brakedown polynomial commitment scheme for better prover efficiency.Here’s the paper: Succinct Arguments over Towers of Binary Fields.If you didn’t understand anything of what I just said, don’t worry. I will explain it all in simple terms so that the proof system is -hopefully- clear by the end of the series 🙏This first part will start with the basics. We’re going to look at what “small fields” are, then we’ll get to field extensions and finally reach the “towers”. Small fields: Goldilocks, Mersenne Big fields (think $>2^{256}$) are used in elliptic-curve-based SNARKs in order to ensure high levels of bit security.On the other hand, hash-based STARKs can afford to use smaller fields (think $2^{64}$ or even $2^{32}$), leading to significant gains in prover efficiency.But the crucial part in verification is sampling a random number r from the field and checking “some” equality at r. If the field is too small, the prover could trick the verifier. That’s where extension fields come in: most of the operations will be done in the small fields while some operations are moved to the larger extension field. We will get into the details later in the article.I’m going to assume that you know what a prime field is. If you don’t, stop here and Google it 🔍What we call “small field” is basically just taking a smaller prime (yes, $2^{64}$ is “small”) and reducing every number modulo that prime.For example, the “Goldilocks field” (I don’t know why it’s named this way) uses $p=2^{64}-2^{32}+1$ while “Mersenne31” uses $p=2^{31}-1$.When doing modular math using these fields, any number will be less than 64 and 31 bits for Goldilocks and Mersenne31, respectively. Why small fields? The idea is simple: make things faster!Generating a ZK proof takes a lot of computational power: due to the modular math operations, to interpolate, and evaluate polynomials. Researchers have been trying to improve that.Small fields speed things up by:
     Like  Bookmark
  • Reed-Solomon Codes: The Math Behind Error Correction and Zero-Knowledge Proofs What are Reed-Solomon codes? What even is a “code” in this context??? That’s the question I kept asking myself. I had no idea what “coding theory” was… yet I kept coming across those “RS codes”. So I decided to dig in. Let’s start with a high level overview before going deeper. I’ll try to keep things simple and avoid copy-pasting the same definitions you see everywhere. From now on, I’ll mostly use “RS” as shorthand for Reed-Solomon codes, because typing it out every time is tiring 😁 The big picture
     Like  Bookmark
  • FRI: Folding Polynomials and Catching Cheaters Introduction FRI (Fast Reed-Solomon Interactive Oracle Proof) is a polynomial commitment scheme. Let's break that down: Polynomial: If you don't know what this is, this article might not be for you… sorry 😕 Commitment Scheme: You choose a value and commit to it (e.g., with a hash function). Once committed, you can't change it. Later, you reveal it to prove what you committed to. However, in FRI, you don’t fully reveal it, that’s the magic! Polynomial Commitment Scheme: You pick a polynomial and commit to it. FRI enables a prover to commit to a polynomial and convince a verifier that the polynomial satisfies certain properties, mainly that it has a low degree.
     Like  Bookmark
  • Sum-Check: The Backbone of ZK Proofs Huge thanks to Oba, Ziemann and Nico for their help and feedback! ❤️ The Sum-Check Protocol is a fundamental tool in cryptographic proofs, particularly in zero-knowledge proofs (ZKPs) and verifiable computation. It allows a verifier to efficiently check that a prover has correctly summed up evaluations of a polynomial over a boolean hypercube without computing every evaluation explicitly. If that sounds confusing, don't worry, that’s exactly why this article exists. We’ll break down the key concepts needed to understand the Sum-Check Protocol and then walk through the protocol itself in an easy-to-follow manner. To assist you, I wrote a few scripts with Sage: https://github.com/teddav/sumcheck-article
     Like  Bookmark
  • Easy Sagemath setup I recently started using SageMath and it’s a game changer! 🔥 Prototyping simple or more complex mathematical thoughts has never been this smooth! I work daily on both an ARM MacBook and an x64 Ubuntu machine, setting it up properly on both was a bit of a hassle at first. After some trial and error, I found the simplest solution: running SageMath in Docker. The official Docker image, sagemath/sagemath, works flawlessly. If you're on an ARM Mac, be sure to add the --platform linux/amd64 flag when pulling the image: docker pull --platform linux/amd64 sagemath/sagemath Once downloaded, you can either launch the Sage REPL or run a script directly:
     Like  Bookmark