# Will a recursive sha256 run over all 2^256 inputs before a collision?

Will a recursive sha256 run over all 2^256 inputs before a collision?

Here'a a python program showing my question - will this loop for 2^256 times - given endless memory or will it terminate before - if so when?

``````import hashlib

# start with 0
input = (0).to_bytes(32, byteorder="little", signed=False)

# dictionary to detect hash collisions - yes, this will eat up ALL memory
hit = {}

print ("first input:" + input.hex())

while (1):
hash = hashlib.sha256(input).digest()

# do we have a collision?
assert (hash not in hit), "Collision!"

# store current hash
hit[hash]=1

print ("Hash: " + hash.hex())

# try again with the hash output as input
input=hash
``````

## 1 Answer

Short answer: you will "probably" find a collision after `2^128` attempts.

The concept you are looking for is called the birthday problem, explained also very well in this video by Professor Christoph Parr.

One of the approximations from The Birthday Problem is that given a random output space of size `n`, the probability of an input collision approaches 50% after approximately `√n` attempts. `(2^256)^1/2 = 2^128`