我可能错过了发财的好机会了(微笑脸)

今年五月的一段聊天记录。

数字签名

一句话的概况：既能加密，又能解密。是一个互逆的过程。

产生的背景

在网络上，我们要确定一起交易的记录，那么怎么来确定交易不是伪造的呢？还有的应用场景就是电子邮件的发送，http的通信等等发面，需要确认信息的来源是真是的而不是伪造的。

真实的世界中的认证

一开始的想法是，模拟人的手签的字迹，但是计算机可以复制粘贴。于是这种方法不可行。

数字世界中的认证

于是，我们需要一些加密的算法，来确定这个交易确实是本人来做的。
每一个人在通信的时候，都会有一对数字
假设Alice手中有这样的数字\(P_A, S_A\),分别代表Alice的公钥和私钥，公钥可以给任何一个人，但是私钥是绝对的保密的。
同理，Bob为\(P_B, S_B\).至于密钥的产生原理，稍后讲解。

下面，我们来展示加密和解密的过程。
\(M = S_A(P_A(M))\)(1)

\(M = P_A(S_A(M))\)(2)

M代表的是信息（在处理的时候我们将其转化为二进制串）。\(S_A()和P_A()互为反函数\)，都可以通过两次函数的变换来得到原来的信息。但是上面的变换却有不同的用处。
(1)式的应用范围：
Bob想向Alice发送一封信息，并且只想让Alice读取。那么Bob先想办法得到Alice的公钥，然后用Alice的公钥进行加密。由于只有Alice有自己的密钥，因此只有自己才能解密。
(2)式的应用范围：
Alice想对其他人发送消息，怎么让别人相信就是她本人呢?用的就是第一个函数，Alice先对其进行加密。在信内容附上公钥，其他人就可以读取，并且确信这是Alice本人所写的了。
更多的应用：
在(2)的基础上,若Alice只想把信发给Bob该怎么办呢？方法很简单：
她先把数字签名加在信的末尾，这样能确定信是本人所写。然后对整体的内容用Bob的公钥进行加密，这样就只能Bob来读这样的一封信了。

公钥与私钥的产生原理

破解难度的核心：

RSA加密系统的安全性主要来源于对大整数进行因式分解的困难性。

公式的推导以及证明：
要设计一个函数，这个函数要满足上面得两个函数式子的性质就行了。由于涉及数论方面的很多的知识，等有时间或者心情好了再更新。

hash function和encrypt的区别

加密哈希函数：将任意长度的文本转化为固定长度的数字串，且稍有改动，整个数字串将发生巨大的变化，称为雪崩效应。
hash函数是不可逆的，将字符串作用与hash function之后，(将任意长度的文本串作用与hash function之后，得到固定长度的数字串)。得到数字之后，不能通过得到的结果推得原来的信息,正是因为它的不可逆，保证了后面nounce值的计算的复杂性。
而encrypt是一个可逆的过程，加密之后，可以通过另外的函数来解密。

用Python的RSA模块来进行模拟通信

进行(1)式的模拟过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

>>> import rsa
>>> (pa, sa) = rsa.newkeys(512, poolsize = 8)
>>> pa
PublicKey(7287399495366257413771058761739868049169593614102396165193288873805572387006976147311991494525422797626345758517789424374926210086557657000622100528243089, 65537)
>>> sa
PrivateKey(7287399495366257413771058761739868049169593614102396165193288873805572387006976147311991494525422797626345758517789424374926210086557657000622100528243089, 65537, 7027647519823044002742644381047673841884240749574828570675817478880418391900191613482469197184481730731244721399577942685962117567047869164370454616227493, 4450325811458253528888359581209252517270748630183017819682214575947560280752282431, 1637497972980627729843564573878420999729638817154052481198228091129519919)
>>> (pb, sb) = rsa.newkeys(512, poolsize = 8) #poolsize表示运算时的cpu的核心数。
>>> message = "Hello, Bob!";
>>> crypto = rsa.encrypt(message.encode('utf-8'), pb);#加密的过程必须要将字符串转化为二进制的存储形式。
>>> ans = rsa.decrypt(crypto, sb);
>>> ans.decode('utf-8')
'Hello, Bob!'
>>> pb.n
8713105263433599534777847820591755626411909814336518766153432253803317287304054914848665740291595392716126580950997697917807332757088457074926547527045377
>>> pb.e
65537
>>> sb.n
8713105263433599534777847820591755626411909814336518766153432253803317287304054914848665740291595392716126580950997697917807332757088457074926547527045377
>>> str1 = bin(sb.n);
>>> len(str1)
514
>>> len(bin(sb.p))
274
>>> len(bin(sb.q))
242

