Zerocoin/Zerocash summary at Real World Crypto 2014

Summary transcript of Matthew Green's talk about Zerocoin/Zerocash at the Real World Crypto 2014 from Soundcloud: https://soundcloud.com/rdlmitedu/140113_0001-wav

* Bitcoin may not be particularly anonymous
* Zero-coin / Zero-cash to anonymize the bitcoin currency
* transactions recorded in public ledger; nothing sophisticated done with the ledger; people can identify and map your identity; if you're very paranoid you can prevent (maybe), but in general case hard to use bitcoin for privacy;
* this should matter to all of us; the technology behind bitcoin may be with us for a very long time; countermeasures are weak even in the face of unsophisticated attacks
* if we make bitcoin private, can possibly find applications beyond currency

* two approaches for anonymous version of bitcoin
* zerocoin - technique to implement electronic cash in bitcoin protocol
* zerocash - way to make zerocoin practical and deployable and usable as ecash currency

* zerocoin - join work with students and colleagues at John Hopkins (JH)
* bitcoin doesn't give us much privacy despite academic thinking from 1980s (esp. David Chong) to build untraceable ecash
* ecash tried to tackle one problem without thinking of all other practical concerns; nobody in the history of academic ecash managed to setup a working, centralized bank; chong's bank attempt failed
* bitcoin solved this problem of a currency take-off and early adoption; but we need a different technique to get rid of a centralized bank
* zerocoin new approach for ecash to get rid of centralized bank; basic idea is public ledger (constructed by bitcoin) blockchain; use this to wash bitcoins that does not require us to trust a centralized party; key ingredient (blockchain) is given by free by the bulletin board;
* zerocoin high-level intuition of original protocol: layer on top of bitcoin; i have some bitcoin; i want to break the link between my current address and a future address; take my bitcoin and turn into zerocoin; they get mixed up; all people making zerocoins will shuffle them together so no linkage with creation and redemption; at some future point, can redeem zerocoins into bitcoins ideally unrelated; breaks graph analysis; when disappearing into the zerocoin network minimizes/removes leakage;
* zerocoins are numbers; digital commitments to a large serial number; viewing the commitment, you should not be able to tell the serial number; once these commitments are minted (easy to create), you put them on the bitcoin blockchain; new instruction in the bitcoin system to produce a transaction that spends a bitcoin for a zerocoin; anybody that sees this transaction sees that this valid zerocoin is worth some money;
* at some point in the future, you redeem; you first reveal the secret serial number to make the first zerocoin and put into transaction; prove that the serial number corresponds to a zerocoin; then prove that the zerocoin is one of the set placed on the blockchain (which somebody paid money);
* zero-knowledge proof; prove statements without using any other information other than that the fact that the statement is true; "there exists some zerocoin in the set of zerocoins placed on the blockchain & the serial number we're revealing is the actual serial number in the coin";
* if the proof is valid, then double-spend is impossible since serial number would have to be revealed again;
* efficiency is important here! the approach used is the accumulator; collect all the zerocoins into the accumulator, then prove that the zerocoin you're trying to spend is contained in the accumulator; proof of knowledge is 4KB; the entire thing is 25KB after optimization; for crypto this is awesome!; but developers hated adding this much to the blockchain; so unlikely to happen in real world
* summary: zerocoin good first approach, libzerocoin; but the problem is that the proofs are just too big; and coins have all the same value; but this means that if you want to spend fractional amounts of bitcoin, then it won't work (have to translate back to bitcoin)
* new solution: zerocash
* presented in May and Bitcoin conference in San Jose; in both conferences with teams working on small zero knowledge proofs aka SNARKS; other cryptographers already had them ready;
* SNARK - Succinct Non-interactive Arguments of Knowledge; Bryan Harno (MS Research); basic idea is that you can prove arbitrarily complex statements in 288 bytes; in addition to having these efficient proofs, there are compilers that have proofs that the program executed correctly; we should simply take existing libzerocoin code and run through the compiler to produce these proofs; but these compilers produce large circuits; the time to make a small proof takes hours or days;
* co-authors have spent a lot of time optimizing these proofs; the right way is NOT to take existing libzerocoin, but throw away RSA and other cryptographic techniques and replace with components that are easier to prove such as hash functions like SHA256 and Merkle trees; easy to prove hash with small circuits e.g. sha256 in 30K gates
* each coin is really the hash of some randomness and the serial number = commitment. once we have these coins we put in the hash tree; 64-depth key (2^64); when want to redeem; reveal the serial number, and can reveal 64-hashes before in the tree;
* if these proofs are powerful and efficient; why need bitcoin? why not put entire system into zerocoin and make everything anonymous through generation, use, redemption of coins? the only information that makes it into the blockchain is the fact that a transaction occurred. just show that two new coins where the value totals the bitcoin that you're splitting; when we merge we spend two coins we prove that the two = same value of the new coin; transfers can be done completely anonymously without knowing who and how much.
* can encrypt transactions and hash the values
* transaction fees have to be public, but everything else can be anonymous
* name for this process; generic transaction is called "pouring coins"
* is this efficient? one detail - the problem with zerocoin 1.0 was that the proofs were huge and took 0.33s; these results mixed; to merge/make takes 87s-108s on a single core; but on bright-side bitcoin takes up to an hour for each transaction; verification time is in ms; comparable to bitcoin; verification is in the network; the catch is that to verify the proofs you need a large set of public parameters; 1.2GB in size
* best part of this is that you already need 16GB to store the blockchain, so to add this is around 7% increase in storage
* somebody needs to generate these parameters; trusted party; possible to find a dozen people that people trust to set up the parameters;
* system that is efficient; will be separate system released in May; real-world crypto; want to get people to use;
* release an altchain; client that implements all these things; put it out there; hope that nobody puts a lot of money in this because these are new techniques and might break down; idea is to test this in an environment separate from bitcoin so we don't break anything else while trying to make this work
* should we even be doing this research? lots of people criticizing us. this is important research not just because people want to commit crimes, but because when you spend money your transactions are hidden from neighbours, but with bitcoin people can see your transactions; important to get it out there.

Thanks.