Lumino仪式技术解析（二）——仪式的意义

本文转载自微信公众号 PlatON Cross

作者： PlatON Cross

Lumino仪式已经接近尾声，用于零知识证明的参数也即将由所有正在参与、曾经参与过的用户们计算出来了。在《Lumino仪式技术解析（一）——椭圆曲线》我们知道，该仪式用到了两条椭圆曲线BN254和BLS12-381，那么接近60天多方参与的计算，其目的是要算出什么结果呢？多方参与的意义何在呢？本篇将通过尽量通俗的说明，给大家一个比较直观的理解。考虑与上一篇文章的衔接性，我们先从椭圆曲线在同态隐藏方面的应用讲起。

| 椭圆曲线与同态隐藏

设想这样一个形式化的场景，A宣称自己知道两个数α和β，A需要说服B，但又不想暴露a和b具体的值。B认为，他不需要知道α和β的具体值，但如果A能够告诉他γ=α+β的值，同时验证γ确实由a和b通过“+”操作得到，那么他就信任A。

大素数指数运算加法同态

最初的方案是大素数取模（模运算基础上的幂次），A使用一个很大的素数g，和另外一个数n，并公开g、n，同时将，以及γ的值公开，B可以通过验证和是否相等，来验证γ是否等于α+β。由于仅知道和g的值，反解α非常的困难（离散对数问题），因此通过这种方式，A可以在不泄露α、β真实值的情况下，让B相信A确实知道α和β的值。

这也是一种加法同态加密的实现，除了效率（大整数指数运算）问题以外，这种方式难以针对乘法运算来进行操作，那么就轮到椭圆曲线出场了。

椭圆曲线加法同态隐藏

在《Lumino仪式技术解析（一）——椭圆曲线》中我们提到，椭圆曲线上的“加法”运算是曲线上的打点，而倍乘操作：P=αG，是在基准点G上，进行α次打点以后得到的点P。同时，已知P、G的情况下，很难计算出α的值（同样是离散对数问题），这就意味着通过椭圆曲线上面的点，可以对α进行隐藏。

同时，椭圆曲线上的“加法”满足结合律和交换律，也就是说，αG+βG=(α+β)G成立，即A可以公开P=αG和Q=βG两个点，以及γ。B验证P+Q是否等于γG即可验证(α+β)是否等于γ，达到加法同态隐藏的效果。

椭圆曲线带来的好处是计算效率会有一定的提升，当然，更重要的是能够支持乘法同态隐藏。

椭圆曲线乘法同态隐藏

乘法同态隐藏需要用到一个非常巧妙的机制——“映射”（规范的说法叫双线性映射[1][2][3]），其示意图如下：

可以直观的理解为，椭圆曲线1中两个点P、Q，通过“乘法”运算（准确的讲，是通过有限域上的超椭圆曲线上的Tate[3]对或Weil[2]对来构造），能够映射成为椭圆曲线2中的的点R。

同时，他们之间有着类似“乘法”结合律、交换率那样的关系：

设P=αG1，Q=βG1，有R=P”*“Q=(α*β)G2，其中G1是椭圆曲线E1中的基点，G2是椭圆曲线E2中的基点。可以表示为：e(αG1, βG1) =αβ· e(G1, G1)，其通俗解释为：E1中点P、点Q“乘法”运算后，映射到E2中的点R，相当于E1中基准点G1和G1进行“乘法”运算“映射成”E2中的一个点，再由该点“打点”α·β次得到R点。（实际上，规范的写法，是e(g^α,g^β)，g^α表示在椭圆曲线中表示g点打点α次后的点，在这里写成αG1是为了与上一篇文章中的椭圆曲线有更好的衔接，在本文剩下的部分，将写成更加规范的g^α形式）。

这是一项非常酷的技术，就好像有限元宇宙中的两个元素，通过某种“运算”，能够“生成”平行元宇宙中的一个元素，它们之间有着类似“乘法”的联系。

有了以上工具，同时通过P点隐藏α，Q点隐藏β，设γ=α·β，就可以通过验证P”*“Q是否等于G1”*”γG1，来验证α·β是否等于γ，即A可以在隐藏α、β的前提下，让B相信A确实掌握了α、β的值。

