解释SNARKs 第4部分:如何进行可验证多项式盲估

原文出自:https://blog.z.cash/snark-explain4/
作者:Ariel Gabizon
译者:Matter实验室

In this part, we build on Part II and III to develop a protocol for verifiable blind evaluation of polynomials, which we will define shortly. In Part V we’ll start to see how such a protocol can be used for constructing SNARKs, so bear with me a little bit longer for the connection to SNARKs :).

在这一部分中,我们在第二部分和第三部分的基础上开发可验证的多项式盲估协议,我们将在稍后给出它的定义。在第五部分中,我们将开始看到如何用这个协议构建SNARKs,因此,请稍微忍受长一点点时间,让我们来建立和SNARKs的联系。:)

Suppose, as in Part II, that Alice has a polynomial P of degree d and Bob has a point s∈Fp that he chose randomly. We want to construct a protocol that allows Bob to learn E(P(s)), i.e. the hiding of P evaluated at s, with two additional properties:

  1. Blindness: Alice will not learn s (and Bob will not learn P).
  2. Verifiability: The probability that Alice sends a value not of the form E(P(s)) for P of degree d that is known to her, but Bob still accepts – is negligible.

This is what we call verifiable blind evaluation of a polynomial. The protocol in Part II gave us the first item but not the second. To get verifiability we need an extended version of the Knowledge of Coefficient Assumption (KCA) that was presented in Part III.

假设,在 第二部分 中,Alice 有 d 阶多项式 P,Bob 有它随机选择的点 s∈Fp 。我们希望建立一个可以让 Bob 知道 E(P(s)) 的协议,比如,采用两种额外的特性,评估 Ps 上的匿数:

  1. 盲的: Alice 将不会知道 s (同时 Bob 也不会知道 P )。
  2. 可验证性:Alice发送一个不是她所知道的以d阶多项式P所构成的E(P(s))形式的值,而Bob仍然接受的可能性,微乎其微。

这就是我们所说的可验证多项式盲估。第二部分的协议给出了我们需要的第一个条款,但没有包括第二个。为了实现可验证性,我们需要一个利用第三部分所描述的知识系数假设(KCA)来进行扩展的版本。

The verifiability and blindness properties are useful together because they make Alice decide what polynomial P she will use without seeing s. [1] This, in a sense, commits Alice to an “answer polynomial” without seeing the “challenge point” s. This intuition will become more clear in the next parts of the series.

[1] In the fully formal proof, things are somewhat more subtle, as Alice does see some information about s before deciding on her P – for example, the hidings of s ,…, s^d.

可验证性和盲的特性合在一起非常有用,因为它可以让 Alice 在没看到 s 的情况下,决定使用何种多项式 P。[1] 这在某种意义上,可以保证 Alice 在没看到 “挑战点” s 的情况下得到”答案多项式”。这种直觉将在后面的系列中变得更加清晰。

    • [1]在完全正式的证明中,这些是多少有些微妙的,比如 Alice 在决定她的P 之前确实看到了一些关于 s 的信息 —— 比如,s ,…, s^d的匿数。

AN EXTENDED KCA

扩展的知识系数假设(KCA)

The KCA as we defined it in Part III essentially said something like this: If Bob gives Alice some α-pair (a,b=α⋅a) and then Alice generates another α-pair (a′,b′), then she knows c such that a′=c⋅a. In other words, Alice knows the relation between a′ and a.

我们在第三部分提出的KCA定义从本质上说像这样:如果Bob给了Alice某个α-pair (a,b=α⋅a),那么Alice生成另外的α-pair (a′,b′),则Alice就知道 c 满足a′=c⋅a。换句话说,Alice知道a′a之间的关系。

Now, suppose that instead of one, Bob sends Alice several α-pairs (a1,b1),…,(ad,bd) (for the same α); and that again, after receiving these pairs, Alice is challenged to generate some other α-pair (a′,b′). Recall that the main point is that Alice must do so although she does not know α.

现在,假设Bob发送给Alice不是一个而是多个α-pairs (a1,b1),…,(ad,bd)(以相同的α);同样,在收到这些对之后,Alice被挑战来产生另外一些α-pair (a′,b′)。回想一下,关键点在于 Alice 必须在她不知道α的前提下这么做。

As we saw in Part III, a natural way for Alice to generate such an α-pair, would be to take one of the pairs (ai,bi) she received from Bob, and multiply both elements by some c∈F(∗,p); if (ai,bi) was an α-pair, then (c⋅ai,c⋅bi) will be one too. But can Alice generate α-pairs in more ways now that she’s received multiple α-pairs? Perhaps using several of the received α-pairs simultaneously to get a new one?

