椭圆曲线数字签名算法源自于1985年KOBLITZ ^[1]与MILLER ^[2]提出的椭圆曲线公钥密码体制（ECC）,是一种安全性基于解离散对数问题困难的数字签名算法。在现代密码学的非对称加密中,RSA、ElGamal等公钥密码体制需要1024 bit长度密钥才能实现80位的安全级别^[3,4],而椭圆曲线签名算法在私钥长度为160 bit时就可实现80位的安全级别。简言之,椭圆曲线数字签名算法能以短密钥实现高安全,也正是如此,ECDSA在区块链这种分布式系统发展早期被广泛地采纳为默认签名算法。

在比特币诞生之初,区块链上的ECDSA算法多数是基于SECP256K1曲线的构造,该曲线因具备自同态映射的特性可加速消息验签过程曾备受青睐。不过随着工程应用的更迭,基于这种曲线的签名算法也暴露出诸多缺点,如总体算法结构冗杂、易遭受侧信道攻击与信息隐私性差等^[5,6]。虽然有学者尝试性设计了基于Montgomery曲线的ECDSA高效算法,并且对其中的标量乘步骤实施了优化以进一步提升签名效率^[7],但此类改进依然无法抵抗有效代数故障注入这种侧信道攻击,量子威胁也对ECDSA算法带来了很大的冲击^[8]。此外,当前大多数ECDSA算法因随机预言机产生的哈希函数与椭圆曲线中存在的离散对数困难问题,安全性也不利于有效证明^[9]。

随着多方计算的场景逐渐增多,多方协作签名的需求也迫使ECDSA算法寻求改进,基于门限签名机制（Threshold Signature Scheme,TSS）的ECDSA算法便是改进过程中一个探讨的方向,这在当前的去中心化跨链技术方案中也是一个炙手可热的研究点。LINDELL^[10]在2017年提出了一种快速安全两方ECDSA签名方案,深入分析了ECDSA门限签名协议在博弈安全证明下的安全性与相关假设下的应用方式。然而这种产生ECDSA签名的门限技术方案需要依赖繁重的密码学原语假设,这对原本ECDSA签名的性能影响很大,实际应用的效益也大大减弱。DOERNER ^[11]等人发现LINDELL方案这一缺陷,基于计算Diffie-Hellman假设以及ECDSA自身依赖的原语假设提出了一个可在随机预言机中抵抗恶意敌手攻击的新型安全两方门限ECDSA签名方案,此方案在密钥生成和签名效率上有很大的提升。在此之后,LINDELL^[12]等人分析出此签名方案虽然在签名效率上有所提升,但却不可避免地带来了严重的带宽问题,且并没有具体展示多方设置的方法,进而他们提出了可分散密钥生成与签名的多方ECDSA的门限签名协议。不过,这种协议方案的消息隐私处理方面尚需改善。CASTAGNOS^[9]等人则在2019年的论文中基于Lin的方案设计出无需交互性假设的基于哈希证明系统的两方ECDSA签名方案,且基于模拟安全情况下给出方案是紧安全性规约的结果证明。

本文研究将以CASTAGNOS^[9]等人提出椭圆曲线数字签名方案为基准,提出能够融入区块链的基于哈希证明系统的两方椭圆曲线签名方案。通过设定合理的计算模型来进行模拟安全分析,拟定在区块链上构造合理的验证操作完善签名方案,使得基于模拟的安全简洁构造方案在真实场景中同样适用且具备灵活性与可分散性。该方案也通过较少的传输比特信息的轮换次数,无需交互性假设即可实现隐私信息的零知识性,实现较为安全的数字签名技术。

在介绍相关的基础知识与签名算法前,预先给出一些通用符号的定义与简要说明以便于理解,如表1所示。

其余未在表中列举的符号含义,请参照具体章节与公式推导。

哈希证明系统于2002年被CRAMER和SHOUP提出,用于设计选择密文安全的公钥加密(PKE)机制,是一类特殊的非交互式证明系统^[13]。因为指定验证者的非交互系统中证明形式表现为哈希值,故被称为哈希证明系统。因为指定验证者的非交互系统中证明形式表现为哈希值,故被称为哈希证明系统。通常来说,哈希证明系统中存在一个实例集合X,存在NP语言L⊂ X,使得L={x∈X |ω ∈W:(x,ω)∈R}。其中R是一种二元关系定义,L为NP语言集合,W为证据集合。那么由语言系统( X,L,W,R )组成的哈希证明系统算法由下面3种概率多项式时间算法组成^[14]。

