20 KiB
Report: header grinding for locality (acceptance rule and memory access, lane adv-accept-2)
internal adversarial pass, not an independent review
Header
| Item | Value |
|---|---|
| Target commit | 017e703764 (class v4 sub-version 3, object byte 7) |
| Base commit of this branch | 04c4d9bc (build/master merged at 19:46 UK). git diff --quiet 017e7037... HEAD -- igneum-pow prints nothing: igneum-pow is byte-identical to the frozen object, verified at 7a7caa34 and again at 04c4d9bc |
| Crate built | igneum-pow at the frozen commit (this worktree's copy). Harness tools/attack/adv-accept-2 (igneum-pow by path; mirrors verify.rs; the real draw Epoch::chain_program(ProgramClass::V4) and the real address map verify::load_index come from the library) |
| Binary sha256 (the sweeps) | 20e0000eb927f094c7d0918cd3b7caea22ab4d2a18be7ca6d123075de22a63f8 (rows sweeps); 0bc825b5cbd4df2d6b866b8d2396d2bd38d67344b330ad054361fb5c70f0ffb1 (prefix, diffuse); 4421f760b37fb0eb9bf906457c8e1fcf97545335224831efba104040d3b73364 (repeats); da8c5e00c4939a7b6a533518f53c31572a0f9fd5d94509317b29258d71779a3d (dump); c0164d66aa556707cf4efc02cba6a8f4e4e4bf10080bfc706c4d87594fb0520f (export) |
| Boxes | build-1 (real programs, plants, live confirmation, probes); build-2 (eight drawn programs). Every run single-thread, nice 10, cores 8 to 95. GPU: RunPod RTX A6000 48 GB (driver 570.195.03, CUDA 12.8), rented by the fleet lane 20:06 to about 21:00 UK |
| Logs | docs/analysis/cryptanalysis/logs/adv-accept-2/ (copied from /srv/builds/_adv-adv-accept-2/ on each box and /root/fleet/out/ on the pod) |
| Box-hours | about 9.0 core-hours in all (the 1e8 pass 8.3: 16 cores x 1,878 s; the first pass 0.7) (first pass: build-1 0.45: two 1e7 sweeps of 377 and 389 s, two plants of 39 s, two live runs of 49 s, probes and exports about 10 min; build-2 0.21: eight 2e6 sweeps of 89 to 99 s). Seven 8 s builds. Pod: about 0.3 h of a 3 h rental |
| Clock | UK time from TZ=Europe/London date throughout |
Rule-change ledger (honest box-hours): 19:3x UK no SIGSTOP yield, taskset cores 8 to 95, logs outside the worktree mirror; 19:55 UK one sweep per box under sweep.lock; 20:2x UK kill hand-started sweeps and start nothing until lease pool (live 20:22 UK). At 20:23 UK nothing of mine was running on either box (pid check: 0 processes); nothing was killed, lost or re-queued; no box run was started after that.
Draw-path validation (passed)
| Program | Through Epoch::chain_program(V4) | Pack | Match |
|---|---|---|---|
| Shared devnet epoch 0 | id 0xa785001687d8688a, attempt 1, generator 4, sites 1 4 6 10 12 20 27 30 35 40 41 43 45 52 53 54 | v4-devnet-epoch0/program.json | yes |
| Devnet 3 epoch 0 | id 0xfce15bf61030be57, attempt 0, generator 4, sites 3 8 14 15 20 26 28 35 40 43 47 49 52 53 61 62 | v4-devnet3-epoch0 (zip sha256 e025750f... verified on build-1) | yes |
Log: logs/adv-accept-2/draw-check.log.
Status board
| Q | Method | Known-failed shape (fired?) | Gate | Result | Status |
|---|---|---|---|---|---|
| Q1 | Header to address: read bind.rs and spec 1.6; one-bit flips of H over 4,096 header pairs, fraction of the 4,096 unit addresses that change; dataflow count of header-predictable load sites | header-blind plant (init = program seed) must read 0: read 0.0000 | real path near 1.0 | 1.0000 of addresses change on both real programs; 2 to 4 of 16 sites in iteration 0 are predictable from the header alone, 0 in iterations 1 to 7 | PASS (bound) |
| Q2 | Distinct 2 KiB rows, 8 KiB rows, 64 B lines, items per hash and per unit over 1e7 hashes on each real program (closed form), 1e5 on the live dataset, 2e6 on eight drawn programs; tails 1e-3, 1e-4, 1e-5 against a windowed random baseline | const-site and tiny-window plants must collapse the counts at once: const-site 4095.4 to 3845.5 items per unit, tiny-window 4018 to 3988 rows8KiB | best tail inside the baseline's own spread | every clean program sits on the windowed baseline at mean, min and all three tails, per hash and per unit; the live dataset agrees with the closed form | PASS (bound) |
| Q3 | Price: search cost in hashes per found group against loads saved; one card point on the A6000 | a 10 percent saving at the 1e-5 tail nets far under 1 percent: 1.0e-5x | no grind nets over 1 percent | the best 1 in 15 header groups run 0.09 percent faster on the card and cost 15 full hashes each: net about 0.07x; the 1e-5 tail saves 37 of 4,096 rows (0.9 percent) at 1e5 hashes each: net 1e-5x | PASS (bound); card point MEASURED |
| Q4 | Does (c)/(c'') bound per-hash or only per-program locality: read accept.rs; tiny-window plant through the rule; the per-program repeat drawn:0 shows | tiny-window plant: the rule's LaneConstantSite and ratio tests are evaluated on the program, not the header, so a header cannot move them (confirmed: no header changes a clean tail) | rule rejects planted clustering; headers do not move a clean tail | the rule bounds the PROGRAM (mean distinct over 120 of 128; per-site ratio 0.98 on 2^20 fixed evaluations); it has no per-header term and needs none: the construction (every load after the first 2 to 4 depends on loaded data) bounds the per-hash side. One accepted drawn program repeats a word in 1.55 percent of hashes per site pair (FINDING, 0.1 percent of loads) | PASS, one small FINDING |
| GPU | Dependent-read throughput of 2,048 units x 200 rounds per table, three repetitions | const-site plant must run faster: +6.3 percent (its 31 duplicate lanes per site coalesce) | the best ground groups against random | random 1.6130e6 units/s; best ground 1.6145e6 (+0.09 percent); tiny-window 1.6211e6 (+0.5); const-site 1.7139e6 (+6.3) | MEASURED |
Q1. What of the header reaches the load addresses
From bind.rs and spec 1.6: the miner's header bytes (coinbase, extra nonce, timestamp) and the high 32 bits of the nonce reach the hash only as I = seed_words_from_bytes("igneum-block/" || H || nonce_hi_le32): FNV-1a 64 over 49 bytes under four salted bases, each finalised by h ^= h >> 33; h *= 0xff51afd7ed558ccd; h ^= h >> 33. Every header byte enters all eight words of I. Register init is r[i] = splitmix32((n XOR I[i]) + 0x9e3779b9 (i+1)) XOR I[(i+1) & 7] per lane. The program (from the epoch seed) and the dataset (from the day) do not depend on the header. Load address (verify::load_index, spec 1.13.1): y = rotl(x M, R), masked into the site's window (the dataset, a half or a quarter) and offset; physical address 4 idx bytes under any era interleave.
Measured: a one-bit flip of H changes 1.0000 of the 4,096 unit addresses on both real programs (4,096 pairs each; logs diffuse-devnet-4096.log, diffuse-devnet3-4096.log). The header-blind plant (I = program seed, the pack vectors' form) reads 0.0000 (diffuse-devnet-headerblind-1024.log), so the probe distinguishes.
The predictable prefix (prefix.log): a load site whose source has no dataflow path from an earlier load can be addressed from (I, n) with ALU work alone. Iteration 0 has 4 such sites on each real program (devnet instructions 1, 10, 12, 30; Devnet 3 instructions 3, 8, 14, 15) and 2 to 3 on the eight drawn ones; iterations 1 to 7 have none. So at most 4 x 32 = 128 of a unit's 4,096 loads (3.1 percent) can be chosen by header search without executing memory; every other address needs the loads before it.
Consequence: a header search can select on at most 3.1 percent of a unit's loads for free; everything else costs the full hash it is trying to save.
Q2. The locality distributions
Per hash (128 loads of one lane) and per unit (4,096 loads), distinct counts, dataset 2^28 words, rows modelled as contiguous 2 KiB (512 words) and 8 KiB (2,048 words), lines 64 B (16 words), items 64 B. "Windowed baseline": uniform y masked into the program's own site windows, the same sample count. Lower is more clustered; q1e-k is the lowest value with at most that fraction below it.
Real programs, closed form, 1e7 hashes each (312,500 units); logs rows-devnet-1e7.log, rows-devnet3-1e7.log:
| Program | Scope | Metric | mean | min | q1e-3 | q1e-4 | q1e-5 | baseline mean | baseline min | baseline q1e-5 |
|---|---|---|---|---|---|---|---|---|---|---|
| devnet | per hash | rows8KiB | 127.924 | 124 | 126 | 126 | 125 | 127.924 | 124 | 125 |
| devnet | per hash | items | 127.999 | 126 | 128 | 127 | 127 | 127.999 | 126 | 127 |
| devnet | per unit | rows2KiB | 4076.40 | 4054 | 4062 | 4058 | 4055 | 4076.39 | 4054 | 4055 |
| devnet | per unit | rows8KiB | 4018.43 | 3978 | 3991 | 3985 | 3981 | 4018.41 | 3974 | 3978 |
| devnet | per unit | lines/items | 4095.38 | 4089 | 4092 | 4091 | 4090 | 4095.39 | 4089 | 4090 |
| devnet3 | per hash | rows8KiB | 127.926 | 123 | 126 | 126 | 125 | 127.926 | 124 | 125 |
| devnet3 | per unit | rows2KiB | 4076.86 | 4055 | 4062 | 4059 | 4058 | 4076.88 | 4053 | 4055 |
| devnet3 | per unit | rows8KiB | 4020.30 | 3976 | 3993 | 3987 | 3984 | 4020.33 | 3978 | 3983 |
| devnet3 | per unit | lines/items | 4095.40 | 4090 | 4092 | 4091 | 4090 | 4095.40 | 4088 | 4090 |
The plain uniform baseline (no windows) reads 4080.05 rows2KiB and 4032.67 rows8KiB per unit: the 4 to 14 row deficit of the real programs against it is the era's quarter and half windows (spec 1.13.1), a per-program property, present on every header and in the windowed baseline.
Live memory-hard dataset, 1e5 hashes each (logs rows-devnet-live-1e5.log, rows-devnet3-live-1e5.log): devnet per unit rows8KiB mean 4018.70, min 3983 (baseline 4018.30, 3986); devnet3 4020.38, min 3989 (baseline 4020.40, 3989); per hash identical to the closed form to three decimals. The loaded values do not change the locality distribution, as argued in the harness header (the address is computed from the source register before its own load).
Eight drawn programs, 2e6 hashes each on build-2 (logs rows-drawn0..7-2e6.log): seven sit on their windowed baseline at every quantile (per-unit rows8KiB means 4009 to 4031 against baselines 4013 to 4031, mins within 6 of the baseline's). drawn:0 (id 0x5d7cc2b09fc6922a, attempt 0, accepted) reads 127.875 items per hash against 127.999, and 4091.35 per unit against 4095.35, on every header: see Q4.
Same-instruction coalescing (lane pairs of one load site sharing a row or line, the only hits a row buffer or a coalescer sees together), per unit: devnet mean 0.297 pairs per 2 KiB row, 1.18 per 8 KiB row, 0.0093 per 64 B line (max over 312,500 units: 5, 9, 2); Devnet 3 0.254, 1.00, 0.0078 (max 5, 8, 2). The windowed expectation is of this size (quarter windows raise the uniform 0.12 / 0.48 / 0.0038). The const-site plant reads 3,970 line pairs per unit (31 x 32 / 2 x 8 = 3,968 expected): the metric fires.
Plants (logs rows-devnet-plant-const-1e6.log, rows-devnet-plant-tiny-1e6.log): const-site, items per unit 3845.50 (every header), tiny-window rows8KiB 3988.34 against 4018.43, both far outside the clean spread at the first unit.
Result: BOUND. Over 2.6e7 header-chosen hashes on ten accepted programs the most clustered unit found saves 40 of 4,096 8 KiB rows (1.0 percent), 26 of 4,096 2 KiB rows (0.6 percent) and 7 of 4,096 lines or items (0.17 percent) against the mean, and the windowed random baseline reaches the same values at the same sample size. Header choice adds no locality beyond chance.
Q3. The price
A card bound by random 4-byte reads mines at (reads per second) / 128 hashes. A header search evaluates candidate groups; each evaluation is a full hash (128 reads per lane) except for the 2 to 4 header-predictable sites of iteration 0, which can be addressed without memory. A found group is one 32-lane unit: the address set is fixed by (program, I, g), so it mines once and the search does not amortise. Net rate against honest, with dL loads saved in the found unit and S candidates searched per find: 128 / ((128 - dL) + S 128).
| Tail | Rows saved per unit (8 KiB, from Q2) | S (hashes per find) | Net rate vs honest |
|---|---|---|---|
| best 1 in 15 (the exported top 2,048 of 31,250) | 17 of 4,096 (0.4 percent) | 15 | 0.066x |
| 1e-3 | 27 (0.7 percent) | 1,000 | 1.0e-3x |
| 1e-5 | 37 (0.9 percent) | 100,000 | 1.0e-5x |
| any dL below 128 per hash | S | below 1 / S |
The free-prefix strategy (select on the 2 to 4 predictable sites only, never execute a rejected candidate): the gain is bounded by collisions among at most 128 predictable addresses, 128^2 / 2 / 2^17 = 0.06 expected 8 KiB row pairs per unit; even all 128 in one row (probability about 2^-17 x 127) saves 127 of 4,096 loads, 3.1 percent, and the realistic 1e-5 tail of a Poisson(0.06) is 4 pairs, 0.1 percent. No strategy nets 1 percent.
Card point (logs/adv-accept-2/gpu-rowbench-a6000-2048x200.log; kernel tools/attack/adv-accept-2/gpu/rowbench.cu; RTX A6000, 2,048 units x 200 rounds, three repetitions each, spread under 0.03 percent):
| Table (devnet program) | Mean distinct 8 KiB rows per unit | Unit-hashes per second | Against random |
|---|---|---|---|
| random headers | 4018.2 | 1.6130e6 | 1.000 |
| best 2,048 of 31,250 headers by fewest rows | 4001.4 | 1.6145e6 | 1.0009 |
| tiny-window plant | 3988.2 | 1.6211e6 | 1.0050 |
| const-site plant (one lane-constant site) | 3776.8 | 1.7139e6 | 1.0626 |
The card gains 0.09 percent on the best header groups, which cost 15 full hashes each to find: net 0.07x of honest. The const-site plant's 6.3 percent is the coalescer serving 31 duplicate lanes per planted site from one transaction, the shape rule (c) rejects. Caveats: the kernel reads the same 2,048 tables for 200 rounds (the 268 MB of touched sectors exceed the 6 MB L2, so cross-round hits are a few percent at most and equal for all four tables); the A6000 reads 6.6 G dependent 4-byte words per second here, about 0.38 of the RTX 5090's 17.5 G in chip-model-v3 5.1; the DRAM address mapping of the card is not the contiguous-row model, which is why the measured gain follows lines, not rows.
Result: BOUND. No header-grinding strategy nets above 1 percent of rate; the measured card point agrees.
Q4. The acceptance rule and per-hash locality
Rule (c) interprets the program for 64 fixed units (base nonces from a seed-keyed stream, init words = the seed words) and rejects a load site that reads one address in all 32 lanes of any of those units, and a program whose distinct-address mean over the 2,048 evaluations is 120 of 128 or under. Rule (c'') rejects a site whose distinct word indices over 2^20 fixed evaluations fall under 0.98 of uniform on its window. Neither test has a header term: they bound the PROGRAM on the acceptance stream, and the miner's init words are different words. So the rule bounds per-program locality only. The per-hash side is bounded by the construction, not the rule: every load after the 2 to 4 predictable ones depends on loaded data (Q1), every address is a bijective image of a register (M odd, R a rotation), and Q2 shows no header moves a clean program off chance. The planted clustering (tiny-window, const-site) is a program property the rule's (c) tests see on their own stream.
FINDING (small, per program, public to every miner): drawn:0 (id 0x5d7cc2b09fc6922a, attempt 0, accepted by the frozen rule) reads the same word at load sites 1 and 5 (instructions 6 and 26) in 1.55 percent of hashes per iteration, 0.124 repeats per hash (logs repeats-drawn0-2e5.log, dump-drawn0.log). Mechanism: both loads read r3; the only write to r3 between them is rotr r3 by (r1 AND 31) at instruction 22, the identity when r1 AND 31 = 0 (1 in 32); site 1's quarter window (win 2, off 1) lies inside site 5's half window (win 1, off 0), so the two indices coincide when bit 26 of y is set (1 in 2): 1/64 per iteration per lane, 0.125 per hash, as measured. Rule (a) counts the rotate as a write; rule (a') counts rotr as freshness-preserving; rule (c) admits it because the mean stays at 127.875 of 128. Gain: a chip or card that serves the second read from the first saves 0.1 percent of loads on this program; the rule's floor of 120 admits up to 6.25 percent per program in principle. The devnet program shows 12 chance repeats in 200,000 hashes (0.00006 per hash). Header grinding cannot move this: it is the same on every header.
Result: PASS with one FINDING of 0.1 percent (a data-dependent rotate by a possibly zero amount as the only write between two loads from one register).
Consequences per user tier
| Tier | What this means | What is being done |
|---|---|---|
| Home miner (one card, any size, any vendor, any OS), rig, pool user | Nobody gains from grinding headers for locality: the best group a search can find runs 0.09 percent faster on a card and costs 15 hashes to find. Mining stays one header, every nonce. The drawn:0 repeat is 0.1 percent for every miner alike, no tier favoured | Nothing to change in the miner. The repeat class is handed to the rule's owners as a one-line note (a rotate by a register amount as the sole write between two loads from one register) |
| A chip that stores the dataset (chip-model-v3 5) | Header choice gives it nothing either; its per-hash read count stays 128 (Q2) and the items per unit stay at 4,095 of 4,096 | The analytic bound of Q3 and the card point stand on their own |
The 1e8 pass (lease pool, build-1): the 1e-6 tail and the prevalence of the finding
Ran 20:48 to 21:15 UK on 16 leased pool cores of build-1 (lease pool 32 --min 8, class adv, owner adv-accept-2; the waiter sat 7 minutes behind the attack-pass F9 leases, then held 16 cores for 1,878 s). 16 shards of 6.25e6 hashes per real program (1e8 hashes, 3.125e6 units each; logs logs/adv-accept-2/rows-1e8/rows--1e8-s.log) and the 300-program census (rotclass-300.log). Binary sha256 003e540eee23c8621eb1282c2c9a1b4aca981e81337daa20f63e8469d01b1e7e. Ledger: the box-1 lease was killed by its pid file at 21:16 UK on the coordinator's move order, AFTER all 33 jobs had finished (the kill is the "Terminated, exit 143" in lease-1e8.log); the duplicate resubmission on build-2 was killed by its pid file at 21:17 UK before it took cores; nothing was lost and nothing is queued.
| Program | Scope | Metric | mean over 1e8 | min over 3.1e6 units (about the 3e-7 quantile) | baseline min, same sample | per-shard q1e-5 range | baseline q1e-5 range |
|---|---|---|---|---|---|---|---|
| devnet | per unit | rows8KiB | 4018.44 | 3967 | 3974 | 3975 to 3980 | 3977 |
| devnet | per unit | items | 4095.38 | 4089 | 4089 | 4090 | 4090 |
| devnet | per hash | rows8KiB | 127.924 | 123 | 124 | 125 | 125 |
| devnet3 | per unit | rows8KiB | 4020.34 | 3971 | 3981 | 3981 to 3983 | 3983 |
| devnet3 | per unit | items | 4095.40 | 4089 | 4088 | 4090 | 4090 |
| devnet3 | per hash | rows8KiB | 127.926 | 123 | 124 | 125 | 125 |
The deepest unit in 1e8 header-chosen hashes saves 51 of 4,096 8 KiB rows (1.2 percent) against the mean, 7 rows more than the windowed baseline's own deepest unit at the same sample size (3967 against 3974; 3971 against 3981 on Devnet 3), a one-sample extreme inside the spread of such minima; at the 1e-5 quantile the two agree to 2 rows. Items per unit and per hash have identical minima to the baseline. Priced through Q3: 51 rows at a 3e-7 tail is 3.3e6 hashes per find for a 1.2 percent saving on one unit, net 3e-7x. The bound stands at 1e8.
Prevalence of the rotate-identity class (Q4's finding) over 300 drawn accepted class v4 programs through the chain draw path: 63 programs (21.0 percent) hold at least one pair of load sites reading one register whose only intervening writes are rotr by a register amount (73 pairs: 71 with one rotr, 1 with two, 1 with three). Each such pair repeats its address with probability 32^-r per iteration times the window-overlap factor (1 for equal windows, 1/2 or 1/4 for nested ones, 0 for disjoint offsets), so one pair costs at most 1 of 128 loads in 1 of 32 iterations: 0.024 percent of loads per pair, 0.1 percent on drawn:0 (two overlapping windows, one rotr). The mean over accepted programs is about 0.006 percent of loads. The two real programs hold no such pair (repeats-devnet-2e5.log: 12 chance repeats in 2e5 hashes). The class is a note for the rule's owners (rule (a) counts a rotate as a write, rule (a') treats rotr as freshness-preserving; both are right about entropy and silent about identity), not a gain anyone mines: a chip or card that serves the second read from the first saves under 0.1 percent on the worst program of 300 and nothing on the real ones.
What a longer pass would add
A 1e9-hash sweep per program moves the 3e-7 tail to 3e-8 on the same baseline; a 3,000-program census refines the 21 percent prevalence and tabulates the window-overlap factor per pair; a card point on an RTX 5090 instead of the A6000 reproduces the 0.09 percent at the production read rate. None of these changes the bound.