Why and How zk-Snark Works (2019)

(arxiv.org)

137 points | by michaelsbradley 3 days ago

5 comments

  • seibelj 3 days ago

    I work in blockchain / cryptocurrency (one and the same) for a long time now and zksnarks are a fundamental building block for the future of generalized financial privacy. Many people don’t understand why financial privacy is so crucial - although many of these same people will argue through the teeth that other forms of privacy are absolutely essential.

    Governments throughout the world are restricting cash more and more. Why? It’s not that cash is paper. It’s that cash eliminates state tracking. The purpose of cash in a digital world is to prevent the state from creating a financial panopticon. Cryptocurrency accomplishes the same goal, but far more effectively.

    How can I explain to you guys how crucial this is? I guarantee you in 40 years the creation of bitcoin will be seen as a watershed moment in society.

    • bigcorp-slave 3 days ago

      I am generally a very privacy-minded person, but serious question here: is there any legitimate use case for financial privacy from the authorities? I don’t mean “ideologically, I am upset that the government can see I buy too many pastries”. When we look at cryptocurrency, it is used for a small collection of things:

      - Speculation on a high volatility, unregulated market

      - Money laundering

      - Distribution of illegal material

      These all seem like things Im fine with the government having visibility into. Perhaps this is ignorance on my part, but all legitimate uses I’ve ever heard of seem like rounding error next to the above. No one is buying pizza with bitcoin in 2020. The uptake for real transactions seems like it’s near zero.

      About the best I can come up with is that financial privacy permits low level lawbreaking for laws generally regarded as stupid or unethical (e.g., marijuana). I think it’s safe to say that people who want to feed their drug habits will find other anonymous ways to to pay, e.g. barter or proxy goods.

      The types of folks who are deeply affected by large governments having logs of their transactions are not the downtrodden masses. They’re the moderately wealthy engaged in corruption and trafficking. Cry me a river.

      • darawk 3 days ago

        What are the legitimate use cases for privacy from the authorities in other domains? What are the legitimate use cases for being allowed to speak to other humans without your voice being recorded in case the authorities want to know what you said later?

        Fundamentally financial privacy is just privacy. People desire financial privacy for all the reasons they desire any other kind of privacy. It's certainly fine to make the collectivist argument that individual privacy is not worth the social cost of opacity, but the idea that this is true only in finance seems odd and difficult to justify.

        • nootropicat 3 days ago

          Politicians and bureaucrats try to maximize their _relative_ power over everyone else. Power ultimately comes from resources - as security apparatus requires resources to function. What this means is that states try to maximize effective real level of taxes.

          Only two forces prevent taxes from going to ~100%: tax evasion and military risk from other states. As taxes become higher, more people start evading, reducing the real effective tax rate, which reduces real relative power of bureaucrats and politicians. Smart governments reduce taxes in that situation. If evasion becomes impossible, taxes are going to approach 100%: everything over resources needed for survival goes to the ruling class (slavery), which is historically the dominant arrangement (eg. serfdom).

          It wouldn't be a fundamentally new situation even in modern times - in the Soviet Union everyone, officially, made roughly the same regardless of what they did, and that amount was barely enough for survival. Which wasn't smart, because tax evasion was enormous (in the form of bribes and black market), which created a new ruling class (now called oligarchs).

          Military risk is another force acting against high taxes, as states that kill its economic activity (due to people having weak motivation) risk being conquered eventually by wealthier and stronger states. However, looking at North Korea in particular, it appears as long as some form of MAD is in place (in the case of NK - destruction of Seoul for decades, lately also nuclear missiles) that doesn't matter that much today.

          To sum it up: I'm convinced total financial surveillance inevitably means a return to slavery. Physical money is going to disappear in decades. Anonymous crypto appears to be the only force that can prevent this future.

          • cycomanic 3 days ago

            Your statements need some serious evidence to back them up. Even if one concedes that the goal of "the ruling class" is serfdom, you have brought no evidence that this is related to the amount of taxes and that taxes somehow would grow to 100%. In fact looking at the history of the US, inequality has grown as tax rates have reduced. Similarly in worldwide comparisons countries with higher tax rates are generally more equal, in other words they are less likely to have an underclass of "serfs". "Financial privacy" and ways to hide your financial transactions almost exclusively benefits those with capital, what I would already call the ruling class, as evidenced by e.g. the Panama papers.

            • exo762 3 days ago

              Equality/Inequality and Freedom/Serfdom lie on two different although not fully independent axes. One can be a rich slave - by not having any political freedoms.

              • cycomanic 3 days ago

                The OP made an economic argument about 100% taxes and "slavery" not political freedoms, so your point is orthogonal. That said, while I agree that equality and freedom lie on different axes, I disagree with your point that one can be a rich slave, being a slave implies that you have neither economic nor political power (which are almost impossible to separate anyway).

            • atleta 3 days ago

              The things that prevent taxes from growing to 100% in a democracy are indeed wrecking the economy, causing the tax income to decrease and the risk of losing the next election.

              You can argue that tax evasion is one way that may cause a decreasing tax income with the increasing tax rates but it's not the only factor.

            • tluyben2 3 days ago

              > The types of folks who are deeply affected by large governments having logs of their transactions are not the downtrodden masses

              Those same masses don't care about cameras everywhere, they don't care about websites tracking them etc; they have no privacy concerns at all outside 'hope they cannot see me naked when in the shower' (which i'm not sure about with all the camera devices either though), so that's not a very good example imho.

              I don't want the gov to see every transaction I make, but i'm not into trafficking, corruption or money laundering or whatever. It is not the govs business; it is their business to see how much money I get in and for me to pay taxes over that. They do not need details of anything unless i'm a suspected criminal. But there is the rub, in my opinion, they would need to prove I did something to warrant that, not blanket rules like AML over everything financial.

              > The uptake for real transactions seems like it’s near zero.

              Not sure, most my work (and many people I know, especially since covid) these days gets paid in crypto because it's international, fast, easy and there are no limits (unlike banks who start AML freezing stuff willy-nilly). I declare everything as income and outgoing business income/expenses. Works fine. It's fast and convenient for non-crime payments; I pay people with it as well. Especially for large amounts.

              Also; I do not work in or with blockchain tech generally, but my clients started asking if they could pay in it this year (they also don't work in blockchain, but it's just far more convenient and faster and cheaper than SWIFT payments internationally).

              I also see no use for it vs local banks; most banking transactions locally here are instant and simple, but international money is still very annoying and can take a long time (and, as we have seen, often bounces or stalls for no visible reason at all).

              • pfortuny 3 days ago

                Yours is not the right question. The use of money has always been assumed anonymous (not the property owned, that is a different thing).

                Governments have a duty to collect taxes but do not have a duty to know anything about how people use their money.

                Governments exist as a need not as something which has “rights”.

                • seibelj 3 days ago

                  Others have basically made the same argument, but to me it comes down to power. Does the government need to know every financial transaction you make? For hundreds of years they couldn’t for technology reasons. Now they deeply desire it and have the means to do so. Would you want the government to have direct access to your brain and thoughts? I assume not. But if you have nothing to hide, is this really a problem? Why are you so worried? It’s why I don’t want the government to have instant access to everyone’s google searches. People use google as a quick extension to thinking, and if the government could see everything I’ve googled in my entire life I’m sure they could paint a picture of a crazy person.

                  Transacting in commerce is equal to freedom. I don’t want the government to instantly know everything I have ever bought in my life. And if you accept that under some threshold ($100? $1000?) the government should not instantly be informed, you’ve opened the door to (insert terrible thing here)! So either we give the government access to everything instantly or we restrict it for some reason. I am in favor of restricting.

                  • scandox 3 days ago

                    I think the issue we all dance around is that ultimately financial privacy provides the only reasonable means of funding anti state violence.

                    Of course this is always immediately labelled terrorism, but at many times in history has been the only means of major social change.

                    So in essence if you can't secretly buy weapons you can't have an IRA etc...

                    • gabcoh 2 days ago

                      Has crypto ever been used for this purpose? And haven’t many other forms of currency effectively been used for this purpose in the past?

                      • scandox 2 days ago

                        As far as I knew we were talking not about Crypto but about the need for financial privacy.

                      • cycomanic 3 days ago

                        I have to say this has been the only satisfactory answer in this thread.

                      • npongratz 2 days ago

                        > I am generally a very privacy-minded person, but serious question here: is there any legitimate use case for financial privacy from the authorities?

                        One might perform an action today that is legal and considered moral or amoral. When the authoritarian regime changes tomorrow, I would not want those legal/(a)moral actions to be retroactively criminalized.

                        • DennisP 3 days ago

                          Corporations are not going to put transactions on blockchains without strong privacy, for competitive reasons. It's probably not practical to do that while also leaving a backdoor for the authorities, but even if it were, it'd just be a tweaked version of the same technology.

                          • auganov 3 days ago

                            > I am generally a very privacy-minded person, but serious question here: is there any legitimate use case for financial privacy from the authorities? I don’t mean “ideologically, I am upset that the government can see I buy too many pastries”.

                            And the vast majority of people have very little to gain from all other kinds of privacy. The government wouldn't find anything interesting in my IM messages either.

                            Most people who really need it are probably up to no good too.

                            I'm on both sides of this debate. I think most privacy issues are overblown by a small set of zealots. But at the same time I don't see much difference between financial privacy and whichever other kind.

                          • ipython 3 days ago

                            Not to get too far off topic, but like many problems transitioning from the physical realm to the digital, we have to recognize that there are logistical challenges associated with carrying, transporting and exchanging cash that simply don’t exist in the digital realm. These logistical challenges essentially force legitimate transactions into the “visible” ledger and off the “private” books for most entities. Here are a few examples.

                            Drug smuggling cartels are experts in transporting and accounting for cash across long distances and national borders. However even they have an issue with physical storage of cash - to the point where they had too much cash to even store, leading to piles of cash buried underground, getting eaten by rodents etc. this would not be an issue with cryptocurrency.

                            Cash is still traceable in a crude fashion- unique serial numbers on each bill. This enables some level of oversight while keeping most transactions essentially private. It also enables replacement of damaged currency, something not possible with crypto currencies.

                            Transacting in cash has a real economic and logistical cost, whereas crypto currencies essentially have none. You have to physically meet to exchange cash- imagine the difference between paying a ransomware in cash versus cryptocurrency from the perspective of the attacker. Same as above, you have a literal physical limitation on the amount of cash you can transact due to weight and volume of the bills themselves. You may also have to enlist (and trust and pay off) intermediaries to transport the cash, representing a real economic cost to transact privately in cash. Not to mention the possibility of surveillance.

                            Honestly the best yet still flawed analogy I can come up with when thinking about the differences between cryptocurrency and cash is remembering back to why I hated high school physics so much. Who cares about a perfectly spherical cow on a frictionless surface? Cows aren’t perfectly round and there’s friction everywhere. I feel like cryptocurrency solves the spherical cow problem but doesn’t address the real messy world.

                            • gspr 3 days ago

                              I do want financial privacy. But I also want a sound and mild policy of inflation as managed by western central banks. Can I have both?

                              I suspect that as with so many other matters of privacy, most of the solution is legal and political rather than technical.

                              • SkyMarshal 3 days ago

                                Privacy and inflation in cryptocurrency are not technologically mutually exclusive, they’re mostly orthogonal. Eg, yes, technically you can have both.

                                The problem is that in purely a private, zero-knowledge cryptocurrency, it’s difficult or impossible to inspect the actual currency issuance rate and ensure that some Byzantine miner/validator hasn’t found a way to hack the issuance algorithm and issue more currency (to themselves) than the system is designed to. For example, ZCash had a famous bug regarding this issue a few years ago, that they patched before disclosing it.

                                That’s an ongoing technical challenge the industry is working on.

                                • im3w1l 3 days ago

                                  > The problem is that in purely a private, zero-knowledge cryptocurrency, it’s difficult or impossible to inspect the actual currency issuance rate

                                  Satoshi could have made mining reward increase at 2% per year, but very deliberately decided on hard cap on how many will exist. This decision made early adopters literally and metaphorically invested in bitcoin's success.

                                  Are you saying that some detail of zk-Snark makes that not possible for cryptocurrencies based on this technology?

                                  • SkyMarshal 3 days ago

                                    No I’m saying the exact opposite. The inflation schedule can be any arbitrary algorithm. It can be a fixed amount like Bitcoin, or a continually increasing one like your 2% example.

                                    Zk-snarks don’t change that. It’s still a choice by the developers based on the economic objectives they’re trying to achieve, and snarks don’t prevent that.

                                    But problem is that in a fully-shielded, 100% private, snark-based blockchain, it’s difficult or impossible to verify that the actual coin supply is what the whitepaper says it should be. Since all the tx’s are hidden, you can’t inspect the blockchain data and just count all the coins in UTXOs or account holdings to see what the total money supply is at any given time and reconcile it with what the issuance algorithm says it should be.

                                    • tromp 3 days ago

                                      Lack of transparent supply auditability is a feature not so much of zk-snarks but of Confidential Transactions, which use Pedersen commitments to obscure amounts. Knowing the discrete logarithm of just one particular point would completely break these commitments and all cryptocurrencies based on them, by allowing undetectable inflation. They thus require complete confidence in the computational hardness of the Elliptic Curve Discrete Log Problem.

                                      • SkyMarshal 2 days ago

                                        Yup, fwiw I'm not actually aware of a fully shielded zk-snark cryptocurrency in production yet, was just using that as a hypothetical example, like a ZCash with only z-addresses.

                                  • aspenmayer 3 days ago

                                    I’d like to know more about the bug mentioned in $ZEC, if you have a link?

                                    • dlubarov 3 days ago

                                      Not the parent, but I think he was referring to https://electriccoin.co/blog/zcash-counterfeiting-vulnerabil...

                                      • im3w1l 3 days ago

                                        Ouch what a nightmare. At that point it seems like the best way may be to start over? Like have everyone who can prove they have old-money get new-money on a first-come-first serve basis. If too much money shows up you know you got owned. Otherwise you are fine. If too much money shows up years down the line, you just deny them new-money, which screws over people who bought-and-forgot but everyone else is ok.

                                        • SkyMarshal 3 days ago

                                          Yup that’s it.

                                          • aspenmayer 3 days ago

                                            Even stranger are comments made in this link:

                                            https://electriccoin.co/blog/defense-against-counterfeiting-...

                                            Especially this part:

                                            >Upon detecting this condition, the Zcash Company would begin its investigation into the possible source of the vulnerability as well as which pool, or pools, are affected. If we are able to identify that the bug affects only a single shielded pool, we might choose to effectively deactivate that pool by invalidating any of its outgoing transactions. A necessary consequence of this action is that any legitimate funds would also be lost forever in the affected pool.

                                            The mechanisms for this remote disabling are not mentioned in detail, and I don’t really mind, but this feature seems difficult to square with their desire for transparency. It’s an anti-feature perhaps serving a justifiable goal, but if this feature is possible to be abused, how would we even know if it had been?

                                            • abecedarius 2 days ago

                                              I'm not sure what they mean there, but I'd guess they mean a hard fork. As with the Ethereum post-DAO fork, you don't have to accept it, but to the extent it seems legitimate, most of the value would go along.

                                  • Financial privacy is a political dead end. Aside from most governments wanting to snoop on essentially everything you do, they really, really want to know the state of your finances. Both domestically and internationally. Most governments will claim a stake in all income of their citizens, no matter where in the world the transaction occurs. This is why AML regulations exist essentially everywhere in the world.

                                    • jacobush 3 days ago

                                      I thought mostly the US wants a cut of their citizens earnings, even if abroad.

                                      • I think most countries will stop demanding taxes from you if you legitimately move to another country, though meeting the criteria for doing that can be tedious. The US doesn’t have such a system, but the way it works most expats won’t end up paying any taxes if they leave the states. Though they’ll still need to file a return.

                                        • gspr 1 day ago

                                          > I think most countries will stop demanding taxes from you if you legitimately move to another country

                                          Most is an understatement. Last I checked, it was all countries, except the US and the two bastions of freedom that are Eritrea and the Soviet Union (when it existed).

                                          > The US doesn’t have such a system, but the way it works most expats won’t end up paying any taxes if they leave the states. Though they’ll still need to file a return.

                                          Won't end up paying any taxes on earned income you mean. For any other income, it's a damn nightmare.

                                    • tromp 3 days ago

                                      For a cryptocurrency to be truly decentralized, its emission cannot depend on factors external to the blockchain.

                                      You can have any any predetermined mild inflation you want.

                                    • keyraycheck 3 days ago

                                      You might want to check out the report below. It should be a good explainer for importance of zero knowledge in context of blockchain (a bit more in context of scaling than privacy, but the fundamentals are the same). Our three cents to help explain why it is important.

                                      [1] https://ethworks.io/assets/download/zero-knowledge-blockchai...

                                      • Kudos 3 days ago

                                        What about the practical limitations with moving cash, this puts _some_ limits on criminal activity. How do we get at least that level of control with cryptocurrencies while maintaining privacy?

                                        • beders 3 days ago

                                          I keep reading these fantasies about how cryptocurrencies will keep the evil government out of your business: It won't. It can't.

                                          Unless you magically change the government, get rid of all influence by special interests and create a shadow economy at the same time.

                                          The old system will not go easily and not without a fight. Already gov organizations are readying their significant sources to track all of this, distributed ledger or not.

                                          How can I explain to you guys, that nothing you do on the internet is private. Nothing.

                                          • It seems zksnarks are also poised to be an important building block in scaling transaction throughput.

                                            It’s not the only example and it hasn’t launched just yet but checkout the Hermez Network[1].

                                            [1] https://hermez.io/

                                            [&] https://hermez.io/hermez-whitepaper.pdf

                                            • lomonosovoc 3 days ago

                                              What cryptocurrency would you recommend to use if privacy were one's goal?

                                          • capnorange 3 days ago

                                            To see zk-Snarks in action, there is a cool MMO space-conquest game based on it.

                                            http://zkga.me/

                                            https://blog.zkga.me/

                                            • tromp 3 days ago

                                              Another great and more extensive resource on zero knowledge proofs is available at

                                              http://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.html

                                              • amitport 3 days ago

                                                We need more papers like this. Very nice. I wonder though if this work would be recognized for academic progress in research institutions? Specifically, is it publishable in some top-tier journal? (If so, which one?)

                                                • lopsidedBrain 3 days ago

                                                  One of my highest-cited papers didn't pass peer-review. But that's okay. The citations (of the pre-print version) speak for themselves. If papers like these are good enough that new students entering the field use it as a ramp-up resource, they won't hesitate to cite it over and over again when they submit something for peer-review.

                                                  So journal publication is not the only means of recognition.

                                                  Speaking of which, computer science is a bit weird in that conference papers tend to have higher visibility than journals, even though the latter still has some of its grandfathered glory. Not all conferences are equal, obviously. Some have a more rigorous submission process than others. But our field definitely carries a bit of skepticism about the value added by journal publishers.

                                                  • red_admiral 3 days ago

                                                    In crypto, eprint.iacr.org is where you want your paper to be - it's their own version of arXiv, so I'm almost a bit surprised this isn't published there.

                                                    If your paper is good, on eprint and you spread the word a bit, then it will get citations - often more than if you publish in a 2nd tier conference - and when it's popular enough then eventually one of the main conferences (journals are less popular in crypto) will accept it in some form. This happened among other things to several of Dan Bernstein's papers (the guy who invented curve25519 among other things).

                                                    • baby 2 days ago

                                                      I wrote a similar survey a while ago on lattice attacks on RSA[1] and got it rejected from eprint because it was not new research. Anecdotal but there is that.

                                                      [1]: https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/sur...

                                                      On the other hands there are a number of such "tutorials" being published on eprint, so I think if it's sort of random on a pre-print, then it must be pretty hard to publish this sort of papers in serious journals.

                                                      • rrmm 3 days ago

                                                        They'd be published as review articles or distributed by the academic institution as technical papers or technical reports.

                                                      • krcz 3 days ago

                                                        By coincidence, I finished reading that document yesterday. Really good one, it builds zk-SNARK understanding step by step. Sometimes though it possibly goes to deep in explaining basic concepts - I'm not sure if someone who didn't have experience with modular arithmetic would be able to get to understand it in a way that would be enough for the whole concept. Assuming basic mathematics knowledge as modular arithmetic, polynomials, interpolation, etc. might be a better approach in my feeling, but YMMV.