论文阅读-Hawk.The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts

Schenk

Paper Reading

更新于：2022年7月20日

字数：5.1k字

时长：18分钟

次浏览

1.引入

区块链上的可信时钟的存在对于协议中实现公平交易至关重要：恶意用户可能会过早地中止协议以避免资金支付，但是有了可信时钟，过早地中止协议会被判定为超时，这样区块链就可以将恶意用户的抵押存款重新分配给诚实用户，以此来惩罚恶意用户。

尽管区块链和智能合约具有表现力和强大功能，但这些技术目前缺乏交易隐私：尽管各方可以创建匿名公钥以增加其匿名性，但每个匿名公钥的所有交易和余额都是公开可见的。缺乏隐私是去中心化智能合约广泛应用的主要障碍，因为一些金融交易，如保险合同或股票交易，被许多个人和组织视为高度机密。

Hawk概览

Hawk编译器负责将程序编译成区块链和用户之间的加密协议，一个Hawk程序包括两个部分：

• 隐私部分 $\phi_{priv}$ ： 用于接收各方的输入数据和货币等，并执行计算来分配收益。$\phi_{priv}$用于保护参与者的数据和资金交换；
• 公开部分 $\phi_{pub}$ ：不涉及隐私数据和资金的部分。

Hawk编译器把Hawk程序编译成以下几个部分，这些部分共同定义了用户、管理员和区块链之间的加密协议：

• 被所有共识节点执行的区块链程序
• 由用户执行的程序
• 由管理员（一个特别协助方）执行的程序

安全保证

1. 链上隐私：只有合约双方自愿公开信息，区块链才会将交易隐私向公众公布，$\phi_{priv}$以加密形式展现在公众眼前。非正式地讲，链上隐私的实现通过向区块链发送“加密”信息，并依靠零知识证明来确保合同执行和资金保存的正确性。
2. 合约安全：保护同一合约协议中的各方互不侵犯，不仅包括机密性和真实性等密码学概念，还包括存在欺骗和中止行为时的公平交易

最低限度信任管理员

Hawk合约的执行由管理员推动，管理员可以看到用户的输入，并被信任不会泄露用户的隐私数据。

• 管理员不是可信第三方：即使管理员可以任意偏离协议或与当事人串通，管理员也不能影响合约的正确执行，如果管理员中止了协议，就会受到经济上的惩罚，而用户则会得到相应的补偿；
• 管理人员不需要被信任来维护基础货币的安全性或隐私，如防止双花攻击等；
• 如果多个合约实例同时运行，则每个合约可以指定不同的管理员，而恶意管理员只会影响该实例；
• 可以用可信计算硬件实例化管理员，或使用用户自己之间的多方计算代替。

实例：密封拍卖

该实例用于实现一个密封的、第二价格的拍卖，其中出价最高的竞标者获胜，但支付第二高的价格，且竞标者在不知道其他人的出价的情况下提交出价。

该实例中$\phi_{priv}$决定中标者和支付金额；$\phi_{pub}$使用公共存款来防止管理员通过中止协议来损害竞标者利益。

合约的安全需求

前提：

• Hawk的安全建立在区块链本身的安全特性上：假设区块链的共识协议在对手不拥有大量计算能力的情况下是安全的；
• 在Hawk中，为了减少链上执行代码产生的费用，设计的协议在链下执行大部分计算

安全需求：

• 独立隐私输入：各用户在提交自己的投注资金之前无法查看其他用户的投注金额，即使与恶意管理员串通也无法查看；
• 交易后隐私保护：只要管理员不公布信息，即使在拍卖之后各用户的出价也不会公布；
• 公平交易：拍卖参与者可能试图提早退出协议，以避免付款或影响资金再分配。如果一方中止或拍卖管理员中止，中止方将受到经济惩罚，而其余方则获得补偿。Hawk在特定超时后强制执行退款；
• 防范不诚实管理员：除了中止协议外，不诚实的管理员不能影响拍卖结果和资金再分配。对于中止协议的管理员，对其进行罚款。