1）参数生成算法（Parameter Generation）Gen：生成密钥对( pr_key, pb_key),pr_key和pb_key之间存在多对一的关系映射,即$p{{r}_{key}}\overset{\alpha }{\mathop{\to }}\,p{{b}_{key}}$,α是一种映射关系。此外密钥pr_key定义一个哈希函数$has{{h}_{pr}}:X\to \Pi $,其中 X为实例空间,$\Pi $为证明空间。

2）私有求值算法（Private Evaluation）Pri：在算法Pri中,输入私钥pr_key,可以快速计算求出hash_pr( x ),x∈X。

3）公开求值算法（Public Evaluation）Pub：在算法Pub中,输入公钥pb_key,可在无私钥的情形下计算出hash_pr(x),前提是需要获取到x∈L中相应的证据ω ,即hash_pr(x)=Pub( pb_key, x, ω)。

一般地,哈希证明系统具备两个特性,分别是平滑性和投射性。投射性是指对于x∉L,hash_pr(x)在证明空间Π中随机分布,即如果私钥不相同,哈希值的产生也不相同,对于x∈L,hash_pr(x)的值可由公钥pb_key和元素x唯一确定,哈希值不变;平滑性是指一个有效密文x∈L与一个无效密文x∉L在哈希证明系统中的输出统计不可区分的。我们可以将具备较好平滑性和投影性的语言系统(X, L,W, R)可视为一个有效的子群问题（Subnet Membership Problem）。

所谓的零知识证明,简而言之,就是不泄露具体信息前提下向别人证明自己知道某个信息。Zcash就是为了实现全部匿名交易,利用零知识证明的算法保证了交易无法被追溯和泄露^[15]。从算法的设计上,零知识证明虽然在常见的隐私技术中算法简洁度比较差,但它的隐私程度相对较高。因此,自从2013年Pinocchio协议首次将零知识证明从理论带到应用到中以来（实现了分钟级证明,毫秒级验证）^[16],很多研究机构团体在零知识证明的算法及应用方面开展了研究与实现,例如斯坦福大学BUNZ ^[17]等人提出的匿名支付协议Zether、WILLIAMSON ^[18]提出的基于以太坊主网的隐私网络协议AZTEC,都采用零知识证明实现隐私保护。当前,应用最为广泛的零知识证明技术是zk-SNARKs,图1是zk-SNARKs的基本实现过程。

首先,需要将一个一般问题经过计算约简成QAP （Quadratic Arithmetic Program）问题,再进行抽样实现算法的简洁性;其次对抽样点进行同态隐藏并进行KCA（Knowledge of Coefficient Test and Assumption）,设置好共同参考数据集CRS）Common Reference String）;最后进行数据的双线性映射,实现无交互的目的。

椭圆曲线数字签名算法是椭圆曲线密码体制 （ECC）对数字签名DSA的模拟,在加密货币中ECDSA算法实现一般是对交易中哈希形式的数据信息进行签名然后利用用户的私钥进行签名的认证。ECDSA主要由密钥生成算法、签名算法、验证算法3部分组成。

1）密钥生成算法

给定算法函数Genkey(G_q,q,G),有如下密钥生成方式：Genkey(G_q,q,G)→(k, K)。其中G_q是阶数为q的椭圆曲线群,拥有基点G,k∈Z_q,为ECDSA算法的私有输入密钥,K为基于k的公钥。密钥生成方式为：K=kG。

2）签名算法

给定签名算法函数Sign(k, m),有如下算法生成方式：Sign(k,m)→(r,s)。其中m是待签名的消息,s为签名,r是有关R横坐标分量r_x的映射关系,取样a∈Z_q^*,有R=aG=(r_x,r_y),那么r就可表示为r←x mod q。如果r计算返回值为0,则重新选择a进行计算;最后对待签名消息进行hash处理计算签名s←a^-1hash(m)+rk mod q。给出签名对(r, s),并序列化为字节流和签名消息m送出进行验证。

3）验证算法

给定验证算法函数Verify(K, m, (r, s)),有如下验证方式：P=s^-1hash(m)+rkG=aG→(x_p, y_p)。如果r←x_p mod q成立,则验证方可证实签名有效。

当前,较为适合实现安全多方计算的数字签名技术是Schnorr签名以及BLS签名,因为自身具备同态特性可以进行公钥聚合然后签名消息通过线性等式验证。而相比之下,ECDSA相对复杂,因为验证的等式并不是线性的。为了使得ECDSA能够在现今多方计算场景中得以被使用,需要对原有ECDSA进行改造。鉴于Castagnos提出的基于HPS的两方椭圆曲线数字签名算法（2P-ECDSA）方案,给出2P-ECDSA的安全模型密钥生成阶段,如图2所示。

