您正在查看: OtherChain-优秀转载 分类下的文章

Algorand 共识算法

2018年是公链技术爆发的一年,诞生了诸多从共识方面创新的项目。由于目前人们普遍认为存在区块链“不可能三角”,这些共识往往要在性能、安全、去中心化、激励机制中做出取舍。例如,EOS达成每秒数千次交易速度是以牺牲去中心化为前提的。然而“不可能三角”从来没有像FLP、CAP这些分布式系统定理一样得到严谨的数学证明,因此有些人认为打破“不可能三角”是有可能的。可验证随机函数VRF被认为是一个有前景的方向。本次为大家带来最近热度非常高的Algorand项目的分析。

1、Algorand共识算法简介

Algorand共识算法是图灵奖获得者Silvio Micali在2017年底提出。Michali是MIT的教授,是一位密码学家和计算机理论学家,在伪随机数以及零知识证明领域很有名。
Algorand共识算法的论文的下载地址:https://people.csail.mit.edu/nickolai/papers/gilad-algorand.pdf

Algorand采用了VRF函数,并结合账户的余额比例,随机确定区块生成以及投票人角色。

所谓VRF(Verifiable Random Function)就是可验证随机函数。

随机数对于区块链技术来说很关键。 本质上,分布式账本的核心问题就是随机选择出块人的问题,这个随机性要能被全网确认,并且不能被操控,也不能被预测, 否则恶意节点通过操控这个随机数就可以操控长链,从而实现双花攻击。

PoW的方案是让大家进行算力竞赛,设置一个计算哈希的难题,谁先算出来谁赢,算力高的赢的概率高,算力低的赢的概率低,以这样的方式保证胜出者是随机的。投入的算力能够体现在哈希值上, 这样全网能够验证,并选择包含最多算力的那条链。恶意节点只能通过提升自己的算力来增加攻击成功的概率。

PoS的方案是选举,大家不用浪费电力去进行算力竞赛,而是文明一点,随机选举一个节点来出块,并且被选中的概率和它拥有的份额相关。 如果“随机”这一步没有问题的话,恶意节点只能通过增加自己的份额,增加自己被选中的概率,从而增加双花攻击的成功概率。 这里有一点比PoW的方案要好就是,要实现攻击,先得成为持币大户,如果攻击成功币价大跌,攻击者也会承受最大的损失。

那么接下来的核心问题就是,这个不能被操控不能被预测的随机数从哪来。传统地PoS方案尝试从链上现有的数据入手,比如使用上一个区块的哈希值,上一个区块的时间戳等等来作为随机数的来源,但这些会带来额外的安全风险。 因为区块本身的信息就是节点写进去的,然后又要根据里面的信息来选举后续的出块者,存在循环论证的嫌疑,安全性不会太好。 这也是传统地认为PoS方案不如PoW可靠的部分原因。

Algorand提出的VRF能够由私钥( SK )以及讯息( X )产生一组可验证的伪随机 (pseudorandom) 数Y以及证明 ⍴。任何人都可以透过Verify函数来检验这个随机字串是否真的是该公钥对应私钥持有者,依照规定使用Evaluate函数所产生,而不是自己乱掰的。更详细一点的VRF三个函示描述如下:

•Keygen(r) → (VK, SK). On a random input, the key generation algorithm produces a verification key VK and a secret key SK pair. •Evaluate(SK, X) → (Y, ⍴) . The evaluation algorithm takes as input the secret key SK , a message X and produces a pseudorandom output string Yand a proof ⍴ . •Verify(VK, X, Y, ⍴) → 0/1 . The verification algorithm takes as input the verification key VK , the message X , the output Y, and the proof ⍴ . It outputs 1 if and only if it verifies that Y is the output produced by the evaluation algorithm on inputs SK and X .

为什么我们需要这么一个大家自己产生,却又要可以被验证的随机字串产生器呢?这是因为在Algorand的拜占庭演算法中,虽然也存在着每一轮不同的区块生产者(称为Leader)以及验证委员会(Committee, Verifiers),但并不是用「公开选举」的方式来选的,而是透过每个使用者自己对奖的方式来看看自己是不是下一轮的Leader。

algorand就是通过随机算法从一群大范围的验证者中选取一部分验证者运行BFT算法(Micali教授实现的BA*算法),从而达到提高共识的效果。

