# 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

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
``````

Short answer: you will "probably" find a collision after `2^128` attempts.
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`