diff options
Diffstat (limited to 'SI/Resource/Blockchain & Cryptography/Midterm Review - CS646.md')
| -rw-r--r-- | SI/Resource/Blockchain & Cryptography/Midterm Review - CS646.md | 309 |
1 files changed, 309 insertions, 0 deletions
diff --git a/SI/Resource/Blockchain & Cryptography/Midterm Review - CS646.md b/SI/Resource/Blockchain & Cryptography/Midterm Review - CS646.md new file mode 100644 index 0000000..5658631 --- /dev/null +++ b/SI/Resource/Blockchain & Cryptography/Midterm Review - CS646.md @@ -0,0 +1,309 @@ +--- +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 |