无论是在何种BFT的共识机制中,都是由Leader以及Committee来完成区块的发布以及共识决议。例如EOS的dPoS BFT是固定21个BP轮流担任Leader以及投票者、Zilliqa透过PoW加入Committee进行PBFT共识算法。这些比较直观的拜占庭共识演算法都有一个共同特征,就是大家都可以看到下一个区块的Leader是谁,以及负责协议共识的Committee是谁。这造成了一个可能的风险,就是这些区块生产者以及Committee成员容易成为DDOS或是贿赂的目标。

Algorand为了解决这种潜在的风险,利用VRF来掩盖Leader Selection的步骤。可以想像成:一般的BFT在每一轮开始时公平公开选出Leader以及Committee,Algorand则是像在每一轮开始时公布中奖号码,每个使用者都可以自己拿自己的票根对奖,中奖的人即可成为下一轮的Leader(或是Committee Verifier),但在中奖者自己表明身分前,没有人知道谁中奖,也就是没有人能预测下一轮的Leader以及Committee。当然中奖与否并不是口说无凭,中奖者需要出示中奖证明,而这个证明是大家都可以验证的,这正是我们刚刚说到的VRF。

2、Algorand共识算法缺陷

(1)现实环境的随机选择的空间并不大。

VRF是可以提供了公平且不容易收到伪造和攻击的委员会随机选择方式,但是任何随机数的生成必须依赖大的种子集合才可以有作用,在VRF中假设80%节点是诚实的,Committee需要2000个成员才够大,现实情况是不太可能有这么多成员的。

(2)完全没考虑网络延迟情况。

VRF Committee集合选举时依赖数量庞大的主机通讯的,主机之间相互沟通造成的延迟,必然大大拖慢整个系统的处理速度。

(3)没考虑节点的动态加入和退出情况。

Algorand的下一个区块的发布者是从k个区块之前的所有参与者(在k区块之前的某段链上发过交易的节点)里选。于是,恶意节点想影响下个区块的发布者,他得影响k个区块才行,当k很大的时候,这个影响也是微乎其微。于是,Algorand得到了一个无偏向的随机数产生器。不过,这个做法有一个问题——k区块之前的节点,有可能已经不在线了。而对于这一点,虽然Micali做出了解释,但是个人觉得并不符合实际情况。

(4)签名数据庞大,造成存储浪费并影响性能。

Algorand使用VRF来确定提案组与验证组,这个方式充分发挥了VRF的可验证性优势,且后验优势使得Algorand的共识体系更安全。但是,Algorand进入验证阶段,采用的是一种可扩展的拜占庭容错算法,即BA算法,参与节点通过VRF秘密抽签选出。这一设计使Algorand在验证前必须等待凭证(VRF prove)到来,才能知晓参与节点。而且,由于使用了可扩展的拜占庭容错算法,使得Algorand的验证组规模必须比较大(2000~4000人),这将导致签名数据异常庞大。根据我们的估算,在平均每组3000个验证节点的规模下,每组的签名数据长达126KB,加上其它信息,通知信息约300K,每块的签名数据可达200064*12=1M(共12组,每组3000人,至少2/3达成共识。ed25519签名数据长度是64。),远超一般门限签名几十个字节,严重浪费存储和容量(因每块存储的交易量将被占用,不存储签名又会影响安全),不仅造成存储浪费,而且更影响性能。

(5)无法构建很好的激励机制

在POW中,提案者得到提案权需要预先付出算力成本,若其提案区块有问题(交易双花),则该提案区块在全网其他节点验证必将失败,从而不但没有铸块收益,还付出了算力成本。

Algorand协议并没有设计经济激励机制,Micali教授曾回应”Algorand协议只需要进行平凡的计算,因此不需要激励”。在没有经济激励机制下,高性能带宽和服务器必然不愿意参与(因为它本身要消耗费用),整个网络会遇到网络本身无法解决的困难。

(6)存在潜在的安全问题

网络用户必须连续访问其私钥,以确定其在每一轮中的VRF状态(即验证者、提议者,或者两者都不是)。

一般认为,对于那些将大量资产存储在区块链上的个人,为了防止攻击,他们应该把私钥以冷存储的方式进行保存。而持续的验证(需要经常签名)会需要高频率地动用私钥,从而增加被攻击的风险。这显然将导致网络中很多诚实的个体(出于安全的考虑)会避免参与验证过程,从而造成区块链缺乏活力的问题。

(7)买断问题

