What are zk-SNARKs?

The Complete Guide to Crypto's Most Powerful Proofs

by O(1) Labs

2019-10-25






Get Started

Zero Knowledge Proofs. zk-SNARKs. These terms are frequently used in cryptocurrency circles, often in the context of making transactions private. In the context of Coda Protocol, they are an essential part of our principal innovation: a small, constant-sized blockchain. Their origins extend back to 1985, when zero knowledge proofs were first explained in the paper “The Knowledge Complexity of Interactive Proof-Systems.” But the question remains: what actually are they?

The central vision of cryptocurrencies is to enable indivduals to decrease their reliance on centralized powers and third parties intermediaries. zk-SNARKs are an innovation that can make that vision a reality. Yet, because zk-SNARKs are so complex, it’s challenging to find clear, accessible resources. Our team of cryptographers and engineers compiled, summarized and reviewed the available resources to help you get started, whether you’re a beginner or an expert. Know of a resource we should include? Let us know in the comments section below.

First, Izaak and Vanishree, two members of our cryptography team who have devoted their lives to the study of zk-SNARKS, will get you started with an introduction.

Zero-knowledge Proofs: An Intuitive Explanation
Vanishee Rao, a cryptographer working on Coda Protocol, offers up this explanation, using the classic 3 coloring problem to introduce key concepts including soundness, zero-knowledgness, and verifiers. Highly visual, this short (<5 minute) read is a great place to start.

Read more →

Coda Protocol Testnet [Beta] Retrospective - Phase 2.2

by Christine Yip & Pranay Mohan

2019-10-24

Testnet Beta Phase 2.2 was a busy period, marked by a lot of tinkering and breaking. The community rose up to the challenge to increase the transaction throughput during ‘Magic Window’ hours, and a new bug soon came to the surface, which the team can now investigate. In the meantime, there are also notable technical developments in the protocol that will be rolled out with the new release of this week, called “Van-Helsing”. We’re excited to see how the testing with the community will go using these new components. If the community reaches a transaction objective together, we will reward everyone with 2X bonus points! Read on for more details and sign up here to receive testnet updates.

Table of Contents

Release 2.3 Challenges

Retrospective Release 2.2 and Updates in 2.3

Community in Action

Read more →

Coda Protocol Testnet [Beta] Retrospective - Phase 2.1

by Christine Yip & Pranay Mohan

2019-10-17

Phase 2 of Coda’s Public Testnet Beta kicked off with a lot of interest in the staking challenge. 70 people signed up to stake on the new release and about 50 people ran a testnet node. Together, the community was going strong and racked up almost 100k testnet points* on the new Phase 2 leaderboard. Want to stay updated about Coda’s testnet? Sign up for testnet updates here.

Table of Contents

Release 2.2 Challenges

Retrospective Release 2.1 and Updates in 2.2

Community in Action

Read more →

O(1) Labs Announces Formation of Testnet Advisory Board

by O(1) Labs

2019-10-07

San Francisco, CA - O(1) Labs, the software development company building Coda Protocol, announced that it has established a Testnet Advisory Board, and will welcome two industry leaders, Zaki Manian and Luke Youngblood, as technical advisors.

O(1) Labs also announced the start of the next phase of Coda Protocol’s testnet in beta, starting with release 2.1, which will allow users to operate nodes on a cryptocurrency network utilizing their succinct blockchain technology.

Coda Protocol, the first succinct blockchain that can remain decentralized at scale, has seen rapid progression and advanced the state-of-the-art in significant ways. Some of Coda’s breakthroughs include:

  • Usage of recursive zk-SNARKs to facilitate a succinct blockchain
  • Production implementation of a modified Ouroboros Proof of Stake consensus algorithm
  • Development of snarky, an OCaml DSL for writing zk-SNARKs
  • First marketplace for zk-SNARK proofs, the ‘SNARKetplace’

The Testnet Advisory Board is in keeping with the collaborative nature of the blockchain industry. According to Emre Tekisalp, Director of Business Development at O(1) Labs, ‘We’re seeing a cambrian explosion of open source and peer-to-peer networks. As the industry iterates on what will become mission critical infrastructure for the internet, it’s imperative that we collaborate.’

Read more →

Coda Protocol Testnet [Beta] Retrospective - Phase 1

by Christine Yip & Pranay Mohan

2019-09-20

Coda Protocol’s Phase 1 of the public Testnet Beta has concluded! We had 8 successful weeks of testnet on a 1-week release schedule. The technical advancement that was made would not have been possible without the participation of enthusiastic members in the community.