中止和超时

该实例定义了三种超时 $T_1<T_2<T_3$：

• $T_1$：Hawk合约在$T_1$之后停止招标；
• $T_2$：所有用户都需要在$T_2$内向管理员公布自己的出价，否则将视作0；
• $T_3$：如果管理员中止协议，用户可以在$T_3$后收回投标资金。

$\phi_{pub}$实现额外的激励机制，本实例中如果管理员提前中止拍卖，将重新分配管理员的公共存款。

本文贡献

Hawk是第一个在去中心化加密货币系统中同时提供隐私交易和可编程性的系统：

• 去中心化智能合约的正式模型：针对密码学的区块链模型，提出了一种形式化的通用可组合性(UC)模型，这种形式模型是独立的，并且在区块链模型中定义协议的安全性时通常是有用的；
• 新的加密套件：实现了一个新的加密套件，它将私有事务与可编程逻辑绑定在一起，包含三个基本原语 freeze，compute 和 finalize ：
  • freeze原语允许各方提交正常数据以及货币，提交的货币在合约中冻结，支付分配在之后由$\phi_{priv}$确定；
  • compute的过程中，各方将提交的数据和货币向管理员公开，以便管理员计算$\phi_{priv}$函数，根据$\phi_{priv}$的结果，管理员构造新的私有货币支付给各用户。然后，管理员向区块链提交新的私有货币以及它们的零知识证明。此时之前冻结的货币在用户中重新分配。
• 实现和评估：创建Hawk原型，实现一些应用来评估性能。提出协议优化，得到10倍性能。在约有100个参与方时，管理员使用四核进行密码计算（协议中最昂贵的部分），时间在2.85分钟内；所有的链上计算（由矿工执行）都十分便宜，都在20毫秒以内。

2.密码学的区块链模型

区块链模型

区块链在正确性和可用性方面受到信任，但在隐私方面不受信任。区块链不仅维护一个存储每个假名账户余额的全局账本，而且还执行用户定义的程序。论文给出了区块链的通用模型，可以运行任意图灵完备程序：

• 区块链的时钟是离散的，每一轮用 round 或 epoch 表示
• 所有链上用户都可以观察到区块链的状态，包括公共账本和任何用户定义的程序
• 发送到区块链的消息将在下一轮开始时到达。在同一轮中，敌手可以任意重新排序发送到区块链的消息，但不能丢弃消息，然而敌手可以在链下丢弃各方之间传递的消息。这意味着敌手可能会尝试抢先攻击（例如当观察到一个诚实用户正在交易一只股票时，对手会通过发送交易同一只股票的竞争交易来抢占先机）
• 用户在区块链上可以创建任意多的假名账户
• 假设区块链将正确执行任何规定好的计算

区块链正式建模

论文提供了正式的、精确的功能规范和安全性规范，并且设计的协议在通用可组合性(UC)框架下正式证明是安全的。

建模的程序分为理想程序（记为$IdealP$）、区块链程序（记为$B$）和用户/管理员程序（记为$UserP$）。同时论文定义包装器来将伪代码程序转换为UC框架下的程序：

• 理想包装器$F(·)$将理想程序$IdealP$转换为理想函数$F(IdealP)$
• 区块链包装器$G(·)$将区块链程序$B$转换为区块链函数$G(B)$，可以延迟区块链上的消息在下一轮开始到达
• 协议包装器$\Pi(·)$将用户/管理员程序$UserP$转换为用户端或管理员端的协议$\Pi(UserP)$

包装器还实现了智能合约应用的一些共同特征，包括时间、公共账本、假名和敌手对消息重新排序，这样就不需要为每个区块链应用重复这些符号。

正式UC建模及证明

附录B

编程约定

