QUO:一文讀懂微軟開發的Nova系統：如何成為零知識證明的新篇章？

作者：Huobi Ventures 資深研究員謝錦斌

零知識證明是密碼學中的一種重要技術，它允許一個人向另一個人證明一個陳述是真實的，而無需透露任何其他信息。這種技術在許多領域都有廣泛的應用，包括身份驗證、區塊鏈和安全計算等。Nova是微軟開發的一種新型零知識證明系統，它使用了一種名為松弛的秩一約束系統（Relaxed Rank-1 Constraint Systems，Relaxed R1CS）的技術，以提高證明的效率和靈活性。最后一章節對源碼進行詳細解讀。

Nova的主要優點在于其使用的松弛的R1CS技術。R1CS是一種用于構建零知識證明的系統，它可以用于證明一個人知道滿足一組多項式等式的解，而不必透露任何關于解的信息。然而，傳統的R1CS系統需要在證明過程中使用大量的隨機性，這會導致證明的生成和驗證過程非常復雜和耗時。Nova通過使用松弛的R1CS來解決這個問題，它允許在證明中使用更少的隨機性，從而大大提高了證明的效率。

Nova還具有其他一些優點。例如，它支持增量計算，這意味著可以逐步計算復雜的函數，而不必一次性計算整個函數。這在處理大規模數據或進行復雜計算時非常有用。此外，Nova還支持多項式計算，這使得它可以處理更復雜的證明任務。

盡管Nova具有許多優點，但它也有一些缺點。首先，由于Nova使用的是松弛的R1CS，因此它的證明可能不如傳統的R1CS系統那么強大。這是因為松弛的R1CS允許在證明中使用更少的隨機性，這可能會降低證明的安全性。然而，Nova的開發者已經采取了一些措施來解決這個問題，例如使用更強大的密碼學算法和更復雜的證明策略。

其次，Nova的實現相對復雜，這可能會增加使用和維護的難度。Nova使用了許多高級的密碼學技術，如多項式計算、群操作和隨機預言機等，這需要深入理解這些技術才能有效地使用和修改Nova。

Nova在零知識證明領域中占據了重要的地位。它的出現，為零知識證明的發展開辟了新的道路。Nova采用的松弛的R1CS技術，使得證明的生成和驗證過程更加高效，這對于大規模的零知識證明應用至關重要。此外，Nova還支持增量計算和多項式計算，這使得它可以處理更復雜的證明任務，進一步擴大了零知識證明的應用范圍。

https://github.com/microsoft/Nova

在 src/ 目錄下，有以下幾個重要的子目錄：

bellperson/：這個目錄可能包含了關于 Bellman-Ford 算法的代碼。

gadgets/：這個目錄可能包含了一些用于構建 zk-SNARK 證明的工具。

provider/：這個目錄可能包含了一些提供者的代碼，如 keccak.rs 可能是實現 Keccak 哈希函數的代碼。

spartan/：這個目錄可能包含了關于 Spartan 協議的代碼。

traits/：這個目錄可能包含了一些 Rust traits，用于定義一些公共的行為。

src/bellperson/mod.rs 文件的內容：

這個模塊主要用于生成 R1CS（Rank-1 Constraint Systems，一種用于 zk-SNARKs 的約束系統）。

它包含了三個子模塊：

r1cs: 這個模塊可能包含了關于 R1CS 的代碼。

shape_cs: 這個模塊可能包含了關于形狀約束系統的代碼。

solver: 這個模塊可能包含了關于解決約束系統的代碼。

在測試部分，它定義了一個函數 synthesize_alloc_bit，這個函數接受一個約束系統，然后添加一些約束來檢查輸入的兩個比特是否確實是比特。然后，它定義了一個函數 test_alloc_bit_with，這個函數首先創建一個形狀

src/bellperson/r1cs.rs 文件的內容：

這個文件主要定義了兩個 trait：`NovaWitness` 和 `NovaShape`，它們分別提供了從實現者獲取 `R1CSInstance` 和 `R1CSWitness`，以及獲取 `R1CSShape` 和 `CommitmentKey` 的方法。

- `NovaWitness` trait 有一個方法 `r1cs_instance_and_witness`，它接受一個 `R1CSShape` 和一個 `CommitmentKey`，然后返回一個 `R1CSInstance` 和一個 `R1CSWitness`。這個 trait 為 `SatisfyingAssignment` 結構體實現，這意味著任何 `SatisfyingAssignment` 都可以使用這個方法來獲取一個 `R1CSInstance` 和一個 `R1CSWitness`。

- `NovaShape` trait 有一個方法 `r1cs_shape`，它返回一個 `R1CSShape` 和一個 `CommitmentKey`。這個 trait 為 `ShapeCS` 結構體實現，這意味著任何 `ShapeCS` 都可以使用這個方法來獲取一個 `R1CSShape` 和一個 `CommitmentKey`。

這個文件還定義了一個函數 `add_constraint`，它接受一個約束系統和三個線性組合，然后在約束系統中添加一個新的約束。這個函數被 `NovaShape` 的實現者在生成 `R1CSShape` 時使用。

總的來說，這個文件的主要作用是提供了一種方式，使得可以從一個滿足特定條件的系統（如 `SatisfyingAssignment` 或 `ShapeCS`）中生成 R1CS 的實例、證人、形狀和承諾密鑰。

src/bellperson/shape_cs.rs

這個文件定義了一個名為 `ShapeCS` 的結構體，它實現了 `ConstraintSystem` trait。`ShapeCS` 是用于創建 R1CS 形狀的約束系統。

`ShapeCS` 結構體包含以下幾個字段：

- `named_objects`: 這是一個映射，用于存儲與路徑關聯的對象。

- `current_namespace`: 這是一個字符串向量，用于存儲當前的命名空間。

- `constraints`: 這是一個向量，用于存儲所有添加到 `ShapeCS` 的約束。

- `inputs`: 這是一個字符串向量，用于存儲所有的輸入。

- `aux`: 這是一個字符串向量，用于存儲所有的輔助輸入。

`ShapeCS` 結構體實現了 `ConstraintSystem` trait，這意味著它提供了以下幾個方法：

- `alloc`: 這個方法用于分配一個新的變量。

- `alloc_input`: 這個方法用于分配一個新的輸入變量。

- `enforce`: 這個方法用于添加一個新的約束。

- `push_namespace`: 這個方法用于推入一個新的命名空間。

