Cryptographic Hash Function

A cryptographic hash function is a mathematical algorithm that takes an input of any size, such as a password, a document or a block of transactions, and produces a fixed-length output called a hash or digest. The same input always gives the same hash, but even a tiny change to the input produces a completely different result, and it is computationally infeasible to work backwards from the hash to the input or to find two inputs with the same hash. These properties make hash functions a basic building block of computer security and of blockchains. It is often shortened to hash function.

Widely used hash functions include SHA-256, part of the SHA-2 family published by the US National Institute of Standards and Technology (NIST); SHA-3 and the closely related Keccak-256 used by Ethereum; RIPEMD-160; and the BLAKE family. Unlike encryption, which scrambles data so it can be recovered with a key, hashing is one-way: there is no key, and the original data cannot be recovered from the hash. Hash functions are part of the broader field described under cryptography.

A hash is like a fingerprint for data. Every person has a unique fingerprint, and you can quickly check whether a fingerprint matches someone, but you cannot rebuild the whole person from it. In the same way, any file or message can be turned into a short code that is, for practical purposes, unique to it.

If someone changes even one comma in a contract, its fingerprint changes completely, so you can tell at once that it has been altered. Blockchains use this trick everywhere: each block carries the fingerprint of the one before it, so changing any old record would change every fingerprint after it, and everyone would notice.

A hash function can be described as a mapping from inputs of any length to outputs of a fixed length of $n$ bits:

Here $\{0,1\}^{*}$ means any string of bits and $n$ is the output length, 256 for SHA-256. A secure cryptographic hash function should have these properties:

• Pre-image resistance. Given a hash, it is infeasible to find any input that produces it.
• Second pre-image resistance. Given one input, it is infeasible to find a different input with the same hash.
• Collision resistance. It is infeasible to find any two different inputs with the same hash.
• Avalanche effect. Changing one bit of input changes about half the bits of the output, unpredictably.

Because of a statistical effect known as the birthday paradox, finding a collision by brute force takes about $2^{n/2}$ attempts rather than $2^{n}$. For SHA-256, that is about $2^{128}$ attempts, a number far beyond the capacity of all the computers in the world.

Hash functions appear at almost every level of a blockchain. Each block header contains the hash of the previous block, linking the chain. Transactions are combined into a Merkle tree whose root hash summarises them all. In Bitcoin's proof of work, miners repeatedly hash block headers, changing a nonce, until they find a hash below a target, which is how the hashrate of the network is measured. Bitcoin uses SHA-256 twice for this, and combines SHA-256 with RIPEMD-160 to derive many addresses from public keys. Ethereum uses Keccak-256 for addresses, transaction identifiers and storage.

Outside blockchains, hash functions are used to store passwords, usually combined with a random salt and deliberately slow algorithms to resist guessing; to create digital signatures, which sign the hash of a document rather than the whole document; to check that downloaded software has not been altered; and to detect duplicate files. Payment systems use hashing in tokenization and message authentication, and the integrity of many financial messages relies on it.

Hash functions can be weakened by advances in mathematics or computing. MD5, once widely used, was shown to be vulnerable to collisions in 2004, and researchers produced a practical SHA-1 collision in 2017, after which both were retired from security-sensitive uses. NIST ran a public competition that selected Keccak as the basis for SHA-3 in 2012, providing an alternative design to SHA-2. Large quantum computers, if built, could speed up some attacks on hash functions, but the effect is expected to be modest compared with their impact on public-key cryptography, so longer outputs are considered an adequate defence. The general immutability that hashing gives to ledgers is described under cryptographic immutability.