区块链以其去中心化、防篡改、可追溯等特性，解决了中心化模式引起的数据可靠性差、维护困难、“数据孤岛”等问题，在金融、医疗、供应链等行业得到了广泛的应用^[1-8]. 目前，区块链已衍生出公有链、私有链、联盟链等多个分支^[9-10]，通过与大数据、人工智能、安全多方计算等新兴技术的深度结合，区块链将深刻地改变社会的管理及运行方式^[11].

持续增长的存储量已成为制约区块链可扩展性的关键瓶颈^[12]. 在区块链中，存储主要分为链上数据和状态数据2部分. 网络中的全节点2部分数据都须存储，数量更多的轻节点通常只需要维护状态数据，即可实现交易合法性的高效验证. 根据状态数据存储方式的不同，区块链可以分为两大范式：以以太坊为代表的“账户-余额”模型(状态数据被存储为State Tries)和以比特币为代表的“未花费的交易输出(unspent transaction outputs, UTXO)”模型(状态数据被存储为UTXO Set)^[13-14]. 随着用户、交易数量的激增，节点需要存储的状态数据不断膨胀. 最近，比特币节点维护的UTXO Set已达到4.65 GB，并保持增长的趋势^[15]. 一方面，状态数据的不断增长加剧了节点的存储负担；另一方面，超出节点内存容量的状态数据将不得不存放到访问速度缓慢的磁盘中，这不仅会拖慢交易验证效率，而且会增大遭受拒绝服务攻击的风险^[16]. 上述“状态爆炸”问题阻碍了资源有限节点参与区块链系统的交易验证过程，在增大区块链中心化风险的同时，制约了其在供应量金融、工业物联网、边缘计算等场景中的应用^[17-18].

针对上述问题，本文提出基于双RSA累加器的UTXO模型区块链无状态交易验证方案. 该方案分别针对未花费的交易输出集合(UTXO Set)和已花费的交易输出集合(spent transaction outputs set, STXO Set)构建2个独立的RSA累加器，2个累加器均只执行添加操作来更新承诺. 交易的有效性由2个承诺共同验证. 得益于定长的RSA证明和高效的添加操作，该方案以较少的通信开销为代价，有效降低了状态数据存储负担，保证了交易验证的效率，具有较高的实用性.

目前针对区块链“状态爆炸”问题，研究者提出一系列解决方案，具体可分为数据转移、分布式存储及无状态交易验证3类. 第1类方案中，Xu等^[19]提出状态信息线下存储方案SlimChain. 其中，完整的状态信息被转移到选定的全节点，轻节点只保留状态信息摘要，实现存储量的大幅削减. 轻节点验证交易必须依靠全节点，在增大系统中心化程度的同时，额外引入了数据泄露的风险. 第2类方法中，Guo等^[20]提出基于冗余余数系统的分布式存储模型，通过求模运算，将固定长度的余额映射为一系列截短的余数，分发至不同节点存储，削减了单个节点的存储量. 单个节点的存储负担会随着整体状态的增加而线性增长，无法从根本上解决问题，数据的分发、收集、恢复过程引入额外的安全风险.

基于密码学累加器的无状态交易验证是解决区块链“状态爆炸”问题的崭新思路，基本思想是利用密码学承诺取代状态信息，利用承诺更新来反映状态变化，利用成员证明来验证交易合法性. 节点只存储承诺就可以验证交易的前提是，交易发起者在原本的交易之上需要提供对应的成员证明，而这份证明会带来额外的通信开销. Todd^[21]通过默克尔树对UTXO Set进行聚合，记录默克尔树根并生成对应的见证，实现了UTXO模型区块链的无状态交易验证. 该方案的不足之处在于默克尔证明的数据大小随着UTXO Set的膨胀呈对数增长，这份证明带来的通信开销将远远大于交易本身. Chepurnoy等^[22-24]提出的方案可以视为Todd方案的变种. Boneh等^[25]利用RSA累加器生成的定长证明来验证UTXO的存在性和未花费性，通过“批处理”技术进一步降低通信开销. 该方案的不足之处在于花掉的UTXO需要从累加器中删除，删除操作的复杂性极大地拖慢了平均出块时间，阻碍了方案的实际应用. 在Boneh等^[25]的基础上，Chen等^[26]利用RSA累加器证明UTXO的未花费性，利用默克尔山脉证明UTXO的存在性，回避了RSA累加器删除元素的问题，提高了交易验证效率，但默克尔证明导致了通信开销的增加.

区块链是一系列区块通过加密算法连缀形成的反向链表. 区块由区块头和区块体组成. 区块头存储整个区块的元数据，主要包括父哈希、默克尔树根、难度值以及随机数等，可以实现区块链的大部分功能^[14]. 父哈希是前一个区块的哈希值，凭借哈希函数的单向性及抗碰撞特性，保证了区块链的安全性^[23]. 默克尔树根由包含在区块体内的全部交易哈希以二叉树的形式两两向上聚合得到，保证了交易的数据完整性. 难度值与随机数用来判定“记账权”，各节点争夺“记账权”的过程被称为共识. 目前，最常用也最安全的共识算法是工作量证明(proof of work, PoW)，在该过程中，节点不断改变随机数的值，直到整个区块头的哈希小于预设难度^[13].