- `pop_namespace`: 這個方法用于彈出當前的命名空間。

某釣魚地址已將28.15枚ETH轉入Tornado Cash:金色財經報道，據CertiK監測，被Etherscan標注為Fake_Phishing156248 已將28.15枚ETH（約51.8K美元）經由EOA地址（0xee122 ）轉入Tornado Cash。[2023/5/24 15:23:09]

- `get_root`: 這個方法用于獲取根約束系統。

這個文件還定義了一些輔助函數，如 `proc_lc` 和 `compute_path`，它們分別用于處理線性組合和計算路徑。

總的來說，這個文件的主要作用是提供了一種方式，使得可以從一個滿足特定條件的系統（如 `ShapeCS`）中生成 R1CS 的形狀。

src/bellperson/solver.rs

這個文件定義了一個名為 `SatisfyingAssignment` 的結構體，它實現了 `ConstraintSystem` trait。`SatisfyingAssignment` 是用于創建 R1CS 實例和證人的約束系統。

`SatisfyingAssignment` 結構體包含以下幾個字段：

- `a_aux_density`, `b_input_density`, `b_aux_density`: 這些是 `DensityTracker` 類型的字段，用于跟蹤查詢的密度。

- `a`, `b`, `c`: 這些是向量，用于存儲 A、B、C 多項式的評估結果。

- `input_assignment`, `aux_assignment`: 這些是向量，用于存儲變量的賦值。

`SatisfyingAssignment` 結構體實現了 `ConstraintSystem` trait，這意味著它提供了以下幾個方法：

- `new`: 這個方法用于創建一個新的 `SatisfyingAssignment` 實例。

- `alloc`: 這個方法用于分配一個新的輔助變量。

- `push_namespace`, `pop_namespace`: 這些方法用于操作命名空間，但在這個上下文中并沒有實際的操作。

- `is_extensible`, `extend`: 這些方法用于擴展約束系統。

總的來說，這個文件的主要作用是提供了一種方式，使得可以從一個滿足特定條件的系統（如 `SatisfyingAssignment`）中生成 R1CS 的實例和證人。

"src/circuit.rs"，它定義了 Nova 協議中的增強電路（Augmented Circuit）。這個電路包括一個步驟電路（Step Circuit）和 Nova 的非交互折疊方案中的驗證器電路。

文件中定義了以下幾個主要的結構體和方法：

- `NovaAugmentedCircuitParams`：這個結構體包含了電路的參數，包括 limb 寬度、limb 數量和一個布爾值表示這是否是主電路。

- `NovaAugmentedCircuitInputs`：這個結構體包含了電路的輸入，包括參數、i、z0、zi、U、u 和 T。

- `NovaAugmentedCircuit`：這個結構體是 Nova 增強電路的主要定義，它包含了電路的參數、只讀常量、輸入和步驟電路。它還定義了一些方法，如 `alloc_witness`（分配證人）、`synthesize_base_case`（合成基礎案例）和 `synthesize_non_base_case`（合成非基礎案例）。

- `synthesize` 方法：這是 Nova 增強電路的主要合成方法，它首先分配所有的證人，然后根據是否是基礎案例來合成電路，并最后輸出計算的哈希值和 u.X。

這個文件還包含了一些測試代碼，用于測試遞歸電路的功能。

總的來說，這個文件的主要作用是定義了 Nova 協議中的增強電路，這個電路是 Nova 協議的核心部分，它包括了一個步驟電路和一個驗證器電路，并提供了一種方式來合成這個電路。

"src/constants.rs"，它定義了一些常量，這些常量在整個項目中被廣泛使用。以下是這些常量的含義：

- `NUM_CHALLENGE_BITS`: 這個常量定義了挑戰的位數，值為 128。挑戰通常是由證明者生成的隨機數，用于 zk-SNARK 證明過程中的交互步驟。

- `NUM_HASH_BITS`: 這個常量定義了哈希的位數，值為 250。哈希函數是一種可以將任意長度的輸入數據映射到固定長度輸出的函數，這里的輸出長度就是 250 位。

- `BN_LIMB_WIDTH`: 這個常量定義了大數（Big Number）的肢寬，值為 64。在計算機科學中，大數是那些超出了標準數據類型能夠表示的范圍的數，它們通常被分解為多個“肢”進行存儲和操作。

- `BN_N_LIMBS`: 這個常量定義了大數的肢數，值為 4。這意味著每個大數都被分解為 4 個肢進行存儲和操作。

- `NUM_FE_WITHOUT_IO_FOR_CRHF`: 這個常量定義了對于沖突抗性哈希函數（CRHF），不包括輸入/輸出的字段元素（FE）的數量，值為 17。

- `NUM_FE_FOR_RO`: 這個常量定義了對于隨機預言機（RO），字段元素（FE）的數量，值為 24。

這些常量在 Nova 協議的實現中起著關鍵的作用，它們定義了一些重要的參數，如挑戰的位數、哈希的位數、大數的肢寬和肢數等。

"src/errors.rs"，它定義了 Nova 庫可能返回的錯誤類型。這些錯誤類型被封裝在一個名為 `NovaError` 的枚舉中。以下是這些錯誤類型的含義：

- `InvalidIndex`: 如果提供的行或列在 (row, col, val) 元組中超出范圍，將返回此錯誤。

- `OddInputLength`: 如果提供的輸入長度不是偶數，將返回此錯誤。

- `InvalidInputLength`: 如果提供的輸入長度不正確，將返回此錯誤。

- `InvalidWitnessLength`: 如果提供的證人長度不正確，將返回此錯誤。

- `UnSat`: 如果提供的證人不滿足給定的形狀和實例，將返回此錯誤。

- `DecompressionError`: 如果無法解壓提供的壓縮承諾，將返回此錯誤。

- `ProofVerifyError`: 如果證明驗證失敗，將返回此錯誤。

- `InvalidNumSteps`: 如果提供的步驟數為零，將返回此錯誤。

- `InvalidIPA`: 如果提供了無效的內積參數，將返回此錯誤。

- `InvalidSumcheckProof`: 如果提供了無效的求和檢查證明，將返回此錯誤。

- `InvalidInitialInputLength`: 如果增量計算的初始輸入與先前聲明的元數不符，將返回此錯誤。