Some important milestones that we hit include:

  • 126 community members participated
  • 96 users connected to the testnet
  • 270,000+ Testnet points* were awarded
  • 10 really cool and useful testnet related resources were created by the community (check them out under community highlights)

After Phase 1, we will progress to more stable, and scalable testnet releases and will move from a rapid iteration cycle of a 1-week cadence to a 2-week cadence to support this, read on to check out what new and exciting things to expect, and sign up here to be notified via email when public Testnet Beta Phase 2 is open!

Table of Contents

Read more →

Coda Protocol Testnet [Beta] Retrospective — Week 8

by Christine Yip & Pranay Mohan

2019-09-18

It has been 8 weeks since Coda Protocol’s Public Testnet Beta was launched. Last week’s testing provided us with interesting findings in the protocol - read on to see how a bug (!) saved the day.

For the next testnet release “Filet Mignon”, there will be an opportunity for testnet users to participate in the upcoming Staking Challenge. The deadline for registration is September 24th 2PM UTC-7, so be sure to check out the instructions here and sign up on time if you want to participate!

Next week, we will have a break from the testnet. Stay tuned, we will announce soon what happens next!

Table of Contents

Retrospective Week 8

Community Awards

Read more →

Coda Protocol Testnet [Beta] Retrospective — Week 7

by Christine Yip & Pranay Mohan

2019-09-11

We’ve arrived at the 8th week since Testnet [Beta] was launched. Last week, we saw about 40 testnet users participating in the ‘Grab Bag’ challenges and members becoming leaders in the growing community. Read on to check out the testnet findings of last week and the exciting things that the Codans have been building. Together, the community racked up more than 250,000 Testnet Points* (check out the leaderboard) and this week, we have a new challenge again!

Table of Contents

Week 8 Challenges

Retrospective Week 7

Community in Action

Read more →

Coda Protocol Testnet [Beta] Retrospective — Week 6

by Christine Yip & Pranay Mohan

2019-09-04

A new testnet release ‘Grab Bag’ is here with an entire set of new, fun challenges! We also have an exclusive BONUS this week for new members! Join this week to get double Testnet Points* on ‘New Member’ challenges and place yourself on the leaderboard with 100+ other members! (Read on for details on challenges.)

Table of Contents

Public Testnet Beta Milestone

Week 7 Challenges

Retrospective Week 6

Read more →

Coda Protocol Testnet [Beta] Retrospective — Week 5

by Christine Yip & Pranay Mohan

2019-08-27

Welcome to week 6 of the Coda Public Testnet Beta. This week’s challenge, Something Snarky, is all about generating zk-SNARKs. Node operators will be competing to produce as many SNARKs as possible to sell to block producers on the snarketplace — read on for more details. In addition, we have a brand new leaderboard design to keep track of your place on the list.

Week 6 Challenges

Challenge #15 — Something Snarky:

This week’s challenge makes snark work the primary objective. Node operators that produce at least one SNARK will get 1000 pts*.

BONUS: Top 3 node operators who are able to sell the most SNARKs in the snarketplace (meaning your SNARK was not just produced, but also selected by a block producer) will win an additional 3000, 2000, and 1000 pts* respectively. Hint — your SNARKs are more likely to be bought if the fees are lower, so feel free to experiment with the economics! ;)

Read more →

Coda Protocol Testnet [Beta] Retrospective — Week 4

by Christine Yip & Pranay Mohan

2019-08-20

Today, we’ve arrived at the fifth week since Coda’s first public testnet [BETA] was released. It has been incredibly fun to dive in with the core group of our community evangelists. While stress-testing the network, testing main parts of the core protocol, staking, and producing blocks, unexpected situations arised and the community graciously embraced these surprises. The testing provided us with invaluable feedback, and instead of having a new testnet release, we will focus on improving the infrastructure and stabilizing the testnet this week. The community is also invited to join us in this retrospective week, and earn Testnet Points* along the way! Read on for more details.

Week 5 Challenges

The total number of Testnet Points* that 105 users racked up on the leaderboard went over 140,000 last week! If you missed out on previous challenges, it is not too late to catch up, since we’re having our biggest points* challenge yet this week! You can also earn bonus points* if you were active in the previous week(s), see Challenge #11 ‘Don’t Break the Chain!’. Check out all challenges here.

New challenges are here for you to rack up more Testnet Points*!

Challenge #12 “CLI FYI”

Read more →

Coda Protocol Testnet [Beta] Retrospective — Week 3

by Christine Yip & Pranay Mohan

