Let’s dissect a zkSNARK! (part 3)
Continuing from part 2, where we discussed building circuits and arithmetization. Now, we conclude our series by discussing how we go from constraint satisfaction through to a proof system and finally end up with a zkSNARK.
Zooming out again
Back to this diagram from last time, we went from an execution trace, cranked it through an arithmetization method (R1CS), and turned it into a constraint satisfaction problem. Now, we’ll be discussing the right half of the diagram:
Commitment schemes
Before diving in, we should back up a bit and ensure that we have an understanding of cryptographic commitment schemes, which are fundamental building blocks of the ZK ecosystem. When you write a message on an envelope and send it via your local post office to your friend, you can’t change that message once it’s been sent. In essence, you’ve effectively committed to the contents of the message.
Cryptographic commitment schemes do something similar. A committer is able to take a message and run it through some function to get a value that they can publish publicly. Once that value is published, the committer has committed to that value, and a verifier can, at some future point, be able to verify that the committer did indeed commit that message. The committed message should not be able to be read by anyone without the key (hiding) and there should be no way for some other version of the message to evaluate to the same commitment (binding).
Commitment schemes happen in two phases: commit and reveal. In the commit phase, the committer calculates c = Comm(u,m) where u is a key, and m is the message. In the reveal phase, the committer sends u and m to the receiver, who can then calculate c' = Comm(u,m) and check that c' = c.
Polynomial Commitment Schemes (PCS)
Polynomials are used in a variety of applied mathematical contexts. Reed-Soloman codes utilizes polynomials to enable a class of techniques called Error Correcting Codes, which automatically correct transmission errors over a potentially noisy channel. These are used in a number of places from hard disk drives to cellular networks to ensure that the data is read or transmitted correctly.
A Polynomial Commitment Scheme allows a committer to generate a polynomial to commit to that is easily verified by the recipient. They are used extensively in zkSNARKs. Polynomials have a very useful property in which a receiver can query one part of the polynomial without having to reveal the entire polynomial (side note: this is called oracle access, which we’ll discuss later).
In other words, we are able to prove that we know a some number of points i on the polynomial p(x) where p(a_i) = b_i without revealing our polynomial p(x). Unlike in a regular cryptographic commitment scheme, (c = Comm(u,m), where u and m must be revealed to the verifier), polynomial commitments allow a verifier to prove evaluations of the polynomial at various points without revealing the entire polynomial.
They can be used to take a large amount of information (such as a very long execution trace of an arithmetic circuit) and fit it into a small amount of information (a polynomial). There are a number of different types of commitment schemes, each with various properties.
KZG Commitments
The KZG polynomial commitment scheme is one of the most common forms of polynomial commitments used in zkSNARKs today. The name KZG comes from the authors of the original paper: Kate, Zaverucha, Goldberg. A KZG commitment is a commitment to a vector of n polynomial evaluations of the polynomial p(x) that is of degree n-1 (called a witness polynomial). Essentially, the verifier is able to discern with very high probability that the committed polynomial is correct.
Interactive Oracle Proofs (IOP)
Interactive Oracle Proofs are an information theoretic model that operate on a number of idealized assumptions such as unbounded computation ability of the prover/verifier or that the prover/verifier must operate on without communicating with other parties during the execution of the protocol.
IOPs are a type of Interactive Proof (IP) that utilizes oracle access to the proof. Interactive Proofs are a class of proofs that require a number of rounds of interaction between a prover and a verifier, wherein the verifier will query the prover and receive responses. Oracle access means that the prover has sent the entire proof P(x) to an oracle, which the verifier can then query random values (i.e. the verifier will choose a random number, say x = 5, and ask P(5) = ?, and will get the answer P(5) = 10 back) without having the entire proof P(x)revealed.
Proof systems
We get a proof system after putting an IOP (which, if you remember, is just an idealized model) through a cryptographic compiler. Cryptographic compilers remove idealized assumptions of communication and utilize cryptographic primitives such as hash functions or elliptic curves to move an IOP into a real-world proof system that can generate a zkSNARK.
We’ll briefly touch on two proof systems that are older but have a wide amount of adoption:
Groth16
Groth16 is an older, well-used proof system. One thing that a lot of people see as a turn off is that that requires a per-circuit trusted setup, which makes it much more difficult to use, but is more secure. Groth16 also has the smallest proof size.
Plonk
Plonk, on the other hand, uses a universal trusted setup and so it’s a lot easier to use. Proofs that are generated by using Plonk are bigger than Groth16 proofs.
Newer proving systems
Newer proving systems such as halo2 and Plonky2 combine the best of other proof systems and other new concepts to allow for orders-of-magnitude faster proving/verifying times, recursion, and more. In this fast-moving field, the is always something new and interesting on the horizon!
zkSNARK
So, we’ve gone through all of this to come up with a zkSNARK! So you might be wondering what a zkSNARK proof even looks like. It can come in a number of different formats, but here’s one that’s generated by Circom/SnarkJS with Plonk:
{
"A": [
"6908956559376137340171196334631977634711358419710404769689125968088654624644",
"16932989149179303110306042962567858437672652090915736000213210179928213052205",
"1"
],
"B": [
"10588840689520264771936066469568807327119382366634392323966486988467407001638",
"10229316063452690801507259777947935670857074599961348945620381561034515164406",
"1"
],
"C": [
"16084899085204675689132108134083605933751081775503786540495196599722848162338",
"21356787944490833330652242243111424190095383591299924564125418627026991789158",
"1"
],
"Z": [
"17765107575899672040993541878831073381023263680467188595309317410911854244771",
"6313343890583290837650965624272827660438348800173375236989766452773637648713",
"1"
],
"T1": [
"9554996580112652857081087006710106006873579191557920158338510670114836358531",
"10692777877219430516985193994926553868926808589724390039483447860423047846932",
"1"
],
"T2": [
"676790424696889453973167662648988910434711585806269850335472050317445000801",
"19046102729811438225780142024141399492680515098326829586767383998198297849113",
"1"
],
"T3": [
"4605880236713526737003637609771442419611615015020516846461894965226380068331",
"19331673596656480838213028785359744521984113367516263088749444124059486171827",
"1"
],
"eval_a": "15485933003077165236672451528127828232974110105382592967191331423684824757418",
"eval_b": "16629977471156978182828773382438576062157680070473413146331064655197104175954",
"eval_c": "19887998895846667152935870867467200995858182358449502995901961038310475312715",
"eval_s1": "2861053678782603869717695335350019077968004966013839132807493210057313857498",
"eval_s2": "12045841120468746488230522035590421057538184460262526104889604898312099136113",
"eval_zw": "4030229530359541063568939638832079137472854642425576803825418801503661461483",
"eval_r": "4007002272841740548667739607769563075966899148986525117512093975687169758932",
"Wxi": [
"2604076815338219820969818933185487042665467863796932384089487859508714979834",
"14726021541798728844627399835533201742658584651576597396311585628406002751083",
"1"
],
"Wxiw": [
"4486542282232103671498159945862056575371277318055006380926533302403456544125",
"6939810882697630067565408176534942709703777425287032514579101958507243736198",
"1"
],
"protocol": "plonk",
"curve": "bn128"
}Wrapping up
The journey to learning ZK is definitely not easy or straightforward, but every new piece of the puzzle makes the image that much more clear. I encourage you to continue learning on your own as there are many resources out there, no matter where you are in your ZK journey.
The next few posts will likely focus on more practical approaches to implementing zkApps using available toolchains, so stay tuned!
Hopefully you’ve been able to learn something through all of this. If so, please share with a friend and follow me here on Medium and on Twitter!