区块体维护全部的历史记录，即网络中发生过的每一笔交易，是区块链数据产生、状态变化的凭证. 交易是实现区块链功能的最小单位. 比特币中，一笔合法的交易由多个输入、输出组成，其中每个输入都必须引用之前某笔合法交易产生的未花费的输出(UTXO). 输入被称为已花费的交易输出(STXO). 最简单的交易只有单个输入和输出. 伴随着交易的执行，各节点添加每个UTXO至UTXO Set，从中移除每个STXO，在区块达成共识后，统一更新本地状态. 在节点本地，UTXO Set一般以键值对的形式存储，一个UTXO可以由键值对{TxID:(Index, Address, Value)}唯一表征. TxID是产生该UTXO的交易哈希，Index是该UTXO在输出集合中的索引，两者结合反映了UTXO 的存在性. Address和Value分别是交易接收者和锁定在该UTXO内的金额. UTXO模型区块链中交易的数据结构如图1所示. 其中，第2笔交易(Tx₁)引用第1笔交易(Tx₀)产生的第1笔输出(Outputs[0])作为自己的第1笔输入(Inputs[0]). Version表示版本号，SignScript与PubScript分别表示解锁脚本与锁定脚本^[13].

目前, UTXO模型区块链均采用状态化设计，即节点本地维护并更新UTXO Set，不需要追溯整个账本，即可高效验证交易合法性. 如图2所示，状态区块链中，一笔交易从签发到最终确认，要经历以下步骤. 1)节点基于本地维护的UTXO Set，引用合法的UTXO作为输入，签发交易并发送给邻居节点. 2)接收到新交易的节点验证交易签名(SignScript)，基于本地维护的UTXO Set验证交易输入是否引用合法的UTXO，锁定在该UTXO内的资产是否不小于转账金额. 若验证通过，则交易合法. 节点将交易缓存进本地交易池，转发给邻居节点. 3)节点从本地交易池挑选部分交易打包进区块，执行交易并更新本地UTXO Set，生成默克尔树根，寻找满足难度要求的随机数. 率先完成PoW过程的节点获得“记账权”，将新生成的区块广播至全网. 4)收到新区块的各节点停止本地PoW过程，校验新区块. 若校验成功，则同步新区块到本地区块链，更新本地UTXO Set (添加新的UTXO，移除STXO). 5)当包含该交易的区块接续足够数量的后续区块时，该交易可以被认为得以最终确认^[14].

无状态区块链是新兴的设计思想，通过实现无状态交易验证来解决状态爆炸问题. 如图3所示，区块头添加密码学承诺(Comm_h)，反映交易执行引起的状态变化. 节点本地不再维护全部的UTXO Set，取而代之的是同Comm_h一一对应的密码学见证(witness). 在无状态区块链中，一笔交易从签发到最终确认，步骤相对状态区块链发生如下改变. 1)签发交易时，witness同原交易内容一同被转发至邻居节点，后者结合witness和包含在最新区块头内的承诺，验证交易签发者引用UTXO的合法性. 2)当节点打包新区块时，根据交易内容更新密码学承诺(Comm_h$ \to $Comm_h+1). 3)当各节点验证新区块时，验证密码学承诺是否被正确更新，校验工作量证明. 在验证通过后，各节点将新区块追加到本地区块链末尾的同时，相应地更新witness. 上述过程表明，区块头中密码学承诺的生成与更新、节点本地witness的生成与更新以及结合两者验证UTXO的合法性，是实现无状态交易验证的关键.

目前，构建无状态交易验证方案常用的密码学工具是RSA累加器. 作为通用累加器，RSA累加器可以通过模幂运算，生成动态变化集合的密码学承诺. 基于该承诺，分别为任何一个(不)属于集合的元素生成定长的(非)成员见证^[27]. RSA累加器具有抗碰撞性与不可否认性，分别使得伪造非集合元素的成员见证、伪造集合元素的非成员见证在计算上不可行，具有极高的安全性. RSA累加器生成的密码学承诺同集合元素插入累加器的顺序无关，相对于密码学承诺与元素顺序深度绑定的默克尔累加器具有明显优势^[28]. RSA累加器的构建过程如下.

1）从未知阶数的有限循环群中选出一大数N作为模幂运算的模数，该模数可以分解为2个强素数，即有N= $ p q $. p、q由可信的第三方机构或安全多方计算秘密生成，计算得到N后即行销毁^[29]. 在实际中，N一般选用RSA-Lab的RSA-2048或RSA-3072^[30].

2）从未知阶数的有限循环群中选出一大质数G作为RSA累加器的生成元. 累加器的密码学承诺称为累加器状态. 初始累加器状态为 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{0}= {G}^{1}{\rm{mod}}\;N $.

基于全素数集合S = {x₁, x₂, $\cdots , x_{n-1} $}，RSA累加器可以生成对S的密码学承诺及任意集合(外)内元素对应的(非)成员见证，通过该承诺，验证某个元素的(非)存在性. 由于RSA累加器只能处理素数，故本文中的集合（外）内元素都默认为素数.

生成承诺：t时刻，累加S内全部元素至RSA后，状态为

(1) $ \begin{array}{c}{\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n-1}^{t}={G}^{x} \mod\;N.\end{array} $

