MIT Review Acclaims zk-SNARKs, but zk-STARKs May Steal the Show

As much as we love the convenience of the internet, our privacy is at great risk whenever we go on social media, check our credit reports, grab a ride, or simply log into a fitness app. Our need to protect our information encompasses much more than financial transactions with a few cryptocurrencies.

In the United States alone, the staggering number of data breaches shows the need for a better privacy solution, and zk-SNARKs or zk-STARKs are poised to fill that need. This year, the Cambridge Analytica data mining scandal affected more than 87 million Facebook users, and the WSJ predicts its repercussions will be huge. Last year, the Equifax data breach shared the social security numbers and dates of birth for more than half the nation. Meanwhile, an Uber hack exposed data from 57 million customers and drivers, and the MyFitnessPal app leaked usernames and passwords of more than 150 million users.

zk-SNARKs and zk-STARKs are two cryptographic protocols that could help prevent personal information from being vulnerable to these types of database breaches in the first place.

The Promise of Privacy: zk-SNARKs

This month, zk-SNARKs were included on an MIT Tech Review list of the 10 Breakthrough Technologies of 2018 among AI developments, 3D metal printing, and a smart city that Alphabet is building from the ground up.

zk-SNARKs protect your privacy, allowing you to prove who you are without having to give away specific details relating to your identity. Some of the potential uses cited in MIT’s article were verifying you’re over 18 without having to share your date of birth, and proving you have enough money in your bank account as collateral without having to give away account details like your exact balance.

Implementation of zk-SNARKs

zk-SNARKs are already running on cryptocurrency Zcash and JP Morgan Chase’s blockchain-based payment system. Both protocols have also grabbed the attention of Vitalik Buterin and the Ethereum foundation, including this exploration of zk-STARKs last year by Buterin. zk-SNARKs have been in the works since the 1980s, but it wasn’t until these recent cryptocurrency applications that interest in them really peaked.

Adding zk-SNARKs brings a layer of privacy previously inaccessible with most cryptocurrencies, traditional passwords, and even two-factor authentication. zk-SNARKs stands for zero-knowledge succinct non-interactive argument of knowledge, while zk-STARKs represents zero-knowledge succinct transparent argument of knowledge.

Potential Problems with zk-SNARKs

If zk-SNARKs sounds too good to be true, you’re onto something. While the world needs a privacy measure to address hacks, privacy breaches, and identity theft, zk-SNARKs need to overcome major hurdles to be a practical privacy solution.

Setting up zk-SNARKs requires a trusted setup that creates a very uncomfortable situation. Take Zcash’s launch as an example: a team of six developers around the world followed a set of instructions on a DVD to add the zk-SNARKs protocol to its blockchain. Essentially, each member generated one shard, or section, of the password to control Zcash. Gaining this control over all six shards would allow a bad actor to create additional tokens or steal funds.

Once the developers had run the code to generate their respective pieces of the password, each supposedly destroyed their portion of the key, some going as far as to drill holes into their hard drives. In this setup, at least one member must destroy their shard, so no one can find the entire key. This means, in theory, that even if the other five developers colluded to share their shards, they still wouldn’t have access, and it would be difficult to figure out the missing piece.  

Later, Zcash performed a larger trusted setup ceremony called “Powers of Tau”, with somewhere between 100 and 1,000 people running the protocol and destroying their shards of the key, some ceremoniously destroying their hardware in the process.

Though this higher number of participants could make things safer, there’s no true way to know it worked, and there’s no way to ensure a fake Zcash isn’t valued as the real Zcash. If Ethereum were to implement zk-SNARKs, it could take thousands of participants to run this kind of scenario unless there were a way around it.

zk-SNARKs are also slow and fairly expensive to implement right now, but this may not always be the case. One implementation, Secure Remote Password protocol (SRP), uses zk-SNARKs so you can log into your account by answering some true or false questions rather than by providing your password. This go-around proves you have the information without ever putting it on a server where a third-party could use it to access your account.

