# ZK Proofs Part III: More ZK Math

**Published by:** [0xDanki ( Tin Erispe )](https://paragraph.com/@tinerispe/)
**Published on:** 2023-05-10
**URL:** https://paragraph.com/@tinerispe/zk-proofs-part-iii-more-zk-math

## Content

Where were we… ah yes, Fiat Shamir Transformation. Anyway from dis point on we’ll probably have less Marites and more cryptography, because I want my frens to know wat these things are called in the actual ZK world. So lezgow.Fiat-Shamir Transformation in DetailAs I sed, ZK-SNARKs make use of a trusted setup as their verifier. And that a trusted setup is an algorithm that looks like dis:Screenshot taken from WikipediaNow, there are two things you can note about this: First is that the trusted setup uses a randomizer at #2, when Peggy picks a number to evaluate from. The second is that in #3 Peggy runs her answers through a hash function… and a hash is a one-way function where you can compute for the answer but you cannot derive the variables that were used to get your answer. So at this point, there’s no way Peggy could have guessed the result of her hash beforehand, not until she runs her variables in the trusted setup. This two-part mechanism ensures that the prover could not fake their proofs. At #4, Peggy just creates the proof by evaluating her hash through another function and submitting this value along with the number she has computed in #2. This proof is publicized and can now be checked by anyone by plugging these values to the equation in #5. And that, my frens, is how ZK-SNARK works.Polynomial CommitmentRemember why Becky couldn’t just recite the polynomial to Marites in the previous article? Becky as the prover can’t just give away the polynomial because it practically gives away her 10 million gossips to Marites who may or may not be trying to fish for it. Plus the polynomial is just too lengthy to recite. So instead of doing that, we use a commitment scheme called the Polynomial commitment scheme. Wat agen? Okay let’s dissect dis frens… A commitment scheme allows you to commit a value while keeping it hidden, like putting a note inside a vault. In our analogy, Becky could put her polynomial inside the vault to solve this problem. Now she sends the vault to Marites. There’s still a problem with that tho. Marites doesn’t have the key to the vault, and Becky isn’t willing to give the key because that would be giving away her precious polynomial to a stranger she doesn’t trust. So what does Becky do? She constructs a special kind of vault that can prove to Marites the value of her polynomial at whichever point Marites asks to evaluate. And dat special type of vault is wat we call a Polynomial Commitment, or PC.Now for the magic trick…Merkle Trees, the data structure through which blockchain data are stored, has properties that act like a polynomial commitment scheme.Image taken from WikipediaAs you see, each node contains a hash of the child nodes below them. So the top hash, or the merkle root, is a hash you can only arrive to if you compute all the hashes from the nodes below it. The top hash represents and proves the existence of all the data below it without revealing what they are. Can you see the similarities now? What if we do this then… Let’s store each term (the variables and coefficients) of Becky’s polynomial inside a merkle tree node. Then we hash them to arrive at a merkle root. Now this top hash serves as a polynomial commitment without revealing any part of Becky’s polynomial, innit? Now you know how it all fits together in ZK-SNARKs.Wait, ders more…Gomsh it’s been a long ride, and by now I hope you already have an idea of how the parts work to produce a ZK Proof. We used ZK-SNARK in our example but as I sed, there are many, many flavors of ZK. And there are many kinds of commitment schemes. For instance, let’s see a polynomial commitment scheme called FRI, which doesn’t even need a trusted setup and is being used by the other common type of ZK, ZK-STARKs.Fast-Reed Solomon Interactive-Oracle Proofs of Proximity (I can’t pronounce it, so just say FRI)Ders a little problem in checking the polynomial commitment in order to verify a polynomial. First, how does the verifier tell if the commitment even represents an actual polynomial? And second and more commonly, how do we check if the polynomial is not so enormously sized that it’s impossible to use for computation? Dis is where we use FRIs. The idea with FRI is that we check the degree of the terms inside the polynomial by running them through a certain mathematical transform (commitment phase) and then letting the verifier evaluate how a few points in the diagonal fits within the range of a graph derived from a billion data points (querying phase).Screenshot taken from Vitalik Buterin's blogThere are still ways to make the FRI more efficient for both the prover and the verifier which you can read on Vitalik’s post. There ar also many other polynomial commitment schemes that are widely used in the blockchain space, like the KZG commitment that will be used in Ethereum along with Proto-Danksharding. But I’ll reserve that for a different post later coz boy, what a story already. Anyway, I hope dis has fed your ZK curiosity for today. Maybe on the next post we’ll talk about the application side and how ZK circuits are actually created. For now, hold Danki’s promise dat der will be another ZK post. Byebye!Subscribe

## Publication Information

- [0xDanki ( Tin Erispe )](https://paragraph.com/@tinerispe/): Publication homepage
- [All Posts](https://paragraph.com/@tinerispe/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@tinerispe): Subscribe to updates