tldr: Bitcoin

-
Part of the tldr series, which summarizes papers I'm currently reading. Inspired by the morning paper.

Bitcoin: A Peer-to-Peer Electronic Cash System [2008]

Nakamoto 

Introduction

Nakamoto was motivated by how much electronic payments relied on trusting third-party financial institutions. Thus, they created Bitcoin, an "electronic payment system based on cryptographic proof instead of trust", which eliminates the need for a central bank. 

Transactions

An electronic coin is a chain of digital signatures. Each owner has a public and private key (also called a wallet). They can transfer a coin to the next owner by signing the hash(previous transaction + next owner's public key) with their private key, and appending this to the end of the chain of signatures.
 
Transactions also contain multiple inputs and outputs, so change is easy. (For example, let's say you wanted to pay someone 0.03, but you only have a previous transaction where you received 0.10. Then, you could have two outputs, where one output of 0.03 goes to the other person, and the other output of 0.07 goes to yourself.)
Spent transactions can be discarded to save disk space, by hashing them into a Merkle Tree.

Blockchain

Although the next owner can check that the signature is valid, they can't check whether the coin has already been spent. In current systems, it's the bank's job to make sure that double spending doesn't  happen. Bitcoin solves this by distributing the responsibility of the bank among all nodes in Bitcoin's network:
  • Transactions are publicly announced 
  • Participants can agree on one history of the order of transactions
  • The next owner has proof that the majority of nodes has agreed on the transaction 
Specifically, a public ledger called a blockchain keeps track of all transactions. Its name comes from how it's made up of blocks of transactions. Each block refers to the previous block, thus forming a chain.

Proof of Work

To make sure some adversary doesn't just flood the network with lots of nodes, a proof of work system makes it hard for nodes to validate transactions. The procedure, called mining, happens roughly like this:
  • A node (also called a miner) hears about new transactions, and add them its own pool of pending transactions. 
  • The node checks that each transaction is indeed valid by verifying them against its own copy of the current state of the blockchain. 
  • Before the node tells other nodes that the transactions are valid, it solves a proof of work puzzle. 
    • The node must find a hash(transaction + nonce) that starts with a specific number of zero bits, say n. 
    • Bitcoin uses a SHA-256 hash function. 
    • A nonce is a counter. The node increments the nonce until they find a hash that works. 
    • n is adjusted to account for CPU power and number of miners, such that one block is produced every 10 minutes. 
    • On average, this work is exponential in n, but can be easily verified. 
    • A miner’s probability of success in creating a block is proportional to the fraction of computational power they have. 

  • Once the node solves the puzzle, it broadcasts the block of transactions to other nodes.
    • Other nodes can easily verify that the hash satisfies the requirements. 
  • The node also receives a reward. 
    • This reward is needed to incentivize nodes to use a lot of computational power to verify other people's transactions. 
    • The reward halves every 210,000 validated blocks, so by the year 2140, the reward for mining will be the smallest unit of Bitcoin: 10^-8 Bitcoin, or a satoshi.
    • However, miners also get rewarded with transaction fees. If the output value of a transaction is less than the input value, then the transaction fee is the difference. 
As we can see now, the proof of work system ensures that there's one vote per CPU, and thus makes it very hard to change a block. A node would have to redo the work, so the probability of it catching up is negligible. 

Forks 

Sometimes, two nodes mine a block at roughly the same time. The other nodes hear about both of these forks, but work on the fork that's longer in their copy of the blockchain (in other words, whichever block they hear about first.) When one fork becomes longer, all nodes will switch to that fork. Transactions in the old fork that haven't been validated yet aren't lost, because nodes are still storing them in their pools. 

The longest chain has had the most work done by nodes to compute it, so it's the majority decision. Specifically, in Bitcoin, a transaction isn't confirmed until the block that its part of and the next 5 blocks have all been mined as part of the longest fork. 

Popular posts from this blog

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each instance of a type that impleme
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized
Read more

tldr: Raft + Implementation Tips

-
Image
Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . Raft (Extended Version) + Implementation Tips [2014] Ongaro et al. Note: For implementation tips, see the end of this blog post.  Introduction Consensus algorithms The r eplicated state machine approach  is useful for providing fault-tolerance in distributed systems. It lets a cluster of unreliable machines continue operating even when some of its members fail. In this approach, machines   usually use a replicated log to stay in sync. As shown in the figure below, each server's log stores the same commands in the same order. Every state machine executes commands from its own log in order. State machines are deterministic, so each produces the same order of outputs. Once the majority of machines have responded, the command is done executing. Consensus algorithms ensure that the replicated log stays consistent. In the figure above, clients send commands to
Read more