Course Overview Document

karl · 2018-04-28 16:58:55 UTC

Please provide feedback! It will make my day <3

I just posted a document with the course overview:

cryptoeconomics-study/website/blob/master/overview.md

# Course Overview

## Chapter 1: Centralized Payment Processor
* Overview of basic crypto concepts
   * Hashes -- not how they work but instead what they do (collision resistance, second preimage resistance [given x and H(x), cannot find y such that H(y) = H(x)], preimage resistance, random oracle)
   * Public / private keys -- Sign with private key, verify with public key
* Overview of PayPal structure
   * State object which is simply a mapping of address->balance
   * Two types of state mutations: 1) `mint` and 2) `send` -- each with their own logic
   * We start with an initial state (ie `genesis block`) and apply transactions (ie `blocks`) to get our most recent state.
      * The list of transactions (blocks) is called the “history”
      * The result of computing all transactions is called the “state”
      * Note: In Ethereum the full history is approx 250 GB, while the state is approx 3 GB.
         * Fun aside: Rent proposals say that people should pay rent on the state storage which they take up. There is no direct incentive to store the history, and so nodes today often do prune or delete historical data. If this happens too much there is a risk that we can’t recreate the chain anymore!
   * Use nonces to provide replay protection. (nonce means you can’t resubmit the same transaction multiple times)
   * Code implementation: https://codepen.io/karlfloersch/pen/YaEoYy?editors=0012 
* Account model vs UTXO model
   * Briefly cover the differences
   * Account model (what we are using for our implementation):
      * A global mapping of `account->balance`

This file has been truncated. show original

I tried to integrate as many of the subjects from Course Subjects List as I could – Thank you for your awesome contributions! I included a list at the bottom of content which was suggested but I did not explicitly cover. I’d like to integrate all of it eventually.

It would be great if you have feedback to leave it here, or if you want to edit the doc itself I’d love any pull requests

Hope everyone has been doing well!

DmSuja · 2018-04-28 20:41:17 UTC

Hi Karl, sending you the best vibes!

@paulapivat’s I love your supplementary dox! I think what we can do to make it easier for us and future students is to add those supplementary things to the current course outline as say footnotes. As @karl states, a lot of the extra stuff cannot be integrated cleanly at this time. So as we go through the course, we can try to match each chapter with at least one link from that document.

So for chapter 1, I am thinking reading E and video/online course 2 would go well together.

paulapivat · 2018-04-29 14:51:36 UTC

Great idea , I’ll go through @karl 's Course Overview and add article, video, course references as footnotes for each chapter through a pull-request

ldct · 2018-05-01 08:31:23 UTC

General feedback: very well thought-out. I particularly liked how concepts like UTXO vs accounts were covered without the confounding factor of decentralized block production.

Brief specific comments:

POW analysis: the best bribing attacks I’ve seen are the P+epsilon attack (https://www.lesswrong.com/posts/a8QMgWCwGML69n9me/link-the-p-epsilon-attack-precommitment-in-cryptoeconomics) and feather forking, and the best presentation I’ve seen for those is this one: https://www.youtube.com/watch?v=UPxaCj8ZsEU. For selfish mining there is a nice expository article from the ACM that I can’t find right now.

I think the PoW section is also the best place to introduce the “cartel” attack where a majority cartel of miners earns more than its fair share of revenue by censoring blocks produced by non-cartel members, and once that cartel has monopolized block production a sub-cartel could form, etc., since a big part of casper is basically ways to discourage this attack.

That said, there are probably more interesting attacks on PoW than can reasonably fit into that section, so I suggest explicitly outlining in the document what the learning goals are (to understand the security assumptions of PoW, or to learn the language of analyzing protocols). Personally I think the most important ones are the cartel attack and validator’s dilemma. Selfish mining is a cute way to show that intuition can lead you astray and you need math™; IIRC before the selfish mining paper was published, someone published an incorrect “proof” showing that bitcoin mining was incentive-compatible, because their model implicitly didn’t allow block withholding, or something like that.

Leaking in casper-ffg: I think it would be good to learn to analyze this from the CAP theorem perspective; from that point of view in a partition, casper-without-leaking sacrifices availability (but with the caveat that the unfinalized tip continues growing) whereas casper-with-leaking sacrifices consistency (if the partition lasts more than 4 months, conflicting finalized blocks will start getting included)

Proof of Stake: I think it’s super important to talk about long-range attacks and weak subjectivity!

Analyzing Proof of Stake: I think it’s important to talk about economic finality in casper-ffg vs probabilistic finality in PoW!

Advanced PoS: I know almost nothing about full PoS (ie without PoW block proposal) but AIUI many schemes simpler than randao, threshold signatures etc are weak to stake grinding, which is “unavoidable” because of the impossibility of fair exchange, which means you have to use deposits, which … etc

Sparse merkle tree: AIUI their name is a bit of a misnomer, the main property is not sparsity inasmuch as that it’s an (implied) “perfect merkle tree”, thus allowing for non-inclusion proofs

Fault proofs: The idea could be introduced in a simpler context earlier, that is, light clients

State Channels: IMO it would be cleaner to explain them outside of plasma first before explaining them on top of plasma

paulapivat · 2018-05-01 12:51:52 UTC

Hey Karl, Jinglan, Aparna,

I’ve read through the course overview. While I don’t understand everything (yet!) I can tell you guys put a lot of thought into the design, particularly the scaffolding of the content, and the way the topics successively build on top of each other.

So kudos! This is awesome

snario · 2018-05-01 13:58:15 UTC

I think it would be valuable to frame state channels, plasma, and sidechains in the same category broadly and then dive into the specific tradeoffs each make. We tried to do something like that here: https://pbs.twimg.com/media/Dbq0zEWU8AAAxsH.jpg:large

It seems like it’s the most intuitive way to introduce “scalability techniques” on top of a root chain. Probably also Plasma can be positioned as a strictly superior alternative to sidechains.

jordan · 2018-05-07 15:57:18 UTC

Just reading Varga’s explanation of the P+Epsilon attack, with the attacker’s credible commitment in addition to the game’s original two rules the outcomes become:

---------------------- | Cooperate | Defect
Attack fails ------- | 10 | 11
Attack succeeds | -1 | 9

However, I have a question on the first rule of the game as it applies to this case for the blockchain analogy:

If her decision coincides with the aggregate outcome, the player gets 10 utilons.

If all majority of the miners defect and consensus is not gained,

How will there be a blockchain reward to pay out?
And if there is one, will it be worth the 10 utilons as in the cases where consensus is reached?

Without a blockchain reward because the blockchain utility goes to zero the possible outcomes become:

---------------------- | Cooperate | Defect
Attack fails ------- | 10 | 11
Attack succeeds | -1 | 0

Then wouldn’t the rational miners choose for some minority to defect and a majority to cooperate? Even better if the “defecters” could credibly commit to giving some of the attacker’s 1 utilon then the average participant could walk away with (10.5 - small number) of utilons.

Wouldn’t this optimal cooperative case apply even if questions (1) and (2) didn’t since (10.5 - small number) > 9?

Daniel · 2018-06-05 12:17:29 UTC

@karl Happy to start tackling chapter 7 if no one is working on it and there are people on 1-6. Can you clarify that what you mean by the ‘1% problem’. To my understanding what you have written is essentially the vulnerability of having too many forks/proliferation of blockchains making them as a whole a lot more vulnerable as they are all competing for miners/validators/nodes… is that correct?