bchain

AI 101

Announcements

  • Welcome to Computing Security
    • Blockchain
  • Action Items:
    • BTCinC

Today

  • Background
  • Blocks
    • Just structs

Background

2000s

  • Dotcom crash (~2000)
    • Many digital currency failed
    • Many ecommerce sites failed
    • Many internet banks (e.g. Net.B@nk) fail
    • Most large sites (Amazon, Cisco) contracted ~80%
  • Centralized servers are politically weak.

2008

  • Great Recession (~2007-)
    • Traditional currency liquity crises
    • Many banks fail
    • Many surviving banks reorganize
    • Huge pressure on governments, central currencies
  • Centralized banks are politically week

Open question

  • How can the client of a currency system:
    • Have access to currency that is
      • Non-physical
      • Non-governmental
      • Non-repudiable
        • Transactions cannot be denied to have happened

Bitcoin

  • Bitcoin is the first blockchain
    • Has no central server
      • Not like ecash with DigiCash, Inc. (failed in Dotcom)
      • Not like USD with the US Treasury (~failed in Great Recession)
    • Allows transactions
      • I can transfer n coins to someone

Features

  • Achieves consensus
    • Transactions cannot be ‘repudiated’ (no chargeback)
    • Cannot spend coins you don’t have
  • Relies on cryptography (instead of servers)
    • Uses RSA for privacy/anonymity
    • Uses SHA for nonrepudiation
  • Uses ‘proof of work’ C. Dwork ’92

Nakamoto ’08

Genesis Block

Blocks

Bitcoin

In this paper, we propose a solution to the double-spending problem using a peer-to-peer distributed timestamp server to generate computational proof of the chronological order of transactions

  • Peer-to-peer
  • Distributed
  • Timestamped (gulp)
  • Computational proofs
  • Chronological ordering
  • Transactions

Transactions

A chain of digital signatures

  • Vs physical coin, a record data struct.
    • Records can be stored in multiple locations, coins cannot
    • Records can produced by anyone, coins cannot
    • Records describe ownership, coins cannot
      • “My” coins don’t have my name on them.
      • “My” bitcoins do

A transaction

Each owner transfers the coin to the next by digitally signing a hash of the previous transaction and the public key of the next owner and adding these to the end of the coin

  • Me and \(n\) friends owners \(m\) coins
  • We all have public keys.
  • We transfer those coins to \(p\) new owners
  • We write this down.

Signage

  • To verify it is (1) our coins and (2) use transferring them, we:
    • Write down the details.
    • SHA256 hash the message
    • RSA encrypt with our private key
    • Release the hash and cipher text

Verify

  • The general public:
    • Decrypts the ciphertext with our public key
    • SHA256 hashes the decrypted text
    • If the hash matches our released hash, then it had to be us and the transaction is valid.

RSA_Encryption cluster_encryption Encryption cluster_decryption Decryption message Message (M) encrypt Ciphertext (C) = M^e mod n message->encrypt inter Encrypted Transaction encrypt->inter public_key_ref Private Key: (n, d) public_key_ref->encrypt ciphertext Ciphertext (C) decrypt Message (M) = C^d mod n ciphertext->decrypt output Decrypted Transaction decrypt->output private_key_ref Public Key: (n, e) private_key_ref->decrypt input Unencrypted Transaction input->message inter->ciphertext

RSA_Encryption cluster_encryption Encryption cluster_digest_pre Precompression cluster_digest_post Postcompression cluster_decryption Decryption cluster_check Integrity Check message Message (M) encrypt Ciphertext (C) = M^e mod n message->encrypt inter Encrypted Transaction encrypt->inter public_key_ref Private Key: (n, d) public_key_ref->encrypt shamsg Message (M) checksum Checksum: sha256 M shamsg->checksum digestpre Tx Digest 1 (MD1) checksum->digestpre squares H^(0) squares->checksum shamsg2 Message (M) checksum2 Checksum: sha256 M shamsg2->checksum2 digestpost Tx Digest 0 (MD0) checksum2->digestpost squares2 H^(0) squares2->checksum2 ciphertext Ciphertext (C) decrypt Message (M) = C^d mod n ciphertext->decrypt output Decrypted Transaction decrypt->output private_key_ref Public Key: (n, e) private_key_ref->decrypt pre MD0 check MD1 == MD0 pre->check post MD1 post->check accept Transaction Acceptance check->accept input Unencrypted Transaction input->message input->shamsg inter->ciphertext output->shamsg2 digestpre->pre digestpost->post

Demo

  • Buckerinos accepted, who needs banks 👍

Wait a minute

  • What stops this from happening?

Doublecount

The problem of course is the payee can’t verify that one of the owners did not double-spend the coin.

  • Banks with only n coins are the exact problem

With Physicalcoin

  • The (central?) bank is sole arbiter of providing credit with those coins.
  • Banks with finite coins are vulnerable to bank runs.
  • Banks have operating expenses that incur transaction costs.
  • A bank must be trusted (very tough in early 2009, or… ever?)

Ledgers

  • All transactions are logged publicly (and verifiable publicly)
    • A “public ledger”
  • These transactions in aggregate form the blockchain.
  • As of ~now the chain is ~600 GB
  • It can be “pruned” down to ~5 GB
  • Remember, transactions = coins.

Aside: Metadata

  • In theory, Bitcoin can be anonymous.
    • I generate a key, never tell anyone.
    • Participate like anyone else.
    • The key has nothing in common with my identity.

Aside: Limits

Timestamps

