一种去中心化且可追责的可编辑区块链方案

A Decentralized and Accountable Redactable Blockchain Scheme

摘要

区块链具有不可修改特性，能永久保存链上数据的同时，也导致了链上的有害数据无法删除、错误数据无法更新。已有的可编辑区块链研究实现了区块链数据可编辑的功能，但是存在编辑权力中心化的问题，这与区块链去中心化的理念不符。同时，现有方案在验证编辑区块时，存在无法追责的问题。为此，提出了一种去中心化且可追责的可编辑区块链方案。该方案设计了去中心化的变色龙哈希函数，通过多个用户节点协同生成变色龙哈希陷门，以实现去中心化的方式管理陷门。增加随机选择阶段和对编辑节点的审查追责阶段，实现对编辑权力的可控监管。对本方案进行了安全性分析，分析结果表明该方案兼具可编辑性和可行性，并以各个阶段的算法运行时间为评估指标，与现有可编辑区块链方案进行了对比实验，实验结果表明该方案具有比较好的运行效率。

Abstract

The blockchain is immutable and can permanently store data on the chain, but it also prevents harmful data from being deleted and incorrect data from being updated. Existing redactable blockchain schemes endow the blockchain with the function of data editing. However, the existing research has the problem of centralizing of editing power, which violates the idea of blockchain decentralization. At the same time, the existing schemes have an accountability problem when verifying the edited block. To this end, a decentralized and accountable redactable blockchain scheme is proposed. In this scheme, a decentralized chameleon Hash function is designed to generate chameleon Hash trapdoors through multiple user nodes to manage trapdoors in a decentralized manner. A random selection stage and a review and accountability stage for editing nodes are added to achieve controllable supervision of editing rights. A security analysis of this scheme is conducted, and the analysis results show that the scheme is both editable and feasible. The algorithm running time of each stage is used as the evaluation index, and the comparison experiment is conducted with the existing redactable blockchain scheme, the experimental results show that the scheme has better running efficiency.

Graphical abstract

关键词

可编辑区块链 / 去中心化 / 变色龙哈希 / 密钥管理

Key words

redactable blockchain / decentralization / chameleon Hash / key management

0　 引 言

区块链技术在2008年由中本聪首次提出^[1]，被看作是一种去中心化、不可更改的分布式账本技术。在近些年来，区块链的相关技术和产业应用始终保持着快速的发展，引起了全球的广泛关注，相关的应用也扩展到了金融、医疗和政务等诸多领域。但是，由于区块链的不可更改特性，使得区块链在实际应用的过程中存在一些问题。

首先，对于现有的无许可区块链，如比特币和以太坊区块链系统，交易数据在存储到区块链之前没有经过审计和过滤，一些恶意用户就会在链上存储有害或者敏感的非法信息，包括被盗取的私钥以及不当链接和视频等等；而链中的非法信息由于不可修改，会导致个人隐私数据的泄漏，甚至会对产业组织的数据安全造成威胁，降低相关组织和用户使用区块链的意愿，在一定程度上制约区块链的发展。其次，欧盟出台的通用数据保护条例（General Data Protection Regulation，GDPR）中指出用户享有数据的遗忘权（right to be forgotten），即用户在符合条件的情况下，有权利编辑和删除他们自己的数据^[2]，这一要求与区块链的不可修改特性相互冲突。最后，出于对区块链数据监管和数据更新方面的考虑。在现实场景中区块链用户不可避免地会产生错误或事故，导致错误的信息数据被永久存储到区块链上，随着时间的推移，这些无法更新的链上陈旧数据和错误信息会增加企业的维护成本，不利于区块链系统的长期使用和发展。

由于区块链在数据更新、信息监管等方面存在切实的编辑需求^[3]，因此，2017年，Ateniese等^[4]首次提出基于变色龙哈希函数（chameleon Hash function）的可编辑区块链的研究方案。随后可编辑区块链的相关研究在近些年来有了一系列的进展，这些研究根据编辑权限设置的不同可以分为中心化和去中心化两类。在中心化设置的可编辑区块链方案中^[5~7]，只有单个节点管理变色龙哈希陷门，存在编辑权过于集中化的问题。如果管理节点被攻击，那么陷门的安全就无法得到保障，并且中心化的节点本身可能是不诚实的节点，存在恶意修改区块链交易的风险。此外，在实际应用场景中，中心化的节点会有离线的可能，这也会影响区块编辑功能的使用和效率。在去中心化设置的可编辑区块链方案中^[4，8，9]，主要是将陷门的管理权限分发给不同的节点，每个节点掌握部分陷门信息，由这些节点共同管理陷门，但这类方案没有考虑到区块链动态节点特性和陷门密钥泄露，验证编辑和节点达成一致的时间较长且效率较低，投票期过长，难以在实际生产中使用。

综上所述，现有的可编辑区块链方案存在以下问题：首先，过于依赖中心化的陷门管理者的信誉，且在已有的去中心化的方案中也都依赖一个可信的陷门分发中心，违背了区块链本身的去中心化原则；其次，在区块链的实际应用场景中，存在节点动态加入和退出区块链的情况，没有考虑到动态区块链节点对持有陷门份额的影响；最后，现有工作缺少对于恶意编辑的节点的审查和追责。