说明：
可以看到公钥对\(P_B(n, e)\),n = (p-1)(q-1), e是一个较小的与n互质的数字。
私钥由\(S_B(n, e, p, q)\).
可以看出私钥可以推出公钥，但是公钥却不能推出私钥。原因就是大整数的因数分解的困难。
可以从后面看出n的二进制有514位，p,q位数差不多，都为两百多位。（这里说的位都是二进制下的位）

并且可以看出，当信息传输完成后，n值发生了改变，这种动态的处理方式是为了信息安全的考虑。

通信失败：

1
2
3
4
5
6
7

>>> crypto = crypto[:-1] + b'X';
>>> rsa.decrypt(crypto, sb)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\python3\lib\site-packages\rsa\pkcs1.py", line 237, in decrypt
    raise DecryptionError('Decryption failed')
rsa.pkcs1.DecryptionError: Decryption failed

通过修改原理的加密的文件，结果自然是无法正常的解读了。

能传输的信息的限制：

1
2
3
4
5
6
7
8
9
10
11
12

>>> message = "longlongage_longlongage_longlongage_longlongage_longlongage_longlongage_longlongage_longlongage"
>>> len(message)
95
>>> crypto1 = rsa.encrypt(message.encode('utf-8'), pb)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\python3\lib\site-packages\rsa\pkcs1.py", line 170, in encrypt
    padded = _pad_for_encryption(message, keylength)
  File "C:\python3\lib\site-packages\rsa\pkcs1.py", line 87, in _pad_for_encryption
    ' space for %i' % (msglength, max_msglength))
OverflowError: 95 bytes needed for message, but there is only space for 53
>>>

可以看到我们的文本信息串是95个字节的，但是最多的传输串长为53个字节，剩余的11个字节用来存储其他的信息，所以无法进行传输。或者是更改密钥的长度，或者用其他的有效的方法，可以在后面的文档进行查阅。文件内容的传输

进行(2)式的模拟: sign and verify
生动形象的原理图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

>>> import rsa
>>> (pubkey, prikey) = rsa.newkeys(512);
>>> message = "hello python, hello world";
>>> signature = rsa.sign(message.encode('utf-8'), prikey, 'SHA-1')
>>> rsa.verify(message.encode('utf-8'), signature, pubkey)
True
>>> rsa.verify("hello world".encode('utf-8'), signature, pubkey)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\python3\lib\site-packages\rsa\pkcs1.py", line 315, in verify
    raise VerificationError('Verification failed')
rsa.pkcs1.VerificationError: Verification failed
>>> rsa.verify("hello python, hello world".encode('utf-8'), signature, pubkey)
True
#数字签名生成的返回值是64个字节的字符串，即256位的二进制数。
>>> signature
b'\x8c\xedy\xc6\xbb\x86\xa7f\x00\xc7\x8c\xdf\xc6Q\xfeE\xff\xcd\xba\x13iec\xaax\x1e2\x08\x83\x05\xd3\xdc&jk\xc9\xfck\xe4\xb7\x0f\x985\x14\xfb=\\\xbd^b\xb3\xa5\x8829\xee\xed\x94~\x95\x181\xf3\xf0'
len(signature)
64
#传输的信息只用验证真假，因此任意长度的文本串都可以进行传输。因为加密哈希函数是将任意长度的文本串转化为固定长度的数字串，固定长度为256位。
>>> str = "long_long_agolong_long_agolong_long_agolong_long_agolong_long_agolong_long_agolong_long_agolong_long_ago"
>>> len(str)
104
>>> signature = rsa.sign(str.encode('utf-8'), prikey, 'SHA-256')
>>> len(signature)
64

注意仔细看代码里面的注释。sign and verify的概念在交易中十分的重要。