在区块链的婴儿期,系统的通证价值通常较低,其市值也是处在相对较低的水平。Token的发行往往要经过私募-->基石-->公募 等逐步分散的过程,因此很长一段时间里币是集中在少数人手里的,因此任何POS共识都面临着EOS类似的中心化的问题。

(8)没有惩罚问题

Algorand所存在的另一个问题是,没有办法识别“离线验证者”并惩罚它们。因此,在没有惩罚措施来防止无效的情况下,没有经济激励就是一个问题,很多人会选择不为共识做贡献,因此离开这个网络。假设网络中只有10%的诚信节点在不断地进行验证,而其余节点是离线的状态,与此同时,恶意的节点选择保持在线,那其就很容易超过在线委员会节点。这使得恶意节点更容易控制共识。

总的来说,Algorand的VRF和加密抽签后验性给出了一个解决“三角悖论”的很好设计思想,但其在验证环节的设计更偏单纯的学术化理想化,导致其对网络流量、有效通讯数据等实际工程落地思考不够,严重影响了公链运行性能、节点网络规模、账本存储容量和去中心化程度。
转载:https://www.8btc.com/article/348383

zk-SNARKs 介绍(零知识证明概述以及如何将 zk-SNARK 集成到以太坊中)

在这篇文章中,我们旨在从实用的角度概述 zk-SNARK。我们会将实际的数学视为一个黑匣子,并尝试围绕如何使用它们建立一些直觉。我们还将给出最近在以太坊中集成 zk-SNARKs 的工作的简单应用

零知识证明

零知识证明的目标是让验证者能够说服自己,证明者拥有秘密参数的知识,称为见证,满足某种关系,而不会将见证透露给验证者或其他任何人。

我们可以更具体地将其理解为有一个程序,表示为C,接受两个输入:C(x, w)。输入x是公开输入,w是秘密见证输入。该程序的输出是布尔值,即,或者true或false。然后给目标一个特定的公共输入x,证明证明者知道一个秘密输入w,使得C(x,w) == true。

我们将专门讨论非交互式零知识证明。这意味着证明本身是一组数据,无需证明者的任何交互即可对其进行验证。

示例程序

假设 Bob 得到了H某个值的散列,他希望有一个证明 Alice 知道s散列到的值H。通常 Alice 会通过给sBob来证明这一点,之后 Bob 会计算哈希并检查它是否等于H。

但是,假设 Alice 不想向sBob透露该值,而只是想证明她知道该值。她可以为此使用 zk-SNARK。

我们可以使用以下程序来描述 Alice 的场景,这里编写为一个 Javascript 函数:

function C(x, w) {  return ( sha256(w) == x );}

换句话说:程序接受一个公共散列x和一个秘密值w,true如果w等于SHA-256 散列,则返回x。

使用函数翻译 Alice 的问题,C(x,w)我们看到 Alice 需要创建一个证明,证明她拥有s这样的C(H, s) == true,而不必透露s。这是 zk-SNARKs 解决的一般问题。

zk-SNARK 的定义

甲 ZK-SNARK 包括三个算法 G, P, V 定义如下:

该 密钥生成器 G 需要一个秘密参数 lambda 和程序 C,并产生两个公开可用的按键, 证明键 pk,和一个 验证密钥 vk。这些密钥是公共参数,只需为给定程序生成一次 C。

该 证明 P 作为输入的证明键 pk,公共投入 x 和私人见证 w。该算法生成 证明 prf = P(pk, x, w) 者知道证人 w 并且证人满足程序的证明。

该 验证 V 单位计算 V(vk, x, prf) 其回报率 true ,如果证明是正确的, false 否则。因此,如果证明者知道w 满足 的证人,则此函数返回真 C(x,w) == true。

这里注意lambda 生成器中使用的秘密参数 。该参数有时会使在实际应用中使用 zk-SNARK 变得棘手。这样做的原因是任何知道这个参数的人都可以生成假证明。具体来说,给定任何程序 C 和公共输入, x 一个知道的人 lambda 可以生成一个证明 fake_prf ,以便 V(vk, x, fake_prf) 在true 不知道秘密的情况下 评估为 w。

因此,实际运行生成器需要一个非常安全的过程,以确保没有人知道并将参数保存在任何地方。这就是 Zcash 团队为了生成证明密钥和验证密钥而进行极其复杂的仪式的原因 ,同时确保“有毒废物”参数 lambda 在此过程中被销毁。

我们示例程序的 zk-SNARK

Alice 和 Bob 在实践中如何使用 zk-SNARK 来让 Alice 证明她知道上面例子中的秘密值?