从图2可以看出,给定的2P-ECDSA的安全模型主要分为密钥生成和签名验证两个阶段,在密钥生成阶段Gen(G_q,q,G,g_q)中,相关的密钥信息的交互是由签名双方在链下进行的,其中g_q是以阶数q为基准的本原元。生成步骤如下：

1）签名参与方P₁首先借助自己的私有输入密钥k₁生成共享密钥K₁,然后将k₁,K₁以及有关k₁知识证明的承诺com₁传入零知识性承诺函数$F_{zk-com}^{{{R}_{DL}}}$中,上标R_DL代表零知识性功能函数,用于证明给定的椭圆曲线点的离散对数知识,特征数式为R_DL:={(K,ω)|K=ωG}。在经过$F_{zk-com}^{{{R}_{DL}}}$处理之后,输出证明proof₁,传递给P₂处理;

2）签名参与方P₂确认接收到证明proof₁后,使用私有输入密钥k₂生成共享密钥K₂,然后将k₂,K₂以及有关k₂知识证明的承诺com₂传入零知识性承诺证明函数$F_{zk-proof}^{{{R}_{DL}}}$中,在经过$F_{zk-proof}^{{{R}_{DL}}}$处理之后,输出证明proof₂,传递给P₁处理。

3）P₁接收到确认接收到proof₂之后,对原有证明proof₁进行拆解,然后再次送入零知识性函数$F_{zk-com}^{{{R}_{DL}}}$进行处理,将证明proof₁的拆解内容Dec_com( proof₁)连同共享密钥K₁进行预存。

4）P₁私下从q阶离散点集分布D_q中取样私密输入k以及ω,然后利用k投影生成哈希钥h。接着通过k,ω以及h产生用于二次零知识性证明的加密值c_key,需要注意的是图中的f是证明空间$\Pi $的一个循环子群。加密值c_key给定完成后,需要将有关私密输入对(k₁,ω)知识的承诺com₃,公共参数组(h,c_key,K₁)以及私密输入对(k₁,ω)送至零知识性哈希证明函数$F_{zk}^{{{R}_{HPS-DL}}}$处理,其中上标${{R}_{HPS-DL}}$指代基于哈希证明系统的零知识性功能函数,用于证明加密的随机性知识、给定椭圆曲线离散对数基点K₁的知识以及有关加密了私密输入k₁的密文对(c_key,1,c_key,2)知识,即c_key。在经过$F_{zk}^{{{R}_{HPS-DL}}}$处理之后,输出证明proof₃以及公共参数组(h,c_key,K₁)交由P₂留存。

5）P₁、P₂分别私下计算统合公钥K,然后需提交至区块链合约contract_bp上进行备份存根。

通过使用具备零知识性的功能函数$F_{zk-com}^{{{R}_{DL}}}$、$F_{zk-proof}^{{{R}_{DL}}}$以及$F_{zk}^{{{R}_{HPS-DL}}}$进行私密信息的处理,将签名参与双方在密钥生成阶段的隐私信息进行封装,对于每次进行零知识函数处理生成的证明,如果接受方接受不到,将会终止接下来的信息交换流程,也就相应无区块链链上操作,减少额外通信的损耗。

在密钥生成阶段处理完成后,便会进入签名阶段Sign(m, seed ),流程如图3所示。

从图3中可以看出,对于给定签名消息m以及用于消息标识的随机数seed,签名双方交互有如下步骤：

1）~3）与密钥生成阶段操作相仿,唯一区别在于每次传输消息数据时多了消息标识seed,其中seed₁代表来自签名参与方P₁的标识,seed₂代表来自签名参与方P₂的标识。以便于在签名阶段对每次输出传输的数据流进行更为精准的判别;

4）P₁、P₂分别私下计算用于ECDSA验证算法的椭圆曲线点R,然后将R的横坐标r_x抽取出来,由签名双方分别对其进行取模运算生成r,并传输至合约contract_ver中进行存根比对,如果比对成功,可以进行下一步签名流转;

5）签名参与方P₂对消息m进行哈希处理产生m',紧接着调取r、a₂、m'以及密钥生成阶段P₁传输过来的哈希钥h生成加密值c₁以及基于c_key生成的加密输入c₂进行组合运算生成c₃,并将其传给P₁;

6）由签名参与方P₁利用投影哈希函数的可分解性对c₃进行解密以便获得随机变量α计算签名的乘幂$\hat{s}$。