式中： $x={\displaystyle\prod }_{i=1}^{n-1}{x}_{i}$. 简略起见，后续模幂运算表示中都将省略“ $\mod\;N$”.

生成集合内元素的成员见证：对于x_i ( $1 \leqslant i \leqslant n-1$)，t时刻成员见证为

(2) $ \begin{array}{c}{\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{t}={G}^{\frac{x}{{x}_{i}}}.\end{array} $

依托此时的承诺 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n-1}^{t} $及成员见证 $ {\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{t} $，可以验证x_i在S中的存在性：

(3) $ \begin{array}{c}{\left({\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{t}\right)}^{{x}_{i}}={\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n-1}^{t}.\end{array} $

生成集合外元素u的非成员见证：对于u( $ u\notin S $),u一定与x_i( $ 1 \leqslant i \leqslant n-1 $)互质. 由裴蜀定理^[31]可知，必有整数a、b, 满足ax+bu=1. 令d = G^b, 则t时刻u对应的非成员见证为

(4) $ \begin{array}{c}{\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{u}^{t}=\left(a,d\right).\end{array} $

依托此时的承诺 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n-1}^{t} $及非成员见证 $ {\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{u}^{t} $，可以验证u在S中的非存在性：

(5) $ \begin{array}{c}{d}^{u}\cdot {\left({\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n-1}^{t}\right)}^{a}=G.\end{array} $

若t+1时刻，新元素 $ {x}_{n}({x}_{n}\notin S,{x}_{n}\ne u) $添加到集合S，则可以将RSA承诺及对应的(非)成员见证，在 $t$时刻的状态基础上进行更新.

添加元素后更新承诺：

(6) $ \begin{array}{c}{\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n}^{t+1}={\left({\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n-1}^{t}\right)}^{{x}_{n}}.\end{array} $

更新集合内元素x_i( $ {\boldsymbol{1}} \leqslant {\boldsymbol{i }}\leqslant {\boldsymbol{n}}-{\boldsymbol{1}} $)的成员见证：

(7) $ \begin{array}{c}{\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{t+1}={\left({\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{t}\right)}^{{x}_{n}}.\end{array} $

更新集合外元素u的非成员见证：对于x_n$ \ne $u,有gcd(x_n, u)=1. 一定存在 $ {a}' $、 $ {b}' $，满足 $ {a}' $x_n+ $ {b}' $u=1. t+1时刻，u的非成员见证为

(8) $ \begin{array}{c}{\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{u}^{t+1}=\left({a}' a,{\left({\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n-1}^{t}\right)}^{{b}' a}\right).\end{array} $

若t+1时刻，从S中删除某个元素x_i( $ 1 \leqslant i \leqslant n-1 $)，则t+1时刻元素x_i的成员见证可以在t时刻成员见证 $ {\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{t} $的基础上进行更新.

删除元素后更新承诺：此时RSA承诺是被删除元素 ${x_i}$的成员证明 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{n-2}^{t+1}={\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{t} $.

更新集合内元素x_j($ {\boldsymbol{1}} \leqslant {\boldsymbol{j }}\leqslant {\boldsymbol{n}}-{\boldsymbol{1}} $, $ {\boldsymbol{j}} \ne {\boldsymbol{1}}$)的成员见证：根据裴蜀定理可知，一定存在a、b满足ax_i+bx_j = 1, 则t+1时刻x_j的成员见证为

(9) $ \begin{array}{c}{\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{j}^{i+1}={\left({\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{t}\right)}^{b}\cdot {\left({\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{j}^{t}\right)}^{a}.\end{array} $

当批量添加元素进S时，将全部元素的乘积视为x_n，根据上述步骤可以完成密码学承诺、见证的更新. 当批量从S中删除元素时，用全部元素的累积成员见证替换密码学承诺^[29]. 基于RSA累加器的性质，删除操作的复杂度远远超过添加元素.

在UTXO模型区块链中，交易的合法性包含2个层面：交易结构的合法性与交易字段的合法性. 交易结构的合法性是指交易符合区块链标准数据结构，交易签名与交易内容、签发者地址相匹配. 交易字段的合法性如下. 1) $ \mathrm{R}\mathrm{e}\mathrm{f}\_\mathrm{O}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{s}\mathrm{ }= \mathrm{ }\left\{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\right|\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\in \mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}\;\mathrm{S}\mathrm{e}\mathrm{t},\mathrm{ }\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\notin \mathrm{ }\mathrm{S}\mathrm{T}\mathrm{X}\mathrm{O}\;\mathrm{S}\mathrm{e}\mathrm{t}\} $，即交易引用的输出集合( $ \mathrm{R}\mathrm{e}\mathrm{f}\_\mathrm{O}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{s} $)同时满足存在性( $ \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{ }\in \mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}\;\mathrm{S}\mathrm{e}\mathrm{t} $)与未花费性( $ \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\notin \mathrm{ }\mathrm{S}\mathrm{T}\mathrm{X}\mathrm{O}\;\mathrm{S}\mathrm{e}\mathrm{t} $). 2) $ v\geqslant {v}'$，即锁定在 $ \mathrm{R}\mathrm{e}\mathrm{f}\_\mathrm{O}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{s} $内的总资产 $ v $不小于转账金额 $ {v}' $，满足可用性. 对于交易结构的合法性，无状态区块链与状态区块链验证方法相同，均依托哈希函数、非对称加密与签名技术实现. 对于交易字段的合法性，由于无法直接访问状态数据(UTXO Set)，无状态区块链主要依托RSA累加器提供的(非)成员见证来检验.

为了验证交易引用输出的存在性与未花费性，各节点本地建立并维护2个RSA累加器 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{U}} $、 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{S}} $，分别基于UTXO Set与STXO Set生成对应的承诺 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}} $与 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}} $，同时添加进区块头中. 相应地，节点本地不再维护完整的UTXO Set，只维护某笔UTXO及对应的 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $，其中 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $由UTXO Set的成员证明 $ \mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t} $和STXO Set的非成员证明 $ \mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t} $两部分组成. 随着交易的进行， $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}} $、 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}} $及本地维护的 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $均同步更新. 基于双RSA累加器的无状态交易验证模型如图4所示. 图中，Alice、Bob对应区块链中2个不同的用户，各自控制1个区块链节点来签发、广播、验证交易，实现相互转账. $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{h} $、 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{h} $组成了第 $ h $个区块block_h对应的RSA承诺. Alice发起转账的工作流程如下. 1）Alice引用属于自己的UTXO签发交易，附带该UTXO相对于 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{h} $、 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{h} $的 $ {\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}}_{h} $. 2）Bob作为矿工，在收到Alice签发的交易后，根据最新的RSA承诺(存储在block_h区块头的 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{h} $、 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{h} $)，结合交易附带的 $ {\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}}_{h} $，分别验证引用UTXO的存在性与未花费性. 在验证通过后，Bob将交易缓存进本地交易池. 3）Bob从交易池中挑选部分交易，打包生成新区块block_h+1. 在交易执行过程中，Bob依次检视各交易的输入、输出集合，将交易引用的旧输出累积进 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{S}} $，将交易产生的新输出累积进 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{U}} $，将 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{h} $、 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{h} $更新为 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{h+1} $、 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{h+1} $存储在block_h+1的区块头. 4）在Bob更新RSA承诺后，遵循特定的共识算法争夺“记账权”. 在成功获得“记账权”后，Bob将新区块block_h+1广播至全网. 5）各节点(包括Alice)在接收到新区块后，验证RSA承诺是否正确更新，验证新区块是否满足共识算法. 在验证通过后，各节点更新本地UTXO对应的 $ {\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}}_{h+1} $，使之对应于最新的RSA承诺 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{h+1} $、 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{h+1} $.