安全團隊：Shonen Junk項目Discord服務器已被入侵:金色財經消息，安全團隊CertiK表示，Shonen Junk項目Discord服務器已被入侵。目前聊天已被鎖定。請社區用戶不要點擊、鑄造或批準任何交易。[2022/9/27 22:33:03]

- `InvalidStepOutputLength`: 如果步驟執行產生的輸出長度與先前聲明的元數不符，將返回此錯誤。

- `InternalTranscriptError`: 如果轉錄引擎遇到輪數溢出，將返回此錯誤。

- `InvalidMultisetProof`: 如果多集檢查失敗，將返回此錯誤。

- `InvalidProductProof`: 如果產品證明檢查失敗，將返回此錯誤。

- `IncorrectWitness`: 如果與公開 IO 和使用的賦值的一致性失敗，將返回此錯誤。

這些錯誤類型覆蓋了 Nova 庫中可能遇到的各種問題，包括輸入錯誤、證明錯誤、內部錯誤等。當 Nova 庫的函數遇到問題時，它們會返回這些錯誤，以便調用者可以了解出了什么問題并采取相應的行動。

"ecc.rs"，它是 Rust 語言編寫的。這個文件主要包含了 Nova 框架中的橢圓曲線密碼學（ECC）相關的實現。

橢圓曲線密碼學（Elliptic Curve Cryptography，ECC）是一種公鑰加密技術，它的主要優點是在提供相同的安全性的情況下，可以使用更短的密鑰。這意味著 ECC 可以使用較小的計算資源和電力，這對于許多設備（特別是移動設備和嵌入式系統）來說是非常重要的。

在這個文件中，你會看到一些 Rust 結構體（structs）和實現（impls）的定義，這些都是為了實現 ECC 的功能。例如，你會看到 `struct EccGadget`，這是一個 ECC 的主要實現，它包含了一些字段，如 `value` 和 `pb_variable`，這些字段用于存儲 ECC 的狀態和相關的變量。

此外，你還會看到一些方法（functions）的定義，這些方法用于實現 ECC 的各種操作，如加密、解密等。例如，`fn encrypt` 是一個加密函數，它接受一個明文和一個公鑰，然后返回一個加密的密文。

總的來說，這個文件是 Nova 框架中實現 ECC 功能的關鍵部分。

"src/gadgets/mod.rs"，它是 Nova 框架中的一個模塊，主要用于實現各種對 Nova 和使用 Nova 構建的應用程序必要的 "gadgets"。

在密碼學中，"gadget" 是一個通用術語，用于描述實現特定功能的代碼塊。在 zk-SNARKs（零知識簡潔非交互式論證）中，gadget 通常指的是實現特定算法或協議的證明系統。

在這個文件中，你會看到以下幾個子模塊：

- `ecc`: 這個模塊可能包含了關于橢圓曲線密碼學（Elliptic Curve Cryptography）的 gadget。

- `nonnative`: 這個模塊可能包含了一些非本地字段的 gadget。

- `r1cs`: 這個模塊可能包含了一些 R1CS（Rank-1 Constraint Systems）的 gadget。

- `utils`: 這個模塊可能包含了一些實用工具函數或者類。

這些子模塊一起提供了 Nova 框架所需的各種功能。

"bignat.rs"，它是 Nova 項目中的一部分，主要用于實現大整數（BigNat）的操作。

在計算機科學中，大整數（或稱為任意精度整數）是可以表示并操作超過常規整數類型（如 int 或 long）能夠表示的范圍的整數。這在許多領域都非常有用，包括密碼學、計算機圖形學、大數計算等。

讓我們來詳細看一下這個文件中的一些主要部分：

1. `use super::super::gadgets::GadgetCaller;`：這行代碼導入了 GadgetCaller，這是一個用于調用其他 gadget 的 trait。

2. `pub struct BigNatGadget;`：這行代碼定義了一個名為 BigNatGadget 的結構體。在 Rust 中，結構體是用來創建復雜的數據類型的。

3. `impl GadgetCaller for BigNatGadget`：這是對 BigNatGadget 結構體的實現，它實現了 GadgetCaller trait。這意味著 BigNatGadget 必須提供 GadgetCaller trait 所需的所有方法的實現。

4. 在這個實現中，我們可以看到一些方法，如 `add`, `sub`, `mul`, `div`, `rem` 等，這些都是大整數運算的基本操作。

5. `pub fn from(&self, val: u64) -> Self`：這個方法用于從一個 u64 類型的值創建一個 BigNatGadget。

6. `pub fn to_u64(&self) -> u64`：這個方法用于將 BigNatGadget 轉換為一個 u64 類型的值。

7. `pub fn eq(&self, other: &Self) -> bool`：這個方法用于判斷兩個 BigNatGadget 是否相等。

總的來說，這個文件提供了一個用于處理大整數的工具，包括創建大整數、將大整數轉換為其他類型的值，以及執行大整數的基本運算。

"mod.rs"，它位于 "src/gadgets/nonnative/" 目錄下。這個文件主要用于實現非本地字段的算術運算。

在密碼學中，非本地字段通常指的是那些不直接由硬件支持的字段。例如，某些密碼學算法可能需要在大于 64 位的字段上進行運算，但是大多數現代計算機硬件只直接支持最多 64 位的運算。在這種情況下，我們就需要使用非本地字段的算術運算。

在這個文件中，你會看到以下幾個主要部分：

1. `OptionExt` trait：這個 trait 為 `Option` 類型添加了兩個方法，`grab` 和 `grab_mut`，它們嘗試獲取 `Option` 中的值，如果 `Option` 是 `None`，則返回一個錯誤。

2. `BitAccess` trait：這個 trait 提供了一個方法 `get_bit`，它接受一個索引 `i`，然后返回該索引位置的位是否為 `1`。

3. `impl BitAccess for Scalar`：這是對 `Scalar` 類型的 `BitAccess` trait 的實現，`Scalar` 是一個代表素數字段的類型。

4. `pub mod bignat;` 和 `pub mod util;`：這兩行代碼導入了 `bignat` 和 `util` 兩個子模塊，它們可能包含了一些實現非本地字段算術運算的函數或者類。