7）取$\hat{s}$与$q-\hat{s}$的最小值作为签名s,最终将签名对(r, s)交付区块链上合约contract_ver进行核验。

8）合约验证签名(r, s)是否正确,验证通过返回1,否则返回0。因验证过程与椭圆曲线签名算法ECDSA的验证过程相同,故不再进行过多赘述。

本文采用第2章中的算法和安全模型,给出融入区块链的哈希证明系统架构,如图4所示。可以看出,该系统架构由3个模块组成：可证数据流转协议模块、哈希证明系统中间件模块和区块链模块。

可证数据协议负责处理可信数据流转,本架构拟采用哈希证明文件（Hash Proof File Protocol）进行模块设计。在该协议内部嵌入了第3部分的安全模型与算法结构、需要签名的真实信息数据以及哈希证明中间件的指向。通过哈希证明中间件位置信息定位到哈希证明系统中间件将安全模型与算法结构桥接到哈希证明系统中间件中进行信息的交互。哈希证明系统中间件则包括两个部分,身份认证中间件以及哈希证明中间件,为了在签名过程中加强参与方之间的可信度,需经过身份认证中间件进行基本核验评判,然后再进入哈希证明中间件进行2P-ECDSA算法实现。根据密钥生成阶段与签名阶段,在进行哈希证明2P-ECDSA算法协议时,需要与区块链数据进行流转,借助智能合约比对验证共享密钥的正确性、签名的合法性等。此外,对于签名消息,也需要借助单向函数进行哈希处理,进行备份保存。

之所以可证数据流转协议中利用哈希证明中间件位置信息先指向哈希证明中间件而不直接指向区块链,是因为参与方不能直接对链数据操作来证明签名信息的可靠,因为代价开销过高,且通过区块节点位置查找证明内容并不方便。但证明中间件是可被经过身份认证的参与方利用链数据来验证的,从而在保证公共存储的公钥数据、签名数据等难以篡改,以建立可信实用的哈希证明系统。

对于该HPFS架构,区块链的链式结构使得哈希证明进一步实现了算法协议控制权声明与数据信息控制权使用的分离,解决信息泄露、信息不可信的问题。一方面,算法的定义与使用在链下进行实现的同时,需要与区块链进行交互对公钥数据、签名信息等进行备份以防在算法协议声明时发生信息篡改;另一方面,借助智能合约也能够在签名验证阶段进行算法自治,对不合法签名予以否认,并仅对共享数据进行哈希处理,使得签名双方保有私有信息时可借助区块链与公共数据建立逻辑纽带,从而释放签名者的隐私数据价值。此外,因为分布式网络中任何人都可以拉取区块链,所以区块链网络上的参与者都可以利用链数据进行验证,从而增强了该哈希证明系统的可靠性。

3.2.1 基于模拟的安全证明

通常密码学领域安全性证明主要分为两种,一种是基于博弈的安全（Proofs Based on Simulation）,一种是基于模拟的安全（Proofs Based on Games）。对于基于博弈的安全,安全性一般是由博弈的过程来判定的。而基于模拟的安全,则是由自己设定的模拟器和理想函数而定的。所以从语义安全上看,基于模拟的安全性证明更加能确定它的正确性。即若敌手获取某消息密文而模拟器未得到,那么敌手此时能计算的所有有关该消息的信息模拟器也是可以计算的,则加密安全^[6]。

本文拟定了3个具备零知识性的理想功能函数：$F_{zk-com}^{{{R}_{DL}}}$、 $F_{zk-proof}^{{{R}_{DL}}}$、$F_{zk}^{{{R}_{HPS-DL}}}$,给定模拟器σ,那么所有这些理想功能函数的执行将会在σ被执行,输入参数会经过模拟器σ传入指定功能函数然后在函数体内执行完成之后将会再次通过模拟器σ被输出出来。为了证明该基于HPS的2P-ECDSA算法协议在存在单一恶意敌手情况下的不可区分性,下面将模拟存在恶意参与方P₁和存在恶意参与方P₂两种情形进行安全分析。

1）存在恶意参与方P₁。给定模拟器σ,在密钥生成步骤将会验证K₁=k₁G是否成立,如果不成立,那么σ将在密钥生成步骤3）中模拟出参与方P₂中止流程的情况。如果成立,那么σ将会通过提取的私密输入k₁验证P₁私下计算的${{c}_{key}}=\left( g_{\omega }^{q},{{h}^{\omega }}{{f}^{{{k}_{1}}}} \right)$是否成立,如果不成立,那么σ将在密钥生成步骤4）中模拟出参与方P₂中止流程的情况。相应地,在签名步骤σ将会验证R₁=a₁G是否成立,如果不成立,那么σ将会在签名步骤3）中模拟出参与方P₂中止流程的情况。如果成立,将会继续生成最终共享公钥K供签名步骤计算核验签名。

