比特币核心概念及算法
区块链、挖矿还有其它
bitcoin项目地址位于github仓库,当前各种“币”,基本都是从抄写bitcoin代码开始起步的。想要深度研究,从看源码开始不可避免。
- P2P:电骡、迅雷、BT,在中国网络影视的发展让大家对P2P很熟悉,可能已经没有人记得比特币实际上是第一批P2P的实践者。所有交易记录在全网通过P2P的方式广播,每个人都保存一份完整的交易记录。所以也叫去中心化。
- 去中心化:bitcoin的去中心化是指的账本去中心化,每个人都拥有完整的交易记录。因此不会出现人为修改某一个账本就导致财产丢失的情况。
在这种模式下,想有效的修改以前的交易记录,就需要有工作量证明(POW)。理论上修改之前的区块必须做到51%的联网机器都认可才可能成功,而这肯定是做不到的。
实际在整个比特币系统的运行中,P2P的特点实际上还是要有服务器系统负责支持维护,这是显然的。
在比特币软件中,这个支持系统采用的是DNS Seed来获取一部分对等节点列表,使用户快速发现对等节点,这部分DNS地址被硬编码在源码中的,每个新安装的客户端需要使用这些地址来工作:vSeeds.emplace_back("seed.bitcoin.sipa.be", true); // Pieter Wuille, only supports x1, x5, x9, and xd vSeeds.emplace_back("dnsseed.bluematt.me", true); // Matt Corallo, only supports x9 vSeeds.emplace_back("dnsseed.bitcoin.dashjr.org", false); // Luke Dashjr vSeeds.emplace_back("seed.bitcoinstats.com", true); // Christian Decker, supports x1 - xf vSeeds.emplace_back("seed.bitcoin.jonasschnelli.ch", true); // Jonas Schnelli, only supports x1, x5, x9, and xd vSeeds.emplace_back("seed.btc.petertodd.org", true); // Peter Todd, only supports x1, x5, x9, and xd
当客户端已经工作过,并且缓存了对等的网络节点地址之后,下次再次启动,就不需要访问这个地址了。每个客户端等于自带了路由,这个时候就是真正的去中心化了。
DNS系统采用UDP方式工作,速度更快,也不容易受到DDOS攻击。
去中心化的商业理念曾经非常火爆,也被认为是比特币的重点创新之处,不过最近业界基本已经认为“去中心化”是个伪命题。因为所有提出去中心化的公司,实际都是为了以此为武器,打破大公司或者行业垄断企业的独占优势。且不说是否能够成功,即便成功的话,新公司仍然是希望自己可以独占和垄断。所以大家实际想要的不是去中心化,而是自己可以控制、别人不能控制的优势。 - 工作量证明:工作量证明(Proof Of Work,简称POW)。因为记账的过程是分布式的,每个人都可能发生,这个过程的监督非常困难。工作量证明等于是只监督结果,你必须付出足够的工作量(有效挖矿),才能证明你的记账工作是有效的。这个工作量的定义是由挖矿的难度决定的,参见后面挖矿。
- 共识机制:区块链系统使用上面所述的工作量证明来解决节点可信的问题(共识问题在计算机算法中有一个典型的模型叫拜占庭将军问题,通常分布式数据库中都会存在这种问题)。
- 区块链:区块链是老概念,软件专业的算法课程,基本上头几节课就会涉及到链表的概念。区块链就是链表,除了第一个“创世纪”节点,每一个节点都有一个指针指向前一个节点。单向链表的特征使得肯定会出现多个节点指向同一个节点的情况,这一般是由于同时出现两个挖矿成功,这种情况就是分叉,无限制的发展就成为了树。比特币系统的设计是不允许这种情况的,每次都会在链表中选择最长的一条链表进行下一个节点的链接,而最终短的分支会被抛弃。比特币的设计中,一个区块之后又链接了5个另外的区块(共6个区块),就可以确认本区块的交易是安全的了。一个示意性的区块链节点结构图示如下:
区块链是把一个基本数据结构模型应用于去中心化记账算法的成功范例。优点是这种创新必将对今后的金融系统设计造成深刻影响,缺点则是至今似乎尚未发现这种区块链结构在其它领域的优势应用或者优选方案。 - 挖矿:区块链中每一个节点都是用来记账的。为了防止节点被伪造,节点的生成有严格、耗时的要求,只有找到一个新的节点符合这些要求,这个节点才能把最近发生的交易记录进去并链接到区块链主链之上。寻找一个新的记账节点的过程就是挖矿。
- 挖矿算法:如果用python来表述一下挖矿算法,源码大致是这样的:
import hashlib, struct ver = 1 prev_block = "000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f" mrkl_root = "0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098" time = 1231469665 bits = 486604799 nonce = 2573394689 hex_str = struct.pack("<L", ver) + prev_block.decode('hex')[::-1] +\ mrkl_root.decode('hex')[::-1] + struct.pack("<LLL", time, bits, nonce) hash_str = hashlib.sha256(hashlib.sha256(hex_str).digest()).digest() # bitcoin矿机就是使用显卡或者FPGA实现sha256算法,通过暴力循环找到一个合适的nonce ... block_hash = hash_str[::-1].encode('hex_codec') #以下是伪代码 if meetReqirements(block_hash): newBlock=bookkeeping(block_hash) block_hash(newBlock)
挖矿的核心是进行两次的sha256运算,并且要求结果符合当前比特币要求的难度值,难度值表示两次sha256计算的结果,前面有符合难度值的0。意思是,假设计算结果是”000000xx…xxxxxx”,前面0的个数,必须符合难度的要求,而且这个难度值在比特币系统中是不断增加的,也就是说挖矿难度越来越大。
参考上面的链表图,开头定义的几个常量都是节点的基本资料,不可改变,可变的只有nonce。而sha256 hash算法的特点,使得最终结果只能暴力循环所有的nonce可能值,才可能得到最终结果,至今尚无投机取巧的办法。
这个设计是为了区块链的生成没有那么容易,从而伪造区块链就成了拼计算能力的行为,而挖矿如此流行,计算能力想超过全球挖矿计算能力的半数已经是一件不可能的事情。从而在技术上杜绝了“账本伪造”这种可能性。这也成为“工作量证明(Proof-of-Work)”的共识达成机制的核心。 - 矿池:因为挖矿的难度越来越高,今天一个人使用自己的电脑挖矿成功的事情已经极难成功,因此出现了在辅助网站及辅助程序的帮助下,把大家零散的计算能力汇聚起来,一起进行挖矿,收益大家分享的方式,这就是矿池。矿池的主要算法是把上述的一个nonce值分段,每人穷举其中一小段,从而并行起来提高找到正确nonce值的概率。实际上今天矿池这种概念已经很成功的应用在了不少领域,诸如分布式计算、众筹等。
- UTXO:一种记账方法,每个交易的记录,仅记录最终最近的交易及“UTXO”也就是未花费输出(Unspent Transaction Output),最重点,每一个交易中都包含这笔钱是谁转给你的。而链表中上一个交易也是,因此实际上每一笔钱都是可以完整追溯的。这种方式的特点是:1.得到余额需要去遍历区块链,而不是某一个节点。2.显然能大大缩小节点的数据尺寸。这对分布式每个人都保存一份账本的情况下,可以大大的降低空间需求。
- 矿机:上面的挖矿源码可以看出,主要的计算就是两次的sha256,想提高速度,除了用CPU,GPU更适合用作这种单纯的数学运算。因此出现了专门为挖矿设计的计算机,比如同时支持多块显卡,从而大大加快速度。这种电脑除了挖矿,在其它应用中意义并不大,所以叫“矿机”。GPU计算之后,又出现过FPGA矿机及ASIC矿机,不过看起来产量并不是很大。也可能是因为一旦挖矿失败,普通设备还可以拆开卖显卡,而这种纯粹的专业机就不好办了。
- 创世块:也就是创世纪区块,链表中第一个区块,相当于链表的头。这个也是硬编码在源代码中的,这个区块及其挖矿收入属于作者中本聪。来看看本尊:
curl https://blockchain.info/rawblock/000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f { "hash":"000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f", "ver":1, "prev_block":"0000000000000000000000000000000000000000000000000000000000000000", "mrkl_root":"4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b", "time":1231006505, "bits":486604799, "fee":0, "nonce":2083236893, "n_tx":1, "size":285, "block_index":14849, "main_chain":true, "height":0, "tx":[ { "lock_time":0, "ver":1, "size":204, "inputs":[ { "sequence":4294967295, "witness":"", "script":"04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73" } ], "weight":816, "time":1231006505, "tx_index":14849, "vin_sz":1, "hash":"4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b", "vout_sz":1, "relayed_by":"0.0.0.0", "out":[ { "addr_tag_link":"https:\/\/en.bitcoin.it\/wiki\/Genesis_block", "addr_tag":"Genesis of Bitcoin", "spent":false, "tx_index":14849, "type":0, "addr":"1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa", "value":5000000000, "n":0, "script":"4104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac" } ] }] }
请注意prev_block之中的一串“0”和height中的“0”,这证明这是链表的root。
创世块有个有趣的“副作用”,因为比特币“账本”的不可篡改性,其内容的唯一确定性是无可质疑的,而且人人可以验证。
因此只要有人用创世块地址的私钥签名一份声明,那就可以肯定是中本聪本人的声明,或者本人泄露了私钥。
如果说秘钥是比特币世界的印章的话,创世块地址对应的秘钥就是传国玉玺。中本聪的比特币地址就是addr中的:1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa。
创世纪区块可以看源码文件:src/chainparams.cpp,其中的:assert(consensus.hashGenesisBlock == uint256S("0x000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f"));
- Merkle Tree:默克尔树,通常也被称作Hash Tree,顾名思义,就是存储hash值的一棵树。Merkle树的叶子是数据块(例如,文件或者文件的集合)的hash值,在区块链中代表用于记账的账本内容。非叶节点是其对应子节点串联字符串的hash。hash算法也就是摘要算法,用于保证主体内容的一点点改变都导致hash内容的改变,逐级的树状结构,保证下一级的数据不被篡改。这里使用默克尔树而不是整个数据块做一个hash值,起源其实是p2p软件,用于在整个账本下载的时候,如果发生错误,不需要全部下载,而是逐级回溯hash值,下载出错的一小块数据就可以。
- 电子签名:比特币也是最早实践电子签名的应用之一。
电子签名分成私钥、公钥两部分,有私钥的话,可以经过计算得到公钥,反之则不可。工作时,私钥自己持有,自己负责保密,公钥发布在网络,所有人都可以看到。
所有的交易数据,都由交易者的私钥签名,其它人则可以使用公布的公钥对签名进行验证。对交易数据的修改会导致签名失效,这个才是比特币系统对资产最大的保证。
比特币电子签名使用ecdsa算法,这个算法有一个小缺陷,就是如果交易记录中仅仅修改了一个字节,仍然会验证通过。
当然这个修改无法做到修改交易金额,但可能造成后续的哈希计算得到完全不同的ID值。在攻击方网络足够快、广播能力足够强的话,可能在小范围内造成的伪造出现。
历史上曾经发生过利用这个方式伪造交易失败并向交易商索赔成功的事情,但是究其原因不算比特币系统设计问题,如果交易商严格遵循交易原则,只接受程序结果,不人为干预,是可以避免损失的。
比特币源码:src/secp256k1/src/secp256k1.c这里主要处理签名相关的东西。
电子签名机制今天已经无孔不入的遍布互联网各个环节,包括https网站、email、电子交易、网络银行,现在的问题已经不是要不要用电子签名,而是努力把每个由公网经过的环节都尽可能的签名化才是现在的趋势。 - 智能合约:比特币系统中的整个过程的商业逻辑就算做智能合约,与他人完成交易就相当于双方共同签订一份合约,随后利用区块链记账、交易广播、工作量证明等手段保障合约正确执行并不被篡改、攻击。这个描述比较抽象化,可能涉及了多个方面。以我个人认为,“智能合约”的理念才是比特币系统中最可贵的概念。
- 交易确认:交易确认分成两个部分,一个是区块生成后的确认,一个是一笔比特币交易完成后的确认,两者都设定了交易确认时间(当前是10分钟)。主要原因都是P2P的广播是需要时间的,在这个广播被尽可能多的人收到之前就确认交易,前者会造成区块链的冲突而出现分支,未能及时矫正的分支甚至会成为树从而造成区块链崩溃。后者未能广播之前就确认会出现伪造的可能,而广播被更多人收到之后,伪造就需要工作量证明,也就不可能达到了。但通常认为,达到不可逆转的6个区块链的标准,6*10实际是1小时的时间,才能真正确定一笔交易安全。