Hash function

Hash functions are the core building blocks that provide the basis of bitcoin and other cryptocurrency generation. Each new block in the blockchain begins with a hash of the previous block.

Overview

In mathematics, a function is a process whereby one or more inputs are transformed into an output. A hash function takes an input of indeterminate length and mathematically transforms it into an output of fixed, pre-determined, usually shorter length. The function "hashes" the input. The output of a hash function, commonly referred to as the hash or the digest, is determined by the hashing such that the same input always produces the same hash.[1] The output of a hash function is usually shorter than the input, and one of the benefits of hashing data is often data compression.[2]

The following characteristics make certain hash functions desirable for cryptographic applications:[3]

• Deterministic - For any input, the hash function produces the same digest, or output, every time the hash function is run on the input.
• Pre-image resistant - For any digest it should be computationally infeasible (meaning it would take far too many resources to actually compute) to determine its input. This is called one-wayedness, meaning that it is almost impossible to determine the input string from any given digest.[4]
• Collision resistant - For any digest it should be computationally infeasible to find a distinct other input that when hashed produces the same digest. When two or more distinct input strings produce the same digest when hashed, they are said to collide.

Other, less cryptographically friendly attributes of hash functions might include compression - taking very large inputs or input strings to be indexed into shorter, fixed-length digests to be used as an index - and familiarity so that similar inputs have similar but different outputs so that hashing is faster, though not safer.[5]

Cryptographic Hash Functions

While there are numerous hash functions in common use, the ones used most frequently in encryption are MD5 (Message Digest 5) and SHA256 (Secure Hash Algorithm 256).[6] Satoshi Nakamoto's "bitcoin whitepaper" refers to SHA-256 as usable for the proof-of-work in a bitcoin blockchain.[7]

As mentioned, hash functions produce output of a fixed length. Here are two examples of the use of MD5 hashing:

• md5("hello world") = 5EB63BBBE01EEED093CB22BB8F5ACDC3 and
• md5(42) = A1D0C6E83F027327D8461063F4AC58A6.[8]

These examples illustrate a few important characteristics of a hash function. For one, the input strings are of different lengths, one is for a quotation and the other is a number. Secondly, the digests are different but of identical 32-bit length. Thirdly, the digest uses hexadecimal digits (which are 0 to 9 and a to f). While common, not all cryptographic functions use 32-bit, hexadecimal output and bitcoin transaction hash digests are 64 characters.[9] SHA256 is used for the bitcoin blockshain. Here is how the same inputs as above are hashed using SHA256:

• sha256("hello world") = 9DDEFE4435B21D901439E546D54A14A175A3493B9FD8FBF38D9EA6D3CBF70826 and
• sha256(42) = 73475CB40A568E8DA8A045CED110137E159F890AC4DA883B6B17DC651B3A8049.[10]

Again, the inputs are of different lengths but both result in 64 bit, hexadecimal digests.

Hash Functions in Blockchains

Blockchains are series of blocks of transactions. For purposes of data compression as well as privacy and security, transaction information is hashed before it is included in a block. Each block includes a hash of the last block which leads to the creation of the chain. Because cryptographic hash functions are deterministic and highly collision resistant, including a hash of the last previous block effectively prevents anyone tampering with its contents once the next block has been formed.[11]

References

1. What Are Hash Functions. Learn Cryptography.
2. Chapter 6, Hash Functions. Computer Science Education at UCSD.
3. Cryptographic Hash Functions. Purdue University.
4. Chapter 6, Hash Functions. Computer Science Education at UCSD.
5. Cryptographic Hash Functions. Purdue University.
6. What is Cryptographic Hashing?. Tip Top Security.
7. Bitcoin: A Peer-to-Peer Electronic Cash System. Bitcoin.org.