Fantom基金會發起一項減少網絡上驗證者質押獎勵的提案:金色財經報道，Fantom 基金會提出了一項提案，以減少網絡上驗證者的質押獎勵。這個新的 Fantom 提案主張降低 13% 的質押獎勵率，以符合市場平均水平。該提案的投票于周一開始，一直持續到 2023 年 2 月 4 日。如果民意調查達到 67% 的法定人數，投票可能會在 8 月 15 日結束。截至發稿時，法定人數目前僅為 1.8%。投票頁面的數據顯示，99% 的選民支持網絡上 6% 的質押獎勵率。如果這個獎勵率成為投票的贏家，那么 Fantom 發放將再持續四年。（the block）[2022/8/10 12:14:09]

總的來說，這個文件提供了一種在非本地字段上進行算術運算的方法，這對于實現某些密碼學算法是非常重要的。

"util.rs"，它位于 "src/gadgets/nonnative/" 目錄下。這個文件主要用于實現一些在非本地字段上進行運算的實用函數。

以下是這個文件中的一些主要部分：

1. `Bit` 結構體：這個結構體表示一個位，包含一個線性組合和一個值，這個值在證人時間被填充。

2. `Bitvector` 結構體：這個結構體表示一個位向量，包含一個線性組合的向量、一個值的向量和一個分配的位向量。

3. `Num` 結構體：這個結構體表示一個數，包含一個線性組合和一個值。

4. `Bit` 結構體的 `alloc` 方法：這個方法在約束系統中分配一個只能是布爾值的變量。

5. `Num` 結構體的 `fits_in_bits` 方法：這個方法檢查一個數是否可以用給定數量的位表示。

6. `Num` 結構體的 `is_equal` 方法：這個方法檢查一個數是否等于一個位向量表示的自然數。

7. `Num` 結構體的 `decompose` 方法：這個方法將一個數分解為一個位向量。

8. `Num` 結構體的 `as_allocated_num` 方法：這個方法將一個數轉換為一個分配的數。

9. `f_to_nat` 函數：這個函數將一個字段元素轉換為一個自然數。

10. `nat_to_f` 函數：這個函數將一個自然數轉換為一個字段元素。

總的來說，這個文件提供了一些實用函數，這些函數可以在非本地字段上進行各種運算，如分配變量、檢查一個數是否可以用給定數量的位表示、將一個數分解為一個位向量等。

"r1cs.rs"，它位于 "src/gadgets/" 目錄下。這個文件主要用于實現 Rank-1 Constraint Systems (R1CS) 的各種 gadget。

R1CS 是一種用于描述算法或協議的證明系統，它是許多零知識證明系統的基礎，包括 zk-SNARKs。

1. `AllocatedR1CSInstance` 結構體：這個結構體表示一個已分配的 R1CS 實例，包含一個點 `W` 和兩個數 `X0` 和 `X1`。

2. `AllocatedR1CSInstance::alloc` 方法：這個方法用于在約束系統中分配一個 R1CS 實例。

3. `AllocatedR1CSInstance::absorb_in_ro` 方法：這個方法用于將 R1CS 實例吸收到隨機預言機 (RO) 中。

4. `AllocatedRelaxedR1CSInstance` 結構體：這個結構體表示一個已分配的松弛 R1CS 實例，包含兩個點 `W` 和 `E`，一個數 `u`，和兩個大整數 `X0` 和 `X1`。

5. `AllocatedRelaxedR1CSInstance::alloc` 方法：這個方法用于在約束系統中分配一個松弛 R1CS 實例。

6. `AllocatedRelaxedR1CSInstance::default` 方法：這個方法用于在約束系統中分配一個默認的松弛 R1CS 實例。

7. `AllocatedRelaxedR1CSInstance::from_r1cs_instance` 方法：這個方法用于將一個 R1CS 實例轉換為一個松弛 R1CS 實例。

8. `AllocatedRelaxedR1CSInstance::absorb_in_ro` 方法：這個方法用于將松弛 R1CS 實例吸收到隨機預言機 (RO) 中。

9. `AllocatedRelaxedR1CSInstance::fold_with_r1cs` 方法：這個方法用于將松弛 R1CS 實例與一個 R1CS 實例折疊，并返回結果。

10. `AllocatedRelaxedR1CSInstance::conditionally_select` 方法：這個方法用于根據一個條件選擇兩個松弛 R1CS 實例中的一個。

總的來說，這個文件提供了一些用于處理 R1CS 的工具，包括創建 R1CS 實例、將 R1CS 實例轉換為松弛 R1CS 實例、將 R1CS 實例吸收到隨機預言機中、將松弛 R1CS 實例與一個 R1CS 實例折疊等。

這個文件名為 "utils.rs"，它位于 "src/gadgets/" 目錄下。這個文件主要用于實現一些低級別的工具函數，這些函數在構建更高級別的密碼學協議和算法時非常有用。

1. `le_bits_to_num` 函數：這個函數接受一個小端表示的位數組，然后返回對應的數值。

2. `alloc_zero` 和 `alloc_one` 函數：這兩個函數分別用于在約束系統中分配一個值為零和一個值為一的變量。

3. `alloc_scalar_as_base` 函數：這個函數用于在約束系統中分配一個標量作為基數。

4. `scalar_as_base` 函數：這個函數用于將一個標量解釋為基數。

5. `alloc_bignat_constant` 函數：這個函數用于在約束系統中分配一個大整數常量。

6. `alloc_num_equals` 函數：這個函數用于檢查兩個數是否相等，并返回一個位。

7. `conditionally_select` 函數：這個函數用于根據一個條件選擇兩個數中的一個。

8. `conditionally_select_vec` 函數：這個函數用于根據一個條件選擇兩個數數組中的一個。

9. `conditionally_select_bignat` 函數：這個函數用于根據一個條件選擇兩個大整數中的一個。

10. `conditionally_select2` 函數：這個函數用于根據一個條件選擇兩個數中的一個，這個條件是一個已分配的數。

11. `select_zero_or_num2` 和 `select_num_or_zero2` 函數：這兩個函數分別用于根據一個條件將一個數設置為零或者保持不變，這個條件是一個已分配的數。

12. `select_num_or_zero` 函數：這個函數用于根據一個條件將一個數設置為零或者保持不變，這個條件是一個布爾值。

STEPNNFT V2 NFT近24小時交易額增幅超4000%:金色財經消息，據opensea最新數據顯示，STEPNNFT V2 NFT近24小時交易額為1542.42ETH，24小時增幅4056.45%。近24小時交易額排名第三。[2022/7/18 2:19:39]

13. `select_one_or_num2` 和 `select_num_or_one` 函數：這兩個函數分別用于根據一個條件將一個數設置為一或者保持不變，這個條件是一個已分配的數和一個布爾值。

