1. 引言

跨鏈互操作性的未來(lái)將圍繞多鏈dapp之間的動(dòng)態(tài)和數(shù)據(jù)豐富的關(guān)系構(gòu)建。Lagrange Labs 正在構(gòu)建粘合劑，以幫助安全地?cái)U(kuò)展基于零知識(shí)證明的互操作性。

2. ZK大數(shù)據(jù)棧

Lagrange Labs 的ZK大數(shù)據(jù)棧 為一種專有的證明結(jié)構(gòu)，用于在任意動(dòng)態(tài)分布式計(jì)算的同時(shí)生成大規(guī)模batch storage proof。ZK大數(shù)據(jù)堆?？蓴U(kuò)展到任何分布式計(jì)算框架，從MapReduce到RDD再到分布式SQL。

使用Lagrange Labs ZK大數(shù)據(jù)棧，可以從單個(gè)區(qū)塊頭生成證明，用于證明任意深度的歷史storage slot 狀態(tài)數(shù)組 和 對(duì)這些狀態(tài)執(zhí)行的分布式計(jì)算的結(jié)果。簡(jiǎn)而言之，每個(gè)證明都在一個(gè)步驟中結(jié)合了storage proof的驗(yàn)證 和 可驗(yàn)證的分布式計(jì)算。

在本文中，將討論ZK-MapReduce（ZKMR）——Lagrange Labs ZK大數(shù)據(jù)棧 的第一個(gè)產(chǎn)品。

3. 何為MapReduce

在傳統(tǒng)的順序計(jì)算中，單個(gè)處理器按照線性路徑執(zhí)行整個(gè)程序，其中每條指令都按其在代碼中出現(xiàn)的順序執(zhí)行。使用MapReduce和類似的分布式計(jì)算范式（如RDD），計(jì)算被劃分為多個(gè)小任務(wù)，這些小任務(wù)可以在多個(gè)處理器上并行執(zhí)行。

MapReduce的工作原理是將一個(gè)大數(shù)據(jù)集分解成更小的塊，并將它們分布在一個(gè)機(jī)器集群中。大體上，這種計(jì)算遵循三個(gè)不同的步驟：

• 1）Map：每臺(tái)機(jī)器對(duì)其數(shù)據(jù)塊執(zhí)行map操作，將其轉(zhuǎn)換為一組鍵值（key-value）對(duì)。
• 2）Shuffle：對(duì)Map操作生成的鍵值對(duì)按鍵（key）進(jìn)行shuffle和排序。
• 3）Reduce：Shuffle的結(jié)果被傳遞給Reduce操作，Reduce操作聚合數(shù)據(jù)并產(chǎn)生最終輸出。

MapReduce的主要優(yōu)點(diǎn)在于其可擴(kuò)展性。由于計(jì)算分布在多臺(tái)機(jī)器上，因此它可以處理無(wú)法按順序處理的大規(guī)模數(shù)據(jù)集。此外，MapReduce的分布式特性允許計(jì)算在更多的機(jī)器上水平擴(kuò)展，而不是在計(jì)算時(shí)間方面垂直擴(kuò)展。

分布式計(jì)算范例（如MapReduce或RDD）通常用于Web 2.0架構(gòu)中，用于處理和分析大型數(shù)據(jù)集。大多數(shù)大型web 2.0公司，如谷歌、亞馬遜和臉書，都在很大程度上利用分布式計(jì)算來(lái)處理PB級(jí)的搜索數(shù)據(jù)和用戶數(shù)據(jù)集。用于分布式計(jì)算的現(xiàn)代框架包括Hive、Presto和Spark。

3. zkMapReduce介紹

Lagrange的zkMapReduce（zkMR）為MapReduce的擴(kuò)展，其利用遞歸證明來(lái)證明基于大量鏈上狀態(tài)數(shù)據(jù)的分布式計(jì)算的正確性。通過(guò)在分布式計(jì)算作業(yè)的Map或Reduce步驟期間為每個(gè)給定worker生成計(jì)算正確性的證明來(lái)實(shí)現(xiàn)的。這些證明可以遞歸組合，構(gòu)建整個(gè)分布式計(jì)算工作流有效性的單一證明。換句話說(shuō)，可以將較小計(jì)算的證明組合起來(lái)，以創(chuàng)建整個(gè)計(jì)算的證明。

將worker computation的多個(gè)sub-proofs組合成單個(gè)zkMR proof的能力使其能夠更有效地?cái)U(kuò)展到大型數(shù)據(jù)集上的復(fù)雜計(jì)算。

