最新论文笔记(+17)：Poicy-based Chameleon Hash for Blockchain Rewriting with Black-box Accountability/ACSA20_cryptocxf的博客

Poicy-based Chameleon Hash for Blockchain Rewriting with Black-box Accountability (基于策略的变色龙哈希和具有黑盒问责的区块链重写）

这篇文章是ACSAC20上的一篇区块链相关论文，并且友好的在文中附上了源码链接，供大家进行实验仿真，还是不错的，且论文写的也非常好，比较适合阅读。以下是我个人在读后记录的笔记和个人的理解，理解还有许多不足，建议还是看原文！

• 原文链接：Poicy-based Chameleon Hash for Blockchain Rewriting with Black-box Accountability

一、背景、简要工作和预备知识

1.1 写作背景

文章开篇，国际惯例。首先介绍区块链相关背景，然后引出了重写区块链的必要性，并指出目前主要为两种类型的区块链重写（若对背景不是很了解的可以结合related work一起看，这里不再赘述）：

• 1）区块级重写：直接用变色龙哈希替换传统区块Merkle树根节点的哈希值。
• 2）交易级重写：发生在特定区块中的交易上。Derler等人介绍了基于策略变色龙哈希（PCH）的区块链重写，它包括以下特性。首先，PCH支持交易级重写。其次，PCH通过使用基于属性加密ABE实现了细粒度的区块链重写，具体来说，访问策略被嵌入到交易和具有PCH陷门的交易修改者中，若其对应的PCH陷门的属性满足嵌入式访问策略则可以修改交易。

动机：基于PCH的区块链重写会有安全问题，例如交易修改者可能滥用重写特权。交易修改者可以拒绝他对交易的恶意重写，因为具有不同PCH陷门的其他交易修改者可以满足嵌入在交易中的相同访问策略。这种安全威胁存在的原因是因为ABE有一个固有属性：匿名。

另外，问责制是区块链重写的关键。

1.2 简要工作

本文引入基于策略的变色龙哈希和黑盒问责（PCHBA），用于确保区块链重写、实现匿名和问责，若对修改后的交易无争议，则交易修改者仍然是匿名的。

黑盒问责两层含义：

• 1）任何公共用户都可以识别一组被指控的交易修改者，其PCH陷门被用于生成访问设备/黑盒。访问黑盒包括各种不同的交易修改程序的改写权限，可以帮助被指控的交易修改程序在市场上获得更好的经济收益或降低被发现的机会；
• 2）属性权威机构可以将修改后的交易链接到负责的交易修改者（即一一映射），以防止对修改后的交易产生争议。由于基于PCH的区块链重写中，不同的修改者可以修改相同的交易，所以本文允许属性权威在对同一交易的多个修改版本产生争议时，将交易的每个修改版本链接到一个负责的交易修改者。

主要贡献：

• 1）通用框架：介绍了第一个黑盒问责的基于策略的变色龙哈希的通用框架PCHBA用于区块链的重写，它不允许交易修改者拒绝对任何由该修改者修改的交易进行恶意重写。
• 2）实例化：提出了一个PCHBA实例，并通过实施和评价验证其实用性。

1.3 预备知识

1.3.1 双线性映射

令 ( g , h ) (g,h) (g,h)表示两个群生成器，给定安全参数 λ \lambda λ作为输入，输出群 G , H \mathbb{G},\mathbb{H} G,H。我们定义 ( g , h ) (g,h) (g,h)的输出为 ( q , G , H , G T , e ) (q,\mathbb{G},\mathbb{H},\mathbb{G}_T, e) (q,G,H,GT​,e)，其中 q q q是一个素数， G , H \mathbb{G},\mathbb{H} G,H和 G T \mathbb{G}_T GT​是阶为 q q q的循环群，双线性映射 e : G × H → G T e:\mathbb{G}\times\mathbb{H}\to \mathbb{G}_T e:G×H→GT​满足：

• 1）双线性： ∀ g , h ∈ G \forall g,h\in G ∀g,h∈G和 a , b ∈ Z q a,b\in \mathbb{Z}_q a,b∈Zq​，我们有 e ( g a , h b ) = e ( g , h ) a b e(g^a,h^b)=e(g,h)^{ab} e(ga,hb)=e(g,h)ab。
• 2）非退化性：在 G T \mathbb{G}_T GT​中， ∃ g ∈ G \exists g\in \mathbb{G} ∃g∈G使得 e ( g , h ) e(g,h) e(g,h)具有 q q q阶。我们假设群操作 G , H \mathbb{G},\mathbb{H} G,H和 G T \mathbb{G}_T GT​和双线性映射 e e e关于 λ \lambda λ在多项式时间上是可计算的。将 G 和 H \mathbb{G}和\mathbb{H} G和H视为源群， G T \mathbb{G}_T GT​作为目标群。

基于决策线性指数DLE和基于扩展决策Diffie-Hellman（eDDH），本文提出了一个新的复合假设，用来证明所提出的基于属性的黑盒跟踪加密的语义安全性（ABET）方案。

1.3.2 基于属性密文策略加密和黑盒可追溯

这里就不再赘述，建议看原文。

1.3.3 数字签名

一个数字签名方案包括 ( S e t u p , K e y G e n , S i g n , V e r i f y ) (Setup, KeyGen, Sign, Verify) (Setup,KeyGen,Sign,Verify)四个算法构成。

二、主要内容

2.1 系统模型

系统模型主要包括三种类型的用户：属性权威机构（AA）、交易拥有者和交易修改者。

如下图，交易所有者将散列对象附加到区块链中，之后由AA授予重写权限的交易修改者来修改哈希对象，而哈希链的链接则保持不变。若修改后的交易发生争议，AA可以决定修改后的交易是否确实被该交易修改人修改。

基于策略的变色龙哈希包含以下算法：

• 1） S e t u p ( 1 λ ) → ( s k , p k ) Setup(1^\lambda)\to(sk,pk) Setup(1λ)→(sk,pk)：输入安全参数 λ \lambda λ，输出变色龙哈希密钥对 ( s k , p k ) (sk, pk) (sk,pk)。
• 2） K e y G e n ( s k , δ ) → s k δ KeyGen(sk, \delta)\to sk_\delta KeyGen(sk,δ)→skδ​：将变色龙的私钥 s k sk sk，和属性集 δ ∈ U \delta \in \mathbb{U} δ∈U作为输入，输出密钥 s k δ sk_{\delta} skδ​，它是由身份 I D ′ ID' ID′索引。
• 3） H a s h ( p k , m , ∧ , I D ) → ( h , r , δ ) Hash(pk, m, \land, ID)\to (h,r,\delta) Hash(pk,m,∧,ID)→(h,r,δ)：将变色龙的公钥 p k pk pk，消息 m ∈ M m\in \mathbb{M} m∈M，策略 ∧ \land ∧和身份 I D ID ID作为输入，输出变色龙哈希值 h h h，随机数 r r r和签名 σ \sigma σ。在这个过程后，变色龙哈希值 h h h出现在区块链中。请注意 M = { 0 , 1 } ∗ \mathbb{M}=\{0, 1\}^* M={0,1}∗表示一般消息空间。
• 4） V e r i f y ( p k , m , h , r , σ ) → b = { 0 , 1 } Verify(pk, m, h, r, \sigma)\to b=\{0,1\} Verify(pk,m,h,r,σ)→b={0,1}：将变色龙的公钥 p k pk pk，消息 m m m，变色龙哈希值 h h h，随机数 r r r，和签名 δ \delta δ作为输入，输出一个位 b b b。
• 5） A d a p t ( s k δ , m , m ′ , h , r , δ , I D ′ ) → r ′ Adapt(sk_{\delta},m,m',h,r,\delta,ID')\to r' Adapt(skδ​,m,m′,h,r,δ,ID′)→r′：将密钥 s k δ sk_\delta skδ​，消息 m m m和 m ′ m' m′，变色龙哈希值 h h h，随机数 r r r，签名 δ \delta δ和身份 I D ′ ID' ID′作为输入，若 1 = ∧ ( δ ) 1=\land(\delta) 1=∧(δ)和 I D ≤ I D ′ ID\leq ID' ID≤ID′，则输出新随机数 r ′ r' r′。
• 6） J u d g e ( s k , T , O ) Judge(sk, \mathbb{T}, O) Judge(sk,T,O)：将变色龙的私钥 s k sk sk，交易集 T \mathbb{T} T和访问黑盒 O O O中的一组被指控身份作为输入，输入一个（或多个）链接的交易标识对。

安全模型：在许可区块链中，交易所有者是诚实的一方，假设属性权威机构是诚实方，则需考虑三种安全保证，包括不可区分性、抗碰撞性和问责性。

• 1）不可区分性。
• 2）抗碰撞性。
• 3）问责性。

2.2 通用构造

通用构造由以下构建块组成：

• 一个不可区分性和抗碰撞性的安全变色龙哈希与临时陷门方案 C H E T = ( S e t u p , K e y G e n , H a s h , V e r i f y , A d a p t ) CHET = (Setup, KeyGen, Hash, Verify, Adapt) CHET=(Setup,KeyGen,Hash,Verify,Adapt)。
• 一种基于属性的自适应安全密文策略加密，具有黑盒可追溯方案 A B E T = ( S e t u p , K e y G e n , E n c , D e c , T r a c e ) ABET = (Setup, KeyGen, Enc, Dec, Trace) ABET=(Setup,KeyGen,Enc,Dec,Trace)。
• 一种存在性不可伪造的选择消息攻击EUF-CMA安全数字签名方案 ∑ = ( S e t u p , K e y G e n , S i g n , V e r i f y ) \sum =(Setup, KeyGen, Sign ,Verify) ∑=(Setup,KeyGen,Sign,Verify)。

本文用属性权威机构AA，交易所有者ID和交易修改者 I D ′ ID' ID′来标识通用构造。我们定义了一个确定性算法 ∑ \sum ∑如 v k ← K e y G e n ′ ( p p , 0 , s k ) vk \leftarrow KeyGen'(pp,0,sk) vk←KeyGen′(pp,0,sk)，它用一个公共值和两个秘密值作为输入。

• S e t u p ( 1 λ ) Setup(1^ \lambda ) Setup(1λ)：AA将安全参数 λ \lambda λ作为输入，输出变色龙密钥 s k ← ( m s k A B E T , s k C H E T ) sk \leftarrow (msk_{ABET}, sk_{CHET}) sk←(mskABET​,skCHET​)和变色龙公钥 p k ← ( p k C H E T , m p k A B E T , p p ) pk \leftarrow (pk_{CHET}, mpk_{ABET},pp) pk←(pkCHET​,mpkABET​,pp)，其中 ( s k C H E T , p k C H E T ) ← K e y G e n C H E T ( P P C H E T ) , P P C H E T ← S e t u p C H E T ( 1 λ ) , ( m s k A B E T , m p k A B E T ) ← S e t u p A B E T ( 1 λ ) (sk_{CHET},pk_{CHET}) \leftarrow KeyGen_{CHET}(PP_{CHET}), PP_{CHET}\leftarrow Setup_{CHET}(1^\lambda), (msk_{ABET}, mpk_{ABET})\leftarrow Setup_{ABET}(1^\lambda) (skCHET​,pkCHET​)←KeyGenCHET​(PPCHET​),PPCHET​←SetupCHET​(1λ),(mskABET​,mpkABET​)←SetupABET​(1λ)和 p p ← S e t u p ∑ ( 1 λ ) pp\leftarrow Setup_{\sum}(1^\lambda) pp←Setup∑​(1λ)。
• K e y G e n ( s k , δ ) KeyGen(sk,\delta) KeyGen(sk,δ)：AA将变色龙密钥 s k sk sk，属性集 δ \delta δ作为输入，输出密钥 s k δ ← ( s k C H E T , s s k ) sk_\delta \leftarrow (sk_{CHET},ssk) skδ​←(skCHET​,ssk)，其中 s s k ← K e y G e n A B E T ( m s k A B E T , δ ) ssk \leftarrow KeyGen_{ABET}(msk_{ABET}, \delta) ssk←KeyGenABET​(mskABET​,δ)，其中 s s k ssk ssk与交易修改者的身份 I D ′ ID' ID′相关联。
• H a s h ( p k , m , ∧ , I D ) Hash(pk, m, \land, ID) Hash(pk,m,∧,ID)：交易拥有者 I D ID ID将带有消息 m m m的基于策略的变色龙哈希附加到区块链中。
• V e r i f y ( p k , m , h , r , C , v k , c , δ ) Verify(pk,m,h,r,C,vk,c,\delta) Verify(pk,m,h,r,C,vk,c,δ)：若以下检查保持，则输出1，否则输出0。 1 ← V e r i f y C H E T ( p k C H E T , m , h , r ) 1\leftarrow Verify_{CHET}(pk_{CHET},m,h,r) 1←VerifyCHET​(pkCHET​,m,h,r)和 1 ← V e r i f y ∑ ( v k , c , δ ) 1\leftarrow Verify_{\sum}(vk,c,\delta) 1←Verify∑​(vk,c,δ)。
• A d a p t ( s k δ , m , m ′ , h , r , C , v k , c , δ , I D ′ ) Adapt(sk_\delta,m,m',h,r,C,vk,c,\delta,ID') Adapt(skδ​,m,m′,h,r,C,vk,c,δ,ID′)：具有密钥 s k δ sk_\delta skδ​和一个新消息 m ′ m' m′的交易修改者 I D ′ ID' ID′执行一系列操作。（见原文）
• J u d g e ( s k , O , T ) Judge(sk,O,\mathbb{T}) Judge(sk,O,T)：给定一个交易集合 { T ′ } ∈ T \{T'\}\in \mathbb{T} {T′}∈T，和被指控交易修改者集合 { I D ′ } ∈ O \{ID'\}\in O {ID′}∈O，若交易 T ′ T' T′连接一被指定的修改者ID‘，其中 T ′ = ( m ′ , h , r ′ , C ′ , v k ′ , c ′ , δ ′ ) T'=(m',h,r',C',vk',c',\delta ') T′=(m′,h,r′,C′,vk′,c′,δ′)，则AA输出一个交易身份对 ( T ′ , I D ′ ) (T',ID') (T′,ID′)。

正确性。Judge算法允许AA识别交易和被指控交易修改者之间的一对一关系。AA重复这个过程，直到识别 T ′ {T'} T′中的交易和 I D ′ {ID'} ID′中的被指控交易修改者之间的一对一关系。

Remark。交易修改者ID’可以将一个新策略 ∧ ′ \land ' ∧′分配给Adapt算法中已修改的交易 T ′ T' T′。交易中嵌入的访问策略可以在区块链系统发展的情况下动态更新，以满足不同的安全需求。

2.3 应用（重点1）

这小节给出了PCHBA在区块链重写中的应用。在high-level，区块链保持不变，即使某些基于策略的可变交易已经被修改。每个区块存储一组交易的紧凑表示。具体来说，TX_ROOT在一个区块内累积的所有交易。（如下图中Merkle树的根哈希）

表示属性权威机构的一方，包括变色龙公钥 p k pk pk使用与地址所有者的公钥对应的密钥下签名的交易。若交易所有者ID希望将某些基于策略的交易附加到区块链中，则属性权威为系统中所有交易修改者发出秘密密钥，且这些交易必须使用 H a s h ( p k , m , ∧ , I D ) Hash(pk, m,\land,ID) Hash(pk,m,∧,ID)进行哈希。如上图所示，一个区块 B i B_i Bi​累积四笔交易 T ( i , 1 ) , T ( i , 2 ) , T ( i , 3 ) , T ( i , 4 ) T_{(i,1)},T_{(i,2)},T_{(i,3)},T_{(i,4)} T(i,1)​,T(i,2)​,T(i,3)​,T(i,4)​，其中 T ( i , 1 ) T_{(i,1)} T(i,1)​和 T ( i , 3 ) T_{(i,3)} T(i,3)​是基于策略的交易，它们具有不同的访问策略和相同的身份 ( ∧ ( i , 1 ) , I D ) (\land_{(i,1)},ID) (∧(i,1)​,ID)、 ( ∧ ( i , 3 ) , I D ) (\land_{(i,3)},ID) (∧(i,3)​,ID)，它们是由交易拥有者ID选择。其余交易照常处理，即 T ( i , 2 ) T_{(i,2)} T(i,2)​和 T ( i , 4 ) T_{(i,4)} T(i,4)​使用传统的抗碰撞哈希函数H进行哈希。

当需要修改基于策略的交易时，交易修改者ID‘与变色龙密钥 s k δ ′ sk_\delta ' skδ′​满足 ( ∧ ( i , 1 ) , I D ) (\land_{(i,1)},ID) (∧(i,1)​,ID)、 ( ∧ ( i , 3 ) , I D ) (\land_{(i,3)},ID) (∧(i,3)​,ID)（例如 1 = ∧ ( i , 1 ) ( δ ′ ) 1=\land_{(i,1)}(\delta ') 1=∧(i,1)​(δ′)和 I D ≤ I D ′ ID\leq ID' ID≤ID′）可以计算哈希值A和C的有效碰撞（或随机数），并提供新的随机数。限制，修改者广播新的随机性到区块链网络。所有参与者都验证了新随机性的正确性（即验证算法），并通过用新的随机性替换旧的随机性来更新区块链的本地副本。由于交易中的随机性、签名和密文不包含在聚合的哈希计算中，而是作为交易/区块的非哈希部分提供，所以PREV_H的值永远不会被修改。

