BrendanChambersBourgeois/sdbkz-benchmark

# BKZ 动力系统基准测试：基于 Li-Nguyen Rankin 分布的格归约实证评估 [](https://github.com/BrendanChambersBourgeois/sdbkz-benchmark/actions) [](https://doi.org/10.5281/zenodo.19686927) [](LICENSE) [](https://creativecommons.org/licenses/by/4.0/) [](https://www.python.org/) CI 工作流会在全新的代码检出基础上构建 Docker 镜像，并在每次提交时运行数值验证，因此任何环境级别的可复现性倒退都会立即使构建失败。 ## 90 秒快速入门 ``` git clone https://github.com/BrendanChambersBourgeois/sdbkz-benchmark cd sdbkz-benchmark docker build -t sdbkz-benchmark:ci . # ~5 min docker run --rm -e NUM_SEEDS=1 sdbkz-benchmark:ci bash scripts/verify.sh # 预期尾部： # PASS seed 1: advantage=0.211363 (ref=0.211363) # VERIFICATION PASSED ``` `verify.sh` 会在锁定版本的容器中从头重新生成一个论文参考种子，并将输出与硬编码的参考值进行 4 位小数精度的比较。如果出现任何数值偏差，则退出状态码为 1。 ### 故障排除 **`docker: permission denied while trying to connect to the Docker daemon socket`** — 安装后用户不在 `docker` 组中。运行一次： ``` sudo usermod -aG docker $USER newgrp docker # or log out + back in ``` **`pytest: collected 0 items`** — `$(pwd)` 从子目录中展开。在执行 `docker run -v $(pwd)/...` 之前，请先 `cd` 到仓库根目录。 **全新的 Ubuntu 虚拟机运行：** `pytest` 和 `analysis/paper_figures.py` 应该**在 Docker 镜像内**调用，而不是在宿主机端。该镜像将所有依赖版本（fpylll、numpy、MPFR）锁定为论文中使用的确切修订版；裸机 Ubuntu 安装上的系统 Python 完全没有安装它们。 **Docker 运行后绑定挂载的文件归 root 用户所有：** 该镜像默认在 UID/GID 1000:1000 下内置了非 root 用户（与最常见的 Linux 桌面相匹配）。如果你的宿主机 UID/GID 不同，请在构建时覆盖： ``` docker build --build-arg HOST_UID=$(id -u) --build-arg HOST_GID=$(id -g) -t sdbkz-benchmark:ci . ``` 或者使用 `docker compose`，首先导出环境变量（compose 会自动展开 `${UID}`/`${GID}`）：`UID=$(id -u) GID=$(id -g) docker compose run --rm verify`。WSL 用户通常需要这样做；默认安装的原生 Linux 通常不需要。 ## 工程 TL;DR 本仓库包含 以及用于数值实验的防御性工程的案例研究。论文 1（LWE-Kannan，通过 Zenodo 发布）与论文 2（进行中，`paper2/`）相伴：NTRU 致密子格发现（DSD）的起始点，以及将 G6K 作为第二个归约引擎接入到受确定性控制的接缝之后的跨引擎（枚举 vs 筛选）研究。标题党式的核心发现是 **fplll 的 Gram-Schmidt 递推中存在灾难性相消 bug**（`fplll/gso_interface.cpp:147–151`），该 bug 在 1000 位 MPFR 精度下会损坏 38% 的基（q=3329 n=100 β=30）。一个 30 行的 Kahan 补偿补丁将发生率降至 0/55，通过了所有 15 个 fplll 回归测试，并在 Intel 13900K 和 AMD 9950X3D 上重现了比特一致的输出。该 bug 是 fpylll #272 中相消系列 bug 的新实例；该补丁已于 2026-05-08 作为 [fplll PR #550](https://github.com/fplll/fplll/pull/550) 提交至上游（于 2026-05-17 关闭未合并；该补丁随本仓库分发，论文 §8 本身依然成立）。详见论文 §8 和 `patches/fplll_gso_kahan.patch`。 本仓库的其他部分是使发现该 bug 成为可能的基础设施：锁定版本的 Docker 构建、经过 SHA-256 校验的种子清单（10,861 个 fplll 条目 + 2,104 个 G6K 条目，均由 CI 进行 lint 校验）、三种环境间字节一致的数值输出、每个声明的证据账本，以及涵盖 clamp 语义、文件身份去重、清单完整性、路径迁移、统计辅助程序、NTRU 构建检查和 v2.0.0 软链接删除回归防护在内的 325 个单元测试。 ## 工程亮点 - **fplll 相消 bug 及 Kahan 补丁。** 论文 §8.3 分离出了一种从未被标记过的数值病理现象，它出现在 fplll 的 GSO 计算中，并在密码学模数下触发。完整链条：诊断脚本 → 原始 `get_r()` 捕获 → 跨机器重现 → 算法级根因 → 30 行补丁 → 55 颗种子的回归重跑。`patches/fplll_gso_kahan.patch` 可以直接插入到 fplll HEAD（提交 `1987472`）中；已于 2026-05-08 作为 [fplll PR #550](https://github.com/fplll/fplll/pull/550) 提交至上游（于 2026-05-17 关闭未合并；随本仓库分发）。 - **经过校验的种子清单。** `results/seed_manifest.json` 使用 SHA-256、大小、mtime、已校验标志、每种子 advantage 索引了每个 fplll 种子文件 — 跨越 7 次活动的 10,861 个条目；`scripts/lint_seed_manifest.py` 在每次 CI 运行时检查三个不变式（无孤立文件、无幽灵条目、无哈希漂移），在 v1.3.x → v2.x 发布链中违规数为 0。G6K 引擎有自己的清单（`results/g6k_seed_manifest.json`，2,104 个条目，`scripts/lint_g6k_manifest.py`）— 两个引擎的哈希不可比较，也从不合并（ADR-005）。 - **跨 3 个环境的比特一致可复现性。** Intel 13900K / AWS Batch / AMD 9950X3D 全部产生字节一致的种子 JSON（在 `hash_verification.txt` 中校验了 100 颗种子的 SHA-256 哈希）。不同的 MPFR 小版本（4.2.0 vs 4.2.1）、不同的 CPU 供应商、不同的容器运行时 — 没有漂移。 - **仅追加的审计链。** `results/clamp_events.jsonl` 记录了每次防御性 clamp 触发（非正的 `get_r` 值）及其时间戳、脚本名称和种子上下文。根据策略从不截断。`logs/pipeline.jsonl` 接收来自每个已提交脚本的结构化事件（由 `scripts/lint_logging.py` 强制执行）。 - **CI 把关的数值可复现性。** `.github/workflows/build-and-verify.yml` 在每次推送时运行：从零开始的 Docker 构建 → 导入冒烟测试 → 325 项测试的 pytest 套件（数值核心开启 mypy strict，ruff F/W/I/B/UP，pytest --cov 75% 下限） → `verify.sh` 在全新容器中重新生成一颗种子并比对 SHA-256 → `verify_g6k.sh` 对 G6K 引擎进行精确 SHA-256 门控 → `validate_seeds.py` 进行 schema + volume 漂移检查 → 清单 lint 及论文图表一致性门控。这些中的任何回归都会导致构建失败。 - **事件驱动的强化。** 仓库策略是针对真实运营事件而非臆想事件制定的。防御性 clamp 必须在替换前记录原始值（这是在某个 clamp 隐藏了真实的 `get_r` 返回值 9 天并在草稿论文中产生了一个错误的第 8 节之后引入的 — 参见 [`docs/incident_q3329_post_mortem.md`](docs/incident_q3329_post_mortem.md)）。数据绝不无备份删除。`sudo` 路径需要显式选择加入。 ## 数据流架构 ``` flowchart LR A[runners
run_campaign · sweep_parallel · q3329_verify
run_3x_extended · run_convergence · ...] -->|writes| B[results/seeds/
<campaign>/] B -->|indexed by| C[results/seed_manifest.json
10,861 entries · SHA-256] C -->|read by| D[analysis/_data.py
load_all_seeds campaign=...] D -->|renders| E[paper figures
stats tables
runtime tables] B -->|validated by| F[lint_seed_manifest
validate_seeds] F -->|CI gate| G[GitHub Actions
Docker + pytest + verify.sh] A -->|side-log| H[results/clamp_events.jsonl
append-only] A -->|structured events| I[logs/pipeline.jsonl] ``` 每个写入器都通过 `scripts/_seed_paths.py::seed_path_for()` 进行路由。每个读取器都查询清单。读取时通过 SHA-256 进行交叉验证。活动树（`main`、`q3329`、`cliff500`、`fplll_sensitivity`、`tours3x`、`convergence`、`ntru`，加上引擎分离的 `ntru_g6k` 和仅用于验证的 `ntru_patched`）是 v1.3 之后唯一的真理来源。 **v2.0.0 布局变更。** v1.3 之前的顶层种子目录（`results/raw/`、`results/cloud/`、`results/q3329/`、`results/cliff_500bit/`、`results/3x_tours/`、`results/convergence/`、`results/convergence_test/`、`results/fplll5*_sensitivity/` 等）作为向后兼容的软链接，从 v1.3 一直存在到 v1.5.2，以便为外部引用留出时间重新规划路径。它们在 v2.0.0 中被废弃；`results/seed_path_crosswalk.csv`（4,387 行，已提交）是永久的旧→新映射对照表。任何论文时代对 v2 之前路径的引用都通过该对照表解析为规范的 `results/seeds//...` 位置。 ## 许可证 - **代码**（脚本、分析、Docker、补丁）：[MIT](LICENSE) - **论文和数据**（`paper1/`、`paper2/`、`results/`）：[CC-BY-4.0](https://creativecommons.org/licenses/by/4.0/) ## 项目范围 本项目将 **自对偶 BKZ (SD-BKZ)** 算法与标准 BKZ 在格基归约方面进行基准对比。论文 1 测量了跨越 11 个维度（n=50–150）、3 个块大小（β=20、30、40）以及每种配置 100 个随机种子（四个填补方差的组为 122 个种子）— 合计 3,388 次主扫描运行 — 的 LWE-Kannan 格上向 Li-Nguyen 不动点 Rankin 分布的收敛情况。论文 2（进行中）扩展到了循环 NTRU — SD-BKZ 优势的维度起始点，一个随维度增长的、无参考的致密子格发现（DSD）起始点鸿沟，以及一项通过 fplll 的精确枚举 oracle 和 G6K 筛选运行相同实例的跨引擎研究。 ## 当前结果（论文 1） **超过 4,000 次独立试验。** 主扫描已完成：33 个 (n, β) 组中的 33 个均拥有 100 颗种子 — 四个填补方差的组为 122 颗 —（3,388 次运行）。除主扫描之外：在 3× tour 能力实验中有 500 颗种子，在 500-tour 收敛测试中有 40 颗种子（在 n=90 和 n=140 时各 20 颗，β=30），在 1000 位 MPFR 下进行 q=3329 n=100 β=30 表征时有 100 颗种子，以及在 n=50/70/80/90（β=30）下进行 q=3329 验证时有 80 颗种子。云上活动已于 2026-04-10 完成并下线；所有剩余工作均在本地运行。整个活动期间零数据丢失。 | Dimension | β=20 | β=30 | β=40 | |---|---|---|---| | n=50–80 | 98–100% win, d=1.7–2.7 | 100% win, d=2.8–3.0 | 90–100% win, d=1.3–3.6 | | n=90 | 100% win, d=2.4 | **100% win, d=4.60, mean +0.922** | 100% win, d=3.04 | | n=100 | 99% win, d=2.12 | **100% win, d=6.20, mean +1.346** | **100% win, d=9.40, mean +1.176** | | n=110 | 92% win, d=1.47 | **100% win, d=5.64, mean +1.112** | **100% win, d=6.88, mean +1.158** | | n=120 | 71% win, d=0.60 | 100% win, d=4.97, mean +0.741 | 44% win, mean −0.028 | | n=130 | 54% win (coin flip) 100% win, d=3.19, mean +0.352 | 0% win, mean −1.334 | | n=140 | 22% win (BKZ wins) | 32% win, mean −0.036 (crossover) | 0% win, mean −1.452 | | n=150 | 12% win (BKZ wins) | 0% win, mean −0.395 | 0% win, mean −1.293 | 全部 33 组均包含 100 颗种子。完整的统计表（95% 置信区间、Cohen's d、t-test 和 Wilcoxon p 值）见论文。 主要发现（按重要性从高到低排序）： - **β=30 倒 U 型曲线：** 峰值出现在 n=100（平均 +1.346 nats，d=6.20，100 颗种子 — 数据集中效应最大），随后一路下滑，从 n=120 的 +0.741，n=130 的 +0.352，n=140 的 −0.036，跌至 n=150 的 −0.395（0% 胜率）。即使对于主力的块大小，反向遍历在高维度下也会变得有害。 - **β=40 悬崖式下跌：** n=50–110 处的 100% 胜率骤降至 n=120 处的 44%（平均 −0.028），并在 n=130（−1.334）、n=140（−1.452）和 n=150（−1.293）处跌至 0%。这不是缓慢的衰退，而是结构性的崩溃：在两个维度梯度（n=110 → n=130）内出现了 2.5-nat 的剧烈波动。 - **峰值随块大小迁移：** β=40 在 n=110 处超越了 β=30（+1.158 vs +1.112，均在 100 颗种子下）。更强大的 SVP oracle = 在更窄的有效窗口内拥有更高的峰值，并伴随着更剧烈的峰后崩溃。 - **β/n 阈值 ≈ 0.20：** 低于此比率，SD-BKZ 的优势便会消退并逆转。β=20 在 n=120 处开始消退（71% 胜率），并在 n=130 处发生逆转（54%）。β=30 坚持的时间更长，因为它在更多的维度范围内都保持在该阈值之上。 - **收敛依赖于状态环境（500-tour 测试）：** 在 n=90 β=30 时，BKZ 在 tour 70 之后趋于平缓，而 SD-BKZ 一直持续获益至 tour 500 — 优势从 +0.92 增长到了 +1.33（100% 胜率）。在 n=140 β=30 时，两种算法都会缓慢收敛，但在完全收敛时 BKZ 获胜（tour 500 时平均为 −0.075）。这预防了在两端出现“你 BKZ 跑得不够久”的质疑。 - **3x tour 能力鸿沟：** 进行 210 tours 的 BKZ 无法匹敌仅进行 70 tours 的 SD-BKZ。在 β=30 时，n=50–80 范围内 0/400 的鸿沟被填平。更强大的 SVP oracle 并不等同于较弱的 oracle 运行更多 tours — 这是一种结构性的能力差异。 - **RHF 对 d(LN) 优势视而不见：** 在 n=100 β=30 时，d(LN) 显示 100% 的胜率，而 RHF（Root Hermite Factor，根埃尔米特因子）仅显示 40%，且两者几乎没有相关性（r=−0.08）。标准指标对 SD-BKZ 效应在结构上不敏感 — 这对于任何使用 RHF 作为质量衡量标准的人来说都具有方法论上的重要性。 - **fplll 的 GSO 中出现的 q=3329 数值不稳定性（论文第 8 节）：** 在 n=100 β=30 q=3329 时（1000 位 MPFR，100 颗种子：10 颗云端 + 45 颗 Intel 13900K + 45 颗 AMD 9950X3D），**38% 的种子（Wilson 95% CI [29.1%, 47.8%]）表现出退化的最终基**，其 Gram-Schmidt 对数范数暴跌至精度下限（~−345）。根本原因：`fplll/gso_interface.cpp:147–151` 中类似 Cholesky 的平方形式 GSO 递推在计算 r(i,i) = ‖b_i‖² − Σ μ_{i,k}² · ‖b*_k‖² 时，将其作为一个单一的标量减法，没有进行任何补偿、重正交化或符号检查。使用 Kahan 补偿的补丁将发生率从 38.0%（未打补丁时为 38/100）降至 0%（打补丁后为 0/55）。BKZ (25) 和 SD-BKZ (22) 的命中率几乎是对称的，证实了该 bug 位于共享的 GSO 代码路径中。急剧的维度起始点：n=50、70、80 时 0/20 退化，n=90 时 1/20，跳升至 n=100 时的 38/100。可跨机器复现（Intel 38.2% vs AMD 37.8%；种子 11 在不同架构间比特一致）。这是 fpylll #272 中相消系列 bug 的新实例 — 而不是新的 bug 类别 — 并已于 2026-05-08 作为 [fplll PR #550](https://github.com/fplll/fplll/pull/550) 提交至上游（于 2026-05-17 关闭未合并；该补丁随本仓库分发）。q=97 的结果不受影响。所有 q=3329 的结果在论文中均列为未来工作。 - SD-BKZ 在所有配置下的运行时间均为 BKZ 的 2.3–2.7 倍。 ## 论文和补丁 `paper1/` 目录包含记录基准设计、结果以及 fplll 数值 bug 发现的技术报告；`paper2/` 包含了正在进展中的 NTRU + 跨引擎技术报告（`paper2/latex/`，相同的 `make` 流程）。论文 1 是通过 `make` 从 `paper1/latex/` 生成的，并以 HTML 和 LaTeX 形式与基准代码一同发布： | File | Purpose | |---|---| | `paper1/sdbkz_paper.html` | 可在网页查看的 HTML（拖入任何浏览器即可） | | `paper1/latex/sdbkz_paper_latex.tex` | LaTeX 源码（规范版） | | `paper1/latex/sdbkz_paper_latex.pdf` | LaTeX 渲染的 PDF，33 页（规范产出物） | | `paper1/latex/Makefile` | `make` 一键重新构建 LaTeX PDF | | `paper1/latex/figs/` | 13 张 300 DPI 的图表，按报告顺序编号 | | `paper1/latex/{abbrev3,crypto,biblio}.bib` | 参考文献（cryptobib 提取 + 本地条目） | | `paper1/latex/iacrj.cls`, `metacapture.sty` | 内置 IACR 期刊类（无需子模块） | 要从源码重新构建 LaTeX PDF： ``` cd paper1/latex && make ``` 需要安装带有 `pdflatex`、`bibtex` 和标准 LaTeX 宏包的 TeX Live 发行版。 论文 §8.3 中引用的 **Kahan 补偿的 fplll GSO 补丁** 位于 `patches/fplll_gso_kahan.patch`，并附带了 `patches/README.md`。它可以干净地应用到 fplll HEAD 上（于 2026-04-15 针对提交 `1987472` 验证，所有 15 个回归测试均通过）。仅当你想要重现 q=3329 数值不稳定性分析时才需要使用它 — 论文中的 `q=97` 结果不受影响，也不需要该补丁。 ## 快速开始 **新来的？** 先运行一个示例以确认安装： ``` python3 examples/01_inspect_one_seed.py ``` 这会加载一个现有的结果文件并打印摘要 — 无需新的计算，运行时间不到 1 秒。关于其他示例，请参阅 `examples/README.md`；关于面向任务的小片段（“我想添加一个新维度”、“我想重新生成某张图”等），请参阅 `COOKBOOK.md`。 ### 验证扫描 在 (n=50, β=20) 下运行 5 颗种子，并将结果与已知的良好参考值进行检查： ``` # 通过 Docker docker compose build sweep docker compose run verify # 或直接 bash scripts/verify.sh ``` ### 完整的本地实验 ``` # 通过 Docker docker compose up sweep # 或直接（推荐用于长时间运行的 sweep） tmux new-session -d -s sweep 'python3 scripts/sweep_parallel.py' # 进度：logs/pipeline.jsonl 中的 structured events ``` 扫描过程是完全可恢复的 — 它在启动时会扫描 `results/seeds/main/q97/` 并跳过已完成的工作。结果将作为每个 (n, β, seed) 三元组的独立 JSON 文件写入。每完成 10 次运行就会重新生成一次摘要，保存到 `results/summary.json`。 工作线程数和超时时间配置在 `scripts/sweep_parallel.py` 的顶部： - `NUM_WORKERS`：并行池大小（默认：22） - `TIMEOUT_BY_BETA`：每颗种子的超时时间，以秒为单位（根据块大小分别为 2小时 / 4小时 / 8小时） ### 云端实验 (AWS Batch) 适用于高维度运行 (n=120+) 且单颗种子运行时间对单个虚拟机来说过长的情况： ``` # 构建并推送 cloud container docker build -f Dockerfile.cloud -t bkz-benchmark:latest . # （然后打标签并推送到 ECR — 详情见 submit_jobs.py） # Dry run python3 scripts/submit_jobs.py --dry-run # 提交特定 group python3 scripts/submit_jobs.py --n 100 --beta 30 # 使用自定义 modulus 和 precision 提交 python3 scripts/submit_jobs.py --n 100 --beta 30 --q 3329 --precision 1000 # 为获得最大 parallelism，每个 job 提交 1 个 seed python3 scripts/submit_jobs.py --n 150 --beta 40 --single-seed --vcpus 2 # 覆盖每个 job 的 seeds（默认：25） python3 scripts/submit_jobs.py --n 100 --beta 30 --seeds-per-job 10 ``` 云端作业通过 AWS Batch 在按需实例 (c7i/c6i) 上运行，并将结果写入 S3。每个作业处理一个 (n, β) 组的一块种子。扫描脚本会跳过已经存在于 S3 中的种子，因此重新提交是安全的。 ### sweep_cloud.py 参数标志 云运行器 (`scripts/sweep_cloud.py`) 在容器内接受以下参数： | Flag | Default | Description | |---|---|---| | `--n` | required | 格维度 | | `--beta` | required | 块大小 | | `--seed-start`, `--seed-end` | 1, 100 | 种子范围 | | `--bucket` | — | 用于存储结果的 S3 bucket | | `--output` | — | 本地输出目录 | | `--workers` | auto | 并行工作线程数 | | `--q` | 97 | LWE 模数 (97 或 3329) | | `--precision` | auto | 以位为单位的 MPFR 精度（q≤97 时为 250，q>97 时为 500） | **精度说明：** q≥100 时的 q=3329 暴露了 fplll 平方形式 GSO 递推中的灾难性相消 bug（论文 §8）。更高的 MPFR 精度只会延迟症状的出现，但无法修复它 — 根本原因是算术层面的，而不是位宽问题。250 位精度会触发可见的 GSO 截断，500 位精度会产生每 tour 100–300 nats 的 d(LN) 尖峰，而 1000 位精度在 n=100 β=30 时仍然有 38% 的退化率。如果你需要纯净的 q=3329 输出，请使用 Kahan 补偿补丁（论文 §8.3）。 ### 看门狗系统（已针对云端活动下线） 云端活动已完成，外部看门狗不再运行（AWS Batch 计算环境已于 2026-04-10 停用）。以下两个超时系统作为架构文档保留在代码树中，并将在未来的任何云端运行时自动激活： 1. **进程内看门狗** (`scripts/sweep_cloud.py`)：如果在最大预期种子时间的 2 倍时间内没有种子完成，则杀死容器。q=3329 作业会自动获得更长的超时时间。 2. **外部看门狗** (`scripts/cloud_watchdog.sh`)：设计为通过 cron 运行，终止没有 S3 进度的 Batch 作业。具有 Q 感知能力 — 从作业命令解析 `--q`。 两者必须保持同步。更新超时时间时，请同时更新两个脚本并重新构建 Docker 镜像。 ## 分析包 `analysis/` 目录是一个 Python 包，用于根据每颗种子的 JSON 结果生成图表、诊断和表格。每个图表都位于其独立的模块中，方便导航和选择性使用。 ``` analysis/ paper_figures.py Entry point — CLI with argparse (77 lines) _style.py Shared color palette + matplotlib rcParams _data.py Data loading, lattice math, decomposition helpers plots/ Content-named modules — no numbers; paper figure numbers live in the paper itself. dimension_scaling.py Hero figure: rise-peak-decline curves advantage_histograms.py Per-group distribution + asymmetry convergence_trajectories.py Per-tour d(LN) at 4 representative groups tour_test_3x.py Capability vs speed evidence spatial_decomposition.py Head/mid/tail profile breakdown absolute_dln.py Absolute d(LN) for both algorithms beta_n_scatter.py β/n ratio vs advantage (threshold visual) dln_vs_rhf.py d(LN) reveals what RHF cannot see basis_profiles.py Mean Rankin profile shapes gso_profiles.py GSO log-norm staircase with GSA + LN predictions convergence_500_tours.py Two convergence regimes (n=90 + n=140) q3329_degeneracy.py q=3329 structural instability _orchestrator.py generate_all() — runs the full pipeline diagnostics.py Distribution, crossover tour, runtime, n=90 deep dive tables.py Paper-ready text tables (main results, statistics, spatial) stats_analysis.py Standalone statistical analysis CLI runtime_table.py Runtime table generator (JSON + paste-ready HTML) ``` **生成所有图表：** ``` python3 analysis/paper_figures.py ``` **以编程方式使用单个图表：** ``` from analysis._data import load_all_seeds from analysis.plots import fig_dimension_scaling groups = load_all_seeds(campaign="main") fig_dimension_scaling(groups, output_dir="./figures") ``` ## 实验脚本 规范的入口点（v2.0.0 合并）： - **`scripts/run_campaign.py`** — 由 `config/sweep.toml` 驱动的单一入口调度器。根据活动名称路由到正确的底层运行器（main/cliff500/q3329 使用 q3329_verify，convergence_* 使用 run_convergence，tours3x 使用 run_3x_extended，fplll_sensitivity 使用 Docker 镜像）。用法：`python3 scripts/run_campaign.py --campaign [--n N] [--beta B] [--start S] [--end E] [--seeds N] [--workers W] [--dry-run]`。替代了在 v2.0.0 合并时删除的六个针对单元格的启动脚本（`run_cliff_500bit.py`、`run_n100_beta40.py`、`run_q3329_n90.py`、`run_q3329_n100_local.py`、`run_overnight_q3329_intermediate_1000bit.py`，以及 `run_fplll54_sensitivity.py` 的调度界面）。 主力程序（由调度器调用；也可独立使用）： - **`scripts/sweep_parallel.py`** — 本地虚拟机 q=97 扫描主力程序（多进程池）。遍历规范的 `results/seeds/main/q97/` 目录树。 - **`scripts/q3329_verify.py`** — 具备 Q 感知能力的扫描主力程序（通过 `--q` / `--precision` 覆盖处理 main、cliff500、q3329）。通过 `_seed_paths.seed_path_for` 写入活动树。 - **`scripts/sweep_cloud.py`** — 云端扫描运行器（S3 支持后台，Docker）。包含进程内看门狗。云端已于 2026-04-10 下线；为保持论文云端扫描部分的可复现性而保留。 - **`scripts/run_sweep_fill.py`** — 用于部分单元格的 Argparse 填充运行器 (`--n --beta --start --end`)。 - **`scripts/run_3x_extended.py`** — 3× tour 能力测试（GROUPS 列表可覆盖）。 - **`scripts/run_convergence_test.py`** — 收敛测试（模块级 N/BETA/MAX_TOURS）。 - **`scripts/run_convergence.py`** — 包裹 `run_convergence_test` 的 Argparse 封装 (`--n --beta --max-tours --seeds --workers`)。 - **`scripts/run_fplll54_sensitivity.py`** — 跨镜像敏感性检查（在源码编译 fplll 5.4.x 以对抗 numpy<2 的 Dockerfile.fplll54 构建下，于规范的 n=100 β=30 单元格进行 5 颗种子的测试）。 云端 / 提交 / 运维： - **`scripts/submit_jobs.py`** — AWS Batch 作业提交。标志：`--n`、`--beta`、`--q`、`--precision`、`--vcpus`、`--single-seed`、`--seeds-per-job`、`--dry-run`。 - **`scripts/cloud_watchdog.sh`** — 用于 Batch 作业的外部看门狗，具有 Q 感知超时功能（随云端活动下线；保留供未来使用）。 - **`scripts/overnight_experiments.py`** — 在单台机器上编排多组运行。 数据清理和日志记录： - **`scripts/validate_seeds.py`** — 每颗种子的 schema 和 volume 漂移校验器；强制执行根据 1,960 颗种子的 q=97 数据集调整的 0.1-nat 体积守恒阈值。 - **`scripts/split_fat_seeds.py`** — 将按 tour 轨迹的伴随文件 `*_fat.json` 从精简种子记录中分离出来。 - **`scripts/log.py`** — 共享日志记录助手，将结构化事件发送到 `logs/pipeline.jsonl`（每个已提交的脚本都通过它路由）。 ## 数据格式 每颗种子的结果都被写为规范活动树（例如 `results/seeds/main/q97/n100_beta30/`）下紧挨着的两个 JSON 文件： - **`seedNNNN.json` (精简版)** — 规范记录：输入参数、BKZ 和 SD-BKZ 的最终 d(LN)、初始 Rankin 分布、终止原因、实际运行时间、SHA-256 输入。此文件定义了种子的身份，也是可复现性验证进行哈希比对的对象。云端部分的副本带有 `_cloud` 后缀；按 tour 的丰富版伴随文件带有 `_fat`。 - **`seedNNNN_fat.json` (伴随文件)** — 可选的按 tour 的轨迹和完整的 Gram-Schmidt 对数范数分布。当扫描在开启 `store_per_tour=True` 的情况下运行时，此类文件存在。缺失的丰富版文件绝不会使种子失效。 `scripts/archive/split_fat_seeds.py`（一次性脚本，为审计链保留）在旧版运行产生单个组合文件时执行分离。`analysis/_data.py` 中的下游分析代码兼容这两种布局。 ### 补充产出物 - **`results/profile_decomposition.json`** — 所有 33 组的完整头部/中间/尾部 Rankin 分布分解，被论文中的表 5 引用（该表仅展示了具有代表性的 n=50–70 子集）。 - **`results/paper_claims/`** — 按声明划分的证据账本：每个论文声明对应一个 JSON 文件，包含用于推导该声明的原始数字、种子数量和源扫描路径。交叉引用了论文中的每一个定量陈述。 - **`results/hash_verification.txt`** — n=100, β=20 时跨环境校验的 100 颗种子的 SHA-256 哈希（虚拟机 Ubuntu 24.04 / MPFR 4.2.1 vs AWS Batch Debian Bookworm / MPFR 4.2.0），全部 100 颗种子比特一致。 ## 可复现性 所有结果均是在三个独立的环境中使用完全相同的软件版本生成的： | Component | Version | Local VM (Intel 13900K) | AWS Batch | Secondary (AMD 9950X3D) | |---|---|---|---|---| | Python | 3.12.3 | Ubuntu 24.04 | Debian Bookworm | Ubuntu 24.04 | | fpylll | 0.6.4 | pip | pip (Docker) | pip (Docker) | | fplll | 5.5.0 | bundled in fpylll | bundled in fpylll | bundled in fpylll | | numpy | 2.4.4 | pip | pip (Docker) | pip (Docker) | | MPFR | 4.2.x | 4.2.1 | 4.2.0 | 4.2.1 | | cysignals | 1.12.6 | pip | pip (Docker) | pip (Docker) | **SHA-256 校验：** (n=100, β=20) 的所有 100 颗种子均在 Intel 和 AWS 环境中独立计算，并且在所有种子之间比特一致（见 `hash_verification.txt`）。在 q=3329 n=100 β=30 seed 11 上进行的跨架构冒烟测试表明，Intel 13900K 和 AMD 9950X3D 的输出比特一致（0/70 个按 tour 的轨迹差异，在 `bkz_final_dln` 和 `sdbkz_final_dln` 上精确匹配到小数点后 10 位），排除了论文 §8 中数值结果是由任何特定微架构引起的可能性。MPFR 4.2.0 和 4.2.1 的差异不会影响输出。 请参阅 `Dockerfile`（本地）和 `Dockerfile.cloud` (AWS) 以获取确切的构建规格。Python 依赖锁定在 `pyproject.toml` 中。 ## 致谢 作者感谢 Dylan Chambers Bourgeois 在 β = 40 扫描活动期间提供计算资源 (AMD Ryzen 9 9950X3D) 并进行跨架构可复现性校验。作者还感谢 Trill White (迪肯大学) 对基准测试结果提供的早期反馈和讨论。 ## 参考文献 关于基准设计和正在测试的算法的核心参考文献。完整的 15 篇参考文献列表见论文。 - Li, J. & Nguyen, P.Q. (2024). "A Complete Analysis of the BKZ Lattice Reduction Algorithm." *Journal of Cryptology*. IACR ePrint 2020/1237. *(定义了 Rankin 分布不动点和本基准测试所基于的 d(LN) 指标。)* - White, T. (2026). "Dynamic analysis of lattice basis reduction algorithms." *AMSI Summer Research Scholarsh 2025–26*, Deakin University. [Profile](https://srs.amsi.org.au/student-profile/trillion-white/) · [Report (PDF)](https://srs.amsi.org.au/wp-content/uploads/sites/92/2026/03/white_trill_srs-report.pdf) - [fplll](https://github.com/fplll/fplll) — 格算法库；本基准测试中的每个 BKZ 和 SD-BKZ 调用都通过 fplll 5.5.0 进行。 - [fpylll](https://github.com/fplll/fpylll) — fplll 的 Python 绑定 (0.6.4)。 - Micciancio, D. & Walter, M. (2016). "Practical, Predictable Lattice Basis Reduction." *EUROCRYPT 2016*, LNCS 9665, pp. 820–849. Full version: ePrint 2015/1123. - Hanrot, G., Pujol, X. & Stehlé, D. (2011). "Analyzing Blockwise Lattice Algorithms Using Dynamical Systems." *CRYPTO 2011*, LNCS 6841, pp. 447–464. - Chen, Y. & Nguyen, P.Q. (2011). "BKZ 2.0: Better Lattice Security Estimates." *ASIACRYPT 2011*, LNCS 7073, pp. 1–20. - Gama, N. & Nguyen, P.Q. (2008). "Predicting Lattice Reduction." *EUROCRYPT 2008*, LNCS 4965, pp. 31–51. - Schnorr, C.P. & Euchner, M. (1994). "Lattice basis reduction: improved practical algorithms and solving subset sum problems." *Mathematical Programming*, 66, pp. 181–199. - Bai, S., Stehlé, D. & Wen, W. (2018). "Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ." *ASIACRYPT 2018*, LNCS 11272, pp. 369–404. ePrint 2018/856. - Aono, Y., Wang, Y., Hayashi, T. & Takagi, T. (2016). "Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator." *EUROCRYPT 2016*, LNCS 9665, pp. 789–819.

标签：Docker, 可复现实验, 安全规则引擎, 安全防御评估, 密码学, 手动系统调用, 格归约, 算法基准测试, 请求拦截, 逆向工具