Cryptography You Need

Why Cryptography Appears In A Ledger

In week 1 we saw that a shared ledger needs three things. Records must be hard to alter after the fact. Only the owner of some value should be able to spend it. And many computers must be able to check all of this on their own. Cryptography, the mathematics of secure information, supplies tools for each need.

You do not need to understand the deep mathematics to use these tools well. You need a clear picture of what each tool promises and how to call it from code. This week we cover four tools: hash functions, key pairs, digital signatures and Merkle trees. We use Python 3 for every demo.

Three Needs, Four Tools

Need	Tool	What it gives you
Detect any change	Hash function	A short fingerprint of any data
Prove who authorised	Digital signature	Proof made with a private key
Summarise many items	Merkle tree	One root for a whole list
Identify an owner	Public key	An address anyone can check

Each tool answers one question a shared ledger must answer. Source: Course summary of standard cryptographic roles

Hash Functions: Digital Fingerprints

A hash function takes any input, a word, a file or an entire book, and returns a fixed-size output called a hash or digest. SHA-256, the function used by Bitcoin, always returns 256 bits, usually written as 64 hexadecimal characters.

Good cryptographic hash functions have several properties. The same input always gives the same output. Computing the hash is fast. A tiny change in the input changes the output completely, which is called the avalanche effect. Given a hash, finding an input that produces it is practically impossible, a property called preimage resistance. Finding two different inputs with the same hash, a collision, is also practically impossible.

These properties make a hash work like a fingerprint. If you and I hold the same file, we can compare 64 characters instead of the whole file. If even one byte differs, the fingerprints differ.

• Deterministic: same input, same output.
• Fast to compute in one direction.
• Avalanche effect: one changed character changes the whole digest.
• Preimage resistant: you cannot work backwards from a hash to the input.
• Collision resistant: finding two inputs with one hash is infeasible.

Hash Demo In Python

Python ships with a module called hashlib. The code below hashes two nearly identical sentences. Run it and compare the output. Not a single visible pattern connects the two digests, even though the inputs differ by one character.

Notice the b before each string. It means the text is bytes, because hash functions work on bytes rather than on text characters. If you have a normal string, call .encode() on it to get bytes.

Hashes also chain blocks together. A block header includes the hash of the previous block. Change anything in an old block and its hash changes, so the next block's stored reference no longer matches. Every later block shows a mismatch, and anyone checking the chain sees it at once.

• import hashlib
• print(hashlib.sha256(b'Alice pays Bob 5').hexdigest())
• print(hashlib.sha256(b'Alice pays Bob 6').hexdigest())

Public And Private Keys

Public-key cryptography uses a pair of keys that are linked mathematically. The private key is a secret number you never share. The public key is derived from the private key and can be shared with everyone. Going from private to public is easy. Going from public back to private is computationally infeasible.

The pair behaves like a mailbox with a public slot. Anyone who knows the address can drop things in or check things, but only the key holder has authority to act. In a blockchain, your public key (or a short value computed from it, called an address) works like your account number. Your private key is the authority to spend.

Bitcoin and Ethereum use elliptic curve cryptography, specifically a curve named secp256k1. The mathematics is advanced, and standard libraries hide it. What matters for you is the practical rule: anyone who obtains your private key controls your funds, and no support desk can reverse that. Guard it carefully and back it up offline.

Digital Signatures

A digital signature proves two things at once: the message came from the holder of a private key, and the message has not changed since it was signed. To sign, you combine the message with your private key to produce a signature. To verify, anyone combines the message, the signature and your public key. The check passes or fails.

Signing is the answer to the question from week 1: how can strangers know that a payment is authorised? A transaction that moves your coins must carry a signature made with the key that controls them. Every node can verify it with the public key, so no phone call to a bank is required.

A signature depends on the message. If an attacker changes the amount from 5 to 500, the old signature no longer verifies. The signature cannot be copied onto a different message either. This is why a signed transaction can travel through many untrusted computers safely.

Sign And Verify

1. Hash the message
2. Sign the hash with the private key
3. Send message and signature
4. Verify with the public key
5. Accept or reject

Only the private key holder can sign, but anyone can verify.

Signature Demo In Python