当矿工生成新区块，更新RSA承诺时，2个RSA累加器 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{U}} $、 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{S}} $均只执行添加操作而无需删除操作. 考虑到RSA累加器添加操作的复杂度远远小于删除操作，基于双RSA累加器的无状态交易验证模型大大提高了RSA承诺的更新效率，适用于实际场景.

如2.3节所示，为了应用基于双RSA累加器的无状态交易验证方案，区块链系统应预置1组公共参数G、N充当模幂运算的生成元与模数. Alice与Bob可以在创世区块block₀(区块高度 $ h=0 $)处对 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{U}} $、 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{S}} $同步进行初始化. 区块链通过创世区块将资产分发至指定地址，使得地址间相互转账成为可能，是区块链状态变化的“第一推动力”^[31]. 创世区块只包含铸币交易（如比特币的coinbase交易），特点是交易只有输出，没有输入. 为了简单起见，假设创世区块包含 $ n $笔coinbase交易，每笔交易均只产生一个输出，将 $ {v}_{i}(0 \leqslant i \leqslant n-1) $个代币分发给 $ n $个不同的账户(包括Alice与Bob)，且Alice取得创世区块的记账权.

对于每一笔交易，由于只有输出，没有输入，则有 $ \mathrm{T}\mathrm{x}\mathrm{I}\mathrm{D}=\mathrm{h}\mathrm{a}\mathrm{s}\mathrm{h}\left(\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}||\mathrm{V}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}||\mathrm{P}\mathrm{u}\mathrm{b}\mathrm{S}\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{t}\right) $，其中“ $ \left|\right| $”表示字符串拼接. 相应地，UTXO可以由键值对 $ \{\mathrm{T}\mathrm{x}\mathrm{I}\mathrm{D}: \mathrm{ }(\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\left|\right|\mathrm{V}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}\left|\right|\mathrm{P}\mathrm{u}\mathrm{b}\mathrm{S}\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{t}\left)\right\} $唯一表示，则哈希值 $H = {\rm{hash}}({\rm{TxID}}||{\rm{Index}}||{\rm{Value}}||{\rm{PubScript}})$具有唯一性. 在创世区块中，coinbase交易产生的全部输出构成了初始的UTXO Set. 由于没有输入，初始的STXO Set为空. Alice初始化 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{U}} $的过程如下.

1）对于UTXO Set中的任意一笔 $ {\mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}}_{i} $，计算对应的哈希值 $ {H}_{i} $.

2）通过系统预置的映射算法 $ {H}_{\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}} $^[25,32]，将 $ {\mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}}_{i} $对应的哈希值 $ {H}_{i} $映射至唯一的大素数 $ {P}_{i} $. 在UTXO Set处理完毕后，得到包含 $ n $个元素的大素数集合 $ {S}_{\mathrm{U}} $.

