YOUChain 开源项目介绍——go-bls

本文介绍YOUChain 加密签名方面的思考和方案,go-bls 库已于 github 开源,项目地址:https://github.com/youchainhq/go-bls

YOUChain 签名方案的考虑

1 面临的问题

YOUChain所采用的共识机制,是基于VRF的一种新型PoS共识。对基于PoS的共识,基本上都存在一个对区块做签名投票的机制,所有这些投票信息,都需要存储及随区块广播。

考虑一个采用secp256k1签名方案的例子,这时单个签名的大小是 64 字节,如果有100个账户给一个区块投票,则仅签名数据就至少62.5KB。这个数据量必须得认真对待。

关于此问题,我们需要考虑,能否减少(压缩)一个区块的签名投票数据,以减轻存储及网络通信负担?

对多个签名进行压缩的技术,已知的包括阈值签名(Threshold signature, 也有翻译叫“门限签名”)方案和BLS签名方案。其中阈值签名方案需要有一个复杂的初始化过程,并且要求参与者集合稳定(若参与者集合发生变更,则必须重新进行一轮全局初始化),这对于YOUChain这种最终将完全去中心化的公链来说,是无法接受的。BLS签名方案也是实现签名聚合的一种主要技术,而这也是我们重点评估并考虑采用的技术。

2 BLS简介

BLS签名方案是由Boneh-Lynn-Shacham三人于2001年提出的一种椭圆曲线签名方案,具有一些良好的特性,最重要的就是“签名聚合”:多个签名可以聚合成单个签名,聚合后的签名长度就是单个签名的长度。基于这些特性,BLS签名方案在多签及签名聚合、m/n多签等方面都能提供很好的支持。

2.1 BLS的基本原理

BLS签名的核心,是椭圆双曲线配对(Elliptic curve pairings)函数,也称双线性映射(bilinear maps)函数。要了解BLS的基本原理,重点是理解配对函数的性质。首先,我们需要一下基本知识:

  1. 椭圆曲线密码学定义了两个运算:曲线上两个点的加法运算 +,以及一个整数与曲线上的一个点进行的标量称法运算 *,其具体定义当前不需深究,只需要记住这些运算的结果也是曲线上的点。
  2. 椭圆曲线有一个"生成点" G, G 做 n 次加法运算后可得到椭圆曲线上(除无穷点,也即零点 之外)的所有点,n称为椭圆曲线的阶。
  3. 定义一个无穷点O,算术上等价于0,即 P+O=P;
  4. 当 d 足够大时,知道椭圆曲线上的两个点 P,Q 其中 Q = d*P,求d困难,这就是椭圆曲线上的离散对数问题。

定义配对函数 e(P,Q),如果函数满足以下性质,则e(P,Q)就是一个双线性映射函数(其中大写字母表示曲线上的点,小写字母除了e为函数标识外,均为标量):

  1. e(P, Q + R) = e(P, Q) * e(P, R)
  2. e(P + S, Q) = e(P, Q) * e(S, Q)
  3. e(aP,bQ) = e(P,Q)^ab

也就是,配对函数对曲线上的运算满足交换律、结合律、分配率以及上面第3条性质。

在配对函数的基础上,令私钥为一个私密的整数 k, 则公钥为 P=k*G,对消息 m ,将其映射为曲线上的一个点,记为 H,则签名 S=k*H

签名的验证过程,即验证 e(P,H)=e(G,S) 是否成立。

证明为:

e(P, H)= e(k*G, H)= e(G, k*H) = e(G, S)

对于签名的聚合,假设聚合签名 S=S1+S2+...+S100,其中每个子签名都是不同秘钥对对同一个消息的签名(分别对不同消息签名也是可以的,那样验证时需要知道每个公钥对应的消息)。

则对聚合签名的验证为 e(G,S)=e(P1,H)*e(P2,H)*...*e(P100,H)
根据签名配对函数的性质,上述等式不难证明。

2.2 pairing-friendly curves

前述的双线性映射函数,并不是在所有的椭圆双曲线上都能实现。对于能实现双线性映射的椭圆曲线,称为pairing-friendly curves。关于这些曲线,IETF在今年初(Jan 2019)开始提出标准草案,当前是第三版 version-02 版。跟踪地址:ietf: draft-yonezawa-pairing-friendly-curves。根据标准草案,能实现双线性配对的曲线主要有两类:

  1. Barreto-Naehrig curve, 2005年提出,简称 BN curve。
  2. Barreto-Lynn-Scott Curve,2002年提出,简称 BLS curve。(BLS签名和BLS曲线,作者不尽相同:L是同一个即Lynn,B分别是Boneh和Barreto,S分别是Shacham和Scott)

一些项目使用的曲线及其安全性见下表(其中,标 * 的表示不能完全达到标题所示的安全性。):

