大数据入门：介绍 ZK MapReduce

跨链互操作性的未来将围绕多链 dapps 之间动态且数据丰富的关系构建。Lagrange Labs 正在构建粘合剂，以帮助安全地扩展基于零知识证明的互操作性。

ZK 大数据栈：

Lagrange Labs ZK 大数据栈是一种专有的证明构造，优化用于与任意动态分布式计算_并发_生成大规模批量存储证明。ZK 大数据栈可以扩展至任何分布式计算框架，范围从 MapReduce 到 RDD 再到分布式 SQL。

使用 Lagrange Labs ZK 大数据栈，可以从一个单一的区块头生成证明，证明在任意深度下一系列历史存储槽状态以及在这些状态上执行的分布式计算的结果。简而言之，每个证明将存储证明的验证_和_可验证分布式计算结合在一个步骤中。

在本文中，我们将讨论 ZK MapReduce (ZKMR)，这是 Lagrange ZK 大数据栈中的第一个产品。

理解 MapReduce：

在传统的顺序计算中，单个处理器按照线性路径执行整个程序，每个指令按照在代码中出现的顺序依次执行。使用 MapReduce 和类似的分布式计算范例如 RDD，计算被分割成多个小任务，可以在多个处理器上并行执行。

MapReduce 通过将大型数据集分解为较小的块并将其分布在一群机器上来工作。大致来说，这种计算遵循三个不同的步骤：

1. Map: 每台机器在其数据块上执行一个 map 操作，将其转换为一组键值对。
2. Shuffle: map 操作生成的键值对被_洗牌_并按键排序。
3. Reduce: 洗牌的结果被传递到一个 reduce 操作，该操作聚合数据并生成最终输出。

MapReduce 的主要优势在于其可扩展性。由于计算分布在多台机器上，它能够处理顺序处理不可行的大规模数据集。此外，MapReduce 的分布式特性允许计算在更多机器上_横向_扩展，而不是在计算时间上_纵向_扩展。

传统 MapReduce 程序执行

分布式计算范式如 MapReduce 或 RDD 通常用于 Web 2.0 架构，以处理和分析大型数据集。大多数大型 web 2.0 公司，如谷歌、亚马逊和 Facebook，都大量利用分布式计算来处理 PB 级别的搜索数据和用户数据集。现代分布式计算框架包括 Hive、Presto 和 Spark。

ZK MapReduce 简介：

Lagrange 的 ZK MapReduce (ZKMR) 是 MapReduce 的一种扩展，利用递归证明来证明在大量链上状态数据上的分布式计算的正确性。这是通过生成针对给定 worker 在分布式计算作业的 map 或 reduce 步骤中的计算正确性的证明来实现的。这些证明可以递归组合，以构建整个分布式计算工作流的有效性证明。换句话说，较小计算的证明可以组合成一整个计算的证明。

将多个 worker 计算的 子证明 组合成一个 ZKMR 证明的能力，使其能够在大型数据集的复杂计算中有效地进行扩展。

在零知识中验证任意 MapReduce 过程

与零知识虚拟机 (ZKVMs) 相比，ZKMR 的一个主要优点是能够在当前和历史合约存储状态之上执行动态计算。而不仅仅是在多个区块中分别证明存储的包含性然后再在聚合数据集上证明一系列计算，ZKMR（及其他 Lagrange ZK 大数据产品）支持将两者组合成一个单一证明。这显著缩短了生成 ZKMR 证明的证明时间，与其他设计相比。

ZK MapReduce 的实际应用：

为了理解如何组合递归证明，我们考虑一个简单的示例。假设我们希望计算一段时间内 DEX 上一个资产对的平均流动性。对于每个区块，我们必须显示对状态根的包含证明的正确性，证明该 DEX 中有多少流动性。接下来，我们必须在每个区块中对所有流动性进行求和，并除以区块的数量。

顺序计算看起来如下：

## 顺序执行
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 avg_liquidity
}

虽然这个计算在直观上似乎简单明了，但随着需要包含的状态量的增加，其性能会迅速下降。考虑下面的表，显示在特定时间范围内每条链的区块数量。到极限情况，在 Arbitrum 上计算一个 DEX 的平均流动性一个月需要来自超过 6500 万个 rollup 区块的数据。