總的來說，這個文件提供了一些實用函數，這些函數可以在約束系統中分配變量、檢查兩個數是否相等、根據一個條件選擇兩個數中的一個等。

這是一個名為 "lib.rs" 的 Rust 語言源代碼文件，它是 Nova 項目的主要組成部分。這個文件主要定義了 Nova 庫的公共接口和一些核心功能。以下是對該文件的詳細解讀：

1. `pub mod ast`：這行代碼導入了一個名為 "ast" 的模塊。"ast" 是 "Abstract Syntax Tree"（抽象語法樹）的縮寫，這是一種用于表示源代碼結構的數據結構。在 Nova 項目中，"ast" 模塊可能包含了用于解析和處理 Nova 語言源代碼的各種數據結構和函數。

2. `pub mod parser`：這行代碼導入了一個名為 "parser" 的模塊。"parser" 是 "解析器" 的意思，這個模塊可能包含了用于解析 Nova 語言源代碼的函數和類。

3. `pub mod codegen`：這行代碼導入了一個名為 "codegen" 的模塊。"codegen" 是 "code generation"（代碼生成）的縮寫，這個模塊可能包含了用于將 Nova 語言的抽象語法樹轉換為目標代碼（例如 LLVM IR 或機器代碼）的函數和類。

4. `pub mod types`：這行代碼導入了一個名為 "types" 的模塊。這個模塊可能包含了 Nova 語言的類型系統，包括各種內建類型和用戶定義類型的表示和處理。

5. `pub mod util`：這行代碼導入了一個名為 "util" 的模塊。"util" 是 "utilities"（實用程序）的縮寫，這個模塊可能包含了各種實用的函數和類，例如錯誤處理、日志記錄、文件讀寫等。

6. `pub mod driver`：這行代碼導入了一個名為 "driver" 的模塊。在編譯器項目中，"driver" 通常是指控制整個編譯過程的模塊，包括源代碼的讀取、解析、類型檢查、代碼生成、優化和輸出等步驟。

7. `pub mod error`：這行代碼導入了一個名為 "error" 的模塊。這個模塊可能包含了 Nova 語言的錯誤處理系統，包括各種編譯錯誤和運行時錯誤的表示和處理。

8. `pub mod config`：這行代碼導入了一個名為 "config" 的模塊。這個模塊可能包含了 Nova 語言的配置系統，包括編譯選項、運行時選項等的表示和處理。

這個文件的主要作用是將 Nova 語言的各個組成部分（例如解析器、代碼生成器、類型系統、錯誤處理系統等）組織在一起，形成一個完整的編譯器庫。

這個文件名為 "nifs.rs"，它位于 "src/" 目錄下。這個文件實現了一個非交互式折疊方案（Non-Interactive Folding Scheme，NIFS）。這是一種密碼學協議，用于在增量計算中證明每一步的正確性。

1. `NIFS` 結構體：這個結構體表示一個 SNARK，它保存了增量計算的一步的證明。它包含一個名為 `comm_T` 的字段，這是一個壓縮的承諾（Compressed Commitment）。

2. `prove` 方法：這個方法接受一個松散的 R1CS 實例-證人對 `(U1, W1)` 和一個 R1CS 實例-證人對 `(U2, W2)`，它們具有相同的結構 `shape` 并且相對于同一個 `ck` 定義。然后，它輸出一個折疊的松散 R1CS 實例-證人對 `(U, W)`，具有相同的結構 `shape`。如果 `W1` 滿足 `U1` 并且 `W2` 滿足 `U2`，則折疊的證人 `W` 滿足折疊的實例 `U`。

3. `verify` 方法：這個方法接受一個松散的 R1CS 實例 `U1` 和一個 R1CS 實例 `U2`，它們具有相同的結構并且相對于同一個參數定義。然后，它輸出一個折疊的實例 `U`，具有相同的結構。如果 `U1` 和 `U2` 是可滿足的，那么折疊的實例 `U` 是可滿足的。

4. 測試模塊：這個模塊包含了一些測試函數，用于測試 `NIFS` 結構體的 `prove` 和 `verify` 方法。

總的來說，這個文件實現了一個非交互式折疊方案，這是一種密碼學協議，用于在增量計算中證明每一步的正確性。這個方案的主要優點是它可以將多個證明折疊成一個證明，從而減少了存儲和傳輸證明的開銷。

這個文件名為 "ipa_pc.rs"，它位于 "src/provider/" 目錄下。這個文件實現了一個使用基于 IPA（Inner Product Argument）的多項式承諾方案的評估引擎。

1. `ProverKey` 結構體：這個結構體表示一個證明者密鑰，它包含一個承諾密鑰 `ck_s`。

2. `VerifierKey` 結構體：這個結構體表示一個驗證者密鑰，它包含兩個承諾密鑰 `ck_v` 和 `ck_s`。

3. `EvaluationArgument` 結構體：這個結構體表示一個多項式評估參數，它包含一個內積參數 `ipa`。

4. `EvaluationEngine` 結構體：這個結構體表示一個使用 IPA 的多項式評估引擎。

5. `EvaluationEngineTrait` trait 的實現：這個 trait 的實現提供了多項式評估引擎的主要功能，包括設置、證明和驗證。

6. `inner_product` 函數：這個函數計算兩個向量的內積。

7. `InnerProductInstance` 結構體：這個結構體表示一個內積實例，它包含一個向量 `a` 的承諾 `comm_a_vec`，另一個向量 `b_vec`，以及一個聲稱 `c = <a, b>` 的值 `c`。

8. `InnerProductWitness` 結構體：這個結構體表示一個內積證人，它包含一個向量 `a_vec`。

9. `InnerProductArgument` 結構體：這個結構體表示一個內積參數，它包含兩個壓縮承諾向量 `L_vec` 和 `R_vec`，以及一個標量 `a_hat`。

數據：當前Solana生態總市值為257.7億美元:金色財經消息，據CoinGecko最新數據顯示，當前Solana生態總市值為257.7億美元（截至發稿時為25,776,752,852美元），24小時交易額為2,253,807,546

美元。目前按市值排名前三的項目分別是：Solana（17,008,465,233美元）、STEPN（1,096,595,061美元）和Serum（347,418,381美元）。[2022/5/22 3:33:36]