• Timer激活点：理想函数包装器$F(·)$和区块链包装器$G(·)$实现了逐轮递增的时钟，并且每次时钟增加，包装器就会调用Timer激活点。因此理想程序和区块链程序可以定义Timer激活点来实现超时操作；
• 理想程序中的延迟处理：在灰色背景中编写的程序指令表示的是不会立即进行的计算，而是推迟到下一轮开始时执行。这是一种简写，因为在实际协议中，区块链函数完成的任何计算都将被延迟；
• 假名：在理想程序、区块链程序和用户端程序中出现的所有表示用户的标识符默认情况下都指假名；
• 账本和转账：$符号仅用于可读性（用于区分与货币相关的变量和其他变量），并没有特殊含义。

3.密码学抽象

论文使用理想程序的形式来描述密码学抽象。Hawk实现了以下规范：

• 私人账本和转账：定义理想程序$IdealP_{cash}$来描述私人账本的需求；
• Hawk-specific原语：定义 freeze、compute 和 finalize 三种Hawk-specific原语来同时满足交易隐私性和可编程性。

隐私资金规范$IdealP_{cash}$

Mint

mint 操作允许用户 $P$ 将资金从他的公共总账 $ledger[P]$ 转移到私有货币池 $Coins[P]$ ，每次转账后用户 $P$ 的私有货币被创建，并与一个值 $val$ 关联。

为保证安全性，$IdealP_{cash}$ 在用户 $P$ 创建私有货币之前检查他的公共总账 $ledger[P]$ 中的余额是否足够。

Pour

pour 操作允许用户 $P$ 私下在其私人货币池花钱。简单起见，采用两种输入货币和两种输出货币来模拟货币交换。

为保证安全性，$IdealP_{cash}$ 会检查：

• 对于两种输入货币，用户 $P$ 确实拥有其声明的量那么多的私有货币
• 两种输入货币的总价值和两种输出货币的总价值相等

隐私

当诚实用户 $P$ 执行 mint 操作时，敌手 $A$ 能获得 $(P, val)$。对于公共货币池的任何操作都会被敌手 $A$ 获得。

当诚实用户 $P$ 执行 pour 操作时，敌手 $A$ 只能获得动态生成的输出假名 $P_1$ 和 $P_2$ ，而不知道哪种在私人池的货币被花了，也不知道花钱的人是谁。如果恶意用户是 pour 操作的接收方，那他会额外获得货币的金额。

额外的微妙之处

• 诚实用户会跟踪一个装有不同货币的钱包，每当诚实用户执行 pour 操作时，首先会检查本地钱包中是否有相同的货币，如果有，会立即将货币从钱包中取出，通过这种方式，如果诚实用户在一轮中进行了多次 pour 操作，将为每次 pour 操作选择不同的货币；
• 诚实用户在下一轮之前是不能花掉同一轮中自己获得的货币的，但是恶意用户可以（因为任何消息都立即被敌手获得，敌手也可以为区块链在同一轮中收到的所有消息选择排序方式）
• 诚实用户总会 pour 给存在的假名，但敌手可以 pour 给不存在的假名 $\bot$ ，这种情况下私人货币实际上进入了一个黑洞，并且无法取回。

Hawk规范$IdealP_{Hawk}$

Freeze

用户 $P$ 从私有货币池 $Coins$ 中移除一种货币，并将其添加到 $FrozenCoins$ 中进行冻结，用户的私有输入 $in$ 也会记录在 $FrozenCoins$ 中。$IdealP_{Hawk}$ 检查 $P$ 之前没有调用过 freeze，并且货币 $(P, val)$ 存在在 $Coins$ 中。

Compute

用户 $P$ 调用 compute​ 时，其私有输入 $in$ 和冻结的货币 $val$ 将公开给管理员 $P_M$

Finalize

