可修改的区块链方案.pdf

海尔塔啾啾

432

14页

7次

2021-01-28

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2020,31(12):3909−3922 [doi: 10.13328/j.cnki.jos.005894] http://www.jos.org.cn

可修改的区块链方案

∗

任艳丽

徐丹婷

张新鹏

谷大武

(上海大学通信与信息工程学院,上海 200444)

(上海交通大学电子信息与电气工程学院,上海 200240)

通讯作者: 任艳丽, E-mail: renyanli@shu.edu.cn

摘要: 随着区块链的迅速发展,上链数据不仅包括金融交易数据,还包括科技、文化、政治等多类数据.而在现有

的区块链系统中,数据一旦上链便无法更改,可能会面临失效数据无法删除、错误数据无法修改等问题.因此,特定条

件下可修改的区块链方案具有广阔的应用前景.在 POSpace(proof of space)共识机制下,基于陷门单向函数和新型区

块链结构,提出了可修改的区块链方案.只要超过阈值数的节点同意,便可实现区块数据的合法修改,否则不能进行

修改.除修改数据外,其余区块数据保持不变,全网节点仍可按原始验证方式对数据合法性进行验证.仿真实验表明:

只要选定合适的阈值,所提方案中,区块生成与数据修改的效率均很高,数据的修改并不改变区块之间的链接关系,

具有现实可操作性.

关键词: 区块链;可修改;陷门单向函数;空间证明;数据安全

中图法分类号: TP309

中文引用格式: 任艳丽,徐丹婷,张新鹏,谷大武.可修改的区块链方案.软件学报,2020,31(12):3909−3922. http://www.jos.org.cn/

1000-9825/5894.ht m

英文引用格式: Ren YL, Xu DT, Zhang XP, Gu DW. Scheme of revisable blockchain. Ruan Jian Xue Bao/Journal of Software,

2020,31(12):3909−3922 (in Chines e). ht tp://www.jos.org.cn/1000 -9825/5894.h tm

Scheme of R evisable B lockc hai n

REN Yan-Li

, XU Dan-Ting

, ZHANG Xin-Peng

, GU Da-Wu

(School of Communication and Infor mation Engineering, Shanghai Univ ersit y, Shanghai 200444, Ch ina)

(School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)

Abstra ct : With the rapid development of the blockchain, the data on the chain not only include financial data, but also have data of

technology, culture, politics, and so on. However, the data will not be revised once it is packaged on the existing blockchain system,

which has the problem that the invalid data cannot be deleted and the wrong data cannot be modified. Therefore, a revisable blockch ain

under certain conditions has broad application prospects. Under the POSpace (proof of space) consensus mechanism, a revisable

blockchain scheme is proposed based on the trapdoor one-way function and a new blockchain structure. In this scheme, the nodes can

execute the revision op eration as long as their number exceeds th e thr eshold. Otherwise, th e revision operation cannot b e executed. Except

for the revised data, the remaining data on the blocks keeps unchanged, and all of the nodes on the network can still verify the validity of

data by using the original verification ways. The experiments show th at block generation and data r evision all have high efficien cy as long

as the threshold is selected appropriately, and the link relationship betw een the blocks will not be changed after the data revision, and the

scheme has practical operability.

∗ 基金项目: 国家自然科学基金(U1736120, 61525203, U1636206); 上海市自然科学基金(20ZR1419700); 国家重点研发计划

(2020YFC1523004)

Foundation item: National Natural Science Foundation of China (U1736120, 61572309, 61525203, U1636206); Beijing Municipal

Natural Science Foundation (20ZR1419700); National Key Research and Development Program of China (2020YFC1523004)

收稿时间: 2019-03-15; 修改时间: 2019-09-06; 采用时间: 2019-09-27; jos 在线出版时间: 2019-12-05

CNKI 网络优先出版: 2019-12-05 14:54:55, http://kns.cnki.net/kcms/d etail/11.2560.TP.20191205.1454.002.html

3910

Journal of Software 软件学报 Vol.31, No.12, December 2020

Key words: blockchain; revisable; trapdoor one-way f unction; proof o f space; d ata security; d ata security

近年来,区块链技术得到学术界和企业界的广泛关注.从以比特币

[1]

为代表的加密货币系统——区块链 1.0,

