思维之海

——在云端,寻找我的星匙。

区块链隐私保护专题论文阅读

区块链隐私保护专题论文来自于《赛博智能经济与区块链》课程论文列表的 隐私保护 专题,一共4篇。将逐一解读。文章包括:

  • 《DIZK: A Distributed Zero Knowledge Proof System》
    • 一个 zkSNARKs 算法的分布式实现
  • 《Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts》
    • 加密实现隐私保护的通用智能合约
  • 《Bulletproofs: Short Proofs for Confidential Transactions and More》
    • 极小证据的零知识证明
  • 《BITE: Bitcoin Lightweight Client Privacy using Trusted Execution》
    • 轻量代理端的隐私保护

这几篇文章会包含一些密码学的知识(主要是零知识证明)。

References

https://vel.life/零知识证明简记

DIZK: A Distributed Zero Knowledge Proof System [USENIX Security 2018]

Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts [IEEE S&P (Oakland) 2017]

Bulletproofs: Short Proofs for Confidential Transactions and More [IEEE S&P (Oakland) 2018]

BITE: Bitcoin Lightweight Client Privacy using Trusted Execution. [USENIX Security 2019]

Zerocash: Decentralized Anonymous Payments from Bitcoin

基础概念

零知识证明 zero knowledge proofs

零知识证明学习资源汇总

什么是零知识证明?

零知识证明,使得一个个体可以向另一个个体证明某个声明的真实性,而无须透露额外的信息。

在一个加密数字货币系统中,这样的机制允许验证交易时无须透露交易的细节。

零知识证明最早源于:The Knowledge Complexity of Interactive Proof Systems

零知识证明分为:

  • 交互式:证明者与验证者需进行多轮通信
  • 非交互式:证明者按照协议向验证者发送一次消息,验证者根据协议即可验证。以 zkSNARKs 算法最为成熟实用,zcash 采用的便是 zkSNARKs 算法

零知识证明的核心在于如何向另一个人证明自己能做到某件特定的事

但是,为了不透露具体的解,必须在证明引入随机性,即只给出解的必要特征,而利用随机化隐去解的全部特征。

你除了“我是对的”啥也不会知道。

zkSNARKs 算法

zkSNARKs(零知识证明)简述

零知识证明算法之zkSNARKs李康

Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture,P25

zkSNARKs (zero-knowledge Succinct Non-interactive ARgument of Knowledge)。

“argument of knowledge”,即“知情证明”,也就是掌握某事内幕的证据。

和比特币系统不同,Zcash 中使用的 zkSNARKs 算法允许用户广播加密后的交易内容,并且其他用户可以在不知道具体交易内容明文的情形下验证交易的有效性。

“given a function F and input x, there is a secret w such that F(x,w) = true.”

$w$:私密的交易内容

$x$:加密的 $w$ 交易内容

$F$:一个检查 “$x$ 是加密的 $w$,$w$ 是一个有效的交易” 的断言操作

succinctness(简洁性):轻量的证据(128B)和低耗的验证(2ms plus a few µs per byte in x)。单纯的验证操作比 $F$ 的计算要快得多。


zkSNARKs给prover带来了极大的计算负担。

One of the main reasons for the prover’s overhead is that the statement to be proved must be represented via a set of logical gates forming a circuit, and the prover’s cost is quasi-linear(拟线性) in this circuit’s size. Unfortunately, this prover cost is not only in time but also in space.

prover在单个机器上运行 zkSNARKs 算法生成零知识证明非常消耗计算资源并且消耗内存。

这种计算瓶颈严重影响了SNARKs 的应用。

Groth16 协议

该协议为目前最高效的 zk-SNARK 协议。

单片机

https://zh.wikipedia.org/wiki/%E5%8D%95%E7%89%87%E6%9C%BA

单片机(Single-Chip Microcomputer,MCU),集成电路芯片。将CPU、存储系统、IO等功能单元集成到一块电路板上的产物,形成小而完善的微型计算机。主要用于工业控制,低功耗领域。

算术电路 arithmetic circuit

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

What are zk-SNARKs?

算术电路并非实际的电路,是一种对基本运算步骤的等效逻辑表示。又称代数电路(Algebraic Circuit)。

The first step in turning our transaction validity function into a mathematical representation is to break down the logical steps into the smallest possible operations, creating an “arithmetic circuit”. Similar to a boolean circuit where a program is compiled down to discrete, single steps like AND, OR, NOT, when a program is converted to an arithmetic circuit, it’s broken down into single steps consisting of the basic arithmetic operations of addition, subtraction, multiplication, and division (although in our particular case, we will avoid using division).

:将 (a+b)*(b*c) 展开为算术电路。

通过引入中间变量,将计算式转换为若干简单的单步算式。
中间的这些 ”+“ / ”x“ 计算节点被称为”gate“,即基于组合逻辑的电路。

Looking at such a circuit, we can think of the input values a, b, c as “traveling” left-to-right on the wires towards the output wire. Our next step is to build what is called a Rank 1 Constraint System, or R1CS, to check that the values are “traveling correctly”. In this example, the R1CS will confirm, for instance, that the value coming out of the multiplication gate where b and c went in is b*c.

在一个有限域(比如,模素数N的域)内,任何复杂的计算过程都可以表述为若干加法、乘法的复合运算。

例:展开 $y=(x+z)^{2}+z+1$。

1) T1 = x $\times$ x 2) T2 = z $\times$ z 3) T3 = 2 $\times$ x $\times$ z

