CodeShell.kr - Palimpsest

Posted on In Views: Disqus:

Challenge

2048 条记录与 128 个 head，题面说要保留正确的历史。难点在于事件里混了大量干扰节点，而且「最小」是按字节序而不是字符串序。

Keep the right history

保留正确的历史。

1
https://codeshell.kr/challenges/infinity-palimpsest/

Solution

附件 infinity-palimpsest-player.zip 含 contract.txt、events.bin（2048 × 36 字节记录）、heads.txt、root.bin（256 字节）。

Step 1：root.bin 长 256 字节 ⇒ 内存 256 字节；每条记录 ID 即自身 SHA-256，parent 指向前驱 ID，用 {id: record} 建表。

Step 2：按 contract 逐字节实现四种 op（0 加法回绕、1 异或、2 同时交换、3 ROL8(x,3)^v），从 root 向 head 正向重放。128 个 head 全部成功回溯到 root_id，无一 miss（事件中其余 1711 条是干扰节点，只有 337 个节点被 128 条链共享）。

Step 3：对每个 head 计算 SHA256(state + b"terminus")，按字节序（非字符串序）取最小：

1
2
3
BEST head : 328f97098c5d822fa97a8e014482cd8549cb4125a7a603d877b942796c575d93
BEST key  : 0141c0343130d6716572a4a25baee0df16cd61b62c36279d6992a48cfd36cd69
state sha256: 8f652d071f0f642acdbbe83b1a82853721c233456ff0ff1e0edd23b9115d6089

Step 4：用完全独立、无缓存、每个 head 从 root 完整重放的第二份脚本复算，得到同一 head、同一 key、同一 SHA256(state)。

Script

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import hashlib, sys, os

D = "infinity-palimpsest/"
root = open(D+"root.bin","rb").read()
ev = open(D+"events.bin","rb").read()
heads = [l.strip() for l in open(D+"heads.txt") if l.strip()]

assert len(ev) % 36 == 0, len(ev)
N = len(ev)//36
recs = {}
for k in range(N):
    r = ev[k*36:(k+1)*36]
    recs[hashlib.sha256(r).hexdigest()] = r

root_id = hashlib.sha256(b"root"+root).hexdigest()
print("records:", N, "unique ids:", len(recs), "heads:", len(heads))
print("root_id:", root_id, "in events:", root_id in recs)

# check all opcodes, i/j range
ops = set(); imax=0; jmax=0; vmax=0
for k in range(N):
    r = ev[k*36:(k+1)*36]
    op,i,j,v = r[32],r[33],r[34],r[35]
    ops.add(op); imax=max(imax,i); jmax=max(jmax,j); vmax=max(vmax,v)
print("opcodes:", sorted(ops), "i max:", imax, "j max:", jmax, "v max:", vmax)

def apply(mem, op, i, j, v):
    m = bytearray(mem)
    if op == 0:
        m[i] = (m[i] + m[j] + v) & 0xFF
    elif op == 1:
        m[i] = m[i] ^ m[j] ^ v
    elif op == 2:
        a = m[j] ^ v
        b = m[i]
        m[i] = a; m[j] = b
    elif op == 3:
        x = m[i]
        m[i] = (((x << 3) | (x >> 5)) & 0xFF) ^ v
    else:
        raise ValueError(op)
    return bytes(m)

MSIZE = len(root)
# resolve each head to root, cache node memories
cache = {root_id: root}
results = []
miss = 0
for h in heads:
    if h not in recs:
        print("HEAD NOT IN EVENTS:", h); miss += 1; continue
    # walk chain collecting records until we hit a cached id
    chain = []
    cur = h
    while cur not in cache:
        if cur not in recs:
            print("MISSING PARENT:", cur); chain=None; break
        r = recs[cur]
        chain.append(r)
        cur = r[:32].hex()
    if chain is None:
        miss += 1; continue
    mem = cache[cur]
    for r in reversed(chain):
        op,i,j,v = r[32],r[33],r[34],r[35]
        mem = apply(mem, op, i, j, v)
        cache[hashlib.sha256(r).hexdigest()] = mem
    results.append((hashlib.sha256(mem+b"terminus").hexdigest(), h, mem))

print("resolved:", len(results), "miss:", miss, "cache size:", len(cache))
results.sort(key=lambda t: bytes.fromhex(t[0]))
best = results[0]
print("BEST head:", best[1])
print("BEST key :", best[0])
print("BEST state sha256:", hashlib.sha256(best[2]).hexdigest())
print("state hex:", best[2].hex())
print("--- top 5 ---")
for k in range(5):
    print(results[k][0], results[k][1])
open("best_state.bin","wb").write(best[2])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import hashlib
D = "infinity-palimpsest/"
root = open(D+"root.bin","rb").read()
ev = open(D+"events.bin","rb").read()
heads = [l.strip() for l in open(D+"heads.txt") if l.strip()]
recs = {hashlib.sha256(ev[k*36:(k+1)*36]).hexdigest(): ev[k*36:(k+1)*36] for k in range(len(ev)//36)}
root_id = hashlib.sha256(b"root"+root).hexdigest()

def apply(m, op, i, j, v):
    m = bytearray(m)
    if op==0: m[i] = (m[i]+m[j]+v)&0xFF
    elif op==1: m[i] = m[i]^m[j]^v
    elif op==2: m[i], m[j] = m[j]^v, m[i]
    else: m[i] = (((m[i]<<3)|(m[i]>>5))&0xFF)^v
    return bytes(m)

def replay(h):
    chain=[]; cur=h
    while cur != root_id:
        r = recs[cur]; chain.append(r); cur = r[:32].hex()
    m = root
    for r in reversed(chain): m = apply(m, r[32], r[33], r[34], r[35])
    return m, len(chain)

best=None
lens=[]
for h in heads:
    st, L = replay(h); lens.append(L)
    k = hashlib.sha256(st+b"terminus").hexdigest()
    if best is None or bytes.fromhex(k) < bytes.fromhex(best[0]): best=(k,h,st,L)
print("chain length min/max:", min(lens), max(lens))
print("best key:", best[0])
print("best head:", best[1], "chain len:", best[3])
print("sha256(state):", hashlib.sha256(best[2]).hexdigest())
print("state == root?", best[2]==root)
# locate first differing byte vs root
print("diff indices vs root:", [n for n in range(256) if best[2][n]!=root[n]])
print("opcodes along best chain (from root):")
chain=[]; cur=best[1]
while cur != root_id:
    r=recs[cur]; chain.append(r); cur=r[:32].hex()
for r in reversed(chain):
    print("  op=%d i=%d j=%d v=%d" % (r[32],r[33],r[34],r[35]))
CodeShell{8f652d071f0f642acdbbe83b1a82853721c233456ff0ff1e0edd23b9115d6089}