2019-08-13

This is the fourth week that the Coda public testnet has been live! Last week, with the help of the early adopters in the community, we successfully stress-tested the network with increased transaction throughput, allowing us to identify potential issues and resolve them before the mainnet launch. A big thanks to all the testnet participants who have stayed active through the entire process, we wouldn’t be able to test out the protocol in the wild without all your contributions!

This week’s testnet release is called ‘Medium Rare’ - a pun on steak, since users will be staking their coda this week to earn new Testnet Points*.

Week 4 Challenges

More challenges are ready for you to win points*! Last week, we saw some fierce competition as participants battled to see who could send the most transactions. Read on for winners of last week and see where you rank now on the leaderboard.

This week’s challenges:

Read more →

Coda Protocol Testnet [Beta] Retrospective — Week 2

by Christine Yip & Pranay Mohan

2019-08-07

This week, we have a new release, ‘Share the Wealth’ and three new challenges to help you earn Testnet points*.

Since we launched Coda’s first public testnet in beta on July 24th, 2019, we’ve had 56 Codans connect and 74 rank on the leaderboard. Competition has been pretty fierce, but fellow Codans are a helpful bunch. Head on over to Discord and Docs to start tackling challenges!

Week 3 Challenges

Fresh challenges are here! See where you rank on the leaderboard and post some points for the week.

Challenge #6 ‘Nice to Meet You’

Read more →

Coda Protocol Testnet [Beta] Retrospective — Week 1

by Claire Kart

2019-07-29

Coda Protocol launched its first public testnet in beta on July 24th 2019 at 2pm PST. As the first succinct blockchain, it generated significant interest from the community.

Hello Coda balloons

The Community in Action

Our community of early-adopters showed up in full-force, with over 250 people joining Discord. Of those, 32 people successfully ran a Coda node, connected to the network, and sent their first transaction. An additional 32 people started playing around in the documentation, and are working on getting their Coda nodes set up for Week 2.

The community is now active in all parts of the globe, with particularly strong participation coming from Australia, China, Europe, Russia, and North America. One community member, turbotrainedbamboo, created a cool visualization of the peers he was chatting to on 07.29.2019 at 7:16 PM PST and shared it with the community.

Map of testnet participants spread across North America, Europe and Asia.

It’s clear from the conversations on the Coda Discord server that our community is highly-technical, loves a challenge, and is passionate about the long-term potential of establishing the foundations of a new, decentralized economic system.

With the release of the testnet beta, we also launched Testnet Points* to recognize community members’ contributions to the testnet and the weekly challenges. We didn’t really anticipate how popular the point system would be… but the whole team was receiving messages from every channel like this all week:

Read more →

O(1) Labs Releases Testnet [Beta] for Coda Protocol, the First Succinct Blockchain

by Claire Kart

2019-07-24

We’re thrilled to announce that Coda Protocol launched its first public testnet in Beta today, July 24th 2019 at 2pm PST. We’ve seen interest from more than 700 members of our community in joining, so we expect that this will be an exciting and engaging process thanks to the efforts of a core group of our community evangelists.

In this blog post, we will introduce Coda at a high level, including our motivations, philosophy, and technology innovations, as well as share a bit more about the testnet process and how the community can get involved.

About Coda

At the core of blockchains and cryptocurrencies is that they allow us to trade centralized institutions for decentralized networks. At a base, technological level, this comes from a distributed network of validators being able to come to consensus about the state of the blockchain. Put a different way, networks are decentralized in large part because of the breadth of the network of validators who can independently validate them.

A decade into the blockchain and cryptocurrency industry, however, we’re discovering an interesting quirk creating a hidden force for centralization. Blockchains are, increasingly, victims of their own success.

As a blockchain is utilized more and more (a good thing), the chain becomes longer and longer. As this happens, it decreases the pool of people who have the computational and bandwidth capacity to participate in validating and securing the network (a bad thing). Over time, this pushes blockchains towards a new form of centralization with only those with the highest network and computational capacity at the top of the food chain.

Read more →

Zero-knowledge Proofs: An Intuitive Explanation

by Vanishree Rao

2019-07-08

Zero-knowledge proofs (ZKPs) are a powerful cryptographic primitive that enables you to prove that you have a secret, without revealing it to anyone. If you are hearing about ZKPs for the first time, you are likely to say “Hah! That sounds impossible.” Read on to get an intuitive understanding of what they are. But first, some background. ZKPs were invented by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. Ever since, ZKPs have been one of the most active areas of research in Cryptography. Moreover, recently, they are enjoying significant impact on real-world applications, specifically on blockchain technologies. Zcash, a pioneering blockchain project, employed ZKPs to achieve anonymity in financial transactions. At O(1)Labs, we are building CODA, the first succinct blockchain, using ZKPs. No matter how many transactions are recorded on the blockchain, the blockchain remains at most the size of a few tweets.