$\longrightarrow$ 4) y = T1 + T2 + T3 + z + 1

因此,所有的Computation,都可以转化为等效的算术电路

一阶约束系统 R1CS

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

http://www.zeroknowledgeblog.com/index.php/the-pinocchio-protocol/r1cs

读懂区块链之零知识证明(zk-SNARK)

R1CS (Rank 1 Constraint System)是目前描述算术电路的一种形式语言。

we are ready to make another reduction (reduction = transforming one problem into another problem), and express the computation in a new format, a “rank-1 constraint system” (R1CS). This new format is not really “human readable”, so this translation will typically be performed by some kind of “compiler”. The idea of R1CS is that it keeps track of the values that each variable assumes during the computation, and binds the relationships among all those variables that are implied by the computation itself.

例: $y=x^3+x+5$。表示为R1CS的解形式向量。

定义 参数向量 s = [~one, x, ~out, sym_1, sym_2, sym_3](~one是伪变量,表示常数1)。

~one用来模拟常数项,即齐次坐标(见图形学-仿射变换-齐次坐标)。

将每个简单算式转换为“s . c = s . a s . b*”的形式。其中,“.”代表向量内积(将两个向量对应位置的成员相乘,结果再累加),abc是其系数向量。

依次完成所有简单算式的转化,将系数向量分别顺序排列,便得到ABC三个矩阵(例如,矩阵C的最后一行,就是简单算式“~out = sym_3 + 5”的系数向量c)。

这一系列向量组成的集合 / 矩阵,就称作”一阶约束系统(R1CS)”。

每一个算术电路中逻辑门都对应一个简单算式,即对应一个约束向量 (a, b, c)

我们得到解的新形式:
s = [~one, x, ~out, sym_1, sym_2, sym_3] = [1, 3, 35, 9, 27, 30]

例子中的R1CS矩阵:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

QAP Quadratic Arithmetic Program

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

Quadratic Arithmetic Programs: from Zero to HeroVitalik Buterin

https://asecuritysite.com/encryption/go_qap

零知识证明 - 从 QSP 到 QAP

SP - Span Program ,采用多项式形式实现计算的验证。

QSP - Quadratic Span Program,QSP 问题,实现基于布尔电路的 NP 问题的证明和验证。

QAP - Quadratic Arithmetic Program,QAP 问题,实现基于算术电路的 NP 问题的证明和验证,相对于 QSP,QAP 有更好的普适性。

PCP - Probabilistically Checkable Proof ,在 QSP 和 QAP 理论之前,学术界主要通过 PCP 理论实现计算验证。PCP 是一种基于交互的,随机抽查的计算验证系统。

NIZK - Non-Interactive Zero-Knowledge,统称,无交互零知识验证系统。NIZK 需要满足三个条件:1/ 完备性(Completeness),对于正确的解,肯定存在相应证明。2/可靠性 (Soundness) ,对于错误的解,能通过验证的概率极低。3/ 零知识。

SNARG - Succinct Non-interactive ARGuments,简洁的无须交互的证明过程。

SNARK - Succinct Non-interactive ARgumentss of Knowledge,相比 SNARG,SNARK 多了 Knowledge,也就是说,SNARK 不光能证明计算过程,还能确认证明者“拥有”计算需要的 Knowledge (只要证明者能给出证明就证明证明者拥有相应的解)。

zkSNARK - zero-knowledge SNARK,在 SNARK 的基础上,证明和验证双方除了能验证计算外,验证者对其他信息一无所知。

Statement - 对于 QSP/QAP 而言,某个计算电路的输入。Statement 对证明者和验证者都是公开的。

Witness - Witness 只有验证者知道。可以理解成,某个计算电路的输出( output )。

zk-SNARK只适合特定形式的计算问题,即所谓QAP(Quadratic Arithmetic Programs)。

拉格朗日插值

最后一步,将每个矩阵(按列)压缩为一个多项式组成的向量,例如矩阵CC(n)=[C1(n), C2(n), C3(n), C4(n), C5(n), C6(n)]。方法是:对矩阵的每一列分别运用拉格朗日插值法

矩阵C的第3列为[0,0,0,1],现在要求取一个多项式C3(n),使得n分别取1、2、3、4时,C3(n)的值为:

n C3(n)
1 0
2 0
3 0
4 1

按照拉格朗日插值法,C3(n)可以分解为4个部分之和:

  • C3_1(n) = A(n-2)(n-3)(n-4)
  • C3_2(n) = B(n-1)(n-3)(n-4)
  • C3_3(n) = C(n-1)(n-2)(n-4)
  • C3_4(n) = D(n-1)(n-2)(n-3)
  • C3(n) = C3_1(n) + C3_2(n) + C3_3(n) + C3_4(n)

已知n = 4时,C3(n) = 1。因为,n = 4时,C3_1(n)、C3_2(n)和C3_3(n)分别为0,因此,C3_4(4) = D(4-1)(4-2)(4-3) = 1,从而得到D = 1/6。同理,A = B = C = 0。于是,可知C3(n) = 1/6(n-1)(n-2)(n-3) = 0.166n*3-n2+1.833n-1。


最终可得到QAP形式的参数为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

Coefficients are in ascending order, so the first polynomial above is actually 0.833 * x**3 — 5*x**2 + 9.166*x - 5.

Checking the QAP

Now what’s the point of this crazy transformation? The answer is that instead of checking the constraints in the R1CS individually, we can now check all of the constraints at the same time by doing the dot product check on the polynomials.

