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.
Where it lands in Jayverse
- Verex: test that no derived key is truncated below a safe length. Add a test that checks, for every place conditionId, collectionId or positionId is shortened for indexing, the resulting collision probability against 2^(b/2), not just against 2^b.
- Devnet indexer: document the bit length and justification for any shortened key. If the indexer builds short internal keys from these hashes for storage efficiency, keep the chosen length and its collision-resistance reasoning in one place instead of scattered across code.
- Auditor: confirm truncated hashes shown in UI are cosmetic-only. Review any place an identifier is shortened for display or logging (Etherscan-style) to confirm it is never reused as an actual lookup key, since that quiet reuse is the failure mode this card warns about.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| pigeonhole principle | 비둘기집 원리(넣을 게 많으면 겹치는 게 생긴다는 원리) · 해시 충돌이 필연적임을 증명할 때 · "The pigeonhole principle states that if you put" |
| computationally hard | 계산적으로 풀기 어려운 · 충돌 자체가 없는 게 아니라 찾기 어려운 것이 목표일 때 · "finding one is computationally hard" |
| birthday problem | 생일 문제(적은 시도로도 충돌이 생기는 확률 현상) · 충돌까지 걸리는 시도 횟수를 추정할 때 · "Layer the birthday problem on top of this" |
| collision resistance | 충돌 저항성(같은 해시값을 만드는 입력을 찾기 어려운 정도) · 해시 안전성을 논할 때 · "collision resistance is effectively about half the output length" |
| preimage attacks | 프리이미지 공격(해시값으로부터 원본 입력을 역산) · 충돌 공격과 구분되는 다른 공격 유형 · "as opposed to preimage attacks" |
| truncating a hash | 해시를 잘라내다·절단하다 · 해시 출력을 짧게 줄여 쓸 때 생기는 위험 · "by truncating a hash or using a short identifier" |
| quietly halves | 눈에 띄지 않게 절반으로 줄이다 · 출력 길이를 줄였을 때 안전성이 은근히 반토막 나는 것 · "quietly halves your strength against collision attacks" |
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/.