3.1 Data Structures

先来看一下DAP方案需要用到哪些数据结构

本币账本

本文提出的协议可以用于基于账本的基础货币，如比特币等，出于一般性考虑，将其记为基本币，任意给定的时刻$T$，所有用户都可访问该时刻的账本$L_T$，账本上保存了一系列的交易

和比特币一样，账本仅用于附加，账本中不仅包含基本币的交易，还包含两种新的交易，下面会介绍

公共参数

Public Parament，记为$pp$，为一个系统中所有用户都可以获取到的参数，该参数由可信方在初始化时生成，应用于系统中所有算法

地址

每个用户都有至少一个地址密钥对$(addr_{pk},addr_{sk})$，前者公开，所有用户可以用前者进行支付，后者用于接受发送给的付款，用户可以用密钥生成算法生成任意数量的地址密钥对

币

币为一种抽象的数据对象，记为$c$，其与下列内容相关联

  • 币承诺（Coin Commitment）：记为$cm(c)$，当一个币$c$被铸造时，币承诺会以字符串的形式出现在账本上
  • 币值（Value）：记为$v(c)$，表示币$c$的面值，取值为一非负整数（范围为$0\leq v(c)\leq v_{max}$，其中$v_{max}$为系统参数，表示币值的最大值）
  • 币序列号（Serial Number）：记为$sn(c)$，一个唯一分配给币$c$的字符串，用于防止双花
  • 币地址（Address）：记为$addr_{pk}(c)$，表示币$c$的所有者为密钥$pk$对应的用户

新的交易

除了除了基本币交易，还有两种新的交易类型

  • Mint交易：记为$tx_{Mint}$，其为一个三元组$(cm,v,*)$，其中$cm$为币承诺，$v$为币值，$*$用于表示其他信息（取决于系统的实现），此类交易记录币$c$及其承诺$cm$和对应的币值$v$被正确的mint
  • Pour交易：记为$tx_{Pour}$，为一个八元组$(rt,sn_1^{old},sn_2^{old},cm_1^{new},cm_2^{new},v_{pub},info,*)$，其中$rt$为Merkle树根，$sn_1^{old},sn_2^{old}$表示两个旧币的序列号，$cm_1^{new},cm_2^{new}$表示两个新币的承诺，$v_{pub}$表示币值，$info$为一个任意的字符串，$*$为其他信息（取决于系统的实现）

$tx_{Pour}$记录了pour操作的两个旧币的输入$c_1^{old},c_2^{old}$，对应于序列号$sn_1^{old},sn_2^{old}$，输出为两个新币$c_1^{new},c_2^{new}$，对应于币承诺$cm_1^{new},cm_2^{new}$，以及一个公共输出$v_{pub}$（公共输出可能为0），此外$tx_{Pour}$还记录了信息串$info$（可能包含基本币$v_{pub}$接收者的信息），当这个交易执行时，其对应的Merkle树根为$rt$

铸币承诺和费币序列号

对于任意给定的时刻$T$，记两个列表

  • $CMList_T$：表示在$L_T$中出现在mint和pour事务中的币承诺的列表
  • $SNList_T$：表示在$L_T$中出现在pour事务中的序列号的列表

这两个列表都由$L_T$得到，可以将它们视为为两个独立的列表处理（实际实现时可以单独维护这两个列表以提高效率，具体可以看原文的8.3节）

基于承诺的Merkle Tree

对于任意给定的时刻$T$，$Tree_T$表示一个基于$CMList_T$的Merkle树，其树根为$rt_T$，函数$Path_T(cm)$表示$CMList_T$中的币承诺$cm$在$Tree_T$中的验证路径

为了方便起见，假设$L_T$同时存储了$rt_{T'}(T<T')$，也即每一棵树都存储了所有过去的Merkle树根

3.2 Algorithms

DAP方案$\Pi$为六个多项式时间算法组成的元组

$$ (Setup,CreateAddress,Mint,Pour,VerifyTransaction,Receive) $$

具体的定义如下

Setup

  • 输入：安全参数$\lambda$
  • 输出：公共参数$pp$

该算法由可信方执行，公共参数会在系统中公开，所有参与方都可见（可以将该算法嵌入到协议的实现中），Setup算法仅执行一次，之后不再需要可信方，不再保留全局密码或陷门

Creating payment addresses

  • 输入：公共参数pp
  • 输出：地址密钥对$(addr_{pk},addr_{sk})$

算法生成一个地址密钥对，每个用户至少有一个地址密钥对以用于接收币，地址密钥对中地址公钥公开，地址私钥由用户保留，以用于兑换发送到对应地址公钥的币，用户可能会生成很多个地址密钥对

该算法无需交互（$pp$是全局可见的，因此无需交互）