现在假设有黑客进行欺骗，他要得到正确的验证，并且传输给别人，让他人相信。由于持有私钥的人未进行相应的计算，黑客需要试\(2^{256}\)(signature有256位)种可能，才可能拿到正确的signature，这样的计算简直就是不可能。（具体可以看3blue1brown的视频）。因此，基于加密哈希函数的验证方式是十分的有效的。

基于数字签名系统不足

• 可复制的：由于每一次的交易口令相同，那么就可以进行多次的复制，一个人原本只给一个人转账。但是经过多次的复制后，他就多次的给那个人转账。解决的方法是：将时间加入交易口令，进行密码哈希函数。或者是加入特殊的序列号，来证明交易的唯一性。
• 无法确认时间的先后顺序：一个人余额为0。他先收到100，后花了50.若不知到时间的先后顺序，那么别人怎么能让他花50呢？解决的方法：一个人要花50，必须要先经过一个中心，中心会收取的你的钱，然后在将钱发给接收方。然而这还是存在中心的管理，没有去中心化。
• 如何让他人相信这一笔交易的成立：这就需要第三方的信用中心的介入了。然而比特币的去中心化就是不希望依赖第三方。

综合上面的问题，比特币的设计就是为了去解决上面的诸多的问题。比特币的设计简直就是精妙绝伦。
下面让我们走进比特币的世界，去感受它的精妙。

比特币

电子货币的本质就是交易的记录

如何决定是否接受交易：工作量的证明

这其中就需要加密哈希函数了。每一个矿工都知道加密哈希函数，需要把为确认的交易收集起来放到一个块（block）中，一般块的交易记录不超过2400条。

提出的问题：每一个block的交易量都是变化的，怎么划分区块链的交易量？
是随机的划分吗，然后不断的改变nounce的值，一旦先确认，那么这些笔交易就会成立。交易量的大小和收入是成正比的。

这个时候在交易的列表的末尾加上一个nounce的东西。这个东西其实就是一个数，设为\(x\)。我们需要不断的改变这个数字，使之满足系统的条件，交易记录+nounce经过密码哈希函数处理后的固定长度的十六进制串中开通必须包含多少个0.

可见上面的图，它的确认数为2，因为这个矿区是比较新的。确认数=后面接的block的个数，个数一般超过6个即可认为交易的准确性。（这笔交易没有小费）

接受交易

假若现在有一个黑客想要造假，那么他要不断的去维护那个最长的区块链，因为每一个人只相信那个区块链中最长的交易记录。
那么，他必须有足够的财力，最少拥有全网算力的50%，才有可能去随心所欲的去修改交易的记录。然而实际上这是不可能的，随着越来越多的网络矿工的出现，去中心化，这几乎是不可能的。全网最大的算力池是slushpool，它集成的是世界的计算机的计算。

产币的时间间隔

一般为10分钟左右，因为全网的算力在不断的加强，因此系统会调整密码哈希函数得到的十六进制串前置0的个数

可以从这张图上看出，它是一个16进制的数字，要求有19个十六进制的0，需要猜\(16^{19}\)次才能得到正确的nounce值。我们可以查看区块一的值，发现只需要几个前置0就可以了，可见全网算力增加之多。
名词解释：
block reword:发现区块的奖励，每隔四年降为原来的一半，2009~2012:50BTC，2012~2016:25BTC，2016~2020:12.5BTC，依次类推
timestamp:基于时间戳的交易确认
Merkle Root:一种存储的树形结构，具体还不是很清楚
previous block, next block:形成链状
nounce：矿工们苦苦寻找的值

如何确定交易的顺序,防止double-spending：区块链

We define an electronic coin as a chain of digital signatures

要验证一次交易，他人是否透支，就需要知道所有的交易记录。

第二条比特币是用区块链来完成的。

区块链的构成

从图中可以看出，一个区块中有前一块的hash value，交易的signature，nounce值。
好处：

1. 一旦某块的交易被更改，那么这一块的nounce值将会发生改变，这一块的hash value会发生改变，后面的块也要重新计算nounce值。这样的计算量是十分巨大的，因此黑客篡改根本是不可能。
2. 若交换前后两块的顺序，也会发生连锁反应，这也是不可能发生的事情的。

这样就很好的确定的交易的准确性，并且确认交易的顺序了。

一笔交易中包含的信息：

