Bitcoin and Cryptocurrencies CS198.1x

Bitcoin Protocol & Consensus: A High Level Overview

Introduction and basic concepts

• bitcoin is a decentralized, digital currency built using principles of computer science, cryptography and economics

• Bitcoin is the network and protocol governing the bitcoin cryptocurrency

• The Bitcoin Blockchain is a data structure that stores a permanent history of all transactions to ever occur in the history of bitcoin, its and append-only ledger so things CANNOT be deleted once added

  • Data structure: virtual format for organizing retrieving and storing information

• The Bitcoin network validates transactions ans stores the entire transaction history

  • The Bitcoin network is a group of users communicating with each other as part of the Bitcoin protocol

• Bitcoin solves inconsistent transaction and double spending attack problems by using the blockchain and consensus protocol (PoW)

Identity

• Needed to verify no-one else can act in your behalf and only you can perform what you want -> Your Identity

• Identity can be used for integrity which means guarantee no one else can replicate out authentication methods -> Your Signature

• To implement identity Bitcoin uses public and private keys

  • Public keys for receiving (like mailbox) and private keys for redeeming (mailbox key to open and close it)
  • Private key is chosen at random and public key generated from private key using a Math function (Math magic, cryptographic primitives)
  • Public key != BTC Address: The BTC address is derived from your public key but NOT identical

• Bitcoin has 2^160 possible addresses so the probability that 2 people get the same address is very, very, very, very, small; considered impossible

Transactions

• A valid transaction consist of: Proof of ownership (signature), Available/sufficient funds and A guarantee of NO double spending (that No other transaction is using or has used the same funds)
• Bitcoin uses Unspent Transaction Output (UTXO), which is the Bitcoin model for transactions, to enforce valid transactions
  • Users do not spend from an account they spend directly from transactions made to them. The amount of bitcoin you own is calculated by summing up the value of each of your transactions
  • A UTXO can only be spent once.

Record Keeping

• Distributed database so everyone keeps a copy of the ledger to keep track of it

• Everyone stores the ledger

• The Ledger doesn't update for every single transaction, it updates in blocks of transactions (a batch that can contain thousands of transactions) and each block is chained to previous blocks which forms a blockchain

  • This block system give the database discrete states (or checkpoints) where every block is an update, and a chain of blocks represents a history.

• Every block contains information about the previous block, as every block is built off the previous one. If any block from the past is mutated we would have to change not only information within that block but information in subsequent blocks in all the distributed copies of the blockchain

Consensus

• Defines/decides which blocks (batch of transactions) are valid, since everyone needs to agree on the history of transactions

• Not only everyone needs to agree on the update, but they also need to agree on a valid update to make sure no corrupted information is accepted

• Consensus is achieved through voting but we cannot assume that each online identity deserves the same voting power to reach consensus, as people with a lot of spare time could create multiple identities, to ensure that a vote is real, we have to make a vote expensive.

• Each vote must be cast with resources not identities, in Bitcoin the resource is computing power

• The consensus algorithm used is Proof of Work (PoW) which provides evidence that someone has spent resources. It is the method to translate computing power into voting power. Process

  • To make a proposal about a transaction someone first have to solve a problem/puzzle that requires a certain amount of computer power and is uniquely generated based on the proposed block
  • Once it finds the solution sends the proposed solution and the proposed block

• Bitcoin's correct operation hinges on one key assumption: that there is an honest majority of computational power.

• An honest majority would be able to mine faster than a malicious minority, and thus have a higher probability of creating the next block. Once the network comes to consensus on these new blocks, generally it is in a miner’s best interest to follow protocol and mine on the longest observed blockchain. The longest chain is seen as the “true” valid transaction history because it has had the most work put into it. Therefore, the majority defines the transaction history.

Forking

• Sometimes, different miners may create different blocks, either intentionally (e.g. double spending) or unintentionally, to add at the same point on the blockchain. This creates multiple chains: multiple different versions of the transaction history. We say that the blocks are competing at the same block height, and that there has been a fork. Following protocol, miners eventually resolve the fork and agree upon one of the chains to be the valid blockchain, and continue to build blocks upon it. While some forks occur naturally, and some are the result of double spending attempts, there also exist purposeful cases of forking, used to make changes to the Bitcoin protocol.
  • Soft Fork: Implement protocol updates that strictly reduces the set of valid transactions
  • Hard Fork: Allow for previously invalid transactions to become valid.

