Skip to content

Instantly share code, notes, and snippets.

@DavidBuchanan314
Last active October 2, 2021 13:57
Show Gist options
  • Save DavidBuchanan314/13020be9e2a251e2a2a5cd357049a756 to your computer and use it in GitHub Desktop.
Save DavidBuchanan314/13020be9e2a251e2a2a5cd357049a756 to your computer and use it in GitHub Desktop.
# This code is very hacky, please excuse the nonsensical variable/function naming
# See https://twitter.com/David3141593/status/1442883432925773829 for context
# Derived from this implementation of XXHASH64: https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h
from xxhash import xxh64
XXH_PRIME64_1 = 0x9E3779B185EBCA87
XXH_PRIME64_2 = 0xC2B2AE3D27D4EB4F
XXH_PRIME64_3 = 0x165667B19E3779F9
XXH_PRIME64_4 = 0x85EBCA77C2B2AE63
XXH_PRIME64_5 = 0x27D4EB2F165667C5
# the multiplicative inverses of the above, mod 1<<64
# calculated using inverse_mod in sagemath
INV_1 = 0x887493432badb37
INV_2 = 0xba79078168d4baf
INV_3 = 0xe9e9f4c41d6df849
INV_4 = 0xd872e78f6fe1434b
INV_5 = 0xc592c09fdfba7f0d
MASK64 = (1<<64)-1
def XXH_rotl64(x, n):
return ((x << n) | (x >> (64 - n))) & MASK64
def inverse_round(acc, inp):
inp = (inp * INV_1) & MASK64
inp = XXH_rotl64(inp, 64-31)
inp = (inp - acc) & MASK64
inp = (inp * INV_2) & MASK64
return inp & MASK64
def XXH64_round(acc, inp):
acc += (inp * XXH_PRIME64_2)
acc &= MASK64
acc = XXH_rotl64(acc, 31)
acc *= XXH_PRIME64_1
acc &= MASK64
return acc
def XXH64_mergeRound(acc, val):
val = XXH64_round(0, val)
acc ^= val
acc = acc * XXH_PRIME64_1 + XXH_PRIME64_4
acc &= MASK64
return acc
def XXH64_avalanche(h64):
h64 ^= h64 >> 33;
h64 *= XXH_PRIME64_2;
h64 &= MASK64
h64 ^= h64 >> 29;
h64 *= XXH_PRIME64_3;
h64 &= MASK64
h64 ^= h64 >> 32;
return h64
def inverse_avalanche(h64):
h64 ^= h64 >> 32
h64 *= INV_3
h64 &= MASK64
h64 ^= (h64 >> 29) ^ (h64 >> 58)
h64 *= INV_2
h64 &= MASK64
h64 ^= h64 >> 33
return h64
def inverse_finalize64(prefinal, postfinal):
h64 = postfinal
h64 = (h64 - XXH_PRIME64_4) & MASK64
h64 = (h64 * INV_1) & MASK64
h64 = XXH_rotl64(h64, 64-27)
h64 = inverse_round(0, h64 ^ prefinal)
return h64
def XXH64_finalize(h64, buf):
#print("pre-finalize", h64)
while len(buf) >= 8:
x, buf = buf[:8], buf[8:]
x = int.from_bytes(x, "little")
h64 ^= XXH64_round(0, x)
h64 = XXH_rotl64(h64,27) * XXH_PRIME64_1 + XXH_PRIME64_4
h64 &= MASK64
while len(buf) >= 4:
x, buf = buf[:4], buf[4:]
x = int.from_bytes(x, "little")
h64 ^= (x * XXH_PRIME64_1) & MASK64
h64 = XXH_rotl64(h64, 23) * XXH_PRIME64_2 + XXH_PRIME64_3
h64 &= MASK64
for x in buf:
h64 ^= (x * XXH_PRIME64_5) & MASK64
h64 = XXH_rotl64(h64, 11) * XXH_PRIME64_1
h64 &= MASK64
#print("pre-avalanche", h64)
return XXH64_avalanche(h64)
# TODO: handle longer suffixes
def inverse_suffix(h64, buf):
for x in buf[::-1]:
h64 = (h64 * INV_1) & MASK64
h64 = XXH_rotl64(h64, 64-11)
h64 ^= (x * XXH_PRIME64_5) & MASK64
return h64
def XXH64_digest(data, seed=0):
if len(data) >= 32:
assert(False)
else:
h64 = seed + XXH_PRIME64_5
h64 += len(data)
h64 &= MASK64
return XXH64_finalize(h64, data)
def premine(data, seed, total_len):
if not data:
return (seed + XXH_PRIME64_5 + total_len) & MASK64
v1 = (seed + XXH_PRIME64_1 + XXH_PRIME64_2) & MASK64
v2 = (seed + XXH_PRIME64_2) & MASK64
v3 = seed
v4 = (seed - XXH_PRIME64_1) & MASK64
for i in range(0, len(data)-31, 32):
v1 = XXH64_round(v1, int.from_bytes(data[i+0 :][:8], "little"))
v2 = XXH64_round(v2, int.from_bytes(data[i+8 :][:8], "little"))
v3 = XXH64_round(v3, int.from_bytes(data[i+16:][:8], "little"))
v4 = XXH64_round(v4, int.from_bytes(data[i+24:][:8], "little"))
h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18)
h64 &= MASK64
h64 = XXH64_mergeRound(h64, v1)
h64 = XXH64_mergeRound(h64, v2)
h64 = XXH64_mergeRound(h64, v3)
h64 = XXH64_mergeRound(h64, v4)
h64 += total_len
h64 &= MASK64
buf = data[i+32:]
#print(data, i, buf)
while len(buf) >= 8:
x, buf = buf[:8], buf[8:]
#print(buf)
x = int.from_bytes(x, "little")
h64 ^= XXH64_round(0, x)
h64 = XXH_rotl64(h64,27) * XXH_PRIME64_1 + XXH_PRIME64_4
h64 &= MASK64
assert(len(buf) == 0)
return h64
def fastmine_inner(prefix, target, suffix=b"", numeric_only=True, seed=2811):
postfinal = inverse_avalanche(target)
postfinal = inverse_suffix(postfinal, suffix)
prefinal = premine(prefix, seed, len(prefix)+8+len(suffix))
nonce = inverse_finalize64(prefinal, postfinal)
nonce = nonce.to_bytes(8, "little")
# DUCO PoW results must have a numeric suffix
if numeric_only:
good = True
for c in nonce:
if c < 0x30 or c > 0x39:
good = False
break
if not good:
return None
lol = prefix + nonce + suffix
#print(lol)
#print(hex(xxh64(lol).intdigest()))
#print(hex(XXH64_digest(lol)))
# sanity check
if xxh64(lol, seed=seed).intdigest() == target:
if numeric_only:
return int((nonce + suffix).decode())
else:
return nonce + suffix
# note: this function can only recover 8 or 9 digit numbers
# for shorter ones, you can just bruteforce
# DuinoCoin doesn't go any longer than 9 so I didn't bother implementing that.
def fastmine(prefix, target):
nonce = fastmine_inner(prefix, target)
if nonce is not None:
return nonce
# we can only mathematically invert 8 digits at a time, the 9th
# digit must be bruteforced
for i in range(10):
nonce = fastmine_inner(prefix, target, str(i).encode())
if nonce is not None:
return nonce
return None
# PoC of chosen-prefix preimage attack
prefix = b"SHITCOIN"*5
target_hash = 0xbadc0de
data = prefix + fastmine_inner(prefix, target_hash, suffix=b"LOL", numeric_only=False, seed=0)
print("chosen-prefix preimage PoC:")
print(f"xxh64({data}) == {hex(xxh64(data).intdigest())}")
print()
# recovering a 9 digit number with known prefix, via hash inversion
target_hash = xxh64(b"SHITCOIN"*5 + b"123456789", seed=2811).intdigest()
print("hash inversion:")
print(fastmine(b"SHITCOIN"*5, target_hash)) # 123456789
print()
# this is what a DuinoCoin PoW challenge looks like
# Solving it naively would require 61952180 xxhash iterations.
print("DUCO block mining:")
print(fastmine(b"32ca86d497608f5e18e8ccf0b967b77b02b5389a", 10284008683930761678)) # 61952180
print()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment