关于本文
为什么要学区块链？
首先哲学三问 why what how。
这个对找工作有帮助么？或许有，但是岗位门槛太高普通人只能望洋兴叹。
多学点关于区块链和比特币的知识，会让我更懂得怎么多赚几个比特币么？不能，除了忽悠韭菜的钱外只有挖矿，而挖矿只取决于你的机器的运算速度和运气，除了买更多的矿机之外，别无他法。(｀_ゝ´)。
那你也许会问我，学这玩意有啥用？嗯，就是没用的。至少目前没用，考试和工作都用不到这么高深的概念。学就是了，没有为什么。就因为我昨天晚上突然灵光一闪，今天就开始学习了。
Begin.
来源
说起区块链相关比特币肯定逃不开，对的。本文就是为了解释比特币底层原理。
文章内容来源于北大肖臻老师的 《区块链技术与应用》 公开课。
会加入部分我个人对知识的理解，当然以肖臻老师老师的口述为主，因为说的太专业了。
引言（李永乐）
可以先预习一下李永乐老师关于比特币简单的介绍：李永乐老师传送门
关于比特币
比特币（Bitcoin）的概念最初由中本聪在2008年11月1日提出，并于2009年1月3日正式诞生。2008年爆发全球金融危机，2008年11月1日，一个自称中本聪的人发布了比特币白皮书《比特币：一种点对点的电子现金系统》，陈述了他对电子货币的新设想——比特币就此面世。2009年1月3日，比特币创世区块诞生。
以上来自百度百科。
比特币实际上是一种电子货币或者叫数字货币，基于密码学。
比特币的出现是一种传奇。
想实现一种区去中心化的电子交易系统，只做一件事，就是记账。现在的记账是谁来记呢？银行记，我们信任银行，因为银行背后是国家的信用。
因为本质就是记账，假设有ABCD四个人，相互转账。A->B 10BTC，B->C 5BTC， C->D 2BTC这样一个账单，被打包。称为区块，一个区块的大小大概是1M，大概存4000条左右的交易记录。这个块打包完成之后，链接到以前的块上，形成一个区块链。
为什么要记账？因为记账有奖励，每一个比特币系统中用户都可以记账，有手续费，比如A付出10个BTC，那么他必须多付出那么一点提供给打包的那个人。打包的那个人还有一个打包奖励，中本聪在2008年提出这个系统的时候，设计了这样一个方案，每十分钟打一个包，最开始这一个包会奖励打包者50个BTC，过了四年之后每打一个包会奖励25个BTC，再过四年就奖励12.5...每相隔四年奖励减少一半。
可以算一下比特币一共有多少个，首先每过十分钟会打一个包。一个包有50个BTC，一个小时可以打包6次。每天24小时，每年365天...前四年是如此，再之后的四年会减半。 50 * 6 * 24 * 365 * 4 * (1 + 1/2 + (1/2)^2 + .....) 最后结果算出来 等于2100万个。
以谁为准？中本聪想到一个办法：工作量证明。这个过程称之为挖矿。
挖矿的原理
哈希函数：可以将一个数据转换成一个摘要的形式，而且你正着算比较容易，反着算很难，只能一个一个去试。
区块链里边有很多区块，区块是由很多信息组成，这个块里有一个块的头部和交易记录。如果有人想进行打包，每一个人拿着账单去网上接块，接块的时候需要做一个数学题。首先会有一个字符串，内容非常多，包含目前这个前块的头部，账单的信息，时间戳和其他很多固定的数据，最后有一个很重要的就是随机数，对这个字符串做两次哈希运算。要求这个数的前N位必须是0，算对了才有资格去打包。打包的意思是说要把算出来的这个哈希值作为一个新块的头部打一个包接到后面去接出一个新块来，这样就获得了想要的奖励。
我们没有办法去改变比如帐单和时间戳等固有值，所以只能改变随机数nonce，然后不断的计算，这个过程就叫挖矿。
这个随机数的确定是由系统决定的，中本聪希望每10分钟打包一个块，那么不同的时间调整不同的难度即可。
假设矿机的运算速度为14T/秒=1.4*10^13/秒。
10分钟1万台机器的计算量 1.4 * 10^13 * 10^4 * 600s = 8 * 10^19
n = 66时 打包的几率是 (1/2) ^ 66 也就是说需要计算 2^66 次才能打包，2^66约等于8*10^19。
当n=66时，1万台矿机10分钟能打包成功一次。
当然这个难度n==66对于整个比特币系统来说也只有25%概率而已。
肖臻的正文开始，以下。
【一】BTC中的密码学原理
【1.1】比特币是加密货币
虽然叫加密货币，但是其实是不加密的
包括账户地址 转账金额都是公开的
比特币中用到了密码学中的2个东西：一个是HASH，另外一个是签名。
【1.1.1】密码学之'HASH'
密码学中的Hash也叫Cryptographic hash function，它有两个重要的性质。
collision resistance和Hidding。
【1.1.1.1】Hash碰撞(collision resistance)
对于x和y x!=y && H(x)==H(y)。两个不同的输入算出来的输出是一样的,这就叫Hash碰撞。
Hash碰撞是很常见的，而一般来说Hash碰撞是不可避免的。因为输入空间是远远大于输出空间的
比如比特币中使用的SHA-256算法，输出的是256位的Hash值。每个位上只有0和1两种选择，全排列则会产生2^256种结果，但是输入却是无限大的，因为数据的多样性。按照鸽笼原理（抽屉原理，即将n+1个苹果放到n个抽屉，则必定有一个抽屉出现2个苹果。），必然会出现两个输入被映射到同一个输出的情况。
这个性质的作用是用来对一个Message做Digest，用来检测对Message的篡改。如果有人改了Message的内容，Hash值就会被修改。这个性质是说，你找不到H(M)==H(M')，所以没有办法篡改内容而又不被检测出来。
比如一个文件，把他放到云存储服务器上，将来用到他的时候再下载回来。你怎么知道你下载的版本就是你上传的版本呢？可以上传之前对文件取HASH，下载之后再取HASH。对比结果，相同则证明文件一致，没有被篡改。
这里你可能会觉得有没有两个不同的文件拥有相同的哈希值？
有一点注意，没有哪个hash函数没有可能在数学上证明是collision resistance的。刚刚说到这么重要的内容，其实从理论上是证明不出来的。这个只能靠实践中的经验。世界上那么多密码学的专家，至今为止也没有人能找到人为制造Hash碰撞的方法。只能说哈希函数设计的好坏是关键。
也有一些Hash函数，之前也是被人为是collision resistance的，但是后来被破解了==。比如某MD5(详情请了解王小云教授，可以去看他的文章，可以人为制造Hash碰撞，如果你云端使用MD5存储，那么很有可能上传过去的东西下载回来并不是一个东西，这样会导致成为肉鸡)。
【1.1.1.2】单向不可逆(Hidding)
比如一个输入值 X可以算出他的哈希值 X->H(X)，但是没有办法通过H(X)算出X的值。换句话说，这个哈希值没有泄露任何跟X有关的信息。但是也是有办法解出x的，比如我遍历所有x，肯定会有一个输出等同于H(x)。蛮力求解是一种办法。
hidding这个性质的前提是，输入空间足够大，使得蛮力求解成为不可能，而且输出空间比较均匀，各种取值都有。比如X很小的时候，产生对应的H(X)也很小并且集中在一片区域。这样也会留下攻击的漏洞。
hidding的作用是和collision resistance结合在一起形成digital commitment，也叫做digital equivalent of a sealed envelope。
举个例子说明一下现实中的a sealed envelope：比如有个人可以预测股市，说可以判断哪只股可以涨停。怎么判断呢？可以让这个人先说某某股票是否会涨停，然后第二天收盘的时候看一下，是不是真的涨停了。
这样做有什么问题么？如果你预测结果提前公布了，可能会影响股市。比如这个人可能预测某某股票会涨，结果所有的人都去买这个股，大家拼命去买，结果变成了涨停。反方向的想，这支股票确实要涨停的，但是有人想踢场子，我就不让他涨，拼命的砸盘。。所以说，预测结果不能提前公开，但是预测结果不公开，等第二天收盘再公开，也没有办法判断那个人说的是否真实。这里得用到sealed envelop，你可以将预测结果写在一张纸上，放在信封里，将信封交给第三方公证机构保管，等第二天收盘之后预测结果准不准即可。
在电子的时间里应该如何做呢？可以把预测结果X算出一个哈希值H(X)，然后把H(X)公布出去。因为有hidding的性质，不知道预测结果是什么，然后第二天收盘之后，把预测结果公布出去。再取Hash对比是否和公布的H(X)相等，如果X和H(X)都相等，那肯定是没问题了。因为collision resistance性质，所以预测结果是不可能篡改的。
注意前提：输入空间足够大，分布均匀。
常用的方法是将输入后面拼接一个随机数nonce，然后一起取哈希。H(X||nonce)，保证我们拼接之后整个输出是足够随机且足够均匀的。
【1.1.1.3】puzzle friendly
除了满足上述两种性质外，比特币还满足这条。
比如哈希值的计算事先不可预测，光看输入很难才出来最终的结果。如果想要哈希值落在某个范围之内的，那么没有什么办法，只能一个的去试。比如想得到一个前面全是0000XXXXXXXX....的哈希值，必须以K个0开始，什么样的输入可以算出来呢？母鸡，谁都不知道。上帝也不可能知道，为了得到这个哈希值只能一个一个去试。
挖矿，其实就是找这么一个nonce，这个nonce和区块的其他信息合在一起做一个输出，这个结果需要小于等于指定的目标预值。H(block header) <= target，其中这个块里边有很多个域，我们能够设置的只有nonce。挖矿的过程就是去不停的试
这个性质是说，挖矿的过程没有捷径，只能靠不停的去试大量的nonce才能找到符合要求的解。挖不挖得到主要看脸==。
某个人如果挖到了nonce，公开出去，其他人想验证只需要取一次哈希即可。挖矿很难，验证很容易，这个性质叫做difficult to resolve, but easy to verify.
【1.1.1.4】SHA-256
全称Seaure Hash Alorithm，由NSA研发的一种哈希算法。上边提到的3个性质它都是满足的。
【1.1.2】密码学之'签名'
举个例子，比如去银行开户。需要携带身份证户口本啥的，然后银行给你颁个账户。现实中。淘宝时基于阿里巴巴来记账，微信和QQ是基于腾讯来记账。这是基于中心化思想的。但比特币是去中心化的呀，所以怎么开户？
其实比特币开户不需要任何人的批准，只需要创建一对私钥和公钥即可。
公私钥的概念来源于非对称的加密体系(asymmetric encryption algorithm)。
加密用的是公钥，解密用的是私钥。比如我要把一个信息传给你，我要用你的公钥加密，然后你用你的私钥解密我传给你的信息。注意，加密和解密用的都是同一个人的公钥和私钥。公钥是不用保密的，直接可以告诉所有人，私钥是要保密的，但是私钥只需要保存在本地就行了，不需要传给对方。要回复他的话只需要用他的公钥加密，然后把加密后的数据公开就行。都不需要知道对方的私钥。这解决了对称加密体系中秘钥分发不方便的问题。
比特币中公钥相当于你的账户名，别人只需要知道你的公钥就可以转账给你。
最开始也说了，比特币是不加密的。那公钥和是要干嘛用呢？签名。
比如我要转10个BTC给你，然后把交易发布到区块链上，别人怎么知道这个交易是我发起的呢？会不会是有人冒名顶替想偷偷转走我账户上的钱？需要在我发布这个交易的时候，需要用我自己的私钥对这笔交易，签名。其他人收到交易之后，再用我的公钥去验证这个签名的正确性。签名用的是私钥，验证签名用的是公钥。
疑问，既然每个人独立的产生账户，不需要任何人批准，万一两个人生成的公私钥对恰好相同怎么办？比如有人想偷取BTC，一种方法是大量产生公私钥，然后和区块链上已经产生的公私钥对比是否相同，如果一样的话，就可以用对应的私钥把账户上的钱偷走，这种攻击方法从理论上来说好像挺好的，但是实际不可行。
如果只是256位的哈希值，产生相同公私钥的可能性微乎其微，即使用一台超级计算机，啥都不干就是产生公私钥对。产生一对相同的公私钥的概率也是忽略不计的，这个概率比地球爆炸的概率还要小。目前为止还没有发现哪个人可以用这个方法攻击成功的先例。
但是得有一个前提，产生公私钥的时候有一个好的随机源(a good source of randomness)。
【二】比特币的数据结构
【2.1】哈希指针(Hash pointers)
普通的指针存储的是某个结构体在内存中的地址。哈希指针除了存地址外还得保存结构体的哈希值。
首先的注意的是，这个哈希指针的哈希是怎么算出来的？比如有一个简单的区块链 A<-B<-C<- D ，是将前一个区块的所有内容，包括哈希值也合在一起取哈希。比如我想计算C的哈希，会将B的头部+数据区+哈希值合在一起取哈希，而B的哈希值又从何而来？从A而来，所以可以理解为C的哈希值其实是和A还有B有关的。可以推测出，任意结点的哈希值是和该结点前边所有的结点相关的，如果A的内容被篡改，A之后的所有的哈希值全部都不对。牵一发而动全身，就是这样做的好处。这个性质叫做tamper-evident log.
比特币中一个最基本的数据结构就是区块链，区块链是什么？就是一个一个区块组成的链表，区块链和普通的链表相比有什么区别呢？一个区别就是用哈希指针代替了普通指针。
【2.2】默克尔树(Merkle tree)
和普通的树的区别就是，一个用哈希指针代替了普通的指针。
比特币中其实是组织成一个默克尔树的形式，底下的块儿，其实都是交易。
大致画了一下：
可以从最底层结点开始验证，查询一个分支上的哈希值，沿途的哈希值都是正确的，该交易就被写到了交易里面。也就是说我只需要验证我拥有的数据交易所在分支是符合要求的，然后对最后的根结点取一个哈希，最后跟我保存在block header里面哈希值是一样的。因为对树种任意一个部位做修改，都会影响到根哈希值。
有一个问题，大家会不会觉得这样的交易不太安全？比如我修改C的值，H(C)也被修改，但是旁边的H(D)是不用去验证的，原来的H(H(C)&&H(D))最后一直取到根哈希的一个结果设为H(root)，会不会有H((H(C')&&H(D'))最后一直取到根哈希的结果为H(root')==H(root)，因为C被篡改了最后的H(root)肯定会被篡改，但是，C和D一块儿被篡改，那会不会导致H(root)反而不被篡改呢？
答案是没有，由于上一节课讲到的collision resistance性质，这个实际上就是在认为的制造哈希碰撞了，即使我给你这样一个自由度，旁边一个哈希值随便的选，你也制造不出这样一个哈希值。
【2.2.1】人为制造哈希碰撞的可能
人为制造哈希碰撞的概率，等同于挖矿中，N的值为256，你得试2^256次可能有一次正确结果出现。这个数字相当于2的32次方和自己相乘8次，2的32次方相当于40亿(42亿多了)，40亿连续相乘8次。
现在全世界人口有70多亿，假设有40亿人人手一台超级GPU，超级GPU的计算速度是40亿次/秒(现如今最快的速度接近10亿次/秒)，并且继续假设，有40亿颗地球(银河系中检测到的恒星数量大约1000-4000亿，1%的恒星可能会有一颗地球，估算约为40亿颗)，接着想象有40亿个这样的银河系。就算你有40亿人手一台的电脑 + 40亿颗地球一样的行星 + 40亿颗银河系。也就是说40亿(GPU计算速度) * 40亿(人口数) * 40亿(地球的数量) * 40亿(银河系的数量) = 我们每秒的计算量，这才4个40亿相乘呀。还剩下40个只能用时间来凑了，然而，40亿的平方已经达到了5070亿年，是宇宙年龄的37倍，满足上述情况下，你只需要花费5070亿年就可以有(40亿)^2的可能性拿到一个正确答案，开不开心。(｀_ゝ´)
【三】BTC-协议
【3.1】如何设计一个加密货币
首先不考虑去中心化的问题，假设就是有一个大家都信任的中性化机构。央行，央行是有权利发行加密货币的，假如大家都知道央行的公钥，央行应该怎么发行呢？
人民币见过木有？
它的发行方式印钞厂印出人民币来，上面有各种各样的防伪标记，你要买东西的时候就把钱给对方就行了。
这个方法我们在数字货币上使用行不行？首先央行的公钥我们都是知道的，我收到了一个数字货币，可以验证一下是不是真的，那么买东西的时候，我需要给你100块钱，就把数字货币发给你，你可以验证一下确实是央行发行的。这就完成了支付的过程，大家觉得这个方案怎么样？
感觉没什么问题，好像很好的一个方案。但如果真的没问题的话，我们也就没必要用区块链了，这里边没有区块链对不对。用到的是密码学中的公私钥体系，非对称加密算法，但是没有用到区块链。
真的没有问题么？比如如果货币的发行量是央行说了算，这样容易导致通货膨胀。你不限制央行，如果像美国那样搞，发行好多货币，就容易影响市场的金融秩序。这些都是很合理的推测。但其实有一个很大的问题，这样设计根本不行。比如我要买东西，我把100快钱给你了，然后你把东西给我。数字货币是什么？就是一个文件啊，对不对，这个文件有央行的签名，所以我们说它文件的内容是无法被篡改了，但是它是可以复制的，我可以复制很多份这样可以无限的复制下去。这个和人民币不一样，我给了你我就没了。这个叫做 double spending attack。
数字货币主要的防范就是 double spending attack，可以让货币上有一个编号，比如100块的是017，50块的是092。而央行呢需要维护一个数据库，就是一个大的表，上面记录了每个编号的数字货币在谁手里。花钱的时候，不光是要验证一下这个数字货币有没有央行的签名，还要找央行核实一下，这个数字货币以前有没有花出去过。这样是没问题的，但这是一个中心化的方案。
我们能不能搞一个去中心化的方案？把央行的职能(发行货币、维护中心数据库)交给广大用户来承担，这就是数字货币系统要解决的问题。一个去中心化的货币，需要解决两个问题，一是谁有权利决定发行数字货币。现在没有央行了，都是普通老百姓，怎么决定货币什么时候该发行？该发行多少？第二是怎么验证交易的有效性，就是刚刚说的，如何防止两次支付？
在比特币中谁来决定发行货币？这是由挖矿决定的，后面讲。先讲一下如何解决双重支付。
【3.1.1】解决双重支付
其实这个问题的解决方案和刚刚提到的解决方案是有一点类似的，也是需要维护一个数据结构来检测这个币以前有没有被花过？被谁花过？只不过这个币呢，不是由央行来维护，而是由所有的用户来维护，这个数据结构就是区块儿链。
比如说有一个用户A，他获得了发行货币的权利，我们叫铸币权，他发行了10个比特币。A拿到钱转给B和C，每个人给5个BTC，这个交易需要有A的签名，证明是经过A同意的。同时这个交易还要说明花掉的10个比特币从哪儿来的，前面的叫铸币交易，后面的交易是从铸币交易的输出中来。比特币系统中每个交易都包含输入和输出两部分，输入部分要说明币的来源;输出部分要给出收款人公钥的哈希。比如A转给B钱，就要说明B的哈希是什么。
