加载中…
个人资料
风间彻
风间彻
  • 博客等级:
  • 博客积分:0
  • 博客访问:233,256
  • 关注人气:63
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

关于量子计算机,我来说点什么

(2014-06-11 16:06:37)
    首先,先介绍一下我自己,我是个网络安全方向的大学老师,博士,参与过量子计算机和安全算法方面的研究,也有意无意的推动了世界上第一台矿机的出现。我很庆幸我参与到了比特币的这个行业,也许,我的研究注定我参与到这个行业中,从穷苦度日到现在的财务自由,造化弄人,还是天命使然?

    常见的论调,一旦比特币算法被破解,比特币连废纸都不是,比特黑常拿出量子计算机来说事。的确,这是科学前沿问题,很多比特人并不了解,那我来给大家对这量子计算机概念进行解释,希望大家理解这些东西对比特币行业的意义和影响。本文阅读至少需要计算机本科知识和一点点浅显的量子物理知识,文章较长,希望您又足够的耐心。

    先说量子计算机,量子计算机真的有实物,并非子虚乌有.
关于量子计算机,我来说点什么 - superay100 - 小样ray

关于量子计算机,我来说点什么 - superay100 - 小样ray

    这是GOOGLE买的D-WAVE,这是一台以绝热量子退火方式工作的商用量子概念的计算机,和真正意义上的量子门电路计算机有很大区别,他的作用是求解离散值上最优化问题(qubo问题),虽然宣称是多项式时间求解,实际上,没有任何证据证明这一点。

    最优化问题是指给定一个函数F,寻找一个元素A使得对于任意函数定义域中的元素x,F(A)<F(x)或者F(A)>F(x)的问题,这个问题是无数重要问题的基础,不过很不幸,这个问题是NP-HARD的,也就是普通计算机无法求解的,(跑题一下,NP-HARD问题没什么神秘的,扫雷,星际,这都是典型的NP-HARD问题)D-WAVE采用量子隧穿效应实现上述功能。

    量子隧穿又是什么呢?就是量子达到障碍物前,因为量子测不准原理,量子的位置是不确定的,这样就又概率穿过障碍物达到障碍物的另一边的穿墙术,量子隧穿的概率随着障碍物的宽度迅速降低,你不用担心你的身体哪天因为量子隧穿而分家。量子隧穿效应实际是我们半导体科技的基础,所谓的电子显微镜的工作原理也是量子隧穿,这是我们身边很广泛应用的技术。
