再者聚集于”数据存储”这一环节,每种数额块中富含比特币交易音信

据上海证券报消息,华泰证券资产管理信息技术部负责人张铭锋日前表示,区块链的共识机制能确保信息在传输过程中的透明性、完整性和及时性,防止传统数据共享模式下的数据篡改。

图片 1

图片 2image

那些参与方众多、缺乏集中交易场所及信息共享机制的交易品种,如票据业务、衍生品交易等,都适用区块链。

最终内容请以原文为准:

最近研究区块链,从区块链起源比特币入手,有些许收获,整理成文分享给大家。文章着重讲解比特币交易系统,适合对比特币系统或区块链技术有一定了解的人群阅读。通过此文可了解比特币底层技术区块链的运作原理。因为大多数文章要么泛泛而谈区块链能去中心化、能防篡改、能追溯,可以改变行业改变世界,而不加以解释如何实现,要么只针对某一环节进行深度解析,缺乏整体的串联介绍,所以本文尝试进行有一定深度的整体介绍,希望能帮助大家理解比特币系统的实现。

在这一系列文章的最开始部分,我们提到过区块链是一个分布式的数据库。那时候,我们决定跳过”分布式”这一环节,并且聚焦于”数据存储”这一环节。到目前为止,我们几乎实现了区块链的所有组成部分。在本篇文章中,我们将会涉及一些在前面的文章中所忽略的一些机制,并且在下一篇文章中我们将开始研究区块链的分布式特性。

中本聪在比特币白皮书中介绍说,比特币交易系统是一种完全通过点对点技术实现的电子现金系统,它使得在线支付能够直接由一方发起并支付给另一方,中间不需要通过任何的金融机构(基于密码学原理而不基于信用)也能防止双重支付问题(double-spending)。该网络通过随机散列对全部交易加上时间戳(timestamps),将他们合并入一个不断延伸的基于随机散列的工作量证明(proof-of-work)的链条作为交易记录,除非重新完成全部的工作量证明,形成的交易记录将不可更改。其实就是一串使用密码学方法相关联产生的数据块,每一个数据块中包含比特币交易信息,用于验证其信息的有效性和生成下一个区块。这个系统核心流程是比特币的产生与交易。

前面各个部分内容:

接下来将会对如何产生比特币,比特币如何交易,去中心化系统如何解决共识问题,数据为何不可篡改,如何追溯进行讲解(这些问题的答案在文中都会用下划线标出便于大家定位)。

  1. 基本原型
  2. 工作量证明
  3. 持久化 & 命令行
  4. 交易
  5. 地址

文章主要分为三大块:一是比特币的产生;二是比特币的交易;三是附录,包含常见问题和涉及技术介绍,帮助大家理解文章。

在 持久化 & 命令行
这篇文章中,我们研究了比特币核心存储区块的方式。当中我们提到过与区块相关的数据存储在
blocks 这个数据桶中,而交易数据则存储在 chainstate
这个数据桶中,让我们来回忆一下,chainstate 数据桶的数据结构:

整个挖矿流程如下:

  • ‘c’ + 32-byte transaction hash -> unspent transaction output
    record for that transaction

    某笔交易的UTXO记录

  • 检索待确认交易内存池,选择包含进区块的交易。中本聪创造的创世区块并无交易打包,所以挖的是空块。因为每一个区块都有容量限制,后人挖矿一般会根据手续费对待确认交易集进行排序,由高到低进行打包,尽可能使得每次挖矿的收益最大;(挖矿除了比特币奖励外还有交易确认记录的手续费)

  • 构造Coinbase,确定打包交易集,统计手续费等信息;

  • 构造HashMerkleRoot,对所有交易构造Merkle数;

  • 填充其他字段,获得完整区块头;(步骤234如果不懂没关系,看完全文再回头看就好理解了)

  • 对区块头进行SHA256D运算(两次SHA256计算)(详见下文,建议先看看附录一的哈希运算,有助于理解);

  • 验证结果,如果符合难度,则广播全网,全网验证通过则所有节点一起记录,不符合改变参数继续计算并验证;(共识机制其实就是此算法及其验证过程,无中心却人人认可;比特币产自哪个节点完全看算力看运气;每个节点都拥有所有交易记录信息)

上述过程最重要的就是哈希计算,过程如下:

  • ‘B’ -> 32-byte block hash: the block hash up to which the
    database represents the unspent transaction outputs

    数据库所表示的UTXO的区块Hash

  • 通过Sha256D(version+hashPrevBlock+hashMerkleRoot+nTime+nBits+nonce)(这几个字段见表2区块头结构)得到64位的十六进制或者256位的二进制哈希值;

从那篇文章开始,我们已经实现了比特币的交易机制,但是我们还没有用到
chainstate
数据桶去存储我们的交易输出。所以,这将是我们现在要去做的事情。

图片 3image

chainstate 不会去存储交易数据。相反,它存储的是 UTXO
集,也就是未被花费的交易输出集合。除此之外,它还存储了”数据库所表示的UTXO的区块Hash”,我们这里先暂且忽略这一点,因为我们还没有用到区块高度(这一点我们会在后面的文章进行实现)。

