path: root/SI/Resource/Blockchain & Cryptography/Midterm Review - CS646.md

---
id: Midterm Review - CS646
aliases:
  - Guideline
tags: []
---

# Guideline

- ProctorU
- 10-15 questions

## History of money

- Historical definition of money
  - A medium of exchange
  - A store of value
  - A unit of account
- Monetary system: is protocols for controlling the supply of money
  - Money, payment system, monetary policy
  - banking/financial system
- Commodity vs fiat money
  - Commodity:
    - Commodity money derives its value from the commodity out of which it is
      made. Its value is determined by the value of the material from which it
      is crafted.
    - Pros: **Intrinsic Value**, **Limited Supply**
    - Cons: **Weight and Portability**, **Storage and Security**, **Dependence
      on Commodity Value**
  - Fiat:
    - Fiat money doesn’t have intrinsic value; instead, it derives its value
      from a government decree. It is not backed by a physical commodity but is
      established as money by government regulation or law.
    - Pros: **Lightweight and Portable**, **Flexible Monetary Policy**, **Not
      Tied to Commodity Fluctuations**
    - Cons: **No Intrinsic Value**, **Inflation Risk**
- M1 vs M2
  - M1: is the most liquid measure of the money supply and includes assets that
    are directly suitable for transactions.
    - **Components**:
      1. **Currency in circulation**: This includes all coins and paper money
         that are in the hands of the public, not held by the government, banks,
         or other financial institutions.
      2. **Demand deposits**: These are checking accounts or other types of bank
         accounts from which deposited funds can be quickly withdrawn without
         any restrictions.
      3. **Traveler's checks**: Although their use has diminished significantly
         with the rise of digital payment methods, traveler's checks are
         traditionally a part of M1.
      4. **Other checkable deposits (OCDs)**: This can include accounts like
         Negotiable Order of Withdrawal (NOW) accounts.
  - M2: includes all components of M1 plus near-money assets, which are
    financial assets that can easily be converted into cash or are already in a
    form that can be used for spending.
    - **Components**:
      1. **All components of M1**: Currency in circulation, demand deposits,
         traveler's checks, and other checkable deposits.
      2. **Savings accounts**: These accounts, including money market deposit
         accounts, generally allow consumers to earn interest on their deposits,
         but they might have some limitations on the number of transactions per
         month.
      3. **Time deposits**: This includes Certificates of Deposit (CDs) with a
         value under $100,000. CDs are deposit accounts with a specific maturity
         date and typically pay higher interest than regular savings accounts.
      4. **Money market mutual funds (retail)**: These are funds that typically
         invest in short-term debt securities and offer a return to their
         holders. They're relatively liquid and can be quickly converted to
         cash, though they are not as liquid as checking or savings accounts.

## Intro to Crypto

- 1-way hash (properties, attacks): is a mathematical algorithm that takes an
  input (or 'message') and produces a fixed-size string of bytes, typically a
  digest.
  - Properties:
    - One-wayness: Given an output, it is infeasible for any one to find an
      input document which is hashed to that specific output
    - Collision resistance: it is infeasible for any one to find two or more
      input documents which are hashed to the same condensed output
      - Type 1:
        - An attacker has one input document in hands
        - He attempts to find a different input document that is hashed to the
          same output as is the first input
      - Type 2:
        - An attack is not given any specific input document
        - His goal is find a pair of different input documents that are hashed
          to the same output
      - A good 1-way hash should be immune to both types of attacks
  - Attacks:
    - Brute force attack:
      - Taking advantage of “birthday paradox”
      - This is a long route, or the worst case scenario from an attacker’s
        point of view, but the best case scenario from the designer’s point of
        view
    - Attacks using short cuts:
      - Identifying inherent weaknesses of a 1-way hashing
      - The nightmare scenario from a designer’s point of view
    - Birthday Attack:
      - Based on the birthday paradox, in a set of randomly generated hash
        outputs, there's a good chance that two of them will be the same.
      - The expected # of messages to be hashed before a coincidence/collision
        occurs is $1.25 * 2^{t/2}$
- Public key encryption: is a cryptographic system that uses two keys: a public
  key, which is shared openly, and a private key, which remains confidential to
  the owner
  - RSA Public key encryption
    - Key Generation:
      1. $n=p×q \quad n,p \; prime$
      2. $\varphi(n)=(p−1)(q−1)$
      3. $1<e<\varphi(n)$ and $gcd(e,\varphi(n))=1$
      4. $e * d \equiv 1*mod(\varphi(n))$
      5. The _public key_ is $(e,n)$, and the _private key_ is $(d,n)$.
    - Encryption:
      - $c = m^e \;(mod\,N)$
    - Decryption:
      - $m = c^d \;(mod\,N)$