| 零知识证明与椭圆曲线

零知识证明可以在不泄露信息本身的前提下，使别人相信自己确实掌握了信息，同态隐藏恰好能够完成这一点，但在实际应用中，同态隐藏的基本形式太简单了，难以代表形式更加复杂的实际问题，因此在零知识证明中，引入了适用性更强的机制。通俗的讲，如果能够将一个实际问题，能够经过一系列变换，转换成一个多项式问题[4]，那么就能用于构造零知识证据，对于这个方面内容的详细讲解，稍稍超出了本系列的目的范畴，后续有机会将开新的专题来详细说明。在这里只需知道，通过多项式可以代表更加复杂的实际情况即可。

零知识证明与多项式

现在我们假设已经将一个实际问题包含的信息，转换到了一个形如 的多项式中，而多项式是由其系数 决定的。再对问题进行简化，设f(x)可因式分解为f(x)=h(x)t(x)，在零知识证明中，t(x)公开，同时问题被转化为：A要向B证明A知道某个信息，仅需向B证明其知道一个可以整除t(x)的多项式。

我们还是从基于大素数指数取模运算的方法讲起，这种方式比较直观，其设计思路如下：

1. （初始化阶段）大素数g、t(x)的表达式公开；
2. （初始化阶段）Verifier选择随机数x=s，以及配对随机数α，公开 ，以及对应的“偏移”数 ，s和α的值仅Verifier知道；
3. （证明阶段）Prover：a. 根据只有他自己知道的f(x)表达式，以及h(x)，计算：
   
   
   b. 同时计算：c. 将 发送给Verifier。
4. （验证阶段）Verifier：a. 验证： 是否等于 ，这是因为Verifier掌握了s的值，可计算出t(s)的值进行上述验证；
   b. 验证： 是否等于 ，这是因为Verifier掌握了α的值。

说明：

1. 由于s、α的值仅Verifier知道，因此Prover只能是在真实知道f(x)表达式的前提下，才能通过、构造出的值来；
2. 由于Prover仅提供了的值，Verifier除非通参数暴力破解，否则很难获知f(x)的具体表达式；
3. t(s)是为了保证A提供的是一个可以整除t(x)的多项式，α“偏移”是为了保证A在计算证据时，确实用的是多项式在进行计算；
4. 因为s、α的值不能暴露给Prover知道，因此每个Verifier在进行验证时，需要独立生成自己认可的值，每次证明和验证，都需要各个Verifier与Prover进行一轮单独的交互。

然而，这种方式（这是一种交互式零知识证明）存在以下问题：

1. 由于不支持乘法同态隐藏，α以及t(s)的值是需要验证者一直保存着的，那么就造成了对验证者进行攻击来获取α、t(s)以伪造证明的可能性；
2. Verifier与Prover可以串通好，伪造证明；
3. Verifier实际上可以通过暴力破解的方式，计算出多项式的各个系数[5]（由于α、s对验证者来说是已知的，同时毕竟很多实际问题转化成的多项式的系数组合并不算很多）。

基于椭圆曲线实现零知识证明

如果完全隐藏上文中α、s的值，想要完成零知识证明过程，需要用到上文中提到的乘法同态隐藏，也就是要用到上文中提到的映射（即双线性映射）方法。有了这样的“神器”以后，零知识证明的设计思路可进化成如下形态（下面我们采用较为规范的标识进行表述，即 代表椭圆曲线上以g为基点打点α次， 代表“映射”）：

1. 可信“第三方”，基于任何人都不可知的随机数s、α，生成两组公开参数，即CRS（common reference string）：
   a. Prover key： ；
   b. Verifier key： ；
2. Prover：
   a. 根据计算出椭圆曲线E1上的点 ， ；
   b. 根据计算出椭圆曲线E1上的点 ；
   c. 公开E1上的点p、h、p’；
3. Verifier：
   a. 根据E1上的点 ，验证映射到椭圆曲线E2上的点 是否等于 ，以验证f(s)==t(s)·h(s)是否成立；
   b. 根据E1上的点 ，验证映射到椭圆曲线E2上的点 是否等于 ，以验证与“偏移”方式是否一致。