2）存在恶意参与方P₂。在密钥生成步骤,σ将会通过提取的私密输入k₂验证P₂计算K₂是否是椭圆曲线上的非零点使得K₂=k₁G。如果不成立,那么σ将在密钥生成步骤2）中模拟出参与方P₁中止流程的情况。如果成立,那么将继续进行理想的ECDSA功能函数,使参与方P₁接受输入,然后进行共享公钥K的链上合约存储备份。在签名步骤,σ将会通过提取的私密输入a₂验证P₂计算R₂是否是椭圆曲线上的非零点使得R₂=k₂G成立。如果不成立,那么σ将在签名步骤2）中模拟出参与方P₁中止流程,不再进行签名计算。如果成立,那么σ将接收从P₂传入过来的c₃,根据α= a₂^-1m'+ rx₂x₁ mod q进行判别,如果σ成立,诚实参与方P₁将会接收输入进行校验,否则算法将会中止。

综合上述两种情形的分析,在与诚实参与方P_i, i∈1,2交互时,经σ输出的内容是不可区分的。因为σ可以从基于哈希证明系统的零知识性功能函数R_HPS-DL中提取私密输入k₁,换句话说,也就是发生恶意行为后可以重新计算密文并验证以获取加密值c_key。另外,因为私密输入元素都源自于循环群Z/qZ,所以在理想情形和实际情形中,私密输入的概率分布将会是相同的。通过设定模拟器σ简要分析了存在恶意参与方的情形,展示了算法的存在性与零知识性,从而完成了模拟安全的证明。

此外,为了证明不可区分性,敌手必须要将原加密方案中的x∈L的元素替换为语言系统(X,L,W,R)之外的x∉L元素,即将有效密文篡改为无效密文。但若想实行这种篡改,敌手又必须知道私密的哈希密钥,然而对于一个语言系统子集成员(X,L,W,R)是一个子集成员困难问题时,那么在多项式时间内,敌手的这种篡改便不会成功,这一点不会被任何多项式时间的对手注意到。此外,因签名方案中的哈希证明系统的平滑性允许参与方用明文空间的某些随机值来替换当前的明文值,从而保证加密方案的不可区分性。

3.2.2 应用安全分析

该理论架构中,将哈希后的签名信息、密钥生成时的共享密钥信息以及签名对信息$\left( r,s \right)$进行上链存储,通过合约对公开的数据信息进行检测认证,防止签名双方链下肆意篡改数据信息进行作恶。在哈希证明系统的中间件中额外添加了身份验证的机制,预先定义唯一的标识信息与签名者的隐匿身份信息进行关联,在身份验证中间件内部进行签名者身份的验证方式将会保证签名者的签名身份具有一定可信性。而针对算法定义、安全模型定义等涉及内部签名实现的原理级别内容,是在可证数据流转协议中进行了内部封装,只向外部服务提供需权限认证通过才可进行调用的接口,即在使用上进行了安全限制。

总而言之,基于HPS的2P-ECDSA算法,融合区块链实现分布式的哈希证明系统服务,将分布式的账本技术逐渐发展成为分布式的服务技术,业务层面上是从单纯的去中心化数据存储机制演变为去中心化的“数据+服务”。通过哈希证明构造语义安全的密码学签名算法,保障了数据的准确性与可信。一旦数据具备可信任的所属性,那么在此前提下便可进一步交换创造价值。

本文研究在CASTAGNOS^[9]等人论文理论之上,实现可以融入区块链的基于HPS的2P-ECDSA方案理论,证实了该方案是基于模拟安全的,且具备良好隐私性。不过目前的方案仍有可以改进的地方,如在哈希证明系统中间中并未将身份认证中间件中判别签名者的算法协议进行具体的描述,需要更为详细的设计方案,我们正考虑在此中间件中融入多方参与的量子密钥分发手段^[20]以实现安全、可双向验证的密钥分发协议。本文方案在后量子密码时代并不具备抵抗量子计算机的能力,设计一个更为安全的基于哈希证明系统的两方椭圆曲线签名依旧需要不断分析和深入研究。此外,下一步工作中会考虑将方案与多学科技术进行交叉融合,如大数据、人工智能等,将算法效率进行调优改进,以便结合真实案例场景进行合理布局。