首页 > 区块链知识 > 正文

第一课:密码学原理——《区块链技术与应用》一课学习笔记

鹿鸣于野UMU 2020-02-14 16:25

  比特币:crypto-currency

  密码学两个功能:哈希+签名

  一、第一个功能:哈希

  哈希函数:cryptographic hash function,两个重要性质:哈希碰撞与隐秘性。

  (一)collision resistance,collision即哈希碰撞。

  X≠y,h(x)=h(y)

  两个不同的输入值,算出来的值一样。哈希碰撞不可避免,因为输入空间远远大于输出空间(2的256次方)。

  暴力求解,遍算所有,找到两个不同的XY,算得的值H(x)与H(y)一样。即brute-force。但工作量太大,实际中不可行。

  H(m),message digest,用来检测对message的篡改。如有人改m,则H(m)也改变。难以找到个m’,其值h(m’)恰好等于h(m)。

  上传文件时,先算个哈希值h(m)存在本地,重新下载文件后,再算个哈希值,看是否等于原来的h(m),以确认上传的文件没有被篡改。这就是collision resistance的一个用处。

  没有哪个哈希函数可以在数学上证明可以是collision resistance,该性质无法理论证明,只能实际验证,基于经验认为它是collision resistance。

  如MD5,曾很流行,但现在已知道如何去认为制造哈希碰撞,于是这个MD5就不能再使用,会被造假。

  (二)hiding,哈希函数的制造是不可以逆的,只可以X到H(x),不可以H(x)反推至X。

  其实算X也是有办法,即上述的蛮力破解法。Hiding性质要求X足够大、分布比较均匀,以致无法通过蛮力破解法计算。

  Hiding可以与collision resistance一起,来实现digital commitment(也称之为digital equivalent of a sealed envelope)。

  digital commitment举例:在预测第二天股市时,把预测结果X算出一个哈希值H(X),然后再把H(X)公布出去,基于hiding的性质,所以H(X)也隐藏了预测结果,等到第二天收盘时,再公布预测结果。

  因为collision resistance的缘故,预测结果也无法篡改,因为一旦篡改,就与当初的哈希值H(x)不一致了。X到H(x)的唯一性(collision resistance),X 到H(X)的不可逆性(hiding),从而就起到sealed envelope的功能。

  实际操作中的细节:hiding的输入空间大、分布均匀。常用做法是输入后加个随机数H(X//nonce),一起取哈希。从而保证输入足够随机、分布足够均匀。

  (三)比特币中要求的哈希函数还需具有第三个性质,puzzle friendly.

  puzzle friendly意思是说哈希值事先不可预算,为了保证哈希值落在某个范围内,只能一个个去算。

  之所以叫puzzle friendly,挖矿就是要找这么一个随机数nonce。这个Nonce 和区块矿头里的其他信息合在一起,进行输入,取出一个哈希来,这个哈希值要小于等于某个指定的目标阈值,即H(block header)≤target。

  block header中有很多个域,其中某个域就是我们可以设置的随机数nonce.挖矿的过程就是不断去算这个随机数,使得block header取哈希之后,落在指定的范围以内,即在target space以内。

  Puzzle friendly就是指没有捷径,只能通过不断的尝试nonce取得符合要求的解,所以这个证明才可以用来作为工作量证明,proof of work。你挖到了矿,一定是因为你做了大量的工作,没有捷径,所以这个挖矿的过程需要很多的工作量,才能找到一个符合要求的nonce。

  但一旦有人找到Nonce,发布出去,其他人想验证这个Nonce是否正确是很容易的,只要算一次哈希值即可,是否在目标阈值以内。挖矿很难,验证很容易,difficult to solve, but easy to verify.

  比特币中用的哈希函数叫SHA-256,secure hash algorithm.

  二、第二个功能:签名

  比特币系统中的账户管理:去中心化系统中,每个用户自行决定开户,无需被批准。

  开户过程只需设立一对公钥和私钥(Public key,private key)即一个账户。

  公私钥来自非对称的加密体系,即asymmetric encryption algorithm。

  最早的加密体系是对称的,即没有词首的a。

  Encryption key,密钥,双方商量好。双方用同一个密钥。但密钥分发不方便,这也是对称体系的弱点。

  非对称里用一对公私钥,加密用A的公钥,解密用A的私钥。公钥不需要保密,私钥要保密,但私钥可以保存在本地,不需传播出去。

  比特币系统中实际信息是不加密的,是公开的,而公私钥在此的作用是作为签名在用。个人在发布交易时,要用我的私钥来发布这个签名,别人可以用我的公钥来验证我的签名。

  两个人生成的公私钥对恰好相同,该如何?理论上可行,实际上不可行,概率极低。

  这里的假设是:产生公私钥时,这里有一个随机源,a good source of randomness。如果随机源不好,则可能导致两个人的公私钥对一样。

  比特币签名算法中,生成公私钥对时有好的随机源,在每次生成签名时也有好的随机源,只要一次随机源不好,就可能泄露私钥,于是就全完了。

  哈希和签名可以一起作用:比特币中,先用message生成哈希,再对哈希值签名。

  

阅读更多

上一篇:第一个零知识证明协议:二次剩余

下一篇:第二课:数据结构——《区块链技术与应用》一课学习笔记

您可能喜欢:

关于我们联系我们作者投稿
Copyright © 2013 比特巴手机版
币圈人都爱上的网站,新闻行情教程人物测评资讯大全