總的來說，這個文件實現了一個使用基于 IPA 的多項式承諾方案的評估引擎，這是一種密碼學協議，用于在零知識證明中證明多項式在某個點的評估值。這個方案的主要優點是它可以在不泄露多項式本身的情況下證明多項式的評估值，從而保護了多項式的隱私。

這個文件名為 "keccak.rs"，它位于 "src/provider/" 目錄下。這個文件實現了一個使用 Keccak256 哈希函數的 TranscriptEngineTrait。TranscriptEngineTrait 是一個用于處理零知識證明過程中的 transcript 的 trait，transcript 是一個記錄了證明過程中所有的交互步驟的數據結構。

1. `Keccak256Transcript` 結構體：這個結構體實現了 TranscriptEngineTrait，它使用 Keccak256 哈希函數來處理 transcript。它包含一個 round 字段來記錄當前的輪數，一個 state 字段來保存當前的哈希狀態，一個 transcript 字段來保存 transcript，以及一個 _p 字段來保存類型信息。

2. `compute_updated_state` 函數：這個函數接受一個輸入，然后計算更新后的哈希狀態。

3. `TranscriptEngineTrait` 的實現：這個 trait 的實現提供了處理 transcript 的主要功能，包括新建一個 transcript、從 transcript 中提取一個挑戰、向 transcript 中添加一個元素、以及添加一個 domain separator。

4. 測試模塊：這個模塊包含了一些測試函數，用于測試 `Keccak256Transcript` 結構體的功能。

總的來說，這個文件實現了一個使用 Keccak256 哈希函數的 TranscriptEngineTrait，這是一種用于處理零知識證明過程中的 transcript 的工具。這個工具的主要優點是它可以在不泄露證明過程中的交互步驟的情況下處理 transcript，從而保護了證明過程的隱私。

這個文件名為 "mod.rs"，它位于 "src/provider/" 目錄下。這個文件主要用于導入 Nova 項目中的各種實現模塊，這些模塊提供了 Nova 項目所需的各種功能。

1. `pub mod ipa_pc;`：這行代碼導入了一個名為 "ipa_pc" 的模塊。這個模塊實現了一個使用基于 IPA（Inner Product Argument）的多項式承諾方案的評估引擎。

2. `pub mod keccak;`：這行代碼導入了一個名為 "keccak" 的模塊。這個模塊實現了一個使用 Keccak256 哈希函數的 TranscriptEngineTrait。

3. `pub mod pasta;`：這行代碼導入了一個名為 "pasta" 的模塊。這個模塊可能包含了一些使用 Pasta 曲線的函數和類。

4. `pub mod pedersen;`：這行代碼導入了一個名為 "pedersen" 的模塊。這個模塊可能包含了一些使用 Pedersen 承諾的函數和類。

5. `pub mod poseidon;`：這行代碼導入了一個名為 "poseidon" 的模塊。這個模塊可能包含了一些使用 Poseidon 哈希函數的函數和類。

總的來說，這個文件的主要作用是將 Nova 項目的各個組成部分（例如評估引擎、TranscriptEngineTrait、Pasta 曲線、Pedersen 承諾、Poseidon 哈希函數等）組織在一起，形成一個完整的密碼學庫。

文件名：`src/r1cs.rs`

這個文件定義了與Rank-1 Constraint System (R1CS)相關的類型和方法。R1CS是一種廣泛用于零知識證明系統的約束系統。

主要定義了以下幾個結構和它們的方法：

1. `R1CS<G: Group>`：這個結構體表示一個R1CS的公共參數。它包含一個方法`commitment_key`用于生成R1CS的公共參數。

2. `R1CSShape<G: Group>`：這個結構體表示R1CS矩陣的形狀，包含了約束的數量、變量的數量、輸入/輸出的數量以及A、B、C三個矩陣。它包含了一些方法，如`new`用于從顯式指定的R1CS矩陣創建一個`R1CSShape`對象，`multiply_vec`用于計算矩陣和向量的乘積，`is_sat_relaxed`和`is_sat`用于檢查給定的證人和其形狀是否滿足Relaxed R1CS實例和R1CS實例，`commit_T`用于計算給定的Relaxed R1CS實例-證人對和R1CS實例-證人對的交叉項`T`的承諾，`pad`用于填充R1CSShape使得變量的數量是2的冪，并重新編號變量以適應填充的變量。

3. `R1CSWitness<G: Group>`：這個結構體表示給定R1CS實例的證人，包含了一些方法，如`new`用于使用標量向量創建證人對象，`commit`用于使用提供的生成器對證人進行承諾。

4. `R1CSInstance<G: Group>`：這個結構體表示一個R1CS實例，包含了一些方法，如`new`用于使用構成元素創建實例對象。

5. `RelaxedR1CSWitness<G: Group>`：這個結構體表示給定Relaxed R1CS實例的證人，包含了一些方法，如`default`用于生成默認的RelaxedR1CSWitness，`from_r1cs_witness`用于從R1CSWitness初始化一個新的RelaxedR1CSWitness，`commit`用于使用提供的生成器對證人進行承諾，`fold`用于將傳入的R1CSWitness折疊到當前的證人，`pad`用于將提供的證人填充到正確的長度。

6. `RelaxedR1CSInstance<G: Group>`：這個結構體表示一個Relaxed R1CS實例，包含了一些方法，如`default`用于生成默認的RelaxedR1CSInstance，`from_r1cs_instance`用于從R1CSInstance初始化一個新的RelaxedR1CSInstance，`from_r1cs_instance_unchecked`用于從R1CSInstance初始化一個新的RelaxedR1CSInstance（不進行檢查），`fold`用于將傳入的RelaxedR1CSInstance折

文件名：`src/spartan/math.rs`

這個文件定義了一個名為`Math`的特質（trait），以及對`usize`類型的實現。這個特質定義了一些數學操作，包括求2的冪、獲取二進制位以及計算對數。

1. `Math`特質定義了以下幾個方法：

- `pow2(self) -> usize`：計算2的self次冪。

- `get_bits(self, num_bits: usize) -> Vec<bool>`：獲取self的二進制表示的前num_bits位。

- `log_2(self) -> usize`：計算以2為底的self的對數。

2. 對于`usize`類型，實現了`Math`特質的所有方法：

- `pow2(self) -> usize`：使用內置的`pow`函數計算2的self次冪。

- `get_bits(self, num_bits: usize) -> Vec<bool>`：通過位移和按位與操作獲取self的二進制表示的前num_bits位。

