Pigeonhole Principle to Hash Collisions TODO
Concept
The pigeonhole principle states that if you put more than n items into n boxes, at least one box gets two or more. Generalized, putting m items into n boxes means some box gets at least ⌈m/n⌉. Since a hash function maps an effectively infinite domain to a fixed-length output, this principle proves that collisions must exist — there's no avoiding them. What a cryptographic hash actually aims for isn't the absence of collisions but that finding one is computationally hard. Layer the birthday problem on top of this, and for a b-bit output, a random collision is expected within roughly 2^(b/2) attempts, so collision resistance is effectively about half the output length.
Mistaking output bit-length for security strength — say, by truncating a hash or using a short identifier — quietly halves your strength against collision attacks (as opposed to preimage attacks). You need to know which resistance property actually matters for the job to pick a safe length.
Code & Formula
# 비둘기집 원리 → 해시 충돌 — 상자(버킷)보다 물건(입력)이 많으면 충돌은 "반드시" 생긴다.
# 8비트로 자른 해시(256개 버킷)에 무작위 입력을 계속 넣어 첫 충돌이 나오는 시점을 관찰.
import hashlib
def short_hash(data: bytes, bits: int) -> int:
full = hashlib.sha256(data).digest()
value = int.from_bytes(full, "big")
return value % (2 ** bits) # bits비트로 잘라 버킷 인덱스로 사용
def find_first_collision(bits: int, seed: int = 0):
buckets = {}
i = seed
while True:
item = f"item-{i}".encode()
idx = short_hash(item, bits)
if idx in buckets:
return i - seed + 1, buckets[idx], item # 시도 횟수, 먼저 있던 입력, 충돌 입력
buckets[idx] = item
i += 1
BITS = 8 # 256개 버킷뿐이라 비둘기집 원리상 257번째 입력까지 가면 충돌이 강제됨
n_buckets = 2 ** BITS
tries, first, second = find_first_collision(BITS)
print(f"버킷 수 = 2^{BITS} = {n_buckets}")
print(f"첫 충돌까지 시도 횟수: {tries} (비둘기집 원리상 최대 {n_buckets + 1}회 이내 보장)")
print(f" 충돌한 두 입력: {first!r} , {second!r}")
# 생일 문제 근사: 무작위 충돌은 대략 2^(bits/2) 시도에서 기대된다.
expected = int(2 ** (BITS / 2))
print(f"생일 문제 근사 기대 시도 수 ≈ 2^({BITS}/2) = {expected}")
Exercise
Truncate keccak256 output to 32, 48, and 64 bits, measure how many random-input attempts it takes to hit the first collision at each length, and compare against the 2^(b/2) prediction.
Practical Connection
Verex's Conditional Tokens derive conditionId, collectionId, and positionId all as hashes, so truncating these identifiers for use as indexing keys creates a real collision risk, and the same math applies to Merkle-tree-based proofs.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.