关于量子计算机,我来说点什么 - superay100 - 小样ray
    D-WAVE求解一个问题的过程大致如同蒸馏提纯,或者说是筛大米
    给定一个函数,然后编码这个函数为某些量子门,也就是说这些量子门能操作量子比特,然后输入大量的量子比特相近的量子,(在某种条件下,量子携带的比特信息是相近的,比如在80度的时候,5%的水呈现气态,95%的水呈现液态,我们可以对大量80度的水分子编码数据0.95,但哪个水分子是气态哪个水分子是液态,并不知道)然后通过量子门电路给量子携带的量子比特加入函数操作,把可调节的量子障碍物放在量子周围,满足条件的量子才能引发较高概率的隧穿,观察隧穿过来的量子个数,如果观测到隧穿量子,那么现在的量子输入中包含能使最优化问题成立的量子比特,调整量子输入,和量子障碍,使得量子输入刚好能保证大量的隧穿,然而稍微调节参数,就观测不到量子隧穿,这样,就完成了最优化问题的求解,然后测量输入的量子的量子比特,得到数值解。(量子比特的概念自己百度吧,实在是篇幅耗不起了,)

    那么根据上面的求解过程,我们发现D-WAVE有什么缺点了么?
    1. D-WAVE不具有编程能力,D-WAVE只能解决最优化问题,不能干别的,连1+1=?都没法处理,不能用于破解私钥。
    2. 如果利用求解sha256达到最小值的方法进行挖矿,理论上是可行的,不过D-WAVE能求解的函数是有需求的,也就是他要求函数是个准平滑函数,这样才可能进行蒸馏提纯,而SHA256类的HASH函数只要一个bit有区别,输出可能差别极大,是不满足平滑函数的定义的,也就是说,D-WAVE的量子绝热退火不能处理SHA256算法。
    3. D-WAVE蒸馏提纯的是一个数的区间范围,而不是一个数,也就是说,即便SHA256在某些条件下满足准平滑函数的时候,得到的也是一个区间,在这个区间里哪个数能两次hash出一个share,并不知道。
    4. 总之,D-WAVE在处理BTC方面废物一个。

    科学界对D-WAVE是不是量子计算机现在还没有定论,真正意义上的量子计算机是量子门电路计算机,或者称量子线路,但目前,量子线路的计算机还没有真正商业化。我国一直走在量子计算机的世界前列,科大的量子小组非常非常的牛逼,不过现在发展的最高水平也就是求解2元1次方程组的层次。

    说一些量子计算机求解问题时你会遇到的问题:
    1. 不可克隆定理(No-Cloning Theorem)是指量子力学中对任意一个未知的量子态进行完全相同的复制的过程是不可实现的,该定理可以通过反证法基于量子态的叠加原理证得。1982年Wootters,Zurek和Dieks在论文《单量子态不可克隆》论文中提出了著名的单量子不可克隆定理,也即:在量子力学中,不存在这样一个物理过程:实现对一个未知量子态的精确复制,使得每个复制态与初始量子态完全相同。  该定理的推论指出:未知量子比特不可能精确复制,使得每个复制比特与初始量子比特相同
    不可克隆定理直接导致的结果是: 在量子计算机的程序里没有复制粘贴,没有函数赋值,没有变量,没有程序调用,没有中断,没有异常处理,没有。。。。  基本上你能想到的编程里的东西,都是不可能实现的。
    2. 测量问题(薛定鄂的猫)。 对任意量子的观察行为将造成量子波函数的塌缩,而塌缩的结果是随机的。也就是说if语句在量子计算机里没有,一旦if,就意味着对量子的测量,测量后,这个量子将不携带量子信息,程序就结束了。没有if,也就是没有while,do-while,for,loop等程序控制功能。
    3. 同时因为测量问题,因为测量的结果是随机的,只能对大量有相同量子态的量子(这和不可克隆定理很神奇的并不矛盾)进行测量才能得到量子中所携带的信息,而且是测量的越多,结果越准确,本质来讲,量子信息不是1,2这样的int数,而是3%的可能是1.0正负10^-3,97%的可能是2正负10这样的数,由于没有好用的int数据类型,所有密码学上基于整形的算符都非常非常的困难。
    4. 还有好多好多,我没法一一举例了,反正量子计算机的程序和计算机的程序根本不是一个领域里的东西,做量子计算机的人都是学物理的,因为他们没有学计算机人的天生的思维定势,想想,在没有变量,没有赋值,没有程序控制,没有数据类型的情况下写程序,学计算机的 肯定都疯了。

    在以上的问题存在的前提下,量子计算机基本失去了编程能力,只能做到给定一个函数,然后将函数施加在输入上,然后通过观察输出,碰撞出问题的解,量子计算机必须通过电子计算机的配合,才能完成工作。

    量子门电路计算机目前已知能处理量子算法主要有基于Fourier变换的量子算法(常数时间处理快速富利叶变换)、量子搜索算法(grover算法为代表,平方级别加速)、阿贝尔隐含子群量子算法(shor算法为代表,指数级别加速)、绝热量子计算进行量子模拟。其他的问题,现在要走的路还太长太长。

    SHOR算法干嘛用的,大数多项式时间因式分解,基本上一个数又多少位,SHOR算法就能在多少次运算的条件下给出因式分解,SHOR的实现这是量子计算机研究领域很古老的问题了,效果非常好。那么SHOR直接破解的就是RSA加密。

    加密有对称加密和非对称加密,非对称加密现在用的最多的就是RSA。 HTTPS等常见通讯都是结合了对称加密和非对称加密,
    对称加密很简单,比如密钥是1,本来我想传明文ABCD,然后我把每位加1得到密文BCDE发送,接受方也知道密钥是1,然后将BCDE每位减1,得到明文ABCD。对称加密的速度很快,而且CPU里面已经集成了AES,DES等加密算法的ASIC,所以,网络上传输的较大的数据都是对称加密的,
    但在双方都没有密钥的时候,怎么把密钥传过去,这时就需要RSA为代表的非对称加密了,RSA就相当与邮箱,每个自己有邮箱的钥匙,这个并不公开,私钥,然后你公开你的邮箱地址 北京XXX信箱,这个就是公钥,然后信投到信箱里,只有你能打开,完成了加密通讯过程。
    RSA的加密过程中,用两个大素数的积作为公钥,然后这个和数的一个素因子就私钥,从而完成加密通讯。

    RSA的安全在于大数的因式分解是非常非常困难的,RSA一般用1000位以上的大数,用我们的计算机一般要算几个银河系灭亡的时间才能算出,因此RSA一统非对称加密的大半壁江山。

    天有不测风云, 因式分解在数学上居然是隐含子群问题,因此,量子计算机可以快速破解RSA。隐含子群是一大堆问题,隐含子群太隐晦,可以理解成求解周期函数的周期的问题推广出来的一系列问题,椭圆曲线上离散对数ELGARMA也是隐含子群问题,几乎一大半的非对称加密都是用的隐含子群,也就是大家传言的量子计算机能破加密的原因。
  
    目前也又不依靠隐含子群的非对称加密,比如基于格的,基于纠错码的加密不是隐含子群问题,因此在量子计算机广泛普及后,我们也又办法安全通讯,或者干脆直接使用量子通讯,量子通讯只要有人观察,就会造成信息的不可逆的消失,这样根本不可能破解。

    虽然量子计算机能破解RSA,但现在的问题是,量子退相干太快了,也就是量子携带量子信息的时间太短了,我们知道观测会造成量子信息的丢失,如果量子在环境中,哪怕是在真空中,真空的量子涨落也会极大的影响量子信息。类似内存,不供电瞬间信息就消失了,量子一旦进入量子线路,是没办法充电的,量子信息通过几个量子门后波函数就塌缩的七七八八了,同时门电路的准确性还不足,每个门电路的准确性只有90%左右,比如一个门电路的准确度是95%,那么一个线路如果含15个部件,那么准确率46%,已经低于50%了,这个线路根本就不能用了。因此,目前的量子线路还没办法弄的太复杂,也就因式分解个15=3*5就基本上极限了,在基础理论科学没有重大突破之前,量子计算机完全破解RSA还不太现实,这也就是量子计算机明明可以破解我们常用的加密通讯,但我们现在还能好好的利用HTTPS进行登录网上银行和科学上网的原因。

    上面说的是量子计算机利用隐含子群问题可以求解很多问题,那么可不可能利用隐含子群来求解SHA256和用于私钥的ECDSA呢,回答是不能。
  
    已知地址的情况下,私钥要经过ECDSA签名获得公钥,然后公钥经过SHA256,RIPEMD-160两种HASH算法生成地址,地址位数远少于私钥的位数,也就是这些算法都是有损的,一本书,翻译成英文,然后把翻译好的前半本书给你,后半本书扔掉,无论你英文再牛逼,也没法用前半本翻译推出原文,一个压过几遍的JPG,无论你的算法再牛逼,也无法恢复原来TIFF的画质。也就是说,量子计算机无论多牛逼,也不能通过地址得到你的私钥,这跟计算能力无关。用GROVER搜索也一样,没法获得私钥。

    但是公钥在你给人发送币的时候会被公开以证明这个交易确实是你发送的,而不是被伪造的,因此,发送过币的地址存在公钥公开的问题,而公钥到你的私钥只隔着一层ECDSA签名算法,这个是量子计算机能否破解BTC的关键。而没发过币的地址,或找零地址,可认定,是量子计算机无法攻击的。

    ECDSA作为椭圆曲线上基于离散对数上的数字签名方法,理论上讲,有可能被量子计算机攻破的,不过,只需要钱包程序升级一下,对钱包中的地址设置一个脏位,发送比特币时,如果接受方地址发过币,则自动重定向到他钱包中其他地址上去,这个问题就解决了,无需改动网络协议,此时,需要对外公布地址的时候,就要公布一个地址的集合,或者用类似花生壳一样的机制让发送方可以查询接受方的钱包中的若干地址,这会带来些许麻烦,现在在量子计算机还没实用化的今天,还不需要这么做,如果真的有研究报道,量子计算技术实用化时,基金会重新发一个钱包,并告知大家转到新钱包就可以了,无需升级比特币的协议,更不会造成硬分叉。

    即便量子器件获得重大突破,退相干,准确率的问题都能解决,也只能拿来攻击网银,没法攻击BTC。

    比特币里没有Fourier变换和量子模拟,因此,量子计算机没法用Fourier变换和量子模拟对比特币进行攻击

    因此,最有可能出问题的,就是GROVER搜索算法搜索能快速产生share的碰撞解,对挖矿进行攻击。
   所有的搜索问题都等价与用小的存储空间在大的存储空间中比对, 电子计算机相当与盲人,只能一格一格的摸过去,而量子计算机相当与一个大近视眼,一开始,要搜索的东西离的很远,看的很模糊,只能看个大概的区域,然后把这个区域放大,再在这个区域中找更接近的区域。量子计算机相当与传统计算机是平方级别的加速,无法达到指数级别。
  挖矿是已知交易数据K,求解X,使得SHA256( SHA256  (K+X))<N/DIFF, 这本质来讲就是搜索问题,可以预见的是,

    量子计算机一旦广泛应用,肯定可以用来挖矿,

    量子计算机就相当与矿机中的矿机,那么量子计算机的出现,会不会造成51%?

    先回答我这个问题,GPUminer刚出现的时候,为什么这东西开源了?ASIC出现的时候,为什么南瓜张自己不留下来,反而是卖出去了?
    1. 单台量子计算机无法达到攻击BTC网络的能力。
    量子计算机虽然可以平方级别减少操作次数,但量子计算机本身是很慢的,即便平方以后,也没法和海量的矿机竞争,因此单台量子计算机并不能完成51%攻击,平方级别看着牛逼,想想比特币算能这一年都涨了几个平方了,面对量子计算机对网络算能的攻击,天空飘来5个字,那都不是事。
    2.量子计算机造价不菲
    3.理性的挖矿者没有摧毁BTC网络 的可能,即便现在来看,算能集中的情况也很严重,Bitfury一个人就有全网30%以上的算能,黑庄东,翟文杰,烤猫他们的算能也很恐怖,他们算能加一起,肯定超过全网50%,比特币现在还不是活的好好的。
    4. 量子计算机的技术是全球竞争的技术,一旦面市,肯定被广泛的分散开,不可能集中在某些人的手里
    以上,造成了量子计算机实际上对矿机行业造成了新的洗牌,大家持有的矿机变成费铁而已,别的,没啥。哦,网络算能又增加了,网络安全又得到了新的提高。

    量子计算机的出现,相当与AVALON上线的过程,只能造成币值暴涨。

    顺便,说说大家对量子通讯的常见误解,纠缠态粒子之间的远程同步现象的速度传输超过光速,目前测量的结果是光速的10^40倍左右,能不能利用这个来进行超光速通讯呢?不能。