为解决上面的问题，本文提出去中心化且可追责的可编辑区块链方案。通过设计去中心化的变色龙哈希算法实现去中心化的方式管理陷门，在该算法中，陷门密钥是由多个区块链节点协作生成，无须依赖可信的陷门分发中心；基于区块链系统节点的动态特性，进一步扩展了变色龙哈希函数，增加密钥分享更新阶段，解决动态节点的密钥分享问题；通过随机选择的方式选出编辑者，并设计验证追责阶段，降低编辑者作恶的可能性。

1　 基础知识

1.1　变色龙哈希函数

变色龙哈希函数，也叫陷门哈希函数，是一种特殊的单向陷门函数。当陷门未知时，变色龙哈希函数与传统哈希函数一样，都具有抗碰撞性，即无法找到不同的数据输入使得哈希值相同；而当陷门已知时，则可以通过简单计算轻松找出碰撞。

变色龙哈希函数由5个算法组成，可以表示为\mathrm{C}{\mathrm{h}}_{\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}}=(\mathrm{P}\mathrm{P}\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n},\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h},\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y},\mathrm{A}\mathrm{d}\mathrm{a}\mathrm{p}\mathrm{t})，算法描述如下：

1) \mathrm{p}\mathrm{p}\leftarrow \mathrm{P}\mathrm{P}\mathrm{G}\mathrm{e}\mathrm{n}(\lambda )：安全参数\lambda为输入，公共参数\mathrm{p}\mathrm{p}为输出。

2) (\mathrm{H}\mathrm{K},\mathrm{C}\mathrm{K})\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{p})：公共参数\mathrm{p}\mathrm{p}为输入，公私钥对(\mathrm{H}\mathrm{K},\mathrm{C}\mathrm{K})为输出，其中\mathrm{H}\mathrm{K}为公钥，\mathrm{C}\mathrm{K}为私钥（也被称为陷门）。

3) \mathrm{C}\mathrm{H}\leftarrow \mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}(\mathrm{H}\mathrm{K},m,r)：公钥\mathrm{H}\mathrm{K}、消息m和随机数r为输入，变色龙哈希值\mathrm{C}\mathrm{H}为输出。

4) b\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{H}\mathrm{K},m,r,\mathrm{C}\mathrm{H})：消息m、随机数r、公钥\mathrm{H}\mathrm{K}和变色龙哈希值\mathrm{C}\mathrm{H}为输入，比特值b为输出。如果b的值为1，则验证通过，\mathrm{C}\mathrm{H}值为有效的哈希值；否则验证不通过。

5) r\text{'}\leftarrow \mathrm{A}\mathrm{d}\mathrm{a}\mathrm{p}\mathrm{t}(\mathrm{C}\mathrm{K},m,r,m\text{'})：私钥\mathrm{C}\mathrm{K}、消息m，随机数r和另一个消息m\text{'}为输入，新随机数r\text{'}为输出；其中，新随机数r\text{'}满足\mathrm{C}\mathrm{H}=\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}\left(\mathrm{H}\mathrm{K},m,r\right)=\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}(\mathrm{H}\mathrm{K},m^{\text{'}},r\text{'})。

1.2　可验证秘密共享

在秘密共享协议^[10]中，把秘密分成w份子秘密，至少获得门限值c份（）才能恢复出秘密，否则无法恢复出秘密。一般地，秘密共享协议有秘密分发和秘密恢复两个阶段。其中，协议要求秘密分发者以及子秘密持有方都要诚实可信。但是在实际情况下，基于“所有成员都是诚实的”这一点难以得到保证，一方面，秘密分发者可能不诚实导致不能正确分发秘密；另一方面，子秘密持有者也可能不诚实从而提供假的份额导致无法恢复出秘密。

针对上述问题，可验证秘密共享^[11]（Verifiable Secret Sharing，VSS）随之提出，VSS在普通的秘密共享协议中增加了验证算法，使得所有子秘密持有者都能验证收到子秘密的正确性，其可以检测出不诚实的参与方成员（包括秘密分发者以及参与者）。可验证秘密共享一般由以下三个阶段组成：

1) Share秘密分发算法。分发者将秘密\mathrm{S}\mathrm{e}\mathrm{c}分成w份子秘密，通过安全信道分发给w个参与者，相应参与者可以计算子秘密的承诺值并公开。

2) Verify共享验证算法。参与者验证收到的子秘密和承诺值，从而确保自己收到的子秘密的有效性。

3) Recover秘密恢复算法。参与者收集到超过门限值c的正确的子秘密时，可以通过秘密恢复算法恢复出秘密\mathrm{S}\mathrm{e}\mathrm{c}。

2　 方案设计

2.1　方案模型

去中心化且可追责的可编辑区块链方案包含用户节点、编辑者和监管者三类角色。

1） 用户节点：该角色是区块链系统的主要参与者，维持着区块链系统的正常稳定运行，具有发起交易、打包区块和就区块数据达成共识的功能。在本文方案中，每个用户节点都会持有变色龙哈希陷门的分享，并依据陷门分享可以计算随机数分享。后文将“用户节点”简写为“节点”。

2） 编辑者：该角色是节点中的一个成员，是通过随机算法在节点中随机选择确定的，主要负责收集来自各个节点的随机数分享，并计算哈希碰撞随机数，对区块链交易数据执行编辑操作。

