Changelog (maintenance began June 2022)

  1. January 24, 2022. Various typo corrections.
  2. December 19, 2022. Corrections to Section 8.4.1 describing the natural reduction from arithmetic-circuit-SAT to R1CS
  3. December 12, 2022. Added a way of understanding the binding analysis of the commit/reveal protocol for linear functions in Section 17.2 as analogous to special soundness of Scnorr's Sigma protocol. Added footnote (currently Footnote 67) further clarifying what should be hashed when applying the Fiat-Shamir transformation.
  4. November 1, 2022. Corrected indexing of rounds in iterative description of the sum-check protocol in Section 4.1.
  5. October 19, 2022. Added to Chapter 6 an overview of Cairo's simplified variant of plookup, and revamped discussion of the final section of the chapter on ASIC-like vs. CPU-like front-end approaches.
  6. October 19, 2022. Added more intuition for zero-knowledge protocols at the end of Section 11.1. Added a sketch of the simulator for Fiat-Shamir-ed zero-knowledge protocols in Footnote 132.
  7. October 19, 2022. Added more detailed discussion of prover time vs. verifier cost tradeoffs in FRI and other IOP-based polynomial commitments in Chapter 16.
  8. October 19, 2022. Added more examples of composed SNARKs to Chapter 19, added Goldilocks field as an example attractive field.
  9. October 19, 2022. In Section 13.1.2, added analogy of commit-and-prove zk argument to FHE schemes, but where the verifier can't perform multiplication on committed/encrypted values.
  10. October 17, 2022. In Chapter 5 on the Fiat-Shamir transformation, added discussion of appropriate statistical/interactive security levels vs. computational/non-interactive. Added extra discussion of "grinding attacks".
  11. October 17, 2022. Added more background on elliptic curve groups in Section 12.3.1, and edited the section header to call attention to this as a self-contained primer on elliptic curves. Added pointers to helpful illustrated primers on elliptic curve groups.
  12. October 17, 2022. Cleaned up analysis of extractability of KZG commitments under the PKoE assumption (Section 15.2).
  13. October 17, 2022. Cleaned up notation in Section 12.2.3 (analysis of Fiat-Shamir applied to Sigma-protocols)
  14. October 17, 2022. In Section 8.4, where R1CS-SAT is defined, added the requirement that the first entry of the witness vector $z$ is $1$, because otherwise the all-zeros vector would trivially satisfy \emph{any} R1CS instance. This also ensures that there are efficient transformations from circuit-SAT to R1CS-SAT.
  15. October 17, 2022. Inserted example of the bivariate polynomial $u_H$ appearing in the holography protocol of Marlin (Section 10.3.2).
  16. October 17, 2022. Clarified that factor-2 overhead in verification costs when using FRI to get a polynomial commitment scheme can be avoided.
  17. October 17, 2022. Added more intuition for binding of KZG commitments in Section 15.2.
  18. October 17, 2022. Added discussion of extractability to the polynomial commitment scheme in Section 13.1, including an attack on extractability if the adversary can choose the evaluation query. Added a pointer to this example in Section 7.4, where the notion of extractable polynomial commitments is first introduced, as an example of how a scheme can be binding but not extractable.
  19. June 27, 2022. Fixed typos and added clarification to the proof of Fact 10.1. Thank you mmagician!
  20. June 21, 2022: Clarified relationship between binding and extractability of polynomial commitments in Section 7.4, clarified notation in knowledge soundness analysis in that section. Thank you Bryan Gillespie!
  21. June 21, 2022: Small clarifications to the description of the circuit-sat problem in Section 6.5.1
  22. June 10, 2022: Corrected typos in Bulletproofs coverage: 4/p --> 1-4/p on page 212. v_L and v_R--> v'_L and v'_R in the final line of Protocol 13 pseudocode. Thank you, Elliott Jin!
  23. June 10, 2022: Clarified intro to knowledge soundness (start of Section 7.4) in response to questions/feedback. Earlier in the chapter, clarified discussion of why Merkle trees alone do not yield a polynomial commitment scheme.