IOTA|IOTA 基石 - Transaction pow IOTA基石-Transactionpow

一、概要
proof of work(pow) 作为区块链技术中最早的共识算法，并应用与比特币、以太坊等区块链项目之中；但pow最早是用于系统抵挡拒绝服务攻击和网络爬虫，后来也被广泛使用于反垃圾邮件，其设计理念是，一个正常用户写一封邮件是需要一定的时间，而发送垃圾邮件者是无法接受这个等待的时间，如果pow系统能够使垃圾邮件发送者需要更多的时间来发送邮件，就可以增大他们的攻击成本，从而起到抵挡攻击的作用。同样，在iota 中，pow 并不是用于共识之中，而是作为交易流程中重要的一环，防止垃圾交易，以及防止女巫攻击，因此，我们来深入IOTA 中pow 实现。
二、详细介绍&解析
随着比特币成功后，pow为人们熟知，基于HASH的pow算法常被人误解为是pow的代名词，然而，hash只是pow采用一种算法而已，你可以使用大部分需要迭代运算的算法(如卷积求导、大质数分解这些复杂的运算)实现POW，其实稍微调整或修改一下pow算法，就有可能诞生一种山寨币，然后大肆宣传欺骗小白，了解原理后就知道这并没有什么卵用。
一方面，由于区块链体系中，包括iota，都是使用hash作为pow 的实现算法，因此，本文还是使用hash 作为pow的其原理分析。另一方面，正如上述所说，不同系统使用的实现算法不一，如果没有具体公布其设计思路，很难深入其hash 算法的实现思路，因此，本文在分析IOTA的pow算法时，不会从数学角度以及核心的hash 实现来深入分析，只从工程学的使用即设计来分析。
2.1pow 原理正如上述介绍，工作量证明最常采用的方式是hash散列函数，因此，我们来详细介绍基于hash 函数的工作量证明是如何工作的。这里，我们作出以下设定：

这里使用的hash 函数为SHA256;
需要被证明的内容用String content表示；
工作量难度系数为16。

基于上述假定，我们通过以下代码来看看什么是工作量证明：