3）根据式(1)可知，Alice累积 $ {P}_{i} $至 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{U}} $，即有 ${\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{0}={G}^{{ \scriptstyle\sum }_{i=0}^{n-1}{P}_{i}}$. 对于 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{S}} $，由于STXO Set为空集，可以利用哈希函数的抗碰撞特性，任选一个素数P_r累积进 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{S}} $完成初始化.

创世区块将 $ {v}_{i} $个代币分发给Bob. Bob控制的UTXO可以唯一表示为 $ \{\mathrm{T}\mathrm{x}\mathrm{I}\mathrm{D}:(0\left|\right|{v}_{i}\left|\right|\mathrm{B}\mathrm{o}\mathrm{b}\left)\right\} $. 在接收、验证并同步Alice发布的创世区块后，Bob初始化本地 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $的过程如下.

1）计算拥有的 $ {\mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}}_{i} $的哈希值 $ {H}_{i} $，映射至大素数 $ {P}_{i} $.

2）根据式(2)，基于RSA承诺 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{0} $，生成 $ {P}_{i} $相对于UTXO Set的成员证明以提供存在性，即有 $ {\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{0}={G}^{\frac{{\sum }_{i=0}^{n-1}{P}_{i}}{{P}_{i}}} $.

3）根据式(4)，基于RSA承诺 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{0} $，生成 $ {P}_{i} $相对于STXO Set的非成员见证以提供未花费性，即有 $ {\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{0}=({a}_{i},{d}_{i}) $，其中 $ {a}_{i}{P}_{i}+{b}_{i} {P}_{{\rm{r}}}=1 $，且 $ {d}_{i}={G}^{{b}_{i}} $.

4）存在性(成员)见证、未花费性(非成员)见证共同组成 $ {\mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}}_{i} $相对于 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{0} $及 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{0} $的见证，即有 $ {\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}}_{i}=({\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{0}，{\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{0}) $.

在初始化完毕后，Bob控制的节点只须将属于Bob的UTXO及对应的见证保存在本地，无须保留完整的UTXO Set. 其他账户控制的节点遵循相同的操作生成并保留各自UTXO及对应的见证. 考虑到实际场景中，完整UTXO Set大小接近甚至超过1亿，单个节点正常发起交易所必须的UTXO数量少于100，而RSA累加器产生的见证是定长的，所以节点本地维护的状态数据将大幅减少.

在状态区块链中，节点通过查询本地保存的完整UTXO Set，引用有效UTXO，签发交易. 验证节点对照本地保存的完整UTXO Set，查询引用UTXO对应的资产并与转账金额比较，判断该UTXO的存在性、未花费性及可用性，决定新交易是否合法. 在无状态区块链中，各节点不再保存完整的UTXO Set，只保留自身相关的部分UTXO、对应的 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $以及存储在区块头的RSA承诺. 除了本地控制的UTXO外，各节点无法掌握锁定在其他UTXO中的金额. 相应地，应用基于双RSA的无状态交易验证模型后，交易数据结构及验证流程将发生改变，以保证交易签发、验证的正常进行.

如图5所示为新的交易数据结构，为了方便、清晰起见，该交易只包含单个输入、输出，各自对应的解锁脚本(SignScript)与锁定脚本(PubScript)均被省略. 与图1所示的有状态UTXO模型区块链中的交易数据结构相比，新交易在输入项内部额外添加了2个字段 $ v $与 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $. 其中， $ v $表示锁定在引用UTXO中的资产，由交易签发者自主声明，方便其余节点比较锁定资产与转账金额的大小，验证可用性. $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $引用UTXO的密码学见证，包括相对于 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}} $的成员证明 $ \mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t} $与相对于 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}} $的非成员证明 $ \mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t} $，分别保证UTXO的存在性(在UTXO Set中)与未花费性(不在STXO Set中). 输出项保持原始数据结构.

假设创世区块产生后，基于锁定在 $ {\mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}}_{i} $中的 $ {v}_{i} $个代币，节点发起转账，转账金额记为 $ v'$. 交易签发流程如下.

1）引用 $ {\mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}}_{i} $作为新交易唯一的输入，对应的Index为0.

2） 声明锁定在 $ {\mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}}_{i} $内的资产为 $ {v}_{i} $.

3）拼接 $ {\mathrm{U}\mathrm{T}\mathrm{X}\mathrm{O}}_{i} $对应的 $ \mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t} $、 $ \mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t} $组成见证.

4）按规则填充交易各个字段. 填充完毕后进行签名，转发给邻居节点.

在收到新交易后，交易验证流程如下.

1）验证交易签名是否合法. 若签名验证失败，则直接抛弃.

2）提取交易输出项各字段，包括声明资产 $ {v}_{i} $、引用的UTXO及对应的 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $.

3）计算该UTXO对应的哈希值

$ H=\mathrm{h}\mathrm{a}\mathrm{s}\mathrm{h} \left(\mathrm{T}\mathrm{x}\mathrm{I}\mathrm{D}||\mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}||{v}_{i}||\mathrm{P}\mathrm{u}\mathrm{b}\mathrm{S}\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{t}\right),$

