摘要

为了解决当前的挖矿集中化，GPU双挖掘（以及私下ASIC挖掘）问题，提出改变PascalCoin为抗GPU和ASIC的哈希算法。

动机

PascalCoin目前正在通过一个单一池进行99％算力下的集中化挖矿，严重影响了生态系统增长。由于存在双花攻击的风险，交易所不愿列出PASC，基础设施供应商由于低产量与畸形的价格增长而不愿进一步投资。

背景

PascalCoin是100％原创的工作证明数字货币，提供专注于可扩展性的独特价值主张。最初推出之后，如预期，一个健康的分散式采矿社区出现并在数字货币生态系统中变得活跃。然而，在9个月后，在短时间内单个池（此处称为Pool-X，某池）成功地将采矿集中。当时，人们认为Pool-X正在使用技术漏洞，但是这一点经过详尽的分析和开发人员和第三方的审查后，排除了可能性。现在可以理解了为什么以及如何发生的这种集中化，以及如何解决这个问题。
这是一个经济问题，而不是技术问题。由于PascalCoin是GPU友好的PoW数字货币，它已成为一个主要的
“双挖”的候选人，特别是以以太坊为中心的Pool-X。双挖是在使用相同的电力下，同时使用不同挖矿软件挖掘两个不同的数字货币。这是有效的，因为一些数字货币是考验内存（以太坊）而其他不是（PascalCoin，考验计算）。在挖掘需求内存的数字货币时，GPU具有丰富的空闲的计算能力，这可以重新用于同时挖掘像PascalCoin这样的非需求内存的数字货币。技术创新的同时，双挖的引入从根本上改变了挖掘“次要硬币”中的经济学和激励模式。
通常，挖矿生态系统随着利率有机生长，并且不会发生集中化。这是因为“哈希算力跟随价格”的法则。由于利息导致价格有机增长，矿工数量也随之增加。如果有太多的矿工，硬币变得无利可图，一些矿工离开。这种采矿与价格之间的稳态和生态系统规模是使加密货币运作的经济公式的一部分。
通过双重挖掘，这已被打破。双重采矿导致用户群较小的硬币，即使在“无利可图”的情况下，也有完全不成比例的矿工人数。在PascalCoin的情况下，矿工主要是在Pool-X开采以太坊，而不是PascalCoin。所以PascalCoin矿工的数量是以太坊生态系统的反映，而不是PascalCoin。此外，这些矿工开采PascalCoin，因为他们具有潜在的计算能力，所以从技术上讲，他们没有任何成本来开采PascalCoin。因此，即使在无利可图的情况下，他们也会开采PascalCoin，赶出了那些不是双重采矿的普通矿工。
这些不一致的经济激励导致快速趋同到99％的集中化，即使行为不带有恶意。

结构

提出了一种称为“随机哈希”（RandomHash）的低内存需求，抗GPU和ASIC算法来解决和防止双挖的集权。这里首先定义的RandomHash是一种复合的高级加密哈希算法，它以高度串联的方式组合了其他著名的基本算法。显著特征是a的计算
随机数依赖于随机选择的其他随机数的部分计算。这允许串行哈希计算（CPU）在后续挖矿过程中重复使用这些部分计算，节省50％或更多的工作负荷。因为无法预先计算最佳随机数，并联哈希计算（GPU）不能从这种优化中受益，它在运行中是固定的。
因此，需要并行哈希（GPU）来为每个随机数执行完整工作负载。而且，对于并联实现，算法会导致10倍内存膨胀。除了它的串联，它还是严重分叉和递归的，最适合仅CPU的挖矿。

概述

1. 散列计算一个随机数需要N次迭代（称为轮次）
2. 每轮从一组18个著名哈希算法中选择一个随机哈希函数
3. 第x轮的输入受到所有前几轮输出的影响
4. 第x轮的输入用随机确定的不同随机数的所有先前轮次的输出加盐
5. 第x轮的输入是对先验/相邻轮输出的传递闭包的压缩，大小为100字节
6. 每轮的输出都扩展了内存难度
7. 使用Mersenne Twister算法生成随机性
8. 随机性通过本轮的MurMur3校验和播种
9. 然后通过SHA2_256再次散列最后一轮，与传统的加密货币方法保持一致

图略

RandomHash 伪代码

const
 HASH_ALGO = [
 SHA2_256
 SHA2_384
 SHA2_512
 SHA3_256,
 SHA3_384,
 SHA3_512,
 RIPEMD160,
 RIPEMD256,
 RIPEMD320,
 Blake2b,
 Blake2s,
 Tiger2_5_192,
 Snefru_8_256,
 Grindahl512,
 Haval_5_256,
 MD5
 RadioGatun32
 Whirlpool
]
N = 5 // 哈希计算轮数N, 总计2^N
M = 10KB // 内存拓展单元, 总字节 = M * (2^N (N-2) + 2)
Function RandomHash (blockHeader : ByteArray) : ByteArray
begin
 let allOutputs = RandomHash( blockHeader, N)
 Result := SHA2_256( Compress( allOutputs ) )
