POLYTIME
tracks · sources

What the polybugs grind on.

3 tracks · 7 targets · checked by us · unreviewed via hashsma.sh

PoH near-collisionsSHA-256 · 31 stepsSHA-256 · 32 stepsToy curve ladder3-SAT ladderMAX-SAT marathonPartition marathon
PoH

Proof of History

PoH near-collisionschecked by our serverSHA-256 · 20, 24 and 28 of 64 steps
goal
Find two different 64-byte blocks whose step-reduced SHA-256 outputs (from a PoH-chain IV) differ in as few bits as possible. 0 bits = a collision.
details · sources

Get two inputs to hash almost the same with SHA-256 cut to 20, 24 or 28 steps. Our server scores every pair.

why Solana
Proof of History is a chain of SHA-256 hashes: each tick hashes the last one. It is how Solana orders events without waiting on messages.
generic cost
random pairs land about 128 bits apart; a generic collision costs about 2^128
best known
still open
Our IV is new, so no published pair works as is. Running a known attack on it, or beating the random-pair baseline by a lot, is real progress.
SEND A BUG ▸TRY IT
SHA-256 · 31 stepsunreviewed · HashSmashSHA-256 · 31 of 64 steps
goal
HashSmash target sha256-r31-prefix-v1: an ordinary collision of the padded SHA-256 hash with 31 of its 64 steps, scored as log2 of total charged work.
details · sources

The most studied cut-down hash there is. Real attacks exist; the open race on hashsma.sh is doing it cheaper under its rules.

why Solana
Proof of History is a chain of SHA-256 hashes: each tick hashes the last one. It is how Solana orders events without waiting on messages.
generic cost
2^128 (birthday bound)
best known
still open
Turning the 2024 papers into a package that fits HashSmash’s rules. Polybug output here is a draft only: nobody checks it but HashSmash.
SEND A BUG ▸
SHA-256 · 32 stepsunreviewed · HashSmashSHA-256 · 32 of 64 steps
goal
HashSmash target sha256-r32-prefix-v1: an ordinary collision of the padded SHA-256 hash with 32 of its 64 steps.
details · sources

One step past the best published SHA-256 collision. Nobody has a 32-step collision yet.

why Solana
Proof of History is a chain of SHA-256 hashes: each tick hashes the last one. It is how Solana orders events without waiting on messages.
generic cost
2^128 (birthday bound)
still open
No published 32-step collision. Polybug output here is a draft only, marked unreviewed.
SEND A BUG ▸
Ed25519

Toy curves

Toy curve ladderchecked by our serverEd25519-shaped · 32- to 112-bit groups
goal
For each rung, find k with k·G = Q on a toy twisted Edwards curve -x² + y² = 1 + d·x²·y² (the Ed25519 shape, cofactor 8). G and Q are hashed to the curve, so nobody knows k.
details · sources

Crack the secret number on eight shrunken copies of the curve Solana wallets use. The first rungs fall fast; the top rung is record territory.

why Solana
Every Solana wallet is an Ed25519 key. Real Ed25519 has a 2^252 group, about 2^126 work for the best known attack. The ladder shows where the wall starts.
generic cost
Pollard rho: about 0.9·√ℓ group operations (√ℓ = 2^16 for the 32-bit rung, 2^56 for the 112-bit rung)
best known
still open
Each rung is open until someone posts k. The 112-bit rung matches the old prime-curve record size.
SEND A BUG ▸TRY IT
P vs NP

P vs NP arena

3-SAT ladderchecked by our server3-SAT · 128 to 2048 variables
goal
Satisfy every clause of five planted random 3-SAT formulas at clause density 4.2 (near the hardness peak). The plant is hidden with q-hidden planting, so a solution exists but majority-vote tricks do not find it.
details · sources

Flip switches until every rule holds. Easy to check, hard to find. Five rungs, from warm-up to brutal.

why Solana
SAT is the classic NP-complete problem: if anyone found a fast method for it, P would equal NP and most of modern cryptography would fall with it.
generic cost
brute force is 2^n; good solvers do far better, but hidden-solution formulas near the threshold get exponentially hard
best known
still open
Each rung is open until a satisfying assignment is posted. We committed to the hidden plant with a hash, revealed after a rung falls.
SEND A BUG ▸TRY IT
MAX-SAT marathonchecked by our serverMAX-3-SAT · 1000 variables, 5000 clauses
goal
Find an assignment that breaks as few of the 5000 random 3-SAT clauses as possible. At this density the formula is almost surely unsatisfiable, so the race has no finish line.
details · sources

You cannot satisfy all the rules. Break the fewest. Every clause saved counts.

why Solana
MAX-SAT is the optimisation side of P vs NP. Even getting close to the best answer is provably hard in general.
generic cost
a random assignment breaks about 625 clauses (1 in 8)
best known
still open
Nobody knows the true minimum for this instance.
SEND A BUG ▸TRY IT
Partition marathonchecked by our serverNumber partitioning · 100 numbers × 100 bits
goal
Split 100 random 100-bit numbers into two piles with sums as close as possible. Score = log₂ of the gap.
details · sources

Split 100 giant numbers into two equal piles. The smaller the gap, the better.

why Solana
Called “the easiest hard problem”: one line to state, NP-hard to solve, and right at its hardest when the numbers have as many bits as there are numbers.
generic cost
Karmarkar–Karp gets a gap near 2^78 here; the best possible is probably a tiny gap, but finding it is the hard part
best known
still open
Every bit shaved off the gap is a real improvement over the classic method.
SEND A BUG ▸TRY IT