其中 $ \mathrm{T}\mathrm{x}\mathrm{I}\mathrm{D} $为产生该UTXO的交易对应的哈希值， $ \mathrm{I}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x} $为该UTXO在交易输出中的索引， $ \mathrm{P}\mathrm{u}\mathrm{b}\mathrm{S}\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{t} $为交易签发者对应的锁定脚本.

4）基于最新的RSA承诺(保存在创世区块头的 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{0} $)，根据式(3)，计算 $ {\left({\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{0}\right)}^{{P}_{i}}={\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{0} $是否成立，验证UTXO的存在性.

5）基于最新的RSA承诺(保存在创世区块头的 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{0} $)，根据式(5)，计算 $ {\left({d}_{i}\right)}^{u}{\left({\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{0}\right)}^{{a}_{i}}=G $是否成立，验证UTXO的未花费性.

6）存在性、未花费性验证通过后，比较 $ {v}_{i} $、 $ {v}'$. 其中， $ {v}_{i} $、 $ {v}' $分别为各输入金额与输出金额的总和. 若 $ {v}_{i}\geqslant {v}'$成立，则UTXO同时满足存在性、未花费性与可用性，交易合法.

与状态区块链一样，通过验证的交易将被节点缓存进本地交易池，遵循自定义规则打包进新区块. 上述的签发和验证过程适用于多个输入、输出的交易，需要多验证几个交易输入的见证.

在无状态区块链中，生成新区块、争夺记账权的过程与状态区块链基本一致. 唯一的不同点如下：在无状态区块链中，矿工在生成默克尔树根之后，进行工作量证明之前，需要遍历每笔交易的输入、输出，更新UTXO Set及STXO Set，进而更新RSA承诺，并保存在新区块头. 基于创世区块，假设Bob作为矿工，创建新区块block₁并取得记账权. block₁包含 $ {n}_{1} $笔交易，每笔交易只包含单个输入输出. Bob生成新区块并更新RSA承诺的步骤如下.

1）根据自定义规则，从本地交易池打包部分交易创建新区块block₁，生成对应的默克尔树根.

2）遍历每笔交易的输入、输出，将输入引用的UTXO缓存进STXO Set，将新产生的UTXO缓存进UTXO Set. 由于交易均为单输入、单输出，STXO Set与UTXO Set的大小均为 $ {n}_{1} $.

3）对于UTXO Set、STXO Set内的每一个元素，计算对应的哈希值，根据预置算法映射为唯一的大素数 $ {P}_{\mathrm{U}}^{i} $、 $ {P}_{\mathrm{S}}^{i}(0 \leqslant i \leqslant {n}_{1}-1) $. 在全部元素处理完毕后，得到2个包含 $ {n}_{1} $个元素的大素数集合 $ {S}_{\mathrm{U}} $与 $ {S}_{\mathrm{S}} $.

4）根据式(6)，基于最新的RSA承诺(存储在创世区块头的 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{0} $)，将 $ {S}_{\mathrm{U}} $全部元素累积至 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{U}} $，将 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{0} $更新为 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{1} $.

5）根据式(6)，基于最新的RSA承诺(存储在创世区块头的 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{0} $)，将 $ {S}_{\mathrm{S}} $全部元素累积至 $ {\mathrm{R}\mathrm{S}\mathrm{A}}_{\mathrm{S}} $，将 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{0} $更新为 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{1} $ .

Bob完成RSA承诺的更新并存储在新区块block₁的区块头后，与状态区块链一样，通过遍历 $ \mathrm{n}\mathrm{o}\mathrm{n}\mathrm{c}\mathrm{e} $完成工作量证明，争夺记账权，将block₁广播至全网. 在其余节点接收到block₁后，遵循上述流程，遍历每笔交易的输入、输出，验证RSA承诺是否正确更新. 与状态区块链一样，各节点验证Bob的工作量证明. 在验证通过后，各节点同步新区块至本地. 此时，各节点根据最新RSA承诺及全部交易，更新本地UTXO对应的 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $. 步骤如下.

1）若在最新区块获得了新的UTXO，则节点需要基于最新承诺中的 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{U}}^{1} $，根据式(2)生成对应的成员证明 $ {\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{1} $，基于最新承诺中的 $ {\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}}_{\mathrm{S}}^{1} $，根据式(4)生成对应的非成员证明 $ {\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{1} $.

2）若本地存在之前获得的UTXO，且未被使用，则节点需要基于 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $中的成员证明，根据式(7)将 $ {\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{0} $更新为 $ {\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{1} $，基于 $ \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s} $中的非成员证明，根据式(8)将 $ {\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{0} $更新为 $ {\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{m}\mathrm{e}\mathrm{m}\mathrm{W}\mathrm{i}\mathrm{t}}_{i}^{1} $.

在区块链网络中，节点可以简单地划分为全节点和轻节点2类. 前者保存区块链历史数据和完整状态，可以独立验证交易；后者只保存区块头，需要依赖全节点验证交易. 在本文方案中，理论上可以实现所有节点均是轻节点，因为节点只需保存最新的累加器承诺，就可以独立验证交易，根据新区块中的交易更新承诺和自己本地的见证. 考虑到实用性，在应用本文方案的系统中会保留一定数量的全节点，但全节点的功能将会发生变化.

在本文方案中，轻节点只保存包含最新承诺的区块头，负责验证交易以及参与区块的生成与共识这些区块链主要事务. 全节点存储区块链历史数据和完整状态，主要功能是保障区块链系统的可追溯性，提供一定的安全性. 因为见证需要一直与承诺保持同步更新，所以全节点还可以提供管理UTXO及见证的服务，不仅可以避免用户因离线或丢失见证而导致UTXO无法使用的情况，而且可以利用全节点的计算及存储资源.

在基于双RSA累加器的无状态交易验证方案中，各验证节点不再维护完整的UTXO Set，只维护自身相关的UTXO及对应的见证，大幅降低节点的存储负担，通过存储在区块头的RSA承诺保证交易合法性的高效验证. 为了保证交易签发、验证的正常进行，相应修改数据结构，增加声明资产及见证字段，导致额外的通信开销. 基于提出的无状态交易验证方案，从理论层面分析在存储效率、通信开销及计算复杂度3个方面的表现. 设计模拟实验，从上述3个方面对无状态验证方案的表现进行评估，与同类型方案进行比较.

压缩率是指在应用无状态交易验证方案后，节点本地节省的存储开销相对于原始存储量的比值. 在状态区块链中，各节点维护完整的UTXO Set. 假设每笔UTXO的平均比特长度为 $ \overline{{L}_{\mathrm{U}}} $，UTXO Set中共包含m笔UTXO，则节点原始存储开销为 $ {\mathrm{V}\mathrm{o}\mathrm{l}}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{f}\mathrm{u}\mathrm{l}}=m \overline{{L}_{\mathrm{U}}} $. 在应用无状态交易验证方案后，假设各节点平均持有 $ {m}' $笔UTXO及对应的witness，则节点实际的存储负担为 $ {\mathrm{V}\mathrm{o}\mathrm{l}}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{s}}={m}' \left(\overline{{L}_{\mathrm{U}}}+{L}_{\mathrm{w}\mathrm{i}\mathrm{t}}\right)+{L}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}} $. 其中 $ {L}_{\mathrm{w}\mathrm{i}\mathrm{t}} $为一份见证的比特长度， $ {L}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}} $为承诺的比特长度. 压缩率 $ \;\beta $可以通过下式计算得到：