3） 监管者：区块链的监管人员，具有监管和追责的功能。

本文方案的模型框架如图1所示。主要流程如下：

1） 初始化阶段。n个节点协作生成变色龙哈希陷门，每个节点都持有一份陷门份额。

2） 分享更新阶段。当存在节点加入或者退出区块链时，需要对各个节点持有的陷门分享进行周期性更新。比如当区块链节点的数量减少至k_{\mathrm{1}}个节点时，将陷门密钥的份额分享更新给k_{\mathrm{1}}个节点；当区块链节点数量增加到k_{\mathrm{2}}个节点时，则将陷门密钥的份额分享更新给k_{\mathrm{2}}个节点。

3） 随机选择阶段。区块链系统存在编辑申请时，在所有节点中，通过随机算法选择出具有编辑功能的编辑者。所有节点根据自己持有的陷门份额计算随机数分享，这样做可以避免陷门在使用一次后，存在的密钥泄露问题。

4） 数据编辑阶段。编辑者收集超过门限值t的随机数分享，计算最终的哈希碰撞随机数，并对区块链数据进行编辑。

5） 审查追责阶段。节点对编辑后的区块链进行验证。若验证未通过，监管者介入，并对相应参与者进行追责。

2.2　去中心化的变色龙哈希函数

现有的可编辑区块链方案使用的变色龙哈希函数大都是基于中心化的设置，也就是存在有中心化的组织机构给节点分发变色龙哈希函数的陷门分享，这对于去中心化的区块链而言是不切实际的；此外，在现有的去中心化方案中，编辑者恢复出陷门编辑区块数据一次后，存在陷门泄露的问题。为解决上述问题，本文提出去中心化的变色龙哈希函数，该函数由多个节点共同生成变色龙哈希陷门，每个节点都持有陷门份额，当计算哈希碰撞时，由节点根据持有的陷门份额，计算哈希碰撞的随机数分享，编辑者只有收到超过门限值的随机数分享时，才能计算获得完整的哈希碰撞随机数，如此可规避陷门泄露的风险。

去中心化的变色龙哈希函数包含5个算法，算法具体描述如下：

1） \mathrm{p}\mathrm{p}\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{P}\mathrm{P}\mathrm{G}\mathrm{e}\mathrm{n}(\lambda )：参数初始化算法。输入安全参数\lambda后，经过处理后输出公共参数\mathrm{p}\mathrm{p}。其中，公共参数\mathrm{p}\mathrm{p}=\{G,p,g\}， G是p阶的有限乘法循环群，g是G群中的一个生成元，p是依赖于安全参数\lambda生成的大素数。

2） (\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{t-\mathrm{1}})\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{p}\mathrm{p})：变色龙哈希密钥生成算法，由t个节点通过t-\mathrm{1}次多项式协同生成。输入公共参数\mathrm{p}\mathrm{p}，经过处理后输出变色龙哈希函数的公私钥对(\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{t-\mathrm{1}})，其中公钥\mathrm{p}\mathrm{k}在系统中公开，私钥(\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{t-\mathrm{1}})分别由t个节点持有。变色龙哈希密钥生成的具体步骤如下。

步骤1：节点选择一个t-\mathrm{1}次的多项式，如（1）式所示：

f_i\left(x\right)=a_{\mathrm{0}}^i+a_{\mathrm{1}}^{i}x+\dots +a_{t-\mathrm{1}}^i{x}^{t-\mathrm{1}}（1）

其中，a_{\mathrm{0}}^i,a_{\mathrm{1}}^i,\dots a_{t-\mathrm{1}}^i都为随机选择的整数，x表示用户的身份信息。每一个节点通过此多项式可以得到t份中间值\left\{\left(j,f_i\left(j\right)\right){|}_{j=\mathrm{0}}^{t-\mathrm{1}}\right\}。

步骤2：t个节点将其中第i份中间值（经过处理后为(f_i(j),g^{f_i\left(j\right)},g^{a_{\mathrm{0}}^j})）分发给节点j。

步骤3：节点j可以验证中间值的正确性，并计算返回输出公钥\mathrm{p}\mathrm{k}=g^s\leftarrow {\displaystyle \prod _{j=\mathrm{1}}^t}{g}^{a_{\mathrm{0}}^j}（s表示变色龙哈希函数的陷门密钥，s={\displaystyle \sum _{j=\mathrm{0}}^{t-\mathrm{1}}}{a}_{\mathrm{0}}^j），以及密钥陷门分享\mathrm{s}{\mathrm{k}}_i={\displaystyle \sum _{j=\mathrm{0}}^{t-\mathrm{1}}}{f}_i(j)。

其余节点通过上述步骤可以获得各自对应的密钥陷门分享。

3） h\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}(m,r,\mathrm{p}\mathrm{k})：哈希算法。输入消息m、公钥\mathrm{p}\mathrm{k}以及随机数r，其中，随机数r由r=g^e（e\in Z_p）计算得到，该算法根据h=H\left(r,m,\mathrm{p}\mathrm{k}\right)=r\cdot \mathrm{p}{\mathrm{k}}^m=g^{e+s·m}输出哈希值h，其中，H:{\left\{\mathrm{0,1}\right\}}^{*}\to G^{*}是为抗碰撞哈希函数。