首先,如上所述,我们将使用由以下函数定义的程序:

function C(x, w) {
  return ( sha256(w) == x );
}

第一步是让 Bob 运行生成器 G 以创建证明密钥 pk 和验证密钥 vk。首先,随机生成 lambda 并将其用作输入:

(pk, vk) = G(C, lambda)

小心处理参数 lambda,因为如果 Alice 了解 lambda 的值,她将能够创建假证明。Bob 将与 Alice 共享 pk 和 vk。

Alice 现在将扮演证明者的角色。她需要证明她知道哈希到已知哈希 H 的值 s。 她使用输入 pk、H 和 s 运行证明算法 P 以生成证明 prf:

prf = P(pk, H, s)

接下来 Alice 向 Bob 提供证明 prf,Bob 运行验证函数 V(vk, H, prf),在这种情况下会返回 true,因为 Alice 正确地知道秘密 s。Bob 可以确信 Alice 知道这个秘密,但 Alice 不需要向 Bob 透露秘密。

可重复使用的证明和验证密钥

在我们上面的例子中,如果 Bob 想向 Alice 证明他知道一个秘密,则不能使用 zk-SNARK,因为 Alice 无法知道 Bob 没有保存 lambda 参数。鲍勃可能能够伪造证明。

如果一个程序对很多人有用(比如 Zcash 的例子),一个独立于 Alice 和 Bob 的可信独立组可以运行生成器并创建证明密钥 pk 和验证密钥 vk,这样就不会有人了解 lambda。

任何相信该团体没有作弊的人都可以使用这些密钥进行未来的互动。

以太坊中的 zk-SNARK

开发人员已经开始将 zk-SNARKs 集成到以太坊中。这看起来像什么?具体来说,您可以将验证算法的构建块以预编译合约的形式添加到以太坊中。方法如下:在链下运行生成器以生成证明密钥和验证密钥。然后,任何证明者都可以使用证明密钥来创建证明,也是链下的。然后,您可以在智能合约中运行通用验证算法,使用证明、验证密钥和公共输入作为输入参数。然后,您可以使用验证算法的结果来触发其他链上活动。

示例:保密交易

这是一个简单的例子,说明 zk-SNARKs 如何帮助保护以太坊的隐私。假设我们有一个简单的代币合约。通常,代币合约的核心是从地址到余额的映射:

mapping (address => uint256) balances;

我们将保留相同的基本核心,除了用余额的散列替换余额:

mapping (address => bytes32) balanceHashes;

我们不会隐藏交易的发送者或接收者。但我们会隐藏余额和发送金额。此属性有时称为机密交易

我们将使用两个 zk-SNARK 将令牌从一个帐户发送到另一个帐户。一份证明由发送方创建,一份由接收方创建。

通常在一个代币合约中,为了使一笔大小值的交易有效,我们需要验证以下内容:

balances[fromAddress] >= value

我们的 zk-SNARK 需要证明这是成立的,并且更新后的哈希值与更新后的余额相匹配。

主要思想是发送者将使用他们的起始余额和交易价值作为私人输入。作为公共输入,他们使用起始余额、期末余额和价值的哈希值。同样,接收者将使用起始余额和价值作为秘密输入。作为公共输入,他们使用起始余额、期末余额和价值的哈希值。

下面是我们将用于发送者 zk-SNARK 的程序,其中 x 代表公共输入,w 代表私人输入。

function senderFunction(x, w) {
  return (
    w.senderBalanceBefore > w.value &&
    sha256(w.value) == x.hashValue &&
    sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore &&
    sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter
  )
}

接收器使用的程序如下:

function receiverFunction(x, w) {
  return (
    sha256(w.value) == x.hashValue &&
    sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
    sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
  )
}

程序检查发送余额是否大于发送的值,并检查所有散列是否匹配。一组受信任的人将为我们的 zk-SNARK 生成证明和验证密钥。我们称它们为 confTxSenderPk、confTxSenderVk、confTxReceiverPk 和 confTxReceiverVk。

在代币合约中使用 zk-SNARKs 看起来像这样:

function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
  bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
  bytes32 hashReceiverBalanceBefore = balanceHashes[_to];

  bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);

  bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);

  if(senderProofIsCorrect && receiverProofIsCorrect) {
    balanceHashes[msg.sender] = hashSenderBalanceAfter;
    balanceHashes[_to] = hashReceiverBalanceAfter;
  }
}

