支持陷门撤销和编辑次数限制的可编辑区块链.pdf

2023 年 7 月 Journal on Communications July 2023 第 44 卷第 7 期 通 信 学 报 Vol.44 No.7支持陷门撤销和编辑次数限制的可编辑区块链 陈越，郝增航，魏江宏，胡学先，杨冬梅（信息工程大学数据与目标工程学院，河南 郑州 450001）摘 要：针对已有支持陷门撤销的可编辑区块链方案虽可撤销陷门持有者的编辑权限，但不能限制利用陷门进行编辑的次数，存在编辑权限管理不够精细的问题，提出了编辑次数限制的变色龙哈希函数，并基于此给出了一个新的可编辑区块链方案。具体而言，所构造的方案包含主陷门和从陷门以及所生成的见证，其中，从陷门用于编辑数据，主陷门用于撤销从陷门，以达到撤销编辑权限的目的，而见证可将从陷门的编辑次数严格限制为一次。所提方案在标准的困难性问题假设下被证明是安全的。理论分析和仿真实验表明，与已有支持陷门撤销的方案相比，所提方案在安全性方面具有优势，且额外引入的计算开销较小，具有一定的实用性。关键词：可编辑区块链；变色龙哈希；陷门撤销；限制编辑 中图分类号：TP309.2 文献标志码：A DOI:10.11959/j.issn.1000436x.2023135 Redactable blockchain supporting trapdoor revocation and limited number of redactions CHEN Yue,HAO Zenghang,WEI Jianghong,HU Xuexian,YANG Dongmei School of Data and Target Engineering,Information Engineering University,Zhengzhou 450001,China Abstract:Aiming at the problem that although the existing redactable blockchain schemes that support trapdoor revoca-tion could revoke the redaction permissions of trapdoor holders,but they were unable to limit the number of redactions using trapdoors,indicating an issue where the management of editing permissions was not adequately refined,a revocable chameleon hash with limited number of redactions was proposed,based on which a new redactable blockchain scheme was proposed.Specifically,the proposed scheme included a master trapdoor,a subordinate trapdoor,and the generated witness.The subordinate trapdoor was deployed for data modification,while the master trapdoor was employed to revoke the subordinate trapdoor,thus accomplishing the objective of revoking editing permissions.Meanwhile,the witness was developed to strictly limit the number of edits via the subordinate trapdoor to one time.The proposed scheme is proved to be secure under the standard complexity assumptions.Theoretical analysis and simulation expe-riments indicate that the proposed scheme has advantages in terms of security guarantee,when compared with the existing schemes supporting trapdoor revocation.At the same time it introduces little additional computation over-head,and thus has certain practicality.Keywords:redactable blockchain,chameleon hash,trapdoor revocation,limit redaction 0 引言 近年来，区块链不仅在概念上越来越被人们所熟知，其典型应用（如比特币1、以太坊2等）也逐渐普及。区块链可被视为一个共享的超级账本，其中记录了大量的交易数据，可被矿工打包生成一收稿日期：20221101；修回日期：20230118 通信作者：郝增航， 基金项目：国家自然科学基金资助项目（No.62172433,No.62172434）Foundation Item:The National Natural Science Foundation of China(No.62172433,No.62172434)第 7 期 陈越等：支持陷门撤销和编辑次数限制的可编辑区块链 101 系列的区块，而相邻区块之间相互链接最终共同组成整个区块链。不可篡改性是区块链的一个主要特性，能使被写入区块链的数据不被任何人修改，确保了链上数据的真实性，也是区块链解决去中心化环境中信任问题的根本所在。由于安全需求，对记录在区块链上的恶意数据、非法数据等应能进行修订，以便及时消除所产生的数据安全缺陷和风险。但是，在实际应用中，矿工在生成区块时无法对数据内容进行识别，使错误、非法数据很容易被写入区块链，而区块链的不可篡改性使这些错误、非法数据永久存储在区块链上，带来潜在的数据安全风险。为解决区块链上数据的不可篡改性与数据监管之间的矛盾，学者提出了可编辑区块链的概念，这一概念于近年来得到不断研究和发展。文献3系统梳理了可编辑区块链的现实需求和工作框架，以及相关的技术与方法。相较于基于硬分叉、节点共识投票等方式的可编辑区块链，使用变色龙哈希（CH,chameleon hash）函数4构建的可编辑区块链具有代价小、效率高等优势，也是目前构建可编辑区块链的主流方式。这主要得益于 CH 具有陷门这一特殊性质，即可以在不改变哈希值的情况下，使用陷门改变哈希函数的输入，同时对于非陷门持有者而言，CH 与标准哈希函数一样具有抗碰撞性。基于 CH 的可编辑区块链方案由 Ateniese 等5提出，该方案在区块层面使用 CH 代替原来的哈希函数 SHA-256，使陷门持有者能够编辑区块而不会中断区块间的链接。文献6提出了一种基于策略变色龙哈希（PCH,policy-based chameleon hash）的可编辑区块链，通过采用基于密文策略属性的加密（CP-ABE,ciphertext-policy attribute-based encryp-tion）来加密陷门信息，实现了更细粒度的事务层面的可编辑性。文献7在文献6基础上增加了黑盒问责机制，解决了由属性策略的匿名性所带来的无法查找恶意编辑者的问题。但是，上述可编辑区块链方案均不具备陷门撤销的功能。在实际应用中，CH 陷门持有者可能会滥用编辑权力，进而影响整个系统的安全性、声誉和鲁棒性。为此，文献8提出了可撤销的 PCH 方案，使被撤销的用户无法再解密获得陷门。文献9通过分别设置用户组和管理员组的访问策略，使满足管理员组策略的用户能够撤销用户组策略的用户对陷门的访问权限，且撤销的同时修改了陷门信息。文献10-11使用双线性映射来构造 CH 函数，同样实现了陷门撤销和修改的功能。但是，文献10中的方案存在陷门暴露问题，即敌手能够通过观察多组碰撞恢复出陷门；文献11中的方案对其进行了改进，通过在每次计算碰撞后立即撤销陷门来防止陷门暴露。文献12使用 2 个 CH 函数的嵌套结构实现陷门撤销，同时设置了半可信的监管机构撤销恶意编辑用户的陷门。支持陷门撤销的可编辑区块链方案虽在一定程度上限制了编辑权限的滥用，但陷门持有者仍可在陷门被撤销前执行多次编辑操作，甚至可以先将数据修改为恶意数据，再修改回来，在缺乏监管或监管机构疏忽的情况下避免陷门被撤销。针对此问题，文献13提出了一次变色龙哈希函数，实现了限制编辑次数为一次的可编辑区块链。文献14提出了支持 k 次编辑的可编辑区块链方案，并给出了编辑次数超过 k 次时的惩罚机制。但是，上述支持编辑次数限制的方案均不具备陷门可撤销性，无法解决陷门暴露后被滥用的问题。为实现可编辑区块链中细粒度的编辑权限管理，本文提出了一个同时支持陷门撤销和编辑次数限制的可编辑区块链方案，该方案能及时撤销陷门并严格限制编辑次数，且通过保留编辑历史实现了对恶意编辑者的问责。具体而言，本文的主要贡献如下。1)提出了编辑次数限制的变色龙哈希（RCHLR,revocable chameleon hash with limited number of redac-tions）函数的概念。RCHLR 使用双陷门结构，即主陷门和从陷门，其中，主陷门用于更改从陷门，而从陷门被限制了使用次数。此外，基于双线性映射给出了 RCHLR 的具体构造。2)基于 RCHLR 提出了新的可编辑区块链方案，并通过令数据所有者、矿工、监管机构协作运行 RCHLR 实现三者之间的相互监督，使任何单一实体都无法独立完成编辑，避免了单一实体编辑权力过大的问题。此外，通过监管机构发布的见证交易记录编辑历史，区分某个事务是否被编辑过以及被哪个实体编辑过，实现了对恶意编辑者的问责。3)严格证明了所构造的RCHLR方案满足特定的安全属性。与已有支持陷门撤销的方案相比，所提方案在安全性能上具有优势，且通过实验分析验证了其实际可用性。102 通 信 学 报 第 44 卷 1 预备知识 1.1 变色龙哈希 定义在消息空间的变色龙哈希函数由以下5 个算法组成。ppSetup()。参数生成算法Setup输入一个安全参数，输出系统参数pp，并假设pp为其他算法的隐式输入。(tk,hk)KGen(pp)。陷门生成算法KGen以系统参数pp作为输入，输出陷门与公钥(tk,hk)。(,)Hash hk,h rm()。哈希算法Hash输入公钥hk和消息m，输出哈希值h，以及随机字符串r。0,1Verify(hk,(,)h m r。验 证 算 法Verify是确定性算法，输入公钥hk，以及一个包含哈希值h、消息m和随机字符串r的三元组，检查(,)h r是否与消息m匹配，匹配则输出1，否则输出0。Adapt(tk,(,),)rh m r m。修改算法Adapt输入陷门tk，一个包含哈希值h、消息m和随机字符串r的三元组，及新消息m，输出一个新随机字符串r。1.2 双线性映射 设1、2和T是素数阶为q的乘法循环群。e是线性映射，12:Te，满足下述性质。双线性。对于任意1g，2h，,qa b，有(,)=(,)ababe ghe g h。非退化性。存在1、2群中的2个元素,p q，使(,)1e p q。可计算性。对于任意1、2群中的2个元素,p q，存在有效的算法计算(,)e p q。1.3 困难问题假设 设g是一个具有大素数阶q的乘法循环群的生成元，则有以下困难问题成立。离散对数问题（DLP,discrete logarithm prob-lem）。给定ag，其中*qa，计算a是困难的。计算迪菲赫尔曼（CDH,computational Dif-fie-Hellman）问 题。给 定,abg gg，其 中*,qa b，计算gab是困难的。可分计算迪菲赫尔曼15（DCDH,divisible computational Diffie-Hellman）问题。给定g,ga,gb ，其中*,qa b，计算abg是困难的。1.4 数字签名 一个数字签名方案包括以下4个算法。ppSetup()。输入一个安全参数，输出系统参数pp。(sk,pk)KGen(pp)。输入系统参数pp，密钥对生成算法KGen输出一个公私密钥对(sk,pk)。Sign(sk,)m。输入sk和m，签名算法Sign输出一个签名。0,1Verify(pk,)m。输入pk、消息m和签名，如果为有效签名，则验证算法输出1，否则输出0。1.5 伪随机数生成器 伪随机数生成器G是将随机输入扩展到更长伪 随 机 数 输 出 的 函 数。对 于:0,1nnG 0,1,b,n b n，若任意多项式时间敌手的区分字符串()(0,1)nncGxx和一个b位的随机字符串的优势是可忽略的，则称G是一个安全的伪随机数生成器16。2 陷门撤销和编辑次数限制的变色龙哈希 2.1 形式化定义 RCHLR采用双陷门结构，使用主陷门撤销从陷门，同时利用一个辅助见证信息实现编辑次数限制。相比于传统的CH函数，RCHLR新增了以下3个算法：用于撤销旧从陷门并输出新从陷门和见证的Update算法、用于验证Update算法输出结果正确性的Preedit算法、用于验证见证和碰撞值是否匹配以及实现从陷门编辑次数限制的Forge算法。具体而言，RCHLR的形式化定义如下。ppSetup()。参数生成算法Setup输入安全参数，输出系统参数pp，并假设pp为所有其他算法的隐式输入。(mtk,hk)KGen(pp)。陷门生成算法输入系统参数pp，生成主陷门mtk和公钥hk，输出变色龙哈希主陷门对(mtk,hk)。,Hash hk,CIDh rm。哈希算法Hash输入公钥hk、消息m、自定义身份CID，输出哈希值h和一个随机字符串r。0,1Verify(hk,(,)h m r。验 证 算 法Verify输入公钥hk，及一个包含哈希值h、消息m和随机字符串r的三元组，如果(h,r)有效，则输出1；否则输出0。第7期 陈越等：支持陷门撤销和编辑次数限制的可编辑区块链 103 ,tk,wtxUpdate(,),*,mtk)rh m r m。陷门更新算法Update输入主陷门mtk、三元组(,)h m r、新消息*m，输出新随机字符串r、从陷门tk和见证wtx。0,1Preedit(hk,(,),wtx)h m r r。预编辑算法Preedit输入公钥hk、三元组(,)h m r、新随机字符串r、见证wtx，若(,wtx)r有效则输出1，否则输出0。Adapt(tk,(,),)rrh m rm。修 改 算 法Adapt输入从陷门tk、三元组(,)h m r、新消息m，输出新随机字符串r。0,1Forge(hk,(,),(,),wtx)h m rh,m r。编辑算法Forge输入公钥hk、三元组(,)h m r和(,)h m r以及见证wtx，若(,wtx)h m r有效则输出1，否则输出0。2.2 安全性定义 本节根据文献12给出RCHLR的安全模型，并额外定义了从陷门一次编辑性，用于严格限制编辑次数为一次。从主、从陷门抗碰撞性的实验可知，实验允许敌手查询多组碰撞，若满足主、从陷门抗碰撞性，则解决了陷门暴露的问题。定义 1 安全的RCHLR。若一个RCHLR方案满足正确性、可撤销性、主陷门抗碰撞性（MTCR,master trapdoor collision resistance）、从陷门抗碰撞性（STCR,subordinate trapdoor collision resistance）和从陷门一次编辑性（STOR,subordinate trapdoor one-time redaction），则称它是安全的。2.2.1 正确性 一方面，正确性要求所有通过Hash、Adapt或Update算法正确生成的哈希值/随机字符串对都可以通过Verify的验证。另一方面，正确性还要求Update算法正确运行的输出结果都可以通过Preedit算法；Adapt算法将Update算法的输出结果作为输入，并编辑预定的消息，其输出结果都可以通过Forge算法。RCHLR的正确性实验如下。CORR,RCHLRExp():ppSetup();(mtk,hk)KGen(pp);CID0,1*;wtx;Trapdoor:;rrm(,)Hash(hk,CID);Mhash:(,);h rmh m r Mpreedit:;Mforge:;Signal:continue;UpdateAdapt,Signal(hk);if Signal Stop,Parse Mhash:(,*,*);h mr 1Verify(hk,*,*);bh m r 1if Mpreedit,return;b 2else Preedit(hk,Mpreedit);b 12if Mforge,return;bb 3else Forge(hk,Mforge);b 123return.bbb end if end if end if Update(,)():mtk hkm Parse Mhash:(,);h m r(,tk,wtx)Update(mtk,(,),);rh m r m Trapdoor:tk;Mpreedit:(,wtx);h m r r Mhash:(,);h m r Adapt(Trapdoor,hk)():m if Trapdoor,return;else Parse Mhash:(,);h m r if,mm Adapt(tk,(,),);rh m rm Mforge:(,wtx);h m r m r Mhash:(,);h m r else Adapt(tk,(,),);rh m rm Mhash:(,);h m r end if end if 正确性实验中，变量(Trapdoor,Mhash,Mpreedit,Mforge)通过的查询而改变。当Trapdoor时，不允许进行Adapt询问。一旦完成了查询，实验就结束。CORR,RCHLRExp()将检查(Mhash,Mpreedit,Mforge)变量的有效性，有效则输出1，否则输出0。2.2.2 可撤销性 可撤销性要求拥有主陷门的一方可以撤销从陷门拥有者查找某个哈希值碰撞的能力。可撤销性实验如下。Revoke,RCHLRExp():ppSetup();(mtk,hk)KGen(pp);tk;wtx;Update(tk*,(*,*,*),*)(hk);hmrm if Verify(hk,*,*,*)0tk*tk*h m r not match(*,*,*),return;h m r else(*,tk*,wtx*)Update(mtk,(,*,*),*);rh m rm if tk*tk*,return 1.104 通 信 学 报 第44卷 end if end if Update(mtk,hk)(,),):h m r m if Verify(hk,)0,return;h m r else(,tk,wtx)Update(mtk,(,),);rh m r m tk;return(,tk,wtx).r end if 可撤销性实验允许敌手在多项式时间内对Update多 次 查 询，并 在 最 终 输 出 调 整 信 息(tk*,(*,*,*),*)h m rm。Revoke,RCHLRExp()检查三元组(*,*,*)h m r的正确性以及tk*是否与之匹配，并运行Update算法输入撤销从陷门。若生成的新旧陷门相同则输出1，否则输出0。2.2.3 主陷门抗碰撞性 主陷门抗碰撞性有两层含义：1)非主陷门的持有者不能生成任何有效的新从陷门；2)非主陷门的持有者不能执行Update算法产生碰撞，生成新随机字符串和见证。在主陷门抗碰撞性中，消息m作为固定的参数，在碰撞前后不发生改变。作为代替，发生改变的将是从陷门，新从陷门tk根据m生成。主陷门抗碰撞性实验如下。MTCR,RCHLRExp():ppSetup();(mtk,hk)KGen(pp);tk;wtx;Update(*,*,*,tk*,*,wtx*)(hk);hmrr if Verify(hk,*,*,*)0tk*tk*h m r not match(*,*,*),return;h m r else if Preedit(hk,*,*,*,*,wtx*)=1,return 1;h m r r else return 0.end if end if Update(mtk,hk)(,),):h m r m if Verify(hk,)=0,return;h m r else(,tk,wtx)Update(mtk,(,),);rh m rm tk;return(,tk,wtx).r end if 如果多项式时间敌手在MTCR,RCHLRExp()中能够生成有效的新从陷门或碰撞，则输出1，否则输出0。2.2.4 从陷门抗碰撞性 从陷门抗碰撞性要求非从陷门持有者在hk下不能发现任何碰撞。从陷门抗碰撞性实验如下。STCRRCHLR,Exp():ppSetup();(mtk,hk)KGen(pp);tk;wtx;Adapt(*,*,*,*,*)(hk);hmrmr if Verify(hk,*,*,*)Verify(hk,*,*,*)h m rh mr 1*,mmmreturn 1.end if Adapt(tk,hk)(,),):h m r m if Verify(hk,)1,return;h m r else Adapt(tk,);rh m r m if,return;r else ,return.m mr end if end if 如果多项式时间敌手在STCR,RCHLRExp()中能够生成有效的新碰撞，则输出1，否则输出0。2.2.5 从陷门一次编辑性 从陷门的一次编辑性要求主陷门持有者通过Update算法生成的从陷门仅能在某个哈希值下对预给定的消息发生一次编辑，编辑其他消息将不被接受。从陷门的一次编辑性实验如下。STOR,RCHLRExp():ppSetup();(mtk,hk)KGen(pp);wtx;tk;Mforge:(,);Update(,)(hk);m r Parse Mforge:(,wtx);h m r m if Forge(hk,wtx)1,mmh m r m r return 1.end if Update(mtk,hk)(,),):h m r m if Verify(hk,)1,return;h m r else(,tk,wtx)Update(mtk,(,),);rh m rm Mforge:(,wtx);h m r m return(,tk,wtx).r end if 如果多项式时间敌手在STOR,RCHLRExp()输出的(,)m r能够通过Forge算法，则输出1；否则输出0。第7期 陈越等：支持陷门撤销和编辑次数限制的可编辑区块链 105 2.3 具体构造 本节给出RCHLR的具体构造。ppSetup()。Setup算法输入安全参数，选择阶为q、生成元为g的乘法循环群和T，设置双线性映射:Te。选择哈希函数*12:0,1,:0,1qHH，安全伪随机数生成器G，输出12pp(,)Tg q e HHG，并将pp作为其他算法的隐式输入。(mtk,hk)KGen(pp)。密 钥 生 成 算 法KGen输 入系 统 参 数pp，选 择3个 随 机 数*12,etdrqrqrqxx，其中，12etdxx，计算etd12,xxggg。运行KGen(pp)生成签名密钥对(sk,pk)，令公钥etd12hk(,pk)xxggg，主陷门12mtk(,x xetd,sk)，输出(mtk,hk)。(,)Hash(hk,CID)h rm。Hash算法输入公钥hk，消息*0,1m，自定义身份CID，选择随机数*,q，计算,gg。令Mh，计算 211(,(CID|)HmxMhe gHh2etd(,)(,)xe gge gg和随机字符串(,CID)Mrggh，输出(,)h r。0,1 Verify(hk,)h m r。Verify算法输入公 钥etd12hk(,pk)xxggg、哈 希 值h、消 息*0,1m、随机字符串(,CID)Mrg g h，检查 2121(,(CID|)(,)HmxxMhe gHhe ggetd(,)e gg是否成立，若是则输出1，否则输出0。(,tk,wtx)Update(,),mtk)rh m r m。Update算法输入三元组(,)h m r、新消息m、主陷门12mtk(,etd,sk)x x，随机字符串(,CID)Mrggh，其中h为哈希值。首先，验证Verify(hk,)h m r是否为1，为1则继续运行算法，否则输出。生成Merkle树M的结构如图1所示。根哈希值为Mh，其叶子节点从左至右依次为伪随机数生成器G生成的2个随机数Nonce1和Nonce2、哈希值2()Hm、自定义身份CID*。计算签名Sign(sk,(,)Mh h和11(CID|)Mgg HhH()211etd(CID*|)Hm xMh，输出,tk,wtxr。其中，见证wtx(,)MhhM，从陷门112tk(CID*|),)xMHhx，新 随 机 字 符 串(,CID*)Mrggh。0,1Preedit(hk,),wtx)h m r r(。Preedit算法输入公钥hk、三元组(,)h m r、新随机字符串(,CID*)Mrggh、见证wtx(,)MhhM。检查是否有Verify(hk,)1h m r，检查签名验证算法是否有Verify(pk,(,)1Mh h，检查三元组与见证wtx中的h值是否相等，检查见证wtx中的Mh是否为M的根哈希值且与r中的Mh相等，检查r与M中的CID*是否相等，若都满足则输出1；否则输出0。图1 Merkle树M的结构 Adapt(tk,(,),)rrh m rm。Adapt算法输入 从 陷 门112tk(CID*|),)xMHhx、三 元 组(,)h m r和 随 机 消 息*0,1m，其 中(,CID*)Mrggh。检 查 验 证 算 法Verify(hk,)h m r是否为1。计算12()()221(CID*|)xHmHmxMgg Hh，输出随机数=(,CID*)Mrggh。0,1Forge(hk,(,),(,),wtx)h m rh m r。Forge算法输入公钥hk、三元组(,)h m r和(,)h m r、见证wtx。检查是否有Verify(hk,)1h m r，检查2个三元组与见证wtx中的h值是否相等，检查见证wtx与rr、中的Mh是否相等，检查2()Hm与M中的2()Hm是否相等，若上述4个检查都满足则输出1，否则输出0。2.4 安全性证明 本节依次证明上述RCHLR方案的正确性、可撤销性、主陷门抗碰撞性、从陷门抗碰撞性和从陷门一次编辑性。2.4.1 正确性 根据安全模型中正确性的定义，意味着根据Hash、Update和Adapt算法的输出结果可以重构哈希值h。对于随机字符串(,CID)Mrggh和消息m，正确性证明如下。1)由公钥etd12hk=(,pk)xxggg，使用Hash算法的输出结果显然可以重构h。106 通 信 学 报 第44卷 2)取Update算法输出结果，消息m和随机字符串(,CID*)Mrggh。计算h如下。21()1etd11(CID|)(CID*|)(1)Hm xMMggHhHh12212221122()etd1()etd1()111()etd1(,(CID*|)(,)(,)(,(CID*|)(,)(,)(CID|)(CID*|),)(CID|)(,)(,)(2)xHmxMxHmxMHm xMMxHmxMhe gHhe gge gge gHhe gge gge HhHhge g,Hhe gge ggh 3)Adapt算法输出(,CID*)Mrggh，消息m。计算h如下。1222()()1(CID*|)xHmHmxMgg Hh(3)1222212222122()1etd()11()()etd1()1etd(,(CID*|)(,)(,)(,(CID*|)(,)(,)(CID*|),(,(CID*|)(,)(,)xHmxMxHmxMxHmHmxxMxHmxMxhe gHhe gge gge gHhe gge gge Hhge gHhe gge gge g122122()()1()1(CID*|)(,(CID*|)(,)HmHmMxHmxM,Hhe gHhe gg etd(,)e gg (4)另一方面，Update算法正确运行的输出结果显然都可以通过Preedit算法；对于Forge算法，由于要检查2()Hm与M中的2()Hm是否相等，则Adapt算法除了将Update算法输出结果作为输入外，必须编辑新消息m才能通过验证，m即预定消息，因此若编辑m则必定通过Forge算法。证毕。2.4.2 可撤销性 引理 1 假设H是满足抗碰撞性的哈希函数，G是一个安全的伪随机数生成器，则对于相同的消息m和自定义身份CID输入，Merkle树M的根哈希值hM也不相同。证明 设2,0,1,:0,10,1nn2nnG，生成2个n位的随机数212()|Grr，Merkle树M叶子节点从左至右依次为r1、r2、H2(m)和CID，中间节点为12(|)H rr、2()|CID)H Hm，根哈希值为hM，即使选择相同的m和CID，由于r1和r2不同，得到的根哈希值也不同，否则就会攻击H的抗碰撞性。证毕。定理 1 假设H1和H是满足抗碰撞性的哈希函数，G是一个安全的伪随机数生成器，则满足可撤销性。证明 在挑战者与敌手、敌手的博弈中证明上述定理。假设存在一个多项式时间敌手能有效对抗可撤销性，则能构造一个敌手利用的输出结果攻击哈希函数H1的抗碰撞性，允许查询Update的次数为poly()q。挑战者输出满足抗碰撞性的哈希函数*1:0,1H给。使用H1构建RCHLR并像可撤销性实验一样设置初始参数。查询阶段。允许查询Update，将输出的第i次查询结果(,tk,wtx)iiir给，0,iq，并创建表存储tki。挑战阶段。输出(tk*,(*,*,*),*)h m rm给，检查(*,*,*)hmr的正确性，检查tk*是否为(*,*,*)hmr的从陷门且在表中，若通过则运行Update算法，输入(*,*,*),*hmrm生成新从陷门tk*。不失一般性，令*=(,CID*)Mrggh，12tk*(tk,tk)112(CID*|),)xMHhx。通过判别Verify(hk,*,*,*)h m r检查(*,*,*)h m r的正确性。通过判断22(*)(*)111*(,tk)(,(CID*|)HmxHmMe ge gHh是否成立来检查tk*是否为(*,*,*)h m r的从陷门。生成从陷门tk*时，生成Merkle树*M，左侧叶子节点为伪随机数生成器G生成的随机数，右侧2个节点为2(*)Hm和自定义身份CID*，根哈希值为*Mh，从陷门11*2tk*=(CID*|),)xMHhx。输出1*(CID*|)MHh、1*(CID*|)MHh给挑战者。一旦具有不可忽略的概率赢得挑战，则挑战中新旧从陷门相等，由于tk2的部分不变，将得到2个相等的哈希值。注意，允许CID*与CID*相等，且允许在挑战中使用查询过的*m，但由引 理1可 知，对得 到 的2个 哈 希 值1*1*(CID*|)(CID*|)MMHhHh，即使输入相同的m和CID，得 到 的hM也 不 相 同。因 此*CID*|CID*|MMhh，破坏H1的抗碰撞性赢得挑战，与在游戏中取胜的优势相同。证毕。2.4.3 主陷门抗碰撞性 主陷门抗碰撞性包含2个部分，即要求非主陷门的持有者不能生成任何有效的新从陷门，要求非第7期 陈越等：支持陷门撤销和编辑次数限制的可编辑区块链 107 主陷门的持有者不能产生新的碰撞。因此，证明也分为2个部分。引理 2 如果存在多项式时间敌手能够生成有效的新从陷门，则能构建敌手破坏CDH困难假设。证明 在以下游戏中证明安全性。游戏 0 与主陷门抗碰撞性实验定义的游戏相似，但系统参数为c2(,)Tg q e q HG，其中，H1被替代为c*q，不存在Update查询，敌手赢得挑战的条件是输出正确的从陷门1cxq。游戏 1 与主陷门抗碰撞性实验定义的游戏相似，敌手赢得挑战的条件是输出一个不在表中的有效从陷门。现将游戏1规约到游戏0。为了简化，不失一般性，假设不会对1()H 发起两次相同的询问；如果请求CID|hM的从陷门查询，则它之前已经查询过H1(CID|hM)，此外，不考虑查询Update得到的碰撞值和见证，因为生成陷门与生成碰撞和见证是独立的。挑战者建立游戏0的方案，将系统参数c2(,)Tg q e q H G 和公钥12etd(,)xxggg给，模拟在游戏1中的挑战者，将系统参数12(,)Tg q eH HG和 公 钥12etd(,)xxggg给，由于没有H1，构造一个H1列表list1H存储iMiiihq b，允许查询H1的次数为1Hq，随机选择一个猜测值11,Hjq，此次对H1的查询对应在挑战时的攻击结果，允许查询从陷门的次数为q。H1查询阶段。如果CID|iMih已经在list1H中，以*iq 作为H1的值应答；否则选择随机数*iqb。若i=j，计算c=biiqq，若ij，计算=biiqg。将iMiiihq b加入list1H，并将iq作为H1的值应答。从陷门查询阶段。若i=j，无法利用；否则从list1H中取出biiqg，计算1b xig作为对应的从陷门给，并将1b xig记录在表中。挑战阶段。输出CID|iMih对应的从陷门11(CID|)xiMiHh，且不在表中。若ij，无法利用；否则，从陷门11(CID|)xiMiHh1cb xiq。计算111cc()b xbxiiqq，输出1cxq给。在以上规约过程中，若猜测正确且不中断，的视图与真实攻击中是同分布的。因为的1Hq次查询都以随机数应答，由于ib的随机性，iq也是随机的，且与H1的结果同分布；在q次查询中得到的从陷门有效。因此若猜测正确且不中断，以不可忽略的优势赢得游戏1，就成功赢得了游戏0，猜测正确概率为11Hq，不中断从陷门查询的概率为111qHq，不中断挑战的概率为11111qHHqq，因此赢得游戏0的概率为11111qHHqq。下面将游戏0规约到CDH问题。使用CDH实例(g,ga,gb)构建游戏0，令c=bqg,1=xagg，若以不可忽略的优势赢得游戏0，输出1cxq作为gab破坏CDH困难假设。在上述证明中，没有考虑x2，因为敌手可以在游戏1的任意一次查询得到，此外在游戏0中输出正确的从陷门与x2无关。证毕。引理 3 如果存在多项式时间的敌手能够产生新的碰撞，则能构建敌手破坏DCDH困难假设。证明 在以下游戏中证明安全性。游戏 0 与从陷门抗碰撞性实验定义的游戏相似，但系统参数为c2(,)Tg q e qHG，其中c*q 替代H1，1xg替换为g，无Update查询，敌 手 赢 得 挑 战 的 条 件 是 输 出 有 效 碰 撞(*,*,*,hmm*,*)rr。游戏 1 与主陷门抗碰撞性实验定义的游戏相似，允许敌手在Update中查询碰撞和从陷门，用表存储查询得到的从陷门，敌手赢得挑战的条件是输出一组有效碰撞，且表中不含有碰撞值对应的从陷门。现将游戏1规约到游戏0，为了简化，不考虑见证wtx。不失一般性，假设不会对1()H 发起两次相同的询问；如果使用CID|hM构建哈希值h，则它之前已经询问过H1(CID|hM)。挑战者建立游戏0的方案，将系统参数c2(,)T