求得多项式向量A(n)、B(n)和C(n)后,计算问题便转换为求取解向量s,使得等式s . C(n) - s . A(n) s . B(n) = 0 在n=1,2,3,4,5,6时成立,等价于:s . C(n) - s . A(n) s . B(n) = H(n) * Z(n),其中, Z(n) = (n-1)(n-2)(n-3)(n-4)(n-5)(n-6)。

问题算式发生变化,但解的形式未变,仍为:
s = [~one, x, ~out, sym_1, sym_2, sym_3] = [1, 3, 35, 9, 27, 30]

QAP

我们只需要代入每一个插值点坐标($x$)的值,验证 $A(x) \times B(x) - C(x) = 0$ 即可。

或者等价地写为:$A(x) \times B(x) - C(x) = H(x)Z(x)$。

其中 $Z(x)=(x - 1)(x - 2)(x - 3) \cdots$,在每个插值点上都等于0。


例如,代入多项式 $A(x), B(x), C(x)$:

1
2
3
A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]

计算 $t = A(x) \times B(x) - C(x)$:

1
t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

计算 $t/Z(x)$:

1
2
Z = [24, -50, 35, -10, 1]
h = t / Z = [-3.666, 17.055, -3.444]

发现刚好可以整除,没有余项。这便完成了验证。

如果有余项,则说明 $Z(x)$ 不包含 $A(x) \times B(x) - C(x)$ 的所有零点。那么 $s$ 便不是真正的解向量。

实际中这些运算可能是在有限域上完成的。在有限域上计算还可以避免舍入误差。

Using finite field arithmetic removes the need to worry about rounding errors and allows the system to work nicely with elliptic curves, which end up being necessary for the rest of the zk-SNARK machinery that makes the zk-SNARK protocol actually secure.

DIZK: A Distributed Zero Knowledge Proof System

零知识证明,在现在的系统中的具体实现往往会遇到性能瓶颈——生成所需求的proofs通常是非常耗费代价的,尤其是对内存空间的需求。

考虑最坏的应用场景:“单片机”。单片机的计算资源十分有限,使得零知识证明机制的应用变得困难。

本文提出了DIZKDIstributed Zero Knowledge)系统。

DIZK可以把零知识证明的生成过程变成分布式的,从而分配到多个主机上(形成集群)进行generation。

介绍

can zkSNARKs be used for circuits ofmuch larger sizes, and at what cost?

文中举例了两个DIZK的实际应用:

  • proving authenticity of edited photos
  • proving integrity of machine learning models

DIZK通过分布式的计算过程,使得对大规模数据实例的处理能力有了突破。

DIZK仍然有一些缺陷。一方面,虽然处理过程变成了分布式,但总的计算量仍然是很多实际应用所不能接受的。另一方面,DIZK存在冷启动问题,必须要一个可信任的集群来完成初始公共参数的设置(这个工作计算量同样很大),因为引入了集群,安全性自然没有单个机器运行高。

但是作者似乎对未来 zkSNARKs 的应用发展很乐观。。


DIZK的分布式解决方案:

  • 将基本的运算任务(域、群的算术)分离,并实现高效的分布式实现
    • 有限域
      • 分布式 FFT 算法
      • 分布式 Lagrange interpolant evaluation 拉格朗日多项式插值
    • 有限群
      • distributed multi-scalar multiplication with fixed bases and with variable bases
  • 将这些分布式的组件集成到一起,从而实现分布式的zkSNARKs。
    • 这样朴素的集成方法在效率上不太好

因为这样实现的zkSNARKs往往会面临稀疏矩阵的问题。$O(NM)$ 的多项式域矩阵里非零元素只有 $O(N+M)$。

zkSNARKs transform the computation of a circuit into an equivalent representation called a Quadratic Arithmetic Program

同时,这样的矩阵的大多数行列都是稀疏的,但仍然存在dense的行列。所以作者提出先有一个lightweight distributed computation标记出所有的dense行/列,然后运行一个混合的计算过程,对稀疏/密集的行列进行不同的处理。

这样,作者便实现了一个比较高效的分布式实现。

最后,作者强调这些技术可以用到其它类似构建分布式证据的系统中。他们对方法进行了包装,并分别写成了库,以便重用。

常见的密码学方案一般只是一个整体化的过程,很难适应大规模的问题集。

DIZK在这样的意义上提出了一个全新的分布式架构,使得“cryptography at scale”成为现实。这具有启发意义。

zkSNARKs

“given a public predicate F and a public input x, I know a secret input w such that F(x,w) = true”

zkSNARKs 算法中有三个主要功能:

  • setup:setup产生的结果都是公共信息,但是它的产生过程包含私密信息的使用,所以必须由一个trusted party来负责。
    • predicate $F$:运行一次
    • proving key $pk_F$:证明
    • verification key $vk_F$:验证
  • prover:任何人都可以运行
    • 获得 $pk_F$,公共输入 $x$,秘密输入 $w$(满足 $F(x,w)=\text{true}$)
    • 生成一个proof $\pi$(生成过程包含一些randomness)
      • $\pi$ 可以证实:“given a public predicate F and a public input x, I know a secret input w such that F(x,w) = true”
      • $\pi$ 不会透露任何关于 $w$ 的信息(零知识)
  • verifier:任何人都可以运行
    • 接收:$vk_F$,$x$,$\pi$
    • 输出:a decision bit (‘accept’ or ‘reject’)