public int searchCounter(String content) { int counter = 1; while(true) { byte[] hashReuslt = SHA256(content + counter)// 转成16进制字符串 String hexHash = toHex(hashReuslt); //难度系数为16，即hexHash 前4个数字为0； if (prefix.equals("0000")) { // find the counter，完成工作量证明 break; } counter++; } return counter; }

我们来解析上述代码。首先，在代码中，定义一个初始值为1计数器counter，代表运算次数，然后在一个while 循环内，通过hash函数SHA256 对需要证明的内容以及计数器的拼接值，求其hash值，而hash 函数SHA256 返回的是长度为256二进制数值，即长度为 256/8 = 32的byte数组，这里用hashReuslt表示。然而，为例方便展示，在通过hashReuslt转成16进制字符串，我们知道，一个16进制数值需要用4个二进制位表示，因此，如果对应难度系数为16意味着前16个二进制位都为0，那么，使用16进制来表示的话，只需前4个 hexHash的字符都为0即可，来判断是否结束运算，如果符合条件，则结束运算；否则，继续counter 自增一，重复上述运算，直到符合条件为止。
当运算方，完成工作量运算后，即找到这样一个符合条件的counter，运算方会使用String workContent = content + counter的方式发给验证方，而验证方只要通过以下简单验证：

public boolean verify(workContent) { byte[] hashReuslt = SHA256(content + counter) // 转成16进制字符串 String hexHash = toHex(hashReuslt); if (hexHash.startsWith("0000")) { return true; } return false; }

据上述实现，只需一次SHA256 运算，即可快速判断运算方所证明的内容是否经工作量证明。
假设我们要处理数据 Hello World(即String content = "Helle World")，那么，至少需要107105 次运算，即counter = 107105，才可以使SHA256("Helle World107105") 的结果，其前16个二进制数字为0，这里为了方便运算，使用16进制表示其结果：

0000BFE6AF4232F78B0C8EBA37A6BA6C17B9B8671473B0B82305880BE077EDD9

最后，我们在来定性分析其工作量，由于散列函数SHA256是基本均匀分布的，因此，对于我们生成的每一个内容hash摘要来说，对应的的哈希值在每一位上出现0和1的概率应该是相同的，假设，我们设定难度值为16，那么，从概率分布来说，我们平均只需2^16次运算，即可得到答案。在假设每次SHA256运算所需时间位 t 秒，那么，平均来说，一次工作量证明所需时间位t * 2^16。
基于hash 函数的特性，用户几乎无法从h(content)反推回content，因此借由该特征，让用户进行大量的穷举运算，就可以达成工作量证明。
2.2IOTA pow 使用在IOTA中，其pow用于防止垃圾交易以及女巫攻击的，具体的使用方式与【2.1pow 原理】所讲解的基于hash实现的pow基本一致，并且也是通过n个连续零值来调节难度，只不过，iota中所使用的hash函数使其自创的hash 函数CURL，这个已在《IOTA 基石 - Sponge 算法详解》详细分析。
iota将相关的pow所依赖的算法都封装在PearlDiver类，并通过以下

public synchronized boolean search(final byte[] transactionTrits, final int minWeightMagnitude, int numberOfThreads)

来执行pow运算。这里我门先来详细解析以下入参：

transactionTrits，该pow 算法是专门针对长度位8019 byte字节数组的transaction序列化实体，当然，这里的每一个byte 都是平衡三进制数值，并且，transactionTrits字节数组中，最后243 位是用来存储nonce，该nonce值用于难度结果校验的，并在方法search(...)内部赋值。
minWeightMagnitude，该参数为难度系数值，用于控制pow运算量;
numberOfThreads，并发线程数，用于并发查找nonce得的线程数量。

因此，运算方只要通过以下调用，则可以完成pow 运算(难度系数为9，线程数为1)：

pearlDiver.search(myTrits, 9, 1);

而校验方，则通过：

boolean verify(byte[] myTrits, int minWeightMagnitude) {byte[] hashTrits = new byte[243]; Sponge curl = new Curl(SpongeFactory.Mode.CURLP81); //hash的入参为经pow运算的myTrits，with nonce curl.absorb(myTrits, 0, myTrits.length); //将myTrits 的hash结果写至hashTrits curl.squeeze(hashTrits, 0, Curl.HASH_LENGTH); // 求hashTrits末尾处开始，连续为0的个数 int zeros = 0; while (index-- > 0 && hashTrits[index] == 0) { zeros++; } return zeros >= minWeightMagnitude }

上述校验与【2.1pow 原理】所讲解的校验流程基本一致，只不过iota 所校验的连续0个数放在了尾部。
到这里，IOTA pow 使用分析完毕
2.3IOTA IOTA pow 分析这里，我们在来简单分析一下pearlDiver.search(...)的实现：

public synchronized boolean search(final byte[] transactionTrits, final int minWeightMagnitude, int numberOfThreads) { //检验入参transactionTrits length of with nonce= 8019 //0 <=minWeightMagnitude< 243 (length(nonce) = 243) validateParameters(transactionTrits, minWeightMagnitude); synchronized (syncObj) { state = State.RUNNING; }// 729 = 3 *243 final long[] midStateLow = new long[729]; final long[] midStateHigh = new long[729]; // 通过transactionTrits 初始化状态midStateLow 以及 midStateHigh initializeMidCurlStates(transactionTrits, midStateLow, midStateHigh); if (numberOfThreads <= 0) { // 获取cpu核数 int available = Runtime.getRuntime().availableProcessors(); numberOfThreads = Math.max(1, Math.floorDiv(available * 8, 10)); } List workers = new ArrayList<>(numberOfThreads); while (numberOfThreads-- > 0) { long[] midStateCopyLow = midStateLow.clone(); long[] midStateCopyHigh = midStateHigh.clone(); // 并行找nonce Runnable runnable = getRunnable(numberOfThreads, transactionTrits, minWeightMagnitude, midStateCopyLow, midStateCopyHigh); Thread worker = new Thread(runnable); workers.add(worker); worker.setName(this + ":worker-" + numberOfThreads); worker.setDaemon(true); worker.start(); // 启动任务 } for (Thread worker : workers) { try { worker.join(); // 等待所有的线程返回 } catch (InterruptedException e) { synchronized (syncObj) { state = State.CANCELLED; } } } return state == State.COMPLETED; }

上述代码段为执行pow 准备代码段，包括像hash 转换所需要依赖的高低位状态midStateCopyLow 、midStateCopyHigh初始化(这里的初始化是iota定制的，感兴趣的同学可以自行阅读)，然后通过多并行的方式取查找符合条件的nonce，我们接着深入具体的任务查找任务构造 getRunnable(...):

private Runnable getRunnable(final int threadIndex, final byte[] transactionTrits, final int minWeightMagnitude, final long[] midStateCopyLow, final long[] midStateCopyHigh) { return () -> { for (int i = 0; i < threadIndex; i++) { increment(midStateCopyLow, midStateCopyHigh, 162 + 243 / 9, 162 + (243 / 9) * 2); }final long[] stateLow = new long[243 * 3]; final long[] stateHigh = new long[243 * 3]; final long[] scratchpadLow = new long[243 * 3]; final long[] scratchpadHigh = new long[243 * 3]; final int maskStartIndex = 243 - minWeightMagnitude; long mask = 0; // do pow, 查找符合条件的nonce while (state == State.RUNNING && mask == 0) {increment(midStateCopyLow, midStateCopyHigh, 162 + (CURL_HASH_LENGTH / 9) * 2, CURL_HASH_LENGTH); //将midStateCopyLow 拷贝至stateLow // midStateCopyHigh 拷贝至stateHigh copy(midStateCopyLow, midStateCopyHigh, stateLow, stateHigh); //转换 transform(stateLow, stateHigh, scratchpadLow, scratchpadHigh); mask = HIGH_BITS; for (int i = maskStartIndex; i < CURL_HASH_LENGTH && mask != 0; i++) { mask &= ~(stateLow[i] ^ stateHigh[i]); } } // 当state != State.RUNNING时，说明别的线程已经找到符合条件的nonce // 当mask!=0时，说明当前线程找到符合条件的nonce if (mask != 0) { synchronized (syncObj) { // 加锁，确保只有一个线程可以填写nonce if (state == State.RUNNING) { // 设置当前状态为完成 state = State.COMPLETED; long outMask = 1; while ((outMask & mask) == 0) { outMask <<= 1; } // 填充nonce值 for (int i = 0; i < CURL_HASH_LENGTH; i++) { transactionTrits[TRANSACTION_LENGTH - CURL_HASH_LENGTH + i] = (midStateCopyLow[i] & outMask) == 0 ? 1 : (midStateCopyHigh[i] & outMask) == 0 ? (byte) -1 : (byte) 0; } } } } }; }// hash 转换 private static void transform(final long[] stateLow, final long[] stateHigh, final long[] scratchpadLow, final long[] scratchpadHigh) {for (int round = 0; round < Curl.NUMBER_OF_ROUNDSP81; round++) { copy(stateLow, stateHigh, scratchpadLow, scratchpadHigh); int scratchpadIndex = 0; for (int stateIndex = 0; stateIndex < CURL_STATE_LENGTH; stateIndex++) { final long alpha = scratchpadLow[scratchpadIndex]; final long beta = scratchpadHigh[scratchpadIndex]; if (scratchpadIndex < 365) { scratchpadIndex += 364; } else { scratchpadIndex += -365; } final long gamma = scratchpadHigh[scratchpadIndex]; final long delta = (alpha | (~gamma)) & (scratchpadLow[scratchpadIndex] ^ beta); stateLow[stateIndex] = ~delta; stateHigh[stateIndex] = (alpha ^ gamma) | delta; } } }

上述代码段的核心是对midStateCopyLow 以及midStateCopyHigh 进行(代换-置换网络)的算法进行hash转换，直到找到符合条件的nonce 值为止，最后在通过midStateCopyLow 以及midStateCopyHigh对transactionTrits 的末尾243位进行填充。对于详细的转换方式，这里不再深入。
【IOTA|IOTA 基石 - Transaction pow】到这里，transaction pow 分析完毕。