零知識證明中的比較

關於如何在零知識設置中進行範圍檢查已經有一個很好的調查。範圍檢查允許將變數限制在某個範圍內。比較看似相似，但實際上卻大不相同，因為它們允許為假。

例如，如果我們編寫這樣的範圍檢查：

0 <= n < c

我們可以確定，如果n不在給定範圍內，驗證將永遠不會成功。但是，如果我們有類似的東西

if 0 <= n < c then x else y

那麼無論是否n在給定範圍內，驗證都應該成功（前提是證明者誠實地完成了工作）。

在其他情況下也會出現類似的問題，例如n /= 0. n要求不等於是微不足道的0：

n * inv n = 1

（因為 only0沒有逆）但是為了編譯

if n /= 0 then x else y

我們需要利用非確定性並引入一個輔助變數。

0 <= n < c所以我的問題是：當它不是一個約束，而是一個我可以在 if 語句中用作條件的正則表達式時，如何編譯？

（這個答案假設一個支持一般算術約束的證明系統，例如 R1CS，在有限域上 $ \mathbb{F}_p $ . 它可以適應其他設置，但這可能很重要。）

考慮一個比較 $ 0 \leq n < c $ 在 $ \mathbb{F}_p $ 有否定 $ c \leq n < p $ . 所以一個約束系統 $ b = (0 \leq n < c) $ 本質上可以

$ \hspace{1em}b: \text{boolean}. \text{ if } b \text{ then assert } 0 \leq n < c. \text{ if not } b \text{ then assert } c \leq n < p $ .

如何使斷言以條件為條件可能並不明顯 $ b $ 或開 $ \text{not } b $ ，但有一個技巧。假設我們使用Zcash 協議規範的附錄 A.3.2.2 中的方法進行斷言，因此我們正在檢查的數字實際上是以位表示形式給出的。然後，對於普通範圍檢查，需要有一個額外的約束 $ n = \sum\limits_{i=0}^{k-1} 2^i n_i $ .

相反，選擇兩個整數 $ x $ 和 $ y $ , 用位表示 $ x = \sum\limits_{i=0}^{k-1} 2^i x_i $ 和 $ y = \sum\limits_{i=0}^{k’-1} 2^i y_i $ . 無條件檢查 $ 0 \leq \langle x_{k-1} \cdots x_0 \rangle < c $ 和 $ c \leq \langle y_{k’-1} \cdots y_0 \rangle < p $ . 最後斷言：

• $ \left(n - \sum\limits_{i=0}^{k-1} 2^i x_i\right) \times b = 0 $
• $ \left(n - \sum\limits_{i=0}^{k’-1} 2^i y_i\right) \times (1-b) = 0 $

這裡的第一個約束斷言 $ b = 0 $ 或者 $ n = x $ ，換句話說（鑑於 $ b $ 被限制為布爾值） $ (b = 1) \Rightarrow (n = x) $ . 第二個斷言要麼 $ b = 1 $ 或者 $ n = y $ ， 換句話說 $ (b = 0) \Rightarrow (n = y) $ . 所以我們可以推斷 $ (b = 1) \Rightarrow (0 \leq n < c) $ 和 $ (b = 0) \Rightarrow (c \leq n < p) $ ， 按要求。之一 $ x $ 和 $ y $ 不會受到約束，所以我們只選擇它作為相應範圍檢查通過的東西。

請注意，需要注意正確實施範圍檢查，因為其中至少有一個 $ k $ 和 $ k’ $ 將接近長度 $ p $ ，但這與我認為你問的主要問題是正交的。對於附錄 A.3.2.2 中的方法應該沒問題，因為該方法支持任意長度的位表示。

可能有一種方法可以通過不進行兩個完整位分解來進一步優化它，但我現在沒有看到它。

引用自：https://crypto.stackexchange.com/questions/71640