具体的算法细节参考基础概念部分。

DIZK

DIZK使用Spark作为实现平台。Spark由driver和executor组成,driver分解并分配任务给executors。

Large datasets are stored as Resilient Distributed Datasets (RDDs).

以前就有过分布式设计的尝试了,但是要么就是过于简单的算法,带来不可接受的时间消耗(quadratic time);要么,就是从对内存的过量消耗中去获取性能提升,形成memory-intensive类算法。

上图展示了DIZK设计框架中的主要内容。

Distributed fast polynomial arithmetic

Arithmetic from evaluation and interpolation

polynomial evaluation 多项式求值

给定一个 $n$ 阶多项式 $P(X)$ 和给定的一组 $(X_1,X_2,…,X_n)$ 的值,计算所有的 $P(X_1),P(X_2),…,P(X_n)$。

最朴素的方法:一个点一个点的计算,$\Theta(n^2)$。

polynomial interpolation 多项式插值

给定一组坐标 $(u_1,v_1),(u_2,v_2),…,(u_n,v_n)$,插值一个 $n$ 阶多项式 $P(X)$。

插值出所有的拉格朗日分项:$L_1(X),…,L_n(X)$。消耗 $\Theta(n^2\log n)$。

得到插值多项式 $\sum_{j=1}^n v_jL_j(X)$,再次消耗 $\Theta(n^2)$。

分布式FFT

Cooley–Tukey algorithm将上述两个问题(多项式求值)的解决时间都缩短到 $\Theta(n\log n)$。

但是Cooley–Tukey algorithm不适用于部署到计算机集群上。这是因为其中涉及到的蝴蝶操作,将使得集群中内存交换密集化,影响部署效率。

Sze提出了另一个方法,通过MapReduce,Sze的方法只需要进行唯一的一次shuffle,

将一个规模为 $n$ FFT问题分解为两个规模为 $\sqrt n$ 的FFT计算。首先用mapper计算第一部分,然后shuffle,再用reducer计算第二部分。

本文中采用了这样的方法,只不过将之部署到了有限域上。

分布式Lag插值

先计算总的拉格朗日乘积,每个拉格朗日插值多项式就可以写为:

分布式multi-scalar multiplication

分为fixMSM和varMSM两类计算。

Distributing the zkSNARK setup

Distributing the zkSNARK prover

应用

Authenticity of edited photos

blalbla

Integrity of machine learning models

blabla

总结与展望

本文提出并实现了DIZK,一个分布式的zkSNARK系统。

当同期的系统支持千万级的门电路时,DIZK通过集群计算支持了10亿量级的算术门电路。

我觉得这个工作量是很充足的。对分布式的应用、对密码学和数学知识的应用,都很有水平。虽然还没有完全读懂此论文,但已经感受到作者花费的心血。

零知识证明的效率仍然是一个大问题,分布式的设计只是延缓了这个问题的暴露。但核心不变。

以后也许可以从更好的分布式设计,或者更好的零知识算法的方向上做文章。

Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts

在分布式数字货币上实现的智能合约,支持不信任的双方无须经过第三方就可以实现安全的交易行为。当发生合约废止等情况时,分布式的区块链系统能够保证参与交易的老实人获得相称的补偿。

但是,这其中没有交易隐私的保护机制。任何流量大小的交易都将完全暴露在区块链维护社群的监控下。

Hawk,本文中将要介绍的智能合约分布式系统,不会在区块链存储任何交易信息。从而保护用户的交易隐私。一个使用Hawk的程序员无须自己去实现智能合约的隐私性,Hawk将会自动采用密码学的技术例如零知识证明等来完成整个智能合约的私密保证。

为了验证Hawk的安全性,本文提供了一个形式化的基于密码学设计的区块链系统模型

介绍

时序关系是区块链的基石,在区块链中你可以嵌入一个不可伪造的时钟——只需要每次挖矿时,时钟便增加计时即可。这样,当一个组织想要在某个合约执行后反悔,区块链系统就可以追源溯头,使得一切无所遁形,使参与的honest paries获得相应的等额补偿。

但是,现在的智能合约做不到隐私性,一旦在区块链上部署以后,每一次调用智能合约,所有的action都会在整个网络上泛洪式地传播,从而被公众所知。尽管区块链上绑定的地址本身不会提供个人信息,但是去匿名化攻击(deanonymization attacks)通过分析整个区块链上的交易图,却有更高的概率把个人的现实身份暴露出来。

Zcash这一类隐去了交易信息的应用,却也同时丢失了programmability,因而无法有效地创建和应用智能合约。

那么 Hawk,能做什么?创建有隐私保护功能的智能合约。并且,创建者不需要掌握深厚的密码学技术,一切只须交给Hawk自动完成。

Hawk 的安全性体现在两个方面:

  • On-chain privacy
    • 交易细节对公众来说是保密的
    • Hawk:货币的流向和金额是基于加密技术隐藏的,并利用零知识证明来保证合约执行的正确性
  • Contractual security
    • 除了对公众进行保密以外,交易双方的参与者也可能需要一些安全保障

Minimally trusted manager

Minimally trusted manager: The execution of Hawk contracts are facilitated by a special party called the manager. 但是,这个manager只能获取少量的信任,他并不会被Hawk系统认定为一个trusted third party。这样,当manager做出一些偏离他原本路线的不好事的时候,当manager和某些parties联合起来创造莫须有的优势的时候,manager也将面临系统的惩罚。除此之外,manager的能力也是十分受限,它根本不能够影响到智能合约(contract)的正确执行。