- Digital signature
  - DSS : A US government standard for digital signatures. It includes
    specifications for the DSA (Digital Signature Algorithm).
    - Public Key = $(y,p,q,g)$
      - $p$ = a prime of at least 2048 bits.
      - $q$ = a 160-bit prime divisor of $p - 1$.
      - $g = h^{(p-1)/q}\;mod\;p$, where _h_ is any integer with $1 < h < p - 1$
        s.t. $h^{(p-1)/q}\;mod\; p > 1$. That is _g_ has order $q\;mod\;p$.
      - $y = g^x \;mod\;p$, where _x_ is an integer randomly selected from $[1,
        q - 1]$
    - Private Key = $x$
    - Relationship: $y = g^x \;mod\;p$, $\;0 < x < q$
    - Signing a document m
      - Pick at random 𝒌 from $[1, q - 1]$.
      - $r$ = $(g^k \;mod\;p)\;mod\;q$
      - $s = (k^{-1} ∗ (HASH(m) + x ∗ r)) \;mod\;q$, where HASH is a 1-way hash
        whose output is 160 bits
      - Signature on $m$ = $(r,s)$
    - Verification:
      - Fetch Alice’s public key $(y,p,q,g)$ from the public key file
      - $w = s^{-1} \;mod\;q$
      - $a = HASH(m) * w \;mod \;q$
      - $b = r*w \;mod\;q$
      - $v = (g^a*y^b \;mod\;p)\;mod\;q$
      - OK only if $v = r$
    - **When 𝒑 is large (say ~700 digits), the best known algorithm for the
      _Discrete-Logarithm Problem_ takes an _infeasible_ amount of time (the
      problem is computationally infeasible).**
  - ECDSA: A variant of the Digital Signature Algorithm (DSA) that uses elliptic
    curve cryptography.
    - ![[CleanShot 2023-10-05 at 10.03.23 1.png]]
    - ![[CleanShot 2023-10-05 at 10.03.34 1.png]]
    - ![[CleanShot 2023-10-05 at 10.03.45 1.png]]
  - Schnorr:
    - ![[CleanShot 2023-10-05 at 09.39.10.png]]
    - ![[CleanShot 2023-10-05 at 09.40.10.png]]
  - EC-Schnorr
    - ![[CleanShot 2023-10-05 at 10.13.48.png]]
    - EC-Schnorr is better than Schnorr
      - Admit
        - Security proofs
        - Easy to implement threshold signature
        - Blind signature
      - Free of signature malleability
      - Cleaner and slightly faster: Shorter Key and Signature Lengths
- Malleability of ECDSA
  - ![[CleanShot 2023-10-05 at 10.12.51.png]]
- Multi-signature
  - Schnorr multi-signature
    - ![[CleanShot 2023-10-05 at 09.47.37.png]]
    - ![[CleanShot 2023-10-05 at 09.47.51.png]]
    - ![[CleanShot 2023-10-05 at 09.49.08.png]]
    - ![[CleanShot 2023-10-05 at 09.50.45.png]]
    - ![[CleanShot 2023-10-05 at 09.51.01.png]]
    - ![[CleanShot 2023-10-05 at 09.56.20.png]]
    - ![[CleanShot 2023-10-05 at 09.56.52.png]]
    - ![[CleanShot 2023-10-05 at 09.57.08.png]]
  - EC Schnorr multi-signature
    - ![[CleanShot 2023-10-05 at 10.19.29.png]]
    - ![[CleanShot 2023-10-05 at 10.19.34.png]]
    - ![[CleanShot 2023-10-05 at 10.19.54.png]]
    - ![[CleanShot 2023-10-05 at 10.20.04.png]]
    - ![[CleanShot 2023-10-05 at 10.20.12.png]]
    - ![[CleanShot 2023-10-05 at 10.22.39.png]]
    - ![[CleanShot 2023-10-05 at 10.22.48.png]]
    - ![[CleanShot 2023-10-05 at 10.22.54.png]]

## Chaumian cash

- 3-party model
  - Bank: Withdraw (creation of cash) to Customer
  - Customer: Payment to Shop
  - Shop: Deposit (end of life of cash) to Bank
  - ![[CleanShot 2023-10-05 at 10.29.17.png]]
  - ![[CleanShot 2023-10-05 at 10.29.24.png]]
- RSA blind signature
  - ![[CleanShot 2023-10-05 at 10.34.02.png]]
  - ![[CleanShot 2023-10-05 at 10.34.08.png]]
  - ![[CleanShot 2023-10-05 at 10.34.16.png]]
