Summary
Today we hear from Zooko Wilcox of Zcash and Howard Wu of Aleo about Zero-Knowledge Proofs, cryptographic techniques that can be (and are) employed to bring provable privacy and scalability to the many cryptocommercial and governance technologies the group has been discussing.
This meeting is part of the Intelligent Cooperation Group and accompanying book draft.
Presenters
Zooko Wilcox
He is known for the Tahoe Least-Authority File Store (or Tahoe-LAFS), a secure, decentralized, fault-tolerant filesystem released under GPL and the TGPPL licenses. He is the creator of the Transitive Grace Period Public Licence (TGPPL)…
Howard Wu
Howard Wu is a co-founder of Aleo, the first developer platform for fully private applications. Howard has a background in Theoretical Computer Science and Computer Security, with specific research interests in theoretical and applied cryptography, verifiable computing, and zero-knowledge proofs. Howard serves as an advisor to …
Presentation: Cooperative Arrangements Enabled by Zero-Knowledge Proofs
- Zero knowlege proofs were discovered in the 80s but were not
practically efficient or really used for anything until Zcash came
around in 2016 using the Groth16 method. - When Satoshi and Hal Finney were building bitcoin, they discussed
the privacy issues with the system and considered using zero knowledge
proofs but deemed them not efficient enough to work well. - By 2016 when Zcash came out, the zero knowlege proof technology had
advanced to the point where it was usable for a currency. This was the
Groth16 technique that Zcash still uses. - But it came with a flaw: there was a backdoor built into the math.
Everyone uses a certain key to verify proofs, and if someone knows the
corresponding private key then they can spoof proofs. Basically, there’s
a master key that creates a major trust issue. - The way Zcash works, it uses good old fashioned encryption for
privacy of users and zero-knowledge proofs for coin data, so if you
broke the zero-knowledge proof then you could mint Zcash coins but not
break the privacy of users. - In a standard use of a zero-knowledge proof system, you can prove
that a computation took place and that the correct answer was arrived
at. - The Zcash team has been working on a new zero-knowledge proof system called Halo2 that is recursive, meaning that you can prove that you ran a verification and the verification came out true.
- With the recursive system, you can verify a computation and generate
a proof that you ran the verifier, and generate a proof that you ran
the verifier on the verification and so on and so on. This let’s you
prove and verify arbitarily large computations by chaining many
verifications together. - The breakthrough: previously it would take something like 100 hours
on a supercomputer for one recursive zero-knowledge proof to complete.
Through the discovery of what cryptographers now call “accumulation
schemes”, a way to combine the computationally heavy parts of multiple
proofs and compute them simultaneously, this time has been dramatically
slashed.
- A comparison of zero-knowledge proof methods.
- The issue with the current Zcash method, Groth16, is that it
requires a private key ceremony that relies on trusting the peole who
performed that ceremony. - This issue with the new Halo system is that it relies on Discrete
Log, which is not robust to a quantum computer of large enough size
(there is a known quantum speed up). “We’re relying on nobody having a
big enough quantum computer.”
Q&A
Once a large enough quantum computer exists, what does that do to the past?
- A:
- Basically, there are two things we do with cryptography: hiding information and integrity or proof. The thing with hiding information is that you’re a hostage to time: if the quantum computer comes along, you can’t hide the info but you can rely on old proofs.
- Basically, there are two things we do with cryptography: hiding information and integrity or proof. The thing with hiding information is that you’re a hostage to time: if the quantum computer comes along, you can’t hide the info but you can rely on old proofs.
What’s immediately next? Can this group help?
- A:
- We’d like more users: we have it released in a restrictive open source license, and also through commerical licenses.
- We’d like more users: we have it released in a restrictive open source license, and also through commerical licenses.
The last time you mentioned proofs you were referring to interactive proofs. These seem to be not the same, these are static proofs that prove that an interactive proof was performed?
- A:
- Yep. It’s called a Fiat-Shamir transform. The interactive kind were a series of challenges and responses that made it very unlikely that the responder could be bluffing the entire time. In this case, the proof is a hash of all of the things that you’re proving and have to satisfy the hash at hundreds of locations.
- This makes it practical: a 2000 byte proof can prove arbitrarily large computations took place.
In the smart contract setting, you need the full contract plus the proof on chain to manage. How are you enforcing this if the contract is not on the blockchain?
- A:
- Yes, you can prove that computations tooks place elsewhere as long as you know the identity of the smart contract.
- The proof is based on proving that a program with a certain ID ran a computation and returned a certain result: you would need this identifier but you could then later generate a proof that that program returned something you’re looking for.
Presentation: Zero Knowledge Applications
- There is more and more excitement and a growing number of use cases for decentralized applications, but they have their problems.
- The scalability problem: the computational integrity of these systems is determined by direct execution, meaning each miner must re-execute every transaction. This constrains computation via limited running time, minimal stack size, and restrictive instruction sets.
- The privacy problem: the core strength o currenty decentralized application systems is also the primary weakness, namely that the history of all state transitions must be executed by all parties. This totally precludes the privacy of the users of these systems and creates opportunities for Miner-Extractable Value: the lack of privacy of transaction details allows for front-running and arbitrage attacks.
- Zero-knowledge proofs can achieve privacy and help scale systems by enabling proof that some known computation was executed honestly, and for some private inputs.
- While bitcoin requires users to broadcast their private details, something like Zcash can prove the validity of the payment without disclosing the contents of the payment.
- The Waldo Explanation of Zero-Knowledge Proofs
- Imagine you want to prove that you found Waldo but you don’t want to ruin the surprise for the person you’re proving it to.
- In a perfectly empty room, you lay the Waldo page on the table, and bring in the person who found him. Cover the map with a big piece of paper (bigger than the page) with a small hole in it: shift the paper around until only Waldo is revealed.
- Another Waldo seeker could take a look at this paper and know that Waldo exists somewhere on the pafe, but can’t see where he is or any other information about the page or Waldo’s relationship to it.
- This is a non-interactive proof that Waldo exists and was found that does not reveal other information about the data.
- Using this method, you can prove that a piece of data is in a database without having a copy of the database. For scaling blockchains, proofs could be provided that prove the chain history exists elsewhere to shorten the time it takes sync a new node.
- Zero-Knowledge Proofs can make web services more secure
- The current way to authorize with an application: you provide a password, it’s sent to the server, it’s hashed (hopefully) and stored in the database. Then each time you log in you do the same and the hashes are compared.
- There are so many ways for this to go wrong: passwords stored in plaintext, passwords hashed with weak encryption, etc.
- The onus shouldn’t be on the server to protect the passwords, because the server operator doesn’t have the same incentives to protect them that the user does!
- With zkps, you can hash, salt and pepper your password client-side and sent the result over to the server. You can prove to the sever that you did this correctly by generating proofs that the correct computations were run.
- Zero-Knowledge Proofs can make web services more compliant
- Let’s say you want buy a stock: now, the user goes to the broker, who is working with the exchange. Right now, the only thing preventing broker dishonesty is after-the-fact audits and regulations.
- Using zkps you could prove you are qualified to invest without revealing your identity, the broker could prove they’re transacting honestly, and everyone wins.
- Zero-Knowledge Proofs make web services fair
- The type of control we saw from Robinhood preventing the trading of Gamestop is enabled by the total command the centralized company has over its software. Using zkps you could build trading software that can prove its own fairness.
Seminar summary by James Risberg.