Sealed Second-price Auction 秘密二价拍卖

Vickrey拍卖(the second-price sealed-bid Auction)是一种拍卖方式,也叫次高叫价拍卖,是第K高叫价拍卖中的一种,当K=2时即为此种方式。(Here)这种拍卖方式最早是Google和雅虎在产品广告事务中逐渐形成的。最后演变形成的 second-price auction 成了程序化竞拍的一种标准方案。

使用Vickrey拍卖法,可以使得买方出价时失去聚焦,从而可能以略高于心理价格的方式出价。

Sealed Auction(秘密拍卖): 出价者互相不知道对方的出价。

Second-price Auction: 最高出价者,只支付“次高出价+1 cent”的价格。如果有多个相同最高出价,则按照自定义机制选择赢家,并支付最高出价。


Hawk将会把这样一个拍卖智能合约加密,只要bidders和manager不故意地自愿泄露信息和交易内容,交易的隐私将得到保护。

以下是second-price auction的智能合约代码:

注意代码的第二十行,

1
out.party[winner].$val = bestprice-secondprice;

这里实现了sencond-price,因为最高价者的refund是bestprice-secondprice,也就是实际收取了secondprice


对于整个contract的安全性要求如下:

  • Input independent privacy
    • 用户之间的竞拍相互独立,且过程保密
  • Posterior privacy
    • 只有manager不泄露信息,用户的竞拍数据就是安全的,连auction本身也不能探知
  • Financial fairness
    • 当出现异常或者dishonesty时,系统可以保护受害者的权益
    • Hawk offers built-in mechanisms for enforcing refunds of private bids after certain timeouts.
  • Security against a dishonest manager
    • 当manager有欺诈行为甚至和某些parties暗谋的时候,拍卖中的货币流不受影响

An auction with the above security and privacy requirements cannot be trivially implemented atop existing cryptocurrency systems such as Ethereum [57] or Zerocash [11]. The former allows for programmability but does not guarantee transactional privacy, while the latter guarantees transactional privacy but at the price of even reduced programmability than Bitcoin.

从以上我们得知,无论是以太坊还是Zcash都不能完美地实现programmability和privacy的良好共存。

Hawk是第一个实现这样的共存机制的去中心化加密数字货币系统。

Background 研究背景

Bitcoin: 有限的programmability,既不是图灵完备(turing-complete),也没有用户友好度(user friendly)。

Ethereum: 以太坊是第一个具备图灵完备性的去中心化智能合约系统。大部分来自社区的智能合约都是在这个平台上完成设计的。

Security of the blockchain: 以往的研究主要是对智能合约与密码学相结合的上层设计,对区块链底层技术的安全、隐私设计则还待加强。

Minimizing on-chain costs: 如果可以把智能合约内的多数操作或者计算变成offline的,那么上链的成本(用户需要支付的transaction fee)就会少很多。因为矿工是按照智能合约的execution steps计费的。


与比特币不同,Hawk框架设计中假设了一个图灵完备的区块链模型。在这样的区块链上可以运行任意的图灵完备的程序。


Programs, wrappers, and functionalities: Program在论文中表示描述算法的伪代码,wrapper则是一个作用在program上的编译器,把program “compile”成相应的UC-style functionality or protocol。(UC: Universal Composability)

下图是两个伪代码示例(describes the requirements of a private ledger):

密码学技术

在一个pour操作中,spender将他要花的钱先转给数个匿名地址,然后通过匿名地址完成交易。

这些匿名地址是一次性使用的,所以不惧泄露。

这些匿名地址和spender账号的密钥存在绑定,其他人无法操作。

spender需要在zkp中证明:

  • coins真的被花掉了
  • 没有双花
  • 货币守恒(input coins = output coins)

应用SNARKs

在应用SNARKs的过程中,Hawk采用了一些提高SNARKs算法效率的方法:

  • 采用SNARK-friendly的密码学技术
  • 自设计算术电路生成器,来优化SNARK电路的底层,产生更SNARK-friendly的电路

效果:using SNARKfriendly implementations can lead to 2.0-3.7× savings in the size of the circuits at the 80-bit security level.

The main cryptographic building blocks in our system are: collision-resistant hash function for the Merkle trees, pseudo-random function, commitment, and encryption.

Optimizations for finalize.(唯一$O(n)$ circuits的一步)

  • Optimization 1: Minimize SSE-secure NIZKs.
  • Optimization 2: Minimize public-key encryption in SNARKs.

未来SNARKs电路优化技术还有待进一步,整个社区里有很多人在朝这个方向努力。

其他应用

除了sealed-auction之外,在Hawk的实验中还应用了很多其他的例子。

Crowdfunding 众筹

在众筹机制里面,设计中允许在大规模的群体上集体贡献资金来达成某种social good。

如果预定的minimum donation tartget达到了,donations就会传递给指定的party。否则,一旦没有达到预定的target,则发起refund,所有的众筹货币原路返回。

众筹协议中的隐私保护:

  • 具体的donation数额在deadline前是保密的
  • 如果contract失败了,那么只会有manager了解到具体的insufficient donation amount。

Rock Paper Scissors 石头剪刀布

一个two-player的游戏,大家都知道怎么玩。可以容易地扩展到N-player version。

如果某一方发生了cheat、abort之类的行为,则继续参与的honest party将会获得最大期望补偿。