Minting coins

  • 输入：公共参数$pp$，币值$v\in\{0,1,...,v_{max}\}$，接收方地址公钥$addr_{pk}$
  • 输出：币$c$，mint事务$tx_{Mint}$

系统参数$v_{max}$限制了一个币的最大面值，输出币$c$具有价值$v$和接收地址$addr_{pk}$，mint交易$tx_{Mint}$为$(cm,v,*)$，其中$cm$为$c$的币承诺

Pouring coins
  • 输入：公共参数$pp$，Merkle树根$rt$，旧币$c_1^{old},c_2^{old}$，旧地址私钥$addr_{sk,1}^{old},addr_{sk,2}^{old}$，验证路径$path_1,path_2$（分别对应于树根$rt$的两个币承诺$cm(c_1^{old},cm_2^{old})$），新币值$v_1^{new},v_2^{new}$，新地址公钥$addr_{pk,1}^{old},addr_{pk,2}^{old}$，公共值$v_{pub}$，事务信息$info$
  • 输出：新币$c_1^{new},c_2^{new}$，pour交易$tx_{Pour}$

Pouring算法将输入币的价值转化为新的输出币，将输入币标记为已消费

此外，输入值的一小部分可能会被公开，pouring操作允许用户将币细分为更小的值、合并币值、转移拥有者或进行公开支付

为了确保两个旧币已被正确mint，pour算法需要将Merkle树根和两个旧币的验证路径作为输入，而两个输入新币值$v_1^{new},v_2^{new}$作为两个新币的面值，两个地址公钥作为这两个新币的接收者

公共值$v_{pub}$指定公开花费的金额（如兑换硬币或支付事务费用），因此输出值必须等于输入值，也即$v_1^{new}+v_2^{new}+v_{pub}=v_1^{old}+v_2^{old}$，且等式两侧都不能超过$v_{max}$

$info$表示接受任意字符串作为信息，将该信息绑定到pour交易中

事务$tx_{Pour}$只显示一个值，即公共值$v_{pub}$（可能为零），且不会透露新旧硬币的支付地址或价值

Verifing transactions
  • 输入：公共参数$pp$，mint或pour交易$tx$，当前账本$L$
  • 输出：单比特$b$（当且仅当该事务$tx$合法时$b=1$）

该算法检查交易的有效性

由于mint和pour交易都必须经过验证，才能被认为是好的交易，实际上交易可以由维护账本的分布式系统中的节点以及依赖这些交易的用户进行验证

Receiving coins
  • 输入：接收方的地址密钥对$(addr_{pk},addr_{sk})$，当前账本L
  • 输出：收到的（未花费的）币的集合

当具有地址密钥对$(addr_{pk},addr_{sk})$的用户希望接受发送到$addr_{pk}$的付款时，该算法会扫描账本L，对于每个出现在账本L上且发送到地址$addr_{pk}$的交易，算法输出对应的币，且这些币的序列号不在账本L上

以这种方式收到的币可能会被使用（比如mint），或使用pour算法（仅要求receive算法通过pour算法检测支付给地址$addr_{pk}$的币，而不要求检测用户自己mint的币）

3.3 Completeness

DAP方案的完备性要求未花费的硬币可以被正确花费

具体而言，考虑一个账本样本器$\mathcal S$，器输出一个账本$L$，若$c_1,c_2$为两个硬币，且两者的币承诺都正确的出现在了$L$上，但他们的序列号并没有出现在$L$上，此时这两个币可以通过pour操作进行花费，也即对这两个币执行pour算法，得到的$tx_{Pour}$事务会通过Verify算法的验证，新币可以用Receive算法指定接收者

更进一步的，事务$tx_{Pour}$正确的记录了预期的公共值$v_{pub}$和事务信息$info$，该性质的形式化基于不完全性实验$INCOMP$

  • Def 3.1：若没有一个多项式大小的账本样本器$S$可以以大于$negl$的概率赢得$INCOMP$，则称DAP方案$\Pi=(Setup,CreateAddress,Mint,Pour,VerifyTransaction,Receive)$为完备的

3.4 Security

DAP方案的安全性描述为三个性质，称为账本的不可区分性，交易不可延展性，平衡性

  • Def 3.2：若DAP方案$\Pi=(Setup,CreateAddress,Mint,Pour,VerifyTransaction,Receive)$满足账本的不可区分性，交易不可延展性，平衡性，则称DAP方案为安全的

性质的非正式概述如下，正式概述见附录C

每个属性形式化为敌手$\mathcal A$和挑战者$\mathcal C$之间的游戏，游戏中，城市放的行为通过DAP方案的预言机$\mathcal O^{DAP}$，其维护一个账本L，并为城市放提供执行算法CreateADDress、Mint、Pour和Receive的接口

