Posts

Lecture 8 - Alternative consensus Puzzle solutions are probabilistic proof of work. A typical puzzle utilization function can be modeled as P(challenge, randomness - nonce, difficulty, …) -> true/false P(c, r, d) for Bitcoin is SHA256^2(c, r, d) <= 2^256-d There are many objections to this. It wastes resources on a meaningless computation, it is highly parallelizable and has returns of scale, randomness, long wait time between blocks, and leads to the creation of the mining pools. It is possible to redesign the system to make mining pools impossible but that would lead to only big players doing the mining. The centralized signing also eliminates all these issues and “private blockchain” is just a misnomer for a centralized blockchain. ...

Lecture 7: Community, Economics, and Politics David Chaum - digital cash in 1981 Satoshi Nakamoto - Oct 2008, bitcoin.org was registered in Aug 2008 Genesis block was mined in Jan 2009 First BTC payment - Feb 2010 First online exchange - July 2010, the price went up 10x by then First GPU miner - Aug 2010 First mining pool - Sep 2010, Satoshi disappeared at this point Silk road launched - Jan 2011 First BTC conference - Nov 2011 Bitcoin requires three levels of consensus ...

Lecture 6: Bitcoin Miner interactions and Game Theory Game Theory: P x S -> R x P P: Players S: Strategies R: Rewards Examples For the prisoner’s dilemma, tit-for-tat with some positive randomization is the best strategy. Trench soldiers in World War 2 decided to start aiming artillery at random “safe” locations instead of killing the enemy. This all happened without any communication. Mechanism design: Design the rules of the game with the outcome you want. ...

Lecture 5: Bitcoin mining How to mine Bitcoin Download and run Bitcoin-core to run full Bitcoin node Listen for a new transaction, assemble a pre-block Solve the puzzle (~270 attempts) Broadcast the block Profit The network runs on port 8333. Non-responding nodes are forgotten after 3 hours (5000-10000 nodes as of Sep 2016). Some seed nodes are hard-coded into the software. Zero transaction fee transactions were accepted until April 2012 before Satoshi Dice came around. Blocks are just an artifact of the mining process. Otherwise, it is just a stream of transactions. Changing the network layer is easy. Changing the protocol layer to add new opcodes is hard. ...

Lecture 4: Blockchains 80 bytes block consists of 32 bytes previous block hash, 32 bytes transactions Merkle tree hash, timestamp, bits, nonce, etc. Each block is <= 1MB to minimize the propagation times. Therefore, large transactions require more service fee to compensate miners to include the transaction in the block. Miner’s transaction checks ScriptSig (from spending transaction) || ScriptPubKey (from funding transaction) executes and this should produce non-empty stack. Empty stack or zero is false. Transaction inputs are in the UTXO set. Sum of all outputs <= Sum of all inputs As of Oct 2016, 43M UTXO, 475K unique addresses, and 15.9M BTC in circulation. ...

Lecture 3: Bitcoin overview There are three Bitcoin protocols Consensus Protocol - decides what the ledger is Transaction Protocol - assigns meaning to the ledger Network Protocol - the P2P protocol which decides what new should be added to the ledger Consensus Protocol Bitcoin fields (Virtual field) Hash - 4 bytes. SHA256-squared. This is not part of the block but is calculated on the fly. Version - 4 bytes. Set to 3, might never change. Previous block - 32 bytes. Hash of the previous block on which we build this block. mrkl_root (Merkle root) - 32 bytes Time - 4 bytes. Timestamp of mining the block. Bits - 4 bits. This is the difficulty level. Lock time - 4 bytes. The transaction cannot be posted on the blockchain till the lock time constraint is met. Nonce - 4 bytes. Random nonce tweaked to find a block with the right difficulty. n_tx & txn_data in the Merkle root are stored separately. The nonce is only 32 bits, Changing that might not be sufficient to get the desired number of difficulty(70+ zeros). Therefore, changes can be made to the Coinbase transaction (explained below) to generate more randomness. ...

Lecture 2: Creating a digital currency Desirable properties of a good digital ledger No deletion Temporal ordering Global consensus Semantic correctness Live - writable, no DOS, no censorship Attempts to create a digital currency in the increasing order of sophistication. A signing key based approach can confirm the authenticity of the transaction but cannot prevent double-spend. Append-only ledger with signing keys ensures a temporal ordering and global consensus, thus, prevents double-spending. Sign “new transaction + hash of the previous transaction”. But if there is a single trusted signing authority, it can still give different signing blocks to the different parties and engage in double-spend. Or it can append invalid transactions to the ledger. To reduce the risk, we can have n signers and require k <= n signers required for a transaction to be a valid part of the ledger. Further safety can be ensured by rotating the trusted signers. The signers will build on (one of the) longest valid chain. The signer will reject any chain with a bad block in it. If the majority of the signers is honest, this works. Otherwise, it does not. A malicious actor can perform a Sybil attack on the system by generating tons of signers who are participating in the system and hence, a majority of signers might end up representing a single entity. Bitcoin (Nakamoto consensus) treats everyone as a trusted signer. The signer in round n is the first signer to solve a proof-of-work (PoW) puzzle. There are no signing keys anymore. The random nonce of the block which leads to H(block) <2256 - d suffices as the valid proof of signing. Two signers can end up signing simultaneously, but eventually, one of the chains will become longest and wins. Each block ~ 1MB and each transaction ~512 bytes. After your transaction ends up in a block, wait for up to 6 blocks to ensure that a different chain won’t become the longest one. Majority of the mining power should be honest though, 51% attack is possible on Bitcoin.

Lecture 1: Introduction Bitcoin is a cryptocurrency with distributed trust. The blockchain is a public append-only ledger. The append-only property is sufficient for having a currency. Hash functions: H: M -> T where |M| » |T| that is space of messages is larger than space of the hash. If H(m0) =H(m1) => collision. Hash function H is collision-resistant if it is hard to find the collision of H. For example, SHA-256 maps long strings to 256-bit hashes. ...

Maui is a small but beautiful island of Hawai’i. Here is a recommended 4-day itinerary for Maui. This itinerary is a slightly modified version of what I was able to do. The public transport on the island is poor. For solo travel outside the rainy season, I would recommend renting a moped to go around. Otherwise, rent a car. The island has a much more developed western part consisting of Kaanapali and Lahaina, which have major resorts. ...

Earlier, the Software world was rigidly divided between closed and open-source software. Microsoft Windows is closed-source, GNU/Linux is open-source. Microsoft Office and Lotus Notes are closed-source, LibreOffice is open-source. Turbo C++ is closed-source, and GCC is open-source. But now, a new class of software products has emerged whose core is open-source, but still, the open-source software is of limited use. One model is to offer some critical and useful functionality in a closed-source layer via a managed service in AWS/GCP/Azure, for example, Redis is open-source, but useful modules on top of it are not. Another model is to use licensing gimmickry, for example, MongoDB is licensed under SSPL which requires that if anyone offers MongoDB as a service, then the source code of the full service must be published under this license. The third approach is to make the core software open-source but make it dependent on closed-source cloud services. For example, the node package manager (npm) is open-source, but a closed source company owns the default npm registry. Android is open-source, but most day-to-day application ranging from Google Maps to Google Music are closed-source. Now onwards, rather than calling such software open-source, we should call them closeum. ...