在这种方式下，不论是证明者还是验证者，都无需知道α、s（不知道s的值肯定不知道t(s)的值）的具体值，仅需要知道椭圆曲线上的点： ， ， 即可完成证明以及验证，这些参数被称为CRS。

然而，这些参数需要通过可信的方式生成和公开，传统方法需要一个可信的“第三方”，这就带来了中心化的风险，规避这种风险的方法，就是在下一节中将要介绍的，Lumino仪式的意义所在。有了这些参数，证明者提供椭圆曲线E1上的点 ，验证者即可完成验证，所有CRS只需要公开一次即可，这也是这种方式被称为非交互式的原因。

| 安全多方算出了什么

从上文中基于椭圆曲线的非交互式零知识证明的实现方式上可以看到，连接证明者、验证者的关键信息为CRS，这个信息需要通过可信的方式生成和公开。一种方式是中心化的方式，通过一个可信的第三方来生成，在区块链领域并不适合；另外一种方式就是Lumino仪式中，所提到的通过安全多方计算的方式来实现，简单的讲，就是s、α的值由多人参与生成，但每个人不知道其他人的“部分”是多少，例如，假设参与者有A、B、C三个人：

1. A计算并发布CRS值： ;
2. B在A的基础上计算并发布： ；
3. C在B的基础上计算并发布： 。

最终C发布的值作为公开CRS。由于A、B、C都只发布了 形式的值，所以对于每个参与者生成的s、α值，其他人都是不可知的。在这种模式下，也正是由于s、α不可知，导致这种形式存在一个问题，最后一个参与者，可以无视前面所有参与者提供的数据，仅通过自己生成的s、α来提供CRS。因此，需要一种验证机制，保证每个参与者（除了第一个人）公开的CRS，是基于前人的结果计算出来的。其实验证机制比较简单，只需要除了第一个以外，其他人在公布CRS的基础之上，再公开其自身的一些信息即可，例如：

1. A计算并发布CRS值： ;
2. B在A的基础上计算并发布： 、 ；
3. C在B的基础上计算并发布： 、 。

例如对B发布的信息，验证方法为：验证 是否等于 即可验证 是否是基于A发布的信息生成的了，其他两项类似。

Lumino活动过程中，为大家提供了各个参与者计算结果的下载途径，就是为了所有人都可以对参与者的计算结果进行验证，任何作弊的参与者，都会被揭发。

通过这种方式，只要所有参与仪式的人，有一个参与者是诚实的（即没有把自己的参数告诉其他参与者），那么生成的CRS，对于所有的人来说，α、s都是不可知的，这样该零知识证明系统就能够具备较高的可信度了。

总结

以上便是关于Lumino仪式目的和意义的讲解，PlatON的隐私计算技术体系，提供了安全多方计算、同态加密这样非常重要的隐私计算基础设施，其实该仪式也是PlatON安全多方计算、同态加密的一个非常重要的应用落地。

同时，其中涉及到零知识证明和椭圆曲线的部分，只向大家进行了简单的科普性说明，为了表述的更加直观，忽略了众多需要专业化、规划化的描述，望专业人士海涵，后续有机会将开辟新的专题为大家带来更加深入的讲解。

参考文献

[1] P.S.L.M. Barreto, H.Y. Kim, B.Lynn, and M.Scott, Efficient algorithms for
pairing-based cryptosystems, Crypto 2002, LNCS 2442, pp.354-368, SpringerVerlag, 2002.
[2] D. Boneh, B. Lynn, and H. Shacham, Short signatures from the Weil pairing,
Asiacrypt 2001, LNCS 2248, pp.514-532, Springer-Verlag, 2001.
[3] S. D. Galbraith, K. Harrison, and D. Soldera, Implementing the Tate pairing,
ANTS 2002, LNCS 2369, pp.324-337, Springer-Verlag, 2002.
[4]Quadratic Span Programs and Succinct NIZKs without PCPs .https://eprint.iacr.org/2012/215.
[5]http://petkus.info/papers/WhyAndHowZkSnarkWorks.pdf