This is a note of Youtube vide Introduction to zk SNARKs STARKs.

1 Introduction

Money history:

  • Limited phyical resources: limited by nature, trusted by humans
  • Fiat Money: fiat rquires Tursted Parties (TPs) such as King or central bank.
  • Crypto-currency: In Crypto we trust, limited by consensus, no TP.

Bitcoion’s innovation is that for the first time in human history, a Societal Function (SF), thought to require a trusted party, is replaced by algorithms and protocols.

  • the SF is Fiat money
  • will other SF follow?: law, corporations, government, academia, religion

The challenge is computational integrity: how can public trust the output of a computation? Often a party executing a computation is incentivized to misreport its output Bitcoin’s solution is to provide enough information for verificatino by re-execution. But financial privacy is a concern. The problem now becomes how can public trust output of computation, while reserving financial privacy? The answer is ZKP: cryptographic zero knowledge proof. ZK was invented in 1985 by Goldwasser, Micali, and Rackoff. They won 1993 Godel prize and 2012 Turing award. But only recently full potential gets implemented.

ZK preserves privacy of inputs, can be applied to any computation and is scalable in verification (poly-logrithmic (logT)^2) and proving (quasi-linear T * (logT)^2). For example, all block UXTO takes about 1PB = 2^50 steps, the verification is 2500 steps and the prover is 2500 * 2^50.

The trusted party folks and the decentralized folks have different mindsets.

2 Zcash

In Bitcoin, both ID and transaction amounts are plaintext. Zcash launched 10/28/2016 and partnered with JP Morgan. Zcash encrypt transactions, append proof, call zkSNARK:

  • short proof, less than 300 bytes
  • fast verification, less than 10ms
  • universal crypto-proof

But it requires “trusted setup” that cannot be transparent and is hard. It is also not secure enough against quantum algorithms.

3 STARK

STARK (Scalable Transparent ARgument of Knowledge) is a new crypto-proof system that features:

  • Scalable proof generation and verification
  • Transparent: pubic randomness, no “trusted setup”. Good for public trust and collaboration.
  • ARgument of Knowledge
  • post-quantum secure