参加比特币源码研读班后首次写作,看到前辈black写的有关密钥,地址写的很好了,就选了他没有写的椭圆曲线,斗胆写这一篇。
在密码学上有两种加密方式,分别是对称密钥加密和非对称密钥加密。
对称加密:加密和解密使用的同样的密钥。
非对称加密:加密和解密是使用的不同的密钥。
二战中图灵破解德军的恩尼格码应该就是用的对称加密,因为他的加密和解密是同一个密钥。比特币的加密是非对称加密,而且用的是破解难度较大的椭圆曲线加密,简称ECC。
非对称加密的通用原理就是用一个难以解决的数学难题做到加密效果,比如RSA加密算法。RSA加密算法是用求解一个极大整数的因数的难题做到加密效果的。就是说两个极大数相乘,得到乘积很容易,但是反过来算数一个极大整数是由哪两个数乘积算出来的就非常困难。
下面简要介绍一下椭圆曲线加密算法ECC。
首先椭圆曲线的通式是这个样子的:
一般简化为这个样子:
()发公式必须吐槽一下,太麻烦了。)
其中
这样做就排除了带有奇点的椭圆曲线,可以理解为所有的点都有一条切线。
图像有几种,下面列举几个:[1]
椭圆曲线其实跟椭圆关系不大,也不像圆锥曲线那样,是有圆锥的物理模型为基础的。在计算椭圆曲线的周长时,需要用到椭圆积分,而椭圆曲线的简化通式:
,周长公式在变换后有一项是这样的:,平方之后两者基本一样。
我们大体了解了椭圆曲线,就会有一个疑问,这个东西怎么加密的呢?也就是说椭圆曲线是基于怎样的数学难题呢?在此之前还得了解一些最少必要知识:椭圆曲线加法,离散型椭圆曲线。
椭圆曲线加法
数学家门从普通的代数运算中,抽象出了加群(也叫阿贝尔群或交换群),使得在加群中,实数的算法和椭圆曲线的算法得到统一。
数学中的“群”是一个由我们定义了一种二元运算的集合,二元运算我们称之为“加法”,并用符号“ ”来表示。为了让一个集合G成为群,必须定义加法运算并使之具有以下四个特性:
1. 封闭性:如果a和b是集合G中的元素,那么(a b)也是集合G中的元素。
2. 结合律:(a b) c = a (b c);
3. 存在单位元0,使得a 0 = 0 a =a;
4. 每个元素都有逆元,即:对于任意a,存在b,使得a b = 0.
如果我们增加第5个条件:
5. 交换律: a b = b a
那么,称这个群为阿贝尔群。[1]
运算法则:任意取椭圆曲线上两点P、Q (若P、Q两点重合,则做P点的切线)做直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R。我们规定P Q=R。(如图)[2]
特别的,当P和Q重合时,P Q=P P=2P,对于共线的三点,P,Q,R’有P Q R’=0∞.
这里的0∞不是实数意义的0,而是指的无穷远点(这里的无穷远点就不细说了,你可以理解为这个点非常遥远,遥远到两条平行线都在这一点相交了。具体介绍可以看参考文献[2])。
注意这里的R与R’之间的区别,P Q=R,R并没有与P,Q共线,是R’与P,Q共线,不要搞错了。
法则详解:
这里的 不是实数中普通的加法,而是从普通加法中抽象出来的加法,他具备普通加法的一些性质,但具体的运算法则显然与普通加法不同。
根据这个法则,可以知道椭圆曲线无穷远点O∞与椭圆曲线上一点P的连线交于P’,过P’作y轴的平行线交于P,所以有无穷远点 O∞ P = P 。这样,无穷远点 O∞的作用与普通加法中零的作用相当(0 2=2),我们把无穷远点 O∞ 称为零元。同时我们把P’称为P的负元(简称,负P;记作,-P)。(参见下图)
离散型椭圆曲线
上面给出的很好看的椭圆曲线是在实数域上的连续曲线,这个是不能用来加密的,原因我没有细究,但一定是连续曲线上的运算太简单。真正用于加密的椭圆曲线是离散型的。要想有一个离散型的椭圆曲线,先得有一个有限域。
域:在抽象代数中,域(Field)之一种可进行加、减、乘、除运算的代数结构。它是从普通实数的运算中抽像出来的。这一点与阿贝尔群很类似。只不过多了乘法,和与乘法相关的分配率。
域有如下性质[3]:
1.在加法和乘法上封闭,即域里的两个数相加或相乘的结果也在这个域中。
2.加法和乘法符合结合律,交换率,分配率。
3.存在加法单位,也可以叫做零元。即存在元素0,对于有限域内所有的元素a,有a 0=a。
4.存在乘法单位,也可以叫做单位元。即存在元素1,对于有限域内所有的元素a,有1*a=a。
5.存在加法逆元,即对于有限域中所有的元素a,都存在a (-a)=0.
6.存在乘法逆元,即对于有限域中所有的元素a,都存在a*=0.
在掌握了这些知识后,我们将椭圆曲线离散化。我们给出一个有限域Fp,这个域只有有限个元素。Fp中只有p(p为素数)个元素0,1,2 …… p-2,p-1;
Fp 的加法(a b)法则是 a b≡c (mod p);它的意思是同余,即(a b)÷p的余数与c÷p的余数相同。
Fp 的乘法(a×b)法则是 a×b≡c (mod p);
Fp 的除法(a÷b)法则是 a/b≡c (mod p);即 a×b∧-1≡c (mod p);(也是一个0到p-1之间的整数,但满足b×b∧-1≡1 (mod p);
Fp 的单位元是1,零元是 0(这里的0就不是无穷远点了,而是真正的实数0)。
下面我们就试着把
这条曲线定义在Fp上:
选择两个满足下列条件的小于p(p为素数)的非负整数a、b,且a,b满足
则满足下列方程的所有点(x,y),再加上无穷远点O∞ ,构成一条椭圆曲线。
其中 x,y属于0到p-1间的整数,并将这条椭圆曲线记为Ep(a,b)。
图是我手画的,大家凑合看哈。不得不说,p取7时,别看只有10个点,但计算量还是很大的。
Fp上的椭圆曲线同样有加法,法则如下:
1. 无穷远点 O∞是零元,有O∞ O∞= O∞,O∞ P=P
2. P(x,y)的负元是 (x,-y),有P (-P)= O∞
3. P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:
x3≡-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)
其中若P=Q 则 k=(3 a)/2y1 若P≠Q,则k=(y2-y1)/(x2-x1)
通过这些法则,就可以进行离散型椭圆曲线的计算。
例:根据我画的图,(1,1)中的点P(2,4),求2P。
解:把点带入公式k=(3*x∧2 a)/2y1
有(3*2∧2 1)/2*4=6(mod 7).
(注意,有些小伙伴可能算出13/8,这是不对的,这里是模数算数,就像钟表一样,过了12点又回到1点,所以在模为7的世界里,13=6,8=1).
x=6*6-2-2=4(mod 7)
y=6*(2-4)-4=2 (mod 7)
所以2P的坐标为(2,4)
那椭圆曲线上有什么难题呢?在模数足够大的情况下,上面这个计算过程的逆运算就足够难。
给出如下等式:
K=kG (其中 K,G为Ep(a,b)上的点,k为小于n(n是点G的阶)的整数)不难发现,给定k和G,根据加法法则,计算K很容易;但给定K和G,求k就相对困难了。
这就是椭圆曲线加密算法采用的难题。我们把点G称为基点(base point),k称为私钥,K称为公钥。
现在我们描述一个利用椭圆曲线进行加密通信的过程[2]:
1、用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G。
2、用户A选择一个私钥k,并生成公钥K=kG。
3、用户A将Ep(a,b)和点K,G传给用户B。
4、用户B接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数r(rn)。
5、用户B计算点C1=M rK;C2=rG。
6、用户B将C1、C2传给用户A。
7、用户A接到信息后,计算C1-kC2,结果就是点M。因为
C1-kC2=M rK-k(rG)=M rK-r(kG)=M
再对点M进行解码就可以得到明文。
整个过程如下图所示:
密码学中,描述一条Fp上的椭圆曲线,常用到六个参量:
T=(p,a,b,G,n,h),p 、a 、b 用来确定一条椭圆曲线,G为基点,n为点G的阶,h 是椭圆曲线上所有点的个数m与n相除的整数部分
这几个参量取值的选择,直接影响了加密的安全性。参量值一般要求满足以下几个条件:
1、p 当然越大越安全,但越大,计算速度会变慢,200位左右可以满足一般安全要求;
2、p≠n×h;
3、pt≠1 (mod n),1≤t20;
4、4a3 27b2≠0 (mod p);
5、n 为素数;
6、h≤4。
200位位的一个数字,那得多大?而且还是素数,所以这种方式是非常安全的。而且再一次交易中,区块被记录下来只有10分钟的时间,也就是说要想解决这个难题必须在10分钟以内。即便有技术能够在10分钟以内破解了现在这个难度的加密算法,比特币社区还可以予以反制,提高破解难度。所以比特币交易很安全,除非自己丢掉密钥,否则不存在被破解可能。
第一次写一个完全陌生的数学领域的知识,也许我有错误的地方,也许有没讲明白的地方,留言讨论吧。总之写完后对比特比系统的安全性表示很放心。
参考文献
[1] 椭圆曲线密码学简介
[2] 什么是椭圆曲线加密(ECC)
[3] 域(数学)维基百科
区块链研习社源码研读班 高若翔
比特币和区块链的诞生需要依赖于很多核心技术的突破:一是拜占庭容错技术;二是非对称加密技术;三是点对点支付技术。下面会依次介绍。
拜占庭容错技术
比特币和区块链诞生的首要难点在于如何创建分布式共识机制,也就是菜斯利·兰伯特等人1982年提出的拜占庭将军问题。所谓拜占庭将军问题是指,把战争中互不信任的各城邦军队如何达成共识并决定是否出兵的决策过程。延伸至计算机领域,试图创建具有容错性的分布式系统,即使部分节点失效仍可确保系统正常运行,也可让多个基于零信任基础的节点达成共识,并确保信息传递的一致性。
中本聪所提到的“拜占庭将军问题”解决方法起始于亚当﹒拜克在1997年发明的哈希现金算法机制,起初该设计是用于限制垃圾邮件发送与拒绝服务攻击。2004年,密码朋克运动早期和重要成员哈尔·芬尼将亚当﹒拜克的哈希现金算法改进为可复用的工作量证明机制。他们的研究又是基于达利亚·马凯与迈克尔·瑞特的学术成果:拜占庭容错机制。正是哈尔·芬尼的可复用的工作量证明机制后来成为比特币的核心要素之一。哈尔·芬尼是中本聪的最早支持者,同时也是第一笔比特币转账的接受者,在比特币发展的早期与中本聪有大量互动与交流。
非对称加密技术
比特币的非对称加密技术来源于以下几项密码学的技术创新:1976年,Sun公司前首席安全官Whitfield Diffie与斯坦福大学教授Martin Hell,在开创性论文《密码学的新方向》首次提出公开钥匙密码学的概念,发明了非对称加密算法。1978年省理工学院的伦纳德·阿德曼、罗纳德·李维斯特、阿迪·萨莫尔三名研究人员,共同发明了公开钥匙系统“RSA”可用于数据加密和签名,率先开发第一个具备商业实用性的非对称RSA加密算法。1985年,Neal Koblitz和Victor Miller俩人,首次提出将椭圆曲线算法(ECC),应用于密码学,并建立公钥加密的算法,公钥密码算法的原理是利用信息的不对称性,公钥对应的是私钥,私钥是解开所有信息的钥匙,公钥可以由私钥反推算出。ECC能够提供比RSA更高级别的安全。比特币使用的就是椭圆曲线算法公钥用于接收比特币,而私钥则是比特币支付时的交易签名。这些加密算法奠定了当前非对称加密理论的基础,被广泛应用于网络通信领域。但是,当时这些加密技术发明均在NSA严密监视的视野之内。NSA最初认为它们对国家安全构成威胁,并将其视为军用技术。直到20世纪90年代末,NSA才放弃对这些非对称加密技术的控制,RSA算法、ECC算法等非对称加密技术最终得以走进公众领域。
不过,中本聪并不信任NSA公布的加密技术,在比特币系统中没有使用RSA公钥系统,原因除了ECC能够提供比RSA更高级别的安全性能外,还担心美国安全部门在RSA留有技术后门。2013年9月,斯诺登就曾爆料NSA采用秘密方法控制加密国际标准,比特币采用的RSA可能留有后门,NSA能以不为人知的方法弱化这条曲线。所幸的是,中本聪神一般走位避开了RSA的陷阱,使用的加密技术不是NSA的标准,而是另一条鲜为人知的椭圆曲线,这条曲线并不在美国RSA的掌握之下。全世界只有极少数程序躲过了这一漏洞,比特币便是其中之一。
生活中我们对文件要签名,签名的字迹每个人不一样,确保了独特性,当然这还会有模仿,那么对于重要文件再加盖个手印,指纹是独一无二的,保证了这份文件是我们个人所签署的。
那么在区块链世界里,对应的就是数字签名,数字签名涉及到公钥、私钥、哈希、加密算法这些基础概念。
首先加密算法分为对称加密算法、非对称加密算法、哈希函数加密算法三类。
所谓非对称加密算法,是指加密和解密用到的公钥和私钥是不同的,非对称加密算法依赖于求解一数学问题困难而验证一数学问题简单。
非对称加密系统,加密的称为公钥,解密的称为私钥,公钥加密,私钥解密、私钥签名,公钥验证。
比特币加密算法一共有两类:非对称加密算法(椭圆曲线加密算法)和哈希算法(SHA256,RIMPED160算法)
举一个例子来说明这个加密的过程:A给B发一个文件,B怎么知道他接收的文件是A发的原始文件?
A可以这样做,先对文件进行摘要处理(又称Hash,常见的哈希算法有MD5、SHA等)得到一串摘要信息,然后用自己的私钥将摘要信息加密同文件发给B,B收到加密串和文件后,再用A的公钥来解密加密串,得到原始文件的摘要信息,与此同时,对接收到的文件进行摘要处理,然后两个摘要信息进行对比,如果自己算出的摘要信息与收到的摘要信息一致,说明文件是A发过来的原始文件,没有被篡改。否则,就是被改过的。
数字签名有两个作用:
一是能确定消息确实是由发送方签名并发出来的;
二是数字签名能确定消息的完整性。
私钥用来创建一个数字签名,公钥用来让其他人核对私人密钥,
而数字签名做为一个媒介,证明你拥有密码,同时并不要求你将密码展示出来。
以下为概念的定义:
哈希(Hash):
二进制输入数据的一种数字指纹。
它是一种函数,通过它可以把任何数字或者字符串输入转化成一个固定长度的输出,它是单向输出,即非常难通过反向推导出输入值。
举一个简单的哈希函数的例子,比如数字17202的平方根是131.15639519291463,通过一个简单的哈希函数的输出,它给出这个计算结果的后面几位小数,如后几位的9291463,通过结果9291463我们几乎不可能推算出它是哪个输入值的输出。
现代加密哈希比如像SHA-256,比上面这个例子要复杂的多,相应它的安全性也更高,哈希用于指代这样一个函数的输出值。
私钥(Private key):
用来解锁对应(钱包)地址的一串字符,例如5J76sF8L5jTtzE96r66Sf8cka9y44wdpJjMwCxR3tzLh3ibVPxh 。
公钥(Public keycryptography):
加密系统是一种加密手段,它的每一个私钥都有一个相对应的公钥,从公钥我们不能推算出私钥,并且被用其中一个密钥加密了的数据,可以被另外一个相对应的密钥解密。这套系统使得你可以先公布一个公钥给所有人,然后所有人就可以发送加密后的信息给你,而不需要预先交换密钥。
数字签名(Digital signature):
Digital signature数字签名是这样一个东西,它可以被附着在一条消息后面,证明这条消息的发送者就是和某个公钥相对应的一个私钥的所有人,同时可以保证私钥的秘密性。某人在检查签名的时候,将会使用公钥来解密被加密了的哈希值(译者注:这个哈希值是数据通过哈希运算得到的),并检查结果是否和这条信息的哈希值相吻合。如果信息被改动过,或者私钥是错误的话,哈希值就不会匹配。在比特币网络以外的世界,签名常常用于验证信息发送者的身份 – 人们公布他们自己的公钥,然后发送可以被公钥所验证的,已经通过私钥加密过的信息。
加密算法(encryption algorithm):
是一个函数,它使用一个加密钥匙,把一条信息转化成一串不可阅读的看似随机的字符串,这个流程是不可逆的,除非是知道私钥匙的人来操作。加密使得私密数据通过公共的因特网传输的时候不需要冒严重的被第三方知道传输的内容的风险。
哈希算法的大致加密流程
1、对原文进行补充和分割处理(一般分给为多个512位的文本,并进一步分割为16个32位的整数)。
2、初始化哈希值(一般分割为多个32位整数,例如SHA256就是256位的哈希值分解成8个32位整数)。
3、对哈希值进行计算(依赖于不同算法进行不同轮数的计算,每个512位文本都要经过这些轮数的计算)。
区块链中每一个数据块中包含了一次网络交易的信息,产生相关联数据块所使用的就是非对称加密技术。非对密加密技术的作用是验证信息的有效性和生成下一个区块,区块链上网络交易的信息是公开透明的,但是用户的身份信息是被高度加密的,只有经过用户授权,区块链才能得到该身份信息,从而保证了数据的安生性和个人信息的隐私性。
公钥和私钥在非对称加密机制里是成对存在的,公钥和私钥可以去相互验证对方,那么在比特币的世界里面,我们可以把地址理解为公钥,可以把签名、输密码的过程理解为私钥的签名。
每个矿工在拿到一笔转账交易时候都可以验证公钥和私钥到底是不是匹配的,如果他们是匹配的,这笔交易就是合法的,这样每一个人只需要保管好TA自己的私钥,知道自己的比特币地址和对方的比特币地址就能够安全的将比特币进行转账,不需要一个中心化的机构来验证对方发的比特币是不是真的。
比特币网络主要会通过以下两种技术保证用户签发的交易和历史上发生的交易不会被攻击者篡改:
非对称加密可以保证攻击者无法伪造账户所有者的签名;
共识算法可以保证网络中的历史交易不会被攻击者替换;
非对称加密
非对称加密算法3是目前广泛应用的加密技术,TLS 证书和电子签名等场景都使用了非对称的加密算法保证安全。非对称加密算法同时包含一个公钥(Public Key)和一个私钥(Secret Key),使用私钥加密的数据只能用公钥解密,而使用公钥解密的数据也只能用私钥解密。
图 2 - 非对称加密特性
比特币使用了非对称加密算法保证每一笔交易的安全,网络中的每一个账户(地址)都是一对秘钥中的公钥,账户的所有者会持有私钥,下面就是一对刚刚生成的比特币地址和私钥4:
Address: 13RTT8MsbAj7o4zL7w4DNNuuwhgGgHqLnK
Private Key: 469d998dd4db3dfdd411fa56574e52b6be318f993ca696cc5c683c45e8e147eb
需要注意的是,使用网站生成比特币地址和私钥是极其危险的做法,我们并不清楚网站是否会存储私钥,所以建议使用比特币的客户端生成公私钥对。
任何人通过上面的地址 13RTT8MsbAj7o4zL7w4DNNuuwhgGgHqLnK 都可以向该账号转账;账号的持有者也可以使用私钥签名交易向其他地址转账,当我们想要向比特币网络中提交一笔新的交易时,需要先构建一个如下所示的交易结构:
{
"txid":"5be7a9e47f56c98e5297a44df52da0475f448ece98bb51489103cdf70653092f",
"hash":"5be7a9e47f56c98e5297a44df52da0475f448ece98bb51489103cdf70653092f",
"version":1,
"size":224,
"vsize":224,
"locktime":0,
"vin": [...],
"vout": [...],
"hex":"0100000001a90b4101e6cbb75e1ff885b6358264627581e9f96db9ae609acec98d72422067000000006b483045022100c42c89eb2b10aeefe27caea63f562837b20290f0a095bda39bec37f2651af56b02204ee4260e81e31947d9297e7e9e027a231f5a7ae5e21015aabfdbdb9c6bbcc76e0121025e6e9ba5111117d49cfca477b9a0a5fba1dfcd18ef91724bc963f709c52128c4ffffffff02a037a0000000000017a91477df4f8c95e3d35a414d7946362460d3844c2c3187e6f6030b000000001976a914aba7915d5964406e8a02c3202f1f8a4a63e95c1388ac00000000",
"blockhash":"0000000000000000000c23ca00756364067ce5e815deb5982969df476bfc0b5c",
"confirmations":5,
"time":1521981077,
"blocktime":1521981077
}
接下来,我们可以使用持有的私钥对整个交易中的全部字段进行签名,然后将签名与交易打包并发送到网络中等待比特币网络的确认就可以了。
在比特币的所有地址中,35hK24tcLEWcgNA4JxpvbkNkoAcDGqQPsP 地址中目前持有 250,000 多个 Bitcoin5,目前的市值大概为 20 亿美元。在只知道地址的情况下,我们来算一下获取该地址对应的私钥需要多长时间。比特币的私钥总共有 256 位,即 22562256 中可能性:
115792089237316195423570985008687907853269984665640564039457584007913129639936115792089237316195423570985008687907853269984665640564039457584007913129639936
目前我们没有较为快捷的破解手段,只能使用暴力破解计算私钥。假设我们使用 IBM 在 2018 年推出的超级计算机 Summit6,它能每秒能做 1.4∗10171.4∗1017 次浮点数计算,假设该计算机可以每秒计算相同次数的公私钥对(计算公私钥对远比一次浮点数计算复杂),想要找到存放 20 亿美元资产的地址对应的私钥需要如下所示的时间:
1.15∗1077365∗86400∗1.4∗1017=2.9∗1052年1.15∗1077365∗86400∗1.4∗1017=2.9∗1052年
我们整个宇宙的存在时间也只是破解该私钥时间的几十亿分之一,所以在目前的计算能力没有革命性突破的前提下,想要通过暴力破解的方式获取公钥对应的私钥只有理论上的可能性,在实践中是完全不可能的7。
共识算法
MySQL 等数据库以行为单位存储数据,而比特币这个分布式数据库中存储的基本单位是区块,区块通过哈希指针连接就会构成一棵树,如下图所示,图中绿色的最长链就是网络的主链。
图 3 - 区块链和主链
如何让网络中的所有节点对下一个区块中的内容达成共识是比特币需要解决的关键问题,只有让节点对数据达成一致才会保证过去的交易不会被篡改,但是作为在公网运行的分布式数据库,它面对的场景非常复杂,需要解决拜占庭将军问题下的分布式一致性问题。
拜占庭将军问题是 Leslie Lamport 在 The Byzantine Generals Problem 论文中提出的分布式领域的容错问题,它是分布式领域中最复杂、最严格的容错模型8。在该模型下,系统不会对集群中的节点做任何的限制,它们可以向其他节点发送随机数据、错误数据,也可以选择不响应其他节点的请求,这些无法预测的行为使得容错这一问题变得更加复杂。
拜占庭将军问题描述了一个如下的场景,有一组将军分别指挥一部分军队,每一个将军都不知道其它将军是否是可靠的,也不知道其他将军传递的信息是否可靠,但是它们需要通过投票选择是否要进攻或者撤退:
图 4 - 拜占庭将军问题
区块链技术使用 共识算法 和激励让多个节点在拜占庭将军场景下实现分布式一致性。比特币使用如下的规则让多个节点实现分布式一致性:
引入工作量证明 — 让节点在提交新的区块之前计算满足特定条件的哈希,取代传统分布式一致性算法中,一人一票(或者一节点一票)的设定;
引入最长链是主链的设定 — 只有主链上的交易才被认为是合法交易;
引入激励 — 提交区块的节点可以获得比特币奖励;
通过以上的规则,各个节点会在最长的链上计算哈希,努力提交合法的区块。然而一旦节点中有人掌握了 51% 以上的计算能力,它能通过强大的算力改变区块链的历史。因为区块具有连续性,所以前一个区块的改变会使后一个区块计算的哈希失效,如图 4 所示,如果攻击者需要改变主链中的倒数第三个黄色区块,它需要连续构建四个区块才能完成对历史的篡改,其他的节点才会在这条更长的链上继续计算:
图 4 - 51% 攻击
1使用如下所示的代码可以计算在无限长的时间中,攻击者持有 51% 算力时,改写历史 0 ~ 9 个区块的概率9:
#include
#include
double attackerSuccessProbability(double q, int z) {
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k = z; k ) {
double poisson = exp(-lambda);
for (i = 1; i = k; i )
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}
int main() {
for (int i = 0; i 10; i ) {
printf("z=%d, p=%f\\n", i, attackerSuccessProbability(0.51, i));
}
return 0;
}
通过上述的计算我们会发现,在无限长的时间中,占有全网算力的节点能够发起 51% 攻击修改历史的概率是 100%;但是在有限长的时间中,因为比特币中的算力是相对动态的,比特币网络的节点也在避免出现单节点占有 51% 以上算力的情况,所以想要篡改比特币的历史还是比较困难的,不过在一些小众的、算力没有保证的一些区块链网络中,51% 攻击还是极其常见的10。
防范 51% 攻击方法也很简单,在多数的区块链网络中,刚刚加入区块链网络中的交易都是未确认的,只要这些区块后面追加了数量足够的区块,区块中的交易才会被确认。比特币中的交易确认数就是 6 个,而比特币平均 10 分钟生成一个块,所以一次交易的确认时间大概为 60 分钟,这也是为了保证安全性不得不做出的牺牲。不过,这种增加确认数的做法也不能保证 100% 的安全,我们也只能在不影响用户体验的情况下,尽可能增加攻击者的成本。
总结
研究比特币这样的区块链技术还是非常有趣的,作为一个分布式的数据库,它也会遇到分布式系统经常会遇到的问题,例如节点不可靠等问题;同时作为一个金融系统和账本,它也会面对更加复杂的交易确认和验证场景。比特币网络的设计非常有趣,它是技术和金融两个交叉领域结合后的产物,非常值得我们花时间研究背后的原理。
比特币并不能 100% 防止交易和数据的篡改,文中提到的两种技术都只能从一定概率上保证安全,而降低攻击者成功的可能性也是安全领域需要面对的永恒问题。我们可以换一个更严谨的方式阐述今天的问题 — 比特币使用了哪些技术来增加攻击者的成本、降低交易被篡改的概率:
比特币使用了非对称加密算法,保证攻击者在有限时间内无法伪造账户所有者的签名;
比特币使用了工作量证明的共识算法并引入了记账的激励,保证网络中的历史交易不会被攻击者快速替换;
通过上述的两种方式,比特币才能保证历史的交易不会被篡改和所有账户中资金的安全。
加密算法是数字货币的基石,比特币的公钥体系采用椭圆曲线算法来保证交易的安全性。这是因为要攻破椭圆曲线加密就要面对离散对数难题,目前为止还没有找到在多项式时间内解决的办法,在算法所用的空间足够大的情况下,被认为是安全的。本文不涉及高深的数学理论,希望高中生都能看懂。
密码学具有久远的历史,几乎人人都可以构造出加解密的方法,比如说简单地循环移位。古老或简单的方法需要保密加密算法和秘钥。但是从历史上长期的攻防斗争来看,基于加密方式的保密并不可靠,同时,长期以来,秘钥的传递也是一个很大的问题,往往面临秘钥泄漏或遭遇中间人攻击的风险。
上世纪70年代,密码学迎来了突破。Ralph C. Merkle在1974年首先提出非对称加密的思想,两年以后,Whitfield Diffie和Whitfield Diffie两位学者以单向函数和单向暗门函数为基础提出了具体的思路。随后,大量的研究和算法涌现,其中最为著名的就是RSA算法和一系列的椭圆曲线算法。
无论哪一种算法,都是站在前人的肩膀之上,主要以素数为研究对象的数论的发展,群论和有限域理论为基础。内容加密的秘钥不再需要传递,而是通过运算产生,这样,即使在不安全的网络中进行通信也是安全的。密文的破解依赖于秘钥的破解,但秘钥的破解面临难题,对于RSA算法,这个难题是大数因式分解,对于椭圆曲线算法,这个难题是类离散对数求解。两者在目前都没有多项式时间内的解决办法,也就是说,当位数增多时,难度差不多时指数级上升的。
那么加解密如何在公私钥体系中进行的呢?一句话,通过在一个有限域内的运算进行,这是因为加解密都必须是精确的。一个有限域就是一个具有有限个元素的集合。加密就是在把其中一个元素映射到另一个元素,而解密就是再做一次映射。而有限域的构成与素数的性质有关。
前段时间,黎曼猜想(与素数定理关系密切)被热炒的时候,有一位区块链项目的技术总监说椭圆曲线算法与素数无关,不受黎曼猜想证明的影响,就完全是瞎说了。可见区块链项目内鱼龙混杂,确实需要好好洗洗。
比特币及多数区块链项目采用的公钥体系都是椭圆曲线算法,而非RSA。而介绍椭圆曲线算法之前,了解一下离散对数问题对其安全性的理解很有帮助。
先来看一下 费马小定理 :
原根 定义:
设(a, p)=1 (a与p互素),满足
的最下正整数 l,叫作a模p的阶,模p阶为(最大值)p-1的整数a叫作模p的原根。
两个定理:
基于此,我们可以看到,{1, 2, 3, … p-1} 就是一个有限域,而且定义运算 gi (mod p), 落在这个有限域内,同时,当i取0~p-2的不同数时,运算结果不同。这和我们在高中学到的求幂基本上是一样的,只不过加了一层求模运算而已。
另一点需要说明的是,g的指数可以不限于0~p-2, 其实可以是所有自然数,但是由于
所以,所有的函数值都是在有限域内,而且是连续循环的。
离散对数定义:
设g为模p的原根,(a,p) = 1,
我们称 i 为a(对于模p的原根g)的指数,表示成:
这里ind 就是 index的前3个字母。
这个定义是不是和log的定义很像?其实这也就是我们高中学到的对数定义的扩展,只不过现在应用到一个有限域上。
但是,这与实数域上的对数计算不同,实数域是一个连续空间,其上的对数计算有公式和规律可循,但往往很难做到精确。我们的加密体系里需要精确,但是在一个有限域上的运算极为困难,当你知道幂值a和对数底g,求其离散对数值i非常困难。
当选择的素数P足够大时,求i在时间上和运算量上变得不可能。因此我们可以说i是不能被计算出来的,也就是说是安全的,不能被破解的。
比特币的椭圆曲线算法具体而言采用的是 secp256k1算法。网上关于椭圆曲线算法的介绍很多,这里不做详细阐述,大家只要知道其实它是一个三次曲线(不是一个椭圆函数),定义如下:
那么这里有参数a, b;取值不同,椭圆曲线也就不同,当然x, y 这里定义在实数域上,在密码体系里是行不通的,真正采用的时候,x, y要定义在一个有限域上,都是自然数,而且小于一个素数P。那么当这个椭圆曲线定义好后,它反应在坐标系中就是一些离散的点,一点也不像曲线。但是,在设定的有限域上,其各种运算是完备的。也就是说,能够通过加密运算找到对应的点,通过解密运算得到加密前的点。
同时,与前面讲到的离散对数问题一样,我们希望在这个椭圆曲线的离散点阵中找到一个有限的子群,其具有我们前面提到的遍历和循环性质。而我们的所有计算将使用这个子群。这样就建立好了我们需要的一个有限域。那么这里就需要子群的阶(一个素数n)和在子群中的基点G(一个坐标,它通过加法运算可以遍历n阶子群)。
根据上面的描述,我们知道椭圆曲线的定义包含一个五元祖(P, a, b, G, n, h);具体的定义和概念如下:
P: 一个大素数,用来定义椭圆曲线的有限域(群)
a, b: 椭圆曲线的参数,定义椭圆曲线函数
G: 循环子群中的基点,运算的基础
n: 循环子群的阶(另一个大素数, P )
h:子群的相关因子,也即群的阶除以子群的阶的整数部分。
好了,是时候来看一下比特币的椭圆曲线算法是一个怎样的椭圆曲线了。简单地说,就是上述参数取以下值的椭圆曲线:
椭圆曲线定义了加法,其定义是两个点相连,交与图像的第三点的关于x轴的对称点为两个点的和。网上这部分内容已经有很多,这里不就其细节进行阐述。
但细心的同学可能有个疑问,离散对数问题的难题表现在求幂容易,但求其指数非常难,然而,椭圆曲线算法中,没有求幂,只有求乘积。这怎么体现的是离散对数问题呢?
其实,这是一个定义问题,最初椭圆曲线算法定义的时候把这种运算定义为求和,但是,你只要把这种运算定义为求积,整个体系也是没有问题的。而且如果定义为求积,你会发现所有的操作形式上和离散对数问题一致,在有限域的选择的原则上也是一致的。所以,本质上这还是一个离散对数问题。但又不完全是简单的离散对数问题,实际上比一般的离散对数问题要难,因为这里不是简单地求数的离散对数,而是在一个自定义的计算上求类似于离散对数的值。这也是为什么椭圆曲线算法采用比RSA所需要的(一般2048位)少得多的私钥位数(256位)就非常安全了。
比特币的核心技术包括1、非对称加密技术 2、点对点传输技术 3、哈希现金算法机制。
1.非对称加密技术和对称加密技术最大的不同就是有了公钥和私钥之分。非对称加密算法需要两个密钥:公开密钥(publickey)和私有密钥(privatekey)。公开密钥与私有密钥是一对,如果用公开密钥对数据进行加密,只有用对应的私有密钥才能解密;如果用私有密钥对数据进行加密,那么只有用对应的公开密钥才能解密。公钥是公开的,私钥是保密的。 由于不涉及私钥的传输,整个传输过程就变得安全多了。后来又出现了具备商业实用性的非对称RSA加密算法以及后来的椭圆曲线加密算法(ECC),这些都奠定了加密算法理论的基础,但是美国国家安全局NSA最初认为这些技术对国家安全构成威胁,所以对这些技术进行了严密的监控,知道20世纪90年代末NSA才放弃了对这些技术的监控,这些非对称技术才最终走入了了公众的视野。这项技术对应到比特币场景中就是比特币的地址和私钥。
2.点对点传输技术顾名思义,就是无需中心服务器、个体之间可以相互传输信息的技术,P2P网络的重要目标就是让所有客户端都能提供资源,包括宽带、存储空间和计算能力。 对应到比特币网络中就是利用点对点的技术实现真正的去中心化。
3.哈希现金算法机制就是让那些制造垃圾邮件的人付出相应的代价!发送者需要付出一定的工作量,比如说哈希运算,几秒钟时间对于普通用户不算什么,但对于垃圾邮件的发送者每封邮件都要花几秒钟的时间,这样的成本是没有办法负担的。同时每次运算都会盖上一个独一无二的时间戳,这样就能保证邮件发送方不能重复使用一个运算结果。 对于比特币而言也是同样的道理,如何保证一笔数字货币没有被多次消费(Double Spending),就类似于验证一封邮件没有被多次发送,所以就要保证每一笔交易顺利完成,必须要付出一定的工作量(proof of Work),并且在完成交易时盖上一个时间戳表示交易完成的时间。
正加licai内容推荐 | ||
OK交易所下载 | USDT钱包下载 | 比特币平台下载 |
永续合约玩法 | 钱包使用教程 | 挖矿教程入门 |