Allen

Allen

crypto seeker||starknet

零知識生成證明速度對比

以下是中文(繁體)的翻譯:

zkVM 項目的 tps 相關因素,1-5 是與零知識相關

  1. 從 EVM 兼容性方案,來看需要證明計算量
    EVM 兼容性 (高級語言等效性,zkVM) > EVM 等效性 > ETH 等效性 (PSE)
    Starknet = Sin7Y > Zksync > PloygonZkevm > Scroll > Ploygon Zero > PSE

  2. 從多項式承諾看生成證明的速度
    小域 + FRI > FRI > FRI&KZG > KZG (算法複雜度排序會有不同)
    Ploygon Zero > Starknet > Sin7Y > PloygonZkevm > Zksync = Scroll = PSE

  3. 從算法方向好實現硬件並行證明的可能
    單一的算法更好實現優化,MSM 目前優於 FFT
    純 MSM > 純 FFT > 混合
    Sin7Y (純 MSM) > Ploygon Zero (純 FTT) > Starknet > PloygonZkevm > Zksync > Scroll > PSE

  4. 零知識證明系統的遞歸證明優化
    Plonky2 > Stark > Plonk = Halo2
    Ploygon Zero > Sin7Y > Starknet > PloygonZkevm > Zksync = Scroll = PSE

  5. 零知識證明系統的可組合性
    Ploygon Zero = Sin7Y > PloygonZkevm > Starknet > Zksync = Scroll = PSE

  6. 從 VM 本身並行性 (交易並行)
    OlaVM > zkVM > zkEVM
    Sin7Y > Starknet > Zksync > PloygonZkevm > Scroll > Ploygon > PSE

實現 VM 的開發語言對效率也有一定影響。

  1. 主網能運行大量應用的時間點(越快越優先)
    Zksync > Starknet > PloygonZkevm > Scroll > Sin7y > Ploygon Zero > PSE

  2. 能運行 L3 的時間點(越快越優先)
    Starknet > Zksync > PloygonZkevm > Sin7y > Ploygon Zero > Scroll

根據證明系統的不同,證明生成過程可能會有所不同,但瓶頸是:

  1. 可變基數和固定基數多標量乘法(MSM)
  2. 快速傅立葉變換 (FFT) 和逆 FFT

在同時存在 FFT 和 MSM 的系統中,大約 70% 的時間生成證明花費在 MSM 上,其餘時間則由 FFT 主導。

MSM 和 FFT 都很慢,但都有提高性能的方法:

  • MSM 具有令人尷尬的並行性,可以通過在多個線程上運行它們來加速。然而,即使在數百個內核上,乘法最終仍然會花費大量時間。這意味著經常重複相同的操作,並且會耗盡設備上的大部分可用內存。簡而言之,MSM 需要大量內存並且即使在高度並行化時仍然很慢。
  • FFT 嚴重依賴算法運行時數據的頻繁洗牌。此外,它們在硬件上運行時需要大量帶寬。改組意味著您需要 “隨機” 加載和卸載元素,例如,具有 16GB 或更少內存的硬件芯片上的 > 100GB 數據集。雖然硬件上的操作非常快,但通過網絡加載和卸載數據的時間最終會顯著減慢操作速度。

簡而言之:

  • MSM 具有可預測的內存訪問,允許大量並行化,但由於所需的原始計算量和內存量,它們的成本仍然很高。
  • FFT 具有隨機內存訪問,這使得它們對硬件不友好,而且自然難以在分佈式基礎設施上運行。

在解決大型 MSM 和 FFT 的緩慢問題方面,我們看到的最有希望的工作是 PipeZK。在他們的論文中,作者描述了一種使用 Pippenger 算法跳過重複計算來使 MSM 更便宜的方法。

他們還描述了一種 “展開” FFT 的方法,這樣它們就可以在沒有顯著改組的情況下執行,由於現在可預測的內存訪問模式,提高速度。

近期,Plonk 系提出一種新的方案,MSM 方向優化後更適合並行。

並行化

rust VM

cairo 1.0

regenesis(重生)

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。