- Public and private keys used in Chaumian
  - ![[CleanShot 2023-10-05 at 10.38.05.png]]
- "Cut and choose" technique
  - ![[CleanShot 2023-10-05 at 10.55.34.png]]
- Detection of double spending
  - Hiding ID in a coin: Force the customer to embed her ID/account # into
    coins, using secret sharing technique
    - Choose s and t such that $ID = s\bigoplus t$
  - ![[CleanShot 2023-10-05 at 11.14.47.png]]
  - ![[CleanShot 2023-10-05 at 11.14.52.png]]
- Withdrawal
  - ![[CleanShot 2023-10-05 at 11.20.12.png]]
- Payment
  - ![[CleanShot 2023-10-05 at 11.22.12.png]]
- Deposit protocols
  - ![[CleanShot 2023-10-05 at 11.24.06.png]]

## Public Ledger

- Blockchain
- Transactions
  - Key components of a TX
  - TX ID
- Examples of TXs
- Bitcoin network
  - Centralized
  - Decentralized
  - Distributed
- How to explain Bitcoin to your grandma?
  - Bitcoin is a decentralized digital currency, without a central bank or
    single administrator, that can be sent from user to user on the peer-to-peer
    bitcoin network without the need for intermediaries. Transactions are
    verified by network nodes through cryptography and recorded in a public
    distributed ledger called a blockchain

## Consensus through proof of work

- Merkle hash tree: is a data structure used in computer science and
  cryptography. It is a tree in which every leaf node is labelled with the
  cryptographic hash of a data block, and every non-leaf node is labelled with
  the cryptographic hash of the labels of its child nodes. This hierarchical
  structure provides an efficient way to verify data and is commonly used in
  blockchain systems and peer-to-peer networks.
  - Pros:
    - Easy to detect modification to TXs
    - Easy to prove inclusion or membership of TX
    - Enhanced privacy
- Block header (80 bytes)
  - Version
  - Hash of previous block
  - Merkle root
  - Time
  - Target threshold
  - None
- Hash puzzle for mining/proof of work
  - Target, difficulty, hashrate etc
- ## Coinbase: is to create new bitcoin by a miner
- Thwarting double spending:
  - TXs are public & broadcast globally
  - Miners always **extend the longest chain** when forking occurs
    - **Block** in a shorter branch will eventually become. **orphaned** & be
      abandoned
    - Some TXs in the orphaned blocks **become unconfirmed**; will be picked up
      by miners for confirmation in the longest chain
- Distributed mining
- Pooled mining
  - Why:
    - Due to the increased level of difficulty, mining individually using home
      computers has become ineffective
    - Pooling together computing power increases chances of success
  - How
    - Divide-and-Conquer
      - Cut-up the space of nonces into sub-spaces
      - search for the right nonce in a distributed manner

## Bitcoin scripts

- 2 parts of a script
  - Public key script (scriptPubKey) in an unspent TX output (UTXO) received in
    the past
    - Akin to 1-time "Account #"
    - Set conditions for ownership
    - Locking UTXO to owner
  - Signature script (scriptSig) in an input of a current TX when spending
    - Proof of ownership
    - Ensuring integrity of TX
    - Unlocking UTXO by owner
- 3 types of addresses
  - Pay to Public Key Hash (P2PKH): _most popular_
    - Alice the recipient prepares a public-private key pair. She gives the hash
      value of her public key to a sender as an address to receive funds.
  - Pay to Public Key (P2PK): _natural but an address could be longer than
    P2PKH_
    - Alice the recipient prepares a public- private key pair. She gives her
      public key to a sender as an address to receive funds
  - Pay to Script Hash (P2SH) Towards programmable cash: _most powerful, make
    "programmable cash" possible_
    - Alice the recipient prepares the script. She gives its hash value to a
      sender as an address to receive funds.
- How a script is executed (stack, left to right, push & pop)
  - Script is stack based, forth-like, and written in "reverse Polish notation"
  - Scan from left to right
  - If it's data, push it onto the stack
  - If it's an operator, pop one or more items off the stack, operate on them
    and push the result back into the stack
  - ![[CleanShot 2023-10-05 at 19.17.13@2x.png]]
- Scripts for threshold multi signature
  - ??
- Common Bitcoin Opcodes/Commands:
  - OP_DUP, OP_HASH160, OP_EQUALVERIFY, OP_CHECKSIG,
    - ![[CleanShot 2023-10-05 at 19.30.19@2x.png]]
  - OP_2 - OP_16:
    - ![[CleanShot 2023-10-05 at 19.28.57@2x.png]]
  - OP_CHECKMULTISIG, OP_EQUAL