因此,区块链上唯一的更新是余额的哈希值,而不是余额本身。但是,我们可以知道所有余额都已正确更新,因为我们可以自行检查证明是否已得到验证。

细节

上述保密交易方案主要是为了说明如何在以太坊上使用 zk-SNARKs 的一个实际例子。为了创建一个强大的机密交易方案,我们需要解决一些问题:

  1. 用户需要在客户端跟踪他们的余额,如果您失去余额,这些代币将无法恢复。余额也许可以使用从签名密钥派生的密钥加密存储在链上。
  2. 余额需要使用 32 字节的数据并编码熵,以防止反向散列计算余额的能力。
  3. 需要处理发送到未使用地址的边缘情况。
  4. 发送方需要与接收方交互才能发送。一个人可能有一个系统,发送者使用他们的证据来发起交易。然后接收方可以在区块链上看到他们有一个“待处理的传入交易”并可以完成它。

原文:https://consensys.net/blog/developers/introduction-to-zk-snarks/

零知识证明:STARKs 与 SNARKs

新技术之间的冲突

纵观历史,总是有类似的技术大约在同一时间进入市场,寻求类似的结果,但以不同的方式解决问题。当这种市场现象发生时,采用者应该尝试客观地评估每一项技术。

由于 STARK 阵营和 SNARK 阵营都对各自的技术充满热情,我们认为对这两种技术进行客观比较会很有趣。

STARKs 与 SNARKs

快速复习一下,零知识证明技术使一方能够向另一方证明他们知道某些事情,而证明者不必自己传达信息来证明他们的知识。它们既是一种隐私增强技术,因为它们减少了用户之间需要提供的信息量,又是一种扩展技术,因为它们可以允许以更快的速度验证证明,因为它们不包含全部信息非私有系统的信息。

当今市场上最引人注目的两种零知识技术是 zk-STARKs 和 zk-SNARKs。两者都是双方证明知识的方法的首字母缩写词:zk-STARK代表零知识可扩展的透明知识论证,zk-SNARK代表零知识简洁非交互式知识论证。本文将深入探讨从文化和技术的角度分析这两种不同的零知识技术之间的核心差异。此外,这两种零知识技术本质上都是非交互式的,这意味着代码可以部署并自主运行。

下面,我们有几个表格描述了两种技术之间的一些高级差异。我们还将深入研究段落格式的差异。


资料来源:物质实验室

SNARK

2012 年 1 月,加州大学伯克利分校一位名叫 Alessandro Chiesa 的教授与人合着了一篇论文,为他们首次构建的零知识证明创造了术语 zk-SNARK。Zk-SNARK 在其基础上依赖于椭圆曲线来保证安全性。密码学中的椭圆曲线在基本假设下运行,即找到相对于公知基点的随机椭圆曲线元素的离散对数是不可行的。

虽然关于椭圆曲线随机数生成器是否存在后门一直存在很大争议,但整个算法通常仍然是安全的。尽管侧信道攻击中有几个流行的漏洞,但可以通过多种技术轻松缓解。量子攻击确实笼罩在基于椭圆曲线的密码学上,但打破其安全模型所需的量子计算尚未广泛应用。

除了基于椭圆曲线之外,zk-SNARK 还需要可信设置。可信设置是指密钥的初始创建事件,用于创建私人交易所需的证明以及这些证明的验证。最初,当这些密钥被创建时,在验证密钥和发送私人交易的密钥之间有一个隐藏的参数链接。如果用于在可信设置事件中创建这些密钥的秘密没有被破坏,则可以利用这些秘密通过虚假验证来伪造交易,从而使持有者能够执行诸如凭空创建新令牌并使用它们等操作用于交易。由于 zk-SNARKs 的隐私特性,将无法验证凭空创建的代币实际上是凭空创造。话虽如此,信任设置仅在最初需要

因此,基于 SNARK 的网络的用户必须依赖于正确执行可信设置的事实,这意味着与可信设置密钥相关的秘密已被销毁,并且不会由监督仪式的个人持有。对可信设置的依赖一直是 SNARK 批评者最关注的领域之一。话虽如此,开发人员只需要最初使用可信设置,而不是持续使用。

SNARK 的另一个重要批评领域是它们不具有量子抗性。一旦量子计算在很大程度上可用,SNARKs 背后的隐私技术将被打破。当然,SNARKs 的支持者正确地指出,当使用量子计算机时,我们将面临更多问题,例如破坏 RSA 和大多数钱包基础设施。

