什麼是遞迴？

遞歸最常用於數學、統計學和電腦科學領域，但它也廣泛應用於其他一系列學科，包括語言學和邏輯學，以及人工智慧和遊戲的實際應用。

遞歸是指函數在循環中直接或間接地呼叫自身。

遞歸可用於提高計算精度並減少所需的總體計算負載。透過將更大、更複雜的問題分解為更小的部分（也稱為「分而治之」），遞歸可以更快、更可行地解決任務。一個關鍵特徵是該函數會連續重複呼叫自身以實現根據基本情況和遞歸步驟定義的遞歸。

基本情況是指所有具有計算輸出的輸入的問題的最簡單實例。遞歸步驟呼叫相同的函數，但輸入的大小和/或複雜度會減少。

迭代演算法和遞歸演算法都將問題分解為更小的問題，但前者需要明確的控制邏輯來管理演算法的順序。遞歸函數的排序是由向量資料和遞歸函數的相互作用決定的。這為處理無法提前明確定義的資料結構提供了更大的靈活性。

遞歸如何應用於區塊鏈技術？

遞歸是一種在區塊鏈上產生證明的方法。現在它為以太坊主網路上的多個生產系統提供服務。例如，Arbitrum 使用遞歸二分演算法來解決爭議，而 StarkWare 和 zkSync 都使用遞歸來實現增強的擴展能力。

如果沒有遞歸技術，證明中可以容納的交易存在上限，該上限由單一區塊的運算能力決定。透過遞歸，可以從包含數十萬個基礎交易的多個經過驗證的證明中產生單一證明。換句話說，我們現在可以在單一證明中處理更多交易，也稱為遞歸擴展。

遞歸技術應用於零知識證明尤其重要，因為它被視為解決區塊鏈可擴展性的關鍵解決方案。以StarkWare 的StarkNet（以太坊上領先的zk-rollup 擴展解決方案之一）為例，SHARP（SHARed Prover）將來自StarkNet 上單獨應用程式的交易批量並壓縮為一個ZK-STARK 證明（或只是STARK 證明）。然後證明者將證明傳遞給驗證者，驗證者的工作是在第 1 層驗證和註冊狀態更改。

現在讓我們在圖中加入遞歸。多個交易（或語句）被送到 SHARP 並並行進行驗證。然後每個證明都會由 STARK 驗證者進行驗證。一旦驗證，它們就會透過遞歸驗證器語句再次合併。這個過程可以重複進行，直到最終證明被提交到第 1 層以供 Solidity 驗證者智能合約使用。因此，該證明證明了所有原始陳述，允許在單一證明中處理多個鏈上交易。理論上，遞歸循環​​可以無限重複，從而具有「超擴展」能力的潛力。

因此，遞歸進一步釋放了匯總技術和第 2 層擴展的潛力。

遞迴的好處

有效性證明遞歸的好處包括由於將多個證明「壓縮」為一個而降低了每筆交易的成本，從而降低了 Gas 成本。這允許更多交易在提交給 L1 的單一證明中拆分，從而分攤每筆交易的 Gas 成本。限制證明大小的計算資源障礙也不再是一種約束，因為不需要一次性證明非常大的語句。

它還可以減少延遲。語句（包含較小的交易）可以並行證明，而不必等待其他交易進入。提高網路的處理能力。

此外，使用者還可以受益於 STARK 的“對數壓縮”，其中證明一個陳述需要 T 時間，而驗證證明大約需要 log(T) 時間。對數壓縮很重要，因為驗證包含兩個正確執行證明的證明將需要 log(2log(T)) 步驟。換句話說，產生和驗證遞歸證明的延遲呈對數減少。

透過遞歸，平台和應用程式有機會進一步擴展其成本和效能。

第 2 層之外的遞歸的用途

遞歸為第 3 層用例奠定了基礎。到目前為止，重點是使用遞歸在第2 層上產生最終在第1 層上解決的證明。完成，最終在第 2 層驗證證明，可以進一步釋放性能優化和成本效益。第 3 層和第 2 層之間的交互作用類似於第 2 層和第 1 層，同時保留所有事務完整性和安全性。

具體來說，私有第 3 層網路是高度可自訂的，因此協議能夠設定自己的操作參數，例如設定交易批量大小以平衡交易成本和速度或實現隱私保護功能。第 3 層的客製化品質可滿足不同的用例，同時透過遞歸提高處理能力，從而實現客製化的鏈體驗，同時確保效能和成本優化工具隨時可用。第 3 層的優點是超可擴展性，這是由於利用了遞歸證明、隱私性以及第 2 層和第 3 層之間改進的互通性的乘法效應。

隨著時間的推移，區塊鏈開發中遞歸的更多用例和好處將被實現。透過解鎖並行化過程，它將使超擴展成為可能，同時改善延遲並降低天然氣費用。

作者

Jane Ma，zkLend 的聯合創始人兼聯合項目負責人，zkLend 是一個基於 StarkNet 構建的 L2 貨幣市場協議，將 zk-rollup 可擴展性、卓越的交易速度和成本節約與以太坊的安全性相結合。該協議提供了雙重解決方案：為機構客戶提供許可且注重合規性的解決方案，為 DeFi 用戶提供無需許可的服務 - 所有這些都不會犧牲去中心化。