Chapter 2 — Discrete mathematics

Lesson map

Lesson 02 published. Map, example, EX004.

flowchart TD
  N0["Learning outcomes"]
  N1["2.1 Sets and functions"]
  N2["2.2 Hash functions"]
  N3["Lab — Hash chain check"]
  N4["2.3 Reading the check"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX004"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["2.1 Sets and functions"]
  N2["2.2 Hash functions"]
  N3["Lab — Hash chain check"]
  N4["2.3 Reading the check"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX004"]

[Learning outcomes]
    |
    v
[2.1 Sets and functions]
    |
    v
[2.2 Hash functions]
    |
    v
[Lab — Hash chain check]
    |
    v
[2.3 Reading the check]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX004]

Learning outcomes

You will (1) use sets, functions and logic for ledger reasoning; (2) explain hash functions; (3) verify a hash chain.

2.1 Sets and functions

A ledger can be described with discrete mathematics. Accounts form a set; balances are a function from accounts to non-negative integers; a transaction is a function from one balance state to the next. Jonas writes the transfer rule in logic: a transfer of amount a from x to y is valid only if balance(x) is at least a, and afterwards balance(x) decreases by a while balance(y) increases by a. Writing rules precisely like this exposes edge cases, such as a transfer to oneself or of zero, that informal descriptions often miss.

2.2 Hash functions

A cryptographic hash function maps any input to a fixed-size output in a way that is easy to compute but practically impossible to reverse or to find two inputs with the same output. Nakamoto's Bitcoin paper chains blocks by including each block's hash in the next, so changing any earlier record changes every later hash. Jonas learns that this gives tamper evidence rather than tamper prevention: anyone can rewrite a copy of the data, but the change becomes visible to anyone who checks the chain against a trusted head value.

Lab — Hash chain check

"""Hash-chain integrity check on a synthetic ledger of energy-credit records (read-only)."""
import hashlib

RECORDS = ["mint 100 to coop", "transfer 20 coop->h01", "transfer 15 coop->h02",
           "transfer 5 h01->h03", "burn 10 from h02"]

def build(records):
    prev, chain = "0" * 64, []
    for r in records:
        h = hashlib.sha256((prev + r).encode()).hexdigest()
        chain.append((r, prev, h)); prev = h
    return chain

def verify(chain):
    prev = "0" * 64
    for i, (r, p, h) in enumerate(chain):
        if p != prev or hashlib.sha256((p + r).encode()).hexdigest() != h:
            return i
        prev = h
    return None

def main():
    chain = build(RECORDS)
    print("blocks", len(chain), "head", chain[-1][2][:12])
    print("intact chain: first bad index =", verify(chain))
    edited = list(chain); r, p, h = edited[2]
    edited[2] = ("transfer 50 coop->h02", p, h)
    print("edited record 2: first bad index =", verify(edited))

if __name__ == "__main__":
    main()

Run with python3 lab_chain.py. Verified output:

blocks 5 head 73420780eb14
intact chain: first bad index = None
edited record 2: first bad index = 2

2.3 Reading the check

Jonas's standard-library script builds a five-record synthetic chain with SHA-256 and verifies it. The intact chain reports no bad index. When the script edits the amount in record 2 without recomputing hashes, verification reports the first bad index as 2. If an editor recomputed every later hash, the chain would verify internally, but its head would no longer match the head value held by other parties. Jonas notes that integrity therefore depends on distributing and comparing head values, which is the role consensus plays in a real network.

Worked example

The lab builds a five-block SHA-256 chain, verifies it intact and detects an edited record at index 2.

Synthetic case. Records and the script are synthetic; Nakamoto (2008) is a real source.

Errors and limits

Believing a hash chain prevents tampering, rather than revealing it to those who compare heads, overstates its protection.

Exercises

• EX004 — Transfer precondition. What must hold for a transfer of a from x?
  Show marking criteria

  Rubric: 3 = balance(x) at least a;; 2 = enough balance;; 1 = vague;; 0 = none.
• EX005 — Tamper evidence. Does a hash chain prevent or reveal tampering?
  Show marking criteria

  Rubric: 3 = reveals it to those who compare;; 2 = reveals;; 1 = prevents;; 0 = none.
• EX006 — Bad index. Which index did the lab flag after editing?
  Show marking criteria

  Rubric: 3 = 2;; 2 = index 2;; 1 = vague;; 0 = none.

Synthesis

Precise logical rules and hash chains provide the mathematical basis of ledger integrity.

Continue studying — chapter 02 of 50

← Chapter 01 (draft) · Course chapter index · Chapter 03 (draft) →