话虽如此,尽管存在与可信设置相关的问题,但实际上 SNARK 的采用速度比 STARK 快得多的原因有很多。SNARKs 比 STARKs 早几年被发现,这使该技术在采用方面取得了重要的领先优势。Zcash 是较早的数字资产项目之一,它在区块链开发社区中普及了 SNARK 的使用。由于 Zcash 和其他 SNARKs 的采用者,SNARKs 拥有最多的开发人员库、已发布的代码、项目和积极致力于该技术的开发人员。除了 Zcash,新兴的 DEX Loopring 也使用了 SNARK。如果开发人员想开始使用零知识技术,他们在使用 SNARK 方面将比 STARK 获得更多支持。

此外,据估计 SNARK仅需要 STARK 所需气体的 24%,这意味着与 SNARK 进行交易对最终用户来说要便宜得多。最后,SNARKs 的证明大小比 STARKs 小得多,这意味着它需要更少的链上存储。

STARKs

虽然 SNARKs 在文档和开发人员支持方面比 STARKs 有一些明显的优势,但 STARKs 确实提供了一些独特的好处。但首先,让我们从技术角度深入了解 STARK 是什么。

Eli Ben-Sasson、Iddo Bentov、Yinon Horeshy 和 Michael Riabzev 在2018 年撰写了第一篇描述 STARK 的论文。与 SNARK 不同,STARK 的基础技术依赖于哈希函数。马上,依靠散列函数提供了一些好处,例如抗量子。此外,开始在网络中使用 STARK 不需要可信设置。

话虽如此,STARKs 的证明尺寸远大于 SNARKs,这意味着验证 STARKs 比 SNARKs 花费更多的时间,并且也导致 STARKs 需要更多的 gas。

此外,由于缺乏开发人员文档和社区,开发人员将很难使用 STARK。虽然有一些项目创建了基于 STARK 的扩展解决方案,例如STARKWARE,但 SNARKs 社区仍然要大得多。

虽然两个开发者社区都支持 SNARKs 和 STARKs,但以太坊基金会特别表达了对利用 Starks 的 STARKware 的声音支持。事实上,以太坊基金会向 STARKware 提供了 1200 万美元的赠款,这清楚地表明了他们对新兴技术的投入。

此外,虽然与 SNARK 相比,STARK 的文档相形见绌,但技术社区最近为那些希望实施尖端技术的人开发了更多资源

感谢 Anish Mohammad 的洞察力和 专业知识。

原文:https://consensys.net/blog/blockchain-explained/zero-knowledge-proofs-starks-vs-snarks/

什么是 zk-SNARK?

Zcash 是 zk-SNARKs 的第一个广泛应用,zk-SNARKs 是一种新颖的零知识密码学形式。Zcash 强大的隐私保证源于这样一个事实,即 Zcash 中的屏蔽交易可以在区块链上完全加密,但仍然可以通过使用 zk-SNARK 证明在网络的共识规则下验证其有效性。

首字母缩略词 zk-SNARK 代表“零知识简洁的非交互式知识论证”,指的是一种证明结构,在这种结构中,人们可以证明拥有某些信息,例如一个秘密密钥,而无需透露该信息,并且之间没有任何交互证明者和验证者。

“零知识”证明允许一方(证明者)向另一方(验证者)证明一个陈述是真实的,而不会透露超出陈述本身有效性的任何信息。例如,给定一个随机数的散列,证明者可以说服验证者确实存在一个具有该散列值的数字,而无需透露它是什么。

在零知识“知识证明”中,证明者不仅可以说服验证者该数字存在,而且他们实际上知道这样一个数字——同样,无需透露有关该数字的任何信息。“Proof”和“Argument”之间的区别是非常技术性的,我们不在这里讨论。

“简洁”的零知识证明可以在几毫秒内得到验证,即使是关于非常大的程序的语句,证明长度也只有几百字节。在第一个零知识协议中,证明者和验证者必须来回通信多轮,但在“非交互式”结构中,证明由从证明者发送到验证者的单个消息组成。目前,生成非交互式且足够短以发布到区块链的零知识证明的最有效的已知方法是具有初始设置阶段,该阶段生成在证明者和验证者之间共享的公共参考字符串。我们将这个公共引用字符串称为系统的公共参数。