4） r\mathrm{\text{'}}\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{A}\mathrm{d}\mathrm{a}\mathrm{p}\mathrm{t}\left(\left(m,r\right),m\text{'},\mathrm{p}\mathrm{k},\right.\left(\mathrm{s}{\mathrm{k}}_{\mathrm{0}}\right.,\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\left.\left.\mathrm{s}{\mathrm{k}}_{t-\mathrm{1}}\right)\right)：碰撞生成算法。算法由持有分享的节点i执行，输入消息和随机数对(m,r)、公钥\mathrm{p}\mathrm{k}、每个节点的各自私钥\mathrm{s}{\mathrm{k}}_i以及需要修正的消息值m\text{'}后，节点i根据陷门分享计算所得出的随机数份额分享r_i^{\text{'}}=g^e\cdot g^{\left(m-m^{\text{'}}\right)·\mathrm{s}{\mathrm{k}}_i}。为方便描述，令e^{\text{'}}=e+\left(m-m^{\text{'}}\right)·\mathrm{s}{\mathrm{k}}_i，其中i\in (\mathrm{0,2},\dots ,t-\mathrm{1})。

5） b\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}\left(\mathrm{p}\mathrm{k},\left(m,r\right),(m^{\text{'}},r\text{'})\right)：哈希验证算法。输入公钥\mathrm{p}\mathrm{k}、原来的消息和随机数对\left(m,r\right)以及修改后的消息随机数对(m^{\text{'}},r\text{'})，通过验证新旧区块的哈希值g^e\mathrm{p}{\mathrm{k}}^m与g^{e^{\text{'}}}\mathrm{p}{\mathrm{k}}^{m^{\text{'}}}是否相等，输出一个比特值b。如果b的值为1，则验证通过；否则，验证不通过。

2.3　方案流程

本文去中心化且可追责的可编辑区块链方案流程包括以下5个阶段：

1） 初始化阶段：主要完成可编辑区块链系统的初始化，生成公共参数以及生成数字签名和变色龙哈希的公私密钥对。具体而言，系统中的每一个节点都需要通过数字签名算法生成用于签名和验证的公私钥对，同时，为确保变色龙哈希陷门无需陷门分发中心进行分发，实现去中心化，本文采用部分节点协同生成变色龙哈希陷门的方式，通过密钥再分享算法将陷门分发给区块链中的所有节点。假设区块链中共有n个节点，通过其中t个节点协作生成陷门，。因此，该阶段包含以下4个算法。

a) \mathrm{p}\mathrm{p}\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{P}\mathrm{P}\mathrm{G}\mathrm{e}\mathrm{n}\left(\lambda \right)：参数初始化算法。输入安全参数\lambda，经过计算后输出公共参数\mathrm{p}\mathrm{p}。

b) \left(\mathrm{D}\mathrm{S}.\mathrm{p}\mathrm{k},\mathrm{D}\mathrm{S}.\mathrm{s}\mathrm{k}\right)\leftarrow \mathrm{D}\mathrm{S}\_\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}\left(\mathrm{p}\mathrm{p}\right)：数字签名算法，为区块链系统中的每个节点生成数字签名密钥对。输入公共参数\mathrm{p}\mathrm{p}，经过计算后输出数字签名密钥对(\mathrm{D}\mathrm{S}.\mathrm{p}\mathrm{k},\mathrm{D}\mathrm{S}.\mathrm{s}\mathrm{k})。其中，节点P的数字签名公钥\mathrm{D}\mathrm{S}.\mathrm{p}{\mathrm{k}}_P在区块链系统中公开，私钥\mathrm{D}\mathrm{S}.\mathrm{s}{\mathrm{k}}_P由节点P自己保存，作为该节点的身份标识，为方便后续描述，下面将以P^{\mathrm{I}\mathrm{d}}来表示节点P的身份标识。

c) \left(\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{t-\mathrm{1}}\right)\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{K}\mathrm{G}\mathrm{e}\mathrm{n}\left(\mathrm{p}\mathrm{p}\right)：变色龙哈希密钥生成算法，选择t个节点生成变色龙哈希密钥对。输入公共参数\mathrm{p}\mathrm{p}，经过计算后输出变色龙哈希函数密钥对\left(\mathrm{p}\mathrm{k},\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{t-\mathrm{1}}\right)。其中，公钥\mathrm{p}\mathrm{k}在系统中公开，陷门\left(\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{t-\mathrm{1}}\right)分别由t个节点掌管持有，具体步骤参考2.2小节。

d) \left(\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{n-\mathrm{1}}\right)\leftarrow \mathrm{R}\mathrm{e}\mathrm{S}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{e}\left(\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\right.\left.\mathrm{s}{\mathrm{k}}_{t-\mathrm{1}}\right)：陷门密钥再分享算法。系统中t个节点将密钥份额从t份再分享成n份，使系统中n个节点各持有一份陷门密钥份额，门限值为t，超过t份分享份额可以恢复陷门。考虑到攻击者可能会与其中t-1个节点合谋，故需要将变色龙哈希的门限值调整为\mathrm{2}t-\mathrm{1}>\mathrm{2}(t-\mathrm{1}),确保陷门的安全性。具体步骤如算法1。

2） 分享更新阶段：主要完成陷门密钥的分享更新操作。由于在去中心化设置的区块链中，存在系统节点可能会随时加入或者退出区块链网络的情况，当持有陷门子秘密的节点下线或者系统上线了新节点，原有的变色龙哈希陷门子秘密的节点分配将不能再满足安全有效地恢复出陷门的要求。因此，为了应对区块链动态节点的情况，需要对节点持有的陷门份额分享进行更新，即将门限秘密分享从(t,n)更新为(t\text{'},n\text{'}),且保证密钥陷门不发生改变。

该阶段仅包含一个分享更新算法，即\left(\mathrm{s}{\mathrm{k}}_{\mathrm{0}}\mathrm{\text{'}},\right.\mathrm{s}{\mathrm{k}}_{\mathrm{1}}\mathrm{\text{'}},

\left.\dots ,\mathrm{s}{\mathrm{k}}_{n^{\text{'}}-\mathrm{1}}^{\text{'}}\right)\leftarrow \mathrm{U}\mathrm{p}\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{e}\left(\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{n-\mathrm{1}}\right)。当系统节点数量由n变为n\text{'}时，将n个节点的分享\left(\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\right.\left.\mathrm{s}{\mathrm{k}}_{n-\mathrm{1}}\right)更新成n^{\text{'}}份(\mathrm{s}{\mathrm{k}}_{\mathrm{0}}\mathrm{\text{'}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}}\mathrm{\text{'}},\dots ,\mathrm{s}{\mathrm{k}}_{n^{\text{'}}-\mathrm{1}}^{\text{'}})，分别由n\text{'}个节点持有，门限值由t更新为t\text{'}。具体步骤如下：

步骤1：选择一个二元t\text{'}次多项式，n个持有分享的节点可以根据多项式分解得到t\text{'}份中间值，并分发给t\text{'}个节点。t\text{'}个节点中每个节点则可以接收到n份中间值，据此生成多项式R\left(x,P_i^{\mathrm{I}\mathrm{d}}\right)，其中，R\left(\mathrm{0,0}\right)=\mathrm{0}。

步骤二：n个节点持有的陷门分享为F_i\left(x,P_i^{\mathrm{I}\mathrm{d}}\right)，计算更新函数F_i\text{'}\left(x,P_i^{\mathrm{I}\mathrm{d}}\right)=F_i\left(x,P_i^{\mathrm{I}\mathrm{d}}\right)+R(x,P_i^{\mathrm{I}\mathrm{d}})来更新每个节点的分享,由于R\left(\mathrm{0,0}\right)=\mathrm{0}，故陷门s=F^{\text{'}}\left(\mathrm{0,0}\right)=F(\mathrm{0,0})并未发生改变。随后n个节点再执行算法1，其中，输入为n个节点持有的分享，输出为n\text{'}个节点持有的分享，门限值为t\text{'}。

3） 随机选择阶段：主要负责在所有节点中随机选择具有编辑权限的编辑者。

该阶段包含一个选择编辑者算法，即\left(P_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{I}\mathrm{d}}\right.,g_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{s}{\mathrm{k}}_i},