- `log_2(self) -> usize`：如果self是2的冪，則使用`leading_zeros`方法計算以2為底的self的對數；否則，使用`leading_zeros`方法和`usize`的最大值的`leading_zeros`方法計算以2為底的self的對數。

這個文件提供了一些基本的數學操作，可能被其他部分的代碼用于實現更復雜的功能。

文件名：src/spartan/mod.rs

這個模塊實現了使用Spartan的RelaxedR1CSSNARKTrait，該Trait是通用的多項式承諾和評估參數（即PCS）。

以下是一些主要的結構和函數：

1. `PolyEvalWitness`：這是一個結構體，它包含一個多項式的證明。

2. `PolyEvalInstance`：這是一個結構體，它包含一個多項式評估的實例。

3. `ProverKey` 和 `VerifierKey`：這兩個結構體分別代表證明者的密鑰和驗證者的密鑰。

4. `RelaxedR1CSSNARK`：這個結構體表示了一個對松弛的R1CS實例的知識的簡潔證明。該證明使用Spartan的sum-check和向量視為多項式承諾的組合產生。

5. `setup`：這個函數用于設置證明和驗證密鑰。

6. `prove`：這個函數用于生成一個松弛的R1CS實例的滿足性的簡潔證明。

7. `verify`：這個函數用于驗證一個松弛的R1CS實例的滿足性的證明。

這個模塊中的代碼主要涉及到了密碼學中的零知識證明，特別是關于R1CS（Rank-1 Constraint Systems）的證明。R1CS是一種用于構建零知識證明的系統，它可以用于證明一個人知道滿足一組多項式等式的解，而不必透露任何關于解的信息。Spartan是一種特定的零知識證明系統，它使用了一種稱為“松弛的”R1CS，這種系統允許在證明中使用隨機性，從而提高了效率。

文件名：src/spartan/polynomial.rs

這個文件定義了與多項式相關的一些基本類型和操作。這些類型和操作用于實現Spartan協議中的多項式計算。

1. `EqPolynomial`：這個結構體表示一個等式多項式。它包含了一個方法`new`用于創建新的多項式，一個方法`evaluate`用于在指定點評估多項式，以及一個方法`evals`用于計算多項式在所有布爾輸入上的評估。

2. `MultilinearPolynomial`：這個結構體表示一個多線性多項式。它包含了一個方法`new`用于創建新的多項式，一個方法`get_num_vars`用于獲取多項式的變量數量，一個方法`bound_poly_var_top`用于將多項式的變量綁定到頂部，以及一個方法`evaluate`用于在指定點評估多項式。

3. `SparsePolynomial`：這個結構體表示一個稀疏多項式。它包含了一個方法`new`用于創建新的多項式，以及一個方法`evaluate`用于在指定點評估多項式。

這個文件中的代碼主要涉及到了密碼學中的多項式計算，特別是關于多線性多項式和稀疏多項式的計算。這些計算在零知識證明系統中扮演了重要的角色，因為它們可以用于構造復雜的證明，而不必透露任何關于證明的信息。

`src/spartan/pp.rs` 是 Nova 項目中的一個 Rust 語言文件。這個文件主要實現了 Nova 中的預處理器（Preprocessor）的功能。預處理器是編譯過程中的一個階段，它在實際編譯之前對代碼進行一些處理。

這個文件中的主要結構和函數包括：

1. `struct Preprocessor`：這是一個預處理器的結構體，它包含了預處理器需要的一些狀態和數據。

2. `impl Preprocessor`：這是對 `Preprocessor` 結構體的實現，包含了一些方法。

3. `fn new(source: String) -> Self`：這是 `Preprocessor` 的構造函數，用于創建一個新的 `Preprocessor` 實例。

4. `fn preprocess(&mut self) -> Result<(), Error>`：這是預處理器的主要函數，它對輸入的源代碼進行預處理，并返回處理結果。如果處理過程中出現錯誤，它會返回一個錯誤。

5. `fn next_token(&mut self) -> Result<Token, Error>`：這個函數用于從源代碼中獲取下一個 token。如果處理過程中出現錯誤，它會返回一個錯誤。

6. `fn skip_whitespace(&mut self)`：這個函數用于跳過源代碼中的空白字符。

7. `fn skip_comment(&mut self) -> Result<(), Error>`：這個函數用于跳過源代碼中的注釋。如果處理過程中出現錯誤，它會返回一個錯誤。

8. `fn read_number(&mut self) -> Result<Token, Error>`：這個函數用于從源代碼中讀取一個數字。如果處理過程中出現錯誤，它會返回一個錯誤。

9. `fn read_identifier(&mut self) -> Result<Token, Error>`：這個函數用于從源代碼中讀取一個標識符。如果處理過程中出現錯誤，它會返回一個錯誤。

10. `fn read_string(&mut self) -> Result<Token, Error>`：這個函數用于從源代碼中讀取一個字符串。如果處理過程中出現錯誤，它會返回一個錯誤。

總的來說，`src/spartan/pp.rs` 文件實現了 Nova 中的預處理器，它對源代碼進行預處理，包括跳過空白字符和注釋，讀取數字、標識符和字符串等。

文件名：src/spartan/sumcheck.rs

這個文件實現了Spartan協議中的Sumcheck算法。Sumcheck算法是一種用于驗證多項式求和的算法，它在零知識證明系統中有著廣泛的應用。

1. `SumcheckProof`：這個結構體表示一個Sumcheck證明。它包含了一個方法`new`用于創建新的證明，一個方法`verify`用于驗證證明，以及幾個`prove`方法用于生成證明。

2. `UniPoly`和`CompressedUniPoly`：這兩個結構體表示一元多項式和壓縮的一元多項式。它們包含了一些方法用于創建多項式，評估多項式，在指定點評估多項式，以及壓縮和解壓縮多項式。

3. `TranscriptReprTrait`：這個trait定義了一個方法`to_transcript_bytes`，用于將對象轉換為字節序列。這在零知識證明系統中是常見的操作，因為它可以用于將對象的表示添加到證明的轉錄中。

這個文件中的代碼主要涉及到了密碼學中的Sumcheck算法，特別是關于多項式的計算和證明。這些計算在零知識證明系統中扮演了重要的角色，因為它們可以用于構造復雜的證明，而不必透露任何關于證明的信息。

文件名：src/traits/circuit.rs

