Announcements

Piazza course schedule lists all remaining assignments

Homework

• HW 7 due Friday 4/7
• Can re-submit each of HW1 through HW6 one more time, until Friday 4/14

Project

• Sign up for a team by 4/7 (only 8 of you have signed up so far)
• First draft due 4/21, and final draft due 5/1

Final Exam on Monday, May 8 at 9-11am

Recap of the semester

Throughout this course, we have studied four fundamental topics.

1. Cryptocurrencies and the blockchains within them, which enable financial transactions in a decentralized way, without the need to give your money to trusted intermediaries (aka, banks).

2. Broadcast protocols in the (a)synchronous setting, which enable consensus over the Internet without needing to rely on trusted intermediaries (aka, leaders).

3. Secure multi-party computation, which enables data analysis without the need to give your data to trusted intermediaries (aka, clouds).

4. Zero knowledge proofs, which enable the world to hold an entity (such as a bank, leader, cloud, or any one of us) accountable, without the need for trusted intermediaries (aka, auditors).

The first two topics provide integrity and availability, and the final two topics added confidentiality as a concern to protect.

Still though, hopefully you see a theme across all four topics:

The tools in this course allow for data-driven decision making, without the need to place blind trust in another company or person.

To be clear: it's perfectly fine to trust other people -- indeed, forming relationships is a fundamental part of being human. And there is value to be gained by building social, civic, and political structures.

But it's not so good if you are forced to trust a random intermediary just to get things done (either in the physical or digital world), and this problem is exacerbated if you cannot verify their behavior to know whether they are worthy of your trust.

By using these and other tools for data security and privacy, the goal is to:

1. Reduce the level of trust required in other entities.
2. Understand exactly what you are trusting other entities to do (i.e., what could go wrong, and how many of them need to collude in what ways for a bad outcome to occur).
3. Verify that trusted entities are acting correctly.

“Cryptography is how people get things done when they need one another, don’t fully trust one another, and have adversaries actively trying to screw things up.”

– Ben Adida

These four topics of cryptocurrencies/blockchains, broadcast & consensus algorithms, secure multi-party computation, and zero knowledge proofs are all of the topics I wanted to cover in this course. So in some sense, we are done!

...Well, not quite. So far we have studied each of these topics in isolation. For the rest of the semester, let's look at what happens when we combine them together.

Spoiler: we can build really powerful data science tools this way!

Lecture 19: Zero Knowledge on a Blockchain

Recap: zero knowledge proofs

Zero knowledge solves a seemingly-impossible problem:

Can a prover convince a verifier that a statement is true, without revealing the evidence or reason why?

The prover could be trying to convince a designated verifier Victor, or might want to post a single proof to the entire world.

prover Peggy($x, w$)		verifier Victor($x$)
	$\underset{\longleftarrow}{\pi} \\ \longrightarrow \\ \vdots \\ \longrightarrow $	output: Accept or Reject

The performance of a ZK proof depends on:

• How much time it takes for the prover to compute the proof, and for the verifier to check it.
• The communication between the parties -- that is, how large the proof is in size.
• The number of rounds of interaction between the prover and verifier.

We studied two types of zero knowledge systems in this course.

1. ZK based on "MPC in the head," which has a faster prover runtime, but the resulting proofs are larger.

2. zk-SNARKs, which have small proofs and (slightly) faster verification time, but slow proof computing time.

Additionally, both of these proofs can be made non-interactive using the Fiat-Shamir transform.

The main idea here is to have the prover choose the random challenge (rather than the verifier), but use a cryptographic hash function so that the prover's choice is fixed.

Recap: blockchains & cryptocurrencies

Cryptocurrencies are digital version of a banking system, where people can transfer money to each other electronically over the Internet without the need for a single trusted banking authority.

It should be "secure" against "powerful adversaries."

Alice		Mallory		Bob
	$\longrightarrow$		$\longrightarrow$

In the physical world, when Bob receives a check from Alice, he may be suspicious that Alice is trying to deceive him. He needs to be able to verify the following three properties.

1. Alice properly signed the check

2. Alice possesses $1 in her bank account

3. Alice does not double spend the money by writing a check to someone else at the same time

In the digital world, cryptocurrencies like Bitcoin solve these security challenges through replication. Specifically, Bitcoin publishes transaction data in a blockchain.

A blockchain is basically a continuous version of a broadcast. Everyone can post to the (effectively append-only) blockchain, and there is eventual consensus about its contents.