如果有人可以访问用于生成这些参数的秘密随机性,他们将能够创建对验证者来说看起来有效的虚假证明。对于 Zcash,这意味着恶意方可以制造假币。为了防止这种情况发生,Zcash 通过精心设计的多方仪式生成了公共参数。要了解有关我们的参数生成仪式的更多信息,并查看我们为防止暴露 Zcash 所必需的秘密随机性(例如,计算机被喷灯)而采取的预防措施,请访问我们的Paramgen 页面。要了解有关参数生成协议背后的数学原理的更多信息,请阅读我们关于该主题的博客文章或白皮书 ( 1 , 2 )。

如何在 Zcash 中构建 zk-SNARK

为了在 Zcash 中实现零知识隐私,根据网络的共识规则确定交易有效性的函数必须返回交易是否有效的答案,而不会泄露其执行计算的任何信息。这是通过在 zk-SNARKs 中编码一些网络的共识规则来完成的。在高层次上,zk-SNARK 的工作原理是首先将您想要证明的内容转换为关于了解某些代数方程的解的等效形式。在下一节中,我们简要概述了如何将确定有效交易的规则转换为方程,然后可以对候选解决方案进行评估,而无需向验证方程的各方透露任何敏感信息。

Computation → Arithmetic Circuit → R1CS → QAP → zk-SNARK

将我们的交易有效性函数转化为数学表示的第一步是将逻辑步骤分解为尽可能小的操作,从而创建一个“算术电路”。类似于布尔电路,其中程序被编译成离散的单步,如 AND、OR、NOT,当程序被转换为算术电路时,它被分解为由加法、减法等基本算术运算组成的单步,乘法和除法(尽管在我们的特殊情况下,我们将避免使用除法)。

以下是用于计算表达式 (a+b)(bc) 的算术电路的示例:

看看这样的电路,我们可以将输入值 a、b、c 视为在电线上从左到右“行进”到输出电线。我们的下一步是构建所谓的 1 级约束系统或 R1CS,以检查值是否“正确移动”。在这个例子中,R1CS 将确认,例如,从 b 和 c 进入的乘法门出来的值是 b*c。

在这个 R1CS 表示中,验证器必须检查许多约束——几乎电路的每条线路都有一个约束。(由于技术原因,事实证明我们只对来自乘法门的电线有约束。)在 2012 年关于该主题的论文中,Gennaro、Gentry、Parno 和 Raykova 提出了一种“将所有这些约束捆绑在一起”的好方法. 此方法使用称为二次算术程序 (QAP) 的电路表示。需要检查的单个约束现在在多项式之间而不是在数字之间。多项式可能非常大,但这没关系,因为当多项式之间不存在同一性时,它在大多数情况下都不会成立。因此,您只需检查两个多项式是否在随机选择的一个点上匹配 以便以高概率正确验证证明。

如果证明者事先知道验证者会选择检查哪一点,他们可能能够制作无效的多项式,但仍然满足该点的身份。与ZK-SNARKs,复杂的数学技术,如同态加密配对的椭圆曲线的用于评价多项式“盲目地” -即在不知道哪个点正被评估。上面描述的公共参数用于确定将检查哪个点,但采用加密形式,以便证明者和验证者都不知道它是什么。

到目前为止的描述主要解决了如何获得“SNARKs”中的 S 和 N——如何获得一个简短的、非交互式的、单消息证明——但没有解决“zk”(零知识)部分,它允许证明者维护其秘密输入的机密性。事实证明,在这个阶段,通过让证明者使用仍然满足所需身份的原始多项式的“随机移位”,可以轻松添加“zk”部分。

有关 Zcash 中 zk-SNARKs 背后关键概念的分步深入解释,请参阅我们的 SNARKs 解释器系列,其中包含以下帖子:

  1. 同态隐藏
  2. 多项式的盲评估
  3. 系数检验与假设的知识
  4. 如何使多项式的盲评估可验证
  5. 从计算到多项式
  6. 匹诺曹协议
  7. 椭圆曲线的配对

Zcash 使用bellman,这是一个用于 zk-SNARK 的 Rust 语言库。在 Sapling 升级之前,Zcash 使用了 C++ 库libsnark 的一个分支。要更深入地了解用于 Zcash 的 zk-SNARK 的协议,请参阅有关Pinocchio 协议的论文,该协议一直使用到 Sapling 升级,以及目前使用的Jens Groth 的 zk-SNARK。

如何应用 zk-SNARKs 来创建屏蔽交易