管理员 $P_M$ 提交一个公共输入 $in_M$ 到 $IdealP_{Hawk}$ ，$IdealP_{Hawk}$ 根据所有用户的输入和冻结的货币价值计算 $\phi_{priv}$ 的结果，并根据这个结果重新分配 $FrozenCoins$ 。为了保证安全，$IdealP_{Hawk}$ 检查冻结货币的总价值等于输出货币的总价值。

与公共合约交互

$IdealP_{Hawk}$ 的功能由公共Hawk合约 $\phi_{pub}$ 参数化，在 finalize 过程中，$IdealP_{Hawk}$ 调用 $\phi_{pub}.check$ 。$\phi_{pub}$ 的作用如下：

• 检查管理员的输入 $in_M$ 的格式是否正确
• 重新分配公共存款：如果用户或管理员提前中止协议，或者用户提供了无效的资金投入（例如少于最低赌注），$\phi_{pub}$ 可以重新分配用户的公开存款

安全和隐私需求

• 当诚实用户 $P$ freeze 冻结一笔金额时，敌手不能看到该金额，但能看到诚实用户的假名 $P$ 。这不会损害诚实用户的隐私，因为他可以随时创建新的假名；
• 当诚实用户调用 compute 时，只有管理员 $P_M$ 能看到用户的输入 和冻结的金额，其他用户不能看到；
• 在 finalize 操作期间，输出 $out$ 会公开该所有用户，如果不希望公开，$out$ 可以为空。

时间和中止

freeze 操作在 $T_1$ 内完成，$compute$ 操作在 $T_2$ 内完成，如果用户冻结了货币但是在 $T_2$ 内没有公布，则这些冻结的货币会丢失，即 $(in_i, val_i):=(0, \bot)$

简化的假设

• 论文实现的协议不支持管理员中止协议时冻结货币的退款
• 假设参与合约的假名集和超时 $T_1, T_2$ 硬编码在程序中

4.加密协议

协议分为两部分：

隐私资金转移

区块链程序 $Blockchain_{cash}$ 维护一系列私有货币 $Coins$ ，每一种货币的形式为 $(P, coin:=Comm_s($val))$ ，其中 $P$ 是用户假名，$coin$ 是根据随机数 $s$ 生成的货币值 $$val$ 的承诺。

