Introduction

We often want a succinct representation of some data
with the expectation that we are referring to the same data.

A "fingerprint"

Hash Function Properties

• Accept unbounded size input
• Map to a bounded output
• Be fast to compute
• Be computable strictly one-way
  (difficult to find a pre-image for a hash)
• Resist pre-image attacks
  (attacker controls one input)
• Second pre-image resistance: Given an input and output
  (resisting second pre-image attacks).
• Resist collisions
  (attacker controls both inputs)

Hash Function API

A hash function should:

• Accept an unbounded input size ([u8] byte array)
• Return a fixed-length output (here, a 32 byte array).

fn hash(s: &[u8]) -> [u8; 32];

Example

Short input (5 bytes):

hash('hello') =
 0x1c8aff950685c2ed4bc3174f3472287b56d9517b9c948127319a09a7a36deac8

Large input (1.2 MB):

hash(Harry_Potter_series_as_string) u
 0xc4d194054f03dc7155ccb080f1e6d8519d9d6a83e916960de973c93231aca8f4

Input Sensitivity

Changing even 1 bit of a hash function completely scrambles the output.

hash('hello') =
 0x1c8aff950685c2ed4bc3174f3472287b56d9517b9c948127319a09a7a36deac8

hash('hellp') =
 0x7bc9c272894216442e0ad9df694c50b6a0e12f6f4b3d9267904239c63a7a0807

Speed

• Some hash functions are designed to be slow.
• Does anyone know why someone would want a hash function to be slow?
• These have applications like password hashing, which would slow down brute-force attackers.
• For our purposes, we generally want them to be fast.

Famous Hash Algorithms

Hash Functions in Blockchains

Hashing Benchmarks

XXHash - Fast hashing algorithm

Non-Cryptographic Hash Functions

Non-cryptographic hash functions provide weaker
guarantees in exchange for performance.

They are OK to use when you know that the input is not malicious.

If in doubt, use a cryptographic hash function.

One Way

Given a hash, it should be difficult to find an input value (pre-image)
that would produce the given hash.

That is, given H(x), it should be difficult to find x.

Second Pre-Image Attacks

Given a hash and a pre-image, it should be difficult to find another
pre-image that would produce the same hash.

Given H(x), it should be difficult to find any x'

such that H(x) == H(x').

Collision Resistance

It should be difficult for someone to find two messages that
hash to the same value.

It should be difficult to find an x and y

such that H(x) == H(y).

Collision Resistance

Difference from second pre-image attack:

In a second pre-image attack, the attacker only controls one input.

In a collision, the attacker controls both inputs.

They may attempt to trick someone into signing one message.

Birthday Problem

With 23 people, there is a 6% chance that someone will be born on a specific date, but a 50% chance that two share a birthday.

• Must compare each birthday with every other, not with a single one.
  
• Number of possible "hits" increases exponentially for more attempts, reducing the expected success to the square-root of what a specific target would be.

Birthday Attack

Thus, with a birthday attack, it is possible to find a collision of a hash function in $\sqrt {2^{n}}=2^{^{\frac{n}{2}}}$, with $\cdot 2^{^{\frac{n}{2}}}$ being the classical preimage resistance security.

So, hash function security is only half of the bit space.

Partial Resistance

It should be difficult for someone to partially (for a substring of the hash output) find a collision or "second" pre-image.

• Bitcoin PoW is a partial pre-image attack.
• Can anyone explain how?
• Prefix/suffix pre-image attack resistance reduces opportunity for UI attacks for address spoofing.
• Prefix collision resistance important to rationalize costs for some cryptographic data structures.

Hash Function Selection

Content-Derived Indexing

Hash functions can be used to generate deterministic
and unique lookup keys for databases.

Data Integrity Checks

Members of a peer-to-peer network may host and share
file chunks rather than large files.

In Bittorrent, each file chunk is hash identified so peers can
request and verify the chunk is a member of the larger,
content addressed file.

Account Abstractions

Public keys can be used to authorize actions by signing of instructions.

The properties of hash functions allow other kinds of representations.

Public Key Representation

Because hashes serve as unique representations of other data,
that other data could include public keys.
A system can map a plurality of key sizes to a fixed length
(e.g. for use as a database key).

For example, the ECDSA public key is 33 bytes:

Public key (hex):
  0x02d82cdc83a966aaabf660c4496021918466e61455d2bc403c34bde8148b227d7a

Hash of pub key:
  0x8fea32b38ed87b4739378aa48f73ea5d0333b973ee72c5cb7578b143f82cf7e9
                                                                    ^^

Commitment Schemes

It is often useful to commit to some information
without storing or revealing it:

• A prediction market would want to reveal predictions only after the confirming/refuting event occurred.
• Users of a system may want to discuss proposals without storing the proposal on the system.
• However, participants should not be able to modify their predictions or proposals.

Commit-Reveal

Reveal

Message with some added randomness:

Data Identifiers

Sometimes people want to store information in one place and reference it in another. For reference, they need some "fingerprint" or digest.

As an example, they may vote on executing some privileged instructions within the system.

The hash of the information can succinctly represent the information and commit its creator to not altering it.

Data Structures (in Brief)

This is the focus of a later lesson.

Pointer-Based Linked Lists

Pointer-based linked lists are a foundation of programming.

But pointers are independent from the data they reference,
so the data can be modified while maintaining the list.

That is, pointer-based linked lists are not tamper evident.

Hash-Based Linked Lists

Hash-based lists make the reference related to the data they are referencing.
The properties of hash functions make them a good choice for this application.

Any change at any point in the list would create downstream changes to all hashes.

Merkle Trees

Proofs

Merkle trees allow many proofs relevant to the rest of this course,
e.g. that some data object is a member of the tree
without passing the entire tree.

More info in the next lesson.

Hash Examples in Substrate

Sr25519 Signatures

Sr25519 hashes the message as part of its signing process.

Transactions

In transactions in Substrate, key holders sign a
hash of the instructions when the instructions
are longer than 256 bytes.

Database Keys

TwoX64 is safe to use when users (read: attackers)
cannot control the input, e.g. when a
database key is a system-assigned index.

Blake2 should be used for everything else.

Again, there is a whole lesson on hash-based data structures.

Other Uses of Hashes in Substrate

Hashes are also used for: