PPCryptoCur Exam 2020-10-21

• Subject: Privacy-Preserving Cryptocurrencies from SS 2020
• Date: 2020-10-21
• Type of Exam: oral exam on-site with a *big* whiteboard for me to draw on
• Examiner: Prof. Dr. Dominique Schröder
• Grade: 1.0
• Undergone Preparation:
  • active collaboration in lecture/exercises during the semester
  • two weeks preparation directly before the exam of 4-5 hours per day (without weekends)
  • I focussed very much on relating all privacy-preserving techniques, on knowing (i) very well all models (e.g. RingCT) (ii) pretty good general ideas on the constructions and ingredients (e.g. zero-knowledge proofs, how RingCT can be instantiated, tagging schemes – but without instantiation of ZeroCash).
  • I skipped almost all proofs altogether. One of the few proofs I looked at was the one for the binding and hiding properties of the Pedersen commitment scheme.
• Evaluation
  • The exam is fair, but notably, also covers a wide range of topics. Some questions are „soft“ in the sense that they ask, say, why BTC does not provide privacy, how DoS is possible with decentral mixing protocols, how that can be avoided (it cannot), or what trusted setup assumptions mean philosophically. Then, other questions are more technical. Overall, it's a good mix of both and you need to be fluent in both.
  • The exam is always started with the question „What did you like the most?“ And this is an invitation for you as the student to freely deliver a well-learnt topic.

This braindump is not exhaustive, I definitely forgot some questions from the exam.

Abbreviations: BTC = Bitcoin, ROM = random oracle model, TS = Trusted Setup, TSA = Trusted Setup Assumption, TTP = Trusted Thirdparty, ZKP = zero-knowledge proof

• What did you like the most?

RingCT. In contrast to BTC, it provides three main advantages: (i) ring signatures, (ii) stealth addresses, (iii) hidden amounts. I elaborated on every point with at least 3-4 sentences saying how it's *not* (or badly) done in BTC and with what consequences and how it's done in RingCT. Roughly:

* ad (ii): in BTC, if you want someone to pay you, you have to publish your BTC address. The same holds true if you want to run, say, a donation campaign. Then, on the blockchain everyone can see who donated to you, and that's bad. Hence, it's recommended to always freshly generate receival addresses, but that's impossible with donation campaigns. Hence, RingCT offloads that fresh generation thing onto the sender via stealth addresses.

• You mentioned some great ideas. Let's dive into that and start with something simple: The BTC blockchain only contains addresses. What's so privacy-invading about that?

I elaborated on blockchain deanonymization and link analysis. I detailled how it's even worse than the traditional banking system: in BTC the blockchain is fully public, permament (non-redactable), and analyzable even by cheap hardware.

• But still, the blockchain only consists of addresses. How do real identities come into play?

(i) if you buy at a real store with a BTC address, a link to a real identity will appear, and (ii) real identities of some addresses are publicly known (e.g. for organizations running donation campaigns such as WikiLeaks)

• How can we avoid these privacy issues with BTC?

Use mixing services. Either centralized (centralized mixer, TumbleBit) or decentralized ones (CoinJoin, CoinShuffle). Centralized mixers [note: this does *not* include TumbleBit] inherently need to be a TTP, can steal your coins and/or leak your identity. Decrentralized ones build upon peer-to-peer protocols. But in CoinJoin all participants still learn about the input/output address pair mapping. At least no coins can be stolen anymore thanks to how BTC transactions work and how transaction inputs need to be signed. Or use a currency that was made with privacy-preservation in mind, e.g. RingCT.

• In RingCT, what are stealth addresses more precisely?

With SKAccGen you create `(msk, mpk)` and from `mpk` senders can derive a `pk`. If senders do that honestly, `pk` cannot be linked back to `mpk`. But if you possess the `msk`, you can scan the blockchain and for matching `pk`s (that have been derived from `mpk`), you can derive the corresponding `sk` to have the money at your disposal.

• How can rings really work? Can't I simply doublespend?

No, that's where tags come in. I wrote down the interface of the RingCT Spend algorithm and that the transaction built later on contains tags. Miners can just check for duplicate tags to prevent double spending.

• How can amounts be hidden?

In the RingCT construction, amounts aren't returned by `OTAccGen`, but rather commitments to it. They bind the amounts, yet hide them at the same time.

