Page 245 - 《软件学报》2020年第12期

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

定义 1(陷门单向函数). 陷门单向函数 f(x)是指满足以下性质的函数:
(1) 对于属于 f 定义域的任意 x,可在多项式时间内计算得到 y=f(x);
−1
(2) 对于属于 f 值域的任意 y,无法在多项式时间内求出 x,使得 x=f (y);
(3) 当 k 已知时,对于属于 f 值域的任何 y,可在多项式时间内计算出 x = f k − 1 ()y ,其中,k 为该陷门单向函数
的陷门.
1.2 Grinding Blocks攻击 [10,16]

传统的区块结构分为区块头与区块体两部分:区块体存储交易信息,区块头包含版本号、父区块哈希、交
易 Merkle Tree 根、时间戳、难度目标和 Nonce.挖矿挑战在于:寻找合适的随机数 Nonce,使区块头哈希结果小
于难度目标.因此,挖矿挑战与交易信息相关.为了利益最大化,矿工可能将交易信息拆分成多份,以形成不同挖
矿挑战,在同一时间寻找多个 Nonce,以打包形成不同区块,提高挖矿成功概率.此类行为没有遵守“将挖矿期间
产生的交易全部打包于区块”的原则,影响系统效率,也可能进一步导致自私挖矿与双花攻击.此类行为称为
Grinding Blocks 攻击,如图 1 所示.

区块头 区块头 区块头 区块头

Version Version Version Version

Hash pre Hash pre Hash pre Hash pre
_
MT_Root τ MTRoot 1 τ MT _Root 2 τ MT _Root τ
Grinding n
T T T ... T
难度目标 Blocks 难度目标 难度目标 难度目标
Nonce Nonce 1 Nonce 2 Nonce n

区块体 区块体 区块体 区块体

τ=τ 1+τ 2+…+τ n τ=τ 1 τ=τ 2 τ=τ n

Fig.1 Schematic diagram of Grinding Blocks attack
图 1 Grinding Blocks 攻击示意图
在图 1 中,Version,Hash pre ,MT_Root τ ,T,Nonce 和τ依次表示区块头中的版本号、父区块哈希、交易 Merkle Tree
根、时间戳、矿工用以完成挖矿挑战的随机数和交易信息.
“Grinding Blocks”攻击在 POW 共识下不常见,因为 POW 共识机制基于算力挖矿,完成一次挖矿挑战需要耗
费巨大算力,矿工在同一时间进行多个挑战的计算难度巨大.但在同时进行多个挖矿挑战难度较小的共识机制
下,如第 1.3 节中介绍的基于空间证明的区块链中,“Grinding Blocks”攻击将变得相对容易.
1.3 基于空间证明的区块链 [10,13]
最近,Park 等人构建了以“空间”为可信度衡量标准的区块链系统 SpaceMint,其共识机制为 POSpace.不同于
POW 和 POS,POSpace 将拥有最大存储空间的节点视为最可信节点,由其完成系统相关操作,获取奖励.各节点
向全网证明自己空间大小、竞争成为记账者的过程,便是 POSpace 共识机制下的挖矿过程.因此,安全可靠的空
间大小衡量标准是 POSpace 共识机制的关键.
POSpace 共识机制使用“pebble game”,通过节点对有向无环图的构造速度来衡量空间大小.当时间一定时,
节点空间越大,对有向无环图的构造越快;反之亦然.具体而言,POSpace 共识机制要求各节点在本地存储一有向
无环图 G=(V,E),其中,V={v 1 ,v 2 ,…,v N }为顶点集合,N 为顶点个数,E 为有向边集合.有向无环图示例如图 2 所示.
为了突出有向无环图的结构,每个顶点 i 将被赋予特定的标签值,记为 l i :
l = Hash (, ,μ i l ,l ,...,l ) ,i=1,2,…,N,
i 1 p 2 p t p
其中,i 为顶点序号,μ为与挖矿节点公钥关联的随机数, l 1 p ,l 2 p ,...,l 为顶点 i 的所有母节点的标签值.
t p