表1:区块结构(区块头信息见表2和交易详情结构见表3表4)

那么,我们为什么需要 UTXO 池呢?

图片 4image

一起来看一下我们前面实现的 findUnspentTransactions 方法:

表2:区块头结构

 /** * 查找钱包地址对应的所有未花费的交易 * * @param pubKeyHash 钱包公钥Hash * @return */ private Transaction[] findUnspentTransactions(byte[] pubKeyHash) throws Exception { Map<String, int[]> allSpentTXOs = this.getAllSpentTXOs(pubKeyHash); Transaction[] unspentTxs = {}; // 再次遍历所有区块中的交易输出 for (BlockchainIterator blockchainIterator = this.getBlockchainIterator(); blockchainIterator.hashNext { Block block = blockchainIterator.next(); for (Transaction transaction : block.getTransactions { String txId = Hex.encodeHexString(transaction.getTxId; int[] spentOutIndexArray = allSpentTXOs.get; for (int outIndex = 0; outIndex < transaction.getOutputs().length; outIndex++) { if (spentOutIndexArray != null && ArrayUtils.contains(spentOutIndexArray, outIndex)) { continue; } // 保存不存在 allSpentTXOs 中的交易 if (transaction.getOutputs()[outIndex].isLockedWithKey(pubKeyHash)) { unspentTxs = ArrayUtils.add(unspentTxs, transaction); } } } } return unspentTxs; }
  • 将结果哈希值与目标哈希值进行比较,如果当前nonce值计算的哈希值小,那么挖矿成功,否则,挖矿失败,旷工需要更改nonce值再试,直到成功;–以上其实就是工作量证明机制(Proof-of-Work),解决了共识问题。

该方法是用来查找钱包地址对应的包含未花费交易输出的交易信息。由于交易信息是存储在区块当中,所以我们现有的做法是遍历区块链中的每个区块,然后遍历每个区块中的交易信息,再然后遍历每个交易中的交易输出,并检查交易输出是否被相应的钱包地址所锁定,效率非常低下。截止2018年3月29号,比特币中有
515698 个区块,并且这些数据占据了140+Gb
的磁盘空间。这也就意味着一个人必须运行全节点(下载所有的区块数据)才能验证交易信息。此外,验证交易信息需要遍历所有的区块。

其中,

针对这个问题的解决办法是需要有一个存储了所有UTXOs的索引,这就是 UTXOs
池所要做的事情:UTXOs池其实是一个缓存空间,它所缓存的数据需要从构建区块链中所有的交易数据中获得(通过遍历所有的区块链,不过这个构建操作只需要执行一次即可),并且它后续还会用于钱包余额的计算以及新的交易数据的验证。截止到2017年9月,UTXOs池大约为
2.7Gb。

  • 目标哈希值target=2*(256-difficulty)

  • difficulty值由节点自动调整,规则为New
    difficulty=OldDifficulty*(Actual time of last 2016
    Blocks/20160minutes)即:最新2016个区块花费时长与20160分钟比较所得,其中20160分钟是这些区块以10分钟一个的速率所花费的时长。

好了,让我们来想一下,为了实现 UTXOs
池我们需要做哪些事情。当前,有下列方法被用于查找交易信息:

那么计算得到的64位的十六进制或者256位的二进制哈希值如何与目标哈希值进行比较呢?如果是二进制直接看结果哈希值的前N个比特位是否全部为0,是的话挖矿成功。(0越多值越小;值越小,N越大,难度越大)可以类比抛硬币,按顺序抛256个硬币,编号为1至256,每进行一次Hash运算,就像抛一次硬币,256个硬币抛出的结果若前N个硬币全部正面向上则获取记账权,挖矿成功。如果是十六进制,直接比较就行。(二进制也可直接比较)

  1. Blockchain.getAllSpentTXOs ——
    查询所有已被花费的交易输出。它需要遍历区块链中所有区块中交易信息。

  2. Blockchain.findUnspentTransactions ——
    查询包含未被花费的交易输出的交易信息。它也需要遍历区块链中所有区块中交易信息。

  3. Blockchain.findSpendableOutputs ——
    该方法用于新的交易创建之时。它需要找到足够多的交易输出,以满足所需支付的金额。需要调用
    Blockchain.findUnspentTransactions 方法。

  4. Blockchain.findUTXO ——
    查询钱包地址所对应的所有未花费交易输出,然后用于计算钱包余额。需要调用

    Blockchain.findUnspentTransactions 方法。

  5. Blockchain.findTransaction ——
    通过交易ID查询交易信息。它需要遍历所有的区块直到找到交易信息为止。

图片 5image

如你所见,上面这些方法都需要去遍历数据库中的所有区块。由于UTXOs池只存储未被花费的交易输出,而不会存储所有的交易信息,因此我们不会对有
Blockchain.findTransaction 进行优化。

图1:挖矿原理图

那么,我们需要下列这些方法:

所以,挖矿流程就是节点构造区块,初始化区块头各字段,计算hash值并验证区块的过程。不合格则nonce自增,再计算并验证,如此往复。每次大约需10分钟产生一个区块,最初每个区块产生50个比特币,每个比特币为1亿聪,之后大约每4年减半。总量大约2100万,到2140年才挖完,而到2045年就挖掉99.9%了。下图是比特币产生年份表

  1. Blockchain.findUTXO ——
    通过遍历所有的区块来找到所有未被花费的交易输出.
  2. UTXOSet.reindex —— 调用上面 findUTXO
    方法,然后将查询结果存储在数据库中。也即需要进行缓存的地方。
  3. UTXOSet.findSpendableOutputs —— 与
    Blockchain.findSpendableOutputs 类似,区别在于会使用 UTXO 池。
  4. UTXOSet.findUTXO —— 与Blockchain.findUTXO
    类似,区别在于会使用 UTXO 池。
  5. Blockchain.findTransaction —— 逻辑保持不变。

图片 6image

这样,两个使用最频繁的方法将从现在开始使用缓存!让我们开始编码吧!

图2:比特币产生年份表

定义 UTXOSet

看上表可以发现第一个区块是在2009年产生的,具体时间是格林威治时间2009年1月3日18:15:05,由中本聪创造。有趣的是,中本聪在创世区块上留下了泰晤士当天的头版文章标题“The
Times 03/Jan/2009 Chancellor on brink of second bailout
forBanks”,讽刺了中心化金融体系并巧妙地证明此区块的生成时间是在09年1月3号之个报纸标题出现之后。下图是创世区块的信息截图,做个了解,记录了区块高度、哈希值、前一区块哈希值、时间难度等交易信息,根据前一区块hash、下一区块哈希可以追溯前一个区块、后一个区块。

@NoArgsConstructor@AllArgsConstructor@Slf4jpublic class UTXOSet { private Blockchain blockchain;}

图片 7image

重建 UTXO 池索引:

图3:创世区块信息

public class UTXOSet { ... /** * 重建 UTXO 池索引 */ @Synchronized public void reIndex() { log.info("Start to reIndex UTXO set !"); RocksDBUtils.getInstance().cleanChainStateBucket(); Map<String, TXOutput[]> allUTXOs = blockchain.findAllUTXOs(); for (Map.Entry<String, TXOutput[]> entry : allUTXOs.entrySet { RocksDBUtils.getInstance().putUTXOs(entry.getKey(), entry.getValue; } log.info("ReIndex UTXO set finished ! "); } ...} 

交易得先从公钥、私钥、地址讲起,构造流程如下:

此方法用于初始化 UTXOSet。首先,需要清空 chainstate
数据桶,然后查询所有未被花费的交易输出,并将它们保存到 chainstate
数据桶中。

  • 使用随机数发生器生成一个256位的私钥;

  • 私钥经过SECP256K1椭圆曲线算法处理,生成公钥,无法反向推出私钥;

  • 将公钥通过SHA256哈希计算得出32字节哈希值(下方有流程图,可参照着理解),再用哈希值进行RIPEMD-160计算得到20字节的哈希值,把版本号—20字节的哈希值组成的21字节数组进行SHA256D运算,取得到的哈希值的头4个字节作为校验和,放在21字节组的尾部,对组成的25位数组进行Base58编码,得到地址。

实现 findSpendableOutputs 方法,供 Transation.newUTXOTransaction
调用

图片 8image

public class UTXOSet { ... /** * 寻找能够花费的交易 * * @param pubKeyHash 钱包公钥Hash * @param amount 花费金额 */ public SpendableOutputResult findSpendableOutputs(byte[] pubKeyHash, int amount) { Map<String, int[]> unspentOuts = Maps.newHashMap(); int accumulated = 0; Map<String, byte[]> chainstateBucket = RocksDBUtils.getInstance().getChainstateBucket(); for (Map.Entry<String, byte[]> entry : chainstateBucket.entrySet { String txId = entry.getKey(); TXOutput[] txOutputs = (TXOutput[]) SerializeUtils.deserialize(entry.getValue; for (int outId = 0; outId < txOutputs.length; outId++) { TXOutput txOutput = txOutputs[outId]; if (txOutput.isLockedWithKey(pubKeyHash) && accumulated < amount) { accumulated += txOutput.getValue(); int[] outIds = unspentOuts.get; if (outIds == null) { outIds = new int[]{outId}; } else { outIds = ArrayUtils.add(outIds, outId); } unspentOuts.put(txId, outIds); if (accumulated >= amount) { break; } } } } return new SpendableOutputResult(accumulated, unspentOuts); } ... } 

图4:地址产生算法

实现 findUTXOs 接口,供 CLI.getBalance 调用:

通过上述流程得到公私钥地址就可以交易了,在交易过程需要通过私钥对交易进行签名,签完名后发起交易,交易会到待确认池子里面,等待节点来打包确认放进区块,也就是上文的挖矿过程。签名通过算法Sig=FuncSig(FuncHash=进行,其中dA是签名私钥、m是交易信息、FuncHash是哈希函数、FuncSig是签名算法、Sig是签名结果。验证过程则是通过一系列函数算法进行验证,略复杂感兴趣可自行了解。数据签名算法的核心在于证明数据的发送方是签名者发出的,防抵赖。签名的这些数据存放在解锁脚本里,如表4交易结构2。比特币系统里的交易分为两种,一种是挖矿所得,即一个区块的第一笔交易,称为coinbase交易;第二种是普通交易,也就是非挖矿交易。

public class UTXOSet { ... /** * 查找钱包地址对应的所有UTXO * * @param pubKeyHash 钱包公钥Hash * @return */ public TXOutput[] findUTXOs(byte[] pubKeyHash) { TXOutput[] utxos = {}; Map<String, byte[]> chainstateBucket = RocksDBUtils.getInstance().getChainstateBucket(); if (chainstateBucket.isEmpty { return utxos; } for (byte[] value : chainstateBucket.values { TXOutput[] txOutputs = (TXOutput[]) SerializeUtils.deserialize; for (TXOutput txOutput : txOutputs) { if (txOutput.isLockedWithKey(pubKeyHash)) { utxos = ArrayUtils.add(utxos, txOutput); } } } return utxos; } ... } 

图片 9image

以上这些方法都是先前 Blockchain
中相应方法的微调版,先前的方法将不再使用。

表3:Coinbase交易结构

有了UTXO池之后,意味着我们的交易数据分开存储到了两个不同的数据桶中:交易数据存储到了
block 数据桶中,而UTXO存储到了 chainstate
数据桶中。这就需要一种同步机制来保证每当一个新的区块产生时,UTXO池能够及时同步最新区块中的交易数据,毕竟我们不想频地进行
reIndex 。因此,我们需要如下方法:

图片 10image

更新UTXO池:

表4:普通交易结构

public class UTXOSet { ... /** * 更新UTXO池 * <p> * 当一个新的区块产生时,需要去做两件事情: * 1)从UTXO池中移除花费掉了的交易输出; * 2)保存新的未花费交易输出; * * @param tipBlock 最新的区块 */ @Synchronized public void update(Block tipBlock) { if (tipBlock == null) { log.error("Fail to update UTXO set ! tipBlock is null !"); throw new RuntimeException("Fail to update UTXO set ! "); } for (Transaction transaction : tipBlock.getTransactions { // 根据交易输入排查出剩余未被使用的交易输出 if (!transaction.isCoinbase { for (TXInput txInput : transaction.getInputs { // 余下未被使用的交易输出 TXOutput[] remainderUTXOs = {}; String txId = Hex.encodeHexString(txInput.getTxId; TXOutput[] txOutputs = RocksDBUtils.getInstance().getUTXOs; if (txOutputs == null) { continue; } for (int outIndex = 0; outIndex < txOutputs.length; outIndex++) { if (outIndex != txInput.getTxOutputIndex { remainderUTXOs = ArrayUtils.add(remainderUTXOs, txOutputs[outIndex]); } } // 没有剩余则删除,否则更新 if (remainderUTXOs.length == 0) { RocksDBUtils.getInstance().deleteUTXOs; } else { RocksDBUtils.getInstance().putUTXOs(txId, remainderUTXOs); } } } // 新的交易输出保存到DB中 TXOutput[] txOutputs = transaction.getOutputs(); String txId = Hex.encodeHexString(transaction.getTxId; RocksDBUtils.getInstance().putUTXOs(txId, txOutputs); } } ... } 

交易结构构造完毕后即可发起交易,交易信息会到待确认交易池中等待打包确认。在比特币的交易信息里,有两个很关键的字段:输入/输出,输入并非明确某人有多少数量的比特币,而是指向比特币来源,即前一个已确认的交易中的UTXO;输出定义某人有多少比特币,并且输出要全部输出,分为两部分,一部分给外人,一部分给自己,其实就是找零机制。正是这种设计建立起分布式账簿,所有区块和交易形成互相连接的链条。找零机制有个好处就是保护隐私。因为每一笔比特币交易都可在全球性的公共总账上看到,如果某个比特币地址偶然被知道其使用者,那么将不利于使用者的隐私保护。而有了找零机制,地址A发起付款给地址B,找零地址不设置为A,而是改为C。那么地址B和C是不是A?都有可能,这样整个交易的真相将变得难以推测。

让我们将 UTXOSet 用到它们所需之处去:

图片 11image

public class CLI { ... /** * 创建区块链 * * @param address */ private void createBlockchain(String address) { Blockchain blockchain = Blockchain.createBlockchain; UTXOSet utxoSet = new UTXOSet(blockchain); utxoSet.reIndex(); log.info("Done ! "); } ... } 

图5:交易例图

当创建一个新的区块链是,我们需要重建 UTXO
池索引。截止目前,这是唯一一处用到 reIndex
的地方,尽管看起有些多余,因为在区块链创建之初仅仅只有一个区块和一笔交易。

交易信息在进入待确认交易池后,每一个节点都将收到的交易信息纳入区块中,当一个节点找到一个足够难度的工作量证明后会向全网进行广播,其他节点会验证该节点区块中所有的交易都是有效且之前未存在过才会认可该区块的有效性(通过默克尔树进行比对校验—防篡改,默克尔树可查看附录二),验证通过则全网的节点都会跟随在该区块的末尾制造新区块以延长该链条,被接受的区块的随机散列哈希值视为先于新区块的随机散列哈希值。如果有两个节点同时找到答案,其他节点会在自己率先收到的区块基础上进行工作,直到下一个区块产生,其中一条链条被证实为是较长的一条,那么较短分支链条上的节点将转换阵营,开始在较长链条上工作。

修改 CLI.send 接口:

在这个共识机制中,新的交易不需要抵达全部节点,只要交易信息能抵达足够多的节点,那么这些交易将被整合进一个区块中,其他没有接收到的节点后续会发现自己缺失了某个区块,重新下载更新即可,此为拜占庭容错。–拜占庭问题可见上一篇文章。最终整个交易信息会被打包在不同的区块之中,区块与区块直接通过哈希算法、时间戳关联起来,实现可追溯。

public class CLI { ... /** * 转账 * * @param from * @param to * @param amount */ private void send(String from, String to, int amount) throws Exception { ... Blockchain blockchain = Blockchain.createBlockchain; Transaction transaction = Transaction.newUTXOTransaction(from, to, amount, blockchain); Block newBlock = blockchain.mineBlock(new Transaction[]{transaction}); new UTXOSet(blockchain).update; ... } ... } 

图片 12image

当一个新的区块产生后,需要去更新 UTXO 池数据。

图6:区块链接图

让我们来检查一下它们的运行情况:

总结一下:比特币电子现金系统通过对每一笔交易进行哈希处理进行关联、通过默克尔树将交易与区块进行关联,通过区块头哈希与下一区块进行关联,实现了整个交易-交易、交易-区块、区块-区块之间的关联,实现过程可追溯;通过哈希处理的默克尔树进行信息比对校验、工作量证明机制、时间戳服务器,实现了防篡改、防双重支付;通过工作量证明机制下的共识算法以及激励,实现了系统去中心化;当然其中还涉及到各种密码学原理,比如非对称性加密技术保证的数据传输安全、Merkle
tree保证的数据真实并优化存储等。所以,其实其底层技术区块链优势无非就两点,一是共识机制打造的去中心化系统,相比较传统技术可以更好解决某些问题;二是密码学技术打造的防篡改可追溯,可以很好解决各行业领域存在的信任问题;至于具体有什么场景可以应用,如何解决这些场景的痛点,我们下次再聊!

$ java -jar blockchain-java-jar-with-dependencies.jar createwalletwallet address : 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf$ java -jar blockchain-java-jar-with-dependencies.jar createwalletwallet address : 1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG$ java -jar blockchain-java-jar-with-dependencies.jar createwalletwallet address : 1L1RoFgyjCrNPCPHmSEBtNiV3h2wiF9mZV$ java -jar blockchain-java-jar-with-dependencies.jar createblockchain -address 1JgppX2xMshr35wHzvNWQBejUAZ3Te5MdfElapsed Time: 164.961 seconds correct hash Hex: 00225493862611bc517cb6b3610e99d26d98a6b52484c9fa745df6ceff93f445 Done ! $ java -jar blockchain-java-jar-with-dependencies.jar getbalance -address 1JgppX2xMshr35wHzvNWQBejUAZ3Te5MdfBalance of '1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf': 10$ java -jar blockchain-java-jar-with-dependencies.jar send -from 1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG -to 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf -amount 5java.lang.Exception: ERROR: Not enough funds$ java -jar blockchain-java-jar-with-dependencies.jar send -from 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf -to 1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG -amount 2Elapsed Time: 54.92 seconds correct hash Hex: 0001ab21f71ff2d6d532bf3b3388db790c2b03e28d7bd27bd669c5f6380a4e5b Success!$ java -jar blockchain-java-jar-with-dependencies.jar send -from 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf -to 1L1RoFgyjCrNPCPHmSEBtNiV3h2wiF9mZV -amount 2Elapsed Time: 54.92 seconds correct hash Hex: 0009b925cc94e3db8bab2958b1fc2d1764aa15531e20756d92c3a93065c920f0 Success!$ java -jar blockchain-java-jar-with-dependencies.jar getbalance -address 1JgppX2xMshr35wHzvNWQBejUAZ3Te5MdfBalance of '1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf': 6$ java -jar blockchain-java-jar-with-dependencies.jar getbalance -address 1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoGBalance of '1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG': 2$ java -jar blockchain-java-jar-with-dependencies.jar getbalance -address 1L1RoFgyjCrNPCPHmSEBtNiV3h2wiF9mZVBalance of '1L1RoFgyjCrNPCPHmSEBtNiV3h2wiF9mZV': 2

附录一:哈希算法

前面的章节中我们省略了矿工挖矿的奖励机制。时机已经成熟,该实现它了。

哈希算法也称为散列函数算法,在区块链中应用广泛。看一个转换例子比较直观,一个字符串xingfushifendouchulaide的hash运算结果。

矿工奖励其实是一个 coinbase
交易。当一个矿工节点开始去生产一个新的区块时,他会从队列中取出一些交易数据,并且为它们预制一个
coinbase 交易。这笔 coinbase 交易中仅有的交易输出包含了矿工的公钥hash。

Text:xingfushifendouchulaide

只需要更新 send 命令接口,我们就可以轻松实现矿工的奖励机制:

算法:sha256

public class CLI { ... /** * 转账 * * @param from * @param to * @param amount */ private void send(String from, String to, int amount) throws Exception { ... Blockchain blockchain = Blockchain.createBlockchain; // 新交易 Transaction transaction = Transaction.newUTXOTransaction(from, to, amount, blockchain); // 奖励 Transaction rewardTx = Transaction.newCoinbaseTX; Block newBlock = blockchain.mineBlock(new Transaction[]{transaction, rewardTx}); new UTXOSet(blockchain).update; ... } ... } 

结果:

还需要修改交易验证方法,coinbase 交易直接验证通过:

b717189a738923eca3789287390b9b9c8a7839bca783928000cbdabed892bc43

public class Blockchain { /** * 交易签名验证 * * @param tx */ private boolean verifyTransactions(Transaction tx) { if (tx.isCoinbase { return true; } ... } ... } 

如果用MD5加密,运算结果是32位十六进制,用Sha512加密,结果是128位十六进制。哈希算法其实就是一个映射的关系组,可以实现快速将明文转换为hash值,而极难在短时间内反推出明文。另外,当明文稍作修改,hash值会有很大出入,不同的明文,难以出现相同hash值。万一真的出现明文x不等于y,而f的情况,那么即产生了冲突,一般会通过链接法、开放定址法、桶定址法来解决。

在我们的实现逻辑中,代币的发送也是区块的生产者,因此,奖励也归他所有。

哈希函数一般有以下几种:

让我们来验证一下奖励机制:

  • 直接取余法:取余

  • 乘法取整法:取整

  • 平方取中法:平方后取中间

  • 加法hash:把输入元素加起来得到结果

  • 乘法hash:乘以某个固定或不断变化的数

  • 位运算hash:利用各种位运算来混合输入元素

  • 混合hash:通过各种hash混合构造

$ java -jar blockchain-java-jar-with-dependencies.jar createwallet wallet address : 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD$ java -jar blockchain-java-jar-with-dependencies.jar createwallet wallet address : 17crpQoWy7TEkY9UPjZ3Qt9Fc2rWPUt8KX$ java -jar blockchain-java-jar-with-dependencies.jar createwallet wallet address : 12L868QZW1ySYzf2oT5ha9py9M5JrSRhvT$ java -jar blockchain-java-jar-with-dependencies.jar createblockchain -address 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUDElapsed Time: 17.973 secondscorrect hash Hex: 0000defe83a851a5db3803d5013bbc20c6234f176b2c52ae36fdb53d28b33d93 Done ! $ java -jar blockchain-java-jar-with-dependencies.jar send -from 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD -to 17crpQoWy7TEkY9UPjZ3Qt9Fc2rWPUt8KX -amount 6Elapsed Time: 30.887 secondscorrect hash Hex: 00005fd36a2609b43fd940577f93b8622e88e854f5ccfd70e113f763b6df69f7 Success!$ java -jar blockchain-java-jar-with-dependencies.jar send -from 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD -to 12L868QZW1ySYzf2oT5ha9py9M5JrSRhvT -amount 3Elapsed Time: 45.267 secondscorrect hash Hex: 00009fd7c59b830b60ec21ade7672921d2fb0962a1b06a42c245450e47582a13 Success!$ java -jar blockchain-java-jar-with-dependencies.jar getbalance -address 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUDBalance of '1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD': 21$ java -jar blockchain-java-jar-with-dependencies.jar getbalance -address 17crpQoWy7TEkY9UPjZ3Qt9Fc2rWPUt8KXBalance of '17crpQoWy7TEkY9UPjZ3Qt9Fc2rWPUt8KX': 6$ java -jar blockchain-java-jar-with-dependencies.jar getbalance -address 12L868QZW1ySYzf2oT5ha9py9M5JrSRhvTBalance of '12L868QZW1ySYzf2oT5ha9py9M5JrSRhvT': 3

区块链中哈希运算简言之就是通过某种映射将一段字符串转换为哈希值并与目标对象进行比较,在签名验证、默克尔树比对中需要相等,在挖矿竞争中需要小于目标哈希值。

1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD 这个地址一共收到了三份奖励:

应用举例:比如数据完整性校验,最简单的方法是对整个数据做Hash运算得到固定长度的Hash值,然后把得到的Hash值公布,用户下载数据后对数据再次进行Hash运算,比较运算结果和公布的Hash值,如果两个Hash值相等,说明数据没有损坏。可以这样做是因为输入数据的稍微改变会引起Hash运算结果的面目全非,而且根据Hash值反推原始输入数据的特征是困难的。–防篡改

  • 第一次是开采创世区块;

  • 第二次是开采区块:00005fd36a2609b43fd940577f93b8622e88e854f5ccfd70e113f763b6df69f7

  • 第三次是开采区块:00009fd7c59b830b60ec21ade7672921d2fb0962a1b06a42c245450e47582a13

附录二:默克尔树(Merkletree)

Merkle Tree 是这篇文章中我们需要重点讨论的一个机制。

Merkle
tree的叶子节点的value是区块数据Hash,非叶子节点的value是根据它下面所有的叶子节点值hash串联后计算得到的哈希值,如果是单身哈希,就直接对它自己进行哈希运算,得到另一个哈希值,层层往上推,会形成一颗倒三角数,到最顶部就只剩下一个根哈希,叫做Merkle
Root。

正如我前面提到的那样,整个比特币的数据库占到了大约140G的磁盘空间。由于比特币的分布式特性,网络中的每一个节点必须是独立且自给自足的。每个比特币节点都是路由、区块链数据库、挖矿、钱包服务的功能集合。每个节点都参与全网络的路由功能,同时也可能包含其他功能。每个节点都参与验证并传播交易及区块信息,发现并维持与对等节点的连接。一个全节点(full
node)包括以下四个功能:

图片 13image

[图片上传失败…(image-d2ccef-1523845374124)]

附图1:默克尔树结构

随着越来越多的人开始使用比特币,这条规则开始变得越来越难以遵循:让每一个人都去运行一个完整的节点不太现实。在中本聪发布的
比特币白皮书 中,针对这个问题提出了一个解决方案:Simplified Payment
Verification
。SPV是比特币的轻量级节点,它不需要下载所有的区块链数据,也不需要验证区块和交易数据。相反,当SPV想要验证一笔交易的有效性时,它会从它所连接的全节点上检索所需要的一些数据。这种机制保证了在只有一个全节点的情况,可以运行多个SPV轻钱包节点。

图片 14image

更多有关SPV的介绍,请查看:《精通比特币》第八章

附图2:默克尔树在区块中的位置

为了使SPV成为可能,就需要有一种方法在没有全量下载区块数据的情况下,来检查一个区块是否包含了某笔交易。这就是
Merkle Tree 发挥作用的地方了。

比对验证从根哈希值比对起,如果一样,那么整个区块的信息都没问题,因为只要有任一环节出现不一样,根哈希都会不一样。如果根哈希不一样,就可以往下层层追溯,找到不一样的环节。如下图:

比特币中所使用的Merkle
Tree是为了获得交易的Hash值,随后这个已经被Pow系统认可了的Hash值会被保存到区块头中。到目前为止,我们只是简单地计算了一个区块中每笔交易的Hash值,然后在准备Pow数据时,再对这些交易进行
SHA-256
计算。虽然这是一个用于获取区块交易唯一表示的一个不错的途径,但是它不具有到
Merkle Tree的优点。

附录三:常见问题

来看一下Merkle Tree的结构:

  • 什么是区块链?

图片 15image

通俗来讲那就是去中心化的分布式账本。在区块链系统中,只要有能力部署自己的服务器都能加入区块链网络,成为网络节点,所有节点拥有完全一样的权利与义务,可进行读写操作,只要满足机制,其他所有节点会依次同步,实现整个网络中所有节点的数据完全一致。

每一个区块都会构建一个Merkle
Tree,它从最底部的叶子节点开始往上构建,每一个交易的Hash就是一个叶子节点(比特币中用的双SHA256算法)。叶子节点的数量必须是偶数个,但是并不是每一个区块都能包含偶数笔交易数据。如果存在奇数笔交易数据,那么最后一笔交易数据将会被复制一份(这仅仅发生在Merkle
Tree中,而不是区块中)。

晦涩一点讲就是利用块链式数据结构来验证与存储数据,利用分布式节点共识算法来生成和更新数据、利用密码学的方式来保证数据传输和访问安全、利用由自动化脚本代码组成的智能合约来编程和操作数据的一种全新的分布式基础架构与计算范式。

从下往上移动,叶子节点成对分组,它们的Hash值被连接到一起,并且在此基础上再次计算出新的Hash值。新的Hash
形成新的树节点。这个过程不断地被重复,直到最后仅剩一个被称为根节点的树节点。这个根节点的Hash就是区块中交易数据们的唯一代表,它会被保存到区块头中,并被用于参与POW系统的计算。

  • 如何防止双重支付?(工作量证明/共识机制)

Merkle树的好处是节点可以在不下载整个块的情况下验证某笔交易的合法性。
为此,只需要交易Hash,Merkle树根Hash和Merkle路径。

为了达到目的,我们只需要关注交易之前发生的交易,而不需要关注交易之后是否会有双重支付,因为比特币系统交易是公开存储于所有节点并且有一系列的交易时间顺序。只要保证交易之前没有其他交易,那么此笔交易就是安全的,除非发生51%攻击。51%攻击是指攻击者在一笔交易被确认后在同一区块发起另一笔交易B,而后联合全网51%的算力进行挖矿(略大于二分之一的概率挖到),打包交易B确认交易记录,继续挖矿,构造一条比之前区块链更长的链条,再公布全网,全网会认可最长链条的记录,因为最长链包含了最大工作量。所以,只要不发生51%攻击,通过工作量机制证明机制、哈希算法构造的唯一公认的历史交易序列可以避免双重支付问题产生。

Merkle Tree代码实现如下:

  • 对称性加密算法和非对称性加密算法的区别?
package one.wangwei.blockchain.transaction;import com.google.common.collect.Lists;import lombok.Data;import one.wangwei.blockchain.util.ByteUtils;import org.apache.commons.codec.digest.DigestUtils;import java.util.List;/** * 默克尔树 * * @author wangwei * @date 2018/04/15 */@Datapublic class MerkleTree { /** * 根节点 */ private Node root; /** * 叶子节点Hash */ private byte[][] leafHashes; public MerkleTree(byte[][] leafHashes) { constructTree(leafHashes); } /** * 从底部叶子节点开始往上构建整个Merkle Tree * * @param leafHashes */ private void constructTree(byte[][] leafHashes) { if (leafHashes == null || leafHashes.length < 1) { throw new RuntimeException("ERROR:Fail to construct merkle tree ! leafHashes data invalid ! "); } this.leafHashes = leafHashes; List<Node> parents = bottomLevel(leafHashes); while (parents.size { parents = internalLevel; } root = parents.get; } /** * 构建一个层级节点 * * @param children * @return */ private List<Node> internalLevel(List<Node> children) { List<Node> parents = Lists.newArrayListWithCapacity(children.size; for (int i = 0; i < children.size() - 1; i += 2) { Node child1 = children.get; Node child2 = children.get; Node parent = constructInternalNode(child1, child2); parents.add; } // 内部节点奇数个,只对left节点进行计算 if (children.size() % 2 != 0) { Node child = children.get(children.size; Node parent = constructInternalNode(child, null); parents.add; } return parents; } /** * 底部节点构建 * * @param hashes * @return */ private List<Node> bottomLevel(byte[][] hashes) { List<Node> parents = Lists.newArrayListWithCapacity(hashes.length / 2); for (int i = 0; i < hashes.length - 1; i += 2) { Node leaf1 = constructLeafNode(hashes[i]); Node leaf2 = constructLeafNode(hashes[i + 1]); Node parent = constructInternalNode(leaf1, leaf2); parents.add; } if (hashes.length % 2 != 0) { Node leaf = constructLeafNode(hashes[hashes.length - 1]); // 奇数个节点的情况,复制最后一个节点 Node parent = constructInternalNode(leaf, leaf); parents.add; } return parents; } /** * 构建叶子节点 * * @param hash * @return */ private static Node constructLeafNode(byte[] hash) { Node leaf = new Node(); leaf.hash = hash; return leaf; } /** * 构建内部节点 * * @param leftChild * @param rightChild * @return */ private Node constructInternalNode(Node leftChild, Node rightChild) { Node parent = new Node(); if (rightChild == null) { parent.hash = leftChild.hash; } else { parent.hash = internalHash(leftChild.hash, rightChild.hash); } parent.left = leftChild; parent.right = rightChild; return parent; } /** * 计算内部节点Hash * * @param leftChildHash * @param rightChildHash * @return */ private byte[] internalHash(byte[] leftChildHash, byte[] rightChildHash) { byte[] mergedBytes = ByteUtils.merge(leftChildHash, rightChildHash); return DigestUtils.sha256(mergedBytes); } /** * Merkle Tree节点 */ @Data public static class Node { private byte[] hash; private Node left; private Node right; }}

对称性加密算法只有一把密钥保证加密数据的安全,加解密都用这把密钥。如何保存和传递密钥是一件比较头疼的事情,一旦传递过程中泄露密钥数据则毫无安全。而非对称性加密算法可以实现不直接传递密钥,也能完成解密。加密和解密使用不同的规则,两种规则存在某种对应关系即可。如下,非对称性加密算法使用私钥进行加密,对方使用公钥即可解密。

然后修改 Block.hashTransaction 接口:

  • 交易中的锁定脚本解锁脚本的重要性?
public class Block { ... /** * 对区块中的交易信息进行Hash计算 * * @return */ public byte[] hashTransaction() { byte[][] txIdArrays = new byte[this.getTransactions().length][]; for (int i = 0; i < this.getTransactions().length; i++) { txIdArrays[i] = this.getTransactions()[i].hash(); } return new MerkleTree(txIdArrays).getRoot().getHash(); } ... }

在中心化方式下,如果某种协议一旦确定,想要变更是非常困难的,需要经过广泛讨论并取得共识。而如果是脚本系统,那么完全可以通过升级或者推出补丁,甚至发行一个新版本来解决。

MerkleTree的根节点的Hash值,就是区块中交易信息的唯一代表。

  • 为何区块的产生时间是10分钟?

这一节我们主要是对前面的交易机制做了进一步的优化,加入UTXO池和Merkle
Tree机制。

总要有一个值,为何不是更短,比如1分钟。时间过短会导致孤块增多,因为出块时间短也就代表着难度低,举个例子,假如1秒扔10个硬币全正面视为出块,若降为1秒扔2个硬币全正面视为出块,那么同一时间出块的节点将大量增加,却只有一个能被共同认可加入链条,也即无用孤块过多。那为何不是1小时呢?效率问题。

  1. 源码:
  2. The UTXO Set
  3. UTXO set statistics
  4. Merkle Tree
  5. Why every Bitcoin user should understand “SPV security”
  6. Script
  7. “Ultraprune” Bitcoin Core commit
  8. Smart contracts and Bitcoin

内容来源:SteveMark

图片 16image

以下是我们的社区介绍,欢迎各种合作、交流、学习:)

图片 17image

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章