区块链技术与应用

比特币原理

graph TD
A[比特币用到的密码学内容]-->B1[哈希]
A-->B2[签名]

Cryptographic hash function

Character 1 Collision

  • Definition of collision:

$$
根据某种定理，对于任意x\ne y,都存在H(x)=H(y)
$$

  • The first important feature of hash function: Collision resistance
  • Collision resistance means: 对于任意一个$x$， 都一个对应的哈希函数值$H(x)$，而除了运用暴力求解，就没有别的办法能够找到一个$y$，使得$H(x)=H(y)$。
  • 应用例子：对与一个$Message\ m$，它的哈希值为 $H(m)$。其中，$H(m)$可以认为是$m$的$Digest$。哈希值在这里可以用来检测人是否对$Messsage \ m$进行了篡改。虽然$H(x)=H(y)$的情况存在，由于根据$x$求取$y$的方式太复杂，以至于只能用暴力求解的办法来找$y$。运算量随输入空间指数增长，在输入空间足够大时，暴力求解也不可取。因此对于网盘来说，只需对比本地文件的哈希值和网上文件的哈希值，即可知道上传的文件有没有被篡改，由此保证了安全性。
  • 所有的哈希函数的Collision resistance性质都没有在数学上被严格证明，一切都是来自于经验。有些哈希函数经过许多高端密码学家检验，是Collision resistance的，也就是说找不到$H(x)=H(y)$的情况，这样的哈希函数就可以实际应用。也有一些哈希函数，原本被以为是Collision resistance的，可后来被找到了认为制造Collision的方法，所以现在已经不安全了，例如著名的MD5。
  • Bitcoin uses SHA-256 hash function. SHA means Secure Hash Algorithm.

Character 2 Hiding

  • Definition: 计算是不可逆的、单向的：
    $$
    \begin{align*}
    x\rightarrow H(x)\\
    H(x)\not\rightarrow x
    \end{align*}
    $$

  • 即从$x$能够推出$H(x)$，而从$H(x)$不能够推出$x$，而如果真想从$H(x)$推出$x$，则只能蛮力求解。

  • 若想真正保证Hiding这条性质，就要使得输入空间是足够大的，而且各个出入取值概率要大致相等。

Combination of Collision resistance and Hiding

  • Collision resistance + Hiding $\underrightarrow{\text{implementation}}$ Digital commitment (or equivalent of a sealed evelope)

  • What is a sealed evelope?

    • A man say that he can predict the stock’s stop, so that he need a way to convince them of his ability. There are generally three ways and we will talk that which one is feasible: 
      graph LR

A[Ways]--1---> B1[He tells everybody on the day before the stock
    close that the stock will stop.]
A[Ways]--2---> B2[He tells everybody on the day after the
    stock close that the stock will stop.]
A[Ways]--3---> B3[He puts the predicting result in a sealed
    evelope and submit it to a trusted institution.
    The institution will open the evelope after the
    stock closes and check if the predicting is right.]
    • Obviously the third way is the only way that he can convince others of his predicting ability. May the first way seem to be realistic, but the information about the stocks itself will influence the behavior of the shareholders, so that the predicting will be unreliable.

  • As the title shows that Digital commitment can be achieved with the combination of collision resistance and Hiding.

  • Sometimes the input space is not enough, for example that there are only a few thousand stocks. In this case an nonce should be put after the input, then they will be taken hash values togather.

    e.g.:
    $$
    H(x||nonce)
    $$
    Nonce here means a random number. When generating nonce we must ensure that the generating must be random enough and the distribution of the random numbers are even enough.

