EIP-: ```md

typedef struct {
    uint32_t z, w, jsr, jcong;
} kiss99_t;

// KISS99 简单、快速，并且通过了 TestU01 套件
// https://en.wikipedia.org/wiki/KISS_(algorithm)
// http://www.cse.yorku.ca/~oz/marsaglia-rng.html
uint32_t kiss99(kiss99_t &st)
{
    st.z = 36969 * (st.z & 65535) + (st.z >> 16);
    st.w = 18000 * (st.w & 65535) + (st.w >> 16);
    uint32_t MWC = ((st.z << 16) + st.w);
    st.jsr ^= (st.jsr << 17);
    st.jsr ^= (st.jsr >> 13);
    st.jsr ^= (st.jsr << 5);
    st.jcong = 69069 * st.jcong + 1234567;
    return ((MWC^st.jcong) + st.jsr);
}

void fill_mix(
    uint64_t seed,
    uint32_t lane_id,
    uint32_t mix[PROGPOW_REGS]
)
{
    // 使用 FNV 将每个 warp 的种子扩展到每个 lane
    // 使用 KISS 将每个 lane 的种子扩展到填充 mix
    uint32_t fnv_hash = FNV_OFFSET_BASIS;
    kiss99_t st;
    st.z = fnv1a(fnv_hash, seed);
    st.w = fnv1a(fnv_hash, seed >> 32);
    st.jsr = fnv1a(fnv_hash, lane_id);
    st.jcong = fnv1a(fnv_hash, lane_id);
    for (int i = 0; i < PROGPOW_REGS; i++)
        mix[i] = kiss99(st);
}

hash32_t keccak_f800_progpow(uint32_t* state)
{
    // keccak_f800 调用用于单次吸收
    for (int r = 0; r < 22; r++)
        keccak_f800_round(st, r);

    // 挤压阶段，用于固定 8 个字的输出
    hash32_t ret;
    for (int i=0; i<8; i++)
        ret.uint32s[i] = st[i];

    return ret;
}

kiss99_t progPowInit(uint64_t prog_seed, int mix_seq_dst[PROGPOW_REGS], int mix_seq_src[PROGPOW_REGS])
{
    kiss99_t prog_rnd;
    prog_rnd.z = fnv1a(FNV_OFFSET_BASIS, prog_seed);
    prog_rnd.w = fnv1a(prog_rnd.z, prog_seed >> 32);
    prog_rnd.jsr = fnv1a(prog_rnd.w, prog_seed);
    prog_rnd.jcong = fnv1a(prog_rnd.jsr, prog_seed >> 32);
    // 创建用于 merge() 的混合目标和用于缓存读取的混合源的随机序列
    // 保证每个目标都合并一次
    // 保证没有重复的缓存读取，可以优化掉
    // 使用 Fisher-Yates 洗牌
    for (int i = 0; i < PROGPOW_REGS; i++)
    {
        mix_seq_dst[i] = i;
        mix_seq_src[i] = i;
    }
    for (int i = PROGPOW_REGS - 1; i > 0; i--)
    {
        int j;
        j = kiss99(prog_rnd) % (i + 1);
        swap(mix_seq_dst[i], mix_seq_dst[j]);
        j = kiss99(prog_rnd) % (i + 1);
        swap(mix_seq_src[i], mix_seq_src[j]);
    }
    return prog_rnd;
}

// 将来自 b 的新数据合并到 a 中的值中
// 假设 A 具有高熵，则仅执行保留熵的运算
// 即使 B 是低熵
// (例如，不要执行 A&B)
uint32_t merge(uint32_t a, uint32_t b, uint32_t r)
{
    switch (r % 4)
    {
    case 0: return (a * 33) + b;
    case 1: return (a ^ b) * 33;
    // 防止旋转 0，这是一个 NOP
    case 2: return ROTL32(a, ((r >> 16) % 31) + 1) ^ b;
    case 3: return ROTR32(a, ((r >> 16) % 31) + 1) ^ b;
    }
}

// 两个输入值之间的随机数学运算
uint32_t math(uint32_t a, uint32_t b, uint32_t r)
{
    switch (r % 11)
    {
    case 0: return a + b;
    case 1: return a * b;
    case 2: return mul_hi(a, b);
    case 3: return min(a, b);
    case 4: return ROTL32(a, b);
    case 5: return ROTR32(a, b);
    case 6: return a & b;
    case 7: return a | b;
    case 8: return a ^ b;
    case 9: return clz(a) + clz(b);
    case 10: return popcount(a) + popcount(b);
    }
}

void progPowLoop(
    const uint64_t prog_seed,
    const uint32_t loop,
    uint32_t mix[PROGPOW_LANES][PROGPOW_REGS],
    const uint32_t *dag)
{
    // dag_entry 保存从 DAG 加载的 256 字节数据
    uint32_t dag_entry[PROGPOW_LANES][PROGPOW_DAG_LOADS];
    // 在每次循环迭代时，旋转哪个通道是 DAG 地址的来源。
    // 来源通道的 mix[0] 值用于确保最后一个循环的 DAG 数据馈送到此循环的地址中。
    // dag_addr_base 是将要访问的 DAG 内的哪个 256 字节条目
    uint32_t dag_addr_base = mix[loop%PROGPOW_LANES][0] %
        (DAG_BYTES / (PROGPOW_LANES*PROGPOW_DAG_LOADS*sizeof(uint32_t)));
    for (int l = 0; l < PROGPOW_LANES; l++)
    {
        // 通道从 dag 条目访问 DAG_LOADS 顺序字
        // 通过 XORing 通道和循环，每个迭代都会混洗各通道访问的条目部分。
        // 这可以防止多芯片 ASIC 仅存储 DAG 的一部分
        size_t dag_addr_lane = dag_addr_base * PROGPOW_LANES + (l ^ loop) % PROGPOW_LANES;
        for (int i = 0; i < PROGPOW_DAG_LOADS; i++)
            dag_entry[l][i] = dag[dag_addr_lane * PROGPOW_DAG_LOADS + i];
    }

    // 初始化程序种子和序列
    // 在挖掘时，这些会在 CPU 上评估并编译掉
    int mix_seq_dst[PROGPOW_REGS];
    int mix_seq_src[PROGPOW_REGS];
    int mix_seq_dst_cnt = 0;
    int mix_seq_src_cnt = 0;
    kiss99_t prog_rnd = progPowInit(prog_seed, mix_seq_dst, mix_seq_src);

    int max_i = max(PROGPOW_CNT_CACHE, PROGPOW_CNT_MATH);
    for (int i = 0; i < max_i; i++)
    {
        if (i < PROGPOW_CNT_CACHE)
        {
            // 缓存的内存访问
            // 通道访问 DAG 第一部分内的随机 32 位位置
            int src = mix_seq_src[(mix_seq_src_cnt++)%PROGPOW_REGS];
            int dst = mix_seq_dst[(mix_seq_dst_cnt++)%PROGPOW_REGS];
            int sel = kiss99(prog_rnd);
            for (int l = 0; l < PROGPOW_LANES; l++)
            {
                uint32_t offset = mix[l][src] % (PROGPOW_CACHE_BYTES/sizeof(uint32_t));
                mix[l][dst] = merge(mix[l][dst], dag[offset], sel);
            }
        }
        if (i < PROGPOW_CNT_MATH)
        {
            // 随机数学运算
            // 生成 2 个唯一的来源
            int src_rnd = kiss99(prog_rnd) % (PROGPOW_REGS * (PROGPOW_REGS-1));
            int src1 = src_rnd % PROGPOW_REGS; // 0 <= src1 < PROGPOW_REGS
            int src2 = src_rnd / PROGPOW_REGS; // 0 <= src2 < PROGPOW_REGS - 1
            if (src2 >= src1) ++src2; // src2 现在是除 src1 之外的任何寄存器
            int sel1 = kiss99(prog_rnd);
            int dst  = mix_seq_dst[(mix_seq_dst_cnt++)%PROGPOW_REGS];
            int sel2 = kiss99(prog_rnd);
            for (int l = 0; l < PROGPOW_LANES; l++)
            {
                uint32_t data = math(mix[l][src1], mix[l][src2], sel1);
                mix[l][dst] = merge(mix[l][dst], data, sel2);
            }
        }
    }
    // 在循环的最后消耗全局内存加载，以允许完全隐藏延迟
    // 始终合并到 mix[0] 中以馈送偏移计算
    for (int i = 0; i < PROGPOW_DAG_LOADS; i++)
    {
        int dst = (i==0) ? 0 : mix_seq_dst[(mix_seq_dst_cnt++)%PROGPOW_REGS];
        int sel = kiss99(prog_rnd);
        for (int l = 0; l < PROGPOW_LANES; l++)
            mix[l][dst] = merge(mix[l][dst], dag_entry[l][i], sel);
    }
}

hash32_t progPowHash(
    const uint64_t prog_seed,    // 值是 (block_number/PROGPOW_PERIOD)
    const uint64_t nonce,
    const hash32_t header,
    const uint32_t *dag          // 位于帧缓冲中的千兆字节 DAG - 第一部分被缓存
)
{
    hash32_t hash_init;
    hash32_t hash_final;

    uint32_t mix[PROGPOW_LANES][PROGPOW_REGS];

    /*  
        ========================================
        初始 keccak 传递的吸收阶段
        ========================================
    */

    {
        uint32_t state[25] = {0x0};
        // 1st 使用头部数据填充（8 个字）
        for (int i = 0; i < 8; i++)
            state[i] = header.uint32s[i];

        // 2nd 使用 nonce 填充（2 个字）
        state[8] = nonce;
        state[9] = nonce >> 32;

        // 3rd 应用填充
        state[10] = 0x00000001;
        state[18] = 0x80008081;

		// 启动 keccak(header..nonce)
        hash_init = keccak_f800_progpow(state);

        // 获取用于初始化 mix 的种子
        seed = ((uint64_t)hash_init.uint32s[1] << 32) | hash_init.uint32s[0]);
	}

    // 为所有通道初始化 mix
    for (int l = 0; l < PROGPOW_LANES; l++)
        fill_mix(seed, l, mix[l]);

    // 执行随机生成的内部循环
    for (int i = 0; i < PROGPOW_CNT_DAG; i++)
        progPowLoop(prog_seed, i, mix, dag);

    // 将混合数据减少为每个通道的 32 位摘要
    uint32_t digest_lane[PROGPOW_LANES];
    for (int l = 0; l < PRO我们不建议目前实施此修复。Ethash 在未来数年内不会被利用，并且 ProgPoW 是否会被利用尚不清楚。最好部署经过审计的代码。

在完成审计后，[Kik](https://github.com/kik/) 的一项巧妙发现披露了一个 [绕过 ProgPoW 内存硬度的漏洞](https://github.com/kik/progpow-exploit)。该漏洞也存在于 Ethash 中，但几乎不可能被利用。在 progPoW 中，利用是不可能的——它假设能够以类似于比特币的方式创建候选区块头哈希的变体，而这在以太坊中实际上是不可能的。攻击者需要修改过的区块头，需要能够接受修改过的区块头的定制节点，并将 extraNonce/extraData 用作熵——这不是标准做法。而且，所需的暴力搜索很难在一个区块时间内完成。即使定制节点支持，此类挖出的区块的传播也会立即被其他节点阻止，因为头部哈希无效。

作者们后来发现了另一个类似于 Kik 的漏洞，但它增加了太多的开销，不适合 ASIC。请参阅 Lanfranchi 的完整解释[此处](https://github.com/ifdefelse/ProgPOW/issues/51#issuecomment-690155355)。为了完全防止此类漏洞，我们可以更改修改最后一个 keccak 过程的输入状态的条件，从
* header (256 bits) +
* mix initiator 的 seed (64 bits) +
* 主循环中的 mix (256 bits)
* 无填充

改为

* 初始 keccak 的摘要 (256 bits) +
* 主循环中的 mix (256 bits) +
* 填充

从而将 keccak 中 [暴力破解 keccak 线性搜索](https://github.com/kik/progpow-exploit) 的目标约束从 64 位扩大到 256 位。

此修复程序作为 PR 提供给参考实现。同样，我们不建议目前实施此修复。Kik 的漏洞和类似漏洞现在无法利用，而且可能永远不会被利用。最好部署经过审计的代码。

请注意，这些漏洞不能被利用来拒绝服务、双重支付或以其他方式损害网络。它们最多只能让其部署者比其他矿工获得效率优势。

## 测试用例

块 30,000（prog_seed 3,000）生成的随机序列可以在 [kernel.cu](https://github.com/ifdefelse/ProgPOW/blob/824cd791634204c4cc7e31f84bb76c0c84895bd3/test/kernel.cu) 中看到。

在块 30,000 上运行的算法产生以下摘要和结果：