Bitcoin, Blockchain, Altcoins History and Cultural Facts

• Privacy is the power to selectively reveal oneself to the world

• Bitcoin block are created every 10 minutes and can only hold 1MB of transactions

• How do you calculate that Bitcoin blockchain can process about three transactions a second?

• Governance is the mechanism by which a protocol makes changes to itself, but no such mechanism was encoded into the Bitcoin protocol.

• Ethereum was developed as a platform to execute peer-to-peer smart contracts and applications

• Ethereum supports Turing-complete languages, meaning that it can perform general computation. This means, any type of code that I run on a regular computer can also be run on Ethereum.

• Code execution on Ethereum is fueled by Ethereum’s internal token, called ether (ETH).

ICOs

• They're a way for new projects, startups and companies to sell their underlying crypto tokens in exchange for investors money, like IPO but instead fo buying stocks you buy the coin underlying a new project, they are different because the coin doesn't give you an amount of ownership of the project the coin enables you to use the project when it becomes available

Bitcoin Mechanics & Optimizations

• Tamper-evident: means that if the information is manipulated we can easily know about this manipulation

• We need to generate unique identifiers (standardized randomness) for the meaningful data and associated these two to ensure integrity of our information

• Shouldn't be able to guess that data knowing the identifier

Cryptographic Hash functions

• Cryptographic Hash functions are one way math functions that take some input and always produce the same output for that given input

• Output looks may look random to us

• Output is of a given-fixed size

• Crypto Hash functions are a specific case of Hash functions designed for security, this means it they have the following properties:

  • Pre-image resistance: Difficult to find the input given the output
  • Second preimage resistance: Difficult to generate the same output for a similar input ; difficult to find x' such that H(x) == H(x')
  • collision resistance: Difficult to find different inputs that produce the same output ; difficult to find y and x such that H(x) == H(y)

• The consequence of these properties is the Avalanche Effect which means a small change in input can produce significant differences in the output

• Bitcoin uses SHA-256^2 (SHA-256 squared) which means SHA-256 is used twice in a row

  • Takes an input of < 2^64 bits and produces a 256 bits fixed size output

Block

• It has 4 main components:
  1. Block Header
  2. Block Size: Size of the block
  3. Transaction Counter: The number of transactions within the block
  4. Transactions: The actual transactions data

Block Header:

• The blockID (also called Block Header) is the Hash of all the fields of the block header concatenated -> BlockId = H(prevBlockHash || merkleRoot || nonce ...)

  

• The Block Header represents the Metadata for the block components, contains the fields:

  • Prev Block Hash: The Hash of the previous block

  

  • Merkle Root: Summary of transactions, the Root of the Merkle tree
    • It's a special case of a binary tree that has a power of two children and the bottommost level
    • The lowest level is made of the hashes of the information that you would like to summarize
    • The nodes are calculated with the hash of it's children so if one element is altered the alteration propagates to the top

  

  • Nonce: Proof of Work is done with Bitcoin's partial preimage hash puzzle.

    • We are given part of an input, and we have to find the other part which produces some particular output. Satisfy -> H(BlockHeader) < target
    • Difficulty A representation of the expected number of computations required to find a block. Implemented with leading zeros in the block hash, more zeros means higher difficulty

  • Timestamp:

  • Target:

  • Version:

• The coinbase transaction is a transaction that the miners include in the block which is always the first transaction of the Merkle tree

Digital Signature Schemes (DSS)

• Private and public keys are generated using ECDSA (Elliptic Curve Digital Signature Algorithm)
• The DSS must guarantee the origin of the message, that the original sender cant backtrack (deny after it has signed), that the message cannot have been modified since sending (message integrity)
• In Bitcoin we generate a private key randomly, then use one-way ECPSM (Elliptic Curve Point Scalar Multiplication) to derive a public key and finally use a Crypto Hash functions to generate a BTC Address

Bitcoin Script

• It's a language that was designed to be used for Bitcoin to process a variety of transactions like payments between two people to more complex multi-signature transactions
• Transactions contain the signature of the owner of the unspent funds, spending Bitcoin is redeeming previous transactions outputs with a proof which is constructed with a public key and a signature

