Web3 Blockchain Fundamentals MOOC

[ZhangCheng-zh]

Properties of Money

• Durability
• Portability
• Divisibility
• Uniformity
• Limited supply
• Acceptability

  Credit vs Cash

  Credit: Debt-based system Cash: 'External' medium of exchange Benefits and drawbacks to each - no perfect solution

FirstVirtual

SET Architecture

Digital Credit to Digital Cash

Cash needs to be boostrapped, but

• Has no risk of default(assuming that the underlying currency is sound!)
• Credit is by its nature not anonymous, very trackable
• With credit, you must be online(checking with a centralized authority) or willing to deal with swindlers

Chaumian Ecash

• First serious digital money proposal
• Anonymous but still required centralization

The Double-Spend Issue

How can we prevent a 'double-spend'.

• Difficult to do without a centralized source of truth
• Chaumian ecash avoids double-spend by determining AFTER the fact
• Your identity is safe unless multiple parties try to redeem your note, in which case you are fingered as the culprit... but this is done after you have eaten your hot dog and ice cream.

Anonymity

Scarcity

• Recall our fifth property of money - it must be of limited supply, you must work to get it
• Computers can do computation work
• So we can we use computation as the backing for our currency?

Computational Backing

"Bitcoin is Hashcash extended with inflation control" - Adam Back

Ledgers

• How to determine the order / timestamp of documents in a decentralized manner?
• If we know Document d1 was written before d2, and d2 before d3, etc. we can have a good idea of when a document was written( and definitely know the order)
• How to enforce order? Links to previous document!
• This makes a chain of document...

Use Linked Timestamps

Efficiency of Linked Timestamps

• Turns out this is very inefficient for large number of documents, and we also usually dont need that much granularity
• Improvement: collect documents into groups(blocks) and only have the signature link going from block to block
• in other words, a 'block chain'

Bitcion-style Blockciain

Bitcoin

• The first modern cryptocurrency
• Decentralized - no central arbiter and no easy way to censor transactions
• Transactions signed cryptographically
• Blocks added to a blockchain with proof of work, and those who add them are rewarded with bitcions

Resolving the double-spend issue

• With Bitcoin, creating the link to a pprevious block (and generating a new one via a complex computational challenge) creates money.
• In case of conflict, chain with most work behind it wins (originally it was the longest chain, this has since been modified)
• This is what miner are doing and what they are rewrded for
• Key modification that allowed Bitcoin to solve previous digital money problems

[ZhangCheng-zh]

Cryptocurrency

Encryption

Symmetric-Key Encryption

Kerckhoff's Principle

• The security of a system must depend only on the secrecy of the key, and not the secrecy of the algorithm
• Security through obscurity is not a valid defense
• How could you break our Caesar cipher, even if you don't know Ke.

Breaking Caesar

• Frequency Analysis
• Known Plaintext Attack
• Brute Force

Symmetric-Key Encryption Weakness

• How do Alice and Bob share keys Ke or Ka? they will need a separate, secure channel
• But if they have a separate, secure channel, why use an insecure one?

Asymmetric-Key Encryption

• Two different keys: one to encrypt, P, a separate one to decrypt, S
• P is your public key. Anyone can encrypt a message to you with it
• S is your secret( or private) key - you can use it along with P to decrypt a message(as its name implies, you should keep it private!)

Public-Key Encryption Fundamentals

• Bob tells the world about Pbob but keeps Sbob secret
• If Alice wants to communicate with Bob, she can encrypt a message m to ciphertext c with function E(Pbob, m)
• The only way to DECRYPT the message is with function D(Sbob, C) which requires knowledge of Sbob

Secure Communication Without Secure Channels

• Bob can also communicate with Alice by using Alice's public key, Palice
• Alice and Bob can communicate over an insecure channel, even if all communication is over that channel
• Eve will only ever see ciphertext c

Public/Private Key Generation

• Public/private keys share a relationship - they are not just two random values
• Bitcoin uses ECDSA to generate your key pair
• There are other possibilities (such as RSA)
• For now, just know the concept

Efficiency - one problem

• Turns out asymmetric encryption itself is extremely inefficient compared to symmetric encryption
• Most modern systems use a hybrid approach

Step 1: Establish a secure communications channel using asymmetric encryption Step 2: Share a symmetric encryption key Step 3: Use symmetric encryption for further communication

Public Key Infrastructure(PKI)

• How do I know that Pbob is actually Bob's key and not Eve's ? Very important for websites / users - make sure you are on amazon.com , not amazoon.com
• Various approaches: certificate authorities, web of trust, SPKI, even some bloackchain-based appraaches
• with most cryptocurrencies, no built-in PKI - if you have the key, you 'own' the coins associated with that account
• "Not yours keys, not your coins"

One-Way Functions

• A one-way function (or trapdoor function) is a function y = f(x) where, given y, it is computationally infeasible to calculate x, but given x, it it possible to calculate y
• That is, while y= f(x) is (relatively) easy to calculate, its inverse x=f'(y), is much more difficult, perhaps impossible, to calculate

One-Way Function Example

• Assume function f is simply the 'square' function
• Calculating y=f(27) is relatively simple, even by hand: 27 * 27 = 729
• However, calculating its inverse ('square root') x = f'(729) is much more difficult
• Obviously, computers have harder algorithms than square / square root but the idea is the same

[ZhangCheng-zh]

Introduction to Hashing

What is a hash function?

• A function which accepts some arbitrary input x and returns a fixed-length digest("summary value")
• Let's look at "bad hash"

Bad Hash

• Converts all values in a string to their ASCII values
• Sums up all of these values
• Returns value modulo 256(result 0x0 - 0xFF)
• Note: this is a valid hashing function, but as its name implies, not a good one for most purposes

Hash vs Cryptographic Hash

• Hash values can be used for a variety of purposes
• These different kinds of hash functions will have different propeties
• For our purpose, we are interested in using hash functions for cryptographic hashes

Cryptographic Hashes

Should have the following properties:

• collision-free
• hiding
• puzzle-friendly

Collisions Always Exist

Finding Collisions

