北大《区块链技术与应用》公开课——比特币密码学原理

longago队长发布在 技术文档
 9398  0

内容整理自 北京大学肖臻老师《区块链技术与应用》公开课

加密货币(Crypto-currency)

加密货币并不加密,区块链上所有的交易内容都是公开的,包括账户地址,转账金额等。

比特币用到密码学的两个功能:

1.哈希(哈希函数工作原理自行百度) Cryptographic hash function

2.签名 Signature

哈希的两个性质:

1.collision resistance

collision 指的是哈希碰撞:如果x != y,Hash(x) = Hash(y),这就是哈希碰撞,两个不同的输入算出的哈希值是相等的,不可避免。因为无限的输入映射到有限的输出(256位的哈希值只有2^256个输出,但是输入是无限的),按照鸽笼原理,必然有两个输入映射到同一输出。

collision resistance并不是说不会出现哈希碰撞,碰撞是客观存在的。该性质是说没有什么高效的方法人为地去制造哈希碰撞。除非是通过brute-force方式去遍历所有输入的可能性,看哪个哈希值算出来正好相等。但是实际中这种方式不可行,因为输入空间大,工作量大。

该性质作用:可以用来对一个message求digest。比如有一个message是m,它的哈希值H(m)是digest.可以用来检测对message的篡改。比如有人改了m的内容,它的哈希值就会发生变化.该性质保证你找不到一个m,使得哈希值H(m) = H(m)。没有办法能够篡改内容,而又不被检测出来。

目前没有哪个哈希函数在数学上能够证明collision resistance,该性质是证明不出来的,只能通过实践中的经验去证明。有一些哈希函数以前认为是collision resistance,但是后来找到了制造哈希碰撞的方法,比如MD5.

2.hiding?

哈希函数计算过程是单项,不可逆的。

理想状态下,给定x生成H(x),无法通过H(x)推出x。换句话说就是H(x)没有泄露有关x的任何信息。

想要知道输入的信息也是有办法的,就是通过暴力算法(brute-force),遍历所有可能取值。

成立条件:1)输入空间足够大,使得蛮力求解的方法是不可行的? 2)输入分布均匀,各种取值的可能性都差不多

该性质作用:collision resistance 和?hiding 两个性质结合实现 digital commitment / digital equivalent of a sealed envelope.

现实生活中,a sealed envelope的作用:假如有人能预测股市,可以预测第二天哪些股票会涨停。要如何证明他预测的是否准确?如果预测结果提前公布,可能会影响股市,所以预测结果不能提前公开。但如果不提前公开,等到第二天收盘之后再公开,如何知道这个预测结果是不是被篡改过?最后公开的结果是不是提前一天做出来的结果?这时候就可以用到 sealed envelope。把预测结果写到一张纸上,放到一个信封里,交给第三方公证机构保管,第二天再打开验证结果是否准确。

电子世界中,把预测结果作为输入,算出哈希值并公开。因为hiding性质所以无法通过哈希值算出预测结果是什么。然后第二天收盘之后把预测结果公开,因为collision resistance性质所以这个结果不能被篡改,改的话哈希值对不上。

为了保证输入空间足够大,分布更均匀,可以对x加盐,然后对整体取哈希值,H(x || nonce).

3.puzzle friendly

该性质为比特币要求的性质,该性质说明哈希值的计算事先是不可预测的,很难猜出某个输入的哈希值是什么,所以如果想要算出来的哈希值在某个范围之内,只能一个个输入去试,看哪个输入的哈希值是落在符合要求的范围之内。事先不知道哪个输入会算出某种Hash值,只能去试。

block header中有nonce,“挖矿”就是不停地去试大量的nonce,使得H(block header) <= target ,没有捷径,同时保证了“工作量证明”(proof of work)机制.“挖矿难,但验证易”.

比特币中的哈希函数使用的是SHA-256(Secure Hash Algorithm),符合上述三个性质.

签名

中心化系统的账户管理方式:带着证件去银行开户。

比特币是去中心化的,开户不依靠外界批准,在本地创建一个公私钥对(public key,private key),就是一个账户,公钥类似于银行账号 ,私钥类似于银行密码。

公私钥(public key,private key)对概念来源于非对称加密(asymmetric encryption algorithm),用公钥加密,私钥解密(接收方)

公私钥对在比特币中,主要是用作签名。发布交易时,自己通过自己的私钥对交易进行签名,其他人通过自己的公钥去验签。

出现两个人公私钥对相同的概率极小,可以忽略不计。

选取好的随机源(a good source of randomness)生成公私钥,签名也要选取好的随机源。

哈希和签名两个性质可以结合使用。比特币系统中,一般是对一个message取一个哈希值,然后对这个哈希值进行签名。

  • 正序
  • 最新
沙发,很寂寞......
登录 账号发表你的看法,还没有账号?立即免费 注册