Hash Functions: The Basics

Almost everything in a blockchain is built on hash functions, so it's worth being precise about what they do and don't guarantee.

What a hash function is

A hash function H takes input of any length and returns a fixed-size output:

H : \{0,1\}^* \to \{0,1\}^{256} \quad \text{(for SHA-256)}

The output is called a digest. The same input always gives the same digest, and the digest is cheap to compute. A small change to the input changes the digest completely, which is called the avalanche effect:

SHA-256("hello")  = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA-256("hellp")  = a completely unrelated 256-bit value

The three properties that matter

For a cryptographic hash function, three things should be infeasible:

Preimage resistance. Given a digest y, find any x with H(x) = y. Brute force costs about 2^256 evaluations for a 256-bit hash.
Second-preimage resistance. Given x, find a different x' with H(x') = H(x). Also about 2^256.
Collision resistance. Find any pair x ≠ x' with H(x) = H(x'). The birthday bound makes this cheaper, about 2^128 for a 256-bit hash, which is still far out of reach.

When a collision is found faster than the birthday bound, the function is considered broken. SHA-1 reached that point in practice in 2017, which is why it's no longer used for signatures.

What blockchains use them for

Linking blocks. Each block header contains the hash of the previous header. Changing an old block changes its hash, which breaks the link in every block after it.
Proof of work. Miners search for a header whose hash is below a target. Since hashes can't be inverted, the only way is to try many inputs.
Merkle trees. Transactions are hashed in pairs, then the hashes are hashed in pairs, up to a single root:

\text{root} = H\bigl(H(H(tx_1) \parallel H(tx_2)) \parallel H(H(tx_3) \parallel H(tx_4))\bigr)

The root sits in the block header. To prove one transaction is in a block, you only need the sibling hashes along the path, about log2(n) values, instead of every transaction.

Addresses and identifiers. Addresses are derived by hashing public keys, and a transaction's ID is the hash of its contents.
Signatures. Signature schemes sign the digest of a message, not the message itself, so the message can be any length.

Which hash, on which chain

Bitcoin uses SHA-256, and often applies it twice (SHA-256(SHA-256(x))) for block and transaction hashes.
Ethereum uses Keccak-256. This is the original Keccak submission, which differs from the final NIST SHA3-256 standard because of a padding change. The two give different outputs for the same input, which trips up people who reach for a generic "SHA3" library.
Ed25519, used by Solana and Stellar, uses SHA-512 internally.

A hash is not encryption

A hash has no key and can't be reversed, so there is nothing to decrypt. It also isn't a good way to store passwords by itself, since fast hashes make guessing cheap. Password storage uses deliberately slow, salted functions such as Argon2 or scrypt.

Takeaways

A digest is a short, fixed-size fingerprint, and two different inputs should never share one.
Blockchains use that fingerprint to make tampering detectable: change anything and every digest above it changes too.
Always check which exact hash a protocol names. "SHA3" and "Keccak-256" are not interchangeable.

Next: Private Keys, Public Keys, and Signatures.