The solution we propose begins with a timestamp server

  • Publicly announce every transaction.
  • Throw in a struct.
  • Hash it every 10 minutes.

From Paper

Each timestamp includes the previous timestamp in sits hash, forming a chain, with each additional timestamp reinforcing the ones before it.

Abstract Tx’s

  • For now, we abstract how transactions are handled.
    • We assume the existence of merkle.h
    • Future week
  • We can get timestamps froms <times.h>
  • We can get hashes from shainc or sha256sum

Block

bchain.h
typedef struct digest_struct {
    /* sha256 - 8 * 32 = 256 */
    uint32_t h[8];
} digest;

struct blockchain_struct {
    /* hash of previous block */
    digest  prev_h;
    /* hash of transaction tree */
    digest  tree_h;
    /* time stamp */
    time_t  time_s;
    /* ???? */
};

Doublespend

  • How does this help?
    • In theory, evidence of past transactions, but…
    • Isn’t it easy enough to spend twice and there be different chains of blocks?
    • With the no central server, what is authoritative.

Solution

  • Two parts:
    • First spend is authoritative
      • Established by timestamps
    • Blocks are expensive to forge
      • This is “bitcoin mining”

Proof of work

  • Make a block except the nonce.
    • “Number used once”
    • The fourth field, with previous, transactions, and time.
  • Pick arbitrary nonce.
  • Then loop:
    • While the hash of the block doesn’t have some trailing zeros…
    • Pick a new nonce.

It’s hard.

  • Let’s get one trailing zero.
  • Add utf-8 “nonce”.

Difficulty

  • Bitcoin has a scaling difficulty.
    • Every binary trailing zero is 2x as hard.
    • Every hex trailing zero is 16x as hard.
    • Exponentially scaling.
  • It targets 1 block per 10 minutes across as bitcoin miners
    • So every participant tries to find the nonce and it takes 10 minutes.

Quoth SN:

  • SN: Proof-of-work is “one-CPU-one-vote”
    • Me: In absolutely no way is this decentralized
    • Me: ~65% of active/public CPUs are owned by AWS/AZ/GCP
    • Me: A cryptography expert happens to have a proposed a currency that would be de facto centralized by the NSA and its tera+scale cryptography datacenters at time of proposal.

Logging

The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it.

  • Security (undeniability) scales with age.
  • Forks can happen (two hashes discovered on different contents within nanoseconds)
  • Most famous fork: Bitcoin and Bitcoin Cash
  • The chain gets more secure every 10 minutes.

Compute

If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains.

  • Big ‘if’
  • Bitcoin good at “dubiously legal”
  • The same authorities with majority of CPU power (trillion dollar companies, US Govt) also influence or control fiat currency (USD, Apple/Google Pay)

Climate

To compensate for increasing hardware speed and varying interest in running nodes over time, the proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour.

  • Bitcoin becomes less efficient/more costly to use over time (by necessity)
  • Miners are more efficient per hash - driving GPU development and a little bit the AI boom.

The Network

Bitcoin Network

  1. New transactions are broadcast to all nodes
  2. Each node collects makes a block.
  3. Each node starts proof-of-work for its block.
  4. If found, broadcasts the block to all nodes.
  5. Nodes accept the block only if all transactions in it are valid (no doublespend).
  6. Nodes accept via starting on the next block.

Broadcast

New transactions are broadcast to all nodes

  • You have seen broadcasts:
    • Within Node.js, a server could receive information and broadcast it publicly.
    • There is existing support in the npm (node package manager) ecosystem.
    • You shouldn’t mine in Node.js and you shouldn’t store on network, but it’s worth a look.
  • There is nothing wrong with thinking of the Bitcoin network as many Node.js servers pinging each other.
  • Doing this well, much less exhaustively, is non-trivial, but doing it “at all” is easy.

Aside: Example

  • This implements the message server of the famous impossibility result from Nancy Lynch that led to the eventual bitcoin result.

Collect

Each node collects new transactions into a block.

bchain.h
struct blockchain_struct {
    /* hash of previous block */
    digest  prev_h;
    /* hash of transaction tree */
    digest  tree_h;
    /* time stamp */
    time_t  time_s;
    /* number used once */
    digest  n_once; /* Nonce has to be digest sized. Why? */
};

Work / Mine

  • Just hash in a loop with a counter.
    • Hash
    • Probably bitshift the result or something.
    • See if zero
      • If yes, broadcast*
      • If no, incrememnt counter.
  • Broadcasting out-of-scope for now.

Broadcast II

When a node finds a proof-of-work, it broadcasts the block to all nodes.

  • Only miners must listen for transactions.
  • All users must listen for blocks.
  • When your transaction is in a block, its means you gained/lost a coin.
  • Until then, in flux.

Accept

Nodes accept the block only if all transactions in it are valid and not already spent.

  • All nodes inspect transaction history for doublecounts, etc.
  • If found, they keep working on the ‘old’ block, which isn’t fraudulent
  • Fraudelent blocks are expensive to make and unlikely to be accepted.

Express

Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash.

  • A block is known to have been expected once it is a previous block to a working block.
  • So, block n-2 is known accepted, n-1 is likely accepted but there may be candidates, n is currently being mined.

In my words:

  1. Broadcast (Transactions)
  2. Collect
  3. Work/Mine
  4. Broadcast (Block)
  5. Accept
  6. Express

Today

  • ✓ Background
  • ✓ Blocks
    • Just structs

Closing thoughts

  • Make a block
  • Put in a list
  • Bam! Blockchain
    • Lists that can’t lie.