若某些交易是使用PCHBA创建的，可以确保：1）不可区分性，给定一个随机性，任何公共用户都无法决定与交易 T ( i , 1 ) T_{(i,1)} T(i,1)​（或 T ( i , 3 ) T_{(i,3)} T(i,3)​)相关的随机性是使用Hash还是Adapt算法创建的；2）抗碰撞性，使得只有交易修改者ID’具有足够的重写权限来重写区块链；3）问责性，即如果对修改后的交易存在争议，属性权威（AA）可以将每一笔修改后的交易关联到一个负责任的交易修改者。

2.4 实例化和实施（重点2）

这个小节给出了PCHBA的实例化，和实现与评估分析。首先，为了启动CHET，可以使用[19]中基于离散对数（DL）的变色龙哈希构造。同时，基于RSA和基于DL的变色龙哈希具有双线性映射[19]也应该适合。其次，选择CP-ABE方案[9]和匿名HIBE方案[14]区实例化ABET。

为了构建一个实际的ABET，我们需要底层ABE方案中密文的大小是恒定的（即，与系统中的用户数量无关）。因此，本文依赖于最近的ABE方案[9]和HIBE方案[14]。然后，后面是具体实例化过程，实验评估，这里就不再赘述。

2.5 源码地址

Github源码地址
本篇文章比较友好的是它提供了源代码（见上面链接），供读者仿真。

源码文件包含了三个文件：test.py、PCHBA.py和msp.py。都是基于python语言开发的，我们只需运行test.py文件即可。

按照作者提供的代码和系统运行，可得出三句successful verification输出结果。至于为什么这样的输出，还需仔细看源代码。

三、总结心得

本文提出了一个基于策略的变色龙哈希的通用框架，该框架具有黑盒问责，用于区块链重写。该方案可以帮助阻止任何变色龙陷门持有者的恶意改写区块链。最后给出了一个实际实例，来表明本方案适合于区块链应用程序。

文章中的公式确实多，证明也比较复杂，需要花时间耐心阅读，本人暂且也是一知半解，上面应该有许多理解（翻译）不对的地方，建议看原文比较好！后续若有修改或更深的理解，也会相应的更新。😀