What are Zero-knowledge Proofs?

The purpose of zero-knowledge proofs is to convince someone you know something without revealing what that thing is. For example, you might want to convince someone that you know the solution to a puzzle without giving them the solution.

Let’s look at a particular puzzle to see how you can accomplish exactly this.

A Puzzle called 3-Coloring.

The 3-coloring puzzle can be described as follows. You are given a graph of nodes and edges (like in the figure below). The task is to find a “3-coloring” to the graph, which is a coloring of the nodes with three different colors in such a way that no two adjacent nodes have the same color.

Figure: An uncolored graph.
Figure: A colored graph.

A Zero-knowledge Proof for the 3-coloring Puzzle.

We will construct a ZKP protocol for the 3-coloring puzzle. Before that, let’s quickly recall the two properties we are looking for in the protocol.

Read more →

Coda + Dekrypt: The SNARK Challenge

A global competition to speed up the SNARK prover

by Coda

2019-05-09

Coda Protocol, CoinList, and DeKrypt are partnering to launch a $100k global public research challenge to dramatically speed up zk-SNARKs. We expect the contest to produce huge advancements in the state of the art. We’ll be contributing all of those advancements back to the public domain with a permissive open-source license that allows them to be used by the broader crypto ecosystem.

SNARKs have been developing rapidly in the past few years, and in crypto they’re one of the most promising ways to bring scalability and privacy to blockchains. But in many ways we’re still at the surface of what’s possible. This gap between opportunity and current state is due to the significant increases in SNARK performance that remain to be unlocked. For example, while many of the computational steps involved in SNARK proving are perfectly parallelizable, this property hasn’t yet been fully implemented on hardware designed to exploit it, such as GPUs.

In the open and collaborative spirit of the crypto space, we’re partnering with teams from around the ecosystem to improve zk-SNARKs and share the resulting research with the broader community. CoinList and DeKrypt will be co-organizers, and sponsors include the ZCash Foundation, Tezos, and Protocol Labs. In addition to the contest, we’ll be hosting regular office hours from top researchers and practitioners and sending out online tutorials. There will be tracks to improve zkSNARKs through both cryptographic improvements and optimizing existing implementations. Sign up here if you’d like to get involved.

Read more →

New O(1) Labs Funding and Coda in 2019

Announcing a fundraise in O(1) Labs and new ways community members will be able to contribute to Coda

by Evan Shapiro

2019-04-02

Tldr: We raised a new round of funding and over the next few months will be inviting users to become more deeply involved with Coda, a more accessible cryptocurrency. Scroll to the bottom to learn how you can participate.

We’re excited to announce that last fall, we finished a new round of funding for O(1) Labs! We raised $15M from a group of fantastic investors including Accomplice, Coinbase Ventures, Paradigm, and General Catalyst. These excellent funds, along with a few other high value-add investors are joined by additional support from our amazing seed investors including MetaStable, PolyChain, Electric Capital, and others.

Since day 1, we have been focused on radically expanding the reach of cryptocurrencies by addressing the root issues behind blockchain’s scalability challenges. We believe our solution to this problem, Coda, will greatly expand the level of decentralization available to a cryptocurrency and the applications it is capable of. Our team of nearly 20 has executed aggressively, and today we are excited to share plans around what’s next on our path to Coda’s launch.

Coda

When Bitcoin was created, it showed the world that it is possible to create any economic system we want, unbound by the historical limitations of nation states and large organizations.

Since then though, cryptocurrencies have run into a problem; as they have become more popular, control and usage has tended towards centralization. No matter what the chain, both consensus and usage has centralized towards large mining pools, delegated proof of stake, and trusted third party validation.

Read more →

A SNARKy Exponential Function

Simulating real numbers using finite field arithmetic

by Izaak Meckler

2019-03-09

In Coda, we use the proof-of-stake protocol Ouroboros for consensus. Naturally since this is Coda, that means we have to check proofs-of-stake inside a SNARK.

A proof-of-stake for a person with some amount of stake \(a\) in Ouroboros is a random number \(s\) between 0 and 1 (which one provably has generated fairly) such that \(s\) is less than some threshold depending on \(a\). Concretely, that threshold is \(1 - (1/2)^{\frac{a}{T}}\) where \(T\) is the total amount of stake in the system.

