Five districts await

Historically, money is defined by three functions. All three must be present for the historical definition.

Money is accepted for goods and services, avoiding direct barter. The course example is cow → money → corn.

A person can retain money as a commonly recognized form of value.

Money gives a common measure for prices and wealth: “How rich are you?”

The Internet-age token-for-debiting-and-crediting definition is a contrast, not one of the historical three. Money, a payments system, and monetary policy are distinct parts of a monetary system.

A one-way hash maps an input of any length, even an empty string, to a short fixed-length output; the course uses SHA-256 and a 256-bit example.

Given a particular hash output, finding an input that produces it is computationally infeasible.

Finding two distinct inputs with the same output is computationally infeasible. The course distinguishes matching a given document from finding any colliding pair, illustrated by the $1,000 versus $10,000 promises.

The function is deterministic for the same input, yet outputs appear random and uncorrelated even when inputs differ by one byte.

For a 256-bit output, the course approximates Prob{SHA256(X) = Y} as 1/2^256 and Prob{SHA256(X) < T} as T/2^256; proof of work uses this threshold behavior.

Alice owns secret signing key KS; her corresponding public key KP is available to Bob through a public key directory.

Alice feeds the document, in practice Hash(m), and KS into signing algorithm S, producing a signature.

The document and its signature travel together over an insecure network; the secret key does not travel.

Bob gives KP, the document, and signature to V. V returns Yes if valid or No if invalid.

A changed document fails verification; the course names unforgeability, undeniability, universal verifiability, and document-specific signatures. A signature is distinct from encryption.

Bitcoin’s public ledger records transactions. The course describes the ledger as copied by participants, with no names or explicit account-balance records.

Miners validate and collect transactions from roughly the preceding ten minutes; the first transaction is the coinbase. A Merkle root summarizes the ordered list.

The 80-byte header contains version (4 B), previous-header hash (32 B), Merkle root (32 B), time (4 B), target (4 B), and nonce (4 B). A transaction count and ordered transaction list follow the header.

Each new header stores the hash of its predecessor’s header, tracing back toward the genesis block. Mining searches for a header hash under the target.

Changing an old transaction changes its Merkle root and header hash, so subsequent links no longer match without redoing their proof of work.

A Bitcoin transaction spends earlier unspent outputs as inputs and creates new outputs; the public ledger records these transfers rather than explicit balances.

Each input identifies a prior transaction output by TXID and output index n, and supplies unlocking material such as a signature and public key in the course’s P2PKH example.

Each output states a value in satoshis and a scriptPubKey; in the course’s P2PKH example it contains a hash of the receiver’s public key.

The course also lists version, input/output counts, script lengths, sequence, and lock_time. It identifies a TX by TXID = Double_SHA256(Transaction).

The cited lecture checks that inputs are unspent, signatures match, and output value does not exceed input value; the difference is the fee.

Miners gather and validate transactions, mostly from the preceding ten minutes. TX0 is the coinbase, and order affects the resulting root.

Hash every transaction separately, for example H01 = Hash(TX0) and H02 = Hash(TX1).

Pair neighboring hashes and hash each pair; when a level has an odd count, duplicate the final hash for that level.

Repeat the pairing until one Merkle root remains. Changing a transaction or its order changes the root.

Store the 32-byte root in the 80-byte block header with the previous hash and mining fields. Proof of work hashes the header; the next block references that header hash.

A verifier can check one transaction using only the hashes along its Merkle path rather than revealing or rehashing every transaction.

Two unspent outputs belong to Alice: 60 BTC locked to Hash(PK1) and 40 BTC locked to Hash(PK2). Together they supply 100 BTC.

TX200 references each earlier TXID plus output index. For each input, show Alice’s public key and signature made by the matching secret key; the key hashes to the UTXO’s receiving address.

Create outputs of 50 BTC to Hash(Bob PK), 40 BTC to Hash(Cathy PK), and 9.5 BTC change to a fresh Hash(Alice PK3).

Outputs total 99.5 BTC, so 100 − 99.5 = 0.5 BTC is the miner fee; the fee is a difference, not its own output.

TX300 spends Cathy’s 40 BTC output #1 from TX200 with Cathy’s public key and signature, then creates a 40 BTC output to Hash(Dana PK).

TX300 has 40 BTC input and 40 BTC output, hence a zero fee. The course notes say a zero-tip transaction will not be picked up by a miner; distinguish this relay/miner expectation from the value-balance rule that permits equality.

The course shows a short message in an OP_RETURN output, often 0 BTC in its coinbase examples. The sample paper asks for a different data-carrying method.

In the course’s P2PKH output model, scriptPubKey contains a 20-byte receiver public-key hash. The answer infers replacing those bytes with message data, producing a fake receiving address.

Random-looking hash bytes do not reveal whether a matching public key exists; the key/signature condition is tested when the output is later spent. Once mined, the output bytes are committed by the Merkle tree and chain.

In the course answer, split a file into ordered 20-byte chunks across many outputs and transactions, then reconstruct it by reading those fields. Its stated 10,000-byte transaction limit is a course-era simplification.

The course describes paying bitcoin to an output for which no one knows a matching key, making the funds effectively unspendable. This is distinct from a provably unspendable OP_RETURN script.

The sample paper explicitly calls these acts unethical and advises against them. This room is an offline explanation, with no live transaction construction or broadcast.

The bank chooses primes p and q, N = p·q, and exponents e and d satisfying e·d ≡ 1 (mod φ(N)); (e,N) is public and d is secret. Alice is the customer and a shop later verifies.

Alice chooses coin identifier x and invertible randomizer r from Z*_N. The bank will not see x during blind signing.

Alice computes Y = r^e·x mod N, or r^e·H(x) mod N in the course’s hash version, and sends Y to the bank.

The bank signs S_Y = Y^d mod N and, in the $10 example, debits Alice’s account by $10 without seeing the unblinded coin.

Alice computes S_x = S_Y/r mod N, meaning multiplication by the modular inverse of r. Since r^(e·d) ≡ r, this yields x^d mod N (or H(x)^d).

The shop checks S_x^e mod N = x (or H(x)) using (e,N). The bank saw Y at withdrawal and cannot link the unblinded coin presented later to that withdrawal. The course’s $10 denomination uses e = 23 and d8.

This is CS 746-only optional practice for a CS 646 student. ECDSA uses public curve parameters (E,G,p,n) on secp256k1 plus a one-way hash.

Alice chooses private scalar d in the source’s interval [2,n−2] and publishes Q = dG.

Choose k, compute kG = (x1,y1), set r = x1 mod n, then s = (Hash(m)+d·r)/k mod n. Retry if r or s is zero; signature σ = (r,s).

Check r,s are in range; w=s^−1 mod n; u1=Hash(m)·w and u2=r·w; compute u1G+u2Q and accept iff its x coordinate mod n equals r.

Replacing s by n−s negates the verification point’s y coordinate but preserves x. Thus both (r,s) and (r,n−s) verify for the same message.

In the course’s legacy scriptSig example, changing the encoded signature changes the transaction hash/TXID while the payment remains valid. The source names a coordinate-committing remedy and EC-Schnorr; modern SegWit nuance is recorded separately.