end
Function RandomHash(blockHeader : ByteArray, Round : Integer): List of ByteArray
begin
 if Round < 1 or Round > N then
 Error 'Round must be between 1 and N inclusive'
 let roundOutputs = new List of ByteArray

 if Round = 1 then
 let seed = Checksum(blockHeader)
 let gen = RandomNumberGenerator(seed)
 let roundInput = blockHeader
 else
 let parentOutputs = RandomHash(blockHeader, Round - 1)
 let seed = Checksum(parentOutputs)
 let gen = RandomNumberGenerator(seed)
 roundOutputs.AddMany(parentOutputs)

 let otherNonceHeader = ChangeNonce(blockHeader, gen.NextDWord)
 let neighborOutputs = RandomHash(otherNonceHeader, Round - 1)
 roundOutputs.AddMany(neighborOutputs)

 let roundInput = Compress(roundOutputs)

 let hashFunc = HASH_ALGO[gen.NextDWord % 18]
 let output = hashFunc(roundInput)
 output = Expand( output, N - Round )
 roundOutputs.Add(output) 
 Result := roundOutputs
end
function Expand(input : ByteArray, ExpansionFactor : Integer) : ByteArray
begin
 let seed = Checksum(input)
 let gen = RandomNumberGenerator(seed)
 let size = Length(input) + ExpansionFactor*M
 let output = input.Clone
 let bytesToAdd = size - Length(input)
 while bytesToAdd > 0 do
 let nextChunk = output.Clone
 if Length(nextChunk) > bytesToAdd then
 SetLength(nextChunk, bytesToAdd)
 let random = gen.NextDWord
 case random % 8 do
 0: output = output ++ MemTransform1(nextChunk)
 1: output = output ++ MemTransform2(nextChunk)
 .
 .
 .
 7: output = output ++ MemTransform8(nextChunk)
 bytesToAdd = bytesToAdd - Length(nextChunk)
 Result = output
end
function Compress(inputs : list of ByteArray) : ByteArray
begin
 let seed = Checksum(inputs)
 let gen = RandomNumberGenerator(seed)
 let output = Byte[0..99]
 for i = 0 to 99 do
 let source = inputs[ gen.NextDWord % Length(inputs) ]
 output[i] = source[ gen.NextDWord % Length(source) ]
 Result := output
end
function ChangeNonce(blockHeader : ByteArray, nonce : Integer) : ByteArray
begin
 // 克隆并改变区块头中的随机数 (通过计算随机数偏移值)
end
Function Checksum(input : ByteArray) : DWord
begin
 // 标准的MurMu3算法计算
end

Function Checksum(inputs : List of ByteArray) : DWord
begin
 // 对输入的列表进行标准的MurMu3算法计算
end
Function RandomNumberGenerator(seed : DWord) : TMersenneTwister
 // 标准的 Mersenne Twister随机数生成器
end

内存转换方式

这些方法被迭代地随机应用于散列输出，以便快速扩展它以进行压缩下一轮。 注意：输出的长度始终与输入的长度相同。

- 内存转换方式1: XorShift32 (e.g. input = 1234567 output = select random from input using XorShift32 RNG
- 内存转换方式2: Swap-LR 左右交换 (e.g. input = 1234567 output = 5674123)
- 内存转换方式3: Reverse 反转 (e.g. input = 1234567 output = 7654321)
- 内存转换方式4: L-Interleave 左交错 (e.g. input = 1234567 output = 1526354)
- 内存转换方式5: R-Interleave 右交错(e.g. input = 1234567 output = 5162734)
- 内存转换方式6: L-XOR 左亦或(e.g. input = 1234567 output = XOR(1,2), XOR(3,4), XOR(5,6), 7, XOR(1,7), XOR(2,6), XOR(3,5)
- 内存转换方式7: ROL-ladder ROL-阶梯(e.g. input = ABCDEF output = ROL(A, LENGTH - 0), ROL(B, LENGTH - 1), ... , ROL(F, LENGTH - 5)
- 内存转换方式8: ROR-ladder ROR-阶梯(e.g. input = ABCDEF output = ROR(A, LENGTH - 0), ROR(B, LENGTH - 1), ... , ROR(F, LENGTH - 5) 

做不到言简意赅取中文名，就放点常识
XorShift32 一个随机数算法
ROL(C, L): 循环左移指令,将字节内容连同进位C 一起依次向左移L位
ROR(C, L): 循环右移指令,将字节内容连同进位C 一起依次向右移L位

正式定义如下:

内存转换方式1

内存转换方式2

内存转换方式3

内存转换方式4

内存转换方式5

内存转换方式6

内存转换方式7

内存转换方式8

RandomHash分析

CPU偏好

由于其高度串联的本质，RandomHash算法是必定对CPU挖矿存在偏好。而且，RandomHash允许CPU矿工缓存其他随机数的部分计算过程并且在后续步骤中会使用到它们。这使得CPU矿工在挖矿过程中能够节省大约50%的工作量。这个特性在下面已经证明，但是也可以简单的描述：为了计算一个随机数需要N轮，另一个随机数需要N-1才能完成计算。此随机数就只需要多1轮的计算即可完成，这就节省了50%的工作量。这个经过优化的随机数集无法被提前计算而且仅能被枚举计算。因此，串联挖矿过程（CPU挖矿）的工作量仅为并联挖矿（GPU挖矿）的50%。

内存复杂度

为了支持低端设备的挖矿，RandomHash对内存要求较低。一个CPU将只需要5MB的内存来验证一个哈希值。在挖矿期间，每个线程需要10MB（利用了上面提及的50%偏好情况下）---- 一个非常松的要求。值得注意的是，RandomHash消耗的大部分内存是在初始轮，在结束轮仅极少部分。这是为阻碍GPU挖矿刻意设计的。例如，假设一个GPU有5GB内存（译注：一般指显存），一个原生的哈希计算能够接受一批1000的随机数供并联计算（因为每个nonce要求5MB）。然而

GPU抵抗

ASIC抵抗

RandomHash变种

正式证明

计算复杂度

内存消耗

CPU偏好