Zk-STARKs: A Better Privacy Breakthrough?

zk-STARKs, on the other hand, are being touted as a less costly and faster alternative to zk-SNARKs. Their biggest advantage is that no trusted setup is required.

Zcash’s founding scientist and zk-SNARKs researcher Professor Eli Ben-Sasson explains, “zk-STARKs use public key (asymmetric) cryptography to establish security. zk-STARKs instead requires a leaner symmetric cryptography, namely, collision resistant hash functions, and thus removes the need for a trusted setup. These same techniques also eliminate the number-theoretic assumptions of zk-SNARKs (and BulletProofs) that are computationally expensive and prone to attack by quantum computers. This makes zk-STARKs both faster to generate and post-quantum secure.” We’re about to jump into some of the technical reasons as to why zk-STARKs work differently from zk-SNARKs.

The zk-STARKs white paper states, “No ZK system realized thus far in code (including that used by cryptocurrencies like Zcash) has achieved both transparency and exponential verification speedup, simultaneously, for general computations.”

Ben-Sasson elaborates on this exponential verification method, saying, “If T represents the number of machine cycles of a computation, then the time to verify a zk-STARK for that computation, as a function of T, is log(T), which is exponentially smaller than T. In contrast, for a computation used only once, zk-SNARK verification … takes exponentially more time than a zk-STARK verification, [and] most of this added computation time is due to the trusted setup.”

When asked how zk-STARKs could help alleviate the number of privacy breaches over time, Ben-Sasson conjectures, “Permissionless blockchains will be the early adopters, followed by conventional businesses. Businesses will be pressured to adapt to the higher standards of transparency and accountability offered by zk-STARKs. As a result, citizens will enjoy a higher level of security and privacy from businesses and organizations who collect and store their personal data.”

To put it simply, zk-SNARKs are like building a top-secret blanket fort with your friends. You each have to assemble all the blankets in just the right way and celebratorily hide the evidence of your fort from your nosey older sister. You also have to put in a lot of effort to keep the sofa cushion walls up, and it will take you more time overall. zk-STARKs, on the other hand, are like a foldable tent you can pull right out of the box. It may not require all the effort and secrecy, but it means you’ll have more time to play flashlight games and tell ghost stories.

A Push for Privacy

Leaders in cryptographic research (i.e., the pioneers of many of the biggest existing and upcoming cryptocurrency projects) are looking into both zk-SNARKs and zk-STARKs. If one were added as an option to the Ethereum platform, you could choose a privacy option to keep your transactions hidden.

There’s a big misconception that transactions on blockchains like Bitcoin, Litecoin, and Ethereum are untrackable. While transactions may appear anonymous because they use long address codes, it is possible to piece together someone’s identity and account balances by tracking the addresses on their public ledgers and elsewhere, especially when someone always uses the same address.

Advances in Privacy Tech

As both zero-knowledge protocols undergo testing on blockchains, the cryptocurrency community is actively testing zk-SNARKs and is likely to test zk-STARKs soon as well. There are also other privacy coins like Monero tackling privacy, at least when it comes to spending.

Monero works by hiding a sender’s identity in a couple of ways, using stealth addresses with one-time destination public keys. It obscures a sender’s IP address and uses a ring signature, which combines a sender’s output address with a group of other possible sender addresses chosen randomly from the Monero blockchain, making it impossible to tell which transaction went where. Ring signatures make it look like a transaction could have been initiated by anyone in a group, kind of like someone with very illegible handwriting signing a check from a group checking account.

In contrast, zk-SNARKs and zk-STARKs fundamentally change how data is shared instead of creating a smoke trail around who sent what. Both are much-needed developments towards protecting our privacy. As Ethereum, banks, and others seek privacy measures in the wake of the increasing amount of data breaches of our sensitive information, zk-SNARKs and zk-STARKs will both be put to the test. Whether it’s either of these or something new, may the best proof win – it’s vitally needed.