Bitcoin Transactions

• A Bitcoin Transaction Contains the following fields:

  • hash: Id of the transaction
  • ver: version of the Bitcoin software using
  • vin_sz/vout_sz: number of UTXOs being referenced for the input and the number of UTXOs being created as a result of this transaction
  • size size of transaction
  • in: The inputs section contains a list of previously created UTXOs as well as a proof that you are eligible of redeeming the money (The scriptSig).
  • out: The outputs section contains a list of new UTXOs that will be sent to new addresses.
    • It contains the value of Bitcoins in Satoshis and a script the receiving user can used to proof and redeem UTXOs in this transaction

• In Bitcoin senders specific a locking script in the output of the transaction, recipients provide an unlocking script in the input whenever they want to redeem their bitcoin

• Timelocks are a type of functionality in Bitcoin that restrict the spending of funds until a later time or a specific block height.

Bitcoin Users

• There are four main functions on the Bitcoin network: Network Routing, Mining, Maintaining a full blockchain and Handling Wallet Services. A Full Node Miner contains all four

Wallets & Wallet Users

• Users who only need a wallet to help manage keys and send/receive bitcoin

• The mains functionality of a wallet is to keep track of out identity which means securing/storing a user private key and send/receive and list transactions

• Wallet forms: Smartphone Apps, Online Web-wallets (Hosted on websites), HW wallets, Paper-Wallets (literal pieces of papers with your private key printed on it) etc.

  • Hot Wallet: connected to the internet
  • Cold Storage: NOT connected to the internet

• Simple Payment Verification (SPV) is a method for verifying if a particular transactions are including in a block without downloading the entire block, just by downloading the block headers (these header include all the transactions so a Merkle Proof of Inclusion can be used). Clients using this method are called thin clients

Miners & Mining

• Mining process in detail

• A miner must:

  1. Download the entire Bitcoin Blockchain (only need to be done once)
  • This step is optional if you mine in a mining pool or are doing lightweight mining.
  2. Verify incoming Transactions. Users send transactions to the network, these wait on a mempool for the miners to include them in a block
  • Verify a transaction means running the unlocking script and check it unlocks the previous bitcoins
  • Miners choose transactions based on the transaction fee (highest fee per byte is preferred)
  • The transaction fee is a price set by the sender of a transaction which represents the cost of service for using the power of the Bitcoin Network. Transaction fees are not required for a transaction to go through, but they incentivize miners to consider choosing your transaction over other ones due to limited block space

  3. Create a block with its metadata. This means generating the Merkel Root and all the other components of a block

  4. Find the PoW, this means finding a valid Nonce. A valid nonce in this case is a nonce which makes the hash of the block header less than some target value

  5. Broadcast your block, other miners validated the block and broadcast the block once more

  • Got to win the other nodes not only in broadcasting but also on getting your block validated
  • There’s the possibility that someone else broadcasted a block before you that you haven't yet seen! Only if your block makes its way into the longest chain will you reap the rewards, you cant ensure that so you can just hope to get lucky
  6. If your block is the one included in the longest chain then you get the Profit (Block Reward + Transaction fees)

All Proof-of-Work really is at its base, a random lottery

• Mining Pools allow individual miners to combine ("pool") their computational power together, and there are many pay schemes
  • Pay-per-share: Pool pays at every share you submit regardless of how much the the pool makes, better for individuals
  • Proportional: Pays when blocks are found proportional to the work individuals have submitted for this block

Extra Bitcoin Notes and Bitcoin summary

• Other coins like Litecoin use memory-bound puzzles (e.g. Scrypt) which instead of computing power need a lot of memory, these make then more ASIC resistant but requires also a lot of memory to verify them

• Other alternative to puzzles is to chain a lot of hash functions (e.g. x11 or x13 algorithms used by DASH) or to switch mining puzzles every some random time

• Confirmations refer to the number of blocks mined on top of a block containing some particular transaction

• The Bitcoin network is peer to peer, so the way that messages get sent around the network is through a gossip protocol (also called flooding)

  • To connect to the network you first connect to a list of hardcoded seeds and peers, ask for their neighbors and repeat until you have a fairly random set of connections
  • Bitcoin allows a maximum of 125 connections per node