這個文件定義了一個名為`StepCircuit`的特質（trait），以及一個實現了這個特質的`TrivialTestCircuit`結構體。這個特質和結構體都與增量計算的步驟函數有關。

1. `StepCircuit`特質：這個特質定義了一個增量計算的步驟函數必須實現的方法。這些方法包括：

- `arity`：返回每個步驟的輸入或輸出的數量。

- `synthesize`：對一個計算步驟進行合成，并返回對應于步驟輸出的變量。

- `output`：當提供步驟的輸入時，返回步驟的輸出。

2. `TrivialTestCircuit`結構體：這個結構體實現了`StepCircuit`特質，它簡單地返回輸入。這個結構體可能用于測試或作為一個基本的步驟函數。

這個文件中的代碼主要涉及到了增量計算的步驟函數。在密碼學中，增量計算是一種常見的技術，它可以用于逐步計算復雜的函數，而不必一次性計算整個函數。這種技術在零知識證明系統中尤其有用，因為它可以用于構造復雜的證明，而不必一次性生成整個證明。

文件名：src/traits/commitment.rs

這個文件定義了一些與承諾（commitment）相關的特質（traits）。在密碼學中，承諾是一種機制，使得一個人可以承諾一個值，而不立即揭示它。這在許多密碼學協議中都是必要的，例如零知識證明。

1. `CommitmentOps`特質：這個特質定義了承諾的基本操作，包括加法和加法賦值。

2. `CommitmentOpsOwned`特質：這個特質為擁有承諾的引用定義了基本操作。

3. `ScalarMul`特質：這個特質定義了承諾與標量的乘法操作。

4. `CommitmentTrait`特質：這個特質定義了承諾的行為，包括克隆、復制、默認、比較、發送、同步、序列化、反序列化、吸收、操作、壓縮、解壓縮等。

5. `CommitmentEngineTrait`特質：這個特質將承諾生成的不同部分綁定在一起，包括承諾鍵、承諾、設置、承諾等。

這個文件中的代碼主要涉及到了密碼學中的承諾。這些承諾在零知識證明系統中扮演了重要的角色，因為它們可以用于構造復雜的證明，而不必透露任何關于證明的信息。

文件名：src/traits/evaluation.rs

這個文件定義了一個名為`EvaluationEngineTrait`的特質（trait）。這個特質定義了一個多項式評估引擎的行為，包括設置、證明和驗證。

1. `EvaluationEngineTrait`特質：這個特質定義了一個多項式評估引擎必須實現的方法。這些方法包括：

- `setup`：這個方法用于進行任何需要生成評估證明的額外設置。

- `prove`：這個方法用于證明一個多線性多項式的評估。

- `verify`：這個方法用于驗證一個多線性多項式的評估的證明。

這個特質還定義了一些關聯類型，包括：

- `CE`：這是與承諾引擎相關聯的類型。

- `ProverKey`：這是證明者密鑰的類型。

- `VerifierKey`：這是驗證者密鑰的類型。

- `EvaluationArgument`：這是評估參數的類型。

這個文件中的代碼主要涉及到了密碼學中的多項式評估。這在零知識證明系統中是一個重要的步驟，因為它可以用于證明一個人知道滿足一組多項式等式的解，而不必透露任何關于解的信息。

文件名：src/traits/mod.rs

這個文件是Nova項目中traits模塊的主要入口點。它主要定義了一些用于密碼學操作的特質（traits）。特質是Rust中的一個關鍵特性，它定義了一種抽象類型，這種類型可以被多種不同的具體類型實現。這使得我們可以編寫通用的代碼，這些代碼可以處理實現了特定特質的任何類型的值。

1. `Group`特質：這個特質定義了一個群的基本操作，包括克隆、復制、默認、比較、發送、同步、序列化、反序列化、吸收、操作、壓縮、解壓縮等。

2. `CompressedGroup`特質：這個特質定義了一個壓縮群的基本操作，包括克隆、復制、比較、發送、同步、序列化、反序列化等。

3. `AbsorbInROTrait`特質：這個特質定義了一個方法`absorb_in_ro`，用于將對象吸收到隨機預言機（Random Oracle）中。

4. `ROTrait`特質：這個特質定義了隨機預言機的行為，包括初始化、吸收和擠壓。

5. `ROConstantsTrait`特質：這個特質定義了隨機預言機的常量。

6. `GroupOps`特質：這個特質定義了群操作，包括加法、減法、加法賦值和減法賦值。

7. `ScalarMul`特質：這個特質定義了標量乘法操作。

8. `TranscriptReprTrait`特質：這個特質定義了一個方法`to_transcript_bytes`，用于將對象轉換為字節序列。

9. `TranscriptEngineTrait`特質：這個特質定義了轉錄引擎的行為，包括初始化、擠壓、吸收和添加域分隔符。

這個文件中的代碼主要涉及到了密碼學中的群操作、隨機預言機和轉錄引擎。這些在零知識證明系統中扮演了重要的角色，因為它們可以用于構造復雜的證明，而不必透露任何關于證明的信息。

文件名：src/traits/snark.rs

這個文件定義了一個名為`RelaxedR1CSSNARKTrait`的特質（trait）。這個特質定義了一個零知識簡潔非交互式論證（zkSNARK）的行為，特別是對于松弛的秩一約束系統（Relaxed Rank-1 Constraint Systems，Relaxed R1CS）。

1. `RelaxedR1CSSNARKTrait`特質：這個特質定義了一個zkSNARK必須實現的方法。這些方法包括：

- `setup`：這個方法用于生成證明者和驗證者的密鑰。

- `prove`：這個方法用于生成一個松弛的R1CS實例的滿足性的簡潔證明。

- `verify`：這個方法用于驗證一個松弛的R1CS實例的滿足性的證明。

這個文件中的代碼主要涉及到了密碼學中的零知識證明，特別是關于R1CS的證明。R1CS是一種用于構建零知識證明的系統，它可以用于證明一個人知道滿足一組多項式等式的解，而不必透露任何關于解的信息。zkSNARK是一種特定的零知識證明系統，它提供了一種生成和驗證證明的有效方法。

火必研究院

個人專欄

閱讀更多

金色財經

金色薦讀

Block unicorn

金色財經 善歐巴

區塊鏈騎士

Foresight News

深潮TechFlow

Tags：TRAQUORAIAITJust for DecentralizationQUO幣Brain SyncSaitaRealty

火必APP