Lecture 10: Anonymity on Blockchain

(Coinjoin continued from the previous lecture)

1. Each participant writes an input transaction (input address, change address) on say Pastebin. Over Tor, each participant writes an output address. These two entries and not linkable to each other.
2. Now, each participant signs a CoinJoin transaction only if they like their own input and output entries.
3. Someone sends the final transaction to the miner.

DoS attacks on CoinJoin:

1. If anyone drops out or goes offline, then the CoinJoin fails.
2. If the UTXO mentioned in #1 is spent between #1 and #2, then the CoinJoin transaction (T_cj) fails.

CoinJoin works only for the small sets ~40. Everyone can collude and unmask a single participant (multiple mixing eliminates it). All outputs must have the same value or else anonymity is lost.

Crypto mixing mechanisms mix over a much larger set. There are two mechanisms for it.

1. Commitment schemes - One commits to a value without revealing the value. commit(m) -> (c, r). c is commitment and r is a secret to reveal it. verify(c, m, r) -> true/false verifies the commitment. This scheme should have the binding property, so that, no other m can be revealed for the same c. The scheme should also have the hiding property, so that, c should not reveal any information about m. For example, H(m, r) -> c where H is a collision-resistant hash function. A simple example of commitment is coin-flipping where Alice sends a commitment to a bit, Bob sends their bit in clear, and then Alice reveals its bit. XOR of the two bits is the final coin toss outcome.
2. ZKPK (Zero Knowledge Proof of Knowledge) - Alice wants to prove that for a given X and P(X,w) -> {0,1}, she knows witness w s.t. P(X,w) = 1. She wants to prove this to verifier Bob without revealing w to Bob. ZKPK is possible for all of NP and beyond. Anything that can be proven, can be proven in Zero-Knowledge. Proof can be non-interactive, so, one single message from Alice to Bob is sufficient. Size of the proof ~ size of the program/predicate P. Even simple example is complicated. ZK-SNARK, a succinct non-interactive argument of knowledge, is based on a CRS (common reference string). Alice produces proof using CRS, X, and w. The proof is ~ 300 bytes which are a huge advantage. CRS is huge ~ 1 GB. Verifier Bob can verify the proof and X using CRS. All SNARKs require a trusted setup. CRS creator can prove wrong statements. So, shorter proofs have CRS size penalty.

Confidential Transactions - replace amounts by commitments along with ZKPK (not SNARK) that sum of inputs >= sum of the outputs and the numbers are non-negative. This proof is ~ 2.5KB. Miners can mine the transaction along with the proof. This is implemented in the Bitcoin core but not enabled.

Zerocoin

Let every Zerocoin = 0.1 BTC. Let Bob chooses a 256-bit sequence number s_n and generates a commitment (c, r) for sn.

1. Bob sends 0.1 BTC to address zc:c. c is linked to Bob but no one knows s_n since r is secret. There are tons of such coins now, c_1, c_2, … c_n. We will create a Merkle tree with root h.
2. To redeem, Bob constructs (L, sn, π) where L is a fresh Bitcoin address, π is a ZKPK (SNARK) that proves Bob knows (r, c) s. t. c is in Merkle Tree rooted in h and verify(c, sn, r) is true. So, Bob is claiming that he owns one bitcoin in the Merkle tree and he knows how to open it without revealing which bitcoin is his. Miners with check π and zero coin s_n is unspent. If this holds, miners post s_n -> L: 0.1 BTC. s_n is public now but no one can connect s_n back to Bob. Binding property ensures no double spending. Hiding property ensures that no one can link s_n to c. Note that, if someone maliciously generates the same s_n as an existing one, the only the first withdrawal would succeed.

Note:

1. Zcash evolved further than Zero coins to allow different amounts.
2. Some other systems worth looking at are CryptoNote and Monero.