到以太坊为代表的智能合约——区块链 2.0, 再到现在,区块链应用走出金融,走向社会多行业,进入区块链 3.0 时

代.去中心化和上链数据不可篡改的特性,使其有别于传统的中心化系统,为金融、科技甚至政治等领域的数据

存储提供了新的模式

[2]

在区块链系统中,共识机制为各节点制定信任标准,构建激励机制,使得各节点就系统状态达成共识,共同

维护系统健康运行

[3]

.目前,主流的共识机制有基于工作量证明的 POW(proof of work)共识机制

[1,4]

、基于权益证

明的 POS(proof of stake)共识机制

[5−7]

、基于授权股权证明的 DPOS(delegated proof of stake)共识机制

[8,9]

等.现

有的区块链系统基本以 POW 与 POS 共识机制为主,但 POW 基于算力竞争,挖矿电力损耗巨大,不利于节能环保.

POS 基于权益竞争,信用机制不牢固,大量低成本货币被分配于开发者,若利益驱使其大量抛售货币,将不利于系

统维护. Park 等人基于 POSpac e(proof of space)共识机制提出 SpaceMint 区块链系统

[10]

,节点基于可循环利用的

本地空间竞争挖矿,计算代价低,避免了算力竞争而造成的资源浪费.同时,安全的证明机制保证其信用牢固性,

实现了对安全性与资源效率的兼顾.另外,S paceMint 系统采用新型链式结构.传统的区块链利用哈希函数将区

块头、区块体以及前后区块链接起来,以哈希函数的不可碰撞性保证数据安全.而 SpaceMint 通过加入签名子块,

打破区块头和区块体的直接链接关系,构建了新型的区块链接结构,详见第 1.3 节.

现有的区块链系统中,数据一旦上链便无法更改.而随着区块链的发展,除金融数据外的科技、文化甚至政

治等多类社会数据也将上链,失效数据无法删除、错误数据无法修改等问题将变得更加突出.例如:一个公司宣

布破产,其交易数据失效,不再具备永久存储的价值,无法及时删除将造成存储资源浪费;或者某些上链的经典

技术参数、公式在若干年后被推翻,需做出修正;又或者恶意、负面的舆论数据由于别有用心的挖矿者而上链,

区块链的公开性将导致其不断扩散传播,造成恶劣影响.及时的数据修正在现有的区块链系统中均无法完成,可

能造成巨大的经济损失和恶劣的社会影响.因此,上链数据无法更改将在一定程度上限制了区块链的进一步发

展,而在特定条件下实现可修改的区块链,具有广阔的应用前景.

在可修改区块链研究中,爱哲森公司基于带陷门的变色龙哈希函数

[11]

,在已知陷门时,可对区块数据进行修

改.但该方案中,陷门被交于可信中心,修改权被中心化,数据安全面临威胁.Li 等人

[12]

对可修改区块链技术进行

了改进,利用秘密共享方案,将陷门分配给系统各节点,当且仅当阈值节点联合时方可恢复陷门,实现数据修改.

但上述方案均基于变色龙哈希函数实现区块数据修改,而现有的区块链系统大多基于传统的抗碰撞哈希函数,

所以上述方案应用价值不高.Ren 等人

[13]

基于抗碰撞哈希函数,提出了可删除区块链系统,利用安全的门限环签

名方案,在超过门限值的节点同意时,可对单个区块的全部交易数据进行删除.但该方案无法删除指定交易数

据,也无法进行数据修改.本文使用抗碰撞哈希函数,基于 POSpace 共识机制实现可修改的区块链方案,在绝大多

数节点同意后,可对指定交易数据进行修改或删除,具有重要的应用价值.

本文基于文献[10]中的区块结构和陷门单向函数,提出了可修改的区块链方案.通过引入机动因子,重构区

块签名子块,在数据失效或错误时,只要超过阈值数节点同意,便可实现区块数据的合法修改;同时保持区块链

接不变,除修改数据,其余数据不变,全网仍可按原始验证方式对数据合法性进行验证.而且我们设置了特定的

阈值,使得修改操作必须经过绝大多数节点同意,恶意的非法修改无法完成,保证了数据的安全.

1 基础知识

本节将介绍一些基本概念,包括陷门单向函数、Grinding Blocks 攻击及基于空间证明的区块链结构.