(10) $ \beta =\;1-\dfrac{{\mathrm{V}\mathrm{o}\mathrm{l}}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{s}}}{{\mathrm{V}\mathrm{o}\mathrm{l}}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{f}\mathrm{u}\mathrm{l}}}= 1-\dfrac{{m}' \left(\overline{{L}_{\mathrm{U}}}+{L}_{\mathrm{w}\mathrm{i}\mathrm{t}}\right)+{L}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}}}{m \overline{{L}_{\mathrm{U}}}}. $

从式(10)可知，RSA累加器的N的选取越大， $ {L}_{\mathrm{w}\mathrm{i}\mathrm{t}} $越大，则方案以牺牲部分压缩率为代价可以换取更高的安全保障. 压缩率随 $ {\mathrm{着}m}' $的增大而减小. 考虑到实际生产环境中，除个别超级节点外，其余节点均维护有限个账户，因此 $ {m}'\ll m $，从而显著减少了各节点实际的存储负担.

在应用无状态交易验证方案后，交易数据结构发生改变，新增的witness字段带来了额外的通信开销. 由于RSA累加器的性质，引用一笔UTXO，witness带来的额外开销是固定值，为3b. 其中，b为所选系统参数N的位宽. N一般选用RSA-2048 (2 048 bits)，则本文方案相应的通信开销为6 144 bits. Boneh等^[25]提出的方案为每笔UTXO引入固定的通信开销. 由于只采用一个RSA累加器，通信开销只有本文方案的1/3. 与基于RSA累加器的无状态交易验证方案相比，Todd^[21]采用的累加器为默克尔累加器，每笔UTXO对应的通信开销随着UTXO数量的增加呈对数增长. EDRAX^[22]采用默克尔累加器的变种，其中每一笔UTXO引入的额外通信开销为10 240 bits，远远超过本文方案. MiniChain^[26]的通信开销不仅会受到区块中输出数量的影响，而且会随着区块的增加而无限制地增大. 考虑到实际生产环境中UTXO数量超过1亿^[15]，基于双RSA累加器的无状态交易验证方案在通信开销表现上，虽然略逊于Boneh等^[25]提出的单RSA方案，但相对于基于默克尔体制的验证方案具有显著的优势. 如表1所示为目前主流无状态交易验证方案体制及通信开销,与本文方案进行了对比. 表中，M为预设的UTXO数量，且M $ > $m $ \gg $b；n为产生该UTXO的区块中交易输出的总数；h为当前区块的高度.

双RSA无状态交易验证方案在交易生命周期的不同阶段，分别执行累加器初始化、见证初始化、(非)成员验证以及承诺、见证更新. 不同的操作具有不同的时间复杂度. 基于通用累加器的性质可知，RSA初始化、添加元素、验证(非)成员见证均为O(1). 当矿工打包新区块时，要遍历全部交易花费及产生的UTXO，对应更新密码学承诺. 时间复杂度与区块体包含花费及产生UTXO的数量呈线性正相关. 与双RSA方案相比，Boneh的单RSA方案由于安全删除操作本身的复杂性，承诺更新的时间复杂度与花费的UTXO总量的平方呈正相关的关系. 尽管双RSA方案要同步更新2个承诺，计算开销仍远远小于单RSA方案. 与RSA体制相比，在基于默克尔累加器的验证方案中，初始化、承诺生成、更新以及见证生成、更新的复杂度均取决于默克尔树(或其变体)的高度，随着UTXO数量的增加呈对数增长的关系. 由于各个过程均实际执行高效的哈希计算，整体时间开销远小于基于RSA的无状态验证方案.

如表2所示为目前主流无状态交易验证方案及时间复杂度,与本文方案进行对比. 表中，k_i、k_o分别为区块包含的已花费和新产生的UTXO数量.

基于上述分析可知，双RSA累加器的无状态交易验证方案能够在压缩率、通信开销、内存占用及计算复杂度等方面达成较好的平衡，更适用于生产环境.

该实验使用的设备是一台配备4核Intel(R) Core(TM) i7-7700HQ CPU @ 2.80 GHz处理器、16.0 GB内存的电脑. 通过Python 3.7模拟UTXO区块链网络及交易处理流程. 对使用了相同体制累加器的单、双RSA方案及MiniChain进行仿真实现，3个方案均选用相同的系统参数. 循环群模数N选定为安全性更强的RSA-3072，G 选用 $ {2}^{256}-{2}^{32}-977 $. 该实验数据源是来自比特币的10⁷笔UTXO的数据. 为了方便实验及数据统计，将所得UTXO重新封装为只包含单输入、单输出的交易. 为了使仿真结果更直观、明显，各节点持有的UTXO数量 $ {m}' $没有选用比特币的典型数据，而是指定为5 000和10 000，区块高度设为100 000. 在实验过程中，对节点压缩率及交易生命周期各阶段耗时进行统计，将实验过程重复多次，以消除结果的偶然性.

当处理不同数量的UTXO时，3个无状态方案下的节点本地存储压缩率变化如图6所示. 可见，m越大， $ {m}'$越小， $ \;\beta $越高. 其中，单RSA方案的压缩率最高，本文方案次之，MiniChain最低，这是因为本文方案和MiniChain均要额外追加一个累加器的数据，MiniChain追加的默克尔累加器的见证和承诺都大于RSA体制的累加器. 在仿真实验中，为了使实验结果具有区分度，节点本地持有的UTXO数量设为5 000及10 000，本文方案能够实现大于80%的压缩率. 在实际的比特币网络中，UTXO总量远超10⁷，节点实际维护的UTXO数量远小于5 000，因此各节点实际的压缩率更可观.

在仿真过程中，基于相同的源数据，分别统计整个交易生命周期内，使用了RSA累加器的Boneh、本文方案以及MiniChain执行各项操作产生的整体时间开销. 实验结果如图7所示. 图中，t为系统耗时，n为区块中的交易数量. 从图7可见，相比于MiniChain，本文方案完成交易的完整生命周期过程的耗时略长. 与单RSA方案相比，本文方案的操作效率具有显著优势，区块中的交易数量越大，这种效率优势越突出. 当区块内交易达到1 000笔时，利用单RSA方案进行交易验证、承诺更新及见证更新等操作的整体耗时超过2 500 s，远大于比特币出块间隔（600 s），实用性较差. 本文方案只需约50 s，对区块链出块间隔及由此决定的吞吐量、分叉率等造成的影响不大，具有更高的实用价值.

MiniChain、单RSA方案与本文的双RSA方案在操作耗时上的差距可以由图8来解释. 如图8所示为MiniChain及单、双RSA方案在交易生命周期各个节点执行各项操作的具体耗时. 可见，MiniChain各环节的耗时均略小于本文方案，这是因为默克尔累加器所进行的都是哈希运算，耗费的时间相比于RSA累加器的模幂运算基本上可以忽略不计. 单RSA方案与本文方案在交易验证、见证生成及更新等环节上的耗时相差不大，但在更新累加器承诺的环节上，本文方案的耗时远小于单RSA方案，且区块中交易数量越多，本文方案的时间优势越显著. 这是因为当更新承诺时，单RSA方案必须为每一笔被引用的UTXO执行复杂的删除操作，计算复杂度远大于执行元素添加操作.

针对区块链的状态爆炸问题，本文提出应用于UTXO模型区块链中基于双RSA累加器的无状态交易验证方案. 该方案通过使用2个分别构建于 UTXO Set和STXO Set的相互独立的RSA累加器，使区块链系统中的节点只存储2个简短的RSA承诺，无须维护完整的区块链状态（UTXO Set），即可参与交易的验证过程，能够大幅降低区块链中轻节点参与交易验证过程的存储压力.

本文描述了该方案的设计细节及完整的工作流程，设计了仿真实验. 结果表明，与其他现有方案相比，利用该方案大幅降低了节点的状态数据存储负担,只产生有限的额外通信开销，保证了交易验证的效率，具有较高的实用性. 使用默克尔累加器的无状态方案适合对交易执行效率要求较高、对通信开销要求较低的场景；本文提出的双RSA方案更适合于对通信开销要求较高、要求一定的交易执行效率的场景.