区块链的设计很好的防止了double-spending的发生，
当你需要花钱的时候，你需要先将你账户中的比特币信息发送出去，这里的信息包含了：

• 你得到的比特币的来源(发掘区块的奖励无来源)
• 之前交易信息（前一个拥有者）的电子签名。(in)
• 受币人的公钥,交易额等等(out)

我们有必要说明交易的输入和输出，下面是我直接复制粘贴的说明：
比特币交易得输入和输出

当你支出(给)一笔钱的时候,首先在交易单中就要描述清楚你要支出(out)的钱的收入来源 (in),然后在支出(out)项中,指明要支出的金额,以及通过脚本的形式写明接收者的公钥,然后用自己的私钥签名(scriptSig)认可该笔交易,最后将交易单广播到网络.

收入来源(in):
Previous tx: 为收入来源交易单的散列值,也就是待支付的钱是谁给你的,经常会有多个收入来源被列在交易单中.
index: 指明是收入来源交易单中具体哪一个out,也就是Previous tx交易单中的out索引值(因为out也可以有多个)。
scriptSig: 拥有者对该交易的ECDSA签名认可。

接收对象(out):
Value: 发送的币值,以Satoshi 为单位,1BTC = 100,000,000 Satoshi
scriptPubKey: 接收方的公钥脚本。

in与out的关系:
每一笔交易,out的总额应该等于in的总额。但是,在这个交易单里,只会有out的Value,没有in的Value,而是通过in的Pervious与index,追溯到上一个交易单的某一个out,获得Value。

一次send bitcoin,剩下的钱,应该out给自己,否则这个钱就丢了。

情况列举:

• 我有10个BTC,是某一次交易获得的,我要送给朋友A,10个BTC。这时候,有一个in,一个out。
• 我有10个BTC,是某一次交易获得的,我要送给朋友A,5个BTC,这时候,有一个in,两个out,一个指向朋友5个BTC,一个指向我自己,得到剩下的5个BTC。
• 我有10个BTC,是以前的两次交易获得的,我要送给朋友A,10个BTC,这时候,有两个in,一个out。
• 我有10个BTC,是以前的两次交易获得的,其中一次获得了6个BTC,另一次获得了4个BTC,我要送给我的朋友7个BTC,这时候,有两个in,两个out。

而这样的一笔交易将会被广播出去，等待矿工去验证，一旦验证成功，那么新的信息会加入到比特币的认证信息中，表明当前持有者，和之前的持有者的记录。这样就有效的避免了double-spending的发生，因为比特币的主人发生了改变，那么依附的信息也会发生改变。

货币的流通

收益来源：
矿工发现新的矿区，系统奖励
确定交易，用户的小费，激励矿工开确认自己的交易信息。

总额

其中系统的小费每隔四年会降为原来的一半。
总的货币发行量：
\(6*24*365*4*(50+25+12.5+\cdots) = 210240*\frac{50*(1-(0.5)^n)}{1-0.5} = 21000000\)
即货币的发行量不超过2100万。

停止产币的时间

比特币的最小的单位为\(10^{-8}\)BTC,因此进过33个4年就会不再产币，即\(2009+4*33=2141\)年不再产币.但是资金还是可以流通的，因为小费机制的存在。

script

前面仅仅模拟的是比特币之间的转账，然而比特币还有其他的功能，而这些功能是用比特币的脚本语言来完成的。

比特币核心的总结

我们再不厌其烦的整理一下思维：
1、 假如仅仅使用电子签名，我们可以确定交易确实是本人。但是，存在重复花一笔钱的危险，因为假设Alice几乎同时向Bob和Petter花了相同的一笔钱，那么到底这笔钱到底归谁呢？此刻，必须存在第三方，来确认交易的顺序，若先支付给Bob,那么就不能再支付给Petter了。
2、 能不能试图消除第三方的存在呢？可以，我们用区块链来确认交易的顺序，通过工作量的证明确认交易的有效性，这就产生了比特币。

资料来源

RSA模块文档
RSA模块的实战
How the Bitcoin protocol actually works
中本聪的最初的论文
bitcoin实时交易的网站
各种加密哈希函数的加密解密
bitcoin交易的收费标准

未解决的问题

中间的公式推导过程
比特币划分block的交易量是怎么确认的？是随机产生的吗？
可能真的是随机化产生的：