在比特币中,交易通过将发送者地址、接收者地址以及公共区块链上的输入和输出值链接起来来验证。Zcash 使用 zk-SNARKs 来证明有效交易的条件已得到满足,而无需透露有关所涉及的地址或价值的任何关键信息。屏蔽交易的发送者构建了一个证明来证明,很有可能:

  • 输入值总和为每个屏蔽传输的输出值。
  • 发件人证明他们拥有输入票据的私人消费密钥,从而赋予他们消费的权力。
  • 输入票据的私人支出密钥以加密方式链接到整个交易的签名,这样交易就不能被不知道这些私人密钥的一方修改。

此外,屏蔽交易必须满足下面描述的一些其他条件。
比特币跟踪未花费的交易输出 (UTXO) 以确定哪些交易是可以花费的。在 Zcash 中,UTXO 的屏蔽等价物称为“承诺”,花费承诺涉及揭示“无效者”。Zcash 节点保存所有已创建承诺的列表,以及已披露的所有无效者。承诺和无效符存储为哈希,以避免披露有关承诺的任何信息,或哪些无效符与哪些承诺相关。
对于由屏蔽支付创建的每个新票据,都会发布一个承诺,其中包含以下各项的散列:票据发送到的地址、发送的金额、该票据唯一的数字“rho”(后来用于派生无效符)和一个随机随机数。

Commitment = HASH(收件人地址,金额,rho,r)

当一个受保护的交易被花费时,发送者使用他们的花费密钥来发布一个无效符,它是来自尚未花费的现有承诺的秘密唯一编号(“rho”)的散列,并提供零知识证明证明他们被授权消费。该散列不能已经在跟踪区块链中每个节点保存的已用交易的无效符集合中。

Nullifier = HASH(支出密钥,rho)

屏蔽交易的零知识证明验证了,除了上面列出的条件外,以下断言也是正确的:

  • 对于每个输入注释,都存在显露的承诺。
  • 无效符和票据承诺计算正确。
  • 输出音符的无效符与任何其他音符的​​无效符发生冲突是不可行的。

除了用于控制地址的支出密钥之外,Zcash 还使用一组证明和验证密钥来创建和检查证明。这些密钥在上面讨论的公共参数仪式中生成,并在 Zcash 网络中的所有参与者之间共享。对于每个受保护的交易,发送方使用他们的证明密钥来生成他们输入有效的证明。矿工通过使用验证密钥检查证明者的计算来检查受保护的交易是否遵循共识规则。Zcash 的证明生成方式需要证明者预先做更多的工作,但它简化了验证,从而将主要的计算工作卸载给交易的创建者(这就是为什么创建屏蔽的 Zcash 交易可能需要几个秒,

Zcash 的屏蔽交易的隐私依赖于标准的、久经考验的密码学(散列函数和流密码),但它是 zk-SNARKs 的添加,与承诺和无效系统一起应用,允许屏蔽交易的发送者和接收者证明加密交易是有效的。为加密货币提供隐私的其他方法依赖于模糊交易之间的联系,但 Zcash 交易可以存储在完全加密的区块链上这一事实为加密货币应用开辟了新的可能性. 加密交易允许各方享受公共区块链的好处,同时仍然保护他们的隐私。计划中的未来升级将允许用户自行决定有选择地披露有关屏蔽交易的信息。有关Zcash 的未来计划,请参阅我们的 Zcash 近期博客文章。

有关如何在 Zcash 中构建屏蔽交易的更深入解释,请参阅我们关于屏蔽地址之间的交易如何工作的博客文章。有关当前 Zcash 协议的完整详细信息,请参阅我们的协议规范

zk-SNARKs 的未来应用

在 Zcash 中创建屏蔽交易只是 zk-SNARK 的许多可能应用中的一个例子。理论上,您可以使用 zk-SNARK 来验证任何关系,而不会泄露输入或泄漏信息。为复杂函数生成证明仍然是计算密集型的,对于许多应用程序来说不实用,但Zcash 团队正在推动优化 zk-SNARKs 的边界,并且已经通过更有效的实现开辟了新天地。

就目前而言,Zcash 的 zk-SNARK 实现可以添加到任何现有的分布式账本解决方案中,作为企业用例的零知识安全层Zcash 团队的科学家是世界上最博学的 zk-SNARKs 研究人员之一,并不断致力于提出新的应用程序并提高零知识协议的效率。如果你的业务需要,可以从零知识证明或具有强大的隐私blockchain应用的解决方案中受益,取得联系我们的业务发展团队。

原文:https://z.cash/technology/zksnarks/