1st meeting: bitcoin and proof of work (and incentives there)
Last time we studied the Byzantine Generals Problem and saw how Lamport’s solution completely broke down in the permissionless setting via Sybil Attacks. This happens because a “1 person 1 vote” policy isn’t sufficient in permissionless networks since a “person” may very well be one of many sockpuppet accounts controlled by one party.
So we need a way to reach consensus on the state of the network in a permissionless manner. This is where Proof of Work and Nakamoto Consensus come in, giving us a sybil resistant consensus algorithm.
a timestamp server
Bitcoin is a peer-to-peer digital cash system that works without central authorities. It works with cryptographic signatures, hash-based proofs-of-work, and a data structure called a “blockchain”.
A blockchain is a linked list of blocks, where blocks are tuples containing $(h_{-1}, \eta, \textbf{txs}, h)$, i.e. the hash of the previous block, a nonce (a number), a list of all transactions in that block, and the hash of this block. The previous hash is what links every block together and is vital to the mechanism.
Every transaction is cryptographically signed by the sender so that only someone with the private keys to an account can move money in an account. Furthermore, the creation of new coins is contingent on valid hash-based proofs-of-work so a malicious party can’t create new coins indefinitely. There is a real computational cost to creating new coins.