(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210267172.X (22)申请日 2022.03.17 (71)申请人 北京工业大 学 地址 100124 北京市朝阳区平乐园10 0号 (72)发明人 詹静　赵江　李永震　 (74)专利代理 机构 北京思海天达知识产权代理 有限公司 1 1203 专利代理师 沈波 (51)Int.Cl. H04L 9/32(2006.01) (54)发明名称 一种基于Spark的高效分布式零知识证明方 法 (57)摘要 本发明公开了一种基于Spar k的高效分布式 零知识证明方法， 包括分布式计算轨迹算术中间 形式构建、 分布式边界约束算术中间形式构建、 分布式转移约束算术中间形式构建、 分布式组合 约束算术中间形式构建、 分布式证明生成。 该方 法所对应 的系统基于Python与PySpark实现， 在 Spark平台上运行， 能够有效的减少证明方所需 要的证明时间以及提高证明方能够处理的计算 规模， 从而让证明系统具有更高的效率与可用 性。 本方法的数据可用性证明能够让证明方在不 暴露数据本身明文信息的情况下， 高效的向验证 者证明数据在经过某些步骤的计算后， 得到某一 个输出。 将计算轨迹中相邻的中间值需要满足的 限制条件称为转移约束条件， 将最终的公开输出 称为边界约束条件。 权利要求书1页 说明书6页 附图3页 CN 114666061 A 2022.06.24 CN 114666061 A 1.一种基于Spark的高效分布式零知识证 明方法， 其特征在于： 包括分布式计算轨迹算 术中间形式构建、 分布式边界约束算术中间形式构建、 分布式转移约束算术中间形式构建、 分布式组合约束算 术中间形式构建、 分布式证明生成； 证明方法的输入为计算轨 迹、 转移约束条件、 边界约束条件； 所述分布式计算轨 迹算术中间形式构建根据输入的计算轨 迹得到算 术中间形式； 所述分布式边界约束算术中间形式构建根据输入的边界约束条件、 分布式计算轨迹算 术中间形式构建中得到的计算轨 迹的算术中间形式， 得到边界约束算 术中间形式； 所述分布式转移约束算术中间形式构建根据输入的转移约束条件、 分布式计算轨迹算 术中间形式构建中得到的计算轨 迹的算术中间形式， 得到转移约束算 术中间形式； 所述分布式组合约束中间形式构建根据分布式转移约束算术中间形式构建中得到的 转移约束中间形式、 分布式边界约束算术中间形式构建中得到的边界约束中间形式， 得到 组合约束中间形式； 分布式证明生成根据分布式组合约束中间形式构建得到的组合约束中间形式、 分布式 边界约束算术中间形式构建得到的边界约束算术中间形式、 分布式转移约束算术中间形式 构建得到的转移约束算 术中间形式， 生成最终的证明结果。 2.根据权利要求1所述的一种基于Spark的高效分布式零知识证明方法， 其特征在于： 根据计算轨迹计算得到对应的多项式， 记为轨迹多项式， 这里的轨迹多项式也就是计算轨 迹的算术中间形式。 3.根据权利要求1所述的一种基于Spark的高效分布式零知识证明方法， 其特征在于： 对边界商多项式与转移域多项式在某个作用域的所有点上求值， 然后对求值结果构建 merkle树， 根据merkle树的根节点值得到随机系数， 以这些随机系数为常量将边界商多项 式和转移商多项式组合在一起得到组合多项式， 组合多项式也就是组合约束的算术中间形 式。 4.根据权利要求1所述的一种基于Spark的高效分布式零知识证明方法， 其特征在于： 根据边界约束 条件得到边界多项式与边界域多项式， 然后用轨迹多项式和边界多项式的差 除以边界域多项式得到边界商多项式， 边界商多项式也就是边界约束的算术中间形式； 具 体的， 根据转移约束条件与轨迹多项式得到转移多项式， 然后根据轨迹多项式所在的作用 域求出转移域多项式， 然后用转移多项式除以转移域多项式得到转移商多项式， 转移商多 项式也就是转移约束的算 术中间形式。 5.根据权利要求1所述的一种基于Spark的高效分布式零知识证明方法， 其特征在于： 对组合多项式在某个作用域上进行求值， 对求值结果构建merkle树， 然后对求值结果进行 聚合将元素数量减少一半， 对减半后的值构建mer kle树， 然后再次减半并构建merkle树， 直 到元素数量为8； 对生 成的所有merkle树计算指定位置处的merkle路径； merkle路径与最后 的元素会成为证明的一部 分； 然后对边界商多项式对应的mer kle树与转移 域多项式对应的 merkle树计算指定位置处的mer kle路径， 将它们与组合多项式得到的所有mer kle路径组合 在一起， 然后就得到最终的证明结果。权　利　要　求　书 1/1 页 2 CN 114666061 A 2一种基于Spa rk的高效分布式零知识证明方 法 技术领域 [0001]本发明涉及一种分布式零知识证明方法， 尤其涉及一种基于Spark的高效分布式 零知识证明方法， 属于信息技 术领域。 背景技术 [0002]zkSTARK(Zero ‑Knowledge  Scalable  Transparent  ARguments  of Knowledge)是 一种零知识证明技术， 它使用户能够与第三方共享经过验证的数据或执行计算， 而无需将 数据或计算方法透露给第三方。 简单来说， 零知识证明技术可以证明某事是真实的， 而不必 透露它究竟证明了什么。 例如， zkSTARK允许Alice使用零知识密码证明来验证Bob的银行信 息， 而不需要Bob向Alice透露机密信息。 zkSTARK不需要第三方进行可信初始化， 具有更高 的安全性， 计算方式具备可扩展性。 但现有的zkSTARK实现只能运行在单机环境下， 存在如 下的问题： 1)受限于单机计算资源， 证明所需的时间较长； 2)受限于单机的内存， 无法处理 大规模计算。 发明内容 [0003]本发明的目的在 于提供一种适用于数据可用性证明的基于zkSTARK的高效分布式 零知识证明方法， 该方法所对应的系统基于Python与PySpark实现， 在Spark平台上运行， 能 够有效的减少证明方所需要的证明时间以及提高证明方能够处理的计算规模， 从而让证明 系统具有 更高的效率与可用性。 基于本发明方法的数据可用性证明能够让证明方在不暴露 数据本身明文信息的情况下， 高效的向验证者证明数据在经过某些步骤的计算后， 得到了 某一个输出。 例如， 证明者可以向验证者证明数据在经过哈希算法的计算后， 得到了一个公 开的哈希 值。 其中，“某些步骤的计算 ”以及“某一个输出 ”是证明者与验证者双方都知道的， 而数据本身以及数据在计算过程中的中间值是只有证明者知道的。 将数据在计算过程中的 中间值称为计算轨迹， 将计算轨迹中相邻的中间值需要满足的限制条件称为转移约束条 件， 将最终的公开输出称为 边界约束条件。 [0004]为达到上述目的， 本发明采用如下技 术方案： [0005]一种基于Spark的高效分布式零知识证明方法， 包括分布式计算轨迹算术中间形 式构建、 分布式边界约束算术中间形式构建、 分布式转移约束算术中间形式构建、 分布式组 合约束算 术中间形式构建、 分布式证明生成。 [0006]证明方法的输入为计算轨 迹、 转移约束条件、 边界约束条件。 [0007]所述分布式计算轨迹算术中间形式构建根据 输入的计算轨迹得到算术中间形式。 具体的， 根据计算轨迹计算得到对应的多项式， 记为轨迹多项式， 这里的轨迹多项式也就是 计算轨迹的算术中间形式。 [0008]所述分布式边界约 束算术中间形式构建根据 输入的边界约束条件、 分布式计算轨 迹算术中间形式构建中得到的计算轨迹的算术中间形式， 得到边界约束算术中间形式。 具 体的， 根据边界约束条件得到边界多项式与边界域多项式， 然后用轨迹多项式和边界多项说　明　书 1/6 页 3 CN 114666061 A 3