为了从诚实的参与方那里获取到行为，$\mathcal A$传递一个请求给C，C（进行健全性检查后）代理到$\mathcal O^{DAP}$，对于请求诚实方执行操作的每个查询，$\mathcal A$指定以前的事务的身份及其输入值，并知晓事物的结果，但不知道事务生成所涉及的陷门或秘密参数

预言机$\mathcal O^{DAP}$同时还提供一个Insert查询，允许$\mathcal A$直接将任意的事务附加到账本$L$中

账本不可区分性

Ledger Indistinguishability，该性质描述了即便敌手可以自适应的诱导诚实的参与方执行其选择的DAP操作，账本除了公开的信息（币的mint信息，公共值，信息串，事务总数等）以外，不会向敌手暴露任何信息

换句话说，账本不可区分性确保了没有一个有界的敌手$\mathcal A$可以区分由使用两个DAP方案预言机建立的不同的账本$L_0,L_1$，这两个预言机的请求为公开一致的（公开一致的表示他们具有相同的类型，且在公开披露的信息和与$\mathcal A$控制的地址相关的信息是相同的）

账本不可区分性形式化为$L-IND$，具体如下

首先挑战者选择一个随即比特并初始化两个DAP预言机$\mathcal O^{DAP}_0,\mathcal O^{DAP}_1$，并维护两个账本$L_0,L_1$。整个过程中挑战者允许敌手$\mathcal A$向两个预言机发起请求，从而控制两个账本上诚实方的行为，挑战者会随机的向敌手提供两个账本的视图（如$L_{left}=L_b,L_{right}=L_{1-b}$），敌手的目标是区分这两个账本（也即敌手需要确认$b=0$或$b=1$）

每一轮实验中，敌手都会成对的发出查询类型$Q,Q'$，若查询类型为CreateAddress，则在两个预言机上会生成相同的地址，若为Mint、Pour、Receive等操作，则Q代表账本$L_0$，Q'代表账本$L_1$，对于Insert请求，$Q$代表向$L_{left}$发起，$Q'$代表$L_{right}$

此外，敌手的查询受到限制，因为必须保持两个分类账的公开一直行（如Mint查询的公共值必须相同，Pour查询的铸币金额也必须相同）

实验结束时，敌手$\mathcal A$输出$b'$，若$b=b'$时敌手赢得游戏，分类账不可区分性要求敌手赢得L-IND的概率不大于$\frac{1}{2}+negl$

交易不可延展性

Transaction Non-Malleability，该性质要求没有任何一个有界的敌手可以修改（有效的）Pour交易中存储的任何数据，交易不可延展性可以防止恶意的攻击者在他人交易添加到分类账之前对其进行修改（如重定向pour交易中基本币的公共输入）

交易不可延展性形式化定义为一个实验$TR-NM$，其中敌手$\mathcal A$与DAP预言机交互并输出一个pour事务$tx^*$，记$T$为DAP预言机返回的一个pour事务集，$L$表示最终账本，$\mathcal A$赢得游戏的方式为：存在一个$tx\in \mathcal T$，满足

  1. $tx^*\neq tx$
  2. $tx^*$中包含了$tx$中的序列号
  3. $tx$和$tx^*$均为$L$包含的所有事务$L'$中的有效事务

换句话说，若敌手$\mathcal A$赢得游戏，则意味着其可以修改以前的某些pour交易，并以不同的方式使用了相同的硬币

交易不可延展性要求敌手$\mathcal A$赢得$TR-NM$为$negl$（若$tx^*$中包含了之前使用过的币的序列号，则$\mathcal A$可以生成与$T$中事务无关的有效的pour交易）

平衡性

Balance，平衡性要求没有任何有界的敌手$\mathcal A$都不能拥有比其mint或received的更多的钱币

平衡性形式化为$BAL$，其中敌手任意的与DAP语言机进行交互，并输出币的集合$S_{coin}$，记$ADDR$表示由请求CreateAddress算法返回的一系列的（诚实用户的）地址，则当且仅当敌手$\mathcal A$可花费或已花费的币（可以是币，也可以是基本币的公共输出）大于其mint或收到的币时，赢得游戏

意思就是，若$v_{Unspent}+v_{Basecoin}+v_{A\rightarrow ADDR}<v_{Mint}+v_{ADDR\rightarrow A}$，则意味着A赢得了$BAL$游戏，其中$v_{Unspent}$表示集合$S_{coin}$中未花费的币，$v_{Basecoin}$表示账本上由$\mathcal A$生成的公共输出的总和，$v_{Mint}$表示$\mathcal A$进行mint交易的总的币值，剩余两个表示由$\mathcal A$转账或转账到$\mathcal A$

平衡性要求$\mathcal A$赢得$BAL$的概率为$negl$