The demo below uses the popular cryptography package (install it with pip install cryptography). It uses the Ed25519 signature scheme, which is modern and simple to call. Bitcoin and Ethereum use ECDSA on secp256k1 instead, but the pattern of generate, sign and verify is identical.

Read the output carefully. The first verification passes silently because verify returns nothing on success. The second verification raises an InvalidSignature exception because the message was altered after signing.

• from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
• private_key = Ed25519PrivateKey.generate()
• signature = private_key.sign(b'Alice pays Bob 5')
• private_key.public_key().verify(signature, b'Alice pays Bob 5')

Merkle Trees: Summarising Many Items

A block may hold thousands of transactions. We want one short fingerprint that commits to all of them, and we want to prove that one transaction sits inside the block without sending the whole block. A Merkle tree, named after Ralph Merkle, does both.

Build it in layers. Hash each transaction to create the leaves. Pair up the leaves, join each pair together and hash the result to make the next layer. Repeat until one hash remains. That final hash is the Merkle root. When a layer has an odd number of items, a common approach is to duplicate the last one.

The root changes if any transaction changes, so placing the root in the block header commits the header to every transaction. A Merkle proof is the short list of sibling hashes along the path from one leaf up to the root. A light client holding only block headers can check a proof with a handful of hashes, even for a block with thousands of transactions.

Building A Merkle Root

1. Hash each transaction
2. Pair hashes and hash again
3. Repeat up the tree
4. One root hash remains
5. Store the root in the block header

Changing any transaction changes the root.

Putting The Pieces Together

A simplified block looks like this. It has a header containing the hash of the previous block, the Merkle root of its transactions, a timestamp and a counter. It has a body listing the transactions, and each transaction carries a signature from the spender.

Each tool carries a distinct duty. Signatures prove authority to spend. Merkle trees compress many transactions into one commitment. Hashes link blocks into a chain and make history tamper-evident. In week 3 we add a fourth ingredient, proof of work, and see how Bitcoin assembles all of them. Keep the demos from this week: you will reuse the hashing code immediately.

A useful habit is to ask three questions of any blockchain claim. Who approved this action, and how do I check it? Could anyone have changed this record afterward, and how would I notice? Is this item really part of that block, and what is the short proof? The answers always come back to signatures, hashes and Merkle proofs. If you can answer those three questions, you understand the security story of a blockchain at the level needed for the rest of the course.

Key Terms

Hash function

A function that maps any input to a fixed-size output and cannot practically be reversed.

SHA-256

A widely used hash function that outputs 256 bits, shown as 64 hexadecimal characters.

Avalanche effect

A tiny change in the input changes the hash output completely.

Private key

A secret number that gives control over funds and creates signatures.

Public key

A number derived from the private key that anyone can use to verify signatures.

Address

A short identifier derived from a public key, used to receive funds.

Digital signature

Data that proves a message was approved by the holder of a private key and has not been altered.

Merkle tree

A tree of hashes that summarises many items into one root hash.

Merkle root

The single hash at the top of a Merkle tree that commits to every leaf.

Exercise: Hash, Sign And Build A Merkle Root

1. Create a file crypto_demo.py and hash two sentences that differ by one character using hashlib.sha256. Compare the digests.
2. Run pip install cryptography, then generate an Ed25519 key pair, sign the message 'Alice pays Bob 5' and verify it.
3. Verify the same signature against 'Alice pays Bob 500' inside try and except InvalidSignature, and print a message when it fails.
4. Write a function merkle_root(leaves) that hashes each leaf, then repeatedly pairs and hashes neighbours, duplicating the last hash when a layer is odd.
5. Call merkle_root on four transactions, change one character in one transaction and confirm the root changes.
6. Write two sentences on which of the three tools prevents a stranger from spending your coins, and why.

Further Reading

• Bitcoin and Cryptocurrency Technologies, Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Steven Goldfeder, Princeton University Press, chapters 1 and 2
• Serious Cryptography, Jean-Philippe Aumasson, No Starch Press, 2017 (chapters on hash functions and public-key cryptography)
• New Directions in Cryptography, Whitfield Diffie and Martin Hellman, IEEE Transactions on Information Theory, 1976
• Python hashlib documentation, Python Software Foundation, docs.python.org