ethresear.ch
This article identifies an algebraic exactness gap in deferred-quotient row equations within BN254/M31 wrappers and proposes a lightweight repair that restores integer semantics while maintaining superior performance over bit-decomposition baselines.
AI 生成摘要
本文指出 BN254/M31 封裝器中延遲商數行方程存在代數精確性漏洞，並提出一種輕量級修復方案，在恢復整數語義的同時，保持比位元分解基準更優異的性能表現。
在 $\mathbb{F}_r$ 上形式為 L = D + pQ 的延遲商數列（deferred-quotient row），其本身並非一個整數除法陳述。
如果 Q 未受限制，該行在外部域（outer field）中可能在代數上是無效的（vacuous）。
對於一個具體的 BN254/M31 封裝器家族，透過「商數範圍綁定 + 標準剩餘綁定 + 無折疊邊界（no-wrap bounds）」可恢復精確的逐行 $\mathbb{Z}$ 語義。
在受限的共享輸入 Halo2 比較中，修復後的結構在 RSS（常駐記憶體）上始終比顯式位元分解（bit-decomposition）基準更快且小得多。
核心表面是延遲商數列方程式：
L = D + pQ \quad \text{over } \mathbb{F}_r.
就其本身而言，該域方程式不是一個整數陳述。如果 p 在外部域中是可逆的且 Q 未受限制，證明者可以設定：
Q = p^{-1}(L-D)
並在 $\mathbb{F}_r$ 中滿足行關係，而無需建立 $\mathbb{Z}$ 上的歐幾里得除法語義。
本文探討了這種精確性差距，並針對一個具體的 BN254/M31 封裝器家族提出了一種輕量級的代數修復方案。
此處的聲明為：
延遲商數等式在外部域層級可能在代數上是無效的；
若要將 L = D + pQ 視為精確的整數恆等式，需要顯式的缺失前提；
對於一個具體的 BN254/M31 封裝器家族，這些前提可以透過輕量級的代數修復來強制執行。
基準測試聲明遵循相同的界限：
這是一個受限的實例化家族比較，
並非聲明在每個封裝器實現中都具有全域語義等價性。
為了使域等式提升為 $\mathbb{Z}$ 中的精確恆等式，本筆記要求：
商數範圍綁定，
標準剩餘綁定，
無折疊邊界。
在這些條件下，在 $\mathbb{F}_r$ 中滿足的行關係可提升為：
\widehat{L} = \widehat{D} + p\widehat{Q} \quad \text{in } \mathbb{Z},
且在指定的剩餘行（residue rows）上，剩餘/商數對成為唯一的歐幾里得餘數/商數。
因此，本手稿為一組具有單肢（one-limb）31/66 位元商數類別的具體 BN254 家族證明了受限模型逐行精確性定理。這是一個關於代數精確性的定理層級結果。後端轉錄提取（transcript extraction）、PCS 層級健全性、Fiat-Shamir 閉包以及封裝器層級的等價性是獨立的問題，不在本筆記的討論範圍內。
在高層次上，該修復為延遲商數列增加了三項內容：
商數綁定。 商數見證被強制進入預期的較小標準類別，因此通用的外部域見證 Q = p^{-1}(L-D) 不再被允許。
標準剩餘綁定。 在指定的剩餘行上，剩餘被綁定到其標準代表，因此該行不再與同一同餘類別的任意域層級別名相容。
無折疊控制。 家族範圍的無折疊邊界確保一旦兩側提升為整數，滿足的域等式將被迫成為精確的整數恆等式，而非折疊後的同餘式。
具體而言，基準測試的修復結構使用重度查找（lookup-heavy）模式而非完整的顯式位元分解來綁定商數單元和剩餘樣式單元。在目前的實例化中，商數側被拆分為受查找限制的小區塊，而非寬泛的布林分解；剩餘側則將 31 位元布林樣式綁定替換為少量的表查找加上一個非等式樣式閘（例如 (x-p)\nu_x = 1）；隨後的無折疊審計證明了整數提升的合理性。這也是為什麼將其與 A_secure 基準進行比較具有意義的主要原因。
在手稿草案完成後，我運行了一個後續的 Halo2 基準測試包，比較了：
A_secure：顯式位元分解基準，
B_note：代數修復結構。
兩個分支均通過相同的 Halo2 證明路徑、相同的轉錄家族、相同的固定 k 合約以及相同的共享輸入配置文件。
對於面向等價性的重複運行（k_\mathrm{run}=17），我測量了：
\mathrm{scale}=1, 4, 8, 16, 32,
包含邊界（boundary）與標準（standard）模式，
\mathrm{repeats}=3。
在這些測試點中：
B_note 的證明時間比例保持在 0.821 到 0.884 之間，
B_note 的驗證時間比例保持在 0.631 到 0.716 之間，
B_note 的 RSS 保持在 A_secure 的約 0.285 到 0.286 之間。
因此，在目前的固定 k、共享輸入基準體系中，B_note 顯示出相當一致的證明時間和記憶體優勢。
我還檢查了目前的公共測試框架首次停止適配 k = 17 的位置。
對於此基準測試合約：
\mathrm{scale}=4519 仍可適配 k_\min=17，
\mathrm{scale}=4520 是第一個強制使用 k_\min=18 的點。
這是目前測試框架的一個屬性。
然後我在以下條件下運行了首次跳躍後的重複驗證：
\mathrm{scale}=4520,
k_\mathrm{run}=18,
\mathrm{input_profile}=\mathrm{boundary},
\mathrm{repeats}=3。
結果如下：
A_secure 證明時間 ~32.37 s，
B_note 證明時間 ~26.71 s，
B/A 證明比例 ~0.825，
A RSS ~6.30 GB，
B RSS ~1.79 GB，
B/A RSS ~0.285。
因此，至少對於這次最小重複跳躍後檢查，優勢在首次 k 跳躍之後依然存在。
手稿 PDF：https://github.com/junbyjun1238/zk2-bench-b1-lite/releases/download/v0.1.0/deferred-quotient-vacuity-in-bn254-wrappers-a-repair-note-on-algebraic-exactness.pdf [blocked]
公共基準測試包：https://github.com/junbyjun1238/zk2-bench-b1-lite/tree/v0.1.0/post_manuscript_fullbench [blocked]
發佈快照：https://github.com/junbyjun1238/zk2-bench-b1-lite/releases/tag/v0.1.0 [blocked]
Zenodo 存檔 (DOI)：https://doi.org/10.5281/zenodo.18910795 [blocked]
1 則貼文 - 1 位參與者 [閱讀完整主題](https://ethresear.ch/t/when-l-d-pq-is-not-enough-exactness-repair-for-bn254-wrappers/24313)