\mathrm{h}\mathrm{a}\mathrm{s}{\mathrm{h}}_{\mathrm{m}\mathrm{i}\mathrm{n}})\leftarrow \mathrm{S}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}\mathrm{t}(P_i^{\mathrm{I}\mathrm{d}},g^{\mathrm{s}{\mathrm{k}}_i},\mathrm{h}\mathrm{a}\mathrm{s}{\mathrm{h}}_i)。首先，根据节点当前持有的密钥分享信息g^{\mathrm{s}{\mathrm{k}}_i}以及当前节点的身份信息P_i^{\mathrm{I}\mathrm{d}}，计算哈希值\mathrm{h}\mathrm{a}\mathrm{s}{\mathrm{h}}_i=H(g^{\mathrm{s}{\mathrm{k}}_i},P_i^{\mathrm{I}\mathrm{d}})；然后，根据哈希值的大小进行排序，从而确定最小哈希值\mathrm{h}\mathrm{a}\mathrm{s}{\mathrm{h}}_{\mathrm{m}\mathrm{i}\mathrm{n}}；最后，将\mathrm{h}\mathrm{a}\mathrm{s}{\mathrm{h}}_{\mathrm{m}\mathrm{i}\mathrm{n}}所对应的节点P_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{I}\mathrm{d}}作为本次选择的编辑者。

4） 数据编辑阶段：主要完成随机数分享的收集和区块链中数据的编辑。

