A Field Guide to zkSNARKs Part I: A Primer on Computation

A Field Guide to zkSNARKs Part I: A Primer on Computation(write.as)

65 points by madrafi 6 years ago | 6 comments

ahelwer 6 years ago |

I wanted to read this blog post but it seems uncertain about its intended audience. It goes over a whole bunch of basics like turing machines, circuits, decidable languages, NP, etc. - but too briefly for people unfamiliar with those concepts to understand, and not briefly enough to keep the attention of everyone else. Then we jump to using something called the Hadamard component-wise product which is not defined. I'm sure there's a good post here but it could use trimming in some places and expansion in others.

JadeNB 6 years ago | |

> Then we jump to using something called the Hadamard component-wise product which is not defined.

Aside from the 'Hadamard', which is just the name of a mathematician who used it, it's pretty self documenting, no? Multiply two vectors of the same size by multiplying corresponding components. (This can be viewed as an intermediate, coordinate-dependent step in the computation of the coordinate-independent dot product—although that doesn't seem to be how it's used here.)

lavrov 6 years ago |

Didn’t read the entire post but I think the characterization of PCP’s is a bit off - some SNARK constructions and STARKs both use PCP’s - using a linear PCP vs a PCP doesn’t impact transparency or proof size, that’s more a function of the commitment scheme

madrafi 6 years ago | |

I meant to skip over PCPs because it would need a separate posts and make the whole longer, I also avoided explicitly mentioning PCPs or SNARKs constructions from PCPs[1] for the same reason. Yes, concluding about the transparency vs proof-size trade-off is a mistake of my part. Thanks for taking the time ! will push an update on that bit soon.

[1]: https://eprint.iacr.org/2012/718.pdf

Ar-Curunir 6 years ago | |

Yeah, it's a relatively good high level post about SNARKs, but there's some confusion about the role of PCPs in SNARKs.

(all SNARKs have some probabilistic checking at the core; that's how you get succinctness)

madrafi 6 years ago | | |

Author here, I did gloss over PCPs certainly, and agree that SNARKs also use PCPs and I might have made the terrible conclusion about proof sizes. Will push an update soon ! thanks for taking the time.