<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Yan Zhang on Medium]]></title>
        <description><![CDATA[Stories by Yan Zhang on Medium]]></description>
        <link>https://medium.com/@krzhang?source=rss-a338b7363293------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*6X5DzHhueDnr3jqq.</url>
            <title>Stories by Yan Zhang on Medium</title>
            <link>https://medium.com/@krzhang?source=rss-a338b7363293------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 23:33:36 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@krzhang/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Privacy in Cryptocurrencies: Zero-Knowledge and zk-SNARKs (2/2)]]></title>
            <link>https://medium.com/@krzhang/privacy-in-cryptocurrencies-zero-knowledge-and-zk-snarks-part-2-f6a3ee167b16?source=rss-a338b7363293------2</link>
            <guid isPermaLink="false">https://medium.com/p/f6a3ee167b16</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[privacy]]></category>
            <category><![CDATA[crypto]]></category>
            <dc:creator><![CDATA[Yan Zhang]]></dc:creator>
            <pubDate>Tue, 19 Feb 2019 19:33:39 GMT</pubDate>
            <atom:updated>2019-02-19T19:36:37.948Z</atom:updated>
            <content:encoded><![CDATA[<h4><a href="https://yanxzhang.com/about/">Yan Zhang</a> and <a href="https://twitter.com/theyisun">Yi Sun</a></h4><p><em>(This 2-part article is the third of a series whose first 2 articles can be found </em><a href="https://medium.com/@yi.sun/privacy-in-cryptocurrencies-d4b268157f6c"><em>here</em></a><em> and </em><a href="https://medium.com/@yi.sun/privacy-in-cryptocurrencies-mixing-based-approaches-ce08d0040c88"><em>here</em></a><em>. The first half of this article can be found </em><a href="https://medium.com/@krzhang/privacy-in-cryptocurrencies-zero-knowledge-and-zk-snarks-1-2-68ce1838fd9c"><em>here</em></a><em>.)</em></p><p>While zk-SNARKs enable the wonderful properties we have just discussed, a number of issues remain with their usage in cryptocurrencies:</p><ul><li>Proof generation time and memory usage are relatively high for the zk-SNARKs used in Zcash, imposing a computational burden for transacting. This has been partially addressed in the recent <a href="https://z.cash/blog/sapling-activation-complete/">Sapling release</a> of Zcash and may continue to improve due to ongoing engineering work.</li><li>Although zk-SNARKs feature “succinct” proof lengths, their size is still non-zero, and their presence makes transactions larger than Bitcoin transactions. This is a particular issue because the corresponding set of commitments must be stored by each node forever, since users do not know which commitments have been spent.</li><li>The BCTV zk-SNARK used in Zcash requires a “trusted setup” step in which some initial secret randomness is generated and destroyed. If this randomness is compromised, an attacker could generate zk-SNARKs for invalid statements, destroying the integrity of the system. For Zcash, the initial trusted setup was generated in October 2016 via a ceremony <a href="https://spectrum.ieee.org/tech-talk/computing/networks/the-crazy-security-behind-the-birth-of-zcash">involving radioactive waste</a> involving 6 distributed participants, while an updated trusted setup was generated in April 2018 via a <a href="https://www.zfnd.org/blog/conclusion-of-powers-of-tau/">multiparty computation</a> involving 88 participants.</li></ul><p>While the Zcash developers are working to alleviate these, some different approaches to them come from extensions to the simple zk-SNARK-based cryptocurrency and replacements for zk-SNARKs which are now under development. We now give a brief description of several of these.</p><h3>zk-STARKs: Removing trusted setup and potential scalability</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/0*im2tWT-OsAOjlRSs.jpg" /><figcaption>A zero-knowledge Stark.</figcaption></figure><p>In <a href="https://eprint.iacr.org/2018/046.pdf">a paper by Ben-Sasson, Bentov, Horesh, Riabzev</a> (BBHR for short), an alternative to zk-SNARKs called zk-STARKs was proposed which removes the need for a trusted setup. As with zk-SNARKs and BCTV, a zk-STARK is any system which satisfies a certain list of properties, but the term is often used to refer to the <em>specific implementation</em> given by BBHR, and we will make our comparisons using this specific implementation.</p><p>A zk-STARK is a system which satisfies all the requirements of a zk-SNARK, with 2 differences:</p><ul><li>The “S” here stands for “<strong>Scalable</strong>” and <em>not </em>“Succinct.” It requires that both proving and verifying are time-efficient, with the Verifier requirement equivalent to that of zk-SNARKs.</li><li>The “T” stands for “<strong>Transparent</strong>,” the most important difference between a zk-STARK and a zk-SNARK. This means that no secret randomness is required for the security of the protocol, and in particular that the trusted setup is not needed.</li></ul><p>Because of their similarity to zk-SNARKs, zk-STARKs are often viewed as a “drop-in” replacement for them in various cryptographic tasks. In particular, our description of SnarkCoin above would not change appreciably if we replaced each instance of a zk-SNARK with a zk-STARK, allowing us to upgrade it to StarkCoin (the official coin of Stark Industries!). Such an upgrade has a few trade-offs:</p><ul><li>Beyond the obvious advantage of removing the trusted setup, BBHR zk-STARKs are believed to be secure against attacks by quantum computers, whereas BCTV zk-SNARKs and many other cryptographic techniques (e.g. Pederson commitments from <a href="https://medium.com/@yi.sun/privacy-in-cryptocurrencies-mixing-based-approaches-ce08d0040c88">post 2</a>) are not, due to their reliance on the difficulty of the discrete log problem (DLP) in elliptic curves and/or finite fields. This makes StarkCoin more <a href="https://en.wikipedia.org/wiki/Post-quantum_cryptography">post-quantum</a> secure.</li><li>While zk-STARKs are asymptotically scalable, constants matter, as anyone working in “real world theory” knows. Unfortunately, in practice BBHR proof sizes are about 1000x larger than BCTV for the same statements, making them impractical to use at the moment. This is an area of active research by <a href="https://www.starkware.co/">Starkware</a>, among others, and researchers believe it can be significantly improved.</li></ul><p>As for the implementation, BBHR zk-STARKs are built on completely different mathematical foundations, involving Reed-Solomon codes. We direct the interested reader to Vitalik Buterin’s (different from his trilogy on zk-SNARKs!) trilogy of guides on them (<a href="https://vitalik.ca/general/2017/11/09/starks_part_1.html">I</a>, <a href="https://vitalik.ca/general/2017/11/22/starks_part_2.html">II</a>, <a href="https://vitalik.ca/general/2018/07/21/starks_part_3.html">III</a>).</p><h3>Recursive (zk)-SNARKs: Compressing the blockchain state</h3><p>Though zk-SNARKs create a need in Zcash to keep each commitment forever as part of the blockchain state, an extension to them called <strong>recursive SNARKs</strong> presented in papers by <a href="https://eprint.iacr.org/2012/095.pdf">Bitansky, Canetti, Chiesa, and Tromer</a> (BCCT) and <a href="https://eprint.iacr.org/2014/595.pdf">Ben-Sasson, Chiesa, Tromer, and Virza</a> (BCTV) provides a technique for dramatically compressing the size of the state. This technique can be used with or without the zero-knowledge aspect of zk-SNARKs, meaning that it can apply to cryptocurrencies with or without privacy. It is currently being applied (without the zero-knowledge component) in <a href="https://codaprotocol.com/">Coda</a> to create a blockchain with compressed shared state.</p><p>The key idea is to create a method for composing SNARK proofs. At a high level, the blockchain state consists of a <a href="https://en.wikipedia.org/wiki/Merkle_tree">Merkle root</a> R of the current set of balances S and a proof P that “there exists a set of transactions T and current set of balances S such that</p><ul><li>S is created by applying the transactions in T to the genesis state,</li><li>Validate(T) = True,</li><li>Merklize(S) = R.”</li></ul><p>In particular, the current set of balances S is <em>not</em> part of the shared blockchain state; instead to track a set of balances, a user would need to store both those balances and a Merkle path to the root R. To transact in this system starting from a state (R, P), a user would need to broadcast a transaction consisting of a <a href="https://en.wikipedia.org/wiki/Merkle_tree">Merkle root</a> R’ of the new set of balances S’and a proof P_diff that “there exists a set of transactions T and sets of balances S and S’ such that</p><ul><li>S’ is made by applying the transactions in T to S,</li><li>Validate(T) = True,</li><li>Merkelize(S) = R,</li><li>Merkelize(S’) = R&#39;.</li></ul><p>This transaction could then be used to update the blockchain state by setting P’ = Compose(P, P_diff; R), where Compose uses P and P_diff to generate a proof that “there exist proofs P_1 and P_2, sets of balances S_1 and S_2, and an intermediate Merkle root R_1 such that</p><ul><li>Merkelize(S_1) = R_1,</li><li>Merkelize(S_2) = R’,</li><li>P_1 is a valid proof that “there exists a set of transactions T_1 such that S_1 is made by applying the transactions in T_1 to the genesis state,”</li><li>P_2 is a valid proof that “there exists a set of transactions T_2 taking S_1 to S_2”.</li></ul><p>This magic operation Compose is the subject of sophisticated techniques in the papers of BCCT and BCTV involving <em>verifying a SNARK inside a SNARK</em>, which we leave it to them to explain.</p><p>The key point is that the size of the output proof P’ is independent of the number of transactions in the history of the blockchain, meaning that the shared blockchain state does not increase with use. This is reminiscent of a property of Mimblewimble as discussed in our <a href="https://medium.com/@yi.sun/privacy-in-cryptocurrencies-mixing-based-approaches-ce08d0040c88">previous post</a> and leverages SNARKs for data integrity rather than privacy.</p><h3>Bulletproofs: Optimized performance for specialized statements</h3><p>In general, there is a tradeoff between efficiency and generality in zero-knowledge proofs. Just as ASICs can be created to optimize <em>doing </em>very specialized kind of computations, zero-knowledge tools can be optimized to <em>privatize </em>very specialized type of computations. One example of this phenomenon is <a href="https://eprint.iacr.org/2017/1066.pdf">Bulletproofs</a>, a general zero-knowledge proof (technically, <strong>argument</strong>, as we described in the first half of this article) system with particularly good performance for <strong>range proofs</strong> introduced in a paper by Bünz, Bootle, Boneh, Poelstra, Wuille, and Maxwell.</p><p>Range proofs prove statements of the form “I know that X is between 0 and MAX_INT”, where MAX_INT = 2^N-1for some N. They can be used for cryptocurrency purposes if we recall the kind of statements we wanted to (zero-knowledge) prove with SnarkCoin. For example, trying to prove that I have enough money M to spend Y SnarkCoin would be proving that (M-Y) &gt; 0, which is done by proving that “(M — Y) is between 0 and MAX_INT”.</p><p>There are quite a few applied math tools in Bulletproofs. We highlight one of the more fun ideas that contain a few generally useful tricks:</p><ol><li>What does it mean that X is between 0 and 2^N-1? It means that X can be written as N 0/1 bits. Thus, we can represent X as anN-dimensional vector A_L whose digits belong to the (bigger!) range {0, 1, ... p-1} for some prime p. Then the Prover commits A_L(again, using the concept of <strong>commitments</strong>) to some (Pedersen) commitment Commit_X = Commit(A_L). Then the goal is to prove the statement “I know some A_L where all the digits are 0 or 1 that satisfies the Pedersen commitment condition.” We will focus on the first part (checking the digits) and ignore Pedersen commitments for this article.</li><li>How do we encode the digit check? The answer is a combination of the <a href="https://en.wikipedia.org/wiki/Dot_product"><strong>dot product</strong></a> (which we write as &lt;X,Y&gt;) and the <a href="https://en.wikipedia.org/wiki/Hadamard_product_(matrices)"><strong>Hadamard product</strong></a> (which we write as h(X,Y)), which are both unctions on a pair of vectors. The statement that “all digits of A_L are 0 or 1” is equivalent to having an AND of 3 statements: &lt;A_L, (2^{N-1}, ..., 2^0)&gt; = X(note this is what it means for A_L to be the vector representation of X), &lt;A_R = A_L — (1,1,...1)&gt;, and h(A_L, A_R) = (0,...,0). Thus, we have reduced digit-checking to conditions on vector operations.</li><li>Now, we “zoom out” and rewrite the above 3 statements into the forms &lt;A,B&gt; = v, &lt;C, D&gt; = 0, &lt;E,F&gt; = 0 , where A,B,C,D,E,F are just functions involving A_L, A_R, and some auxiliary variables (so in particularA = A_L, B = (2^{N-1}, ... 2^0), etc.) .</li><li>The benefit of this zoomed-out form is that the Prover can argue that these 3 statements are all true <em>in one shot</em> by picking a random z(in {0,1,…p-1}) and proving &lt;A,B&gt;z^2 + &lt;E,F&gt;z + &lt;C,D&gt; = z^2v.</li></ol><p>Stepping back, the upshot of all of this is we changed the logical AND of N statements (about checking each entry of a vector to be 0 or 1) into a single algebraic statement about some vectors instead, which makes the task both conceptually and practically easier. It turns out we can apply some shielding terms to make checking this statement zero-knowledge, so we obtain a zero-knowledge argument.</p><p>When applied to range proofs, Bulletproofs give much shorter proofs than previous methods, and they have <a href="https://www.getmonero.org/2017/12/07/Monero-Compatible-Bulletproofs.html">already been adopted</a> into Monero. On the other hand, their general instantiation has a more complex space of tradeoffs as detailed <a href="https://crypto.stanford.edu/bulletproofs/">here</a>, making their comparison to zk-SNARKs or zk-STARKs less clean.</p><h3>Conclusion</h3><p>Various incarnations of zero-knowledge proofs such as zk-SNARKs and zk-STARKs are exciting iterative developments on classical techniques in cryptography that have found themselves at the center of the theory of cryptocurrencies. Their raw power to apply zero-knowledge proofs to general statements gives us hope that their continued development will open up exciting new possibilities.</p><p>Philosophically, controlling which things an observer has zero-knowledge of <em>is</em> (an idealized version of) privacy, and we are excited to see these theoretical constructs evolve as they are forced to survive contact with practical applications in cryptocurrency.</p><p>— Yan X Zhang and Yi Sun</p><p><em>We thank Mihaly Barasz, Albert Ni,Vitalik Buterin, and Alessandro Chiesa for valuable comments and feedback.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f6a3ee167b16" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Privacy in Cryptocurrencies: Zero-Knowledge and zk-SNARKs (1/2)]]></title>
            <link>https://medium.com/@krzhang/privacy-in-cryptocurrencies-zero-knowledge-and-zk-snarks-1-2-68ce1838fd9c?source=rss-a338b7363293------2</link>
            <guid isPermaLink="false">https://medium.com/p/68ce1838fd9c</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[privacy]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <dc:creator><![CDATA[Yan Zhang]]></dc:creator>
            <pubDate>Fri, 25 Jan 2019 17:01:00 GMT</pubDate>
            <atom:updated>2019-02-20T01:16:46.630Z</atom:updated>
            <content:encoded><![CDATA[<h4><a href="https://yanxzhang.com/about/">Yan Zhang</a> and <a href="https://twitter.com/theyisun">Yi Sun</a></h4><p><em>(This 2-part article is part of a series whose first 2 articles can be found </em><a href="https://medium.com/@yi.sun/privacy-in-cryptocurrencies-d4b268157f6c"><em>here</em></a><em> and </em><a href="https://medium.com/@yi.sun/privacy-in-cryptocurrencies-mixing-based-approaches-ce08d0040c88"><em>here</em></a><em>. The second half of this article is </em><a href="https://medium.com/@krzhang/privacy-in-cryptocurrencies-zero-knowledge-and-zk-snarks-part-2-f6a3ee167b16"><em>here.</em></a><em>)</em></p><p>(<em>EDIT: we added some edits from valuable comments by Alessandro Chiesa. We also added a link above to the second half of the article)</em></p><p>Even though we have already shown (e.g. in <a href="https://medium.com/@yi.sun/privacy-in-cryptocurrencies-mixing-based-approaches-ce08d0040c88">our second article</a>) that it is possible, it should still be very mysterious that we can have a blockchain and transactions where so much of the state (such as identity of participants, the amount of the transaction, etc.) is private. Let’s take a step back and think about what such a system looks like.</p><p>Apparently, you’re part of some elite, exclusive, and eccentric club of people (why else would you want to join cryptocurrencies?), where all activities are under constant high-def video surveillance in a well-lit room with a giant podium. Every so often, a cloaked stranger walks up to the podium, and shouts, out loud, a bunch of numbers.</p><p>Then you and the other club members all nod, update your ledgers (your copies of the blockchain), accepting that the stranger (let’s call him/her/it A) indeed gave <em>some</em> other stranger B some coins, in a way that:</p><ol><li>Nobody else knows who A and B are. Maybe they’re even the same person.</li><li>Everyone is convinced that no coins were destroyed or created from thin air.</li><li>Nobody knows the amount that was transmitted, even though everyone is sure that A did not give B more coins than what A already had.</li></ol><p>These are absurd conditions. In particular, the next time some stranger shouts out a bunch of numbers that is meant to correspond to their trying to pay X coins to someone else, people will be able to detect if they were trying to cheat (e.g. they had less than X coins). In that case, the <em>only</em> thing that the other club members learn is that the stranger didn’t have enough coins! They don’t learn anything about X or the amount of coins the stranger had!</p><p>The above experience is what it is like to participate in a system based on Zero-Knowledge Proofs (ZKP). ZKPs are a beautiful part of theoretical cryptography very popular with the cryptocurrency community, mostly thanks to the well-known applications (and acronyms) of zk-SNARKs (made famous by Zcash) and zk-STARKs, though other ZKP systems such as Bulletproofs have recently been gaining traction.</p><p>Keeping with our theme, this article introduces the technical but not necessarily theoretically-trained reader to the main theoretical ideas as they relate to <strong>privacy, </strong>using a simplified version of Zcash as the main example (and the goal of this first half of the article)<strong>.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aGY6Tju2x7Jl41Z8ViZqwg.jpeg" /><figcaption>All aboard. Source: Wikipedia.</figcaption></figure><p>Our goal is to have readers understand these concepts and their contrasts with each other at a slightly more detailed level than “cryptography magic” while still leaving the very technical parts in a black box. Corrections and suggestions are, as usual, welcome.</p><h4>Proofs, Zero Knowledge Proofs, and zk-SNARKs</h4><p>What do these letter soups mean? Fundamentally, they are <strong>proofs </strong>with additional guarantees. A proof is some string (which could just be a sequence of numbers) that allows a <strong>Prover </strong>to convince a <strong>Verifier</strong> that some statement is true. We need 2 conditions:</p><ol><li><strong>completeness</strong>: If the statement is true, the Verifier will be convinced. Obvious enough.</li><li><strong>soundness</strong>: If the statement is false, it is “hard” to convince the Verifier of it. As in usual applications of complexity theory and cryptography, “hard” means with “very low probability”, i.e. 10^{-800}. While allowing the possibility of a “fake” proof sounds bad when money is involved, being able to lie with such a small probability is as good as any protection you have in real life.</li></ol><p>Now, we say a proof is a <strong>zero-knowledge proof (ZKP)</strong> if “the Verifier learns no new extra information” beyond the truth value of the statement. This magic-sounding term is formally defined by requiring the proof to be indistinguishable from one created by a <strong>simulator</strong>; intuitively speaking, this means that “<em>if someone who doesn’t know anything could have simulated the entire interaction convincingly, then there is no way you could have gained information by looking at the interaction.</em>” We refer the interested reader to <a href="https://en.wikipedia.org/wiki/Zero-knowledge_proof">the Wikipedia article</a> or <a href="https://blog.cryptographyengineering.com/2017/01/21/zero-knowledge-proofs-an-illustrated-primer-part-2/">Matthew Green’s post</a> for more details, but the rough definition above is sufficient for our purposes, as simulators are important for formalism but not implementation (i.e. once you prove something is a ZKP, you do not need to make a simulator to use it).</p><p>To see why such ZKPs could be useful for privacy, it is helpful to look at what the more familiar <strong>digital signatures </strong>do. Philosophically, a (good) digital signature Tproves the statement “I know a secret SK such that when I run the program Sign(SK,M)on a (public) message M, I get the value T.”</p><p>Think about this for a moment. If SK were only given to Denise and it is assumed that it is hard to get Sign(SK,M) = T if you didn’t have SK, then if Denise proves the above statement and then supplies her signature T to her message M, she has proven her identity! Thus, you can think of a digital signature as a non-interactive proof that Denise knows the secret key SK. Such a signature scheme would in addition be zero-knowledge if the signature T reveals no information about the secret key SK.</p><p>This is a good intermediate rest stop, as ZKPs are one of the coolest theoretical parts of classical cryptography. A type of ZKP popularized by cryptocurrencies is zk-SNARK, which impose additional requirements (corresponding to additional letters) which are good to have in cryptocurrencies. 2 letters down, 5 more to go! (Yes, we know that the P disappears. We’ll get there too.)</p><ul><li>First, the “S” means <strong>“succinct,”</strong> which promises that 2 things must be small/fast: proof length (as cryptocurrencies require the users as a whole to throw duplicates of the same data around) and verification time (because of decentralization, many people may want to independently verify each transaction).</li><li>Then, the “N” stresses the <strong>non-interactive </strong>property of our proofs. We have this because theoretical computer scientists frequently work with <strong>interactive </strong>(zero-knowledge or otherwise) proofs where the Verifier may interactively query the Prover in the verification step. These are more general and easier to think about, but less well-adapted to cryptocurrencies for many reasons. For example, one reason would be that (for both scalability and security reasons) we want to avoid requiring the Prover and Verifier to be online at the same time to interactively verify a proof. Another deep philosophical reason would be that interactive protocols depending on the Verifier (which is the blockchain!) using some secret randomness usually needed as part of such protocols seems impossible.</li><li>The “AR” stands for “<strong>argument,” </strong>which is a weaker form of “proof.” The technical difference is that the “soundness” property we talked about for proofs require that it is hard for a <em>computationally all-powerful</em> Prover to convince a Verifier of a false statement, while <strong>argument </strong>systems require that it is hard for a <em>polynomial-time</em> Prover to convince the Verifier of a false statement. At a zoomed-out level, this difference is negligible.</li><li>Finally, the “K” means our arguments are about <strong>knowledge</strong>, a formal way of saying that we consider statements of the form “I know X” rather than straight mathematical statements like “Y=Z.” The formal definition of an “argument of knowledge” relies on the technical concept of an <strong>extractor</strong>, which specifies exactly what it means for a statement to take the form “I know X”.</li></ul><p>To summarize, a zk-SNARK system for Prover Alice and Verifier Bob is where:</p><ul><li>Alice knows a piece of (K)nowledge.</li><li>Alice can prove to Bob that she knows it with an (N)oninteractive (AR)gument (basically a proof), after which Bob can be convinced that Alice knew the piece of knowledge, while acquiring (Z)ero (K)nowledge about what that piece is.</li><li>The length of Alice’s argument and the time Bob needs to check the argument are both (S)uccinct.</li></ul><p>Of course, these are just the <em>requirements</em> for a zk-SNARK; we said nothing about how such things are actually implemented. When people in cryptocurrencies say “SNARK,” they usually mean a particular implementation of zk-SNARKs, like “Xerox” versus “xerox.” These SNARKs arose in <a href="https://eprint.iacr.org/2013/879.pdf">a paper by Ben-Sasson, Chiesa, Tromer, and Virza</a> (so we’ll call them “BCTV”), using algebra over a finite field, elliptic curves, and QAPs (<strong>quadratic arithmetic programs</strong>, which encode individual gates in an arithmetic circuit as multiplications between pairs of polynomials). If, like us, you’re excited to learn the mathematics more deeply, we would recommend going through Vitalik Buterin’s trilogy of posts (<a href="https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649">I</a>, <a href="https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627">II</a>, and <a href="https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6">III</a>); we have also personally found learning from <a href="https://eprint.iacr.org/2013/279.pdf">Pinocchio</a>, a predecessor QAP-based SNARK implementation by Parno and Gentry, very educational to understanding BCTV.</p><p>The most important upshot for us is that BCTV <em>produces zk-SNARKs for general computation</em>! This means we can “zk-SNARK-ify”<em> arbitrary arguments </em>that sound like “I know some inputs X such that if you run a particular list of computations on X, then you get Y,” by turning these statements into e.g. lists of numbers. This is very, very powerful. With this result, we can create strings which prove statements like:</p><ol><li>“I know a secret S such that when I run a hash function f(S), I get the value H” (because a hash function is just a computation)</li><li>“I know numbers X,Z such that X² + Y² = Z² (for some given Y)”</li><li>“I know a number SK that is the private key for at least one of UTXO_1 and UTXO_2.”</li></ol><p>so that the recipients are convinced of these statements, but learn nothing about what you know after you convince them!</p><p>We will now see this “in action” in a hypothetical cryptocurrency.</p><h4>What about Privacy in Cryptocurrencies?</h4><p>We now describe <em>how</em> zk-SNARKs can be used in SnarkCoin, a hypothetical slimmed-down version of Zerocash (the <a href="http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf">protocol</a> leading to <a href="https://z.cash/technology/zksnarks/">Zcash</a>), to perform something like the zero-knowledge club meetings we described in our introduction. We have removed some details specific to Zerocoin, such as the distinction between the “basecoin” and the “shielded coin,” to focus on the meat of the idea.</p><p>In SnarkCoin, a <strong>coin</strong> consists of 3 pieces of data:</p><ul><li>a <strong>value </strong>(amount of money)</li><li>a <strong>serial number </strong>(an identifier for the coin which will later ensure it is not spent twice)</li><li>an <strong>address</strong> (this is a <strong>public key. </strong>It ties the coin to someone with a matching <strong>private key, </strong>who is the only person that can spend it)</li></ul><p>Each coin has a <strong>commitment</strong>, which is a number computed from the coin by some function (the idea of commitments and revealing appeared in <a href="https://medium.com/@yi.sun/privacy-in-cryptocurrencies-mixing-based-approaches-ce08d0040c88">our second post</a>; the main idea is that it is hard for a commitment to one value to be reinterpreted as a commitment to some other value, so in our case once we have a commitment for 30 coins it is basically impossible to lie and say the commitment was for 50 coins instead). When we “put a coin on the chain,” we only put commitments on, and not the values or serial numbers. The SnarkCoin blockchain consists of transactions which are applied to create the current state, which consists of:</p><ul><li>the set of commitments, playing a completely analogous role to <strong>UXTOs (unspent transaction outputs)</strong> in Bitcoin</li><li>the set of revealed serial numbers, which will play the role of the list of spent coins</li></ul><p>To describe transactions in SnarkCoin, suppose a user Alice knows the private keys for coins Coin_A and Coin_B , each of value 50 and wants to send 30 SnarkCoins to another user Bob by spending Coin_A and Coin_B and creating two new coins Coin_C (of value 30 for Bob) and Coin_D (of value 70 for Alice). She can accomplish this by broadcasting a transaction called Pour(Serial_A, Serial_B, Commit_C, Commit_D) with the following information:</p><ul><li>the serial numbers Serial_A and Serial_B for Coin_A and Coin_B</li><li>commitments Commit_C = Commit(Coin_C) and Commit_D = Commit(Coin_D) for Coin_C and Coin_D</li><li>a zk-SNARK (of any type, e.g. BCTV, that can prove such statements) proving that Pour(Serial_A, Serial_B, Commit_C, Commit_D) is valid, i.e. a zk-SNARK for the statement: “I know the data of some coins Coin_A, Coin_B, Coin_C, and Coin_D and the private keys Key_A and Key_B such that…”</li></ul><ol><li>“private keys Key_A and Key_B are valid keys corresponding to the public keys of Coin_A and Coin_B.” The validation of private keys simply performs a computation, and we can make zk-SNARKs for a computation!</li><li>“the commitments Commit(Coin_A) and Commit(Coin_B) appear on the ledger.” As commitments are functions, the first part is another computation check to compute the commitments. The second part is just checking that we have certain elements in some set, which is easy to implement (in Zerocash, this is done via a Merkle tree check).</li><li>“the commitments Commit_C and Commit_D are equal to Commit(Coin_C) and Commit(Coin_D).” Contrasting this to the previous bullet is educational: Commit_C and Commit_D are public, while Commit(Coin_A) and Commit(Coin_B) are not. We also don’t do a ledger check, because Commit_C and Commit_D are new.</li><li>“the serial numbers Serial_A and Serial_B of the old coins are not in the list of spent coins.” We need something like this to ensure coins are not spent multiple times.</li><li>“the values of Coin_A , Coin_B, Coin_C, and Coin_D are all nonnegative numbers and Value(Coin_A) + Value(Coin_B) = Value(Coin_C) + Value(Coin_D).” These statements ensure coins are not created or destroyed.</li></ol><p>Understanding the specific bullet points here will help, but <em>the main idea is that we have encoded what we want into mathematical statements, and BCTV knows how to turn these mathematical statements into zk-SNARKs.</em></p><p>All transactions in SnarkCoin will take this form. Some things to notice from just the input of Pour are:</p><ol><li>The <em>serial numbers </em>Serial_A and Serial_B of the <em>old</em> coins are exposed, but the coins themselves are not. This is because we want the value and the address corresponding to the coins to be private, but exposing the old serial numbers allows us to ensure the coins are not spent again.</li><li>The c<em>ommitments </em>Commit_C and Commit_D of the <em>new</em> coins are exposed (because we need to put them on the public ledger) but again, the coins themselves (even their serials) are not.</li></ol><p>While Pour only allows Alice to turn two coins into two other coins, it is a building block that can be combined to handle arbitrarily complex transactions involving many people.</p><p>For another coverage, we recommend <a href="https://www.youtube.com/watch?v=84Vbj7-i9CI">this video</a> by Alessandro Chiesa on the main ideas of the Zerocash protocol.</p><h4>What’s Next</h4><p>And there you have it — a simple cryptocurrency that realizes our seemingly-impossible skit in the introduction. As people transact coins (i.e. go to the podium and shout out strings of numbers, updating everyone’s ledgers), the coins start to move around, with nobody in the club knowing anything beyond how much coins they own. And if you think SnarkCoin is not sufficiently exciting, we leave you with the following (strange!) properties:</p><ul><li>By agreeing on the sequence of transactions, nodes agree that a valid notion of coin ownership <em>exists</em><strong> </strong>(no coin has been spent twice, and coins have only been spent by owners who know their private keys), but no node knows who the owners or values are.</li><li>Nuanced caveat to above: as Alessandro Chiesa points out, our simplified scheme allows payees to be recognized by the payer when the payee spends the coin created by the payer later. This is fixable, as in Zcash, but requires more work.</li><li>In particular, it is even possible for users to remember their private key, but be unable to spend some of their SnarkCoins if they forget the relevant serial numbers.</li><li>To validate transactions, users must store the full set of commitments, even of spent coins, since they <em>do not know which coins have been spent</em>.</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fz8NEXJNfyHY%3Ffeature%3Doembed%26autohide%3D1%26iv_load_policy%3D1&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Dz8NEXJNfyHY&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fz8NEXJNfyHY%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/e9cf59ce4840ffe90170261569a5f706/href">https://medium.com/media/e9cf59ce4840ffe90170261569a5f706/href</a></iframe><p>We are now at a natural place for a break. The second half of this article, coming soon, will be about other ZKP protocols inspired by zk-SNARKs and the comparisons between them.</p><p>— to be continued.</p><p><em>We thank Mihaly Barasz, Albert Ni, Vitalik Buterin, and Alessandro Chiesa for helpful comments and feedback on both halves of this article.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=68ce1838fd9c" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>