该阶段主要包含一个数据编辑算法，即r\text{'}\leftarrow\mathrm{E}\mathrm{d}\mathrm{i}\mathrm{t}\left(\left(m,r\right),m^{\text{'}},\mathrm{p}\mathrm{k},(\mathrm{s}{\mathrm{k}}_{\mathrm{0}},\mathrm{s}{\mathrm{k}}_{\mathrm{1}},\dots ,\mathrm{s}{\mathrm{k}}_{n-\mathrm{1}})\right)。该算法先由持有分享的用户节点执行，输入消息和随机数对(m,r)、公钥\mathrm{p}\mathrm{k}、每个用户节点的各自私钥\mathrm{s}{\mathrm{k}}_i以及需要修正的消息值m\text{'}，通过变色龙哈希函数中的碰撞生成算法（\mathrm{D}\mathrm{H}\_\mathrm{A}\mathrm{d}\mathrm{a}\mathrm{p}\mathrm{t}）输出每个用户节点根据陷门分享计算所得出的随机数份额分享r_i^{\text{'}}=g^e\cdot g^{\left(m-m^{\text{'}}\right)·\mathrm{s}{\mathrm{k}}_i}（i\in (\mathrm{1,2},\dots ,n)）；然后由编辑者收集随机数份额来计算随机数r^{\text{'}}={\displaystyle \prod _{i-\mathrm{1}}^t}{r}_i^{\text{'}}（i\in (\mathrm{1,2},\dots ,n)），使得\mathrm{D}\mathrm{H}\_\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}\left(m,r,\mathrm{p}\mathrm{k}\right)=\mathrm{D}\mathrm{H}\_\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}\left(m^{\text{'}},r^{\text{'}},\mathrm{p}\mathrm{k}\right)，从而保证编辑前后哈希值一致，随后编辑者将区块消息m更改为m^{\mathrm{\text{'}}}。

5） 审查追责阶段：主要完成对区块数据编辑之后的审查验证和追责工作。当区块完成数据编辑之后，系统中的节点都可以对编辑后的数据进行审查验证，验证失效，将由监管者进行追责。

该阶段包含验证算法，即\left(b_{\mathrm{1}},b_{\mathrm{2}}\right)\leftarrow \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(m,m\text{'},

r,r^{\text{'}},(\mathrm{h}\mathrm{a}\mathrm{s}{\mathrm{h}}_{\mathrm{m}\mathrm{i}\mathrm{n}},P_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{I}\mathrm{d}},g_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{s}{\mathrm{k}}_i}))。输入相应的验证参数，输出验证结果。当区块数据完成编辑后，如果验证结果表征验证无效，则由监管者进行追责。具体步骤如下：

步骤1：验证编辑前后区块哈希值的一致性。重新计算\mathrm{D}\mathrm{H}\_\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}(m,r,\mathrm{p}\mathrm{k})=\mathrm{D}\mathrm{H}\_\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}(m\text{'},r\text{'},\mathrm{p}\mathrm{k})是否成立。如果成立，则b_{\mathrm{1}}输出为1，此次数据编辑有效；否则，b_{\mathrm{1}}输出为0，此次数据编辑无效，由系统中的节点进行相关方追责。

步骤2：验证编辑者的身份信息是否对应最小的哈希值，重新计算\mathrm{h}\mathrm{a}\mathrm{s}{\mathrm{h}}_{\mathrm{m}\mathrm{i}\mathrm{n}}=H(g_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{s}{\mathrm{k}}_i},P_{\mathrm{m}\mathrm{i}\mathrm{n}}^{\mathrm{I}\mathrm{d}})是否成立。如果成立，则b_{\mathrm{2}}输出为1，那编辑者的身份是合法的，享有编辑权；否则，b_{\mathrm{2}}输出为0，编辑者的身份不合法，由监管者追责此编辑者。

3　 安全性分析和实验评估

3.1　安全性分析

本小节给出本文可编辑区块链方案的详细安全性分析，首先是正确性分析，这是作为本文方案设计合理的基本要求，接下来是可编辑性分析和安全属性分析。

1） 正确性分析

方案正确性要求编辑者在数据编辑算法中，可以正确找到有效的哈希碰撞。即验证：给定m和r，h\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}(m,r,\mathrm{p}\mathrm{k})，对于m^{\text{'}}\ne m，存在有h\text{'}\leftarrow \mathrm{D}\mathrm{H}\_\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}(m^{\text{'}},r^{\text{'}},\mathrm{p}\mathrm{k})，使得\mathrm{D}\mathrm{H}\_\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}\left(\mathrm{p}\mathrm{k},\left(m,r\right),\right.\left.\left(m^{\text{'}},r\text{'}\right)\right)=\mathrm{1}且h=h^{\text{'}}。在数据编辑算法中，编辑者收集超过t个节点的随机值分享r_i^{\text{'}}=g^{e+\left(m-m^{\text{'}}\right)·\mathrm{s}{\mathrm{k}}_i}(i\ge t)并通过公式（2）计算得到r'：

r^{\mathrm{\text{'}}}={\displaystyle \prod _{i=\mathrm{1}}^t}{r}_i^{\text{'}}=g^{e+\left(m-m^{\mathrm{\text{'}}}\right)·{\displaystyle \sum _{i=\mathrm{1}}^t}s{k}_i}（2）

因为在秘密共享协议中，编辑者持有超过t\mathrm{个节}\mathrm{点}的密钥分享才能恢复出陷门，即s={\displaystyle \sum _{i=\mathrm{1}}^t}\mathrm{s}{\mathrm{k}}_i(i\ge t)。并且，已知\mathrm{p}\mathrm{k}=g^s，所以可以很容易计算哈希值h^{\text{'}}=h，如公式（3）所示：

h^{\text{'}}=r^{\text{'}}·\mathrm{p}{\mathrm{k}}^{m^{\text{'}}}=g^{e+\left(m-m^{\text{'}}\right)·s}·g^{s{m}^{\text{'}}}=g^{e+m·s}=r·\mathrm{p}{\mathrm{k}}^m=h（3）

即可以证明编辑者通过收集随机分享所得的碰撞r^{\text{'}}可以使\mathrm{D}\mathrm{H}\_\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}(\mathrm{p}\mathrm{k},\left(m,r\right),(m^{\text{'}},r\text{'}))=\mathrm{1}且h=h^{\text{'}}成立。因此，本文方案可以正确找到有效的碰撞值，即满足方案的正确性要求。

2） 可编辑性分析

可编辑性要求编辑者当收集到超过t个随机数分享时，可以计算得出哈希碰撞，在编辑之后，保证哈希值仍然一致。由正确性分析中的公式（2）和公式（3）可知，编辑者通过t个随机数分享计算出r^{\text{'}}时，可以满足编辑前后的哈希值仍然一致的要求，因而方案具有编辑性。

3） 安全属性分析

区块链中的安全属性包括三个方面，分别是链增长、链质量、公共前缀。接下来分析本文方案是否会影响这三个安全属性。首先，编辑者编辑的区块信息数据是在交易层级，没有影响到区块链的块增长，因而不会对链增长产生影响；其次，方案采用随机选择的方式确定编辑者，无法预测，故编辑者是恶意节点的概率会大大降低，若编辑者与其他恶意节点合谋，恶意编辑数据，诚实节点可以通过区块验证向监管方追责编辑者，从而保证区块链的整体质量；最后，本文方案并未修改共识算法，不会因为共识延迟受到影响，诚实节点可以就有效的编辑达成一致，保证了公共前缀。

3.2　功能特性对比

为了更加全面展示本文方案的功能特性，将本文方案与文献[6，12，13]的方案进行比较。如表1所示，文献[6]的方案和文献[13]的方案都使用了可验证秘密分享技术来分发变色龙哈希陷门份额给其他节点，但这两个方案都依赖于可信第三方分发变色龙哈希密钥，都属于中心化的可编辑区块链方案，同时这两个方案都没有考虑节点加入或退出区块链网络时的对于秘密恢复的影响，但后者考虑了在区块编辑后对恶意节点的追责。文献[12]的方案和本文方案都无需可信的中心化机构分发变色龙哈希密钥，采用去中心化的方式管理陷门密钥，都是去中心化的可编辑区块链方案，且都考虑了区块链节点的上下线对陷门分享的影响，本文还实现了对相关责任方的可追责性。

3.3　实验评估

3.3.1 实验环境

本文通过各阶段算法的运行时间来评估方案的效率，实验采用Python语言编写，主体部分大约由4 000行代码实现，所用的环境配置如表2。

3.3.2 效率分析

在本文方案中，采用了多个节点协同生成变色龙哈希陷门的方式，使用了秘密分享和恢复的思想。考虑门限值这个参数对方案中算法效率的影响，一方面，在密钥生成和分享更新过程中，需要门限值的节点数作为算法的启动输入；另一方面，在数据编辑阶段，需要收集超过门限值的分享才能计算。因此在本文实验中，考虑使用不同的门限值测试方案各个阶段算法的效率。

本文的性能测试主要包含两部分实验，一部分是使用不同的门限值测试本方案各个阶段的算法运行效率，另一部分是将本方案与其他方案测试数据编辑阶段的算法运行效率进行对比。

1） 各个阶段的算法运行效率分析

本文设置门限值数量以2 000个节点起步，每次密钥分享更新后，门限数量增加2 000个节点。图2给出了本方案5个阶段的算法运行时间。可以看出，初始化阶段、数据编辑阶段以及更新分享阶段的算法运行时间都会随着门限值的增加而增加，这是由于这3个阶段都存在所有节点进行分配或者收集分享的过程，因而当门限值增加时，这几个过程执行的时间也就更长。其中，初始化阶段相较其他阶段时间更长，是因为该阶段包括了生成密钥和生成数字签名的过程，但系统的初始化仅需执行一次，后续不用重复；而在更新分享阶段，只有节点数量存在变化时才需要执行此阶段，故门限值在初始为2 000时，因没有参照（即节点数量不存在变化）并未执行该阶段，其对应的算法运行时间为0 s，当门限值增加2 000个节点时，分享更新得以执行，以更新前的门限值为参照，所花时间均未超过1 s。选择编辑者阶段和审查追责阶段的算法运行效率都比较高，算法运行时间均未超过1 s。因此，从整体看来，本方案各个阶段的算法均有较高的运行效率。

2） 区块编辑效率分析

将本文方案与文献[12]和文献[13]的方案在区块编辑效率方面进行比较，实验中门限值均设定为4 000，三种方案编辑多个区块的累计时间对比如图3所示。实验结果表明，在编辑的区块数量相同的情况下，文献[12]的方案所花的时间最长，文献[13]的方案所花的时间最短。文献[12]采用的方案是设置编辑者群体共同分享陷门，需要达到门限值的编辑者达成投票共识才准许编辑，因而其区块编辑的时间包括了达成共识的时间；而本文方案是通过编辑者收集分享进行计算碰撞，因此，在区块编辑效率方面，本文的方案略优于文献[12]的方案。此外，文献[12]的方案并未考虑对恶意编辑者的追责，因此相较于本文的方案而言，编辑者作恶的可能性更高。文献[13]的方案采用权威中心分配变色龙哈希密钥，在编辑区块时，可以更快寻找到哈希碰撞，因此，其编辑效率比本文的方案更高。但文献[13]的方案需要一个可信的权威中心分发密钥，这种基于中心化的设置，存在一定的安全风险，且违背了区块链本身的去中心化原则。考虑到在区块链中，需要编辑的区块在所有区块中占比会较少，因此在无需权威分发中心的情况下，本文方案的区块编辑效率的降低在可以接受的范围内。

4　 结 语

本文提出了一种去中心化且可追责的可编辑区块链方案，该方案可以对区块链中非法有害数据以及错误信息进行编辑，且对区块链本身的一致性不会造成影响。该方案采用去中心化方式管理密钥，无须依赖分发中心。当编辑的内容存在问题时，系统中的用户节点能验证出此问题并向编辑者进行追责。实验结果和安全性分析结果表明，本文的方案满足可编辑性和区块链的安全属性，且各个阶段的算法都比较高效。考虑到在去中心化密钥管理的机制下，所有节点存在较多的空间存储开销和部分计算开销，下一步工作将考虑更高效的节点存储结构。

参考文献

[1] NAKAMOTO S. Bitcoin：A peer-to-peer electronic cash system［EB/OL］.［2023-02-10］. DOI: 10.2139/ssrn.3977007 .

[2] IBÁÑEZ L， O’HARA K， SIMPERL E. On blockchains and the general data protection regulation［EB/OL］. ［2021-11-20］. DOI: 10.1017/9781108609708.004 .

[3] 袁勇， 王飞跃. 可编辑区块链： 模型、技术与方法［J］. 自动化学报， 2020， 46（5）： 831-846. DOI： 10.16383/j.aas.2020.y000002 .

[4] YUAN Y， WANG F Y. Editable blockchain： Models， techniques and methods［J］. Acta Automatica Sinica， 2020， 46（5）： 831-846. DOI： 10.16383/j.aas.2020.y000002（Ch ）.

[5] ATENIESE G， MAGRI B， VENTURI D， et al. Redactable blockchain–or–rewriting history in bitcoin and friends［C］//2017 IEEE European Symposium on Security and Privacy （EuroS&P）. New York： IEEE Press， 2017： 111-126. DOI： 10.1109/EuroSP.2017.37 .

[6] DERLER D， SAMELIN K， SLAMANIG D， et al. Fine-grained and controlled rewriting in blockchains： Chameleon-hashing gone attribute-based［C］//Proceedings 2019 Network and Distributed System Security Symposium. Reston： Internet Society， 2019：1-15. DOI： 10.14722/ndss.2019.23066 .

[7] 李佩丽， 徐海霞， 马添军， 等. 可更改区块链技术研究［J］. 密码学报， 2018， 5（5）： 501-509. DOI： 10.13868/j.cnki.jcr.000259 .

[8] LI P L， XU H X， MA T J， et al. Research on fault-correcting blockchain technology［J］. Journal of Cryptologic Research， 2018， 5（5）： 501-509. DOI： 10.13868/j.cnki.jcr.000259（Ch ）.

[9] ZHANG J N， LU Y S， LIU Y H， et al. Serving at the edge： A redactable blockchain with fixed storage［C］//Web Information Systems and Applications. Cham： Springer， 2020： 654-667. DOI： 10.1007/978-3-030-60029-7_58 .

[10] DEUBER D， MAGRI B， THYAGARAJAN S A K. Redactable blockchain in the permissionless setting［C］//2019 IEEE Symposium on Security and Privacy （SP）. New York： IEEE Press， 2019： 124-138. DOI： 10.1109/SP.2019.00039 .

[11] LI X Y， XU J， YIN L Y， et al. Escaping from consensus： Instantly redactable blockchain protocols in permissionless setting［EB/OL］. ［2021-11-03］. DOI: 10.1109/tdsc.2022.3212601 .

[12] BLAKLEY G R， MEADOWS C. Security of ramp schemes［C］//Advances in Cryptology. Berlin： Springer， 2007： 242-268. DOI： 10.1007/3-540-39568-7_20 .

[13] CHOR B， GOLDWASSER S， MICALI S， et al. Verifiable secret sharing and achieving simultaneity in the presence of faults［C］//26th Annual Symposium on Foundations of Computer Science （sfcs 1985）. New York： IEEE Press， 2008： 383-395. DOI： 10.1109/SFCS.1985.64 .

[14] JIA M， CHEN J， HE K， et al. Redactable blockchain from decentralized chameleon hash functions［C］//IEEE Transactions on Information Forensics and Security. New York： IEEE Press， 2022： 2771-2783. DOI： 10.1109/TIFS.2022.3192716 .

[15] 赵晓琦， 张正昊， 李勇. 可编辑且可追责的区块链方案［J］. 信息安全学报， 2022， 7（5）： 19-28. DOI： 10.19363/J.cnki.cn10-1380/tn.2022.09.02 .

[16] ZHAO X Q， ZHANG Z H， LI Y. An editable and accountable blockchain scheme［J］. Journal of Cyber Security， 2022， 7（5）： 19-28. DOI： 10.19363/J.cnki.cn10-1380/tn.2022.09.02（Ch ）.

基金资助

国家重点研发计划(2021YFB2700200)

国家自然科学基金(61772383)

国家自然科学基金(U1836202)

国家自然科学基金(62076187)

国家自然科学基金(62172303)

湖北省自然科学基金(2020CFB628)