• Brute force is always possible, but timescales for large hash functions are massive (millions of years using today's computers or even networks of computers)
• But holes are always possible in any hash function

Using A Hash As a Message Digest

• Generally speaking, if H(x) == H(y), we can be reasonably certain that x == y
• So if we want to check, say, if we have seen something before, we can store its hash instead of the actual data

Hiding

• Given the result of a hash function H(x), it is infeasible to "go backwards" to determine x
• That is, H(x) should be a one-way function

Hiding: A Formal Definition

• A hash function H is said to be hiding when a secret value is chosen from a probability distribution that has high min-entropy, then given H(r || x), it is infeasible to find x.
• min-entropy: a measure of how predictable an outcome is
• In other words, for any given input, if r is chosen uniformly, the result is likely to be any one of the possible output values

Bad Hash - Is it hiding?

• NO
• Adding an additional character will strongly favor one half of the possibilities in our output.

Application of Hiding: Commitment

• Assume you want to wager on something happening, but you don't want others to know your guess

Commitment Scheme

com := commit(m, nonce)
verify(com, msg, nonce)

A nonce is random value that can be used only once. Nonces will come up very often in our exploration of Bitcoin.

Assumes the commit function is hiding and binding

Binding = collision - resistant Given two pairs m / nonce and m' / nonce', it is infeasible to find m != m' and commit(m, nonce) == commit(m', nonce')

• To commit to something:

com = commit(msg, nonce) Publish com publicly

• To "open the envelope"

  Publish nonce and msg publicly Anyone can use verify(com, msg, nonce) function to verify msg

Commitment Scheme Example

• You are betting with your friend, "Who will be US President next year?" but you don't want to declare it
• Name: "Bill Laborn", Nonce: "324255234"
• com = commit(msg, nonce)
• SHA-256('Bill Laboon 324255234")
• Publicly announce that hash value

Puzzle Friendliness

• For every possible n-bit output value y, if k chosen from a distribution with high min-entropy, then it is infeasible to find x such that H(k || x) == y in time significantly less than Math.pow(2, n)

• In other words, if someone wants the hash value result H(x) to be a particular value y, if H(x) produces a result of size n bits, then finding some value x such that H(x) == y should require at least pow(2, n) attempts(O(pow(2,n))

• In other other words, the best way to find the result of a hash function is to just do the hash with different inputs, and brute force it.

Puzzle Friendliness Application

• Proof of work
• I want to prove that you have done some work before you get a prize
• So I may ask you to find a value x where H(x) = 0
• Best way to do it should be to just try every possible input

Is Bad Hash PuzzleFriendly ?

• No
• Very easy to determine output and modify input to modify output
• Bad hash has a shortcut to find x from H(x)

Hash Functions Used in Bitcoin

many fields

SHA-256

• SHA-256 is a "good" hash for our purposes
• As far as we know (it has not been proven!), it is

  Collision-resistant Hiding Puzzle-friendly

[ZhangCheng-zh]

Hashing In-Depth

Hash Pointers and Related Data Structures

What is a hash pointer?

• Two parts

  A pointer to some object or data set A cryptographic hash of that data or representation of that object

What good are hash pointers?

• Regular pointers(or object references on Java) can tell you where data is
• Hash Pointers tell you that, plus let you verify that it has not been modified

Data Structures with Hash Pointers

• Many data structures which use pointers / references can have their pointers / references replaced with hash pointers
• This makes them tamper-resistant versions of the 'naive' data structure

Linked List with Hash Pointers

Tamper-Resistant

Hash pointer of previous data includes both data in node and hash of preceding node.

Binary Tree with Hash Pointers

Merkle Tree:

Proving Membership with a Merkle Tree

Why Merkle Trees?

• Good access time
• Can just store Merkle root to verify entire tree
• Verify membership

Where Are Merkle Trees Used in Bitcoin?

• The Merkle root in a block is the Merkle root of all transactions tn that block
• Allows mining to be approximately equally difficult no matter how many transactions are included

And thus incentivizes miners to add more transactions, so they get transaction fee

Where Can't We Use Hash Pointers ?

• Data Structures without explicit pointers / references(e.g. arrays)
• Data Structures which can include cycles

Cyclic structures = no starting point for hashes

[ZhangCheng-zh]

Blockchain related data structures and concepts

More Hashing, Digital Signatures and Centralized Legers

Merkle-Damgard Transforms

• Recall that hash functions should compress an arbitary-length string into a fixed-size output
• Also recall our initial attempt at this, BadHash

Covert each character into a corresponding value, sum them up modulo size of output Variety of problems with this scheme

• Merkle-Damgard Transforms solve some of the problems converting arbitrary "input to fixed output" using a very similar process to a blockchain
• "Chunks" data into blocks (padding if necessary)
• Accepts results of previous blocks along with current block to produce a new output

compression algorithm accepts two arguments: current block (size m) and previous result (size n) outputs result of size n (where n < m)

• Can repeat as many times as needed

Example:

Digital Signatures

• We have already discussed how cryptographic hashes can be used to hide information
• We can also use them to prove our identity using digital signatures

Characteristics of Digital Signatures

• Only I can make a signature, but anyone can verify its validity
• The signature cannot be re-used. it is tied to a specific document (= set of bits)
• Signature creation does NOT have to be deterministic
• Note this is more powerful than a hand-written signature which can easily be forged, cannot easily be validated, and can be re-used

Digital Signature Scheme = Three Algorithms

(sk, pk) = generateKeys(keysize)

Given a key size keysize, return a 'keypair' - a public key used for verification and a secret key for signing

sig = sig(sk, message)

Given a secret key sk and a message, return a signature for that message

isValid = verify(pk, message, sig)

Given a public key pk, a message, and a signature, return a Boolean value indicating whether or not the message was properly signed

Key = Identity

• Now that I can always prove that I am me, I have a digital identity
• If I want a new identity, I can always make a new keypair - I will be just another face in the crowd

  But be careful! Could use other ways to link your real identity to a generated keypair

• If someone wants to impersonate me, it should be computationally infeasible

GoofyCoin

• The first rule of GoofyCoin is that only one entity, Goofy, can create a new coin, and all new coins belong to Goofy
• The second rule of GoofyCoin is whoever owns a coin can transfer the coin to somebody else
• Both of these rules can be implemented using cryptographic operations

Generating Money With GoofyCoin

• Goofy generates a unique coin ID u
• Goofy computes a digital signature s with his secret key
• u || s(u concatenated with s) is a coin
• Anyone can run verify(pk, u, s) to determine if a coin is valid (i.e., has been signed by Goofy)

Transferring Coins with GoofyCoin

• Goofy creates a new transaction "Give this to Alice", where this is a hash pointer to a coin and Alice is Alice's public key
• Then Goofy signs that transaction with his private key
• Anyone can now verify that Goofy generated the coin and that it was transferred to Alice
• Since Alice's public key is specified in the transaction, if Alice tries to send the coin to someone else, she will need the corresponding secret key to the address it was sent to
• Anyone can verify that the secret key she used to sign off sending the coin to someone else matches the public key used to give the coin to her
• You need public key to send to, you need secret key to send from

The GoofyCoin Ecosystem

• Goofy can generate an infinite amount of new coins (as long as he can think up new unique strings)
• Whoever owns a coin can transfer it by saying "Give this to the person with public key X"
• Anybody can verify by following the "chain of ownership" back to Goofy (the originator of all coins)

Creating Coin

Transfer Coin

Continue Transfer Coin

Problem

• What if Alice gave that coin to Bob and neither Bob nor Alice have told anyone
• Alice can also give the coin to Carol and Bob would be none the wiser!
• Double-spending attack

To solve this problem, ScroogeCoin is Here

• Transactions occur just as in GoofyCoin But...
• Scrooge also creates an append-only ledger(blockchain) where people can verify that a coin transfer is "official"
• Scrooge determines that a transaction is valid (i.e. signed correctly and no double-spend) and signs the block
• Transactions that are not recorded on Scrooge's blockchain( and signed with Scrooge's digital signature) are not official

Problems with ScroogeCoin

• Scrooge can't steal coins (as he does not know secret keys of individual account holders)
• But he can:

  Blacklist users or coins Create new coins for himself Stop updating the blockchain (holding the entire system hostage)

Centralization

• So far, technical challenges have been minimal - earlier cryptocurrencies got to approximately this far, but all relied on some centralized intermediary
• Central technical challenge and breakthrough of BitCoin: how do we come to a consensus of valid transaction without a coordinating entity? We need to figure out a way:

  For users to agree on a single, published, authoritative blockchain For users to agree on what transactions are valid and which occurred IDs to be assigned in a decentralized way Minting of coins to be done in a decentralized way

[ZhangCheng-zh]

Decentralization

ScroogeCoin Recap

• Using public-key cryptography and a blockchain validated by Scrooge (a centralized validator), we had a basic but functioning cryptocurrency
• HOWEVER- Scrooge was a weak point!

  He generated all coin He could punish users by not adding transactions to his blockchain He could hold the entire system ransom by refusing to update

Decentralizing ScroogeCoin

• Can we obtain the same benefits of ScroogeCoin without a centralized party?
• Spoiler alert: YES! We will make a few simple attempts and see what other trade-offs are made to achieve it, as well as try to find problems with these simpler solutions

Centralization vs Decentralization: The Very Idea

• There is always a tension between centralization and decentralization, not just in cryptocurrency
• Examples: Roman Empire vs Greek city-states, Apple vs Android ecosystems, mainframes vs personal computers
• Benefits and drawbacks- everything is a trade-off
• Most systems are a hybrid: ever try to set up your own SMTP server?

Bitcoin: Designed to Be Decentralized

"Abstract. A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution, but the main benefits are lost if a trusted third party is still required to prevent double-spending"

• Satoshi Nakomoto

How To Decentralize?

• Who maintains the ledgers of transactions?
• Who has authority over which transactions are valid?
• Who creates new bitcoins?
• Who determines how the rules of the system change?
• How do bitcoins acquire exchange value?

How Decentralized is Bitcoin?

• Different aspects = different levels of centralization, BUT the possibility always exists for further decentralization
• Bitcoin network itself = Very decentralized - easy to spin up a fully-validating node
• Mining = Somewhat centralized - Open to anyone, but hard to do profitably and large economies of scale
• Updating protocol/rules = Very centralized in practice - Vast majority of nodes use Bitcoin Core. Anyone can write their own node software (or use an alternative such as BitcoinJ), but the VAST majority use Core

Distributed Consensus

• How can a group of users come to a consensus on the "true" state of something(ledger, activity, status)?
• Distributed Consensus protocol: There are n nodes that each have an input value. Some of these nodes are faulty or malicious. A distributed consensus protocol has the following properties:
  • It must terminate with all honest nodes in agreement on the value
  • The value must have been generated by an honest node.

Transactions in Bitcoin

Alice want to pay Bob one bitcoin:

Possible Consensus Mechanism

Every Node(circle) has: 1 The blockchain up to that point in time 2 A list of outstanding transactions which have been broadcast but are not yet in the blockchain (the transaction pool or mempool)

Different nodes may have different transaction lists Every 10 minutes, nodes use some consensus mechanism (e.g. voting) to determine which transactions are put in blockchain. If a transaction is missed, no problem, wait for the next block!

Problem with Naive Consensus Protocol

• No notion of universal time (who decides when it has been 10 minutes?)
• What consensus mechanism to use?
• Network is imperfect - some nodes will have high latency, faults in network, how many nodes actually exist?
• Malicious users could provide invalid / spam transactions

Distributed Systems And Time

• Segal's Law: ` A man with a watch knows what time it is. A man with two watches is never sure"
• Lack of a centralized mechanism of time control (or even a supposedly-centralized mechanism like NTP) means that event-ordering is not strictly possible!
• Many common algorithms will not work when you don't / can't have a concept of " do x, THEN y"

Sybil Attacks

Simplified Bitcoin Consensus Algorithm

• New Transactions broadcast to all nodes
• Each node collects new Transactions into a block
• In each "round", a random node gets to broadcast its block (note: assuming we can avoid Sybil attacks here!)
• Other nodes accept block if all transactions are valid
• Nodes express acceptance by including its hash in the next block (lengthening the chain)

• Recall all nodes have copy of blockchain
• Red packages all valid transaction into block, adds to blockchain
• Red broadcasts new blockchain
• Other nodes add red's blockchain with new block and hash pointer

Denial Of Service

• Red packages all valid transactions (EXCEPT bob's) into block
• Adds valid block to blockchain, which does not have Bob's transaction
• Red broadcasts new blockchain
• Other nodes add red's blockchain with new block and hash pointer

Double-Spend w/ Simplified Consensus

• Alice purchases software from Bob for one bitcoin and generates a transaction to that effect
• An honest node includes it in the blockchain
• Bob sees that it has been confirmed, Alice downloads software
• Alice node is selected for next block
• Instead of building on block n, she builds on block n - 1, ignoring the previous block and making her own block n where the bitcoin go to another address she control
• Transaction to Bob is useLess - bitcoin in that block cannot be used by him in later blocks because it is not under his control

Protecting Against Double-Spend with Simplified Consensus

• More blocks in blockchain since transaction, harder for someone to generate a different blockchain with different blocks
• General rule in Bitcoin: wait six blocks (heuristic)

What about Sybil Attacks?

• Two related assumptions: > 50% of nodes are honest, plus invulnerable to Sybil attacks?
• Not true in practice... so how to avoid?
• Next lecture: incentives, proof of work, proof of stake, and mining

[ZhangCheng-zh]

proof of work and mining

Recall Our Naive Consensus Protocol

• "Pick a node at random, allow them to add their transactions in their transaction pool to blockchain"
• Problems:
  • How to pick a random node?
  • Assumes honest nodes - easy to subvert
  • Nothing at stake, no reason to be honest

Incentives

• We can't punish dishonest nodes but...
• What if there was an incentive to be an honest node ?
• How about... bitcoins?

Incentives in Bitcoin

• Two incentive mechanisms:
  • Block reward
  • Transaction fees

Block Reward

• The creator of a valid block gets a reward (currently 12.5 bitcoin - halves every 210,000 blocks, will drop to 6.25 around May 2020)
• Block reward only valid if it's on long-term consensus branch, which means other nodes must accept it
• If longest-valid-branch, will incentivize to work off of longest branch and be honest
• Creating blocks is hard work (as we will see) - don't want to waste it!

The Future of the Block Reward

• No other way to generate bitcoins besides block reward
• Block rewards will end around the year 2140 (they keep halving approximately four years, for much longer than that they will be so small as to be insignificant)
• So... nobody will mine from 2140 on, right?

Transaction Fees

• The other incentive mechanism is transaction fees
• The creator of a transaction can decide to give themselves back less in "change" than necessary
• This "missing bitcoin" can be claimed by the miner of a block

UTXOs

• Although we think of bitcoin as a distributed ledger where address X has 4 bitcoin and address Y has 2.5 bitcoin, really each has a collection of unspent transaction outputs, that is, transactions that have been input to an address but not yet output to another
• We can tally up these outputs and determine the full amount of bitcoin that a particular address has, but behind the scenes they are actually a collection of these outputs

Transactions Behind the Scenes

Splitting TXs - Sending 0.4 btc

Multiple TX Input / Output

Transaction Fees

• `Ceteris paribus, miners prefer to include transactions with higher fees
  • There are reasons not to do so, however, which we will discuss later...
• Think of it as bidding for space or express mail - if you want your transaction in a block quickly, you gotta pay more

Proof of Work

• What's to stop you from going out there and making a block yourself and gathering some transaction fees? NOTHING!

As Long You Can Provide a Valid Block

• To create a block is going to require work (a tax on identity - avoids Sybil attacks, or at least cheap ones)
• Bitcoin uses SHA-256 hash puzzles, i.e., find a block with a nonce(number used once) such that a hash of concatenation of the nonce, the hash of the previous block, and all transactions in the block is less than some target
• H(nonce || prev_hash || tx1 || tx2 || ... txn) < target

Recall Puzzle-Friendliness of SHA-256 Hash

• No solving strategy for H(id || x) ( Y better than trying possible values of id
• Inother words, assuming a non-trivial target, we are going to have to try some very large number of nonces (with no shortcuts) before we find a nonce such that H(nonce || rest_of_block) < target
• And trying different values is the ONLY way to do so - no shortcut, one-way function

Hash Puzzle Properties

• should be difficult to compute
• Parameterizable (i.e. adjustable) cost
• Trivial to verify

Difficult to Compute

• We want people to prove that they have worked for this (to avoid Sybil attacks / nothing-at-stake problem)
• As of the creation of this slide, miners around the world are trying >100 quintillion possible blocks every second, and they generally don't find a solution until after about them minutes of this!
• This number of attempts per second is called the hash rate or hash power of the Bitcoin network

Paramaterizable Cost

• January 12,2009 - hash rate was (best estimate) 4,500,000(orders of magnitude lower than today)
• But blocks still were generated at a rate of about one every ten minutes
• Target re-adjusts itself every 2016 blocks based on (self-reported!) block times
  • If block are taking longer than 10 minutes, difficulty adjusts down (target increases, making it easier to find nonce)
  • If blocks are taking less than 10 minutes, difficulty adjusts up(target decreases, making it harder to find nonce)

Impact of Puzzle-Friendliness

• Solving hash values is probabilistic - some blocks are produced within seconds (or even "negative" time - remember dealing with time in a distributed system!), others can take hours
• Average is ~ 10 minutes

Bernoulli Trials

• A Bernoulli trial is a process with two possible outcomes (success and failure), and the probability of being successful (and by implication, failure) is fixed between trials
• Examples: coin flip, dice, roulette
• Mining: Success - H(nonce || rest_of_block) < target Failure - H(nonce || rest_of_block) >= target

Poisson Process

• Iterated Bernoulli trials (at large enough numbers so that we can basically act as if the result is continuous instead of discrete) represent a Poisson process
  • A continuous probabilistic process where events soccer independently at a constant average rate
  • Likelihood of a block occurring follows an exponential distribution

Poisson Process - Mining Bitcoin

• No nonces have been tried - what is the mean time until H(nonce || rest_of_block) < target?
• 500 quintillion nonces have been tried - what is the mean time until H(nonce || rest_of_block) < target? all are ten minutes

Poisson Process - Dice

• I just rolled 1. How many rolls on average until I roll a 6?
• I just rolled 4,3,3,4,4,2,1,4,5. How many rolls on average until I roll a 6 ?

How Long for a Given Miner To Find a Block?

• I don't care about the network as a whole, I care about me!

mean time to my next block = 10 m / fraction of hash power I control

Trivial to Verify

• It should be very difficult to MINE a block, but easy for others to verify that it is valid
• Computationally simple
  • Run SHA-256 hash function against block with miner-calculated nonce
  • if H(nonce || rest_of_block) < target, block is valid

Mining Overview

// Should I mine Bitcoin?
mining_reward = block_reward + tx_fees
mining_cost = hardware_cost + operating_costs
if (mining_reward > mining_cost)
    return true
else
    return false

51% Attack

• Recall that a key tenet of Bitcoin is decentralization
• Mining allows us to perform distributed consensus and avoid a ScroogeCoin-like(or a Scrooge hiding behind an army of Sybils) centralization
• But what if more than half of the hashpower is owned by a single entity? Is this a new Scrooge?

What Can our Pseudo-Scrooge Do?

• Steal coins? No. The only way to move coins is knowing the secret key of the owner(public key)
• Suppress transactions? Yes. Just list Scrooge, they can ignore transactions and refuse to put them in blocks - but users will see transactions in mempool and realize this attack is occurring.
• Change the block reward? No. They cannot change the rules of consensus - valid nodes will ignore the blocks
• Double-spend? Yes. They can decide to build off a blockchain which does not include the block which includes a sent transaction
• Hurt confidence in Bitcoin? Yes. A key benefit of Bitcoin lies in its decentralized nature; destroying this may start an exodus to alternatives

A Pale Yet Dangerous Shadow

• Scrooge could change the block rewrad, suppress transactions without others realizing, or even change the rules of consensus - none of which our Pseudo-Scrooge can do
• Decentralization has benefits even when it's been centralized!

[ZhangCheng-zh]

Mining In-Depth

Being A Miner

• Listen for transactions(Maintain tx pool)
• Maintain and update blockchain (listen for new blocks)
• Assemble a candidate block
• Find a nonce that fits the candidate block where H(block) < target, or generate a different candidate block
• Found, broadcast your block (and hope others accept it) coinbase gets sent to address you control (with locktime)

Finding a Valid Block

Generate Block Using Merkle Root of Tx Tree

example:https://blockchair.com/bitcoin/block/741014

Try Nonces, 0 through pow(2, 32) - 1, Only pow(2,32) nonces?

• Yes, But we can always modify the candidate block in other way
  • Use a different subset of transactions
  • Modify the coinbase(unused scriptSig) attribute
  • Send coinbase to a different address
  • Modify timestamp
  • Anything that modifies a transaction will also modify the Merkle root

Keep Modifying Candidate Block Until H(block) < target

Once it does, broadcast it ASAP to the network

How Do I Know the Target?

• Calculated from the mining difficulty, which changes self-correcting every 2016 blocks:

SHA-256 and Double-SHA-256

• SHA-256: Secure Hashing Algorithm, part of NSA's SHA-2 series of cryptographic hashes
• Some conspiracy theories!
• H(block) = SHA-256 hash of the SHA-256 hash of the block (double-SHA-256 hash)

How Does SHA-256 work?

• standard Merkle-Damgard construction (with a few twists)
• Output: 256 bits, Block size: 512 bits
• Initialization vector (by necessity also 256 bits) = fractional parts of the cube roots of the first 64 primes (to avoid accusations of backdoor values)
• Strengthening (padding): a 1 and then as many 0s to get up to 448 bits, followed by a 64-bit length of string

SHA-256

• Goal is for miners to compute as many SHA-256 hashes as possible in a short a time as possible to maximize block production
• By-hand rate, 0.67hashes / day

CPU Mining

• In the original Bitcoin paper, Satoshi Nakamoto seemed to imply that most/many nodes would also mine
• "One CPU, one vote"
• With well-optimized software, on a regular desktop or laptop, you can get several tens of millions of hashes per second

GPU Mining

• Soon after Bitcoin's release (~2010), GPU programming became popular
• GPUs allow you to massively parallelize relatively simple operations (such as the ones necessary for SHA-256 calculations)
• GPU increased hash power by approximately an order of magnitude over a CPU
• And you could run multiple GPUs off a single computer!
• The era of mining rigs

The Brief Reign of FPGAs

• GPUS are better for mining than CPUs, but still not optimized - lots of superfluous hardware. e.g. for floating-point arithmetic
• Around 2011, people moved to field-programmable gate arrays - basically "programmable integrated circuits"
• Performance of FPGAs is about an order of magnitude better than GPUs, but prone to failure and costly

ASICs: From 2012 to Now

• Application-Specific Integrated Circuits - specialized computers that can do nothing but mine Bitcoin
• Although not as fast as in the years of 2012-2014, improvements still come quickly
• Once newer generation mining hardware is out there, older hardware rapidly becomes a very expensive electric heater

Energy Consumption

• Recall that we need proof-of-work to allow for decentralized generation of valid blocks (need to have "skin in the game" to avoid spamming network with invalid blocks / building off other chains / etc.)
• But this comes at cost - currently estimated at ~73 TWh / year(0.33% of worldwide electricity usage, approximately equivalent to Austria)

Can We Increase Efficiency?

• Definitely! As we have already seen!
  • but Bitcoin mining is a Red Queen's Race (have to go faster just to stay still) - as long as it is profitable to mine, people will do so, and mining is a zero-sum game
• Plus, limits on efficiency - `Landauer's Principle' -Could we eliminate mining entirely? ... we'll go back to this later on in the term!

Is Bitcoin Mining Wasteful?

• Any payment system requires energy (digging gold out of the ground, printing dollar bills, running a bank, etc.)
• Mining = securing the network, under Bitcoin's rules, the security of a network comes from the vast amount of hashing that is being done
• Mining rewards can be thought of as "stored electricity"

Can we make it less wasteful?

• Renewable energy
• Use otherwise-wasted electricity
• Bitcoin miners are essentially space heaters - can we utilize the generated heat instead of venting it?

You still want to mine Bitcoin?

• OK, you go out and spend $10000 on ASICs from Bitmain
• You start paying an extra $500 / month on your electricity bill
• But your income is sporadic - an entire year can easily go by without you finding a block (so you just spent $500 * 12 + $10000 = $16000 with no return)
• or you could find two blocks in a row the day after you set out your rig, giving you ~$170,000 in block rewards

Mining Pools

• What if you could work with others to make a "collective" where you all pitched in to work and smoothed your earnings (reduce variance)?
• A mining pool is a collective of miners generally run by a pool manager (who takes a small cut).

Mining Shares

• How do you prove that you're contributing to the pool?
• Turn in near misses AND hits (where H(block) < (target + value))
• Only way to generate misses is using your hash power!
• such entry is a "share" in the next block reward

Mining Payout

• Pay-per-share: every share you submit to the pool entitles you to a flat amount of bitcoin
• Proportional: every share you submit gives you a higher proportion of bitcoin found in the next block - if no block is ever found, no reward for you!
• Note: most proportional mining pools actually use PPLNS(Pay-Per-Last-N-Shares) or Score algorithm proportion weighted by time submitted) due to pool dropping and other game theory

What's to Stop You From Withholding A Valid Block?

• Technically, nothing - this is called a block withholding attack
• But from a game theory perspective, you're just wasting hash power, so hopefully you have a non-economic reason for doing so!

What About Block Modification?

• The blocks you are given (and the shares generated from them) all have a coinbase transaction pointing to the pool operator's address
• Modifying the payout address will modify the coinbase transaction which will modify the Merkle root
• you may as well just mine on your own then!

Can Pools Be Too Powerful?

• Recall that a pool acts under the supervision of a pool manager but otherwise act as one "giant miner"?
• GHash.IO briefly had > 50% of hash power in 2014
  • Intentionally reduced it themselves to avoid potential loss in trust to the Bitcoin network
• Could super-powerful miners be hiding their actual hash power by joining multiple pools?
• This is called hash laundering

Mining Pools: Good or Bad?

• Pros: reduce variance for smaller miners, make it easier for miners to get involved, easy way to upgrade network (can't join pool unless you have upgraded to latest version of bitcoin software)
• Cons: one form of centralization, reduce the number of fully validating Bitcoin nodes (only one necessary per pool)

Mining Decisions

• You have access to hardware, cheap electricity, and an Internet connection. You can mine - either on a pool or on your own. Now you (or your mining software) needs to decide:
  • Which transactions should I include in the next block?
  • Which block should I mine on (deal withchainsplits)?

Attacks By Miners

• Seems like there are some good default answers built-in to the software
• But could we maximize our payout by modifying these algorithms?
• This will most likely have a negative impact on other miners which is why they are often called attacks?

Forking Attack

Forking Attack via Bribery

• Out-of-band: Go to biggest pool managers with a bag of cash with a giant dollar bill painted on the side
• Run a pool at a loss (i.e pay more for shares than they're worth) - attract hash power
• Leave big "tips" (i.e. transactions) in transactions only valid on the forked chain to entire others to build on it
• Site: something similar appears to happened recently in EOS, an altcoin blockchain

Block-Withholding

• Generally, you want to announce immediately to the world that you found a block - at any moment someone else could find one, and general algorithm is to build on the block you found first
• But what if you hold on to your block, then try to build a second block on top of that one before you broadcast
• If you are now two blocks ahead of the network, all of the hash power thay've been using has been wasted
• Selfish mining - all other blocks produces are immediately orphaned, and you have a head start on creating the third block
• Can be an improvement over default strategy if your hash power is over 1 / 4 of the network! Kind of a backer 51% attack

Blacklisting / Punitive Forking

• We have already discussed blacklisting particular UTXOs / addresses
• However, in the absence of a centralized controller, others could always include transactions in a block, it just might take longer
• But if we have sufficient mining power, we can take this to the next level with punitive forking
• Not only will I not include those transactions,I won't mine on any chain that includes those transactions

Feather Forking

• Punitive forking is really only an issue if you have a majority of hash power (variation of 51% attack), otherwise a big waste of time (you waste your hash power on a chain nobody else is following, blacklisted transaction goes through anyways on main chain)
• Feather forking - You'll attempt to fork, but eventually give up if you can't do it. Probability of success is pow(a, 2) (where a = your percentage of hash power of entire network)
• is pow(a, 2) and not a ? You need to get at least one block ahead of everybody else (i.e. generate two blocks before someone else generates one).

So What ?

• Assume you have 15% of hash power (note that many pools have had this or more - I chose this number because it is current approximate hash power of both the btc.com and AntPool pools
• Probability of a successful feather fork = pow(0.15, 2) = 0.0225 = 2.25%
• if you are another miner, and you don't care about the evil transaction one way or the other, will you take that risk?

[ZhangCheng-zh]

Mechanics of Cryptocurrency

Bitcoin Consensus

• Append-only ledger(via blockchain)
• Decentralized consensus (via consensus mechanisms)
• Validation of transactions (via miners & proof-of-work)

Account-Based Ledger

• Accounts (could still be delineated by public keys) would have a certain number of bitcoins
• A transaction would e.g. take five coin from Alice and give five coins to Bob

Efficiency Issues

Transaction-Based Model(Bitcoin)

• Every transaction has valid inputs and outputs
  • Properly signed
  • Inputs must be consumed entirely
  • Total value of outputs <= inputs
• "Accounts" are just a collection of UTXOs(unspent transaction outputs)

Refresher: UTXOs

Verification Only Back Until Coin Creation

Joint Payment - 10 Bitcoin To Carol From Bob & Alice

A Look at a Raw Block

• That was conceptual - let's look at an actual block (in JSON - key:value format)
• Blocks generally indicated by hash or height
• Block 000000000000000000024e913801f94cf9b3053dc8db3883f5407f5483e2c38b

Anatomy of a Block

• Information in these slides is correct as of the slides' creation date! Bitcoin block structure is liable to change even more in the future.
• Metadata: Information about the block (size, block, number, Merkle root, nonce, etc.)
• Transactions:
  • Array of all transactions in this block
  • Number of transaction must be >= 1!(coinbase transaction always present)

Block Metadata

Compare to Genesis Block

Transactions

• Metadata
  • Information about the transaction (hash, size, number of inputs, number of outputs, lock time)
• Input
  • Previous output (all inputs are previous outputs, except coinbase) to be consumed, signature
• Outputs
  • Value of output, a Script script (note: no recipient address directly specified here!)

Transaction Metadata

• weight
• time
• tx_index
• vin_sz
• hash
• vout_sz
• relayed_by
• lock_time
• ver
• size

Transaction Inputs

Transaction Outputs

Programmable Money

• Bitcoin is programmable money
• A transaction specifies a script to execute
• The VAST majority of scripts just move previous transaction outputs to a new address, we can (theoretically) do anything that the Script language lets us
  • Although other nodes may have something to say about that...

Script - The Bitcoin Scripting Language

• Inputs contain scripts (scriptSig atttribute) and outputs contain scripts (scriptPubKey) - concatenated and executed
• Script
  • Stack-based language
  • Not Turing-complete (purposely limited)
  • Native support for complex cryptographic functions
  • Note: you may see a hex version of this in a blockchain explorer - think of it as the actual bytecode instead of helpful mnemonics

Stack-Based Programming

Why Not Turing-Complete?

• Would never be able to determine if program would end (Halting Problem)
• Could force arbitary-length execution on validating nodes (denialof-service attack)
• In practice, only a very few kinds of scripts are allowed by most validating nodes (whitelist)
• See Ethereum (especially concept of gas) for one way to have a Turing-complete language running on a blockchain

Common Script Commands

• VALUE: Put value on top of stack
• OP_DUP: Duplicate top item on stack
• OP_HASH160: Hash value on top of stack with SHA-256, then hash again with RIPEMD-160 and put final value back on stack
• OP_EQUALVERIFY: Return true if top two values of stack are equal, return false and mark transaction if not
• OP_CHECKSIG: Check that the input signature is valid using the input public key for the hash of the current transaction

Script Execution Walkthrough

• Concatenate scriptSig and scriptPubKey
• Execute script

Basic Bitcoin Script

Proof of Burn

• Proof of burn extablishes that a transaction has been destroyed
• Why? Destroy bitcoin to generate some other token
• How? Add an OP_RETURN opcode to the scriptPubKey of the transaction - script will always return false

P2PKH vs P2SH

• P2PKH - Pay to Public Key Hash (remember address are actually hashes of hashes of a public key, so "indirectly pay to address"
• P2SH - Pay to Script Hash (allow easy multisig or other more complex transactions - not part of original Bitcoin spec, added as BIP-16 in 2012)
• Additional transaction types:
  • P2PK - "Pay to Public Key" - generally not used since 0.3, not supported since 0.8
  • P2WPKH - "Pay To Wintess Public Hey Hash" - SegWit(Segregated Witness) transaction

[ZhangCheng-zh]

Network Concepts

Join the Bitcoin Network

Dynamic Random Topology

The Gossip Protocol

Valid Transactions at the Gossip Level

• Is the transaction valid whithin the current block chain? (i.e. does scriptSig || scriptPubKey return true?)
• Have the transaction outputs being used as inputs not already been redeemed (i.e., are they unspent?)
• Has this node not seen this transaction before?
• Is the script whitelisted?

Transaction Propagation

• Relatively slow process (decentralization and efficiency are often at loggerheads)
• Block propagation has gotten much faster with optimizations and focus
• Interestingly, though the number of (known) fully validating nodes has remained about the same!(~10000)

Storage (as of 16 February 2020)

• Current size of the Bitcoin Blockchain (~262 gigabytes (monotonically increasing))
• Size of the Bitcoin transaction pool over the last week: (25Million bytes)
• If you really want to get down in the weeds

Fully Validating Nodes

• Connect to the Bitcoin network and act as a full peer
• Download and verify the entire blockchain (generally > 24 hours to do so)
• Verify / propagate / drop transactions
• Broadcast transactions

SPV("Lightweight") Nodes

• Simple Payment Verification
• Not as secure as a fully validating node - only downloads headers of blocks, so checks that blocks and their hashes are valid, but not every single transaction in the block
• Can ONLY validate transactions that "affect them", not the entire network
• The majority of nodes on the Bitcoin network are SPV nodes - if you use a Bitcoin wallet, chances are it is an SPV node.

Why Run a Lightweight Node?

• Storage / CPU usage savings ~~ three orders of magnitude (1 / 1000th) compared to a fully validating node
• Very little "lag time" when spinning up a node

The Evolution of Bitcoin

• Want to change Bitcoin? File a BIP. Some notable active BIPs:
  • BIP-11: Added MULTISIG support - Used for excrow
  • BIP-13: Added P2SH
  • BIP-141: Added SegWit support - Prevent transaction malleability, allow second-tier scaling to take place

Escrow Transactions

Remember: Bitcoin transactions are immutable once they are completed and on the blockchain! third-party arbiter: Judy buyer: Alice legitimate businessman: Bob need to be signatured by 2 of 3

Kinds of Forks

• Hard Fork: Introduce new features were previously considered invalid; previous versions of software will not accept new blocks
  • Can lead to chain splits ("coin forks", e.g. Bitcoin Cash, Bitcoin Gold, Bitcoin Private)
• Soft fork: Make validation rules stricter; previous versions of software will still accept blocks produced under the stricter rules

Changes to Consensus

• How do people decide?
• If nodes accept changes, that change continues
• Other nodes can follow along or go off on their own which has happened before!
  • Bitcoin Classic, Bitcoin XT, Bitcoin Unlimited - all are now subsumed under Bitcoin Cash

Limitations of Bitcoin Network

• Known implementation bugs (e.g. MULTISIG instruction popping multiple values off of the stack)
• Transactions per scond (~7)
• Fixed cryptographic hashing algorithm (SHA-256, RIPEMD-160, ECDSA / secp256k1)
• Future / minor issues: divisibility smaller than satoshis, number of operations per block, Year 2106 problem)
• Not likely to ever be modified: number of bitcoin produced, mean time between blocks, block rewards / halvening
• Difficult / impossible to fix most of these without a hard fork

[ZhangCheng-zh]

Achieving Consensus

Consensus

• Consensus about rules - How do nodes communicate? What kinds of data is sent over the network? What makes a transaction valid?
• Consensus about history - What is the correct blockchain?
• Consensus about value - What is the value of any amount of bitcoin that I use ? Is there a value attached to the "token" that I send?

Consensus Relationships

Consensus in Value

• If I were to give you $10 for some goods or services, why do you accept it?
• Why would you accept cryptocurrency instead?

How to Determine Value

• This is essentially subjective
• Empirical solutions: oracles or other off-chain references (e.g. latest average price across exchanges), pegs (e.g. Tether), not mapped to other prices at all (e.g. testnet coins)

Consensus About History

• Providing a canonical history is what blockchain is all about!
• But - you need to agree on what the rules are on what constitutes a valid block and what constitutes the canonical chain

BIP(Bitcoin Improvement Proposal)

• Minor changes are done via pull request to the Bitcoin Core Github repository
• Major changes need a BIP
• Formally open to anyone, but there's definitely a lot to learn before you file a BIP!

Who's In Charge?

• Developers - They write the code
• Miners - They write history and decide which transactions are valid.
• Users - They decide which consensus to follow.
• Investors - They buy and hold, thus providing a value for Bitcoin.
• Merchants - They are the only ones who could make Bitcoin with anything, by accepting it in return for goods and services

Blockchain Hard Fork

Hard Fork and New Currency

• Hard forks do not necessarily lead to a new currency
• Network upgrades are not necessarily hard forks
  • Example: Polkadot upgrades its runtime by storing the runtime state transition function on-chain; changing the runtime changes the rules without a hard fork

Monero Network Upgrade

Love it or leave it

• The right to fork and start your own currency - either by building off the current blockchain, or creating your own blockchain, is extremely powerful
• Nobody is holding you hostage - many people have started their own related currencies forking either code or the entire blockchain

Major Bitcoin Fork

• Bticoin XT - 8 MB blocks, launched late 2014, Failed to activate (needed 75% consensus).
• BitCoin Classic - 2 MB blocks, launched early 2016, officially folded in November 2017, officially supported Bitcoin Cash
• Bitcoin Cash - 8 MB (now 32 MB) blocks, forked August 2017. By far the most popular Bitcoin fork.
• Bitcoin Gold - ASIC-resistant EquiHash algorithm replaced SHA-256, forked October 2017.
• Bitcoin Private - ASIC-resistant EquiHash algorithm replaced SHA-256 hash-style optional anonymity. Forked February 2018.

Bitcoin Cash Split

• The largest split in Bitcoin history - August 1st, 2017
• Bitcoin Cash: Did not implement SegWit; increased block size to 8MB
• Bitcoin (Bitcoin Core): Implemented SegWit via UASF; modified block size limit to be a block weight limit

Bitcoin Core

• General consensus is that Bitcoin Core is the "model implementation"
• There are a few others, but they tend to defer to Core and are only a very small percentage of active nodes

Bitcoin Cash

• Several competing implementations exist

User-Activated Soft Fork(UASF)

• Nodes create a soft fork but without the support of miners
• Playing "chicken" with the miners! Proof of work majority will want to follow economic majority
• Most famous UASFs: introduction of SegWit(BIP 141); production of P2SH(BIP 16)

Bitcoin Scalability Debate

• Second-tier scaling("small-blockers")
• Layer One scaling, e.g. increasing block size("big-blockers)

Small Blocker Arguments

• Increasing block size is a temporary solution
• Larger blockchain makes it harder for nodes to participate, thus centralizing nodes
• Centralized nodes make a future UASF more difficult (putting more power in hands of miners)
• Secondary scaling solutions are available
• hard fork is an attack vector on Bitcoin itself

Big Blocker Arguments

• Big blocks = more room for transactions, and thus lower fees
• Big blocks = faster transactions (less jockeying for space in a block, thus less waiting)
• Secondary scaling is ripe for centralization
• Secondary scaling is an additional attack / failure vector
• It might be slightly more difficult to run a node, but more people will use Bitcoin more often, thus incentivizing more people to run nodes

Satoshi's Thoughts

• The original Bitcoin did not have a block size limit
• Satoshi added it IN SECRET as part of another commit!
• Rumors that others who noticed it were asked to keep it secret, as well
• Although not explained well, generally seen as an anti-Dos measure

What is Bitcoin?

• Store of Value? (small-blocker argument)
• Means of exchange? (big-blocker argument)
• Both?

Ethereum / Ethereum Classic

• DAO hack - allowed a hacker to drain a large amount of funds from a small contract
• This was a significant portion of Ether - should code be law(ETC), or should a pragmatic decision be made to essentially return the fund(ETH)?

Categories of Consensus

• Probabilistic
  • You are never 100% sure you are following the correct or longest chain
  • Simple to implement
  • Nakamoto consensus most famous example
• Provable
  • You can prove that you are on the canonical chain
  • More complex and can be vulnerable to stalling

Practical Byzantine Fault Tolerance(pBFT)

• Classic provable finality solution
• Works well with small number of nodes
• Vulnerable to stalling
• Some features are proven mathematically
• E.g., as long as 2 / 3 + 1 of all nodes honest, result are valid

Variations

• Tendermint - Used by Cosmos. Evolved to be "plug and play" into other blockchains. More performant that pBFT, but still vulnerable to stalling (prefers safety over liveness).
• Casper FFG - Used by Ethereum 2.0. Prefers liveness over safety - finalization can slow down
• GrandPA - GHOST- Based Recursive Ancestor Deriving Prefix Agreement - Used in Polkadot. Allows quick conciliation after network partition. Divorced from block production, so even if it stalls, block production can continue until fix later

[ZhangCheng-zh]

Using Cryptocurrency

Owning Bitcoin

• Owning bitcoin really means:
  • I have the ability to control an UTXOs sent to some set of addresses (loosely, public keys) and generate new transactions from them...
  • ...which I can prove by signing said transactions with the corresponding secret keys for each address."

Public Keys != Addresses

• Although a public key can be a kind of public address, in Bitcoin (and most cryptocurrencies) it is slightly more complex
• Your address is A(pk), where A() is a rather convoluted multi-hashing process (will briefly cover this in a few slides)
• Thus, P2PKH ("pay-to-public-key-hash") as opposed to P2PK ("pay-to-public-key")
• addresses are generally represented in Base58Check format

Base58Check Encoding

• Just like binary (base 2) has 2 possible values (01), octal (base 8) has 8 (01234567), hexadecimal (base 16) has 16 (0123456789ABCDEF), Base58 has 58(1 ~ 9A~Za~z)
• Note that O (capital O), 0(zero), 1(lowercase L), and I (capital I) are omitted to avoid confusion
  • Thus, the "1" at the beginning of standard Bitcoin addresses actually means the value "0"!
  • B58Check also includes a four-byte checksum at the end to ensure unrate transcription

A Number Base58Check is still a Number

Bitcoin Address Generation From a Public Key

• Generate an ECDSA keypair, and take its public key
• Take the SHA-256 hash of the public key
• Take the RIPEMD-160 hash of the SHA-256 hash generated in the step above
• Prepend a "0" (i.e. "1") to indicate this is a Bitcoin Mainnet address.
• Take the SHA-256 hash of the prepended RIPEMD-160 hash
• Take the SHA-256 hash of the previous SHA-256 hash
• Take the first four bytes of that last SHA-256 hash and store it as a checksum
• Append the four-byte checksum to the end of the prepended address found in
• revert the result from Step 8 to Base58Check encoding

What If I want a specific address?

• 1CS1699xxxxxxxxxxx is a valid address, I want it!
• Recall that generating an address means taking a randomly generated public key, pretending it with 1, then hashing it(twice, with two different hash algorithms) then adding a checksum
• go, generating an address equal to a value or matching the pattern can be seen as a kind of Bernoulli trial

Vanity Address Generation

-Just like mining, we can just keep trying with different inputs For each character we want, there is a 1 / 58 chance we will get the correct one, ergo chances are 1 / pow(58,k) for a k-character pattern -Luckily, programs can do this for us... do this locally! keys have been stolen from "online vanity generations!" Also note that there are some possible efficiency optimizations sheer random guesses, see book for details

How do I store my cryptocurrency?

• Storing cryptocurrency is ALL about managing your secret (and to a lesser extent, your public) keys
• But there are a variety of ways to do so, with various trade-offs, mainly: Availability; Security; Convenience

Hot vs Cold Storage

• Hot Storage: Transactions can be directly made; implies general network connectivity (i.e. node or node-proxy is online)
• Cold storage: Transactions cannot be directly sent (i.e. secret keys are offline)
• Note: With most blockchains, cold storage retains the possibility of sending funds to it even if offline

Wallet Software (Hot)

-Sofeware on your computer or phone which keeps track of your keys, coins, makes transactions, etc.

• Usually a SPV node or connected to a SPV node
• Think of it as the wallet in your pocket - simple to use and understand, but pickpockets are rife!
• availability: HIGH, Convenience: HIGH, Security: LOW

Paper Wallet(Cold)

• A generated address /secret key which is printed out and kept on piece of paper Availability: LOW, Convenience: LOW, Security: MEDIUM

Brain Wallet (Cold)

• Remember a pass phrase and use the hash of it as a seed to pseudorandomly generate a keypair Availability: LOW, Convenience: LOW, Security: LOW/MEDIUM

Hardware Wallet (hybrid hot / cold)

• Simple devices (not full computers) which generate keys and/or sign transactions, but secret keys never leave device
• Transaction are fed in, signed, and output
• Examples: Trezor, Nano, Parity Signer Availability: MEDIUM, Convenience: MEDIUM, Security: HIGH

Why Address Re-Use is a bad idea

• Leaks information about your identity
• Assume you have been sending transactions all of your life to a single address. If anyone links that address to you, they know you have several hundred thousand dollars in Bitcoin
• Assume you pay your landlord in Bitcoin from the same address every month and get paid from your employer to the same address. Now your landlord knows you can afford a raise in rent
• Bitcoin wallet can generate a large (in practical terms, infinite) number of addresses, so let's use them

Hierarchical Deterministic Wallets

• Instead of a wallet specifically generating an address, it generates a way to create a series of unlinked addresses, but to which it has all of the secret keys
• Now you can have as many addresses as you like, but "see" them all in your wallet as a single Bitcoin "address"
  • Recall that tx inputs can come from multiple addresses!
  • BIP 32

Splitting and Sharing Keys

• Assume my wife and I want veto power over spending from out joint Bitcoin account - i.e. we both need to agree that Bill buying a Bitcoin sweater is a good use of our funds, and so we want to only be able to reconstruct our key if both of us agree
• How can I do this?

Naive Splitting

• one hash split into two part

Secret Sharing - K of N

• Idea: Given some values K and N and K <= N, can we split the key into N pieces such that if we have K shares we can determine the key...
• ...but having any number of shares n (where n > 0 and m < K), we will not gain any knowledge of the key?

Secret Sharing

• Suppose N = 2, K = 2, and our secret key S is 128 bits.
• Generate a random 128-bit value R
• Two shares: R and (S XOR R)
• Together, can calculate S; otherwise, basically random numbers
• an extrapolate out to any N >= 2 and K >= 2 BUT N must equal K

What if we want K != N ?

• Example: I want to bequeath my bitcoin to my son upon my death. I want to split my key into three, so that 2/3 of my lawyer, me, and my wife can determine my key
• Or extrapolate this out further: 2 out of 6 board members must agree to spend money from a corporation's bitcoin account, or 5 out of 9 justices on a gurt must agree to pay bitcoin held in escrow

2-of-n Secret Sharing

2-of-n Secret Sharing, One share

3-of-n Secret Sharing

you need have 3 or more points on the parabola

Arbitrary k-of-n Secret Sharing

• Determine key(randomly)
• Determine k, and randomly generate a(k - 1) - order polynomial which intersects origin at 0, key
• Determine n random points on the function and dirtribute
• an expand indefinitely via lagrange interpolation

Threshold Signatures

-Problem with previous schemes - they all generate the actual secret key, which is a point of weakness (key can be stolen after reconstruction and used on its own)

• There is a (mathematically complex) way to make partial signatures and if enough actors generate partial signatures, they can sign a transaction with a key without ever revealing the key or even their key shares
• voids the single point of failure problem above

Online wallet

• Software runs online where you havean account
• You will either need to enter key or they will store it in an encrypted format
• Very convenient! No installation on your part
• If you don't have the keys, though, or they are grabbing keys that you pass in, big, security worry. NOT YOUR KEYS, NOT YOUR COINS

Online Exchange

• Online wallet plus place to buy / sell bitcoin (like a stock exchange... I'll give you $9.25 for one share of Ford, or I'll give you $6595.76 for one bitcoin)
• Fractional reserve- Just like real banks, exchanges promise to give you your bitcoin when you ask for it, but may not actually have it!
• very convenient, offloads responsibility, but there are risks with trusting any bank

Risk 1: Bank / Exchange Runs

• Many people ask for their money back at a bank; bank does not have enough cash on hand
• Rumors spread that bank is insolvent
• More people try to cash out, exacerbating problem
• In US, bank accounts are backed by FDIC so this couldn't happen (since the FDIC can always print more money... can't print more bitcoins!)

Risk 2: counterparty Risk

• Bank /exchange is not really planning on giving people the bitcoin that is rightfully theirs
• "exit scam"
• Ponzi scheme: paying people who ask for bitcoin with newcomer's bitcoin

Risk 3: Security Breach

• A hacker could break into the exchange's software and move all of their bitcoin
• There in no "arbiter" to determine who "rightly" owens some bitcoin
• Why do you rob banks? Cause that's where the money is .

[ZhangCheng-zh]

Cryptocurrency and Anonymity

What Do We Mean By "Anonymity"?

• From the Greek - an - "without" + onoma "name"

• Is Bitcoin anonymous?

  • Yes - If we mean, can be used without your real name
  • NO - If we mean, can you use no "name" at all

  Bitcoin is Pseudonymous

• Also from the greek: pseudes "false" + onuma "name"
• Your name is your address/PK, so you do have a "pseudo-identity", even though you can generate more

What about anonymity ?

• The technical definition of anonymity
  • A pseudonymous system which also provides
  • unlinkability (individual but distinct interactions should not be traceable to a single identity

Why do we even want anonymity?

• Recall that every Bitcoin transaction that has ever taken place is recorded(directly or indirectly) on the blockchain
• Motivation One: Have the same level of privacy that you do when using a bank/credit card (where only some others have access to your transaction history)
• Motivation Two: Make it computationally infeasible for someone to track the participants in a transaction

The ethics of anonymity

• Personal privacy - do you want your co-workers to know your salary?
• Business privacy - do you want your competitors to know who your suppliers are?
• Political privacy - do you want others to know to whom has send political contributions?

On the other hand

• Truly anonymous currency can be used to evade taxes, launder money, participate in 'dark markets', gamble illegally, etc.

Squaring the circle

• Potential idea: can technology be implemented such that users can reap the benefits of anonymity as long as they are doing good things with it?
• No! You have to take the good with the bad if we want to be decentralized. Otherwise, we would depend upon a central arbiter to determine the good/bad use cases.
• particular "bad" and "good" use cases look the same on the point of view of the technology!

Crypto-anarchy

• Being able to communicate and exchange information with no way for others to monitor you weaks the power of the state
• With Bitcoin, money is now a form of communication

Is pseudonymity enough?

• Perhaps - but not if your goal is privacy!
• Blockchain is public - and if your real identity can be linked to your address, you can easily be de-anonymized
  • Many, many, many ways to do this
  • it is very difficult to avoid leaking information

So

• Bitcoin is pseudonymous, NOT anonymous
• Operating under the assumption that anonymity is good (anonymity = pseudonymity + unlinkability)
• Trivial for anyone to follow transactions
• steps can be taken to improve anonymity!

Ideal world: unlinkability

• It should be hard to link together different address of the same user.
• It should be hard to link together different transactions of the same user.
• It should be hard to link the sender of the payment to recipient

Deanonymization via side-channels

• side channel = indirect(i.e. off-chain) leakages of information
• Examples:
  • Paying with Bitcoin at a coffee shop exposes your physical body to barista
  • Analysis of usage times can be used to determine time zone
  • Re-using or posting addresses
  • special meaning behind vanity address?

Anonymity set

• Turns out the third concept is rather difficult (since identity A needs to verify that they sent a certain amount to identity B, as does identity B - and we are vulnerable to traffic analysis)
• But what we can do is hide the transaction in with a bunch of others
• the anonymity set - the set of transactions an adversary not distinguish from your own transaction
• Adversaries may be able to know that you made a transaction, but they can't tell which one of some set
• The larger the number of possible transactions, the better able to hide you are
  • Cicada strategy
• Note that this is not one specific number! Different adversaries may have more motivation / skill / resources minimize the anonymity set further than others
• To calculate, need to determine:
  • What the adversary DEFINITELY(trivially) knows
  • What the adversary PROBABLY DOESN'T know
  • What the adversary CANNOT know

Taint Analysis

• How related are two Bitcoin identities?
• If coins from S always end up in R even if they go through intermediaries a,b,c,..., S and R are highly "tainted"(have a high taint score)
• ameliorated by avoiding address re-use

Linking - Change Address

0.08 BTC or 0.02 BTC Payment?

Avoid Address Re-Use

Idioms of Use

• Change addresses tend to be fresh addresses
• Shared spending implies a single identity
• Verification via re-identification attacks

Real-world IDs: TXs/Addresses

• If you can link part of a cluster to a real-world identity, you now know much more about cluster and that real-world identity!
• Ways to do it:
  • Directly transacting
  • Via service providers
  • Carelessness (posting address in forum)
  • Anonymization tends to get worse over time ( as an archers discover better deanonymization techniques)

Transaction Graph analysis

Network-level deanonymization

• We have seen how we can use the blockchain to create a transaction graph and analyze it in order to deanonymize
• But we can also use the Bitcoin network itself
• Seminal work here was done by Dan Kaminsky

Nuts and bolts of network-level deanonymization

Avoiding network-level deanonymization

• Need to hide your IP (using Tor or similar service)
• However, Tor:
  • Can be blocked
  • Is very slow and not well-suited to running on the bitcoin network
  • dandelion protocol

Offline / off-chain transfers

• Harder, but possible
• See openDime

Mixers

• Want to improve anonymity, need to improve anonymity set
• Exchanges are theoretically good, but often have KYC or other requirements
• dedicated mixing services

Multi-mix

Should You Trust a Mixer?

• You need to trust them with your bitcoin, even if momentarily
• Many, many, many scams
• Network effect difficulty - need to have large number of people using same mixer for high anonymity set (different mixers, different chunk sizes)
• Turns out tracking is possible since few (if any?) mixers follow the practices

CoinJoin

• Single-transaction mixing
  • find peers who want to mix
  • exchange input/output addresses
  • construct transaction
  • send the transaction around. Each peer signs after verifying their output is present
  • broadcast the transaction

Problems with coinjoin

• Vulnerable to denial-of-service attacks
• hard to defend against bad actors in a decentralized system
• Possible to leak data via side channels with poor implementation

Privacy-focused altcoins

• ZCash - zk-SNARKS (zero-knowledge Succinct Non Intercative Argument of knowledge proofs); anonymity by choice
• Monero - Ring signatures, RingCT (Ring Confidential Transactions), stealth addresses

Other Privacy Enhancements

• Wasabi wallet, Samourai Wallet - Bilt-in Coinjoin with every bitcoin transaction
• Tornado.cash - Users can submit ether to a big pot, then use zs-SNARKs to withdraw an equivalent amount
• AZTEC - Privacy engine for Ethereum to obscure input to output addresses