與zkVM相比，zkMR的主要優(yōu)勢(shì)之一在于，其能在合約現(xiàn)有和歷史storage state基礎(chǔ)之上執(zhí)行動(dòng)態(tài)計(jì)算。無(wú)需：

• 分別跨越一系列區(qū)塊來(lái)證明storage inclusion
• 再基于aggregated data set之上證明一系列計(jì)算

zkMR（以及Lagrange的其它ZK大數(shù)據(jù)產(chǎn)品）支持將以上2者組合為單個(gè)proof。與其他設(shè)計(jì)相比，這樣可大幅降低生成zkMR proof的證明時(shí)長(zhǎng)。

3.1 zkMR示例

為理解遞歸證明的組合原理，先舉個(gè)簡(jiǎn)單的例子。假設(shè)需計(jì)算某DEX內(nèi)某資產(chǎn)對(duì) 在指定期間內(nèi)的平均流動(dòng)性。為此，必須：

• 對(duì)于每個(gè)區(qū)塊，必須展示其correctness of an inclusion proof on the state root，以證明該DEX內(nèi)的流動(dòng)性數(shù)量。
• 必須對(duì)每個(gè)區(qū)塊的流動(dòng)性求和，再除以區(qū)塊數(shù)。

這樣的順序計(jì)算類似為：

# Sequential Execution
func calculate_avg_eth_price_per_block(var mpt_paths, var liquidity_per_block){
    
    var sum = 0;
    
    for(int i=0; i<len(liquidity_per_block); i++){
        
         verify_inclusion(liquidity_per_block[i], mpt_path[i])
         sum += liquidity_per_block[i]
        
    }
    
    var avg_liquidity = sum / num_blocks

    // return the average liquidity
    return avg_liquidity
}

但是，隨著所包含state數(shù)量的增加，該程序的性能將急速下降。以下圖為例，展示每個(gè)鏈單位時(shí)間內(nèi)的區(qū)塊數(shù)。以Arbitrum上的單個(gè)DEX一個(gè)月內(nèi)某單一DEX的平均流動(dòng)性為例，其需要的數(shù)據(jù)需橫跨約6500萬(wàn)個(gè)rollup區(qū)塊。

但是，借助zkMR，可將該dataset切分為更小的chunks，并分發(fā)給多個(gè)處理器。每個(gè)機(jī)器執(zhí)行map操作——計(jì)算Merkle-Patricia Trie（MPT）proof 并基于其chunk of data對(duì)流動(dòng)性求和。該map操作會(huì)生成key-value pair，其中key為某constant string（如average_liquidity），value為a tuple containing the sum and count。

該map操作輸出的為一組key-value pairs，可shuffled and sorted by key，然后傳遞給reduce操作。reduce接收的為key-value pair，其中key為average_liquidity，value為a list of tuples containing the sum and count of the liquidity from each map操作。該reduce操作將通過(guò)對(duì)單個(gè)sums和counts求和來(lái)聚合數(shù)據(jù)，然后將final sum除以final count，以獲得最終的平均流動(dòng)性。

示例代碼為：

# Map step
func map(liquidity_data_chunk,mpt_path_chunk){
    
    var sum = 0
    
    for(int i=0; i<len(liquidity_data_chunk); i++){
        
         verify_inclusion(liquidity_data_chunk[i], mpt_path_chunk[i])
         sum += liquidity_data_chunk[i]
    }
    
    return ("average_liquidity", (sum, len(liquidity_data_chunk)))
}

# Reduce step
func reduce(liquidity_data_chunk){
    
    var sum = 0
    var count = 0
    
    for(int i=0; i<len(liquidity_data_chunk); i++){
        
        sum += value[0]
        count += value[1]
    }
    
    return ("average_liquidity", sum/count)
}

廣義上來(lái)說(shuō)，可將開(kāi)發(fā)者定義和消費(fèi)zkMR proof的流程分為三步：

• 1）定義dataframe和computations：zkMR proof基于某dataframe來(lái)執(zhí)行，所謂dataframe是指一定范圍的區(qū)塊，以及這些區(qū)塊內(nèi)的特定memory slots。如上例中，dataframe是指流動(dòng)性求平均的區(qū)塊方位，memory slot對(duì)應(yīng)某DEX內(nèi)某資產(chǎn)的流動(dòng)性。
• 2）為batched storage生成證明 并 分發(fā)計(jì)算：zkMR proof會(huì)驗(yàn)證某特定dataframe input的計(jì)算結(jié)果。每個(gè)dataframe對(duì)應(yīng)某個(gè)特定的區(qū)塊頭。組委驗(yàn)證計(jì)算的一部分，每個(gè)proof必須證明現(xiàn)有底層狀態(tài)數(shù)據(jù)存在的同時(shí)，還需證明基于這些數(shù)據(jù)的動(dòng)態(tài)計(jì)算結(jié)果。如上例中，所謂的動(dòng)態(tài)計(jì)算設(shè)置求平均操作。
• 3）Proof verification：zkMR proof可提交并在任意EVM兼容鏈上驗(yàn)證（后續(xù)將支持更多的虛擬機(jī)）。