Character 3 Puzzle friendly

  • This character means that calculation of hash value is unpredictable. If one wants the hash value $H(x)$ fall within a certain range, one must try different $x$ one by one.

  • Question: What is puzzle friendly?

    • Intro 1: The mining process is actually finding a nonce. This nonce will combine with the block header in a block and this combined number is the input $block header + nonce$. Then its hash value must less than or equal to a certain threshold. This is showed in the following equation:
      $$
      H(block header + nonce)\leq target
      $$

    • Intro 2: Block chain is a chain consits of blocks. In each block there is a block header. In each block header there are many regions. Nonce is one of these regions. The process of mining is actually continually trying different nonce to find one nonce that satisfy the equation above.

  • Answer: The puzzle friendly character means that in mining Bitcoin there’s no easy way but only finding a feasible nonce in plenty of nonces. So that only this process can be seemed as the proof of work.

Character 4 Difficult to solve but easy to verify

  • This character means: Mining needs a lot of calculation and workload. But if one has calculated a feasible nonce and put it on the Internet, other people can just calculate for only once to verify.

Signature

比特币账户管理方式：去中心化

日常生活中我们用的账户管理方式是中心化账户管理方式，即个人去相关机构开户，然后得到批准。而比特币系统使用的是去中心化系统账户管理方式，即每个用户自己决定开户与否，不需要任何人批准。

比特币开户很简单，即创立一个公钥和私钥对：$public\ key,\ private\ key$。这种方法来自非对称加密体系。

非对称加密体系 $asymmetric\ encryption\ algorithm$

我们先来说一下对称加密体系。社会最开始的加密方式是对称加密：$symmetric\ encryption\ algorithm$。

例：我们两个人想要互相传递信息，可是在传递信息的途中可能有人窃听，所以我们需要对信息进行加密。我们俩事先商量好一个密钥，即$encryption\ key$。我用这个$key$将信息加密后发送给对方，对方再解密。因为我俩用的是同一个密钥，所以是对称密钥。

对称密钥的前提是：必须要有某种安全的途径，将密钥分发给双方。（肯定不能以明文的形式将密钥发布在网上。）这是对称加密的一个弱点。而非对称密钥弥补了这一缺陷。

非对称加密体系

非对称加密体系中有公钥和私钥之分。

公钥与私钥
graph LR
A[非对称加密]-->B1[公钥]
A-->B2[私钥]
B1-->C1[加密]
B2-->C2[解密]

这里要注意：加密和解密都是用的同一方的公钥和私钥，即接受方的公钥和私钥。我想传递信息给家家，就要先用家家的公钥将信息加密，家家收到后就再用自己的私钥将其解开，就得到了完整信息。

这样的好处是：公钥是可以让所有人都知道的，而私钥是要保密的，但私钥保存在本地即可。这就解决了信息传输过程中密钥分发不方便的问题。

比特币系统中，每人拥有一对公钥和私钥。公钥相当于自己的银行账户，而私钥就相当于自己的密码。别人知道我的公钥就可以向我转钱，而我只需要知道私钥就可以把这笔钱转走。

签名

比特币虽被称为加密货币，但比特币系统是不加密的，信息都是公开的。那要公钥和私钥有什么用？实际上是为了签名。比如，我想对某个人转10个比特币，那应该如何防止别人顶替我的名义呢？这就需要我在转出比特币的时候对他们进行签名。其他人收到这个交易之后，会用我的公钥对我的签名进行验证。

graph LR
A[同一个人的公钥和私钥]-->B1[公钥]-->C1[验证签名]
A-->B2[私钥]-->C2[实施签名]
问题

问：既然公钥和私钥都是自己生成的，那有没有可能，两个人生成了同一对公钥和私钥，这样就可以把对方的比特币转走？

答：理论上这种情况是存在的，这种盗取手段在理论上也是可行的，但在实际当中是不可行的。因为256位哈希值的系统产生相同公钥和私钥对的概率微乎其微，开玩笑讲，比地球爆炸的概率还小。

强调一点：在这里我们假设产生公私钥的源是一个好的随机源。如果随机源不好，则可能会导致相同的公私钥对产生。$BTC$不仅要求在产生公私钥对的时候而且还要在签名的时候都要有好的随机源。只要有一次随机源不好就可能导致私钥泄露。

总结：$BTC$系统结合使用哈希和签名两者，一般来说，是先对一个message取一个哈希值，然后再对这个哈希值签名。