• Bitcoin is special because is a system that allows us to:

  • Identity -> Authentication and Integrity
  • Make Transactions -> Decentralized transactions -> Uncensorable, No central point of failure
  • Do Record keeping -> blockchain which simplistically speaking is a distributed database -> Immutable
  • Generate trust with PoW Consensus -> Trustless

• Bitcoin's intended purpose is solely to allow the transaction of bitcoins, its native asset. "It’s a global payment system"

Ethereum

• Ethereum is a decentralized platform designed to run smart contracts, it's like a distributed computer (spread across nodes around the world) to execute code

• Because of decentralization applications are run exactly as programmed without possibility of downtime, censorship, fraud or third party intervention

• Bitcoin blockchain enabled used to conduct transactions that were decentralized a more general case is to allow the execution of arbitrary computation on the blockchain that's what smart contracts enable us to do in Ethereum

• Ethereum allows the creation of decentralized apps, otherwise known as dApps which are just SW running on the Ethereum blockchain

• smart contract is a piece of code that facilitates verifies and/or enforces the negotiation or execution of a digital contract. A Trusted entity must run (enforce) this code (smart contract)

  • It has conditions or terms that must be executed on and the execution and enforcement is done through algorithms

• Ethereum is implemented as a distributed state machine and uses a user-based blockchain -> Ethereum is account based

  • Transactions on the network change the global state of the system (change the state state-machine)
  • The private keys prove ownership of an account which tracks a current balance

• Ethereum supports a Turing complete scripting language

• Ethereum is a smart contract blockchain platform, a distributed world computer. It's native asset ether(ETH) exists to fund computation and to align incentives.

• Smart contracts in Ethereum are like autonomous agents that live inside of the Ethereum network. Smart contracts react to the external world when they are poked by transactions, which call specific functions.

• Ethereum's main goal is to enable distributed and trustless computation

• Ethereum is redundantly parallel so contract executions are redundantly replicated across all nodes which makes it expensive

Account types

• Externally owned accounts

  • Owned by an entity (person, group, company, etc.)
  • Contain an address to receive ETH and an ETH balance
  • They can send transactions to transfer ether or to trigger contract code

• Contract accounts

  • "Own/store contracts" and also contain an account address to receive ETH
  • Store associated contract code and have internal storage associated
  • They control internal ETH balance, internal contract state and its permanent storage

Ethereum Virtual Machine

• Smart contracts in Ethereum are usually written in a high level programming language.

  • Most popular is Solidity (Which is like a mix of C++ & JS), Viper is another example

• Smart contracts are compiled to Ethereum Virtual Machine (EVM) code, this is the code that is executed by every node in Ethereum, then nodes come to consensus on the new state of the network by using PoW

• Miners in Ethereum competitively create blocks by executing EVM code and searching for a solution to a mining puzzle.

  • Block are created every ~15 seconds

• Gas is what fuels the execution of a given contract, every EVM op-code requires gas in order to execute so every contract requires "gas" which "fuels" contract execution

  • Every transaction specifies startgas which is the max quantity of gas is willing to consume and the gasprice which is the fee in ETH the contract is willing to pay per unit gas

• EVM execution and Gas process

  1. startgas * gasprice (represents the amount of ether paid for a computation) is subtracted from the sender who is the one invoking the contract by sending a transaction.
  2. If the contract successfully executes, then the remaining gas is refunded to the sender.
  3. If the contract execution runs out of gas before it finishes, then the execution reverts and startgas * gasprice is not refunded
  4. So a program either terminates or run out of gas

Blockchain generalizations.

• The Internet focuses much more on information exchange, while blockchain focuses on value exchange. When thinking about a blockchain use case, ask yourself whether it leverages some value exchange, particularly that which cannot be handled by a single authority. Blockchain’s innovation was not to enable distributed information sharing, but distributed record-keeping and decentralized exchange of value.

• Blockchains allow us to solve coordination failures, allow us to create a system which incentivizes individuals to operate according to our expectations.

  • When individuals don't trust each other, then the blockchain allows them to coordinate between each other

• The most abstract yet fundamental property of a good blockchain use case is pure decentralization for the sake of keeping it out of the hands of a central authority.

References, Sources and Other Links

• BerkeleyX: CS198.1x Bitcoin and Cryptocurrencies edX online course - (2018)
• Bitcoin Exchanges
• Exchange Price Compare