“Swap” Financial Instrument

一个持有高风险资产的人可能会通过购买保险的方式,来控制风险。

generic bolockchain 模型优势

设计了一个图灵完备的底层区块链模型可以让整个program在efficiency(复杂度层面)上提升。

总结与展望

简单总结一下这篇文章。我觉得Hawk的形式化工作做的还是挺多的,但是挺难读懂的。

Appendix里面有FAQ是我没有想到的。比如下图所示的motivation。

感觉并没有看太懂,如果想看懂要花费的精力可能会成倍增加。所以从我的角度而言,这篇论文写的不太好。

这篇文章的工作可以分为两个主要部分,一个是底层通用区块链模型,一个是Hawk的设计。两者相对独立,但是相互促进。

可以做的进步空间也有,包括在Hawk上的应用,对Hawk的算术电路编译器的改进,等等这些事情都是可以做的。从展望的角度来说,未来的区块链包括智能合约在内的机制设计应该是面向更多更复杂的垂直场景,所以像这样的适应性的创新应该还会层出不穷。

Bulletproofs: Short Proofs for Confidential Transactions and More

Bulletproofs (short like a bullet with bulletproof security assumptions), a new non-interactive zeroknowledge proof protocol with very short proofs and without a trusted setup. Proof size 仅仅是witness size 的 $O(\log n)$ 级别。但是proof和verification的生成过程仍然是 $O(n)$ 的。

介绍

multi-party computation (MPC) protocol,这个名词经常出现。实际上就是一个多方参与的计算过程。Bulletproof使得这样的一个过程可以让多方共同生成一个single proof的同时,保持多方之间的隐私。实现的算法过程可以达到$O(1)+O(n)$或者双份$O(\log n)$的number of rounds和communication time。

One version of our MPC protocol is constant-round but with linear communication. Another variant requires only logarithmic communication, but uses a logarithmic number of rounds.

这个MPC协议可以把所有parties的proofs聚合成一个单独的short proof’。

下图是一个例子,展示了聚合技术所带来的空间节省:

本文中将一个payments的privacy被分为两个部分:

  • anonymity
    • 隐藏交易中的双方ID(identities)
  • confidentiality(机密性)
    • 隐藏交易的具体金额
    • 保证了这一条的叫做:confidential transactions (CT)

在privacy的实现方面,Bitcoin作为一个案例,提供了弱化版的数字地址到真实世界实体的隔断,但是它没有实现confidentiality的任何隐私化。这种严重的缺陷劝退了一些潜在的使用场景下的用户。

比如企业的薪资发放就不太可能通过比特币的方式来发放, 因为大部分企业都不希望自己发放的工资的具体数额被公之于众。(在现实中甚至会签署各种薪酬保密合约来禁止打工人之间的信息交流……)

目前实现了CT的技术,要么就是计算量过大;要么就需要一个trusted setup(可信启动),比如SNARKs算法,每个人都需要假设setup是正确执行的。

这篇文章实现了:Short non-interactive zero-knowledge proofs without a trusted setup。标红处应该算是本文中提及的算法最大的改进。

其次,short proof对于实际应用的成本来说,也是一个明显的改进。

Bulletproofs do not require a trusted setup. They rely only on the discrete logarithm assumption, and are made non-interactive using the Fiat-Shamir heuristic.

Mimblewimble

在介绍Mimblewimble之前,需要先了解一下什么叫scriptSig。

首先,对于交易来说,一般只限定了输入的金额大于输出的金额。也就是说,交易可能产生结余金额。这些结余金额(unspent transaction outputs)被称之为UTXO。

如果想要花掉这些UTXO,则需要提供一个与transaction script相关的数字签名,即scriptSig。

这一通操作看上去就很麻烦是不是。

Mimblewimble改进了这一点,并提出:for a valid confidential transaction the difference between outputs, inputs, and transaction fees must be 0.

这是一个对交易金额流的更强的限制,输出流必须完全等于输入流,也就不会再产生UTXO,也就用不到所谓的scriptSig。从而极大地简化了confidential transaction的结构

Poelstra进一步指出,这样的新约束还可以对区块链的交易信息需求构成剪枝(prune),用户不再需要下载所有的历史交易来确认整个区块链中的UTXO,他们现在可以很容易验证整个区块链。

Mimblewimble还支持交易在上链以前先进行聚合,从而节省空间。这对于MPC应用场景来说无疑是个好消息,因为我们之前已经说到本文中实现了MPC的聚合。

A Mimblewimble blockchain grows with the size of the UTXO set. Using Bulletproofs, it would only grow with the number of transactions that have unspent outputs, which is much smaller than the size of the UTXO set.

NIZK Proofs for Smart Contracts

Non-interactive zero-knowledge (NIZK) proofs. 非交互式零知识证明。

NIZK在智能合约上的计算消耗很大,因此SNARKs应运而生,提高了计算效率。但是SNARKs算法也存在一个问题:必须要有一个非常复杂的 trusted setup。对应产生的common reference strings (CRS)公共参考串很长,而且对每一个应用都要单独处理。这显然不适用于MPC的多用户场景。

Bulletproofs improves on this by enabling small proofs that do not require a trusted setup.

一些定义

Range Proofs

Range proof是一种断言某个加密的值落在一个特定的区间(interval)以内的证明。除此之外,range proof不会泄露暴露具体值在内的其他任何信息。

Commitments

