0
$\begingroup$

My background is that of a reasonably experienced programmer who hasn't learnt Comp Science formally. I am now learning Cryptography as a hobby in my spare time & I think I have learnt a reasonable amount of stuff through self-study.

I have learnt Elementary Number, Abstract Algebra & some amount of Algebraic Geometry through self study. I am not great at any of this but I think I have reached a satisfactory amateur level in these subjects.

I also have managed to get fair understanding of Cryptographic Hashing, RSA, DH, ECDH, Pairings etc. through self-study. Now I am trying to learn zkSNARKs & I am kind of getting stuck with self study of the non-math parts - i.e. the Comp Science parts - Theory of Computation, Complexity Theory, Circuits, Arithmetization etc.

I am looking for self study books which will help me with whatever I need to learn to understand zkSNARKS (& possibly other similar stuff like STARKs, PLONKs etc).

I tried a few books

  1. Borak & Arora - In "About the book", they write this book is also meant for Self-Study but this is absolutely not true. I got totally stumped in page 3 or something where I couldn't make head nor tail what they write very casually. May be they assume some prerequesites.

  2. Justin Thaler's Proof's, Arguments & Zero Knowledge book. I started it but it seems you need to know Computation Theory to understand this book, so this doesn't seem suitable.

  3. Michael Sipser's book (Introduction to Theory of Computation) - this seems to be a very good book & also possibly suitable for self-study but it's quite a big book & I am wondering if I need to know the whole book? Are there parts I can skip & jump ahead.

So I am wondering if someone can tell me what all I need to learn for understanding zkSNARKs & if there is a better book than Sipser for self study & what parts of the book I need to study? What do I need to learn & what can I skip? I am not going to be giving any exams so I don't think I need an end-to-end knowledge at least to start.

$\endgroup$
5
  • $\begingroup$ I would say it is not mandatory to have a deep understanding of theory of computation to be able to understand SNARKS. I think this is necessary if you really want to learn dig into the theoretical fundations. Why not start with something like this: youtube.com/…. Make your way to learning PLONK and then see if you need to fill in some gaps? $\endgroup$ Commented Sep 30, 2022 at 12:05
  • 1
    $\begingroup$ @MarcIlunga - I am not looking to have a deep understanding. I am just looking to have a very basic understanding. For e.g. when I started on video on ZK, the first sentence in the video talked about "languages" very casually. I had to computation theory and understand what is a language. Any material I look at seems to casually assume basic understanding of theory. Every line I read about zk, I seem to go down a rabbit hole. $\endgroup$
    – user93353
    Commented Sep 30, 2022 at 12:11
  • $\begingroup$ I can empathize with this, I have a hard time learning whenever I feel like that, I don't quite know some of the pre-requisites. But, I think the message that I was trying to convey was that maybe try and go through some of these materials (like the videos) without getting caught in rabbit holes. Then see how much you understand and prehaps you'll get a better feel for the knowledge gaps. $\endgroup$ Commented Sep 30, 2022 at 12:18
  • $\begingroup$ BTW, among cryptographic topics you have already studied, Pairings seems to me by far much more difficult than the others... can I ask you which sources have you employed? (just to "stole" them ;-) ) $\endgroup$
    – baro77
    Commented Sep 30, 2022 at 13:10
  • 1
    $\begingroup$ @baro77 - I didn't really master Pairings - I just understand enough of it to get by. It's far more difficult as compared to other topics. It's probably my weakest spot in Math & I need to get back to it again later. I mostly used Silverman's Mathematical Cryptography along with a lot of googling. $\endgroup$
    – user93353
    Commented Sep 30, 2022 at 14:32

1 Answer 1

1
$\begingroup$

I met the same importance of Computation Theory while dealing with ZKPs... (by the way, I would start from ZKP if you still don't master them before going on with zkSNARKs)

About CT prerequisites, I suggest you to read section IV.20 “Computational Complexity” of "The Princeton Companion to Mathematics". Just 30 pages, co-authored by Oded Goldreich (the author of Foundation of Cryptography, which I found inspiring -even if demanding- in self-studying ZKPs): I think this authorship is a bonus regarding our (as amateurs) need to read "the right amount" of CT to satisfy our cryptography eagerness

$\endgroup$
4
  • $\begingroup$ Won't ZKP need the same prerequisites of Computational Theory as zkSNARKs $\endgroup$
    – user93353
    Commented Sep 30, 2022 at 14:36
  • $\begingroup$ I'm not sure to get the meaning of your comment here, anyway zkSNARKs are, apart from other things, non-interactive zero knowledge arguments (a soundness-relaxed flavour of proofs), so ZKPs' related CT is relevant imho (even if maybe not enough, I don't know, I haven't studied zkSNARKs yet) $\endgroup$
    – baro77
    Commented Sep 30, 2022 at 17:35
  • $\begingroup$ by the way, I would start from ZKP if you still don't master them before going on with zkSNARKs - I thought this meant you were advising me to start with ZK instead of CT $\endgroup$
    – user93353
    Commented Sep 30, 2022 at 19:10
  • $\begingroup$ ok, now I get it: nope, imho the path should be light CT (e.g. via Princeton Companion), ZKPs, zkSNARKs $\endgroup$
    – baro77
    Commented Sep 30, 2022 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.