在 pour 操作期间，用户 $P$ 选择两种 $Coins$ 中的货币来花费，分别为 $(P, coin_1)$ 和 $(P, coin_2)$ 。pour 操作将 $val^{‘}_1$ 和 $val^{’}_2$ 分别付给两个输出假名 $P_1$ 和 $P_2$ ，并且保证 $val_1+val_2=val^{'}_1+val{‘}2$ 。支付用户选择新的随机数 $s_i^{'}(i\in{1,2})$ 并计算输出货币 $(P_i,coin_i:=Comm{s^{{'}_i}($val_i}{’}))$ ，支付用户将 $s_i^{‘}$ 和 $val_i^{’}$ 发送给收款用户 $P_i$ 。发送者计算一个零知识证明来证明输出的货币是适当构造的，其中正确性涉及以下方面：

• 货币的存在性：$(P, coin_1)$ 和 $(P, coin_2)$ 确实是私有货币池 $Coins$ 的一部分，这里使用零知识证明可以确保支付用户隐藏其花费的货币种类。为了提高效率，$Blockchain_{cash}$ 维护一个 $Coins$ 的Merkle树 $MT$ 来证明货币的存在性；
• 不会双重支付：每一个货币 $(P, coin)$ 都有一个唯一的序列号 $sn$ ，在 pour 货币时，必须提供货币的 $sn$ 以及其零知识证明来证明 $sn$ 的正确性，$Blockchain_{cash}$ 确保 $sn$ 不会被用两次；
• 保护金额：零知识证明确保输入的货币和输出的货币的总价值相等。

当诚实用户向诚实用户 pour 时，敌手 $A$ 不会知道承诺方案 $Comm$ 隐藏的输出货币的值，敌手 $A$ 可以看到接收两种输出货币的用户假名；

当不诚实用户 $P^$ 向诚实用户 $P$ pour 时，尽管敌手知道 $coin$ 公开，然而一旦交易在$Blockchain_{cash}$生效，敌手就不能使用 $(P,coin)$，因为 $P^$ 不知道 $P$ 的密钥。

PRF：伪随机函数

ENC：加密

DEC：解密

同时实现隐私和可编程逻辑

Freeze

freeze 操作不直接向用户支出，而是将资金以及附带的隐私输入提交给智能合约，这是使用类似pour​的协议完成的：

• 用户 $P$ 选择一个私有货币 $(P,coin)\in Coins$，其中 $coin:=Comm_s($val)$。$P$使用自己的密钥计算 $coin$ 的序列号 $sn$ 并公开，用于防止双重支付；
• 用户 $P$ 计算承诺 $(val||in||k)$ ，其中 $in$ 是用户输入，$k$ 是一个对称加密密钥（用于实际优化）；
• 用户 $P$ 进行零知识证明，类似 pour 操作。

Compute

compute 操作在链下计算 ${val_i^{‘}}_{i\in[n]}$以及进行正确性证明。Hawk依赖管理员 $P_M$ 来进行计算，所有用户将自己的输入经过管理员的公钥加密后发送给管理员：$ct:=ENC(P_M.epk,r,($val||in||k||s^{’}))$ ，其中 $ct$ 是密文， $P_M.epk$ 是管理员的公钥。

在获取用户的公开信息后，管理员通过私有合约 $\phi_{priv}$ 计算 ${val_i^{'}}_{i\in[n]}$ 以及公开输出 $out$。管理员同时也会构建一个零知识证明来证明结果。

Finalize

管理员提交$\phi_{priv}$的结果以及零知识证明到$Blockchain_{cash}$之后，$Blockchain_{cash}$验证证明并重新分配冻结的资金，与此同时还将管理员的公开输入 $in_M$ 和公开输出 $out$ 发送给公开Hawk合约 $\phi_{pub}$。

定理1

假设Merkle树使用的哈希算法是抗碰撞的，承诺方案 $Comm$ 是 perfectly binding 和计算隐藏的，零知识证明的NIZK方案满足零知识需求，加密方案ENC和SENC是正确并且安全的，PRF方案是安全的，则协议 $UserP_{cash}$ 和 $UserP_{hawk}$ 安全地模拟了静态模型中抵抗恶意对手的理想功能$F(IdealP_{hawk})$ 。

证明在文献[37]:
A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk:
The blockchain model of cryptography and privacy-preserving smart
contracts. http://ia.cr/2015/675.

扩展和讨论

使用可信硬件实例化管理员

使用可信硬件SGX实例化管理员从而在安全秘密地进行链下计算。但是任何不与区块链交互的链下协议都不能在中止的情况下提供公平交易——即使使用了可信硬件。

5.在UC协议中采用SNARKS以及实际优化

在UC协议中采用SNARKS

简洁非交互式知识论证（Succinct Non-interactive ARguments of Knowledge）对一般计算任务进行了简洁的证明，并已在多个系统中实现。

论文的UC协议实现采用高效的SNARK-lifting转换。

实际考虑

高效SNARK电路

一个SNARK证明器的性能主要取决于代数电路中乘法门的数量，为了更高效，论文通过两种方式设计优化电路：

1. 使用SNARK友好的密码原语
2. 构建定制的电路生成器来友好地实现SNARK，而不是依赖编译器来编译更高级别的实现

Hawk中在主要的密码学构造块包括：针对Merkle树的抗碰撞哈希函数、伪随机函数、承诺和加密。在实现中，模数q被设置为底层SNARK实现的254位素数，维数d在80位的安全级别下设置为3，在112位的安全级别下设置为4。

更多性能优化略。。。

6.实现和评估

略