• What are commitments?

It's like writing something on a piece of paper and putting it upside down on a table and later flipping (revealing) it. The revealed value must not be different than the initial value I wrote down. This is the binding property. And nobody must be able to read the value without revealing the bottom side of the paper.

• How can commitments be realized?

For example by the Pedersen commitments. There, in Setup: (i) a group `(G, g, q) ← GenGrp` is chosen with generator g of order q, (ii) `h ← Z_q` is chosen uniformly at random from the „exponent space“, and (iii) `pp ← (G, g, q, [h])` is returned. Importantly, from `[h]` we *cannot* infer `h` under the DLOG assumption. Then, in `Com(m;r)` we simply return `[1]*r + [h]*m`.
Pedersen commitments are perfectly binding because for every commitment `Com(m;r)` and for every other message `m'`, there is a randomness `r'` such that `Com(m;r) = Com(m';r')`. Note that this `r'` cannot be efficiently computed. Me saying „there is a randomness `r'`“ is on the meta level of mathematics, not on the meta level of efficient crypto algorithms.
Finally, Pedersen commitments are just computationally binding. You cannot have perfect hiding and perfect binding at the same time.

• Why cannot we have perfect hiding and perfect binding at the same time?

> See https://crypto.stackexchange.com/questions/41822/why-cant-the-commitment-schemes-have-both-information-theoretic-hiding-and-bind.

• Alright. Let's get back to amounts being hidden because they are just committed to. Why cannot I just create money out of thin air?

Because `Verify` checks the ZKP and verifies the „of knowledge“ part for the amounts.

• What are ZKPs?

Intuitively, interactive or non-interactive protocols between a prover and a verifier such that the verifier doesn't learn anything except that the statement is true, and for „of knowledge“ systems, that the prover possesses a witness.

• How is this possession of a witness formalized?

By requiring the existence of an extractor that given a prover and a statement stmt outputs a (putative) witness fulfilling the following property: if that prover was able to convince the (honest) verifier, then the witness output by the extractor is in fact a witness for the statement stmt being in the relation R. R is the NP relation in the usual definitions of ZKP-related concepts. Importantly, the extractor is given oracle access to the prover and can also rewind it. Something that isn't doable in practice and hence this extractability notion actually makes sense. [note: I said this paragraph purely orally and that sufficed. I don't think they want you to know the exact notation or learn the typesetting of definitions by heart.]

For non-interactive protocols we also formalize this by the existence of an extractor. How can this work for non-interactive protocols? For interactive ones, it's clearer: you have this rewinding technique.

• The extractor can control the common reference string crs or some trapdoor - depends on the exact formalization of ZKP-related concepts, though. [note: Prof. Schröder here just repeated a question of mine; namely that question I had asked days before on the course forum and there got the very same reply I answered, too.]

How does a (non-interactive) signature of knowledge work? How can it be secure without any communication/challenges by the verifier?

• We often have an interactive protocol that we then transform via the Fiat-Shamir transform. There, we replace the challenges by the verifier (that all need to be public-coin) by hashes of all previous messages. This is then guaranteed to be secure in the ROM.

• We covered many different privacy-preserving techniques in the lecture: CoinJoin, CoinShuffle, TumbleBit, ZeroCoin, RingCT, ZeroCash. Which one of these would you recommend using?

As always depends on your threat model. For any serious threat model, I would never recommend Bitcoin or anything building on that (e.g. CoinJoin, CoinShuffle, TumbleBit, ZeroCoin). Hence, the decision is between RingCT and ZeroCash. Here, it from a rough point of view, they differ in whether they need a TSA or not. ZeroCash requires one, RingCT not.

• But for RingCT we need also a bit of trust for the non-interactive zero-knowledge signatures of knowledge, no?

They are only secure in ROM. Hence, you need to trust the specific instantiation of the hash function.

• And the ROM doesn't exist in reality. So this might be a bit philosophical, but doesn't that make RingCT need a TS, too?

Indeed, one could say so.

• So after all there are no cryptocurrencies without a TSA?

I guess there are algorithms to perform the required trusted setups in a decentral way. But still, this is only spreading the risk, ultimately, it'll remain a TSA for the users that performed that setup decentrally.