Commitments:一个非交互的commitment scheme包括一对算法(Setup,Com)。Setup负责生成公共参数$pp$,Com则负责产生随机种子$r$,并利用$pp$、message $x$和$r$计算出commitments $\text{com}$

Range Proof Protocol with Logarithmic Size

We now present a novel protocol for conducting short and aggregatable range proofs.

我们要设计一个证明(Range proof):

  • The proof convinces the verifier that a commitment V contains a number v that is in a certain range, without revealing v.

然后是一堆数学证明。。

Logarithmic Range Proof

使用文中提到的improved inner product技术,可以使得range proof中传递的communication elements从$O(n)$个降到$O(\log_2 n)$。

Aggregating Logarithmic Proofs

在很多场景下,一个单独的prover需要同时提供多个range proof。

比如说,一个confidential transaction经常会有多个output,但在实际中大多数交易会执行一个叫做“change output”的操作,把没有花掉的funds退还给sender。那么,就会出现对多个账号的发送,每一个账号都需要一个range proof……

假设总共的$m$个参与方,那么aggregated range proof就可以将总range proof的消耗降到$2\log (n\times m)$,也就是对于额外的$2\log m$的消耗。

具体的证明过程就不看了,,

Zero-Knowledge Proof for Arithmetic Circuits

大概就是一通操作把电路元素的用量从 $6\log_2(n)+13$ 优化到了 $2\log_2(n)+13$。。。

总结与展望

本文的主要贡献:

  • Distributed Bulletproofs generation.
    • 支持高效的MPC协议,$O(\log n )$
    • 应该是本文中理论研究最多的篇幅,在复杂度上确实做到了质的提高
  • Proofs for arithmetic circuits.
    • The proof size is logarithmic in the number of multiplication gates in the arithmetic circuit for verifying a witness.
    • 把电路元素的用量从 $6\log_2(n)+13$ 优化到了 $2\log_2(n)+13$
    • 一个不大不小的改进
  • Optimizations and evaluation.
    • 一些优化工作和测试工作。。

至于有什么展望。。我倒是没有什么感觉。也许可以对于理论的优化上界做一些更严谨的研究,比如,到底能够优化到什么程度?

BITE: Bitcoin Lightweight Client Privacy using Trusted Execution

This paper is included in the Proceedings of the 28th USENIX Security Symposium.

现在移动互联网飞速发展,人们的大多数时间花费产生了转移,于是,原本只在PC或者服务器上运行的区块链系统,也把触角伸向了移动设备……

传统的区块链需要用户节点保存完整的区块链信息,这对于资源受限的设备来说是不可接受的(比如手机)。目前主流的解决方案是使用轻量化的客户端代理,同时将大多数的计算、存储任务卸载到相应的区块链节点上,但是这样的方法容易泄露客户的交易信息,从而使得用户隐私无法得到保证——隐私恰恰是很多去中心化金融系统的核心目标之一。

本文提出了一种保护轻量客户端(lightweight clients)的隐私的全新方法,BITE (for BItcoin lightweight client privacy using Trusted Execution)。

  • Privacy
    • 轻量客户端在交易过程中不会泄露它们的链上地址
  • Completeness
    • 任何有效的交易都会被执行
  • Performance
    • BITE的性能不低于现存的light client schemes

Our main idea is to leverage the trusted execution capabilities of commonly available SGX enclaves.

概念

Decentralized Time-stamping Mechanism

Decentralized Trusted Timestamping using the Crypto Currency Bitcoin

Trusted timestamping is a process for proving that certain information existed at a given point in time.

一个去中心化的时间标签,使得所有的区块链上信息有一个真实的时间序号,从而使得一些攻击手段失效,并且区块链在聚合大量节点上更多的信息、交易的时候可以有条不紊。

比如,如果有人在挖块后故意等候一段时间再上链,希望冒充新块,在时间标签的约束下,这样的行为就做不到了。因为时间标签记录了某个区块的产生时间,与具体的发布、上链时间无关。

SGX enclave

SGX技术的分析和研究

旨在以硬件安全为强制性保障, 不依赖于固件和软件的安全状态, 提供用户空间的可信执行环境, 通过一组新的指令集扩展与访问控制机制, 实现不同程序间的隔离运行, 保障用户关键代码和数据的机密性与完整性不受恶意软件的破坏。

SGX (Software Guard Extensions)指令集扩展,用于增强软件的安全性。SGX是一种Trusted Execution Environments (TEEs)。除了提供安全性以外,TEEs通常也能提供更好的性能,因为简化的processing和bandwidth等结构。

SGX允许应用程序实现一个被称为enclave的容器, 在应用程序的地址空间中划分出一块被保护的区域, 为容器内的代码和数据提供机密性和完整性的保护, 免受拥有特殊权限的恶意软件的破坏。

在SGX中,enclave使用的内存空间最大只有128MB

Bitcoin Lightweight Clients

Bitcoin是当之无愧的世界上最热门的数字货币市场。参与者通过自己的address提交transaction的方式完成各种交易支付活动。

When a user wants to perform a payment, she creates a transaction that contains inputs, outputs, and the signatures
that allow her to spend the inputs.

为了解决移动终端的部署和验证问题,最初的解决方案被称为 Simplified Payment Verification (SPV)。在这种技术下,轻量客户端只需保存block headers而不是整个区块链。

介绍

现在,一个典型的Bitcoin完整安装,可能需要多达200GB的空间。

Therefore, users operating resource-constrained clients like mobile devices cannot afford to run their own full node.