正如我们在第三部分看到的,一个让 Alice 产生这样的 α-pair 的自然方式,是选取她从 Bob 处收到的配对中的一个 (ai,bi),并将两个元素都与某个 c∈F(∗,p) 相乘; 如果 (ai,bi) 是一个 α-pair,则 (c⋅ai,c⋅bi) 将同样也是。 但是,既然Alice收到了多个α-pairs,那么她能以多种方式产生α-pairs吗?或许可以同时使用多个收到的 α-pairs 来产生一个新的配对?

The answer is yes: For example, Alice can choose two values c1,c2∈Fp and compute the pair (a′,b′)=(c1⋅a1+c2⋅a2,c1⋅b1+c2⋅b2). An easy computation shows that, as long as a′ is non-zero, this is also an α-pair:

b′=c1⋅b1+c2⋅b2=c1α⋅a1+c2α⋅a2=α(c1⋅a1+c2⋅a2)=α⋅a′.

答案是肯定的: 例如, Alice能选择两个值 c1,c2∈Fp 并计算配对 (a′,b′)=(c1⋅a1+c2⋅a2,c1⋅b1+c2⋅b2). 一个简单的计算显示,只要a′不为零,这就是一个**
α**-pair:
b′=c1⋅b1+c2⋅b2=c1α⋅a1+c2α⋅a2=α(c1⋅a1+c2⋅a2)=α⋅a′.

More generally, Alice can take any linear combination of the given d pairs – that is choose any c1 ,…, cd ∈ Fp and define (a′,b′)=(∑(d,i=1)ci⋅ai,∑(d,i=1)ci⋅bi).

更一般的,Alice 可以使用给定的d个配对的任何线性组合——那就选择任意的 c1,…,cd∈Fp,同时定义 (a′,b′)=(∑(d,i=1)ci⋅ai,∑(d,i=1)ci⋅bi).

Note that, if Alice uses this strategy to generate her α-pair she will know some linear relation between a′ and a1,…,ad; that is, she knows c1,…,cd such that a′=∑(d,i=1) ci⋅ai.

注意到,如果 Alice 使用这种策略生成她的 α-pair,她将知道某种 a′a1,…,ad 之间的线性关系;也就是说,她将知道c1,…,cd可以满足a′=∑(d,i=1) ci⋅ai

The extended KCA states, essentially, that this is the only way Alice can generate an α-pair; that is, whenever she succeeds, she will know such a linear relation between a′ and a1,…,ad. More formally, suppose that G is a group of size p with generator g written additively as in Part III. The d-power Knowledge of Coefficient Assumption (d-KCA) [2] in G is as follows:

The d-KCA was introduced in a paper of Jens Groth

扩充的 KCA 表明,本质上,这是 Alice 产生一个 α-pair 的唯一方式; 并且,当她成功时,她会知道 a′a1,…,ad 之间有这样的线性关系。 更正式地来说,假设 G 是一个像第三部分说的那样,拥有字面加法的生成器g,并且以p为大小的群。 在G中的d次知识系数假设(d-KCA)[2]就是下面这样:

    • [2]d-KCA在Jens Groth的论文中有介绍。

d-KCA: Suppose Bob chooses random α∈F(∗,p) and s∈Fp, and sends to Alice the α-pairs (g,α⋅g),(s⋅g,αs⋅g),…,(( s^d )⋅g, α⋅(s^d )⋅g). Suppose that Alice then outputs another α-pair (a′,b′). Then, except with negligible probability, Alice knows c0,…,cd∈Fp such that ∑(d,i=0) ci⋅( s^i )⋅g=a′.

d-KCA: 假设 Bob 随机选择 α∈F(∗,p)s∈Fp, 并且发送给 Alice α-pairs (g,α⋅g),(s⋅g,α⋅s⋅g),…,(( s^d )⋅g, α⋅( s^d )⋅g). 假设 Alice 随后输出了另外一个 α-pair (a′,b′)。这时,除了微乎其微的可能性外,Alice 知道 c0,…,cd∈Fp 满足 ∑(d,i=0) ci⋅( s^i )⋅g=a′.

Note that in the d-KCA Bob does not send an arbitrary set of α-pairs, but one with a certain “polynomial structure”. This will be useful in the protocol below.

注意到,在 d-KCA 中,Bob 并没有发送任意的 α-pairs,而是发送了有特定“多项式结构” 的多项式。这将对下面提到的协议有所帮助。

THE VERIFIABLE BLIND EVALUATION PROTOCOL

可验证的盲估协议

Assume that our HH is the mapping E(x)=x⋅g for a generator g of G as above.