It’s important to use a threshold of this form because it means that the density of blocks over time does not depend on the distribution of stake.

If you know anything about SNARKs, you know that inside of a SNARK all we can do is arithmetic (that is, addition and multiplication) in a finite field \(F_p\). It’s not at all clear how we can compute a fractional number raised to a fractional power!

We’ll go through a very cool technique for computing such a thing. All the code for doing what we’ll talk about is implemented using snarky and can be found here.

Read more →

Fast Accumulation on Streams

Succinctly Verifying Coda’s Ledger

by Brandon Kase

2018-12-20

1 If you’d rather consume this content in video form, watch this talk.

While developing Coda, we came across an interesting problem that uncovered a much more general and potentially widely applicable problem: Taking advantage of parallelism when combining a large amount of data streaming in over time. We were able to come up with a solution that scales up to any throughput optimally while simultaneously minimizing latency and space usage. We’re sharing our results with the hope that others dealing with manipulation of online data streams will find them interesting and applicable.1

Background

2 Equivalent to security as a full node.

The Coda cryptocurrency protocol is unique in that it uses a succinct blockchain. In Coda the blockchain is replaced by a tiny constant-sized cryptographic proof. This means that in the Coda protocol a user can sync with full-security2 instantly—users don’t have to wait to download thousands and thousands of blocks to verify the state of the network.

What is this tiny cryptographic proof? It’s called a zk-SNARK, or zero knowledge Succinct Non-interactive ARgument of Knowledge. zk-SNARKs let a program create a proof of a computation, then share that proof with anyone. Anyone with the proof can verify the computation very quickly, in just milliseconds, independent of how long the computation itself takes. While validating proofs is fast, creating them is quite slow, so creating this SNARK proof is much more computationally expensive. We use a few different SNARK proofs throughout Coda’s protocol, but the important one for this post is what we call the “Ledger Proof”.

Read more →

Functional programming + crypto reading list

by Brad Cohn

2018-04-01

Recently a candidate sent us a very thoughtful email asking what kind of knowledge we’re looking for in a candidate. It set off a discussion at the office, as we wondered what direction we could provide candidates who might not yet have all of the perfect qualifications.

Below is our response to the candidate, giving guidance on what kinds of knowledge we are looking for in candidates.


None of us came into this field knowing everything. In fact, we came from quite varied backgrounds, and we all have areas we’re more or less comfortable in. So even though I’ll be giving a more comprehensive list below, it’s much more important to be excited about learning new things than having any particular expertise, and we’d be interested in talking to any candidate that knows some things in the list below and is capable and energized to tackle more.

So, after some deliberation, here are some basic resources to get you started. For our company, knowing the basics in cryptography (and cryptocurrency), functional programming, and math is probably the most important.

Functional Programming

We’re building our protocol in OCaml, but you can learn the functional style in any functional programming language: Haskell, Scala, SML, and Elm are all great. You should be familiar with common techniques such as - modeling with types - how to read type signatures and recognize monads - algebraic data types - programming in an immutable style - higher order functions - pattern matching - recursion and so on.

Read more →

Snarky: A high-level language for verifiable computation

by Izaak Meckler

2018-03-11

Living in the world today requires giving up a lot of control. We give up control of our financial lives to banks and unaccountable credit bureaus. We give up control of our most intimate data to use online services like Facebook, Amazon, and Google. We give up control of our elections to voting-system companies who run opaque and unauditable elections. We even give up some control over our understanding of the world through exposure to false or misleading news stories.

But it doesn’t have to be this way. Cryptography as a discipline provides us with some of the tools necessary to regain some of this control over our resources and data while reducing the need to trust unaccountable actors.

One such tool is verifiable computation. A verifiable computation is a computation that produces an output along with a proof certifying something about that output. Until very recently, verifiable computation has been mostly theoretical, but recent developments in zk-SNARK constructions have helped maked it practical.

Verifiable computation makes it possible for you to be confident about exactly what other people are doing with your data. For example, it enables

  • Online services that are forced to be transparent about what data of yours they have and how they are using it.
  • Auditable elections that protect the privacy of your vote.
  • Publishing stories that provably come from a reliable source, without leaking what that source is.
  • Sending money to others without yielding control of your account or your privacy.

Verifiable computation is powered by zk-SNARKs. Right now, however, progamming directly with SNARKs is comparable to writing machine code by hand, and trusting “SNARK machine code” is a lot like trusting a compiled binary without the source code.

Read more →