用于去信任零知识或有支付的计算机实现的系统及方法
技术领域
本说明书总体上涉及适用于在计算机处理器(例如，区块链网络的节点)或成组的此类处理器中实施的计算机实现的方法和系统。提供了一种生成证明的改进方法，该方法能够实现对语句(statement)的有效零知识验证。该方法适用于并入到现有的针对不需要使用双线性配对友好椭圆曲线的电路可满足性的基于离散对数的零知识证明协议中。本发明特别适合于但不限于数据的去信任公平交换。各方之一可以在不透露所述语句的情况下证明知道密钥或语句，以便在所述参与者之间产生安全的去信任交换。特别地，交换的数据能够实现为区块链网络上的指定虚荣地址(vanity address)确定私钥。
背景技术
在本文献中，术语“区块链”用来包括所有形式的电子的、基于计算机的、分布式的账本。这些包括基于共识的区块链和交易链技术、被许可的和未被许可的账本、共享账本及其变型。尽管已经提出并开发了其他区块链实现，但是区块链技术最广为人知的应用是比特币帐本。
尽管为了方便和说明的目的在本文中可能提及比特币，但是应当注意，本发明不限于与比特币区块链一起使用，并且替代的区块链实现和协议落入本发明的范围内。术语“用户”在本文中可以指基于人类或基于处理器的资源。区块链是一种点对点的电子帐本，其被实现为基于计算机的去中心化的、分布式系统，该系统由区块组成，该区块又由交易组成。
每个交易是一个数据结构，该数据结构对区块链系统中的参与者之间的数字资产的控制权的转移进行编码，并包括至少一个输入和至少一个输出。每个区块都包含前一个区块的哈希值，以使得区块被链接在一起来创建自区块链建立以来就已经被写入到该区块链的所有交易的永久、不可更改的记录。交易包含被称为嵌入到交易的输入和输出中的脚本的小程序，这些小程序指定如何以及谁可以访问交易的输出。在比特币平台上，这些脚本是使用基于堆栈的脚本语言编写的。
此外，在该文献中，参考了已知的零知识证明协议的结构和使用算术电路的系统。区块链提供了一种去中心化且无需许可的全局机制，该机制实现了一种能够在无需第三方仲裁或托管的情况下解决两个互相去信任方之间的公平交换问题的方案。针对经济报酬的或诸如数字商品之类的信息的交换中的数据或信息的公平交换被体现在称为零知识或有支付(ZKCP)[Maxwell 2016]的交易协议中。在ZKCP中，仅当确认支付的情况下，指定的数据才从卖方转移到买方，并且仅当指定的数据根据销售条件有效时，才完成从买方到卖方的支付。这种协议的细节是已知的[Campanelli 2017]，但是它本质上基于哈希时间锁定合约(HTLC)与零知识证明的结合，其同时验证某些加密信息(“数字商品”)是有效/正确的，并且验证解密此信息的“密码”是必须在区块链上透漏才能要求支付的数据。
ZKCP协议的中心组成部分是针对有关数据/信息有效性或正确性、密钥有效性及其对应的哈希值的一系列从属语句的零知识证明。这种复杂的复合语句需要用于通用计算的有效零知识证明系统：本质上，这使得一方能够运行带有秘密输入的任意程序，并且然后向另一方证明该程序接受了输入为有效的并且该程序被正确地执行—无需透露有关秘密输入或程序执行的任何信息。在已知的ZKCP示例中，采用的通用零知识证明系统已经基于Pinocchio协议[Parno 2016]和C++libsnark库[Libsnark 2016]中实现的简洁的非交互式知识论证(SNARKs)框架。零知识SNARK(zkSNARK)提供了一种以零知识来证明任意计算的有效性的方法，该任意计算可以表示为算术电路。zkSNARK的两个主要区别性质是它们是非交互性的(证明者一口气将证明发送给验证者)和简洁的(证明很小且易于验证)。但是，它们具有明显的局限性：
-证明生成对计算的要求极高。
-证明密钥非常大，并且与电路大小成比例。
-它们取决于强大且未经测试的加密假设(即，对指数假设和基于配对的假设的了解)。
-对于任何给定的程序(电路)，它们都需要由必须被信任的第三方计算的公共参考字符串(CRS)以删除设置参数。知道设置参数的任何一方都有能力创建伪造的证明。
迄今为止，尚未尝试构造zkSNARK来证明涉及任意加密椭圆曲线密钥操作的语句，但是假设该zkSNARK将由具有数十万或数百万个门的算术电路组成，并且因此，证明生成时间将花费几分钟，并且证明密钥的大小将达到数百兆字节。
技术背景
交互式零知识证明的基本系统可以使用∑(Sigma，西格玛)协议，该协议包括证明者与验证者之间的许多通信步骤。通常，∑协议包括3个移动：证明者向验证者发送初始承诺(a)，然后验证者以随机挑战(x)进行响应，并且最后证明者以最终响应或“公开(opening)”(z)进行回答。然后，验证者基于成绩单(transcript)(a，x，z)接受或驳回语句。
∑协议可用于证明知道仅证明者知道的见证(w)或证明有关仅证明者知道的见证(w)的语句。如果除去与见证有关的语句为真的事实之外未向验证者透漏有关见证或秘密的任何信息，则该协议为零知识[Bootle 2015]。
许多交互式零知识协议的核心是承诺方案，其被用于算术电路可满足性。承诺使得证明者能够提前对秘密值进行承诺，并且再后来可验证地透露(公开)秘密值。承诺方案具有两个主要性质。首先，它是隐藏的-承诺将值保密。其次，它是绑定的-仅公开对于原始承诺的值的承诺。佩德森承诺(Pedersen commitment)[Bootle 2015]方案涉及两个椭圆曲线生成器点：各方都知道的素数阶p的组
Com(s，r)＝s×G+r×F
其中，×表示椭圆曲线点乘。
承诺者可以在后期阶段通过提供值s和r来完全公开该承诺(即，该承诺可以被验证)。承诺者还可以响应于作为∑协议的一部分的特定挑战值来公开承诺，而无需透露秘密s或随机数r。
Pedersen承诺是加法同态的，这意味着(在椭圆曲线上)将两个承诺相加会导致对承诺的值之和的承诺，即：
(s1×G+r1×F)+(s2×G+r2×F)＝(s1+s2)×G+(r1+r2)×F
算术电路可满足性的证明可以在“零知识”中实现。算术电路(在域
每个门具有两个输入线和一个输出线，并对输入执行乘法(×)或加法(+)运算。图1a示出了具有左侧线输入(wL)和右侧线输入(wR)以及一个线输出(wO)的乘法门的示意图，而图1b示出了简单的算术电路的示意图，该简单的算术电路具有三个门、三个输入线((w1、w2、w3)、一个输出线(w6)和两个内部线(w5、w6)。
实际上，完整的电路具有限定外部(电路)输入值和输出值的自由输入线和自由输出线。合法赋值(legal assignment)是将线的值限定为满足电路的那些值，即，向每个线赋予一个值，在这里，每个门的输出正确地对应于输入的乘积或和(即，门是一致的(consistent))。
对于给定的算术电路，证明者可以通过以下方式在无需透露线值的情况下向验证者证明他们知道该电路的合法赋值：首先承诺合法赋值中的每个线值(使用Pedersen承诺)，然后对于电路中的每个门(它们可以被并行执行)、利用线值作为见证与验证者执行特定的∑协议。这些∑协议利用了Pedersen承诺的同态性质，如下所述。
为了产生证明(电路得到满足的证明)，最初，证明者对电路中的每个线wi生成承诺(i＝1，...，n，其中，n是线的数量)，并将其发送给验证者：
Wi＝Com(wi，ri)
对于电路中的每个“加法”门(图1b中示出了一个)，执行∑zero协议：这涉及(以零知识)证明wL+wR-wO＝0(即，加法门得到满足：输入线wL和wR等于输出线wO)。这包括以下步骤：
1.证明者生成对零的承诺：B＝Com(0，rB)，并将其发送到验证者。
2.验证者以随机挑战值进行响应：
3.然后证明者计算公开值(opening value)：z＝x(rL+rR-rO)+rB并将其发送给验证者。
4.作为wL+wR-wO＝0的证明，验证者检查Com(0，z)＝x×(WL+WR-WO)+B
B表示曲线点，类似于公钥；B＝r x F+0x G
rB表示对应配对的私钥。
对于每个“乘法”门(如图1a所示)，执行∑prod协议：这涉及对于每个乘法门证明(以零知识)wL·wR＝wO(即，乘法门得到满足)。
1.证明者生成5个随机盲值：
2.证明者计算C1＝Com(t1，t3)、C2＝Com(t2，t5)和C3＝t1×WR+t4×F，然后将它们发送给验证者。
3.验证者以随机挑战值进行响应：
4.证明者计算公开值：
e1＝wLx+t1
e2＝wRx+t2
z1＝rLx+t3
z2＝rRx+t5
z3＝(rO-wLrR)x+t4
并将它们发送给验证者。
5.然后作为wL·wR＝wO的证明，验证者检查以下等式：
Com(e1，z1)＝x×WL+C1
Com(e2，z2)＝x×WR+C2
e1×WR+z3×F＝x×WO+C3。
∑zero协议和∑prod协议可以并行运行以验证电路中的每个门，并且相同的验证者挑战值(x)可以被用于所有门。
例如，考虑图1b中的电路：为使证明者以零知识向验证者证明他们知道合法赋值(即，线值满足电路)，证明者最初向验证者发送针对每个门的线承诺(W1，...，W6)和∑协议承诺(这是对于每个加法门的一个附加承诺和对于每个乘法门的五个)。
然后，验证者以随机挑战进行响应
w1·w2＝w4
w4·w5＝w6
w2+w3＝w5
并且因此，承诺W1，...，W6对应于满足的线值w1，...，w6。
如果证明者想展示，除了满足电路之外，特定的线还具有特定的值，则他们可以完全公开对相关线的承诺。在该示例中，证明者可以附加地向验证者发送值w6和r6(然后验证者可以确认W6＝Com(w6，r6))，以演示w6是来自特定合法赋值的实际输出。
图1b中的示例是平凡电路(trivial circuit)。实际上，有用的电路由更多的门组成。特别令人感兴趣的是用于SHA-256哈希函数的算术电路-该电路使得证明者能够在没有透露原像(pre-image)的情况下演示他们知道对特定(输出)值进行哈希化的SHA-256函数的原像(输入)。SHA-256算法的电路的最有效实现方法之一由27,904个算术门组成[Zcash 2016]。然后为了证明知道SHA-256原像，将需要发送上述协议的初始承诺和公开回合(opening round)二者中的大约5MB的数据，并且对于证明者和验证者二者都需要大约200,000个椭圆曲线运算(每次处理器需要几秒钟的时间)。
已经开发出几种方法来显著地改善用来证明算术电路可满足性的并行∑协议方法的性能。已知的方法[Bootle 2016][Groth 2009]涉及对电路线值的承诺进行批处理，以大幅减少必须从证明者发送给验证者的数据的大小(即，降低通信复杂性)。这些方法实现了通信复杂度从
再次，作为证明同一SHA电路的可满足性的比较，协议[Bootle 2016]的证明密钥的大小仅为5KB，并且密钥生成时间为180ms。证明大小为24KB，并且需要大约4秒钟才能生成，并且证明也需要大约4秒钟进行验证。
除了阐述在下面的步骤中描述采用的主要矢量(vector)批处理协议之外，此处没有完整描述这些方法。这遵循与标准Pedersen承诺相同的性质，但是对n个元素(m＝m1，...，mn)进行承诺仅需要发送单个组元素：
1.证明者和验证者就组元素达成一致
2.证明者生成n个随机数
3.证明者计算点Ki＝xi×F(for i＝1，...，n)。这些值形成发送给验证者的证明密钥PrK。
4.证明者生成随机值：
5.证明者计算承诺：
并将其发送给验证者。
发明内容
总体而言，本发明在于一种用于实现语句的零知识证明或验证的计算机实现的方法。证明者可以使用本文的方法向验证者证明语句为真，同时将针对该语句的见证保密。
特别地，见证可以是访问数据，当获取到该访问数据时，使得验证者能够访问由见证保护的数据。可以使用区块链网络及其功能来保护受保护的数据。更特别地，见证可以是访问数据，其使得能够确定区块链网络上的指定虚荣地址的私钥。
这些语句是复合语句，其同时涉及算术电路可满足性和有关公钥的有效性的从属语句(密钥语句证明)两者。
本文的方法可以被用在电路可满足性的已知协议中，例如现有的基于离散对数的零知识证明协议中。该方法特别适合不需要使用双线性配对友好椭圆曲线的协议。
在该方法中，证明者向验证者发送包括语句的数据集，该语句是对于给定的功能电路输出和椭圆曲线点，功能电路输入等于对应的椭圆曲线点乘数(multiplier)。该语句可以是证明者知道区块链网络上的指定虚荣地址的私钥。
数据包括针对语句的电路的各个线承诺和/或成批的承诺、输入和输出。证明者可以将语句中使用的该椭圆曲线或每个椭圆曲线的规范包括在数据中，或者已经提前共享语句中使用的该椭圆曲线或每个椭圆曲线的规范。然后，响应于来自验证者的挑战，证明者发送公开。备选地，证明者附加地包括证明密钥。
利用从证明者接收到的数据，验证者能够确定电路得到满足并验证语句，由此确定证明者持有对语句的见证。还可以计算椭圆曲线点。在接收到数据时，验证者通过计算来确定数据符合该语句。本发明特别适合于哈希原像和椭圆曲线私钥的等效的零知识证明。
因此，根据本发明，提供了如所附权利要求书中限定的方法和系统。
因此，期望提供一种计算机实现的方法，该方法是用于在来自卖方或证明者的访问数据的交换中实现来自买方或验证者的奖励数据的去信任零知识或有支付或交换的计算机实现的方法。奖励数据可以是与支付相关联的数据，例如未花费的交易输出(UTXO)的分配。访问数据可以是来自EC密钥对的秘密密钥或提供对来自EC密钥对的秘密密钥的访问。总体而言，该方法使得验证者能够证明他们拥有所请求的数据。
可以提供一种计算机实现的方法，其用于在来自卖方或证明者的访问数据的交换过程中实现来自买方或验证者的奖励数据的去信任零知识或有支付或交换，该方法包括：
从买方接收买方公钥(pkB)，该买方公钥(pkB)是从将买方秘密密钥(skB)与椭圆曲线生成器点(G)相乘导出的；
生成卖方公钥(pks)，该卖方公钥(pks)是从将卖方秘密密钥(i)与椭圆曲线生成器点(G)相乘确定的，其中，卖方秘密密钥是访问数据或用于保护买方所需的访问数据；
准备数据集并将数据集发送给买方，所述数据集包括零知识证明语句，其是对于表示该语句的算术电路的给定功能电路输出和椭圆曲线点，功能电路输入等于卖方秘密密钥(i)，其中，所述语句使得买方能够确定电路得到满足并且验证该语句，由此确定卖方拥有解锁访问数据所需的卖方秘密密钥；
从买方接收第一交易Tx1，该第一交易Tx1包含将奖励数据分配给买方的输出，该奖励数据是使用卖方秘密密钥(i)可访问的；
在区块链上签署和广播第一交易，以便第一交易被挖掘成区块，并通过提供第二交易Tx2来访问来自第一交易Tx1的输出的奖励数据，该第二交易供应卖方秘密密钥(i)以解锁奖励数据，然后该奖励数据被透漏在区块链上，从而使得买方能够获得由卖方提供的访问数据。
该方法包括：从买方接收买方公钥，该买方公钥是从将买方秘密密钥与椭圆曲线生成器相乘而导出的。该买方公钥可以是用于保护访问数据或维护访问数据或秘密密钥的机密性的“种子”。该方法还包括：生成从将卖方秘密密钥与椭圆曲线生成器相乘而确定的卖方公钥，其中，卖方秘密密钥是访问数据或用于保护买方所需的访问数据。此外，该方法包括：准备数据集并将其发送给买方，所述数据集包括零知识证明语句，其是对于给定功能电路输出和椭圆曲线点，功能电路输入等于卖方秘密密钥，其中，所述语句使得买方能够确定电路得到满足并且验证该语句，从而确定卖方持有解锁访问数据所需的卖方秘密密钥；从买方接收第一交易Tx1，该第一交易Tx1包含向买方分配奖励数据的输出，该奖励数据是使用卖方秘密密钥可访问的。秘密密钥可以是电路功能输入。最后，该方法包括：在区块链上签署和广播第一交易，以便第一交易被挖掘成区块，并通过提供第二交易Tx2来访问来自第一交易Tx1的输出的奖励数据，该第二交易供应卖方秘密密钥(i)以解锁奖励数据，然后该奖励数据被透漏在区块链上，从而使得买方能够获得卖方提供的访问数据。验证者除提供卖方秘密密钥外，还可以提供其签名。
该方法可以由证明者或卖方使用以实现针对访问数据(例如，加密密钥)的零知识或有交易。证明者可以与验证者或买方保持联系，以确认要提供的奖励数据和要接收的访问数据，并与验证者建立通信信道。该通信信道可以是公开的。
证明者或卖方可以从验证者或买方接收椭圆曲线公钥pkB，所述卖方已经从安全的随机秘密密钥skB生成所述公钥，其中
pkB＝skB×G，并且G为椭圆曲线，并且
证明者或卖方可以确保要为访问数据提供锁定值i，以使得
访问数据＝pkB+i×G
并且卖方可以将其公钥pkS和来自功能电路的输出f(i)包括在发送给买方的数据集中，其中，pkS＝i×G，并且功能电路输入是锁定值i。
证明者或卖方可以将语句(S)证明发送给验证者或买方，该语句(S)证明向验证者证明功能电路的输入是对应于pkS的私钥。这使得验证者能够验证该证明，并确认对应于pk＝pkV+pkP的地址与商定的模式匹配，从而确定知道锁定值i能够导出访问数据的完整私钥(skB+i)，并且锁定值i是到功能电路i的功能电路输入。
卖方可以从买方接收交易Tx1，该交易Tx1包含输出，该输出包含要接收的奖励数据，该奖励数据可以通过来自卖方的签名和功能电路输入i来访问，并且卖方可以在交易被挖掘成区块的区块链上签署和广播交易，使得通过提供第二交易Tx2卖方能够从交易Tx1的输出获得访问数据，该第二交易Tx2提供其签名和值i以解锁交易，然后该交易被透漏在区块链上，从而使得买方能够识别锁定值i并获得卖方提供的访问数据，其中
sk＝skB+i，
其中，pk＝sk×G.
从买方或验证者的角度，同样希望提供一种补充的计算机实现的方法，以使本发明的方法扩展到验证者以插头-插座的方式(in a plug-socket manner)进行的对等的(reciprocal)动作。本发明扩展到证明者和验证者之间的全面合作。
因此，本发明还在于一种计算机实现的方法，该方法用于在来自卖方或证明者的访问数据的交换过程中实现来自买方或验证者的奖励数据的去信任零知识或有支付或交换，该方法包括：向卖方发送买方公钥，该买方公钥是从将买方秘密密钥与椭圆曲线生成器相乘导出的；从卖方接收数据集，所述数据集包括零知识证明语句，其是对于给定的功能电路输出和椭圆曲线点，该功能电路输入等于卖方秘密密钥，其中，卖方的公钥是从将卖方秘密密钥与椭圆曲线生成器相乘导出的，其中，卖方秘密密钥是访问数据或被用于保护访问数据；验证证明；向买方发送第一交易Tx1，该第一交易Tx1包含在用于获得访问数据的交换中将奖励数据分配给买方的输出，该奖励数据是使用卖方秘密密钥可访问的；在区块链上确认卖方已经签署并广播了第一交易，以便第一交易被挖掘成区块，由此使得通过提供第二交易Tx2卖方能够访问来自第一交易Tx1的输出的奖励数据，该第二交易Tx2提供其签名和卖方秘密密钥以解锁奖励数据；以及获得由卖方提供的访问数据。该方法可以由买方或验证者使用以进行针对数据(例如，加密密钥)的零知识或有交易或支付。
该方法还可以包括：向卖方发送椭圆曲线公钥pkB，所述卖方已经从安全的随机秘密密钥skB生成了所述公钥，其中
pkS＝skS×G，并且G为椭圆曲线，并且
卖方确保要为访问数据提供锁定值i，以使得
访问数据＝pkS+i×G
以及利用数据集从卖方接收其公钥pkS和来自功能电路的输出f(i)，其中，pkS＝i×G，并且功能电路输入是锁定值i。
证明者或卖方可以将语句(S)证明发送给验证者或买方，该语句(S)证明向验证者证明至功能电路的输入是对应于pkS的私钥。这使得验证者能够验证该证明，并确认对应于pk＝pkV+pkP的地址与商定的模式匹配，从而确定知道锁定值i能够导出针对访问数据的完整私钥(skB+i)，并且锁定值i是到功能电路i的功能电路输入。
该方法还可以包括：向买方发送包含输出的交易Tx1，该输出包含要接收的访问数据，该访问数据可以通过来自卖方的签名和功能电路输入i来访问，其中，卖方在交易被挖掘成区块的区块链上签署和广播交易，使得通过提供第二交易Tx2卖方能够访问来自交易Tx1的输出的数据，该第二交易Tx2提供其签名和值i以解锁交易，然后该交易被透漏在区块链上，访问区块链以识别锁定值i并访问由卖方提供的数字内容，其中
sk＝skB+i，
其中，pk＝sk×G
要从卖方接收的奖励数据包括加密货币支付。数据可以是未花费的交易输出或UTXO。数据可以包括比特币支付。在整个本申请中指代的区块链可以是比特币区块链。
卖方要提供的访问数据是虚荣地址的秘密密钥，或者使得能够确定虚荣地址的秘密密钥。卖方秘密密钥可以是锁定值i，其用于保护数字内容并且是买方所需的。期望的虚荣地址是事先指定的。
因此，还期望提供一种计算机实现的方法，其是用于实现语句的零知识证明或验证的计算机实现的方法，在其中，证明者在对语句的见证(w)保密的同时向验证者证明语句为真。该证明可以是显式证明。
该方法包括：证明者向验证者发送数据集。该数据集包括具有算术电路的语句，该算术电路具有m个门和n个线，该算术电路被配置为实现功能电路并确定对于给定的功能电路输出(h)和椭圆曲线点(P)，至功能电路或功能电路中的线的功能电路输入(s)是否等于对应的椭圆曲线点乘数(s)。功能电路可以是实现哈希函数的功能的电路。哈希函数电路或函数电路中的线的原像可以等于对应的椭圆曲线点乘数。
数据还包括单独的线承诺和/或成批的承诺。该承诺或每个承诺可以是针对电路的门的被加密的线输入和输出。数据还包括输入。输入操作为针对算术电路的线[椭圆曲线点(P)]的密钥公开。证明者或验证者都可以对线命名。输入或密钥公开可以是针对电路中的第一线的。该数据还包括功能电路输出。语句中使用的椭圆曲线或每个椭圆曲线的规范可以被包括在数据中。
在发送数据后，证明者从验证者接收挑战值，并以公开进行回复。该公开可以是依据∑(sigma，西格玛)协议的值语句。公开值可以针对使得验证者能够确定该语句为真并计算椭圆曲线点的电路的每个门。
作为等待挑战的替代方法，证明者可以附加地将证明密钥发送给验证者。证明密钥可以从作为证明的一部分的数据生成。证明密钥可以是证明中使用的一个或多个随机数的哈希值。
发送给验证者的数据使得验证者能够确定电路得到满足，并计算椭圆曲线点并验证语句，由此确定证明者拥有对该语句的见证。
发送的数据集和/或发送给验证者的挑战的公开可以像独立于验证者创建的密钥一样起作用。来自验证者的挑战类似于确定证明者的身份和密钥的完整性。
输入或密钥公开可以是针对算术电路中的第一线的。然而，优选的是，选择随机线，因为证明知道中间线比证明知道第一线更困难。而且，选择第一线以外的任意线更为稳健，并且阻止恶意的第三方发现证据或见证。
同样期望提供一种补充的计算机实现的方法，其是用于实现语句的零知识证明或验证的计算机实现的方法，在其中，验证者在不知道对语句的见证(w)的情况下通过分析从证明者接收到的数据来验证语句为真。清楚地，本发明的方法扩展到验证者以插头-插座的方式采取的对等的动作。本发明扩展到证明者和验证者之间的全面合作。
证明者可以发送单独的线承诺，并使用∑(Sigma，西格玛)协议与验证者进行通信，以证明知道见证。在从证明者接收到单独的线承诺时，验证者可以使用∑协议与证明者进行通信，以确认证明者已知道见证。
除了等待挑战值之外或作为等待挑战值的替代，证明者还可以向验证者发送随机值，以使得验证者能够确定语句为真并计算椭圆曲线点。在从证明者接收到数据时，验证者可以可替代地接收随机值，以使得验证者能够确定该语句为真并计算椭圆曲线点。随机值可以是至少一个承诺的函数。所述函数可以是哈希函数。
可以替换随机值或挑战以提高过程的便利性和效率。还存在与验证者在提取关于见证的信息的尝试中生成非随机挑战相关联的风险。而且，用证明者提供的随机值代替挑战值会将方法从交互式方法转换为非交互式方法。证明者可以生成能够被独立且公开地离线验证的证明。随机值可以是来自哈希函数的输出。用来自一个或多个承诺的哈希值的输出替换随机值(x)利用了菲亚特-沙米尔(Fiat-Shamir)原理。
可以通过哈希化由证明者生成并发送给验证者的所有承诺的级联(concatenation)来计算随机值。
承诺可以是：
Wi＝Com(wi，ri)
其中
Com是对功能电路的承诺，
wi是线值，
ri是随机数，即对于每个线承诺来说，随机数都不同，以及
i是线名称，
以使得
Com(w，r)＝w×G+r×F
其中
F和G是椭圆曲线点。
算术电路中线l的输入可以是：
ko＝rl x F，
其中
ko是密钥公开的输入，
rl是随机数，以及
F是椭圆曲线上的点。
线可以是电路中的第一线。
验证者可以确认电路得到满足，并能够通过椭圆曲线点减法来计算线l的公钥：
pkl＝Com(wl，rl)-kol
证明者可以发送成批的线承诺，并生成随机数以计算每个线的椭圆曲线点，从而形成证明密钥。
针对见证的成批的承诺可以是
其中
r是证明者生成的随机数，
证明者计算对线值wi(对于i＝1，...，n)的矢量w的承诺，其中，wn将被密钥公开，
Ki是计算的椭圆曲线点，
wi是线值，其中wn是密钥被公开的，
F是椭圆曲线上的点。
算术电路中的线n的输入为：
其中
kon是密钥公开的输入，
r是随机数，以及
F是椭圆曲线上的点。
输入可以是针对第一线的。
验证者可以通过椭圆曲线算术来计算密钥语句线的公钥公开：
pkn＝Com(w)-kon
附加地，证明者可以向至少一个线发送完全公开的承诺。该方法可以使用Pedersen承诺。该语句只能将一个算术电路用于功能电路。功能电路可以实现哈希函数。哈希函数可以是SHA-256哈希函数。
该方法可以由证明者使用以实现针对数据(例如，加密密钥)的零知识或有交易(其可以是零知识或有交易)，其中，证明者与验证者联系以确认要提供的数据(可以是虚荣地址)和要接收的数据(所述数据可以是UTXO形式的支付)，并建立与验证者的通信信道(所述信道可以是公开的)，证明者从验证者接收椭圆曲线公钥pkB，所述验证者已经从安全的随机秘密密钥skB生成该椭圆曲线公钥pkB，其中
pkV＝skV×G，并且G为椭圆曲线，
证明者确保要为数据提供锁定值i，使得
数据＝pkV+i×G
证明者可以在通过更改i得出的Base58编码地址中执行对所需模式的搜索。证明者向验证者发送其公钥pkP和来自功能电路的输出f(i)，其中，pkP＝i×G，并且功能电路输入(例如，原像)是锁定值i。
证明者可以将语句证明发送给验证者，该语句证明向验证者证明至功能电路的输入是与pkP相对应的私钥，从而使得验证者能够验证证明，并确认与pk＝pkV+pkP相对应的地址匹配商定的模式，从而确定知道锁定值i能够导出数据的完整私钥，并且确定锁定值i是至功能电路的功能电路输入。
证明者可以从验证者接收交易Tx1，该交易Tx1包含输出，该输出包含要接收的数据，该数据可以通过来自证明者的签名和功能电路输入i来访问。该交易可以是哈希化的时间锁定函数。要接收的数据可以提供对UTXO的访问。
证明者可以在交易被挖掘成区块的区块链上签署和广播交易，使得证明者能够通过提供第二交易Tx2来访问来自交易Tx1的输出的数据，该第二交易Tx2提供其签名和值i以解锁交易，然后该交易被透漏在区块链上，从而使得验证者能够识别锁定值I并访问由证明者提供的数据，其中
sk＝skB+i，
其中，pk＝sk×G
证明者要提供的数据可以包括虚荣地址。要从验证者接收的数据可以包括加密货币支付(例如，UTXO)。
交易可以是完全原子性的和无需信任的：只有当买方提供在区块链上公开透漏的有效值i时，买方才能支付。由于私钥的分裂，区块链上暴露的值对其他任何人都没有用，并且不会损害完整私钥的安全性。
一种计算机实现的方法可以涉及：证明者执行与验证者的数据的去信任公平交换(无需第三方中心化交换)。这可以被描述为跨链原子交换或原子交易，因为在此上下文中指的是公平交换性质：双方要么完成其交易，要么都不完成交易。这种交换可以在支持脚本功能的区块链之间执行，该脚本功能实现哈希化和时间锁定的合约。
证明者访问了第一区块链上的第一数据，例如1个比特币的UTXO，且验证者访问了第二区块链上存在的第二数据，例如100LTC，并且证明者和验证者就交换所述数据达成一致。该方法包括：证明者为第二区块链生成密钥对，将公钥发送给验证者，并保留私钥；证明者接收针对第一区块链的验证者公钥，所述验证者已经为第一区块链生成密钥对并保留私钥；证明者发送语句、一个或多个承诺、输入或密钥公开以及功能电路输出以及椭圆曲线规范。
证明者可以创建第一区块链交易TxA，该交易TxA将第一数据发送到公共公钥地址，并在第一区块链网络上广播所述交易，所述地址由输入和验证者的公钥之和限定。在交换的24小时之内没有进行交换之后，证明者便可以访问该数据。
证明者可以验证第二区块链交易TxB，所述交易是在确认第一区块链交易TxA包括在第一区块链中之后由验证者在第二区块链网络上创建并在第二区块链网络上进行广播，所述交易以100LTC的形式将第二数据发送到证明者的公钥地址，该公钥地址可由证明者使用针对证明者的公钥地址的有效签名以及作为用来确定功能电路输出的功能电路输入的值来访问。在交换的24小时之内没有进行交换后，验证者便可以访问该数据。
证明者确认第二区块链交易TxB被包括在第二区块链上，并通过提供其签名和作为功能电路输出的功能电路输入的值来访问第二数据，从而使得验证者能够观察作为用来确定功能电路输出的功能电路输入的值，并通过使用私钥提供签名来访问第一数据(对于PC，其是来自椭圆曲线点乘法的同态性质的sB+s)。
交换的数据可以是加密货币，并且第一数据对应于第一加密货币(优选地比特币)的数量，并且第二数据对应于第二加密货币(优选地莱特币)的数量。
如上所述，证明者的每个动作都需要验证者的对等动作来验证证明。本发明扩展到由验证者执行的方法或动作。因此，提供了一种用于实现语句的零知识证明或验证的计算机实现的方法，在其中证明者向验证者证明(最好明确地)该语句为真，同时将对语句的见证保密，该方法包括：验证者从证明者接收：具有算术电路的语句，该算术电路具有被配置为实现功能电路(最好是哈希函数)的m个门和n个线，以及确定对于给定的功能电路、以及优选的指定的功能电路、输出和椭圆曲线点，功能的功能电路输入或原像是否等于椭圆曲线点乘数。验证者还接收：针对电路的线的单独的线承诺和/或成批的承诺，它们是加密的线输入和输出；针对算术电路中的线(优选的是除第一线之外的线)的输入或密钥公开；以及功能电路输出(h)。验证者还可以接收语句中使用的椭圆曲线或每个椭圆曲线的规范。验证者可以将挑战值发送给证明者，然后接收公开。公开可以按照∑协议进行，并包含电路的每个门的值，这些值使得验证者能够确定该语句为真并计算椭圆曲线点。附加地或替代地，验证者可以从证明者接收证明密钥。
然后，验证者确定电路得到满足，并计算椭圆曲线点(P)并验证语句，从而确定证明者持有对语句的见证(w)。
这可以通过使用Sigma协议(如果证明是交互式的)或使用证明密钥(如果使用了Fiat-Shamir启发法则)以零知识来证明证明者知道语句电路的每个门的值来实现。验证者可以从证明者接收针对每个门的Σ_zero和Σ_prod承诺、利用挑战值答复、从证明者接收公开值并且就承诺进行检查。验证者可以通过经由椭圆曲线点减法计算针对线l的公钥来确认电路得到满足。验证者可以确认每个线的每个公钥都与语句中指定的(一个或多个)密钥相匹配。验证者可以确定完全公开的线与可以在语句中指定的值相匹配，以完成验证。
还期望提供一种包括计算机可执行指令的计算机可读存储介质，该计算机可执行指令在被执行时将处理器配置成执行由证明者、验证者或协作的证明者与验证者来执行的方法。
还期望提供一种电子设备，该电子设备包括：接口设备；耦合到接口设备的一个或多个处理器；耦合到一个或多个处理器的存储器，该存储器上存储有计算机可执行指令，该计算机可执行指令在被执行时将一个或多个处理器配置成执行本文所要求保护的方法。还期望提供一种区块链网络的节点，该节点被配置为执行所要求保护的方法。还期望提供一种具有诸如节点等的区块链网络。
附图说明
上面已经在技术背景部分中使用图1a和图1b描述了用于交互式零知识证明的基本系统，其中，图1a是具有左侧线输入和右侧线输入以及一个线输出的乘法门的示意图，而图1b是具有三个门、三个输入线、一个输出线和两个内部线的算术电路的示意图。
本发明的方面将从本文描述的实施例变得显而易见并参考这些实施例而阐明。现在将仅通过示例的方式并参考附图来描述本发明的实施例，在附图中：
图2是用于语句的复合电路的示意图，该复合电路包含针对哈希函数和椭圆曲线乘法的算术电路；
图3是图1的复合语句的算术电路的替代示意图，其中，只需要一个算术电路；
图4是具有四个门和五个线的算术电路的示意图，其中，线的公钥是从具有密钥公开值的线承诺中透漏的或公开的；
图5是在证明者和验证者之间交换的用于语句S的证明的数据的示意性表示，所述语句具有电路描述并且第一线具有对应的公钥；
图6是在证明者与验证者之间交换的数据的替代示意性表示；以及
图7是由验证者验证图4的电路得到满足时执行的检查的示意图，其中输入线具有所需的公钥并且输出线的哈希值具有所需的值。
具体实施方式
总述
本发明能够对复合语句进行有效的零知识验证，该复合语句同时涉及算术电路可满足性和有关公钥的有效性的从属语句(密钥语句证明)两者。在同态承诺函数中采用公钥椭圆曲线规范来证明电路可满足性。这使得能够以有效的方式来证明与用作电路输入和/或输出的私钥相对应的公钥语句。
为涉及电路可满足性和椭圆曲线密钥对两者的语句生成证明的证明大小和计算费用可以大大减少。本文中的方法可以容易地并入现有的针对电路可满足性的基于离散对数的零知识证明协议中，而无需使用双线性配对友好的椭圆曲线。该方法与比特币secp256k1标准完全兼容。
描述了与区块链(例如，比特币区块链)上的两方之间的公平交换的交易有关的该方法的两个应用。第一个应用涉及外包虚荣地址的去信任销售的零知识或有支付，这需要SHA256哈希原图和椭圆曲线(例如，比特币)秘密密钥的相等性的零知识证明。第二个应用涉及提高跨链原子交换的安全性，这需要证明SHA256哈希原像等于未知的私钥(利用供应的公钥)乘以供应的随机数(nonce)。
通用方案
本发明涉及一种使得能够证明特定类别的复合语句的方法，该复合语句涉及与椭圆曲线公钥/私钥对(基于椭圆曲线点乘法)的关系。
使用zkSNARK来证明涉及任意加密椭圆曲线密钥操作的语句被认为是不切实际的，并且因此，该方法使用有关椭圆曲线公钥的信息，该信息直接从在构造针对通用电路可满足性的证明中使用的‘同态隐藏’(或承诺方案)提取。方法的语句中涉及的特定类型的椭圆曲线与电路承诺方案中使用的椭圆曲线相同。
但是，SNARK方法涉及配对操作，并且因此需要特殊的双线性配对友好椭圆曲线。由于某些区块链上使用的椭圆曲线与双线性配对友好椭圆曲线不兼容，因此排除了使用zk-SNARKs。
举例来说，与比特币公钥有关的语句使用不兼容的比特币secp256k1曲线。
因此，本发明的方法与用于证明不依赖于配对并且具有较少的加密假设的算术电路可满足性的替代协议兼容。总的来说，本发明的方法比zkSNARKS更有效，因为需要较少的计算并且减小了对于去信任交换应用的证明的大小。
举例来说，表示下面的“语句1”的复合电路的图2的示意图包含用于哈希函数和椭圆曲线乘法两者的子电路。在图2中，该示意图具有三个输入：具有对应的配对公钥“P”的秘密密钥“s”和作为秘密密钥“s”的哈希值的值“h”。该示意图包含两个算术电路，其中，第一算术电路对秘密密钥执行哈希化，而第二算术电路对秘密密钥执行椭圆曲线乘法。将电路的输出与输入进行比较。
注意，内部门仅用于说明目的。电路检查哈希的输出等于椭圆曲线(EC)公钥。只有输入“h”、“P”和输出被完全透漏给验证者。所有其他值均被加密。
语句1
“给出哈希函数(H)的输出h和椭圆曲线点P(公钥)，
则哈希的原像s(即，h＝H(s))等于椭圆曲线点乘数(私钥，即P＝s×G，其中，G是椭圆曲线生成器点)”
该方法使得证明者能够以零知识证明该特定语句。受益于这种方法的应用的示例将在以下与数据的去信任交换(例如，出售外包的比特币虚荣地址)以及匿名和安全的跨链原子交换相关地进行描述。
例如使用下面的伪代码函数，语句1的真实性的验证是可确定的，该伪代码函数接受输入“h”、“P”和“s”，并且如果语句为真则输出“1”，否则输出“0”：
依据图2，以零知识验证“语句1”(即，证明者利用zkSNARK系统使“s”的值对于验证者保密)将需要针对哈希函数和椭圆曲线点乘法两者的算术电路。
尽管SHA-256哈希函数的算术电路已得到广泛使用和优化，并且通常包含少于30,000个乘法门，但文献中尚无实现针对加密椭圆曲线点乘法的算术电路的已知示例。即使已知这样的电路，但由于它们的大小和复杂性以及包含更多的门，所以它们也是不切实际的。
如图2所示，该方法利用针对单个哈希函数的完整算术电路来运行，图2具有用于采用密钥语句证明的复合语句1的算术电路和用于哈希函数的仅一个算术电路的示意图。该电路检查哈希的输出是否正确，并且公钥是否等于EC加密的输入(密钥语句证明)。以蓝色突出显示的值(即，输入“h”、“P”和输出“1”)被透漏给验证者，并且所有其他值均被加密。
使用图3的电路，证明者能够通过电路可满足性明确地证明秘密密钥“s”哈希化为“h”，并且密钥对的相应公钥“P”等于“s×G”，其中，G是椭圆曲线生成器点。秘密密钥“s”是哈希的原图，或者是函数的输入，并且在证明语句时不会被透漏给验证者。
值得注意的是，验证“s×G”等于“P”可以通过在作为证明协议的一部分的承诺方案中采用所需的椭圆曲线来以可忽略的额外计算成本从电路证明中提取。这样的操作称为“密钥语句证明”，并使用被称为“密钥公开”的承诺公开程序。
技术效果
已知的零知识简洁的非交互式知识论证(zk-SNARKs)是用于算术电路可满足性的通用证明系统的实现。在SNARK框架中，将编码为算术电路的语句转换为称为二次算术程序(QAP)的构造，其由多项式等式的集合组成。然后通过在单个点处演示该等式集合的有效性来证明该语句。SNARK方法的主要优点在于，验证者仅需要执行一些椭圆曲线(配对)操作(花费几毫秒)，并且证明非常小(288字节)且与电路大小无关。
通过SNARK方法实现的非常小的证明和验证时间以可信任的设置、非标准的加密假设和证明者承担的更重的计算负担为代价。SNARK方法还需要使用椭圆曲线双线性配对。但是，使用计算上可行的双线性配对需要使用特殊的“配对友好”椭圆曲线。这就排除了使用许多标准的加密椭圆曲线参数集(包括比特币secp256k1)。然后，涉及一般椭圆曲线点乘法的语句必须使用显式电路(其可能非常大)。
通过与上一部分中描述的用于证明SHA电路可满足性的∑协议方法进行比较的方式，利用SNARK(Pinocchio)框架，生成证明密钥将花费大约10秒并且证明密钥的大小大约为7MB，并且证明也将需要大约10秒钟才能生成。但是，证明的大小为288B，并且只需要大约5毫秒即可验证[Bootle 2016]。
另外，将明确的椭圆曲线乘法(密钥语句)并入电路中是使证明密钥大小和证明生成时间二者倍增(multiply)至少一个数量级。
本发明实现语句的零知识证明，该语句同时涉及椭圆曲线公钥-私钥关系和一般的算术电路可满足性。除了证明算术电路的可满足性之外，这可以以可忽略的计算费用来实现，并且避免了为将大大增加证明的计算费用的椭圆曲线点乘法运算创建显式算术电路的需要。
实现方式
下面针对基于成批处理的和未成批处理的承诺的零知识证明系统来描述本发明的实现。
在示例中，零知识证明协议中涉及两方：证明者(P)和验证者(V)。该协议的目的是使证明者在将有关语句的见证的信息保密的同时说服验证者给定的语句
语句中指定的(一个或多个)椭圆曲线公钥与目标椭圆曲线规范(其由椭圆曲线参数的完整集合限定：
在比特币脚本的情况下，这些参数由secp256k1的规范[SEC 2010]限定。该规范包括基本生成器点G。除了指定基点之外，该语句还必须指定第二点F(其中，F＝f×G，且f是
关于图4描述了成批和未成批的承诺，图4是具有四个门和五个线的代表性算术电路。输入线(wl)使其公钥从具有‘密钥公开’值kol的线承诺Wl被透漏或公开。
实现方式-单独的线承诺
以图4为例，‘密钥公开’是对电路中的每个线的单独承诺，这些承诺由证明者创建并发送给验证者。这些密钥公开遵循针对算术电路可满足性的已知∑协议。图5示出了在证明者和验证者之间交换的数据。
可满足性通过包括以下的多个步骤来实现：
1.电路的每个线i(i＝1，...，n)均以Pedersen承诺来承诺：
Wi＝Com(wi，ri)
其中，
Com(w，r)＝w×G+r×F
2.对于需要其对应的公钥的证明(密钥语句证明)的电路线l，证明者还会发送密钥公开：
kol＝rl×F
3.可选地，如果电路线j需要被公开地透漏(完全公开的线)，则证明者发送完全公开元组(opening tuple)：
(wj，rj)
4.然后使用∑协议，以零知识证明电路的每个门都得到满足，这涉及证明者计算并发送针对每个门的∑zero和∑prod承诺(即，分别为B或C1、C2、C3)，并且验证者以挑战值(x)进行答复，然后证明者发送公开值(z值和e值)，并且然后验证者就承诺进行检查。
5.一旦验证者确认电路得到满足，则验证者便通过椭圆曲线点减法计算线l的公钥：
pkl＝Com(wl，rl)-kol
6.然后，验证者确认每个pkl与语句中指定的(一个或多个)密钥相匹配(并且完全公开的线与指定的值相匹配)以完成验证。
实现详情-单独的线承诺
继续图4，提供了详述示例的单独承诺和验证的明确示例，其描述了利用各线中的一个的密钥语句证明和另一线的完全透漏二者来验证简单的算术电路的可满足性。
如图4所示的电路
证明者和验证者就语句达成一致，该语句包括电路、线5的值和线1的公钥以及椭圆曲线和承诺规范。证明者想要向验证者证明其真实性的语句
“我知道满足电路
线1至4的值未被透漏。然后，证明者和验证者如图6所示的那样进行交互，并如下所述：
1.证明者生成5个随机盲值(r1，...，r5)，然后计算5个线承诺(W1，...，W5)并将这些发送给验证者。
2.证明者计算针对线1的密钥公开：ko1＝r1×F，并将其发送给验证者。
3.证明者将针对线5(w5，r5)的完全公开信息发送给验证者。
4.对于加法门(g1和g3)，证明者生成对零的承诺(利用随机数(random nonce)rB1和rB3)：B1＝Com(0，rB1)和B3＝Com(0，rB3)并将它们发送给验证者。
5.对于乘法门(g2和g4)，证明者将如下生成承诺：
对于门2：
C12＝Com(t12，t32)，
C2＝Com(t22，t52)，以及
C3＝t12×W1+t42×F
对于门4：
C14＝Com(t14，t34)，
C2＝Com(t24，t54)，以及
C3＝t14×W3+t44×F
其中，txx值为随机盲随机数。证明者将这些承诺发送给验证者。
6.然后验证者生成随机挑战值x，并将其发送给证明者。可替代地，证明者可以使用Fiat-Shamir启发法通过哈希化所有承诺的级联来生成值x。
7.对于加法门(g1和g3)，证明者计算以下公开并将其发送给验证者：
z1＝x(r1+r1-r2)+rB1
z3＝x(r2+r1-r4)+rB3
8.对于乘法门(g2和g4)，证明者计算以下公开并将其发送给验证者：
e12＝w1x+t12
e22＝w2x+t22
z12＝r1x+t32
z22＝r2x+t52
z32＝(r3-w1r2)x+t42
e14＝w3x+t14
e24＝w4x+t24
z14＝r3x+t34
z24＝r4x+t54
z34＝(r5-w3r4)x+t44
9.最后，验证者检查相等性。如果这些通过，则证明被验证。
在图7中概述了由验证者执行的验证，其中，内框中的检查将验证电路得到满足，并且第一线具有所需的公钥，且线5具有所需的值。
图5和6中的挑战“x”提供了交互式证明，其中，通信在证明者和验证者之间来回传递。
这种交互在发生零知识或有支付(ZKCP)时可能会方便，因为卖方和买方可能无法同时有空(available)或在线。此外，买方(验证者)可能希望证明是公开可验证的，例如它可能是数字商品的广告的一部分。
此外，在完美的特别诚实验证者(perfect special-honest verifier)模型中，证明仅是严格的零知识：也就是说，假设验证者生成真正的随机数作为挑战，而不是选择挑战值来尝试和提取有关见证的信息。
为了解决这些问题，应用了Fiat-Shamir启发式，其用证明者做出的承诺的哈希值的输出替换了随机挑战值“x”。在随机预言模型(其中，加密哈希函数的输出被视为真正地随机)中，证明者无法作弊，并且验证者可以检查生成的挑战值。
因此，可以通过使用Fiat-Shamir启发式方法将交互式证明系统转换为非交互式证明系统来改进该示例，并且证明者可以生成能够独立和公开地离线验证的证明。
更具体地说，将挑战值(x)替换为通过哈希化(使用例如SHA-256)由证明者生成的所有承诺(即，分别用于求和门和乘积门的所有线承诺以及所有B和C1、C2、C3承诺)的级联而计算得出的值。
实现方式-成批的矢量承诺
针对涉及矢量承诺[Bootle 2016，Groth 2009]的批处理的电路可满足性的压缩证明系统使用以下描述的方法，其中，该方法能够从成批的电路线承诺中提取密钥语句证明。
为了避免重复，没有描述整个过程，并且以下步骤着重于成批的线承诺的生成，并演示其包含指定的公钥。在下面的步骤中，成批的承诺被如下生成，其中，线l将被提供有密钥公开-在矢量承诺中将n个线一起批处理。
1.证明者生成n-1个随机数
2.证明者计算椭圆曲线点Ki＝xi×G(对于i＝1，...，n-1)。
这些值加上Kn＝G形成发送给验证者的证明密钥PrK。
3.证明者生成随机值：
4.证明者计算对线值wi(对于i＝1，...，n)的矢量w的承诺，其中，wn要被密钥公开：
并将其发送给验证者。
5.证明者还发送针对矢量承诺的密钥公开：
6.验证者通过椭圆曲线算术计算密钥语句线的公钥公开：
pkn＝Com(w)-kon
发明概述
哈希原像和椭圆曲线私钥的相等的证明可被用在众多应用中。下面描述了两种应用，它们概述了构造密钥语句零知识证明的特定示例以进行应用。
为了示例应用的目的，下面的语句
“给出具有公开的输出h的SHA-256哈希函数(H)和secp256k1椭圆曲线上的公开点P，则哈希的秘密原像s(即，h＝H(s))等于椭圆曲线点乘数(即，对应的私钥，即，P＝s×G)”
在所提供的示例中，该语句由用于SHA-256哈希函数的单个算术电路
因此，为了完全验证该语句，证明者必须使用基于secp256k1的承诺方案来向验证者演示他们知道对于SHA256电路的满足赋值，并且然后仅提供针对线1的密钥公开(ko1)和针对线n的完全公开(wn，rn)。验证者不会得到输入线(w1)的值，也不会得到除完全公开的输出线wn以外的任何其他线的值。
应用I
如以上实现方式部分中所描述的，本发明的示例可以应用于外包比特币虚荣地址的ZKCP，该比特币虚荣地址代表将要被交换以用于支付或访问资源的数据。
比特币地址以人类可读的字母数字格式(Base58编码)进行编码，以使其易于公开、复制和转录。这种格式的使用已导致所谓的虚荣地址的流行，在这里，对密钥空间进行了强力搜索，以便找到私钥，其产生的结果是包含期望字符串(比如名称)的地址，例如如下所示的一个。
由于导出具有显著模式的虚荣地址可能在计算上是昂贵的(例如，上面示出的地址在找到匹配项之前需要生成大约1013个不同的公钥)，因此通常将搜索外包，并且存在委托和出售虚荣地址的几个在线市场。使用椭圆曲线的点乘法的同态性质可以安全地完成此操作[JoelKatz 2012]。
尽管外包该生成是安全的，但虚荣地址的出售不是去信任的。买方要么在卖方获得付款之前就获得了所需的值，要么卖方在释放要求的值之前就已获得付款，或者他们二者都必须信任托管服务。可以采用本发明来实现经由ZKCP进行虚荣地址的去信任销售。买方/验证者与卖方/证明者之间采取的步骤如下所述。
1.买方和卖方就所需的虚荣模式(Str)和价格(a比特币)达成共识，并建立不需要被保护的通信信道。
2.买方生成安全的随机秘密密钥skB和对应的椭圆曲线公钥，其中公钥pkB＝skB×G
3.买方将pkB发送给卖方。
4.然后，卖方在通过改变i从pk＝pkB+i×G导出的Base58编码地址中执行对所需模式的搜索。
5.当找到具有所需模式的地址时，卖方保存值i，向买方发出信号，并且然后向他们发送pks＝i×G和SHA256哈希H(i)。
6.卖方还向买方提供针对H(i)的原像是对应于pks的私钥的证明，如上面的示例所述的。
7.买方验证该证明，并且还确认与pk＝pkB+pks对应的地址与商定的模式相匹配。此时(凭借证明)，买方知道学习值i将会使得他们能够得出针对虚荣地址的完整私钥(skB+i)，并且特定值i哈希化为h＝H(i)。
8.然后，买方构造哈希时间锁定合约(HTLC)交易Tx1，该交易包含输出，该输出包含商定的费用(a)。该输出可以通过两种方式被解锁：
i.利用来自卖方的签名和哈希原像i随时地进行解锁。
ii.通过使用例如CHECKLOCKTIMEVERIFY(OP_CLTV)脚本操作码，利用在指定的时间之后来自买方的签名进行解锁，该脚本操作码可用于防止在指定时间或区块高度之前花费输出。
9.然后，买方签署该交易并将其广播到区块链，在该区块链中，该交易被挖掘为区块。
10.一旦被确认，卖方就可以通过提供交易Tx2来在Tx1的输出中索要费用，该交易Tx2提供其签名和值i以解锁哈希锁定，然后该哈希锁定被透漏在区块链上。
11.买方可以计算最终虚荣地址私钥sk＝skB+i，其中，pk＝sk×G
12.如果买方未能在指定的OP_CLTV时间之前提供值i，则卖方可以提供其签名以重新索要该费用(以防止由于不合作的买方而损失费用)。
于是，该交易是完全原子的和去信任的：只有当买方提供在区块链上公开透漏的有效值i时，买方才能进行支付。由于私钥的分裂，该值对其他任何人都没有用，并且不会损害完整私钥的安全性。
应用II
如以上实现方式部分中所描述的，本发明的示例可以应用于在两方之间的数据的私人交换，每一方都具有在不同区块链上注册的要被交换的其相应的数据。
更具体地说，本发明可以应用于保护隐私的跨链原子交换，这是一种利用区块链交易特征(也称为原子交易)的去信任公平交换协议。该协议用于在没有第三方中心化交换的情况下在两个不同的区块链上交易两个不同的加密货币令牌。在该上下文中，“原子”一词是指公平交换性质：要么双方都完成交易，要么双方都没完成。
已知的基本协议的示例按照以下步骤执行。为了安全起见，交换中使用的两种加密货币都必须具有实现哈希化和时间锁定合约的脚本功能。交换涉及两方：爱丽丝(Alice)和鲍勃(Bob)。在此示例中，爱丽丝拥有1个比特币，并同意将其与鲍勃的100枚莱特币(Litecoin)进行交易。
1.爱丽丝生成莱特币公钥PA，她将该莱特币公钥PA发送给鲍勃
2.鲍勃生成比特币公钥PB，他将该比特币公钥PB发送给爱丽丝
3.爱丽丝生成安全的随机数x
4.爱丽丝计算x的SHA-256哈希值：h＝H(x)
5.爱丽丝创建比特币交易TxA，该交易TxA：
i.利用有效签名和(AND)哈希化为h的值向PB支付1比特币
ii.或者，24小时后将1比特币返还给爱丽丝。
6.爱丽丝将交易广播到比特币网络。
7.一旦鲍勃观察到TxA在比特币区块链上被确认，他就创建莱特币交易TxB，该交易TxB：
i.利用有效签名和哈希化为h的值向PA支付100莱特币
ii.或者，24小时后将100莱特币返还给鲍勃。
8.鲍勃将交易广播到莱特币网络。
9.一旦交易被确认，则爱丽丝就可以通过提供其签名和值x来索要莱特币输出。
10.一旦鲍勃观察到莱特币区块链上的值x，然后就可以通过提供其签名和值x来索要比特币输出。
该示例确保要么双方都得到了币，要么都没有得到。爱丽丝生成哈希值，并且只有她知道原像，但是要求她透露该原像以索要币，然后这使得鲍勃能够索要他的币。如果任一方未遵循协议完成交易，则他们都可以在锁定时段排除后重新索要其币。
上述已知协议的一个显著缺点特征是，两个区块链上的交易可平凡地链接：一旦被确认，唯一值x永远在两个区块链上公开可见。这会影响币的可替代性和交易的机密性。
为了使两个交易不链接，每个链上的输出必须使用不同的密钥，但是为了使该协议是安全的且去信任的，爱丽丝必须向鲍勃提供证明：当她透露自己的哈希原像时，他将获知解锁其币所需的信息。
通过采用上述示例中描述的密钥语句证明，可以将第二区块链上的哈希锁定输出转换为正常的支付到公钥哈希(P2PKH)输出，从而掩饰了交易的性质并断开了任何可能的链接。
应用于爱丽丝拥有1个比特币并同意将其与鲍勃的100莱特币进行交易的上面的示例的改进的流程将包括以下动作：
2.爱丽丝生成莱特币公钥PA(具有私钥sA)，她将其发送给鲍勃
3.鲍勃生成比特币公钥PB(具有私钥sB)，他将其发送给爱丽丝4.爱丽丝生成安全的随机数
5.爱丽丝计算x的SHA-256哈希值：h＝H(x)，以及与x对应的椭圆曲线公钥：：Px＝x×G
6.爱丽丝安全地将h和Px二者发送到鲍勃。
7.爱丽丝还向鲍勃发送密钥语句证明：h的原像等于生成Px的私钥。
8.爱丽丝创建比特币交易TxA，该交易TxA：
i.向公钥PC＝PB+Px支付1比特币
ii.或者，24小时后将1比特币返还给爱丽丝。
9.爱丽丝将交易广播给比特币网络。
10.一旦鲍勃观察到TxA在比特币区块链上被确认，他就创建莱特币交易TxB，该交易TxB：
i.利用有效签名和SHA-256哈希化为h的值向PA支付100莱特币
ii.或者，24小时后将100莱特币返还给鲍勃。
11.鲍勃将交易广播到莱特币网络。
12.一旦交易被确认，爱丽丝就可以通过提供其签名和值x来索要莱特币输出。
13.一旦鲍勃观察到莱特币区块链上的值x，他就通过使用针对PC的私钥提供签名来索要比特币输出，该私钥是来自椭圆曲线点乘法的同态特性的sB+x。
一般应用
本发明适用于对语句(S)的零知识证明或验证，在其中，证明者在使语句的见证(w)保密的同时向验证者证明语句为真。该秘密可以通过诸如哈希函数之类的函数来处理，但是该秘密附加地包括加密椭圆曲线密钥操作，例如，有关公钥的语句的有效性。在上面的示例中，本发明的方法已被用来实现虚荣地址的去信任ZKCP。这也可以应用于例如：密码的导出；有效的机器可读文件的验证，例如护照或身份证的验证；或其他此类机密交易。
应当注意，上述实施例说明而不是限制本发明，并且本领域技术人员将能够设计许多替代实施例而不脱离由所附权利要求限定的本发明的范围。
在权利要求中，括号中放置的任何附图标记都不应解释为对权利要求的限制。单词“包括”和“包含”等不排除任何权利要求或整个说明书中列出的元件或步骤之外的元件或步骤的存在。在本说明书中，“包括”是指“包括或由……组成”并且“包含”是指“包含或由……构成”。
元件的单数引用并不排除此类元件的复数引用，反之亦然。本发明可以借助于包括几个不同元件的硬件以及借助于适当编程的计算机来实现。
在列举几个装置的设备权利要求中，这些装置中的几个可以由一个且相同的硬件项来实施。在互不相同的从属权利要求中记载某些措施的事实并不意味着不能有利地使用这些措施的组合。
参考文献
[Campanelli 2017]Campanelli，Matteo，et al.″Zero-knowledge contingentpayments revisited:Attacks and payments for services."Commun.ACM(2017).
[Maxwell 2016]https://github.com/zcash-hackworks/pay-to-sudoku
[Parno 2016]Parno,Bryan,et al."Pinocchio:Nearly practical verifiablecomputation."Security and Privacy(SP),2013 IEEE Symposium on.IEEE,2013.
[Libsnark 2016]https://github.com/scipr-lab/libsnark
[Bootle 2015]Bootle,Jonathan,et al."Efficient zero-knowledge proofsystems."Foundations of Security Analysis and Design VIII.Springer,Cham,2015.1-31.
[Groth 2009]Groth,Jens."Linear Algebra with Sub-linear Zero-KnowledgeArguments."CRYPTO.Vol.5677.2009.
[JoelKatz2012]https://bitcointalk.org/index.php？topic＝81865.msg901491#msg901491
[Bootle 2016]Bootle,Jonathan,et al."Efficient zero-knowledgearguments for arithmetic circuits in the discrete log setting."AnnualInternational Conference on the Theory and Applications of CryptographicTechniques.Springer,Berlin,Heidelberg,2016.
[SEC 2010]Standards for Efficient Cryptography(SEC)(CerticomResearch,http://www.secg.org/sec2-v2.pd
可从http://bitcoin.org/en/developer-reference获得比特币开发参考。
