IOTA 基石 - Transaction pow
一、概要
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<Thread> 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位进行填充。对于详细的转换方式，这里不再深入。
到这里，transaction pow 分析完毕。
