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

HTX Research ｜2023-07-11 12:18

Nova是微軟開發的一種新型零知識證明系統，它使用了一種名為鬆弛的秩一約束系統（Relaxed Rank-1 Constraint Systems，Relaxed R1CS）的技術，以提高證明的效率和靈活性。

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

引言

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

Nova的優點

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

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

Nova的缺點

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

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

Nova在零知識證明領域的重要地位

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

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`: 這個方法用於彈出當前的命名空間。
  - `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`: 這個方法用於分配一個新的輔助變量。
  - `alloc_input`: 這個方法用於分配一個新的輸入變量。
  - `enforce`: 這個方法用於添加一個新的約束。
  - `push_namespace`, `pop_namespace`: 這些方法用於操作命名空間，但在這個上下文中並沒有實際的操作。
  - `get_root`: 這個方法用於獲取根約束系統。
  - `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 增強電路的主要合成方法，它首先分配所有的證人，然後根據是否是基礎案例來合成電路，並最後輸出計算的哈希值和uX[1]。
  這個文件還包含了一些測試代碼，用於測試遞歸電路的功能。
  總的來說，這個文件的主要作用是定義了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`: 如果增量計算的初始輸入與先前聲明的元數不符，將返回此錯誤。
  - `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` 兩個子模塊，它們可能包含了一些實現非本地字段算術運算的函數或者類。
  總的來說，這個文件提供了一種在非本地字段上進行算術運算的方法，這對於實現某些密碼學算法是非常重要的。
- "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` 函數：這個函數用於根據一個條件將一個數設置為零或者保持不變，這個條件是一個布爾值。
  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`。
  總的來說，這個文件實現了一個使用基於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