[Image source: Nakamoto whitepaper]

In a blockchain, you could consider one of the following two models.

1. An account model where you record every account and its current balance. When a transaction is submitted, the bank updates its record of accounts by debiting the sender and crediting the receiver.
2. An unspent transaction model (or UTXO), where the public ledger stores the transactions and everyone keeps track of which ones are still unspent.

There are ~three~ four types of participants within Bitcoin. Each participant may (but doesn't have to) hold one or more secret keys for a digital signature scheme.

• A miner tries to write new blocks on the blockchain by solving the proof-of-work puzzle.

• A node stores the entire state of the blockchain. (Note: this can be large! The Bitcoin blockchain is currently 470 gigabytes in size.)

• A light client only needs to hold the block headers (which are currently about 62 MB in size).

• An ultralight client has no data whatsoever about the blockchain, and blindly trusts a node. This is what happened when we visited https://mempool.space/ and screen-captured the image above. Our browser knew nothing about the blockchain, and just trusts that the above image corresponds to the real blockchain.

19.1 The Zcash cryptocurrency

Bitcoin achieved its goal of a secure, decentralized ledger through replication -- that is, making every financial public to the world.

Additionally, the blockchain is stored in so many places that it would be effectively impossible for all of us to "forget" a transaction, and the proof-of-work puzzle ensures that we won't be fooled into undoing a transaction.

In other words, Bitcoin achieves strong integrity and availability. But it does so at the expense of confidentiality.

The problems of establishing consensus and preventing double spending are indeed hard, and we spent several lectures discussing them -- but why do they require the whole world to know exactly when you buy coffee in the morning? One problem doesn't seem related to the other.

Today, let's explore how to use zero knowledge proofs in order to design new cryptocurrencies that provide anonymous payments.

We'll start by talking about Zcash, which is based on the Zerocoin and Zerocash papers.

Two kinds of addresses

Recall that in Bitcoin, you must maintain a secret key, and from that you can derive a public key. As the name suggests, a public key can be posted to the world -- it is safe to do so, in the sense that nobody will be able to calculate your secret key from it, so your coins are safe.

But just because you can publish a public key, doesn't mean that you have to do so.

In Bitcoin, the hash of each public key is immediately posted to the ledger, and the real public key is posted whenever you want to spend a transaction. That's why we see them on https://mempool.space.

And publishing your public key can lead to de-anonymization attacks, where others can figure out which real-world people correspond to which alphanumeric sequence of keys. We will talk more about this next week.

By contrast, the Zcash currency has two kinds of addresses:

• Transparent addresses, which work exactly like Bitcoin does.
• Shielded addresses, which are new and different.

If you and your friends only ever used transparent addresses in Zcash, everything would look basically the same as it does in Bitcoin.

• You can send money to your friends by digitally signing a transaction to pay their addresses.
• You can download the entire blockchain of all transactions that everyone has ever sent using transparent addresses.

There's only one thing that might look a bit different: there is one account that stores an incredibly large amount of money in it.

Upon closer inspection, actually there are a large number of transactions that take money into and out of that wallet.

Even stranger, there are some weird transactions posted to the blockchain that you cannot decipher.

That's because the big pool of money is actually the sum total of all shielded accounts. Anyone with a shielded account can move some (but not all!) of the money in the pool.

Source: Anatomy of A Zcash Transaction

Inspecting Zcash transactions

Let's look at a transaction between two shielded accounts. It has a transaction id, as normal. But the identity of the accounts is concealed. From the perspective of the public blockchain, no money has moved! All of it stayed in the giant money bag.

Source: Blockchair

And here is a transaction that moves between the giant shielded money bag and a "normal" public account. Note: public addresses on Zcash always begin with the letter t, and shielded accounts begin with the letter z (although we can't see the shielded address here via the public view of the blockchain; only the account owner would see that).

Source: Blockchair

19.2 How Zcash private transactions work

[This portion of the lecture notes is derived from Electric Coin Company: How Transactions Between Shielded Addresses Work.]

In order to explain the transactions between shielded addresses, it is helpful to recall how transactions between transparent (Bitcoin-like) addresses work.

To simplify the story for now, let's leave aside the scripting language, and suppose that a transaction only contains a digital signature.

Recall that Bitcoin is based on the unspent transaction (UTXO) model.

For a transaction to be valid, the sender of the transaction must specifiy where they got their coins from. Also, the sender shouldn't be sending more than what they have. What goes out must be less than or equal to what goes in. If $in \ge out$, the amount $in-out$ is considered fees and a miner can claim the money for themself. Else the transaction is considered invalid.

In other words, we can think of the blockchain as storing a table of hashed public keys and associated monetary amounts. After the first two transactions in the above figure, the table would look something like this:

Hashed key	Amount
H(pk1)	1.5
H(pk2)	2.2
H(pk3)	0.5

Here is the first change that Zcash makes, which on its own is relatively minor. Let's say that each transaction output has an associated "serial number" $r$; you can think of this like the serial number on a dollar bill. The sender of each transaction creates the serial number and sends it privately to the recipient.

Hashed key	Amount
H(pk1, r1)	1.5
H(pk2, r2)	2.2
H(pk3, r3)	0.5

When the third transaction is posted to the blockchain, suppose that the sender posts both a digital signature and the serial numbers of the just-spent coins.

Afterward, all nodes:

• Check the validity of the digital signature
• Check the serial number
• Make sure that the outgoing amount is no more than the incoming amount.

If all checks pass, the nodes update their record of the unspent transactions as follows.

Hashed key	Amount
~H(pk1, r1)~	~1.5~
~H(pk2, r2)~	~2.2~
H(pk3, r3)	0.5
H(pk4, r4)	1.8

They can also keep a list of spent serial numbers: in this case r1 and r2. Assuming that serial numbers are unique, this is a quick way to check that nobody posts the same transaction twice.

The main idea of Zcash is to do the work described above in zero knowledge.

Concretely, the parties maintain a hashed version of the above table, so that nobody can read the keys or the amounts.

To make the above transaction, the sender posts hashes of the serial numbers H(r1) and H(r2) (which are called nullifiers in Zcash-lingo) along with a zero knowledge proof that:

• The sender knows values pk1 and pk2 such that when you hash them together with the serial numbers, the results are the hashed keys H(pk1, r1) and H(pk2, r2) that are being spent.
• The sender knows the secret keys corresponding to the public keys pk1 and pk2. (This is essentially what the digital signature did before... remember that a signature is a special case of a ZK proof.)
• These nullifiers have never been used in a previous transaction. This is where the name comes from -- posting H(r1) effectively nullifies the coins held by pk1 to ensure that they aren't spent twice.

The sender creates a non-interactive zk-SNARK and posts it to the blockchain, and everyone verifies it. If so, they add H(r1) and H(r2) to their nullifier set.

The takeaway here is that all of the money owned by all shielded accounts is lumped together into one giant account. And with the correct key material and serial numbers, you have the right to re-assign some of it to belong to someone else. You post a ZK proof to convince the rest of the world that you have this right.

But: the rest of the world never learns the sender's keys, receiver's keys, or the amount transferred!

The actual Zcash protocol includes many tricks to make this process more efficient. For instance: rather than storing a big table of all hashed keys and hashed amounts, instead all of that data is put into a Merkle tree.

Transactions that move money between shielded and transparent accounts work similarly. In this case, it is publicly visible that the size of the giant account is increasing or decreasing, but nobody knows who has control of the money that just entered/left.

But there is one unfortunate catch:

• In order to spend money from a shielded address, you need to create a ZK proof.
• Part of the statement being proved is that "nobody has ever used this nullifier in any other transaction in the blockchain."

So: in order to construct this proof, the sender/prover needs to know the entire blockchain. Unlike Bitcoin, it's not possible for light clients to spend money just by posting a signature and letting the nodes and miners sort out the details. In some sense, everyone needs to be a full node.

19.3 Interactivity vs transferrability of ZK proofs

In the last lecture, we discussed the Fiat-Shamir transform, which was a way to convert an interactive proof into a non-interactive one.

As a reminder, this transformation works when the verifier's only task in the interactive proof is to create a random challenge. We can replace this step with a prover-chosen challenge using a hash function.

Source: Trail of Bits blog

There is actually a subtle yet important difference between the interactive and non-interactive protocols though.

• An interactive zero knowledge proof is non-transferrable. Remember when you watched Prof. Kaptchuk's proof that he knew the solution to the Sudoku puzzle. After watching that, you did not learn the solution, and also you did not gain the ability to prove knowledge of the solution to anyone else.

• By contrast, a non-interactive proof is inherently transferrable. Suppose that Prof. Kaptchuk had applied the Fiat-Shamir transform, created a one-shot proof, and gave it to me to post on the slides. In this case, he may never have even come to class. From such a ZK proof, still you wouldn't learn the solution to the Sudoku puzzle... but now you can turn around and hand the proof to someone else.

  So now the proof doesn't convince the verifier that you know a solution; it could also have been the case that you've seen it from somebody else.

Just remember: you always get exactly one of interactive or transferrable.

In a cryptocurrency on top of a peer-to-peer gossip network, transferrability is a useful feature to relay the proof across the globe! But note that there are times when transferring a proof would be actively bad, such as if you wanted to prove knowledge of a password in order to log into an account.

If your application allows for a transferrable (aka non-interactive) proof, then you can do something magical with it.

Remember that zero knowledge proofs enable the prover to demonstrate to the world that they possess some information, without the need to broadcast it to the world. Typically the prover wants to hide the underlying information for confidentiality reasons, but the idea works just as well if the prover simply wants to avoid sending the data for efficiency reasons.

Here's an intriguing question: what happens if the prover's information itself includes a transferrable zero knowledge proof that the prover received earlier from someone else?

For example: suppose I ask everyone in the class to solve one Sudoku puzzle, and give me a transferrable ZK proof that you know the solution. Then, I want to make a single ZK proof that applies to all of the Sudoku puzzles.

I cannot prove the statement "I know the solution to all Sudoku puzzles," because I don't know the solutions.

But what I can do is prove "I have seen transferrable ZK proofs to all Sudoku puzzles."

This is a perfectly valid thing to do! It is called a recursive zero knowledge proof.

Sometimes this technique is also called proof-carrying data. You can attach a tiny proof to any piece of data that explains its full provenance -- which raw data it came from, and what data analysis was performed in order to produce it.

Source: PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations

This technique has a wide range of applications in data science. But today we will look at one application involving cryptocurrencies.

19.4 The Mina cryptocurrency

Every cryptocurrency we have seen so far -- Bitcoin, Ethereum, and Zcash -- fundamentally relies on a blockchain data structure.

The individual transactions might include digital signatures, smart contracts, or ZK proofs; no matter what, they are periodically grouped together into a block and appended to the existing chain.

As a result, the blockchain for each cryptocurrency grows linearly with the number of transactions that have ever been made. For instance, the Bitcoin blockchain is ~451~ 470 gigabytes in size.

Source: blockchain.com

Using recursive zero knowledge proofs, we can substantially reduce the size of the blockchain.

Let's imagine that the following picture contains part of the Zcash blockchain. Each block contains a series of transactions, and suppose that each one is a zero knowledge proof corresponding to a private transaction.

Question. How can the miner reduce the size of a block?

Answer. The miner can produce a recursive proof of the following statement:

"I have seen a series of proofs by individual senders, and they are all valid, and they result in specific nullifiers being added to the set."

Remember that a single zk-SNARK has constant size, independent of the complexity of the statement that produced it. So we can compress the size of a single block, effectively down to the size of a single transaction!

But why stop there? Recursion is such a powerful technique that we can use it between blocks too.

Recall that when a new client joins the cryptocurrency, the first thing it must do is to download the blockchain (or at least the headers) and verify all of them. That's a lot of work, and we're asking each new client to do the same thing.

So here is an idea: when a miner produces a block, it proves that all blocks since the start of time are valid.

That sounds like a lot of work, but actually it isn't, thanks to the power of recursion. The miner of block $N-1$ has already posted a proof that the first $N-1$ blocks are valid. So the current miner can create a proof that:

"I have seen individual proofs that each transaction in block $N$ are valid, and I have seen a proof that the first $N-1$ blocks contain valid transactions as well."

(It does take some computing work for the miners to build these proofs, but compared to the immense amount of work in a proof-of-work puzzle, this is nothing.)

The amazing result of all this recursion is a succinct blockchain.

The Mina blockchain can be summarized in about 20kB of data, even though the number of transactions on the network is continually growing.

• The zk-SNARK is about 1 kB in size.
• The Merkle tree of the account table (which I mentioned earlier today) is about 20 kB in size.

This is so small that anyone can easily download it and verify the entire blockchain.

Note that some people need to act as:

• Full nodes that store the entire blockchain and perform the consensus protocol on top of it.
• Miners that produce new blocks to add to the chain.

Fortunately, most people can act as ultralight clients. Thanks to the (recursive) ZK proofs, they only need the succinct summary of the blockchain in order to verify their balance, unlike with Bitcoin where the clients needed to place trust in the nodes/miners.