但是实际上呢, 按照目前得出的量子纠缠态实验结果来看, 真正的"所谓超光速通讯"的真相是这样的, 我用一个简单的例子来说明一下, 大家就知道这是怎么回事了.
  例子: 有两张扑克牌, 一张是红心A, 另一张是黑桃A, 我们把它们放到两只密封的盒子里. 如果不打开盒子,我们无法知道其中的某个盒子里到底是哪一张牌. (我们用这两张牌来形容一对处于纠缠态的量子)
  现在一架星际飞船带上其中的一个盒子(随机选择)开始星际旅行,另一个盒子则放在地球上. 此时两个盒子都处于密封状态. 直到飞船抵达5光年外的半人马座. 飞船上的宇航员按照事先约定打开盒子, 当他打开盒子看到盒子里的那张牌是红心A的那一瞬间, 他就瞬间"知道"处于5光年外的地球上的那只密封盒子里的牌是黑桃A了(瞬间跨越5光年知道另一处的结果哦). 
  从宇航员打开半人马座上的那只箱子到他"知道"地球上那只盒子里面的牌的时间, 如果抛开人的神经传递信息所需要的时间的话, 那么这种"通讯"确实是瞬时的, 肯定是"超光速"的. 

  但是实际上呢, 大家看了这个实验也知道了, 这种"超光速通讯"毫无实际意义, 因为根本不能传递有效的信息. "不知道"不等于"不存在", 所能改变的仅仅在于从"不知道"到"知道"这一过程而已, 不再具有任何其他的意义.
  如果想要这个实验变成有意义,那么还得加上另一个步骤: 宇航员将他所知道的结果发送回地球, 等到5年之后(无线电波传播的时间), 地球上的人得知如下信息: 5年前半人马座的宇航员"知道"了我们地球上的这个盒子里的牌是XXX. 
  这中间的荒谬之处就是: 必须有"超光速"的通讯方式才能得到"超光速"通讯的结果. 

    因此,量子纠缠无法让比特币超光速传输,进而利用量子纠缠让比特币实现跨星球货币的可能性=0,唯一可能的是,有人跨宇宙搬砖,实现汇率的准互通,然后,在引入大量对冲机制后,实现不太精准的贸易。

    那么有没有超光速通讯呢?有,比如量子隧穿,量子隧穿是超光速的,有实验实现了2.43倍光速的量子隧穿通讯,在上面载波了一首欢乐颂,但量子隧穿的通讯半径是nm级别,没可能远距离通讯。同时,我国在光纤中也实现了信号的超光速,这个超光速不是光子速度超光速,是波的包络超光速了,相当于我拿强光手电筒乱摇,在足够远的距离上,光班的移动速度超光速。利用这些,没准能把比特币弄成全宇宙货币,不过,天知道这科技树能不能暴出来。


    最后,对下一篇文章进行预告,如果SHA256,或者椭圆曲线真的被破解了,比特币还是比特币么?

    第一次写科普文章,可能写的比较深,或者举的例子不太恰当,各位多包含。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:量化交易
后一篇:二元期权
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇量化交易
    后一篇 >二元期权
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有