przchojecki/rs-mca

# 平滑 Reed-Solomon 域的 Proximity Prize 本代码库是一个处于研究阶段的工作包，旨在解决 [Proximity Prize 项目](https://proximityprize.org/) 中提出的关于平滑域 Reed-Solomon **互相关一致性 (MCA)** 和邻近列表的问题。 请参阅相关的 [IACR ePrint 论文](https://eprint.iacr.org/2026/680.pdf)。 其核心理念很简单： 本代码库面向那些希望帮助将修正后的理论转化为证明、反例、参数证书，并最终转化为协议级声明的研究人员和 AI 智能体。 ## 代码库内容 核心代码库由四篇论文和两个指南文件组成。.tex 版本位于 tex 文件夹中，.pdf 位于根文件夹中，用于启发式探索的 Python 脚本位于 scripts 文件夹中。 | 文件 | 简称 | 作用 | |---|---|---| | `RS_disproof_v3.tex` | **论文 A：无松弛阻碍** | 反驳了针对平滑乘法 RS 域“直至容量”的无松弛、基于支撑集的线 MCA 解读。提供了显式的下界机制和部署域上的阻碍。 | | `slackMCA_v3.tex` | **论文 B：松弛 / 商 / 熵理论** | 主理论论文。构建了修正后的预留框架：定位子纤维、生成域熵、商核、松弛坏斜率微积分、失败阶梯、商下限，以及最终的局部极限猜想。 | | `cs25_cap_v4.tex` | **论文 D：通用上限** | 提取并强化了上限结果：在引入列表转一致性的转换条件下，为 MCA 挑战阈值给出了一个域大小通用的天花板。 | | `snarks_v4.tex` | **论文 C：SNARK 账本** | 将修正后的理论转化为面向协议的证书：域分离账本、域上列表预算、MCA/线解码假设、维度规范以及回退模式。 | | `README.md` | 代码库概述 | 解释了各篇论文的作用、它们之间的依赖关系，以及该项目试图证明的内容。 | | `AGENTS.md` | 研究智能体指南 | 为 AI 智能体和新贡献者提供了一份按优先级排列的证明目标、玩具案例、脚本列表以及“请勿混淆”的规则。 | 论文的字母顺序遵循内部蓝图：A = 无松弛，B = 松弛理论，C = SNARK 账本，D = 通用上限。逻辑阅读顺序通常为 **A → B → D → C**。 ## 我们试图解决的问题 设 `C = RS[F, D, k]`，其中 `D` 是一个平滑乘法域，通常是阶数为 2 的幂 `n` 的子群或乘法陪集，且 `rho = k/n` 是以下之一 ``` rho in {1/2, 1/4, 1/8, 1/16}. ``` Proximity Prize 机制要求在接近容量时具备敏锐的阈值，特别是对于目标错误 ``` epsilon* = 2^-128, k <= 2^40, |F| < 2^256. ``` 这里有两个相互关联的阈值问题。 1. **MCA / 相关一致性阈值。** 确定半径 `delta` 可以多接近 `1 - rho`，同时保持 MCA 错误极小。 2. **交织列表阈值。** 确定半径 `delta` 可以多接近 `1 - rho`，同时保证相关的交织列表大小至多为挑战域的极小部分。 这些问题与协议息息相关，因为许多邻近性/SNARK 归约在形式上具有如下的可靠性项 ``` MCA_error(C, delta) + |interleaved_list(C, delta)| / |challenge field| + query_error. ``` 除非将其与协议使用的 MCA、CA、线解码或曲线 MCA 的精确量联系起来，否则仅凭列表定理是不够的。 ## 当前图景 曾经被寄予厚望的旧声明大致如下： 修正后的图景是： 必须区分的账本包括： 1. **生成域熵。** 列表/定位子熵的分母是由域和接收字生成的域，而不是自动默认的大型扩展挑战域。 2. **商核阻碍。** 平滑域具有商纤维。如果 `k` 和 `n` 与较大的商尺度对齐，则可能出现大型列表或坏斜率。 3. **定位子纤维列表大小。** 基础码的定位子纤维必须先被限定，然后才能用于协议的列表预算中。 4. **交织列表大小。** 协议通常会消耗 `|Lambda(Int(C, mu), delta)|`，而不仅仅是基础码的列表大小。 5. **挑战域除法。** 列表项除以的是验证者从中抽取相关挑战的域。请勿暗中将其替换为更大或更小的域。 6. **MCA / CA / 线解码 / 曲线 MCA。** 这些概念相互关联，但在没有定理支持的情况下不可互换。 7. **已知的失败阶梯和通用上限。** 显式的下界或通用上限排除了某些差距。 ## 各论文如何相互契合 ``` Paper A: no-slack obstruction | v Paper B: slack / entropy / quotient-core theory |\ | \__ Paper D: universal cap via list-to-agreement conversion | v Paper C: SNARK/protocol ledger consuming B and D ``` ### 论文 A：无松弛阻碍 `RS_disproof_v3.tex` 是基础的下界论文。 它表明，对于平滑乘法 RS 域，无松弛、基于支撑集的线 MCA 版本的“直至容量”猜想是不成立的。其核心组织机制是**商定位子恒等式**：在平滑商子群中的受限和为如下形式的线产生了许多坏斜率 ``` x^(k+a) + z x^k. ``` 该论文给出了在常见平滑素域（如 BabyBear、KoalaBear、`3*2^30+1` 以及 Fermat 素数示例）上的显式结论。它在代码库中的作用是作为下界预言机：如果提出的定理与论文 A 的阻碍区间相矛盾，则该定理是错误的，或者遗漏了某个预留假设。 ### 论文 B：松弛 / 商 / 熵理论 `slackMCA_v3.tex` 是主理论论文。 它将阻碍机制推广为一种修正后的正/负理论。它区分了： - 生成域熵下限， - 商核列表阻碍， - 特征零刚性与有限域碰撞筛， - 精确的松弛坏斜率微积分， - 二进制下降与失败阶梯， - 切线与商周期 MCA 下限， - 残留线范式， - 关于列表解码和 MCA 的局部极限猜想。 论文 B 是大多数新数学内容应归属的地方。它包含了修正后的预留定理的定理/猜想形态：不是“直至容量”，而是“直至容量减去每一个显式下限”。 ### 论文 D：通用的域大小上限 `cs25_cap_v4.tex` 是一篇简短的上限论文。 它将定位子纤维下界与引入的 Crites--Stewart 列表转一致性转换相结合。在此引入的前提下，它在整个挑战域范围 `|F| < 2^256` 内，基于所述的平滑性/可分性假设，证明了 MCA 挑战的域大小通用上限： ``` delta*_C(2^-128) <= 1 - rho - 2^-9 for rho in {1/2, 1/4, 1/8}, delta*_C(2^-128) <= 1 - rho - 2^-10 for rho = 1/16, ``` 它均匀地给出 `> 2^-86` 的错误率，并在 `|F| >= 2n` 时改善至 `> 2^-42`。 对于最终的常数，论文 D 取代了论文 B 中较早的内部上限。论文 B 保留了其原生的商核上限，因为它解释了背后的机制；而论文 D 则拥有敏锐的域大小通用声明。 ### 论文 C：SNARK 账本 `snarks_v4.tex` 将修正后的理论转化为面向协议的预留证书。 其目的并非证明所有缺失的 MCA/列表定理。其目的是防止协议分析中混淆账本。特别是，它坚持要求区分以下内容： - 基础域 vs 生成域 vs 扩展挑战域， - 实现交织 vs 协议列表元数， - 基础码列表 vs 交织列表， - CA vs MCA vs 线解码 vs 曲线 MCA， - 定理支持模式 vs 猜想性激进模式 vs 阻碍审计模式。 论文 C 是连接理论与系统的桥梁。一旦缺失的局部极限和线/MCA 声明得到证明，论文 C 应当成为一个从码/域元组到可靠性证书的编译器。 ## 已证明、附条件与开放状态 一个粗略的状态图谱： | 主题 | 当前状态 | |---|---| | 无松弛平滑域 MCA 阻碍 | 已在论文 A 中证明。 | | 显式的部署域下界下限 | 已在论文 A/B 中针对所述机制证明。 | | 商核列表阻碍 | 已在论文 B 中证明。 | | 精确的松弛微积分与多种失败阶梯 | 已在论文 B 中证明。 | | 通用的域大小上限 | 依赖于引入的列表转一致性转换；论文 D 是权威参考。 | | 所有下限之上的生成域定位子局部极限 | 开放。主要的列表方正向定理目标。 | | 所有下限之上的修正 MCA / 残留线局部极限 | 开放。主要的 MCA 方正向定理目标。 | | 修正 MCA 的线解码形式化 | 开放。对协议很重要。 | | 扩展线 MCA 传递 | 开放：证明一个清晰的提升或寻找反例。 | | 接近容量时敏锐的交织列表常数 | 开放。对协议可靠性预算很重要。 | | 协议级 FRI/WHIR 账本重写 | 开放的工程/证明任务。 | | 证书扫描器 | 待实现。 | ## 脚本层 第一个启发式脚本是 `scripts/run_frontier.py`，这是一个**实验性 (EXPERIMENTAL)** 的论文 B 前沿扫描器。对于命令行传入的每个素数 `p`（预期满足 `32 | p-1`），它构建 `F_p` 的 32 阶乘法子群，在固定的 `l = 18` 下使用中间相遇子集枚举，并记录由 `l` 个子群元素所实现的所有初等对称指纹 `(e1, e2)`。它的覆盖线测量了这个受限的商定位子映射在 `F_p^2` 中击中的比例，并将结果追加到 `frontier_results.txt` 中；完全覆盖是关于商/受限和前沿行为的证据，但这本身并不构成证明。该脚本目前需要 `numpy` 和 `sympy`。 更广泛的预期脚本层包括： ``` scripts/ run_frontier.py # EXPERIMENTAL psi_2 restricted-subset frontier scan entropy_margin.py # generated-field entropy reserve quotient_profile.py # active quotient scales at actual (n, k, a) restricted_sum_dp.py # restricted-sum / DSH verification certificates locator_fiber_scan.py # small-field locator-fiber experiments mca_slope_scan.py # small-field bad-slope / residue-line experiments interleaved_budget.py # base/interleaved list-to-field soundness budget certificate_emit.py # JSON + TeX certificate tables for Paper C ``` 一个有用的脚本应该同时输出人类可读的内容和机器可检查的证书。手工计算的表格最终应被脚本的输出所取代。 ## 约定 在添加结果时请使用以下约定： - `rho = k/n` 为码率。 - `delta = 1 - rho - eta` 为邻近半径。 - `eta` 为距离容量的预留/间隙。 - `q_gen` 为由域/接收字数据生成的域。 - `q_line` 为抽取线或 CA/MCA 挑战的来源域。 - `q_chal` 为验证者挑战域；它可能等于也可能不等于 `q_line`。 - `mu` 为协议列表元数。 - `nu` 为实现交织度。 - `Qprof` 为商剖面阻碍账本。 如有疑问，请保持域的分离。大多数关于接近容量的错误声明都源于将相同的域大小信用分配给了两个不同的账本。 ## 引用与发布规范 在编辑论文时： - 引用相关结果时请使用定理/命题编号，而不仅仅是“相关论文证明了”。 - 将每个结果标记为已证明、附条件、猜想性、实验性或仅供审计。 - 在引入的转换经过完全审计之前，请勿将通用上限作为无条件结果引用。 - 请勿从论文 D 的上限中声明存在单错误（error-one）结果；论文 D 对阈值进行了上限限制并给出了一个较小的经认证的失败概率，但频带内的单错误问题仍然悬而未决。 - 保留论文 D 作为最终通用上限常数的规范参考。 - 保留论文 C 作为协议账本和域核算规则的规范参考。 ## 项目目标 本项目的目标是以对证明系统有用的方式，解决平滑域 Reed-Solomon 码的 Proximity Prize MCA/列表问题。 理想情况下的正向结果将是基于定理的预留证书：给定域、码率、域大小、交织度和协议归约，本代码库可以认证一个接近容量的半径和可靠性预算。 负面的结果同样有价值：每一个阻碍都会成为一个新的下限、对协议设计者的警告，或者成为转向折叠/子空间设计码、随机/穿孔域或域破碎构造的理由。 无论结果如何，我们的目标都是用精确的、可检查的数学理论来取代那些缺乏依据的“接近容量的 RS 应该可行”的传言。 当前的工作是使用 GPT-5.5 Pro 和 Claude Fable 5 完成的，仍需经过适当的修订。欢迎人类专家提供意见。

标签：LaTeX, Python, 学术研究, 密码学研究, 无后门, 纠错码, 逆向工具, 零知识证明