Name 100 bit 128 bit 192 bit 256 bit
ISO/IEC 15946-5 BN256 BN384
TCG BN256
FIDO/W3C BN256
PBC BN
mcl BN254 / BN_SNARK1 BN381_1 (*) / BN462 /BLS12-381
RELIC BN254 / BN256 BLS12-381 / BLS12-455
TEPLA BN254
AMCL BN254 / BN256 BLS12-381 (*) / BLS12-383 (*) / BLS12-461 BLS48
Intel IPP BN256
Kyushu Univ. BLS48
MIRACL BN254 BLS12
Zcash BN128(CurveSNARK) BLS12-381
Ethereum BN254 BN382 (*) / BLS12-381(*)
Chia Network BLS12-381 (*)

目前比较多的BLS实现是基于Barreto-Naehrig curve的,即上表中 BN 开头的曲线。这些曲线的安全性目前打了些折扣。比如,BN256 (签名长度是256 bits),原来预期是能达到 128 bit的安全性,但是在2016年的时候,Kim 和 Barhulescu提出了一种新算法:the extended tower number field sieve (exTNFS),大幅降低了解决FFDLP(有限域离散对数问题)的复杂度,使得 BN256 所提供的安全性从预计的128 bits降低到了大约 100 bits。见上表。参考 https://crypto.stackexchange.com/questions/22835/are-barreto-naehrig-curves-suitable-for-pairing-based-cryptographyhttps://moderncrypto.org/mail-archive/curves/2016/000740.html
BLS一族的曲线,其安全性可能跟实现细节有关,上表中标 * 的BLS12-381,其安全性大概是 117~120 bits。

2.3 BLS签名标准草案

2.3.1 简介

IETF于今年初(Feb 2019)开始提出BLS签名标准草案。该标准草案的其中一个作者就是Dan Boneh。

根据标准草案,BLS实现上有两种策略(不同的侧重点):

  1. 最小化签名大小。签名放在G1中,公钥放在G2中,G1/E1的表达更紧凑。
  2. 最小化公钥大小。就是简单的换一下,将公钥放在G1中,将签名放在G2中。如果涉及大量的公钥传输,可以考虑这种策略。

相同的实现,将两条曲线对换一下,就成第二种策略了。

2.3.2 实现现状

标准草案介绍了BLS签名当前的实现现状(只介绍了基于 BLS12-381 的实现,因为BN256安全性不够):

  • Algorand:https://github.com/algorand/bls_sigs_ref
  • Chia:规格说明C++/Python实现源码。采用的是最小化公钥的策略,好像未包含成员检查(成员检查即检查公钥或签名是否在相应的有限群G1或G2内)。数据映射到曲线上(hashing to curve)使用的方案叫 Fouque-Tibouchi,可以在常量时间完成(这对于防止旁道攻击 side channel attacks 是非常必要的)。
  • Dfinity:go封装版,基于BN Curve, C++实现,实验室项目。C++实现是从herumi/bls fork的。好像未包含成员检查。(go封装版不支持G1、G2调换)。
  • Ethereum 2.0:只有规格说明没有实现。规格说明中提到这不是确定稿,会随着BLS标准的情况作出修改。并提到规格中的hash_to_G2函数是不安全的。

根据我们的比较研究,目前值得我们重点考虑的项目,一个是Algorand的项目,另一个是:https://github.com/phoreproject/bls

3 YOUChain 中的考虑

BLS签名方案,虽然有签名聚合的优点,但目前也还存在以下两个主要约束:

  1. 目前BLS的技术实现还不是很成熟,其安全性还没有得到严格验证;
  2. 目前双线性映射函数的性能较差,相比主流的一些椭圆曲线签名方案,其性能劣势非常显著(如相比secp256k1,性能差距在两个数量级以上)。

综合考虑,YOUChain将重点考虑以下应用方案:

  1. 用户账户体系,采用成熟稳定、高性能的secp256k1签名方案;
  2. 在共识过程中,区块投票的签名,采用BLS签名方案,在区块形成共识后,将投票者的签名进行聚合。

通过上述方案,将能更好地实现账户安全以及投票的签名数据量之间的更好平衡。

4 参考&引文

  1. BLS签名方案:https://www.iacr.org/archive/asiacrypt2001/22480516.pdf
  2. Compact Multi-Signatures for Smaller Blockchains :https://eprint.iacr.org/2018/483.pdf
  3. https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716
  4. https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
  5. ietf: draft-yonezawa-pairing-friendly-curves:https://datatracker.ietf.org/doc/draft-yonezawa-pairing-friendly-curves/
  6. IETF BLS标准草案: https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/
  7. https://crypto.stackexchange.com/questions/22835/are-barreto-naehrig-curves-suitable-for-pairing-based-cryptography
  8. https://moderncrypto.org/mail-archive/curves/2016/000740.html
  9. https://github.com/algorand/bls_sigs_ref
  10. https://github.com/Chia-Network/bls-signatures/blob/master/SPEC.md
  11. https://github.com/Chia-Network/bls-signatures
  12. https://github.com/dfinity/go-dfinity-crypto
  13. https://github.com/dfinity-lab/bls-tmp
  14. https://github.com/ethereum/eth2.0-specs/blob/master/specs/bls_signature.md
  15. https://github.com/phoreproject/bls
相关文章推荐