1.1 陷门单向函数

陷单向函数是密码学领域的一个重要概念,可简单描述为:正向求解容易,但反向求解不可实现的函数.陷

门单向函数

[14,15]

不同于单向函数的“不可逆”,它是“陷门”可逆的.在陷门未知时,它等同于普通单向函数;当陷门

已知时,求逆便计算上可实现.

任艳丽等:可修改的区块链方案

3911

定义 1(陷门单向函数). 陷门单向函数 f(x)是指满足以下性质的函数:

(1) 对于属于 f 定义域的任意 x,可在多项式时间内计算得到 y=f(x);

(2) 对于属于 f 值域的任意 y,无法在多项式时间内求出 x,使得 x=f

−1

(y);

(3) 当 k 已知时,对于属于 f 值域的任何 y,可在多项式时间内计算出

()

−

= ,其中,k 为该陷门单向函数

的陷门.

1.2 Grinding Blocks攻击

[10,16]

传统的区块结构分为区块头与区块体两部分:区块体存储交易信息,区块头包含版本号、父区块哈希、交

易

Merkle Tree 根、时间戳、难度目标和 Nonce.挖矿挑战在于:寻找合适的随机数 Nonce,使区块头哈希结果小

于难度目标

.因此,挖矿挑战与交易信息相关.为了利益最大化,矿工可能将交易信息拆分成多份,以形成不同挖

矿挑战

,在同一时间寻找多个 Nonce,以打包形成不同区块,提高挖矿成功概率.此类行为没有遵守“将挖矿期间

产生的交易全部打包于区块

”的原则,影响系统效率,也可能进一步导致自私挖矿与双花攻击.此类行为称为

Grinding Blocks 攻击,如图 1 所示.

Fig.1 Sc hemat ic diagram of Grindin g Blocks attack

图 1 Grinding Blocks 攻击示意图

在图 1 中,Version, Ha s h

pre

,MT_Root

,T,Nonce 和

依次表示区块头中的版本号、父区块哈希、交易 Merkle Tr ee

根、时间戳、矿工用以完成挖矿挑战的随机数和交易信息.

“Grinding Bl ocks”

攻击在 POW 共识下不常见,因为 PO W 共识机制基于算力挖矿,完成一次挖矿挑战需要耗

费巨大算力

,矿工在同一时间进行多个挑战的计算难度巨大.但在同时进行多个挖矿挑战难度较小的共识机制

下

,如第 1.3 节中介绍的基于空间证明的区块链中,“Gri nding Bloc ks”攻击将变得相对容易.

1.3 基于空间证明的区块链

[10,13]

最近,Park 等人构建了以“空间”为可信度衡量标准的区块链系统 SpaceMint,其共识机制为 POSpace.不同于

POW 和 POS,POSpace 将拥有最大存储空间的节点视为最可信节点,由其完成系统相关操作,获取奖励.各节点

向全网证明自己空间大小、竞争成为记账者的过程

,便是 POSpace 共识机制下的挖矿过程.因此,安全可靠的空

间大小衡量标准是 POSpace 共识机制的关键.

POSpace

共识机制使用“pebble game”,通过节点对有向无环图的构造速度来衡量空间大小.当时间一定时,

节点空间越大,对有向无环图的构造越快;反之亦然.具体而言,POSpace 共识机制要求各节点在本地存储一有向

无环图

G=(V,E),其中,V={v

,…,v

}为顶点集合,N 为顶点个数,E 为有向边集合.有向无环图示例如图 2 所示.

为了突出有向无环图的结构,每个顶点 i 将被赋予特定的标签值,记为 l

(,, , ,..., )

ippp

lHashill l,i=1,2,…,N,

其中,i 为顶点序号,

为与挖矿节点公钥关联的随机数,

, ,...,

ll l为顶点 i 的所有母节点的标签值.

区块头

Version

难度目标

Nonce

区块体

区块头

Version

难度目标

Nonce 1

区块体

区块头

Version

难度目标

Nonce 2

区块体

区块头

Version

难度目标

Nonce n

区块体

Grinding

Blocks

...

Hash

pre

Hash

pre

Hash

pre

Hash

pre

+…+

MT_Root

T Root

TRoot

T Root

of 14

免费下载

区块链

相关文档

评论