3.2 增加不可知傳輸層

zkMR proof（以及其他zk Big Data proof）的強(qiáng)大特性之一是其可實(shí)現(xiàn)傳輸層不可知。由于proof是基于初始的區(qū)塊頭input生成的，任何現(xiàn)有的傳輸層都可用于生成和relay zkMR proof。現(xiàn)有的傳輸層包含有;

• messaging protocol
• oracle
• bridge
• watcher/cron job
• 甚至untrusted or incentivized用戶機(jī)制

zkMR proof的靈活性可大幅增加鏈間state的表達(dá)性，而不需要與現(xiàn)有的高性能傳輸基礎(chǔ)設(shè)施競(jìng)爭(zhēng)。

Lagrange SDK提供了簡(jiǎn)單的接口來(lái)將zk Big Data proof集成進(jìn)任何現(xiàn)有的跨鏈messaging或bridging協(xié)議中。通過(guò)簡(jiǎn)單的函數(shù)調(diào)用，某協(xié)議可簡(jiǎn)單請(qǐng)求某指定區(qū)塊頭內(nèi)某特定dataframe的任意計(jì)算結(jié)果的proof。

當(dāng)與現(xiàn)有協(xié)議集成時(shí)，zkMR不設(shè)計(jì)為對(duì)用作proof input的區(qū)塊頭的有效性做assertion。通常當(dāng)傳輸消息時(shí)，傳輸協(xié)議可證明或斷言某區(qū)塊頭的有效性，也可額外包含基于某dataframe歷史狀態(tài)之上的動(dòng)態(tài)計(jì)算。

值得指出的是，zkMR proof還支持將多個(gè)鏈的proof合并為單個(gè)final computation。

4. zkMR性能改進(jìn)

現(xiàn)有的zkMR看起來(lái)要比傳統(tǒng)的線性計(jì)算更復(fù)雜，其性能可隨并行處理器/機(jī)器而水平擴(kuò)展，而不是隨時(shí)間垂直擴(kuò)展。

最大并行化情況下，證明某zk MapReduce流程的時(shí)間復(fù)雜度為$O(\log (n))$，而順序執(zhí)行需要的run-time為$O(n)$。

例如，計(jì)算以太坊區(qū)塊數(shù)據(jù)1天內(nèi)的平均流動(dòng)性。順序執(zhí)行需要循環(huán)6643 steps。具有recursive proof的分布式方式，僅需要單個(gè)map操作，高達(dá)6643個(gè)并行線程以及12個(gè)recursive reduction steps。從而可將rum-time復(fù)雜度reduce 約523倍。

對(duì)于擴(kuò)容方案間的state storage碎片，如app chains、app rollup L3s、alt-L2s，鏈上數(shù)據(jù)以指數(shù)級(jí)增長(zhǎng)并碎片化。很快就有關(guān)于：如何處理部署在100個(gè)不同app rollups上的某DEX的1周TWAP數(shù)據(jù)？

總之，zkMR是在分布式計(jì)算環(huán)境下、在zero-knowledge上下文中處理大規(guī)模數(shù)據(jù)集的強(qiáng)大范例。雖然順序計(jì)算在通用應(yīng)用程序開(kāi)發(fā)中效率很高，表達(dá)能力很強(qiáng)，但在分析和處理大型數(shù)據(jù)集時(shí)，它的優(yōu)化效果很差。分布式計(jì)算的效率使其成為主流Web2的許多大數(shù)據(jù)處理的標(biāo)準(zhǔn)。在zero-knowledge上下文中，可擴(kuò)展性和容錯(cuò)性使其成為處理不可信大數(shù)據(jù)應(yīng)用程序的理想支柱，如復(fù)雜的鏈上定價(jià)、波動(dòng)性和流動(dòng)性分析。

參考資料

[1] Lagrange Labs 2023年5月博客 A Big Data Primer: Introducing ZK MapReduce文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-489399.html

到了這里，關(guān)于區(qū)塊鏈?zhǔn)澜绲拇髷?shù)據(jù)入門之zkMapReduce簡(jiǎn)介的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！