与 ZKMR 相比，我们可以将数据集分为较小的块，并将其分布到多个处理器上。每台机器将执行一个 map 操作，计算 Merkle-Patricia Trie (MPT) 证明并对其数据块的流动性进行求和。map 操作然后生成一个键值对，其中键是一个常量字符串（例如 _averageliquidity），值是包含总和和计数的元组。

map 操作的输出将是一组可以根据键进行洗牌和排序的键值对，然后传递给 reduce 操作。reduce 操作将接收一个键值对，其中键是 _averageliquidity，值是包含每个 map 操作的流动性总和和计数的元组列表。reduce 操作将通过对单个的总和和计数进行求和，然后通过最终总和除以最终计数来聚合数据，以计算整体平均流动性。

## Map 步骤
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 步骤
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)
}

广泛来讲，我们可以将定义和消费 ZKMR 证明的过程总结为以下三个步骤：

1. 定义数据帧和计算：ZKMR 证明是针对某个 数据帧 执行的，该数据帧是区块范围及特定内存槽。上述示例中，数据帧将是对流动性进行平均的区块范围和与资产的流动性相对应的内存槽。
2. 证明批量存储和分布式计算：ZKMR 证明验证在特定数据帧输入上执行的计算结果。每个数据帧是针对特定区块头定义的。在验证计算的过程中，每个证明必须证明基础状态数据的存在以及在其上运行的动态计算的结果。在上述示例中，这将是一个平均操作。
3. 证明验证：ZKMR 证明可以在任何 EVM 兼容链上提交和验证（未来将支持更多虚拟机）。

使用一系列顺序区块的数据帧生成 ZKMR 证明

传输层无关的证明：

ZKMR 证明（和其他 ZK 大数据证明）的一个强大特性是其能够与传输层无关。由于证明是相对于初始区块头输入生成的，任何现有的传输层都可以选择生成和中继这些证明。这包括消息传递协议、预言机、桥接、观察者/定时任务，甚至不受信任或有激励的用户机制。ZKMR 证明的灵活性使它们能够大幅增加状态在链之间使用的 表达性，而不需要与现有和高性能的传输基础设施竞争。

ZKMR 证明的传输层无关中继和验证

Lagrange SDK 提供了一个简单的接口，以将 ZK 大数据证明集成到现有的跨链消息或桥接协议中。通过一个简单的函数调用，协议可以轻松请求特定区块头中包含的某个数据帧上任意计算的结果证明。

在与现有协议进行集成时，ZKMR 的设计并未针对锚定证据的 有效性 对所使用的区块头进行断言。传输协议可以如通常传递信息那样证明或断言区块头的有效性，但现在还可以包括在历史状态的数据帧上方的动态计算。

值得注意的是，ZKMR 证明还支持将来自多个链的证明_合并_为一个最终计算。

ZKMR 的效率改进：

虽然 ZKMR 方法似乎比传统的顺序计算更复杂，但其表现随着并行进程/机器的数量_横向_扩展，而不是_纵向_延伸时间。

在最大并行处理时，证明 ZK MapReduce 过程的时间复杂度为 O( log(n))，而顺序执行的时间复杂度为 O( n)。

作为示例，考虑计算为期 1 天的 Ethereum 区块数据的平均流动性。顺序执行将需要 6,643 步的循环。分布式方法通过递归证明则只需要一个 map 操作和多达 6,643 个并行线程，然后进行 12 次递归减法步骤。这是大约 ~523 倍的运行时间复杂度降低。

随着我们继续在应用链、应用聚合 L3 以及替代 L1 等可扩展性解决方案中分割状态存储，链上数据的创建量只会呈指数增长和碎片化。问题很快可能变成，处理多少数据才能计算在 100 个不同应用聚合上的 DEX 的为期一周的 TWAP？

总之，ZKMR 是一种强大的范例，用于在零知识上下文中跨分布式计算环境处理大规模数据集。尽管顺序计算在通用应用开发方面效率高且表现优异，但它在对大型数据集的分析和处理方面却没有得到很好的优化。分布式计算的效率使其成为 Web2 中占主导地位的大数据处理的标准。在零知识的上下文中，可扩展性和容错性使其成为处理无信任大数据应用（如复杂的链上定价、波动性和流动性分析）的理想基础。

联系我们：

想了解更多关于 Lagrange 的信息？

访问我们的网站 https://lagrange.dev 并关注我们的 Twitter @lagrangedev，获取最新动态。

• 原文链接： medium.com/@lagrangelabs...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～