所以大部分数字货币平台推出了lightweight clients。

不中用的filter

实际有一些对于user privacy的改进措施,比如:Bitcoin’s BIP37 [31] and Ethereum’s LES [6]。这样的技术被称为filters

The goal of filters is to allow the client to define an anonymity set in an attempt to hide its real addresses from the full node.

简单来说,filter就是一种地址混淆技术,让代理节点无法知晓真实的用户地址。

这样的技术会发送很多false positives(主动错误信息),真正的交易隐藏大量的伪造交易里面,让代理节点很难分辨哪个才是真的。这样便达到了混淆的目的。

不过这样做,自然有一种“杀敌一千,自损八百”的感觉。为了更好的混淆和隐私性,客户端不得不制造大量的假交易,这样通讯成本就会很高。

并且,最近的一些研究表明,filter在实际中几乎提供不了什么有效的隐私保护……


所以,目前的轻量客户端是没有什么实际有效的隐私保护技术的。

新的Solution

作者的目标在于提升BItcoin的轻量客户端的隐私性,同时不必付出在代理节点或者通信上性能下降的代价。

BITE (for BItcoin lightweight client privacy using Trusted Execution), a solution in which a potentially untrusted entity runs a full node with an SGX enclave that serves transaction confirmation requests from clients.

简单地利用SGX技术并不能完全解决隐私性的问题,因为SGX本身也只能维护enclave之内的安全性,对external memory就束手无策;并且,SGX对side channel attack来说比较脆弱。所以,恶意的full node是可能从SGX中拿到client的地址的。

于是,本文中应用了 private information retrieval (PIR) 和 side-channel protection techniques 两大技术。试图解决SGX技术中的缺陷。


作者实现了两个variant(版本)的solution。

  • Scanning Window
    • similar to the current SPV clients that verify transactions using block headers and Merkle paths received from the full node.
  • Oblivious Database
    • allows the client to verify the amount of coins associated with its addresses by querying a specially-crafted version of the unspent transaction output (UTXO) database.
    • 这个版本可以实现比上一个版本更加轻量的客户端。因为不需要下载和验证Merkle paths。

作者所实现的BITE可以稍作修改便部署的实际存在的应用当中。尽管BITE是为比特币设计的,但它的思想也可以直接应用到很多其他的区块链平台上。

以下是它们实际性能的一个比较:

Contributions

如文中所示。

Approach

上图是BITE系统的设计框架。轻量客户端通过一个优化过后的SGX enclave环境,进行具有隐私保护性的交易。

以下是作者分别实现的BITE的两个实际框架。

Scanning Window

简单解释一下上图。

  • 初始化:
    • 方框a代表着节点$FN_j$从比特币网络中下载整个区块链
    • 方框b代表着轻量客户端下载最新的block headers
  • 1)attestation:SGX安全确认
  • 2)TLS:建立安全信道
  • 3)request:客户端发送一个想要搜索的地址和一个区块号(表示最深的搜索区块,搜索到这个区块时就停止搜索)
  • 4)scanning:节点利用一个scanning算法在enclave内搜索相应的地址和区块
  • 5)response:节点传递搜索结果
  • 6)verify:客户端验证相关结果(block headers, Merkle Tree paths……),更新内部状态,并结束和enclave的连接信道

Oblivious Database

简单解释一下上图。

主要是方框b的初始化和第4步的搜索机制不同。

  • 初始化:
    • 方框a代表着节点$FN_j$从比特币网络中下载整个区块链
    • 方框b代表着Enclave检查本地的区块链,并建立一个UTXO Database
    • 方框c代表着轻量客户端下载最新的block headers
  • 1)attestation:SGX安全确认
  • 2)TLS:建立安全信道
  • 3)request:客户端发送一个想要搜索的地址和一个区块号(表示最深的搜索区块,搜索到这个区块时就停止搜索)
  • 4)search:节点在UTXO Database中搜索客户端所请求的unspent transaction output information
  • 5)response:节点传递搜索结果
  • 6)verify:客户端验证相关结果(block headers, Merkle Tree paths……),更新内部状态,并结束和enclave的连接信道

更多细节之处就不再细读了。

总结与展望

保护用户隐私是去中心化的数字货币系统所需要考虑的重要目标之一。然而,对于交易的验证通常需要下载和处理整条链上所有的信息——这个工作量对于手机客户端上的计算资源来说是不可操作的。

所以主流的区块链都支持一个简化的验证模式,让轻量化客户点在一些全功能节点的帮助下完成交易的验证。

然而这样的payment verication无法保证用户隐私不被泄露,从而重创了像Bitcoin这样的系统的安全性。

这篇文章提出的解决方案提升了轻量客户端在执行验证时的隐私性和安全性。作者的结果显示,解决方案提供了强有力的隐私保护以及附加的对于当前的轻量客户端的执行性能提升效应。

作者相信,在Bitcoin中,BITE是第一个保证了轻量客户端(如,移动设备)隐私性的实际解决方案

对于未来的可能工作,可以尝试从性能的角度做文章,比如如何把BITE的实现更加高效化。也可以从应用的角度出发,把BITE应用到更多的区块链系统上,而不仅仅只是一个Bitcoin的解决方案。

BUG记录

Typora图片缩放后的自动生成的HTML标签,不能被hexo的图片渲染器识别,因此会出现相对引用失常。目前没有什么好的解决方案,只能先将所有涉及的图片逐一改回原始的markdown源码。