For simplicity, we present the protocol for this particular E:

  1. Bob chooses a random α∈F(∗,p), and sends to Alice the hidings g,( s )⋅g, … ,( s^d )⋅g (of 1,s,…,s^d) and also the hidings α⋅g,α⋅( s )⋅g,…,α⋅( s^d )⋅g (of α,α⋅( s ),…,α⋅(s^d )).

  2. Alice computes a=P(s)⋅g and b=α⋅P(s)⋅g using the elements sent in the first step, and sends both to Bob.

  3. Bob checks that b=α⋅a, and accepts if and only if this equality holds.

假设我们的HH是由上面说到的G的一个生成器g所构成的映射 E(x)=x⋅g

为了简单,我们就这个特定的E来描述一下协议:

  1. Bob 选择一个随机的 α∈F(∗,p),并且发送给 Alice 一系列匿数 g,( s )⋅g, … ,( s^d )⋅g (对应着 1,s,…,s^d) ,以及匿数 α⋅g,α⋅( s )⋅g,…,α⋅( s^d )⋅g (对应着 α,α⋅( s ),…,α⋅(s^d ))。

  2. Alice 使用第一步中发送的元素计算出 a=P(s)⋅gb=α⋅P(s)⋅g,并且都发送给 Bob。

  3. Bob 检查 b=α⋅a,当且仅当这个等式成立就会将(a,b)接受。

First, note that given the coefficients of P, P(s)⋅g is a linear combination of g,( s )⋅g,…,( s^d )⋅g; and αP(s)⋅g is a linear combination of α⋅g,α⋅( s )⋅g,…,α⋅( s^d )⋅g. Thus, similarly to the protocol of Part II, Alice can indeed compute these values from Bob’s messages for a polynomial P that she knows.

首先,注意到对于给定的系数 PP(s)⋅gg,( s )⋅g,…,( s^d )⋅g 的线性组合;而 αP(s)⋅gα⋅g,α⋅( s )⋅g,…,α⋅( s^d )⋅g 的线性组合。 因此,与第二部分的协议相似,Alice 确实能由她所知道的多项式P根据Bob的消息计算出这些值。

Second, by the d-KCA if Alice sends a,b such that b=α⋅a then almost surely she knows c0,…,cd∈Fp such that a=∑(d,i=0)ci⋅( s^i )⋅g. In that case, a=P(s)⋅g for the polynomial P(X)=∑(d,i=0)ci⋅( X^i ) known to Alice. In other words, the probability that Bob accepts in Step 3 while at the same time Alice does not know such a P is negligible.

其次,通过d-KCA,如果Alice发送的 a,b 满足 b=α⋅a,则几乎可以确认她知道 c0,…,cd∈Fp 满足 a=∑(d,i=0)ci⋅( s^i )⋅g。在这种情况下,Alice是知道由多项式P(X)=∑(d,i=0)ci⋅( X^i )所构成的a=P(s)⋅g的。换句话说,Bob在第三步成功接受的同时,Alice并不知道这样的P的可能性微乎其微。

To summarize, using the d-KCA we’ve developed a protocol for verifiable blind evaluation of polynomials. In the next posts, we will see how this building block comes to play in SNARK constructions.

总结一下,通过使用d-KCA,我们已经开发出一个协议来进行可验证多项式盲估。在接下来的文章中,我们将看到在SNARK的架构下,如何
总结,通过使用 d-KCA ,我们已经研发出了可验证的盲评价多项式的协议。在下面的博文中,我们将看到这样的构建块,如何在SNARK结构中产生作用。


译者总结

数学关系
交互模型
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,552评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,666评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,519评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,180评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,205评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,344评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,781评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,449评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,635评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,467评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,515评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,217评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,775评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,851评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,084评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,637评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,204评论 2 341

推荐阅读更多精彩内容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,274评论 0 10
  • pyspark.sql模块 模块上下文 Spark SQL和DataFrames的重要类: pyspark.sql...
    mpro阅读 9,438评论 0 13
  • 今天看一新闻,就是叙利亚新娘最小新娘才九岁,结论是太悲惨了。 我就想起大老师说过的话了,所谓低俗是自认为高雅的人发...
    奶味冰咖燕子阅读 165评论 2 1
  • 提起月光,我总想到《蒂凡尼的早餐》中的桥段,夜色渐浓时,赫本坐在窗台上弹唱这一首《月亮河》,柔情的嗓音伴着醇厚的吉...
    栗子_栗子阅读 508评论 9 3
  • 你在你的生活中文质彬彬 我在我的世界里刁蛮任性 你在你的世界里激情奔放 我在我的生活中温婉雅致 我们似曾相识吗 我...
    青苗之湾阅读 303评论 0 3