精华内容
下载资源
问答
  • 以太坊的Ethash算法

    万次阅读 2017-09-06 16:22:08
    Ethash 是 Ethereum 1.0 计划PoW算法。这是最新版本Dagger-Hashimoto, 虽然它不能再恰当地被称为Dagger-Hashimoto, 因为这两种算法的许多原始特性已经在上个月研究和开发中发生了翻天覆地变化。请参见 ...


    Ethash

    认真的阅读,理解,计算和调试了一番,顺便自己翻译了一下, 共同学习. 微笑
    此规范是修订版23。

    Ethash 是 Ethereum 1.0 的计划的PoW算法。这是最新版本的Dagger-Hashimoto, 虽然它不能再恰当地被称为Dagger-Hashimoto, 
    因为这两种算法的许多原始特性已经在上个月的研究和开发中发生了翻天覆地的变化。
    请参见 https://github.com/ethereum/wiki/blob/master/Dagger-Hashimoto.md 的原始版本。

    该算法所采用的一般流程如下所示:

    1. 存在一个种子, 可以通过块高度直到该点来计算每个块。
    2. 从种子, 你可以计算一个 16 MB 的伪随机缓存, 用于轻客户端存储缓存。
    2. 从缓存中, 我们可以生成一个 1 GB 的数据集, 该属性表示数据集中的每个项只依赖于缓存中的少量项。完整的客户和矿工存储这个数据集。数据集会随时间线性增长。
    挖矿涉及抓取数据集的随机切片并将它们一起哈希。可以通过使用缓存来重新生成所需的数据集的特定部分, 从而低内存的机器可以进行验证, 因为只需存储缓存即可验证。
    完整的大数据集每隔30000块更新一次, 因此大多数矿工的工作将是读取数据集, 而不是对其进行更改。


    有关此算法的设计基本原理注意事项, 请参见 https://github.com/ethereum/wiki/wiki/Ethash-Design-Rationale。




    算法使用python来字义和描述, 几个重要的库函数要查清文档,别望文生义, 如:
    1.map是遍历数组的作为参数去调用函数,得到一个新的数组.
    2. **这个指数运算符等, 
    3. //是整除
    4. [::-1]是将元组或列表的内容翻转
    5. RLP是一个编码算法,请另外查阅和理解
    ...


    ***全局常量定义


    我们使用以下定义:


    WORD_BYTES = 4                    # 一个字的字节数
    DATASET_BYTES_INIT = 2**30        # 创世块的字节数
    DATASET_BYTES_GROWTH = 2**23      # 每个纪元(30000块一次)的数据集增长字节数
    CACHE_BYTES_INIT = 2**24          # 创世块的缓冲字节数
    CACHE_BYTES_GROWTH = 2**17        # 每个纪元(30000块一次)的缓冲增长字节数
    CACHE_MULTIPLIER=1024             # 相对于DAG缓存的大小
    EPOCH_LENGTH = 30000              # 每个纪元的块数
    MIX_BYTES = 128                   # 混合体的字节数
    HASH_BYTES = 64                   # 哈希的字节数
    DATASET_PARENTS = 256             # 每个数据集元素的父级数
    CACHE_ROUNDS = 3                  # 缓存生产中的回合数
    ACCESSES = 64                     # hashimoto循环的访问次数






    有关本规范中描述的 "SHA3" 哈希的说明


    Ethereum 的发展恰逢 SHA3 标准的发展, 标准过程在最终的哈希算法的填充上做了后期的更改, 因此 Ethereum 的 "sha3_256" 和 "sha3_512" 哈希不是标准的 sha3 哈希, 而是一个变体在其他语境中经常被称为 "Keccak-256" 和 "Keccak-512"。
    请记住,  这个算法仍然当做 "sha3" 哈希在下面的算法描述中被引用。




    ***参数


    Ethash 的缓存和数据集的参数取决于块号。
    高速缓存大小和数据集大小均呈线性增长。
    然而, 我们总是把最高的素数放在线性增长的阈值之下, 以减少偶然的规律性,从而导致循环行为的风险。
    isprime来定义这个是不是素数,请看附录。


    #根据给出的块号, 计算cache的大小, 如果大小除法HASH_BYTES不是符合定义的素数, 会一直减少这个直至这个大小是符合定义的素数
    def get_cache_size(block_number):
        sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
        sz -= HASH_BYTES
        while not isprime(sz / HASH_BYTES):
            sz -= 2 * HASH_BYTES
        return sz


    #根据给出的块号, 计算DAG的完整大小, 如果大小除以MIX_BYTES不是符合定义的素数, 会一直减少这个直至这个大小是符合定义的素数


    def get_full_size(block_number):
        sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
        sz -= MIX_BYTES
        while not isprime(sz / MIX_BYTES):
            sz -= 2 * MIX_BYTES
        return sz


    附录中提供了数据集和缓存大小值的表。


    ***缓存生成


    下面是现在我们指定用于生成缓存的函数:
    def mkcache(cache_size, seed):
        n = cache_size // HASH_BYTES


        # Sequentially produce the initial dataset
        o = [sha3_512(seed)]
        for i in range(1, n):
            o.append(sha3_512(o[-1]))


        # Use a low-round version of randmemohash
        for _ in range(CACHE_ROUNDS):
            for i in range(n):
                v = o[i][0] % n
                o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))


        return o


    缓存生产过程首先需要依次填充 32 MB 内存, 然后从严格的内存难度型哈希函数 (2014) 执行两次Sergio Demian Lerner的 RandMemoHash 算法。
    输出是一组 524288 个64 字节的值。


    ***数据聚合函数


    在某些情况下, 我们使用由 FNV hash算法作为 XOR 的关联替换。请注意, 我们将素数与完整的32位输入相乘, 与 FNV-1 规范相比, 它反过来将素数与一个字节 (八进制) 相乘。


    FNV_PRIME = 0x01000193


    def fnv(v1, v2):
        return ((v1 * FNV_PRIME) ^ v2) % 2**32




    请注意, 即使是黄皮书指定FNV 为 v1 * (FNV_PRIME ^ v2), 但所有当前的实现始终使用上述定义。


    ***完整数据集计算




    完整的 1 GB 数据集中的每个64字节项都按如下方式计算:


    def calc_dataset_item(cache, i):
        n = len(cache)
        r = HASH_BYTES // WORD_BYTES
        # initialize the mix
        mix = copy.copy(cache[i % n])
        mix[0] ^= i
        mix = sha3_512(mix)
        # fnv it with a lot of random cache nodes based on i
        for j in range(DATASET_PARENTS):
            cache_index = fnv(i ^ j, mix[j % r])
            mix = map(fnv, mix, cache[cache_index % n])
        return sha3_512(mix)
    实质上, 我们将来自 256个伪随机的选定缓存节点的数据和哈希值合并到一起以计算 数据集的 节点。然后生成整个数据集,算法如下:


    def calc_dataset(full_size, cache):
        return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]


    ***主循环
    现在, 我们说明类"hashimoto"的循环, 在这里我们从完整的数据集收集资料, 以便为特定的Header和nonce生成我们的最终值。
    在下面的代码中, header表示截取过的块头部(即不包括 mixHash字段 和nonce的头部)使用RLP 表示的 SHA3-256 哈希。
    nonce是一个64位无符号整数的八个字节。因此, [:-1] 是该值的八字节小字节表示:




    def hashimoto(header, nonce, full_size, dataset_lookup):
        n = full_size / HASH_BYTES
        w = MIX_BYTES // WORD_BYTES
        mixhashes = MIX_BYTES / HASH_BYTES
        # combine header+nonce into a 64 byte seed
        s = sha3_512(header + nonce[::-1])
        # start the mix with replicated s
        mix = []
        for _ in range(MIX_BYTES / HASH_BYTES):
            mix.extend(s)
        # mix in random dataset nodes
        for i in range(ACCESSES):
            p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes
            newdata = []
            for j in range(MIX_BYTES / HASH_BYTES):
                newdata.extend(dataset_lookup(p + j))
            mix = map(fnv, mix, newdata)
        # compress mix
        cmix = []
        for i in range(0, len(mix), 4):
            cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3]))
        return {
            "mix digest": serialize_hash(cmix),
            "result": serialize_hash(sha3_256(s+cmix))
        }


    def hashimoto_light(full_size, cache, header, nonce):
        return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))


    def hashimoto_full(full_size, dataset, header, nonce):
        return hashimoto(header, nonce, full_size, lambda x: dataset[x])


    本质上, 我们保持一个 "混合体" 128 字节宽, 并重复地从完整的数据集中获取128个字节, 并使用FNV函数将它与"混合体" 组合在一起。
    128字节顺序访问的方法, 可以使每一个回合的算法总是从 RAM 中提取一个完整的页面, 这样可以最小化TLB的命中失败次数, 这个主要是为防ASIC。
    如果该算法的输出小于目标值, 则nonce就是正确的解。


    解释一下TLB:  Translation Lookaside Buffer. 根据功能可以译为快表,直译可以翻译为旁路转换缓冲,也可以把它理解成页表缓冲。里面存放的是一些页表文件(虚拟地址到物理地址的转换表)。当处理器要在主内存寻址时,不是直接在内存的物理地址里查找的,而是通过一组虚拟地址转换到主内存的物理地址,TLB就是负责将虚拟内存地址翻译成实际的物理内存地址,而CPU寻址时会优先在TLB中进行寻址。处理器的性能就和寻址的命中率有很大的关系。


    ASIC在理论上是有能力做到避免TLB的命中失败次数的, 但这样做了ASIC就没有优势了, 因为这个命中失败率已经是很小的了, 改进这个无法显著提高处理速度。


    请注意, 最后的一次sha3_256 哈希用来来确保存在一个中间的nonce,它可以提供证明至少有少量的工作被完成。 这个快速的PoW验证可以用于反 DDoS 的目的。
    它也可以为结果是一个不偏不倚的256 位数,提供统计性的保证。




    *** 挖矿


    挖矿算法定义如下:


    def mine(full_size, dataset, header, difficulty):
        target = zpad(encode_int(2**256 // difficulty), 64)[::-1]
        from random import randint
        nonce = randint(0, 2**64)
        while hashimoto_full(full_size, dataset, header, nonce) > target:
            nonce = (nonce + 1) % 2**64
        return nonce


    *** 定义种子哈希


    为了计算将用于在给定块顶部挖矿的种子哈希值, 我们使用以下算法:


     def get_seedhash(block):
         s = '\x00' * 32
         for i in range(block.number // EPOCH_LENGTH):
             s = serialize_hash(sha3_256(s))
         return s


    请注意, 为了平滑地进行挖矿和验证, 我们建议在单独的线程中 预先生成和计算 下一个要使用到的种子哈希和数据集。




    *** 附录


    如果您有兴趣将上面的 python 规范作为代码运行, 则应预置以下代码。


    import sha3, copy


    # Assumes little endian bit ordering (same as Intel architectures)
    def decode_int(s):
        return int(s[::-1].encode('hex'), 16) if s else 0


    def encode_int(s):
        a = "%x" % s
        return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]


    def zpad(s, length):
        return s + '\x00' * max(0, length - len(s))


    def serialize_hash(h):
        return ''.join([zpad(encode_int(x), 4) for x in h])
      
    def deserialize_hash(h):
        return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]
      
    def hash_words(h, sz, x):
        if isinstance(x, list):
            x = serialize_hash(x)
        y = h(x)
        return deserialize_hash(y)


    def serialize_cache(ds):
        return ''.join([serialize_hash(h) for h in ds])
      
    serialize_dataset = serialize_cache


    # sha3 hash function, outputs 64 bytes
    def sha3_512(x):
        return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)


    def sha3_256(x):
        return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)


    def xor(a, b):
        return a ^ b


    def isprime(x):
        for i in range(2, int(x**0.5)):
             if x % i == 0:
                 return False
        return True




    *** 数据大小


    下面的查找表提供了大约2048个纪元的数据集大小和缓存大小的表格。它们是使用下面的 Mathematica 函数生成的:




    def get_datasize(block_number):
        return data_sizes[block_number // EPOCH_LENGTH]


    def get_cachesize(block_number):
        return cache_sizes[block_number // EPOCH_LENGTH]


    data_sizes = [
    1073739904, 1082130304, 1090514816, 1098906752, 1107293056, 
    1115684224, 1124070016, 1132461952, 1140849536, 1149232768, 
    1157627776, 1166013824, 1174404736, 1182786944, 1191180416, 
    1199568512, 1207958912, 1216345216, 1224732032, 1233124736, 
    1241513344, 1249902464, 1258290304, 1266673792, 1275067264, 
    1283453312, 1291844992, 1300234112, 1308619904, 1317010048, 
    1325397376, 1333787776, 1342176128, 1350561664, 1358954368, 
    1367339392, 1375731584, 1384118144, 1392507008, 1400897408, 
    1409284736, 1417673344, 1426062464, 1434451072, 1442839168, 
    1451229056, 1459615616, 1468006016, 1476394112, 1484782976, 
    1493171584, 1501559168, 1509948032, 1518337664, 1526726528, 
    1535114624, 1543503488, 1551892096, 1560278656, 1568669056, 
    1577056384, 1585446272, 1593831296, 1602219392, 1610610304, 
    1619000192, 1627386752, 1635773824, 1644164224, 1652555648, 
    1660943488, 1669332608, 1677721216, 1686109312, 1694497664, 
    1702886272, 1711274624, 1719661184, 1728047744, 1736434816, 
    1744829056, 1753218944, 1761606272, 1769995904, 1778382464, 
    1786772864, 1795157888, 1803550592, 1811937664, 1820327552, 
    1828711552, 1837102976, 1845488768, 1853879936, 1862269312, 
    1870656896, 1879048064, 1887431552, 1895825024, 1904212096, 
    1912601216, 1920988544, 1929379456, 1937765504, 1946156672, 
    1954543232, 1962932096, 1971321728, 1979707264, 1988093056, 
    1996487552, 2004874624, 2013262208, 2021653888, 2030039936, 
    2038430848, 2046819968, 2055208576, 2063596672, 2071981952, 
    2080373632, 2088762752, 2097149056, 2105539712, 2113928576, 
    2122315136, 2130700672, 2139092608, 2147483264, 2155872128, 
    2164257664, 2172642176, 2181035392, 2189426048, 2197814912, 
    2206203008, 2214587264, 2222979712, 2231367808, 2239758208, 
    2248145024, 2256527744, 2264922752, 2273312128, 2281701248, 
    2290086272, 2298476672, 2306867072, 2315251072, 2323639168, 
    2332032128, 2340420224, 2348808064, 2357196416, 2365580416, 
    2373966976, 2382363008, 2390748544, 2399139968, 2407530368, 
    2415918976, 2424307328, 2432695424, 2441084288, 2449472384, 
    2457861248, 2466247808, 2474637184, 2483026816, 2491414144, 
    2499803776, 2508191872, 2516582272, 2524970368, 2533359232, 
    2541743488, 2550134144, 2558525056, 2566913408, 2575301504, 
    2583686528, 2592073856, 2600467328, 2608856192, 2617240448, 
    2625631616, 2634022016, 2642407552, 2650796416, 2659188352, 
    2667574912, 2675965312, 2684352896, 2692738688, 2701130624, 
    2709518464, 2717907328, 2726293376, 2734685056, 2743073152, 
    2751462016, 2759851648, 2768232832, 2776625536, 2785017728, 
    2793401984, 2801794432, 2810182016, 2818571648, 2826959488, 
    2835349376, 2843734144, 2852121472, 2860514432, 2868900992, 
    2877286784, 2885676928, 2894069632, 2902451584, 2910843008, 
    2919234688, 2927622784, 2936011648, 2944400768, 2952789376, 
    2961177728, 2969565568, 2977951616, 2986338944, 2994731392, 
    3003120256, 3011508352, 3019895936, 3028287104, 3036675968, 
    3045063808, 3053452928, 3061837696, 3070228352, 3078615424, 
    3087003776, 3095394944, 3103782272, 3112173184, 3120562048, 
    3128944768, 3137339264, 3145725056, 3154109312, 3162505088, 
    3170893184, 3179280256, 3187669376, 3196056704, 3204445568, 
    3212836736, 3221224064, 3229612928, 3238002304, 3246391168, 
    3254778496, 3263165824, 3271556224, 3279944576, 3288332416, 
    3296719232, 3305110912, 3313500032, 3321887104, 3330273152, 
    3338658944, 3347053184, 3355440512, 3363827072, 3372220288, 
    3380608384, 3388997504, 3397384576, 3405774208, 3414163072, 
    3422551936, 3430937984, 3439328384, 3447714176, 3456104576, 
    3464493952, 3472883584, 3481268864, 3489655168, 3498048896, 
    3506434432, 3514826368, 3523213952, 3531603584, 3539987072, 
    3548380288, 3556763264, 3565157248, 3573545344, 3581934464, 
    3590324096, 3598712704, 3607098752, 3615488384, 3623877248, 
    3632265856, 3640646528, 3649043584, 3657430144, 3665821568, 
    3674207872, 3682597504, 3690984832, 3699367808, 3707764352, 
    3716152448, 3724541056, 3732925568, 3741318016, 3749706368, 
    3758091136, 3766481536, 3774872704, 3783260032, 3791650432, 
    3800036224, 3808427648, 3816815488, 3825204608, 3833592704, 
    3841981568, 3850370432, 3858755968, 3867147904, 3875536256, 
    3883920512, 3892313728, 3900702592, 3909087872, 3917478784, 
    3925868416, 3934256512, 3942645376, 3951032192, 3959422336, 
    3967809152, 3976200064, 3984588416, 3992974976, 4001363584, 
    4009751168, 4018141312, 4026530432, 4034911616, 4043308928, 
    4051695488, 4060084352, 4068472448, 4076862848, 4085249408, 
    4093640576, 4102028416, 4110413696, 4118805632, 4127194496, 
    4135583104, 4143971968, 4152360832, 4160746112, 4169135744, 
    4177525888, 4185912704, 4194303616, 4202691968, 4211076736, 
    4219463552, 4227855488, 4236246656, 4244633728, 4253022848, 
    4261412224, 4269799808, 4278184832, 4286578048, 4294962304, 
    4303349632, 4311743104, 4320130432, 4328521088, 4336909184, 
    4345295488, 4353687424, 4362073472, 4370458496, 4378852736, 
    4387238528, 4395630208, 4404019072, 4412407424, 4420790656, 
    4429182848, 4437571456, 4445962112, 4454344064, 4462738048, 
    4471119232, 4479516544, 4487904128, 4496289664, 4504682368, 
    4513068416, 4521459584, 4529846144, 4538232704, 4546619776, 
    4555010176, 4563402112, 4571790208, 4580174464, 4588567936, 
    4596957056, 4605344896, 4613734016, 4622119808, 4630511488, 
    4638898816, 4647287936, 4655675264, 4664065664, 4672451968, 
    4680842624, 4689231488, 4697620352, 4706007424, 4714397056, 
    4722786176, 4731173248, 4739562368, 4747951744, 4756340608, 
    4764727936, 4773114496, 4781504384, 4789894784, 4798283648, 
    4806667648, 4815059584, 4823449472, 4831835776, 4840226176, 
    4848612224, 4857003392, 4865391488, 4873780096, 4882169728, 
    4890557312, 4898946944, 4907333248, 4915722368, 4924110976, 
    4932499328, 4940889728, 4949276032, 4957666432, 4966054784, 
    4974438016, 4982831488, 4991221376, 4999607168, 5007998848, 
    5016386432, 5024763776, 5033164672, 5041544576, 5049941888, 
    5058329728, 5066717056, 5075107456, 5083494272, 5091883904, 
    5100273536, 5108662144, 5117048192, 5125436032, 5133827456, 
    5142215296, 5150605184, 5158993024, 5167382144, 5175769472, 
    5184157568, 5192543872, 5200936064, 5209324928, 5217711232, 
    5226102656, 5234490496, 5242877312, 5251263872, 5259654016, 
    5268040832, 5276434304, 5284819328, 5293209728, 5301598592, 
    5309986688, 5318374784, 5326764416, 5335151488, 5343542144, 
    5351929472, 5360319872, 5368706944, 5377096576, 5385484928, 
    5393871232, 5402263424, 5410650496, 5419040384, 5427426944, 
    5435816576, 5444205952, 5452594816, 5460981376, 5469367936, 
    5477760896, 5486148736, 5494536832, 5502925952, 5511315328, 
    5519703424, 5528089984, 5536481152, 5544869504, 5553256064, 
    5561645696, 5570032768, 5578423936, 5586811264, 5595193216, 
    5603585408, 5611972736, 5620366208, 5628750464, 5637143936, 
    5645528192, 5653921408, 5662310272, 5670694784, 5679082624, 
    5687474048, 5695864448, 5704251008, 5712641408, 5721030272, 
    5729416832, 5737806208, 5746194304, 5754583936, 5762969984, 
    5771358592, 5779748224, 5788137856, 5796527488, 5804911232, 
    5813300608, 5821692544, 5830082176, 5838468992, 5846855552, 
    5855247488, 5863636096, 5872024448, 5880411008, 5888799872, 
    5897186432, 5905576832, 5913966976, 5922352768, 5930744704, 
    5939132288, 5947522432, 5955911296, 5964299392, 5972688256, 
    5981074304, 5989465472, 5997851008, 6006241408, 6014627968, 
    6023015552, 6031408256, 6039796096, 6048185216, 6056574848, 
    6064963456, 6073351808, 6081736064, 6090128768, 6098517632, 
    6106906496, 6115289216, 6123680896, 6132070016, 6140459648, 
    6148849024, 6157237376, 6165624704, 6174009728, 6182403712, 
    6190792064, 6199176064, 6207569792, 6215952256, 6224345216, 
    6232732544, 6241124224, 6249510272, 6257899136, 6266287744, 
    6274676864, 6283065728, 6291454336, 6299843456, 6308232064, 
    6316620928, 6325006208, 6333395584, 6341784704, 6350174848, 
    6358562176, 6366951296, 6375337856, 6383729536, 6392119168, 
    6400504192, 6408895616, 6417283456, 6425673344, 6434059136, 
    6442444672, 6450837376, 6459223424, 6467613056, 6476004224, 
    6484393088, 6492781952, 6501170048, 6509555072, 6517947008, 
    6526336384, 6534725504, 6543112832, 6551500672, 6559888768, 
    6568278656, 6576662912, 6585055616, 6593443456, 6601834112, 
    6610219648, 6618610304, 6626999168, 6635385472, 6643777408, 
    6652164224, 6660552832, 6668941952, 6677330048, 6685719424, 
    6694107776, 6702493568, 6710882176, 6719274112, 6727662976, 
    6736052096, 6744437632, 6752825984, 6761213824, 6769604224, 
    6777993856, 6786383488, 6794770816, 6803158144, 6811549312, 
    6819937664, 6828326528, 6836706176, 6845101696, 6853491328, 
    6861880448, 6870269312, 6878655104, 6887046272, 6895433344, 
    6903822208, 6912212864, 6920596864, 6928988288, 6937377152, 
    6945764992, 6954149248, 6962544256, 6970928768, 6979317376, 
    6987709312, 6996093824, 7004487296, 7012875392, 7021258624, 
    7029652352, 7038038912, 7046427776, 7054818944, 7063207808, 
    7071595136, 7079980928, 7088372608, 7096759424, 7105149824, 
    7113536896, 7121928064, 7130315392, 7138699648, 7147092352, 
    7155479168, 7163865728, 7172249984, 7180648064, 7189036672, 
    7197424768, 7205810816, 7214196608, 7222589824, 7230975104, 
    7239367552, 7247755904, 7256145536, 7264533376, 7272921472, 
    7281308032, 7289694848, 7298088832, 7306471808, 7314864512, 
    7323253888, 7331643008, 7340029568, 7348419712, 7356808832, 
    7365196672, 7373585792, 7381973888, 7390362752, 7398750592, 
    7407138944, 7415528576, 7423915648, 7432302208, 7440690304, 
    7449080192, 7457472128, 7465860992, 7474249088, 7482635648, 
    7491023744, 7499412608, 7507803008, 7516192384, 7524579968, 
    7532967296, 7541358464, 7549745792, 7558134656, 7566524032, 
    7574912896, 7583300992, 7591690112, 7600075136, 7608466816, 
    7616854912, 7625244544, 7633629824, 7642020992, 7650410368, 
    7658794112, 7667187328, 7675574912, 7683961984, 7692349568, 
    7700739712, 7709130368, 7717519232, 7725905536, 7734295424, 
    7742683264, 7751069056, 7759457408, 7767849088, 7776238208, 
    7784626816, 7793014912, 7801405312, 7809792128, 7818179968, 
    7826571136, 7834957184, 7843347328, 7851732352, 7860124544, 
    7868512384, 7876902016, 7885287808, 7893679744, 7902067072, 
    7910455936, 7918844288, 7927230848, 7935622784, 7944009344, 
    7952400256, 7960786048, 7969176704, 7977565312, 7985953408, 
    7994339968, 8002730368, 8011119488, 8019508096, 8027896192, 
    8036285056, 8044674688, 8053062272, 8061448832, 8069838464, 
    8078227328, 8086616704, 8095006592, 8103393664, 8111783552, 
    8120171392, 8128560256, 8136949376, 8145336704, 8153726848, 
    8162114944, 8170503296, 8178891904, 8187280768, 8195669632, 
    8204058496, 8212444544, 8220834176, 8229222272, 8237612672, 
    8246000768, 8254389376, 8262775168, 8271167104, 8279553664, 
    8287944064, 8296333184, 8304715136, 8313108352, 8321497984, 
    8329885568, 8338274432, 8346663296, 8355052928, 8363441536, 
    8371828352, 8380217984, 8388606592, 8396996224, 8405384576, 
    8413772672, 8422161536, 8430549376, 8438939008, 8447326592, 
    8455715456, 8464104832, 8472492928, 8480882048, 8489270656, 
    8497659776, 8506045312, 8514434944, 8522823808, 8531208832, 
    8539602304, 8547990656, 8556378752, 8564768384, 8573154176, 
    8581542784, 8589933952, 8598322816, 8606705024, 8615099264, 
    8623487872, 8631876992, 8640264064, 8648653952, 8657040256, 
    8665430656, 8673820544, 8682209152, 8690592128, 8698977152, 
    8707374464, 8715763328, 8724151424, 8732540032, 8740928384, 
    8749315712, 8757704576, 8766089344, 8774480768, 8782871936, 
    8791260032, 8799645824, 8808034432, 8816426368, 8824812928, 
    8833199488, 8841591424, 8849976448, 8858366336, 8866757248, 
    8875147136, 8883532928, 8891923328, 8900306816, 8908700288, 
    8917088384, 8925478784, 8933867392, 8942250368, 8950644608, 
    8959032704, 8967420544, 8975809664, 8984197504, 8992584064, 
    9000976256, 9009362048, 9017752448, 9026141312, 9034530688, 
    9042917504, 9051307904, 9059694208, 9068084864, 9076471424, 
    9084861824, 9093250688, 9101638528, 9110027648, 9118416512, 
    9126803584, 9135188096, 9143581312, 9151969664, 9160356224, 
    9168747136, 9177134464, 9185525632, 9193910144, 9202302848, 
    9210690688, 9219079552, 9227465344, 9235854464, 9244244864, 
    9252633472, 9261021824, 9269411456, 9277799296, 9286188928, 
    9294574208, 9302965888, 9311351936, 9319740032, 9328131968, 
    9336516736, 9344907392, 9353296768, 9361685888, 9370074752, 
    9378463616, 9386849408, 9395239808, 9403629184, 9412016512, 
    9420405376, 9428795008, 9437181568, 9445570688, 9453960832, 
    9462346624, 9470738048, 9479121536, 9487515008, 9495903616, 
    9504289664, 9512678528, 9521067904, 9529456256, 9537843584, 
    9546233728, 9554621312, 9563011456, 9571398784, 9579788672, 
    9588178304, 9596567168, 9604954496, 9613343104, 9621732992, 
    9630121856, 9638508416, 9646898816, 9655283584, 9663675776, 
    9672061312, 9680449664, 9688840064, 9697230464, 9705617536, 
    9714003584, 9722393984, 9730772608, 9739172224, 9747561088, 
    9755945344, 9764338816, 9772726144, 9781116544, 9789503872, 
    9797892992, 9806282624, 9814670464, 9823056512, 9831439232, 
    9839833984, 9848224384, 9856613504, 9865000576, 9873391232, 
    9881772416, 9890162816, 9898556288, 9906940544, 9915333248, 
    9923721088, 9932108672, 9940496512, 9948888448, 9957276544, 
    9965666176, 9974048384, 9982441088, 9990830464, 9999219584, 
    10007602816, 10015996544, 10024385152, 10032774016, 10041163648, 
    10049548928, 10057940096, 10066329472, 10074717824, 10083105152, 
    10091495296, 10099878784, 10108272256, 10116660608, 10125049216, 
    10133437312, 10141825664, 10150213504, 10158601088, 10166991232, 
    10175378816, 10183766144, 10192157312, 10200545408, 10208935552, 
    10217322112, 10225712768, 10234099328, 10242489472, 10250876032, 
    10259264896, 10267656064, 10276042624, 10284429184, 10292820352, 
    10301209472, 10309598848, 10317987712, 10326375296, 10334763392, 
    10343153536, 10351541632, 10359930752, 10368318592, 10376707456, 
    10385096576, 10393484672, 10401867136, 10410262144, 10418647424, 
    10427039104, 10435425664, 10443810176, 10452203648, 10460589952, 
    10468982144, 10477369472, 10485759104, 10494147712, 10502533504, 
    10510923392, 10519313536, 10527702656, 10536091264, 10544478592, 
    10552867712, 10561255808, 10569642368, 10578032768, 10586423168, 
    10594805632, 10603200128, 10611588992, 10619976064, 10628361344, 
    10636754048, 10645143424, 10653531776, 10661920384, 10670307968, 
    10678696832, 10687086464, 10695475072, 10703863168, 10712246144, 
    10720639616, 10729026688, 10737414784, 10745806208, 10754190976, 
    10762581376, 10770971264, 10779356288, 10787747456, 10796135552, 
    10804525184, 10812915584, 10821301888, 10829692288, 10838078336, 
    10846469248, 10854858368, 10863247232, 10871631488, 10880023424, 
    10888412032, 10896799616, 10905188992, 10913574016, 10921964672, 
    10930352768, 10938742912, 10947132544, 10955518592, 10963909504, 
    10972298368, 10980687488, 10989074816, 10997462912, 11005851776, 
    11014241152, 11022627712, 11031017344, 11039403904, 11047793024, 
    11056184704, 11064570752, 11072960896, 11081343872, 11089737856, 
    11098128256, 11106514816, 11114904448, 11123293568, 11131680128, 
    11140065152, 11148458368, 11156845696, 11165236864, 11173624192, 
    11182013824, 11190402688, 11198790784, 11207179136, 11215568768, 
    11223957376, 11232345728, 11240734592, 11249122688, 11257511296, 
    11265899648, 11274285952, 11282675584, 11291065472, 11299452544, 
    11307842432, 11316231296, 11324616832, 11333009024, 11341395584, 
    11349782656, 11358172288, 11366560384, 11374950016, 11383339648, 
    11391721856, 11400117376, 11408504192, 11416893568, 11425283456, 
    11433671552, 11442061184, 11450444672, 11458837888, 11467226752, 
    11475611776, 11484003968, 11492392064, 11500780672, 11509169024, 
    11517550976, 11525944448, 11534335616, 11542724224, 11551111808, 
    11559500672, 11567890304, 11576277376, 11584667008, 11593056128, 
    11601443456, 11609830016, 11618221952, 11626607488, 11634995072, 
    11643387776, 11651775104, 11660161664, 11668552576, 11676940928, 
    11685330304, 11693718656, 11702106496, 11710496128, 11718882688, 
    11727273088, 11735660416, 11744050048, 11752437376, 11760824704, 
    11769216128, 11777604736, 11785991296, 11794381952, 11802770048, 
    11811157888, 11819548544, 11827932544, 11836324736, 11844713344, 
    11853100928, 11861486464, 11869879936, 11878268032, 11886656896, 
    11895044992, 11903433088, 11911822976, 11920210816, 11928600448, 
    11936987264, 11945375872, 11953761152, 11962151296, 11970543488, 
    11978928512, 11987320448, 11995708288, 12004095104, 12012486272, 
    12020875136, 12029255552, 12037652096, 12046039168, 12054429568, 
    12062813824, 12071206528, 12079594624, 12087983744, 12096371072, 
    12104759936, 12113147264, 12121534592, 12129924992, 12138314624, 
    12146703232, 12155091584, 12163481216, 12171864704, 12180255872, 
    12188643968, 12197034112, 12205424512, 12213811328, 12222199424, 
    12230590336, 12238977664, 12247365248, 12255755392, 12264143488, 
    12272531584, 12280920448, 12289309568, 12297694592, 12306086528, 
    12314475392, 12322865024, 12331253632, 12339640448, 12348029312, 
    12356418944, 12364805248, 12373196672, 12381580928, 12389969024, 
    12398357632, 12406750592, 12415138432, 12423527552, 12431916416, 
    12440304512, 12448692352, 12457081216, 12465467776, 12473859968, 
    12482245504, 12490636672, 12499025536, 12507411584, 12515801728, 
    12524190592, 12532577152, 12540966272, 12549354368, 12557743232, 
    12566129536, 12574523264, 12582911872, 12591299456, 12599688064, 
    12608074624, 12616463488, 12624845696, 12633239936, 12641631616, 
    12650019968, 12658407296, 12666795136, 12675183232, 12683574656, 
    12691960192, 12700350592, 12708740224, 12717128576, 12725515904, 
    12733906816, 12742295168, 12750680192, 12759071872, 12767460736, 
    12775848832, 12784236928, 12792626816, 12801014656, 12809404288, 
    12817789312, 12826181504, 12834568832, 12842954624, 12851345792, 
    12859732352, 12868122496, 12876512128, 12884901248, 12893289088, 
    12901672832, 12910067584, 12918455168, 12926842496, 12935232896, 
    12943620736, 12952009856, 12960396928, 12968786816, 12977176192, 
    12985563776, 12993951104, 13002341504, 13010730368, 13019115392, 
    13027506304, 13035895168, 13044272512, 13052673152, 13061062528, 
    13069446272, 13077838976, 13086227072, 13094613632, 13103000192, 
    13111393664, 13119782528, 13128157568, 13136559232, 13144945024, 
    13153329536, 13161724288, 13170111872, 13178502784, 13186884736, 
    13195279744, 13203667072, 13212057472, 13220445824, 13228832128, 
    13237221248, 13245610624, 13254000512, 13262388352, 13270777472, 
    13279166336, 13287553408, 13295943296, 13304331904, 13312719488, 
    13321108096, 13329494656, 13337885824, 13346274944, 13354663808, 
    13363051136, 13371439232, 13379825024, 13388210816, 13396605056, 
    13404995456, 13413380224, 13421771392, 13430159744, 13438546048, 
    13446937216, 13455326848, 13463708288, 13472103808, 13480492672, 
    13488875648, 13497269888, 13505657728, 13514045312, 13522435712, 
    13530824576, 13539210112, 13547599232, 13555989376, 13564379008, 
    13572766336, 13581154432, 13589544832, 13597932928, 13606320512, 
    13614710656, 13623097472, 13631477632, 13639874944, 13648264064, 
    13656652928, 13665041792, 13673430656, 13681818496, 13690207616, 
    13698595712, 13706982272, 13715373184, 13723762048, 13732150144, 
    13740536704, 13748926592, 13757316224, 13765700992, 13774090112, 
    13782477952, 13790869376, 13799259008, 13807647872, 13816036736, 
    13824425344, 13832814208, 13841202304, 13849591424, 13857978752, 
    13866368896, 13874754688, 13883145344, 13891533184, 13899919232, 
    13908311168, 13916692096, 13925085056, 13933473152, 13941866368, 
    13950253696, 13958643584, 13967032192, 13975417216, 13983807616, 
    13992197504, 14000582272, 14008973696, 14017363072, 14025752192, 
    14034137984, 14042528384, 14050918016, 14059301504, 14067691648, 
    14076083584, 14084470144, 14092852352, 14101249664, 14109635968, 
    14118024832, 14126407552, 14134804352, 14143188608, 14151577984, 
    14159968384, 14168357248, 14176741504, 14185127296, 14193521024, 
    14201911424, 14210301824, 14218685056, 14227067264, 14235467392, 
    14243855488, 14252243072, 14260630144, 14269021568, 14277409408, 
    14285799296, 14294187904, 14302571392, 14310961792, 14319353728, 
    14327738752, 14336130944, 14344518784, 14352906368, 14361296512, 
    14369685376, 14378071424, 14386462592, 14394848128, 14403230848, 
    14411627392, 14420013952, 14428402304, 14436793472, 14445181568, 
    14453569664, 14461959808, 14470347904, 14478737024, 14487122816, 
    14495511424, 14503901824, 14512291712, 14520677504, 14529064832, 
    14537456768, 14545845632, 14554234496, 14562618496, 14571011456, 
    14579398784, 14587789184, 14596172672, 14604564608, 14612953984, 
    14621341312, 14629724288, 14638120832, 14646503296, 14654897536, 
    14663284864, 14671675264, 14680061056, 14688447616, 14696835968, 
    14705228416, 14713616768, 14722003328, 14730392192, 14738784128, 
    14747172736, 14755561088, 14763947648, 14772336512, 14780725376, 
    14789110144, 14797499776, 14805892736, 14814276992, 14822670208, 
    14831056256, 14839444352, 14847836032, 14856222848, 14864612992, 
    14872997504, 14881388672, 14889775744, 14898165376, 14906553472, 
    14914944896, 14923329664, 14931721856, 14940109696, 14948497024, 
    14956887424, 14965276544, 14973663616, 14982053248, 14990439808, 
    14998830976, 15007216768, 15015605888, 15023995264, 15032385152, 
    15040768384, 15049154944, 15057549184, 15065939072, 15074328448, 
    15082715008, 15091104128, 15099493504, 15107879296, 15116269184, 
    15124659584, 15133042304, 15141431936, 15149824384, 15158214272, 
    15166602368, 15174991232, 15183378304, 15191760512, 15200154496, 
    15208542592, 15216931712, 15225323392, 15233708416, 15242098048, 
    15250489216, 15258875264, 15267265408, 15275654528, 15284043136, 
    15292431488, 15300819584, 15309208192, 15317596544, 15325986176, 
    15334374784, 15342763648, 15351151744, 15359540608, 15367929728, 
    15376318336, 15384706432, 15393092992, 15401481856, 15409869952, 
    15418258816, 15426649984, 15435037568, 15443425664, 15451815296, 
    15460203392, 15468589184, 15476979328, 15485369216, 15493755776, 
    15502146944, 15510534272, 15518924416, 15527311232, 15535699072, 
    15544089472, 15552478336, 15560866688, 15569254528, 15577642624, 
    15586031488, 15594419072, 15602809472, 15611199104, 15619586432, 
    15627975296, 15636364928, 15644753792, 15653141888, 15661529216, 
    15669918848, 15678305152, 15686696576, 15695083136, 15703474048, 
    15711861632, 15720251264, 15728636288, 15737027456, 15745417088, 
    15753804928, 15762194048, 15770582656, 15778971008, 15787358336, 
    15795747712, 15804132224, 15812523392, 15820909696, 15829300096, 
    15837691264, 15846071936, 15854466944, 15862855808, 15871244672, 
    15879634816, 15888020608, 15896409728, 15904799104, 15913185152, 
    15921577088, 15929966464, 15938354816, 15946743424, 15955129472, 
    15963519872, 15971907968, 15980296064, 15988684928, 15997073024, 
    16005460864, 16013851264, 16022241152, 16030629248, 16039012736, 
    16047406976, 16055794816, 16064181376, 16072571264, 16080957824, 
    16089346688, 16097737856, 16106125184, 16114514816, 16122904192, 
    16131292544, 16139678848, 16148066944, 16156453504, 16164839552, 
    16173236096, 16181623424, 16190012032, 16198401152, 16206790528, 
    16215177344, 16223567744, 16231956352, 16240344704, 16248731008, 
    16257117824, 16265504384, 16273898624, 16282281856, 16290668672, 
    16299064192, 16307449216, 16315842176, 16324230016, 16332613504, 
    16341006464, 16349394304, 16357783168, 16366172288, 16374561664, 
    16382951296, 16391337856, 16399726208, 16408116352, 16416505472, 
    16424892032, 16433282176, 16441668224, 16450058624, 16458448768, 
    16466836864, 16475224448, 16483613056, 16492001408, 16500391808, 
    16508779648, 16517166976, 16525555328, 16533944192, 16542330752, 
    16550719616, 16559110528, 16567497088, 16575888512, 16584274816, 
    16592665472, 16601051008, 16609442944, 16617832064, 16626218624, 
    16634607488, 16642996096, 16651385728, 16659773824, 16668163712, 
    16676552576, 16684938112, 16693328768, 16701718144, 16710095488, 
    16718492288, 16726883968, 16735272832, 16743661184, 16752049792, 
    16760436608, 16768827008, 16777214336, 16785599104, 16793992832, 
    16802381696, 16810768768, 16819151744, 16827542656, 16835934848, 
    16844323712, 16852711552, 16861101952, 16869489536, 16877876864, 
    16886265728, 16894653056, 16903044736, 16911431296, 16919821696, 
    16928207488, 16936592768, 16944987776, 16953375616, 16961763968, 
    16970152832, 16978540928, 16986929536, 16995319168, 17003704448, 
    17012096896, 17020481152, 17028870784, 17037262208, 17045649536, 
    17054039936, 17062426496, 17070814336, 17079205504, 17087592064, 
    17095978112, 17104369024, 17112759424, 17121147776, 17129536384, 
    17137926016, 17146314368, 17154700928, 17163089792, 17171480192, 
    17179864192, 17188256896, 17196644992, 17205033856, 17213423488, 
    17221811072, 17230198912, 17238588032, 17246976896, 17255360384, 
    17263754624, 17272143232, 17280530048, 17288918912, 17297309312, 
    17305696384, 17314085504, 17322475136, 17330863744, 17339252096, 
    17347640192, 17356026496, 17364413824, 17372796544, 17381190016, 
    17389583488, 17397972608, 17406360704, 17414748544, 17423135872, 
    17431527296, 17439915904, 17448303232, 17456691584, 17465081728, 
    17473468288, 17481857408, 17490247552, 17498635904, 17507022464, 
    17515409024, 17523801728, 17532189824, 17540577664, 17548966016, 
    17557353344, 17565741184, 17574131584, 17582519168, 17590907008, 
    17599296128, 17607687808, 17616076672, 17624455808, 17632852352, 
    17641238656, 17649630848, 17658018944, 17666403968, 17674794112, 
    17683178368, 17691573376, 17699962496, 17708350592, 17716739968, 
    17725126528, 17733517184, 17741898112, 17750293888, 17758673024, 
    17767070336, 17775458432, 17783848832, 17792236928, 17800625536, 
    17809012352, 17817402752, 17825785984, 17834178944, 17842563968, 
    17850955648, 17859344512, 17867732864, 17876119424, 17884511872, 
    17892900224, 17901287296, 17909677696, 17918058112, 17926451072, 
    17934843776, 17943230848, 17951609216, 17960008576, 17968397696, 
    17976784256, 17985175424, 17993564032, 18001952128, 18010339712, 
    18018728576, 18027116672, 18035503232, 18043894144, 18052283264, 
    18060672128, 18069056384, 18077449856, 18085837184, 18094225792, 
    18102613376, 18111004544, 18119388544, 18127781248, 18136170368, 
    18144558976, 18152947328, 18161336192, 18169724288, 18178108544, 
    18186498944, 18194886784, 18203275648, 18211666048, 18220048768, 
    18228444544, 18236833408, 18245220736]


    cache_sizes = [
    16776896, 16907456, 17039296, 17170112, 17301056, 17432512, 17563072, 
    17693888, 17824192, 17955904, 18087488, 18218176, 18349504, 18481088, 
    18611392, 18742336, 18874304, 19004224, 19135936, 19267264, 19398208, 
    19529408, 19660096, 19791424, 19922752, 20053952, 20184896, 20315968, 
    20446912, 20576576, 20709184, 20840384, 20971072, 21102272, 21233216, 
    21364544, 21494848, 21626816, 21757376, 21887552, 22019392, 22151104, 
    22281536, 22412224, 22543936, 22675264, 22806464, 22935872, 23068096, 
    23198272, 23330752, 23459008, 23592512, 23723968, 23854912, 23986112, 
    24116672, 24247616, 24378688, 24509504, 24640832, 24772544, 24903488, 
    25034432, 25165376, 25296704, 25427392, 25558592, 25690048, 25820096, 
    25951936, 26081728, 26214208, 26345024, 26476096, 26606656, 26737472, 
    26869184, 26998208, 27131584, 27262528, 27393728, 27523904, 27655744, 
    27786688, 27917888, 28049344, 28179904, 28311488, 28441792, 28573504, 
    28700864, 28835648, 28966208, 29096768, 29228608, 29359808, 29490752, 
    29621824, 29752256, 29882816, 30014912, 30144448, 30273728, 30406976, 
    30538432, 30670784, 30799936, 30932672, 31063744, 31195072, 31325248, 
    31456192, 31588288, 31719232, 31850432, 31981504, 32110784, 32243392, 
    32372672, 32505664, 32636608, 32767808, 32897344, 33029824, 33160768, 
    33289664, 33423296, 33554368, 33683648, 33816512, 33947456, 34076992, 
    34208704, 34340032, 34471744, 34600256, 34734016, 34864576, 34993984, 
    35127104, 35258176, 35386688, 35518528, 35650624, 35782336, 35910976, 
    36044608, 36175808, 36305728, 36436672, 36568384, 36699968, 36830656, 
    36961984, 37093312, 37223488, 37355072, 37486528, 37617472, 37747904, 
    37879232, 38009792, 38141888, 38272448, 38403392, 38535104, 38660672, 
    38795584, 38925632, 39059264, 39190336, 39320768, 39452096, 39581632, 
    39713984, 39844928, 39974848, 40107968, 40238144, 40367168, 40500032, 
    40631744, 40762816, 40894144, 41023552, 41155904, 41286208, 41418304, 
    41547712, 41680448, 41811904, 41942848, 42073792, 42204992, 42334912, 
    42467008, 42597824, 42729152, 42860096, 42991552, 43122368, 43253696, 
    43382848, 43515712, 43646912, 43777088, 43907648, 44039104, 44170432, 
    44302144, 44433344, 44564288, 44694976, 44825152, 44956864, 45088448, 
    45219008, 45350464, 45481024, 45612608, 45744064, 45874496, 46006208, 
    46136768, 46267712, 46399424, 46529344, 46660672, 46791488, 46923328, 
    47053504, 47185856, 47316928, 47447872, 47579072, 47710144, 47839936, 
    47971648, 48103232, 48234176, 48365248, 48496192, 48627136, 48757312, 
    48889664, 49020736, 49149248, 49283008, 49413824, 49545152, 49675712, 
    49807168, 49938368, 50069056, 50200256, 50331584, 50462656, 50593472, 
    50724032, 50853952, 50986048, 51117632, 51248576, 51379904, 51510848, 
    51641792, 51773248, 51903296, 52035136, 52164032, 52297664, 52427968, 
    52557376, 52690112, 52821952, 52952896, 53081536, 53213504, 53344576, 
    53475776, 53608384, 53738816, 53870528, 54000832, 54131776, 54263744, 
    54394688, 54525248, 54655936, 54787904, 54918592, 55049152, 55181248, 
    55312064, 55442752, 55574336, 55705024, 55836224, 55967168, 56097856, 
    56228672, 56358592, 56490176, 56621888, 56753728, 56884928, 57015488, 
    57146816, 57278272, 57409216, 57540416, 57671104, 57802432, 57933632, 
    58064576, 58195264, 58326976, 58457408, 58588864, 58720192, 58849984, 
    58981696, 59113024, 59243456, 59375552, 59506624, 59637568, 59768512, 
    59897792, 60030016, 60161984, 60293056, 60423872, 60554432, 60683968, 
    60817216, 60948032, 61079488, 61209664, 61341376, 61471936, 61602752, 
    61733696, 61865792, 61996736, 62127808, 62259136, 62389568, 62520512, 
    62651584, 62781632, 62910784, 63045056, 63176128, 63307072, 63438656, 
    63569216, 63700928, 63831616, 63960896, 64093888, 64225088, 64355392, 
    64486976, 64617664, 64748608, 64879424, 65009216, 65142464, 65273792, 
    65402816, 65535424, 65666752, 65797696, 65927744, 66060224, 66191296, 
    66321344, 66453056, 66584384, 66715328, 66846656, 66977728, 67108672, 
    67239104, 67370432, 67501888, 67631296, 67763776, 67895104, 68026304, 
    68157248, 68287936, 68419264, 68548288, 68681408, 68811968, 68942912, 
    69074624, 69205568, 69337024, 69467584, 69599168, 69729472, 69861184, 
    69989824, 70122944, 70253888, 70385344, 70515904, 70647232, 70778816, 
    70907968, 71040832, 71171648, 71303104, 71432512, 71564992, 71695168, 
    71826368, 71958464, 72089536, 72219712, 72350144, 72482624, 72613568, 
    72744512, 72875584, 73006144, 73138112, 73268672, 73400128, 73530944, 
    73662272, 73793344, 73924544, 74055104, 74185792, 74316992, 74448832, 
    74579392, 74710976, 74841664, 74972864, 75102784, 75233344, 75364544, 
    75497024, 75627584, 75759296, 75890624, 76021696, 76152256, 76283072, 
    76414144, 76545856, 76676672, 76806976, 76937792, 77070016, 77200832, 
    77331392, 77462464, 77593664, 77725376, 77856448, 77987776, 78118336, 
    78249664, 78380992, 78511424, 78642496, 78773056, 78905152, 79033664, 
    79166656, 79297472, 79429568, 79560512, 79690816, 79822784, 79953472, 
    80084672, 80214208, 80346944, 80477632, 80608576, 80740288, 80870848, 
    81002048, 81133504, 81264448, 81395648, 81525952, 81657536, 81786304, 
    81919808, 82050112, 82181312, 82311616, 82443968, 82573376, 82705984, 
    82835776, 82967744, 83096768, 83230528, 83359552, 83491264, 83622464, 
    83753536, 83886016, 84015296, 84147776, 84277184, 84409792, 84540608, 
    84672064, 84803008, 84934336, 85065152, 85193792, 85326784, 85458496, 
    85589312, 85721024, 85851968, 85982656, 86112448, 86244416, 86370112, 
    86506688, 86637632, 86769344, 86900672, 87031744, 87162304, 87293632, 
    87424576, 87555392, 87687104, 87816896, 87947968, 88079168, 88211264, 
    88341824, 88473152, 88603712, 88735424, 88862912, 88996672, 89128384, 
    89259712, 89390272, 89521984, 89652544, 89783872, 89914816, 90045376, 
    90177088, 90307904, 90438848, 90569152, 90700096, 90832832, 90963776, 
    91093696, 91223744, 91356992, 91486784, 91618496, 91749824, 91880384, 
    92012224, 92143552, 92273344, 92405696, 92536768, 92666432, 92798912, 
    92926016, 93060544, 93192128, 93322816, 93453632, 93583936, 93715136, 
    93845056, 93977792, 94109504, 94240448, 94371776, 94501184, 94632896, 
    94764224, 94895552, 95023424, 95158208, 95287744, 95420224, 95550016, 
    95681216, 95811904, 95943872, 96075328, 96203584, 96337856, 96468544, 
    96599744, 96731072, 96860992, 96992576, 97124288, 97254848, 97385536, 
    97517248, 97647808, 97779392, 97910464, 98041408, 98172608, 98303168, 
    98434496, 98565568, 98696768, 98827328, 98958784, 99089728, 99220928, 
    99352384, 99482816, 99614272, 99745472, 99876416, 100007104, 
    100138048, 100267072, 100401088, 100529984, 100662592, 100791872, 
    100925248, 101056064, 101187392, 101317952, 101449408, 101580608, 
    101711296, 101841728, 101973824, 102104896, 102235712, 102366016, 
    102498112, 102628672, 102760384, 102890432, 103021888, 103153472, 
    103284032, 103415744, 103545152, 103677248, 103808576, 103939648, 
    104070976, 104201792, 104332736, 104462528, 104594752, 104725952, 
    104854592, 104988608, 105118912, 105247808, 105381184, 105511232, 
    105643072, 105774784, 105903296, 106037056, 106167872, 106298944, 
    106429504, 106561472, 106691392, 106822592, 106954304, 107085376, 
    107216576, 107346368, 107478464, 107609792, 107739712, 107872192, 
    108003136, 108131392, 108265408, 108396224, 108527168, 108657344, 
    108789568, 108920384, 109049792, 109182272, 109312576, 109444928, 
    109572928, 109706944, 109837888, 109969088, 110099648, 110230976, 
    110362432, 110492992, 110624704, 110755264, 110886208, 111017408, 
    111148864, 111279296, 111410752, 111541952, 111673024, 111803456, 
    111933632, 112066496, 112196416, 112328512, 112457792, 112590784, 
    112715968, 112852672, 112983616, 113114944, 113244224, 113376448, 
    113505472, 113639104, 113770304, 113901376, 114031552, 114163264, 
    114294592, 114425536, 114556864, 114687424, 114818624, 114948544, 
    115080512, 115212224, 115343296, 115473472, 115605184, 115736128, 
    115867072, 115997248, 116128576, 116260288, 116391488, 116522944, 
    116652992, 116784704, 116915648, 117046208, 117178304, 117308608, 
    117440192, 117569728, 117701824, 117833024, 117964096, 118094656, 
    118225984, 118357312, 118489024, 118617536, 118749632, 118882112, 
    119012416, 119144384, 119275328, 119406016, 119537344, 119668672, 
    119798464, 119928896, 120061376, 120192832, 120321728, 120454336, 
    120584512, 120716608, 120848192, 120979136, 121109056, 121241408, 
    121372352, 121502912, 121634752, 121764416, 121895744, 122027072, 
    122157632, 122289088, 122421184, 122550592, 122682944, 122813888, 
    122945344, 123075776, 123207488, 123338048, 123468736, 123600704, 
    123731264, 123861952, 123993664, 124124608, 124256192, 124386368, 
    124518208, 124649024, 124778048, 124911296, 125041088, 125173696, 
    125303744, 125432896, 125566912, 125696576, 125829056, 125958592, 
    126090304, 126221248, 126352832, 126483776, 126615232, 126746432, 
    126876608, 127008704, 127139392, 127270336, 127401152, 127532224, 
    127663552, 127794752, 127925696, 128055232, 128188096, 128319424, 
    128449856, 128581312, 128712256, 128843584, 128973632, 129103808, 
    129236288, 129365696, 129498944, 129629888, 129760832, 129892288, 
    130023104, 130154048, 130283968, 130416448, 130547008, 130678336, 
    130807616, 130939456, 131071552, 131202112, 131331776, 131464384, 
    131594048, 131727296, 131858368, 131987392, 132120256, 132250816, 
    132382528, 132513728, 132644672, 132774976, 132905792, 133038016, 
    133168832, 133299392, 133429312, 133562048, 133692992, 133823296, 
    133954624, 134086336, 134217152, 134348608, 134479808, 134607296, 
    134741056, 134872384, 135002944, 135134144, 135265472, 135396544, 
    135527872, 135659072, 135787712, 135921472, 136052416, 136182848, 
    136313792, 136444864, 136576448, 136707904, 136837952, 136970048, 
    137099584, 137232064, 137363392, 137494208, 137625536, 137755712, 
    137887424, 138018368, 138149824, 138280256, 138411584, 138539584, 
    138672832, 138804928, 138936128, 139066688, 139196864, 139328704, 
    139460032, 139590208, 139721024, 139852864, 139984576, 140115776, 
    140245696, 140376512, 140508352, 140640064, 140769856, 140902336, 
    141032768, 141162688, 141294016, 141426496, 141556544, 141687488, 
    141819584, 141949888, 142080448, 142212544, 142342336, 142474432, 
    142606144, 142736192, 142868288, 142997824, 143129408, 143258944, 
    143392448, 143523136, 143653696, 143785024, 143916992, 144045632, 
    144177856, 144309184, 144440768, 144570688, 144701888, 144832448, 
    144965056, 145096384, 145227584, 145358656, 145489856, 145620928, 
    145751488, 145883072, 146011456, 146144704, 146275264, 146407232, 
    146538176, 146668736, 146800448, 146931392, 147062336, 147193664, 
    147324224, 147455936, 147586624, 147717056, 147848768, 147979456, 
    148110784, 148242368, 148373312, 148503232, 148635584, 148766144, 
    148897088, 149028416, 149159488, 149290688, 149420224, 149551552, 
    149683136, 149814976, 149943616, 150076352, 150208064, 150338624, 
    150470464, 150600256, 150732224, 150862784, 150993088, 151125952, 
    151254976, 151388096, 151519168, 151649728, 151778752, 151911104, 
    152042944, 152174144, 152304704, 152435648, 152567488, 152698816, 
    152828992, 152960576, 153091648, 153222976, 153353792, 153484096, 
    153616192, 153747008, 153878336, 154008256, 154139968, 154270912, 
    154402624, 154533824, 154663616, 154795712, 154926272, 155057984, 
    155188928, 155319872, 155450816, 155580608, 155712064, 155843392, 
    155971136, 156106688, 156237376, 156367424, 156499264, 156630976, 
    156761536, 156892352, 157024064, 157155008, 157284416, 157415872, 
    157545536, 157677248, 157810496, 157938112, 158071744, 158203328, 
    158334656, 158464832, 158596288, 158727616, 158858048, 158988992, 
    159121216, 159252416, 159381568, 159513152, 159645632, 159776192, 
    159906496, 160038464, 160169536, 160300352, 160430656, 160563008, 
    160693952, 160822208, 160956352, 161086784, 161217344, 161349184, 
    161480512, 161611456, 161742272, 161873216, 162002752, 162135872, 
    162266432, 162397888, 162529216, 162660032, 162790976, 162922048, 
    163052096, 163184576, 163314752, 163446592, 163577408, 163707968, 
    163839296, 163969984, 164100928, 164233024, 164364224, 164494912, 
    164625856, 164756672, 164887616, 165019072, 165150016, 165280064, 
    165412672, 165543104, 165674944, 165805888, 165936832, 166067648, 
    166198336, 166330048, 166461248, 166591552, 166722496, 166854208, 
    166985408, 167116736, 167246656, 167378368, 167508416, 167641024, 
    167771584, 167903168, 168034112, 168164032, 168295744, 168427456, 
    168557632, 168688448, 168819136, 168951616, 169082176, 169213504, 
    169344832, 169475648, 169605952, 169738048, 169866304, 169999552, 
    170131264, 170262464, 170393536, 170524352, 170655424, 170782016, 
    170917696, 171048896, 171179072, 171310784, 171439936, 171573184, 
    171702976, 171835072, 171966272, 172097216, 172228288, 172359232, 
    172489664, 172621376, 172747712, 172883264, 173014208, 173144512, 
    173275072, 173407424, 173539136, 173669696, 173800768, 173931712, 
    174063424, 174193472, 174325696, 174455744, 174586816, 174718912, 
    174849728, 174977728, 175109696, 175242688, 175374272, 175504832, 
    175636288, 175765696, 175898432, 176028992, 176159936, 176291264, 
    176422592, 176552512, 176684864, 176815424, 176946496, 177076544, 
    177209152, 177340096, 177470528, 177600704, 177731648, 177864256, 
    177994816, 178126528, 178257472, 178387648, 178518464, 178650176, 
    178781888, 178912064, 179044288, 179174848, 179305024, 179436736, 
    179568448, 179698496, 179830208, 179960512, 180092608, 180223808, 
    180354752, 180485696, 180617152, 180748096, 180877504, 181009984, 
    181139264, 181272512, 181402688, 181532608, 181663168, 181795136, 
    181926592, 182057536, 182190016, 182320192, 182451904, 182582336, 
    182713792, 182843072, 182976064, 183107264, 183237056, 183368384, 
    183494848, 183631424, 183762752, 183893824, 184024768, 184154816, 
    184286656, 184417984, 184548928, 184680128, 184810816, 184941248, 
    185072704, 185203904, 185335616, 185465408, 185596352, 185727296, 
    185859904, 185989696, 186121664, 186252992, 186383552, 186514112, 
    186645952, 186777152, 186907328, 187037504, 187170112, 187301824, 
    187429184, 187562048, 187693504, 187825472, 187957184, 188087104, 
    188218304, 188349376, 188481344, 188609728, 188743616, 188874304, 
    189005248, 189136448, 189265088, 189396544, 189528128, 189660992, 
    189791936, 189923264, 190054208, 190182848, 190315072, 190447424, 
    190577984, 190709312, 190840768, 190971328, 191102656, 191233472, 
    191364032, 191495872, 191626816, 191758016, 191888192, 192020288, 
    192148928, 192282176, 192413504, 192542528, 192674752, 192805952, 
    192937792, 193068608, 193198912, 193330496, 193462208, 193592384, 
    193723456, 193854272, 193985984, 194116672, 194247232, 194379712, 
    194508352, 194641856, 194772544, 194900672, 195035072, 195166016, 
    195296704, 195428032, 195558592, 195690304, 195818176, 195952576, 
    196083392, 196214336, 196345792, 196476736, 196607552, 196739008, 
    196869952, 197000768, 197130688, 197262784, 197394368, 197523904, 
    197656384, 197787584, 197916608, 198049472, 198180544, 198310208, 
    198442432, 198573632, 198705088, 198834368, 198967232, 199097792, 
    199228352, 199360192, 199491392, 199621696, 199751744, 199883968, 
    200014016, 200146624, 200276672, 200408128, 200540096, 200671168, 
    200801984, 200933312, 201062464, 201194944, 201326144, 201457472, 
    201588544, 201719744, 201850816, 201981632, 202111552, 202244032, 
    202374464, 202505152, 202636352, 202767808, 202898368, 203030336, 
    203159872, 203292608, 203423296, 203553472, 203685824, 203816896, 
    203947712, 204078272, 204208192, 204341056, 204472256, 204603328, 
    204733888, 204864448, 204996544, 205125568, 205258304, 205388864, 
    205517632, 205650112, 205782208, 205913536, 206044736, 206176192, 
    206307008, 206434496, 206569024, 206700224, 206831168, 206961856, 
    207093056, 207223616, 207355328, 207486784, 207616832, 207749056, 
    207879104, 208010048, 208141888, 208273216, 208404032, 208534336, 
    208666048, 208796864, 208927424, 209059264, 209189824, 209321792, 
    209451584, 209582656, 209715136, 209845568, 209976896, 210106432, 
    210239296, 210370112, 210501568, 210630976, 210763712, 210894272, 
    211024832, 211156672, 211287616, 211418176, 211549376, 211679296, 
    211812032, 211942592, 212074432, 212204864, 212334016, 212467648, 
    212597824, 212727616, 212860352, 212991424, 213120832, 213253952, 
    213385024, 213515584, 213645632, 213777728, 213909184, 214040128, 
    214170688, 214302656, 214433728, 214564544, 214695232, 214826048, 
    214956992, 215089088, 215219776, 215350592, 215482304, 215613248, 
    215743552, 215874752, 216005312, 216137024, 216267328, 216399296, 
    216530752, 216661696, 216790592, 216923968, 217054528, 217183168, 
    217316672, 217448128, 217579072, 217709504, 217838912, 217972672, 
    218102848, 218233024, 218364736, 218496832, 218627776, 218759104, 
    218888896, 219021248, 219151936, 219281728, 219413056, 219545024, 
    219675968, 219807296, 219938624, 220069312, 220200128, 220331456, 
    220461632, 220592704, 220725184, 220855744, 220987072, 221117888, 
    221249216, 221378368, 221510336, 221642048, 221772736, 221904832, 
    222031808, 222166976, 222297536, 222428992, 222559936, 222690368, 
    222820672, 222953152, 223083968, 223213376, 223345984, 223476928, 
    223608512, 223738688, 223869376, 224001472, 224132672, 224262848, 
    224394944, 224524864, 224657344, 224788288, 224919488, 225050432, 
    225181504, 225312704, 225443776, 225574592, 225704768, 225834176, 
    225966784, 226097216, 226229824, 226360384, 226491712, 226623424, 
    226754368, 226885312, 227015104, 227147456, 227278528, 227409472, 
    227539904, 227669696, 227802944, 227932352, 228065216, 228196288, 
    228326464, 228457792, 228588736, 228720064, 228850112, 228981056, 
    229113152, 229243328, 229375936, 229505344, 229636928, 229769152, 
    229894976, 230030272, 230162368, 230292416, 230424512, 230553152, 
    230684864, 230816704, 230948416, 231079616, 231210944, 231342016, 
    231472448, 231603776, 231733952, 231866176, 231996736, 232127296, 
    232259392, 232388672, 232521664, 232652608, 232782272, 232914496, 
    233043904, 233175616, 233306816, 233438528, 233569984, 233699776, 
    233830592, 233962688, 234092224, 234221888, 234353984, 234485312, 
    234618304, 234749888, 234880832, 235011776, 235142464, 235274048, 
    235403456, 235535936, 235667392, 235797568, 235928768, 236057152, 
    236190272, 236322752, 236453312, 236583616, 236715712, 236846528, 
    236976448, 237108544, 237239104, 237371072, 237501632, 237630784, 
    237764416, 237895232, 238026688, 238157632, 238286912, 238419392, 
    238548032, 238681024, 238812608, 238941632, 239075008, 239206336, 
    239335232, 239466944, 239599168, 239730496, 239861312, 239992384, 
    240122816, 240254656, 240385856, 240516928, 240647872, 240779072, 
    240909632, 241040704, 241171904, 241302848, 241433408, 241565248, 
    241696192, 241825984, 241958848, 242088256, 242220224, 242352064, 
    242481856, 242611648, 242744896, 242876224, 243005632, 243138496, 
    243268672, 243400384, 243531712, 243662656, 243793856, 243924544, 
    244054592, 244187072, 244316608, 244448704, 244580032, 244710976, 
    244841536, 244972864, 245104448, 245233984, 245365312, 245497792, 
    245628736, 245759936, 245889856, 246021056, 246152512, 246284224, 
    246415168, 246545344, 246675904, 246808384, 246939584, 247070144, 
    247199552, 247331648, 247463872, 247593536, 247726016, 247857088, 
    247987648, 248116928, 248249536, 248380736, 248512064, 248643008, 
    248773312, 248901056, 249036608, 249167552, 249298624, 249429184, 
    249560512, 249692096, 249822784, 249954112, 250085312, 250215488, 
    250345792, 250478528, 250608704, 250739264, 250870976, 251002816, 
    251133632, 251263552, 251395136, 251523904, 251657792, 251789248, 
    251919424, 252051392, 252182464, 252313408, 252444224, 252575552, 
    252706624, 252836032, 252968512, 253099712, 253227584, 253361728, 
    253493056, 253623488, 253754432, 253885504, 254017216, 254148032, 
    254279488, 254410432, 254541376, 254672576, 254803264, 254933824, 
    255065792, 255196736, 255326528, 255458752, 255589952, 255721408, 
    255851072, 255983296, 256114624, 256244416, 256374208, 256507712, 
    256636096, 256768832, 256900544, 257031616, 257162176, 257294272, 
    257424448, 257555776, 257686976, 257818432, 257949632, 258079552, 
    258211136, 258342464, 258473408, 258603712, 258734656, 258867008, 
    258996544, 259127744, 259260224, 259391296, 259522112, 259651904, 
    259784384, 259915328, 260045888, 260175424, 260308544, 260438336, 
    260570944, 260700992, 260832448, 260963776, 261092672, 261226304, 
    261356864, 261487936, 261619648, 261750592, 261879872, 262011968, 
    262143424, 262274752, 262404416, 262537024, 262667968, 262799296, 
    262928704, 263061184, 263191744, 263322944, 263454656, 263585216, 
    263716672, 263847872, 263978944, 264108608, 264241088, 264371648, 
    264501184, 264632768, 264764096, 264895936, 265024576, 265158464, 
    265287488, 265418432, 265550528, 265681216, 265813312, 265943488, 
    266075968, 266206144, 266337728, 266468032, 266600384, 266731072, 
    266862272, 266993344, 267124288, 267255616, 267386432, 267516992, 
    267648704, 267777728, 267910592, 268040512, 268172096, 268302784, 
    268435264, 268566208, 268696256, 268828096, 268959296, 269090368, 
    269221312, 269352256, 269482688, 269614784, 269745856, 269876416, 
    270007616, 270139328, 270270272, 270401216, 270531904, 270663616, 
    270791744, 270924736, 271056832, 271186112, 271317184, 271449536, 
    271580992, 271711936, 271843136, 271973056, 272105408, 272236352, 
    272367296, 272498368, 272629568, 272759488, 272891456, 273022784, 
    273153856, 273284672, 273415616, 273547072, 273677632, 273808448, 
    273937088, 274071488, 274200896, 274332992, 274463296, 274595392, 
    274726208, 274857536, 274988992, 275118656, 275250496, 275382208, 
    275513024, 275643968, 275775296, 275906368, 276037184, 276167872, 
    276297664, 276429376, 276560576, 276692672, 276822976, 276955072, 
    277085632, 277216832, 277347008, 277478848, 277609664, 277740992, 
    277868608, 278002624, 278134336, 278265536, 278395328, 278526784, 
    278657728, 278789824, 278921152, 279052096, 279182912, 279313088, 
    279443776, 279576256, 279706048, 279838528, 279969728, 280099648, 
    280230976, 280361408, 280493632, 280622528, 280755392, 280887104, 
    281018176, 281147968, 281278912, 281411392, 281542592, 281673152, 
    281803712, 281935552, 282066496, 282197312, 282329024, 282458816, 
    282590272, 282720832, 282853184, 282983744, 283115072, 283246144, 
    283377344, 283508416, 283639744, 283770304, 283901504, 284032576, 
    284163136, 284294848, 284426176, 284556992, 284687296, 284819264, 
    284950208, 285081536]

    展开全文
  • 以太坊Ethash算法

    千次阅读 2018-04-15 11:15:56
    Ethash前面我们分析了以太坊挖矿的源码,挖了一个共识引擎的坑,研究了DAG有向无环图的算法,这些都是本文要研究的Ethash的基础。Ethash是目前以太坊基于POW工作量证明的一个共识引擎(也叫挖矿算法)。它的前身是...

    Ethash

    前面我们分析了以太坊挖矿的源码,挖了一个共识引擎的坑,研究了DAG有向无环图的算法,这些都是本文要研究的Ethash的基础。Ethash是目前以太坊基于POW工作量证明的一个共识引擎(也叫挖矿算法)。它的前身是Dagger Hashimoto算法。

    Dagger Hashimoto

    作为以太坊挖矿算法Ethash的前身,Dagger Hashimoto的目的是:

    • 抵制矿机(ASIC,专门用于挖矿的芯片)
    • 轻客户端验证
    • 全链数据存储

    Dagger和Hashimoto其实是两个东西,

    Hashimoto算法

    是这个人Thaddeus Dryja创造的。旨在通过IO限制来抵制矿机。在挖矿过程中,使内存读取限制条件,由于内存设备本身会比计算设备更加便宜以及普遍,在内存升级优化方面,全世界的大公司也都投入巨大,以使内存能够适应各种用户场景,所以有了随机访问内存的概念RAM,因此,现有的内存可能会比较接近最优的评估算法。Hashimoto算法使用区块链作为源数据,满足了上面的1和3的要求。

    Dagger算法

    是这个人Vitalik Buterin发明的。它利用了有向无环图DAG同时实现了Memory-Hard Function内存计算困难但易于验证Memory-easy verification的特性(我们知道这是哈希算法的重要特性之一)。它的理论依据是基于每个特定场合nonce只需要大型数据总量树的一小部分,并且针对每个特定场合nonce的子树的再计算是被禁止挖矿的。因此,需要存储树但也支持一个独立场合nonce的验证价值。Dagger算法注定要替代现存的仅内存计算困难的算法,例如Scrypt(莱特币采用的),它是计算困难同时验证亦困难的算法,当他们的内存计算困难度增加至真正安全的水平,验证的困难度也随之难上加难。然而,Dagger算法被证明是容易受到Sergio Lerner发明的共享内存硬件加速技术,随后在其他路径的研究方面,该算法被遗弃了。

    Memory-Hard Function

    直接翻译过来是内存困难函数,这是为了地址矿机而诞生的一种思想。我们知道挖矿是靠我们的电脑,但是有些硬件厂商会制造专门用于挖矿的硬件设备,它们并不是一台完整的PC机,例如ASIC、GPU以及FPGAs(我们经常能听到GPU挖矿等)。所以这些作为矿机的设备是超越普通PC挖矿的存在,这是不符合我们区块链的去中心化精神的,所以我们要让挖矿设备平等。

    那么该如何让挖矿设备是平等的呢?

    上面谈到Dagger算法的时候其实提到了,这里换一种方式再来介绍一下,现在CPU都是多核的,如果从计算能力来讲,CPU有几核就可以模拟几台设备同时平行挖矿,自然效率就高些,但是这里采用的衡量对象是内存,一台电脑只有一个总内存。我们做过java多线程开发的朋友知道,无论机器性能有多高,但我们写的程序就是单线程的,那么这个程序运行在高配多核电脑和低配单核电脑的区别不大,只要他们的单核运算能力和内存大小一样即可。所以也是这个原理,通过Dagger算法,我们将挖矿流程锁定在以内存为衡量标准的硬件性能上,只要通过“塞一堆数据到内存中”的方式,让多核平行处理发挥不出来,降低硬件的运算优势,只与内存大小有关,这样无论是PC机还是ASIC、GPU以及FPGAs,都可达到平等挖矿的诉求,这也是ASIC-resistant原理,目前抵制矿机的主要手段。

    两个问题的研究

    在Dagger以及Dagger Hashimoto算法中,有两个问题的研究是被搁置的,

    • 基于区块链的工作量证明:一个POW函数包括了运行区块链上的合约。该方法被抛弃是因为这是一个长期的攻击缺陷,因为攻击者能够创建分叉,然后通过一个包含秘密的快速“trapdoor”井盖门的运行机制的合约在该分叉上殖民。
    • 随机环路:一个POW函数由这个人Vlad Zamfir开发,包含了每1000个场合nonces就生成一个新的程序的功能。本质上来讲,每次选择一个新的哈希函数,会比可重配置的FPGAs(可重编程的芯片,不必重新焊接电路板就可通过软件技术重新自定义硬件功能)更快。该方法被暂时搁置,是因为它很难看到有什么机制可以用来生成随机程序是足够全面,因此它的专业化收益是较低的。然而,我们并没有看到为什么这个概念无法让它生效的根本原因,所以暂时搁置。

    Dagger Hashimoto算法

    (区别于Hashimoto)Dagger Hashimoto不是直接将区块链作为数据源,而是使用一个1GB的自定义生成的数据集cache。

    这个数据集是基于区块数据每N个块就会更新。该数据集是使用Dagger算法生成,允许一个自己的高效计算,特定于每个轻客户端校验算法的场合nonce。

    (区别于Dagger)Dagger Hashimoto克服了Dagger的缺陷,它用于查询区块数据的数据集是半永久的,只有在偶然的间隔才会被更新(例如每周一次)。这意味着生成数据集将非常容易,所以Sergio Lerner的争议共享内存加速变得微不足道了。

    挖矿补充

    前面我已经写了一盘关于挖矿的文章了,这一节是挖矿的补充内容。

    以太坊将过渡到POS(proof-of-stake),代替传统的POW,挖矿将会被淘汰掉,所以现在不推荐再去做一名矿工(前期购买设备等成本较大,POS实现前未必能回本)。

    挖掘以太币=网络安全=验证估算

    目前以太坊的POW算法是Ethash,

    Ethash算法包含找到一个nonce值输入到一个算法中,得到的结果是低于一个基于特定困难度的阀值。

    POW算法的关键点是除了暴力枚举,没有任何办法可以找到这个nonce值,但对于验证输出的结果是非常简单容易的。如果输出结果有一个均匀分布,我们就可以保证找到一个nonce值的平均所需时间取决于那个难度阀值,因此我们可以通过调整难度阀值来控制找到一个新块的时间,这就是控制出块速度的原理。

    DAG

    Ethash的POW是memory-hard,支持矿机抵御。这意味着POW计算需要选择一个固定的依赖于nonce值和块头的资源的子集。

    这个资源(大约1G大小)就是DAG!

    一世epoch

    每3万个块会花几个小时的时间生成一个有向无环图DAG。这个DAG被称为epoch,一世(为了好记,refer个秦二世)。DAG只取决于区块高度,它可以被预生成,如果没有预生成的话,客户端需要等待预生成流程结束以后才能继续出块操作。除非客户端真实的提前预缓存了DAG,否则在每个epoch的过渡期间,网络可能会经历一个巨大的区块延迟。

    特例:当你从头启动一个结点时,挖矿工作只会在创建了现世DAG以后启动。

    挖矿奖励

    有三部分:

    • 静态区块创建奖励,精确发放3以太币作为奖励。
    • 当前区块包含的所有交易的gas钱,随着时间推移,gas会越来越便宜,获得的gas总和奖励会低于静态区块创建奖励。
    • 叔块奖励,整块奖励的1/32。

    Ethash

    Ethash算法路线图:

    • 存在一个种子seed,通过扫描块头为每个块计算出来那个点。
    • 根据这个种子seed,可以计算一个16MB的伪随机缓存cache,轻客户端存储这个缓存。
    • 从这个缓存cache中,我们能够生成一个1GB的数据集,该数据集中的每一项都取决于缓存中的一小部分。完整客户端和矿工存储了这个数据集,数据集随着时间线性增长。
    • 挖矿工作包含了抓取数据集的随机片以及运用哈希函数计算他们。校验工作能够在低内存的环境下完成,通过使用缓存再次生成所需的特性数据集的片段,所以你只需要存储缓存cache即可。

    以上提到的大数据集是每3万个块更新一次,所以绝大多数的矿工的工作是读取该数据集而不是改变它。

    pkg ethash源码分析

    以上我们将所有的概念抽象梳理了一下,包括POW,挖矿,Ethash原理流程等,下面我们带着这些理论知识走进源代码中去分析具体的实现。正如我们的题目,本文主要分析的是ethash算法,因此整个源码范围仅限于go-ethereum/consensus/ethash包,该包实现了ethash pow的共识引擎。

    入口

    分析源码要有个入口,这个入口就是在《以太坊源码机制:挖矿》中挖下的坑“Seal方法”,原文留下了这个印子,在本文进行展开讨论。

    在go-ethereum/consensus/consensus.go 接口中定义了如下的方法,正是对应上面的“Seal方法”,该接口方法的定义如下:

    Seal(chain ChainReader, block *types.Block, stop <-chan struct{}) (*types.Block, error)//该方法通过输入一个包含本地矿工挖出的最高区块在主干上生成一个新块。

    参数有ChainReader,Block,stop结构体信号,返回一个主链上的新出的块实体。

    • ChainReader
    // 定义了一些方法,用于在区块头验证以及叔块验证期间,访问本地区块链。
    type ChainReader interface {
        // 获取区块链的链配置
        Config() *params.ChainConfig
    
        // 从本地链获取当前块头
        CurrentHeader() *types.Header
    
        // 通过hash和number从主链中获取一个区块头
        GetHeader(hash common.Hash, number uint64) *types.Header
    
        // 通过number从主链中获取一个区块头
        GetHeaderByNumber(number uint64) *types.Header
    
        // 通过hash从主链中获取一个区块头
        GetHeaderByHash(hash common.Hash) *types.Header
    
        // 通过hash和number从主链中获取一个区块
        GetBlock(hash common.Hash, number uint64) *types.Block
    }

    总结,ChainReader定义了几个方法:从本地区块链获取配置、区块头,从主链中获取区块头、区块,参数条件包括hash和number,随意组合。

    • Block
    // Block代表以太坊区块链中的一个完整的区块
    type Block struct {
        header       *Header // 区块包括头
        uncles       []*Header // 叔块
        transactions Transactions // 交易集合
    
        // caches缓存
        hash atomic.Value
        size atomic.Value
    
        // Td用于core包存储所有的链上的难度
        td *big.Int
    
        // 这些字段用于eth包来跟踪inter-peer内部端点区块的接替
        ReceivedAt   time.Time
        ReceivedFrom interface{}
    }

    总结,Block除了我们熟知的区块中必有的区块头、叔块以及打包存储的交易信息,还有cache缓存的内容,以及每个块之于链的难度值,还有用于跟踪内部端点的字段。

    • stop

    stop是一个空结构体作为信号源。

    关于空结构体的讨论,为什么go里面经常出现struct{}?

    go中除了struct{}类型以外,其他类型都是width,占有存储,而struct{}没有字段,没有方法,width为0,灵活性高,不占内存空间,这可能是让Gopher青睐的原因。

    sealer

    seal方法有两个实现,我们选择ethash,该方法存在于consensus/ethash/sealer.go文件中,第一个函数就是seal的实现,先来看该方法的声明部分:

    // 尝试找到一个nonce值能够满足区块难度需求。
    func (ethash *Ethash) Seal(chain consensus.ChainReader, block *types.Block, stop <-chan struct{}) (*types.Block, error) {

    可以看出这个方法是属于Ethash的指针对象的,

    type Ethash struct {
        // cache配置
        cachedir     string // 缓存位置
        cachesinmem  int    // 在内存中缓存的数量
        cachesondisk int    // 在硬盘中缓存的数量
        
        // DAG挖矿数据集配置
        dagdir       string // DAG位置,存储全部挖矿数据集
        dagsinmem    int    // 在内存中DAG的数量
        dagsondisk   int    // 在硬盘中DAG的数量
    
        // 内存cache
        caches   map[uint64]*cache   // 内存缓存,可反复使用避免再生太频繁
        fcache   *cache              // 为了下一世估算的预生产缓存
        
        // 内存数据集
        datasets map[uint64]*dataset // 内存数据集,可反复使用避免再生太频繁
        fdataset *dataset            // 为了下一世估算的预生产数据集
    
        // 挖矿相关字段
        rand     *rand.Rand    // 随机工具,用来为nonce做适当的种子
        threads  int           // 如果在挖矿,代表挖矿的线程编号
        update   chan struct{} // 更新挖矿中参数的通道
        hashrate metrics.Meter // 测量跟踪平均哈希率
    
        // 以下字段是用于测试
        tester    bool          // 是否使用一个小型测试数据集的标志位
        shared    *Ethash       // 共享pow模式,无法再生缓存
        fakeMode  bool          // Fake模式,是否取消POW检查的标志位
        fakeFull  bool          // 是否取消所有共识规则的标志位
        fakeFail  uint64        // 未通过POW检查的区块号(包含fake模式)
        fakeDelay time.Duration // 验证工作返回消息前的休眠延迟时间
    
        lock sync.Mutex // 为了内存中的缓存和挖矿字段,保证线程安全
    }

    为了更好的读懂之后的代码,我们要对区块头的数据结构进行一个分析:

    type Header struct {
        ParentHash  common.Hash    `json:"parentHash"       gencodec:"required"`
        UncleHash   common.Hash    `json:"sha3Uncles"       gencodec:"required"`
        Coinbase    common.Address `json:"miner"            gencodec:"required"`
        Root        common.Hash    `json:"stateRoot"        gencodec:"required"`
        TxHash      common.Hash    `json:"transactionsRoot" gencodec:"required"`
        ReceiptHash common.Hash    `json:"receiptsRoot"     gencodec:"required"`
        Bloom       Bloom          `json:"logsBloom"        gencodec:"required"`
        Difficulty  *big.Int       `json:"difficulty"       gencodec:"required"`
        Number      *big.Int       `json:"number"           gencodec:"required"`
        GasLimit    *big.Int       `json:"gasLimit"         gencodec:"required"`
        GasUsed     *big.Int       `json:"gasUsed"          gencodec:"required"`
        Time        *big.Int       `json:"timestamp"        gencodec:"required"`
        Extra       []byte         `json:"extraData"        gencodec:"required"`
        MixDigest   common.Hash    `json:"mixHash"          gencodec:"required"`
        Nonce       BlockNonce     `json:"nonce"            gencodec:"required"`
    }

    可以看到一个区块头包含了父块hash值,叔块hash值,Coinbase结点账户地址,状态根,交易hash,接受者hash,日志,难度值,块编号,最低支付gas,花费的gas,时间戳,额外数据,混合hash,nonce值(8个byte)。我们要对这些区块头的成员属性了然于胸,后面的源码内容才能更好的理解。下面我们继续Seal方法,下面展示完整代码:

    func (ethash *Ethash) Seal(chain consensus.ChainReader, block *types.Block, stop <-chan struct{}) (*types.Block, error) {
        // fake模式立即返回0 nonce
        if ethash.fakeMode {
            header := block.Header()
            header.Nonce, header.MixDigest = types.BlockNonce{}, common.Hash{}
            return block.WithSeal(header), nil
        }
        // 共享pow的话,则转到它的共享对象执行Seal操作
        if ethash.shared != nil {
            return ethash.shared.Seal(chain, block, stop)
        }
        // 创建一个runner以及它指挥的多重搜索线程
        abort := make(chan struct{})
        found := make(chan *types.Block)
    
        ethash.lock.Lock() // 线程上锁,保证内存的缓存(包含挖矿字段)安全
        threads := ethash.threads // 挖矿的线程s
        if ethash.rand == nil {// rand为空,则为ethash的字段rand赋值
            // 获得种子
            seed, err := crand.Int(crand.Reader, big.NewInt(math.MaxInt64))
            if err != nil {// 执行失败,有报错
                ethash.lock.Unlock() // 先解锁
                return nil, err // 程序中止,直接返回空块和报错信息
            }
            ethash.rand = rand.New(rand.NewSource(seed.Int64())) // 执行成功,拿到合法种子seed,通过其获得rand对象,赋值。
        }
        ethash.lock.Unlock() // 解锁
        if threads == 0 {// 挖矿线程编号为0,则通过方法返回当前物理上可用CPU编号
            threads = runtime.NumCPU()
        }
        if threads < 0 { // 非法结果
            threads = 0 // 置为0,允许在本地或远程没有额外逻辑的情况下,取消本地挖矿操作
        }
        var pend sync.WaitGroup // 创建一个倒计时锁对象,go语法参照 http://www.cnblogs.com/Evsward/p/goPipeline.html#sync.waitgroup
        for i := 0; i < threads; i++ {
            pend.Add(1)
            go func(id int, nonce uint64) {// 核心代码通过闭包多线程技术来执行。
                defer pend.Done()
                ethash.mine(block, id, nonce, abort, found) // Seal核心工作
            }(i, uint64(ethash.rand.Int63()))//闭包第二个参数表达式uint64(ethash.rand.Int63())通过上面准备好的rand函数随机数结果作为nonce实参传入方法体
        }
        // 直到seal操作被中止或者找到了一个nonce值,否则一直等
        var result *types.Block // 定义一个区块对象result,用于接收操作结果并作为返回值返回上一层
        select { // go语法参照 http://www.cnblogs.com/Evsward/p/go.html#select
        case <-stop:
            // 外部意外中止,停止所有挖矿线程
            close(abort)
        case result = <-found:
            // 其中一个线程挖到正确块,中止其他所有线程
            close(abort)
        case <-ethash.update:
            // ethash对象发生改变,停止当前所有操作,重启当前方法
            close(abort)
            pend.Wait()
            return ethash.Seal(chain, block, stop)
        }
        // 等待所有矿工停止或者返回一个区块
        pend.Wait()
        return result, nil
    }

    以上Seal方法体,针对ethash的各种状态进行了校验和流程处理,以及对线程资源的控制,下面看Seal核心工作的内容(sealer.go文件只有两个函数,一个是Seal方法,另一个就是mine方法,可以看出Seal方法是对外的,而mine方法是内部方法,只能被当前ethash包域调用):mine方法

    // mine函数是真正的pow矿工,用来搜索一个nonce值,nonce值开始于seed值,seed值是能最终产生正确的可匹配可验证的区块难度
    func (ethash *Ethash) mine(block *types.Block, id int, seed uint64, abort chan struct{}, found chan *types.Block) {
        // 从区块头中提取出一些数据,放在一个全局变量域中
        var (
            header = block.Header()
            hash   = header.HashNoNonce().Bytes()
            target = new(big.Int).Div(maxUint256, header.Difficulty) // 后面有大用,这是用来验证的target
    
            number  = header.Number.Uint64()
            dataset = ethash.dataset(number)
        )
        // 开始生成随机nonce值知道我们中止或者成功找到了一个合适的值
        var (
            attempts = int64(0) // 初始化一个尝试次数的变量,下面会利用该变量耍一些花枪
            nonce    = seed // 初始化为seed值,后面每次尝试以后会累加
        )
        logger := log.New("miner", id)
        logger.Trace("Started ethash search for new nonces", "seed", seed)
        for {
            select {
            case <-abort: // 中止命令
                // 挖矿中止,更新状态,中止当前操作,返回空
                logger.Trace("Ethash nonce search aborted", "attempts", nonce-seed)
                ethash.hashrate.Mark(attempts)
                return
    
            default: // 默认执行
                // 我们没必要在每一次尝试nonce值的时候更新hash率,可以在尝试了2的X次方nonce值以后再更新即可
                attempts++ // 通过次数attemp来控制
                if (attempts % (1 << 15)) == 0 {// 这里是定的2的15次方,位操作符请参考 http://www.cnblogs.com/Evsward/p/go.html#%E5%B8%B8%E9%87%8F
                    ethash.hashrate.Mark(attempts) // 满足条件了以后,要更新ethash的hash率字段的状态值
                    attempts = 0 // 重置尝试次数
                }
                // 为这个nonce值计算pow值
                digest, result := hashimotoFull(dataset, hash, nonce) // 调用的hashimotoFull函数在本包的算法库中,后面会介绍。
                if new(big.Int).SetBytes(result).Cmp(target) <= 0 { // 验证标准,后面介绍
                    // 找到正确nonce值,创建一个基于它的新的区块头
                    header = types.CopyHeader(header)
                    header.Nonce = types.EncodeNonce(nonce) // 将输入的整型值转换为一个区块nonce值
                    header.MixDigest = common.BytesToHash(digest) // 将字节数组转换为Hash对象【Hash是32位的根据任意输入数据的Keccak256哈希算法的返回值】
    
                    // 封装返回一个区块
                    select {
                    case found <- block.WithSeal(header):
                        logger.Trace("Ethash nonce found and reported", "attempts", nonce-seed, "nonce", nonce)
                    case <-abort:
                        logger.Trace("Ethash nonce found but discarded", "attempts", nonce-seed, "nonce", nonce)
                    }
                    return
                }
                nonce++ // 累加nonce
            }
        }
    }

    mine方法主要就是对nonce的操作,以及对区块头的重建操作,注释中我们也留了一个坑就是对于nonce尝试的工作,这部分内容会转到算法库中来介绍。

    algorithm

    ethash包中包含几个algorithm开头的文件,这些文件的内容是pow核心算法,用来支持挖矿操作。首先我们继续上面留的坑继续研究。

    hashimotoFull函数

    该函数位于ethash/algorithm.go文件中,

    // 在传入的数据集中通过hash和nonce值计算加密值
    func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
        // 本函数核心代码段:定义一个lookup函数,用于在数据集中查找数据
        lookup := func(index uint32) []uint32 {
            offset := index * hashWords // hashWords是上面定义的常量值= 16
            return dataset[offset : offset+hashWords]
        }
        // hashimotoFull函数做的工作就是将原始数据集进行了读取分割,然后传给hashimoto函数。
        return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
    }

    hashimoto函数

    继续分析,上面的hashimotoFull函数返回的是hashimoto函数的返回值,hashimoto算法我们在上面概念部分已经介绍过了,读源码的朋友不理解的可以翻回上面仔细了解一番再回到这里继续研究。

    // 该函数与hashimotoFull有着相同的愿景:在传入的数据集中通过hash和nonce值计算加密值
    func hashimoto(hash []byte, nonce uint64, size uint64, lookup func(index uint32) []uint32) ([]byte, []byte) {
        // 计算数据集的理论的行数
        rows := uint32(size / mixBytes)
    
        // 合并header+nonce到一个40字节的seed
        seed := make([]byte, 40) // 创建一个长度为40的字节数组,名字为seed
        copy(seed, hash)// 将区块头的hash(上面提到了Hash对象是32字节大小)拷贝到seed中。
        binary.LittleEndian.PutUint64(seed[32:], nonce) // 将nonce值填入seed的后(40-32=8)字节中去,(nonce本身就是uint64类型,是64位,对应8字节大小),正好把hash和nonce完整的填满了40字节的seed
    
        seed = crypto.Keccak512(seed) // seed经历一遍Keccak512加密
        seedHead := binary.LittleEndian.Uint32(seed) // 从seed中获取区块头,代码后面详解
    
        // 开始与重复seed的混合
        mix := make([]uint32, mixBytes/4)// mixBytes常量= 128,mix的长度为32,元素为uint32,是32位,对应为4字节大小。所以mix总共大小为4*32=128字节大小
        for i := 0; i < len(mix); i++ {
            mix[i] = binary.LittleEndian.Uint32(seed[i%16*4:])// 共循环32次,前16和后16位的元素值相同
        }
        // 做一个temp,与mix结构相同,长度相同
        temp := make([]uint32, len(mix))
    
        for i := 0; i < loopAccesses; i++ { // loopAccesses常量 = 64,循环64次
            parent := fnv(uint32(i)^seedHead, mix[i%len(mix)]) % rows // mix[i%len(mix)]是循环依次调用mix的元素值,fnv函数在本代码后面详解
            for j := uint32(0); j < mixBytes/hashBytes; j++ {
                copy(temp[j*hashWords:], lookup(2*parent+j))// 通过用种子seed生成的mix数据进行FNV哈希操作以后的数值作为参数去查找源数据(太绕了)拷贝到temp中去。
            }
            fnvHash(mix, temp) // 将mix中所有元素都与temp中对应位置的元素进行FNV hash运算
        }
        // mix大混淆
        for i := 0; i < len(mix); i += 4 {
            mix[i/4] = fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3])
        }
        // 最后有效数据只在前8个位置,后面的数据经过上面的循环混淆以后没有价值了,所以将mix的长度减到8,保留前8位有效数据。
        mix = mix[:len(mix)/4]
    
        digest := make([]byte, common.HashLength) // common.HashLength=32,创建一个长度为32的字节数组digest
        for i, val := range mix {
            binary.LittleEndian.PutUint32(digest[i*4:], val)// 再把长度为8的mix分散到32位的digest中去。
        }
        return digest, crypto.Keccak256(append(seed, digest...))
    }

    该函数除了被hashimotoFull函数调用以外,还会被hashimotoLight函数调用。顾名思义,hashimotoLight是相对于hashimotoFull的存在。hashimotoLight在后面有机会就介绍(看看能不能绕进我们的route吧)。

    下划线与位运算|

    以上代码中的seedHead := binary.LittleEndian.Uint32(seed),我们挑出来单练,跳转到内部方法为:

    func (littleEndian) Uint32(b []byte) uint32 {
        _ = b[3] // bounds check hint to compiler; see golang.org/issue/14808
        return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
    }
    • go语法补充:下划线变量代表Go语言“垃圾桶”的意思,这个垃圾桶并不是说销毁一个对象,而是针对go语言报错机制来处理的,所以b[3]这一行可以是b[3]未使用防止go报“xxx未使用”的错误,同时观察后面的官方注释,也是为了在真正使用b[3]数据前进行边界检查,如果b[3]为空,则会提前报错,不会引发程序问题。
    • 位运算,我们在《掌握一门语言GO》中对左移和右移进行了介绍,这里针对或|和与&进行介绍。位运算都是将原数据转换为二进制进行运算,或|就是0和1或得1,例如1和2或得3,因为1的二进制表达为01,2的二进制表达为10,01和10或运算以后就是11,等于3。同理,与&运算就是,0和1与得0,所以1和2的与运算结果为0,因为与&运算是只有都为1才能得1。
    FNV hash 算法

    FNV是由三位创建者的名字得来的,我们知道hash算法最重要的目标就是要平均分布(高度分散),避免碰撞,最好相近的源数据加密后完全不同,哪怕他们只有一个字母不一样,FNV hash算法就是这样的一种算法。

    func fnv(a, b uint32) uint32 {
        return a*0x01000193 ^ b
    }
    
    func fnvHash(mix []uint32, data []uint32) {
        for i := 0; i < len(mix); i++ {
            mix[i] = mix[i]*0x01000193 ^ data[i]
        }
    }

    0x01000193是FNV hash算法的一个hash质数(Prime number,又叫素数,只能被1和其本身整除),哈希算法会基于一个常数来做散列操作。0x01000193是FNV针对32 bit数据的散列质数。

    验证方式

    我们一直提,pow是难于计算,上面这么长篇章深刻体现了这一点,但是pow是易于验证的,所以本节讨论的是ethash的pow的验证方式,这个验证方式也很容易找到,就是上面mine方法中我在注释里留下的坑:

    new(big.Int).SetBytes(result).Cmp(target) <= 0

    我们的核心计算nonce对应的加密值digest方法hashimoto算法返回了一个digest和一个result两个值,而由这行代码可知,与验证方式相关的就是result的值。result在hashimoto算法中最终还经过了crypto.Keccak256(append(seed, digest...)的Keccak256加密,参数列表中也看到了digest值。得到result值以后,就要执行上面这行代码的表达式了。这行表达式很简单,主要含义就是将result值和target值进行比较,如果小于等于0,即为通过。

    那么target是什么?

    target被定义在mine方法体中靠前的变量声明部分,

    target = new(big.Int).Div(maxUint256, header.Difficulty)

    可以看出,target的定义是根据区块头中的难度值运算而得出的。所以,这就验证了我们最早在概念部分中提到的,我们可以通过调整Difficulty值,来控制pow运算难度,生成正确nonce的难度,达到pow工作量可控的目标。

    总结

    代码读到这里,已经完成了一个闭环,结合前面的《挖矿》,我们已经走通了以太坊pow的全部流程,整个流程我没有丝毫懈怠,从入口深入到内核,我们把源码扒了底掉(实际上,目前为止的流程中,以太坊的pow并未真正使用到如我所想的DAG)。到目前为止,我们对pow,以及以太坊ethash的实现有了深刻的理解与认识,相信如果让我们去实现一套pow,也是完全有能力的。大家在阅读本文时有任何疑问均可留言给我,我一定会及时回复。

    参考资料

    go-ethereum源码,以太坊官方文档,网络名词解释文章

    展开全文
  • 以太坊Ethash算法源码分析

    千次阅读 2018-08-02 17:14:36
    Ethash以太坊目前使用共识算法,其前身是Dagger-Hashimoto算法,但是进行了很大改动。 1. Dagger-Hashimoto Dagger-Hashimoto算法想要达到以下几个目标: 抵制ASIC矿机 轻客户端验证...

    Ethash是以太坊目前使用的共识算法,其前身是Dagger-Hashimoto算法,但是进行了很大的改动。

    1. Dagger-Hashimoto

    Dagger-Hashimoto算法想要达到以下几个目标:

    • 抵制ASIC矿机
    • 轻客户端验证
    • 全链数据存储

    实际上Dagger-Hashimoto是由两种不同的算法Dagger和Hashimoto融合而成的:

    Hashimoto

    Hashimoto算法由Thaddeus Dryja发明,旨在通过“内存读取”瓶颈来抵制ASIC矿机。ASIC矿机可以通过设计专用电路来提升计算速度,但是很难提升“内存读取”速度,因为经历了这么多年的发展,内存访问已经经过了极致的优化。Hashimoto算法直接采用区块链数据,也就是区块中的交易作为输入源。

    注:为了减小计算量,Dagger-Hashimoto中实际上只使用了低64位参与移位。

    Dagger

    Dagger算法由Vitalik Buterin发明,旨在通过DAG(有向无环图)来同时获得“memory-hard计算”和“memory-easy验证”这两个特性,其主要原理是针对每一个单独的nonce只需要访问数据集中的一小部分数据。Dagger曾经被认为可以替代一些memory-hard的算法(如Scrypt),但是后来被Sergio Lerner证明该算法易于遭受共享内存硬件加速的攻击,从而逐渐被废弃。

    Dagger-Hashimoto vs. Hashimoto vs. Dagger

    Dagger-Hashimoto和Hashimoto的主要区别是:
    Hashimoto直接使用区块链数据作为输入源,而Dagger-Hashimoto使用一个定制的1GB的dataset(数据集)作为输入源,该dataset每隔N个区块会被更新。dataset是通过Dagger算法生成的,轻客户端验证算法可以针对每一个nonce对其中一个子集完成高效计算。

    Dagger-Hashimoto和Dagger的主要区别是:
    与Dagger不同,Dagger-Hashimoto用于查询区块的dataset是半持久化(semi-permanent)的,需要间隔很长一段时间才会更新。这样生成dataset的工作量比例接近于0,Sergio Lerner用于共享内存加速的参数就可以忽略不计了。

    2. Ethash

    Ethash算法主要分为以下几个步骤:

    • 根据区块信息生成一个seed
    • 根据seed计算出一个16MB的伪随机cache,由轻客户端存储
    • 根据cache计算出一个1GB的dataset,其中的每一个数据都是通过cache中的一小部分数据计算出来的。该dataset由完整客户端或者矿工存储,大小随时间线性增长
    • 矿工会从dataset中随机取出数据计算hash
    • 验证者会根据cache重新生成dataset中所需要的那部分数据,因此只需要存储cache就可以了

    这里写图片描述

    下面分别讨论这几个部分的实现。

    2.1 生成seed

    consensus/ethash/ethash.go:

    func (d *dataset) generate(dir string, limit int, test bool) {
        ... ...
        seed := seedHash(d.epoch*epochLength + 1)
        ... ...
    }
    
    func seedHash(block uint64) []byte {
        seed := make([]byte, 32)
        if block < epochLength {
            return seed
        }
        keccak256 := makeHasher(sha3.NewKeccak256())
        for i := 0; i < int(block/epochLength); i++ {
            keccak256(seed, seed)
        }
        return seed
    }
    

    这里有个epoch(纪元)的概念:epochLength等于30000,也就是每30000个区块形成一个纪元,每个纪元更新一次数据集(就是前面提到的“半持久化”)。

    seed初始值为0,每过一个纪元会取前一个seed的哈希值作为下一个纪元的seed。

    2.2 生成cache

    接下来就是用这个seed生成16MB的cache了。首先看一下cache大小的计算:

    func cacheSize(block uint64) uint64 {
        epoch := int(block / epochLength)
        if epoch < maxEpoch {
            return cacheSizes[epoch]
        }
        return calcCacheSize(epoch)
    }
    
    func calcCacheSize(epoch int) uint64 {
        size := cacheInitBytes + cacheGrowthBytes*uint64(epoch) - hashBytes
        for !new(big.Int).SetUint64(size / hashBytes).ProbablyPrime(1) {
            size -= 2 * hashBytes
        }
        return size
    }
    

    前2048(maxEpoch)个纪元的cache大小是硬编码在代码里的,如果超过这个数量就需要自己计算了。
    cache的大小是线性增长的,size的值等于(2^24 + 2^17 * epoch - 64),用这个值除以64看结果是否是一个质数,如果不是,减去128再重新计算,直到找到最大的质数为止。

    接下来分析cache数据的生成:

    func generateCache(dest []uint32, epoch uint64, seed []byte) {
        ... ...
        // Create a hasher to reuse between invocations
        keccak512 := makeHasher(sha3.NewKeccak512())
    
        // Sequentially produce the initial dataset
        keccak512(cache, seed)
        for offset := uint64(hashBytes); offset < size; offset += hashBytes {
            keccak512(cache[offset:], cache[offset-hashBytes:offset])
            atomic.AddUint32(&progress, 1)
        }
        ... ...
    }
    

    看明白没?先用seed的哈希值生成第一个数(64字节),然后以新生成的数作为seed,生成下一个数,依次迭代,直至填充满整个cache。当然这只是第一步,后面还要跟之前cache中的数据按一定规则做一次异或,然后再求一次哈希,具体细节参见一下代码:

        for i := 0; i < cacheRounds; i++ {
            for j := 0; j < rows; j++ {
                var (
                    srcOff = ((j - 1 + rows) % rows) * hashBytes
                    dstOff = j * hashBytes
                    xorOff = (binary.LittleEndian.Uint32(cache[dstOff:]) % uint32(rows)) * hashBytes
                )
                bitutil.XORBytes(temp, cache[srcOff:srcOff+hashBytes], cache[xorOff:xorOff+hashBytes])
                keccak512(cache[dstOff:], temp)
    
                atomic.AddUint32(&progress, 1)
            }
        }
    

    2.3 生成dataset

    dataset大小的计算和cache类似,量级不同:2^30 + 2^23 * epoch - 128,然后每次减256寻找最大质数。

    生成数据是一个循环,每次生成64个字节,所以看generateDatasetItem()就可以了。代码分为下面几个部分:

    1. 用cache里的值进行初始化,计算一次哈希
        // Calculate the number of theoretical rows (we use one buffer nonetheless)
        rows := uint32(len(cache) / hashWords)
    
        // Initialize the mix
        mix := make([]byte, hashBytes)
    
        binary.LittleEndian.PutUint32(mix, cache[(index%rows)*hashWords]^index)
        for i := 1; i < hashWords; i++ {
            binary.LittleEndian.PutUint32(mix[i*4:], cache[(index%rows)*hashWords+uint32(i)])
        }
        keccak512(mix, mix)
    
    1. 转换成无符号整数
        // Convert the mix to uint32s to avoid constant bit shifting
        intMix := make([]uint32, hashWords)
        for i := 0; i < len(intMix); i++ {
            intMix[i] = binary.LittleEndian.Uint32(mix[i*4:])
        }
    

    2)计算FNV哈希

        // fnv it with a lot of random cache nodes based on index
        for i := uint32(0); i < datasetParents; i++ {
            parent := fnv(index^i, intMix[i%16]) % rows
            fnvHash(intMix, cache[parent*hashWords:])
        }
    

    4)整数转回字节数组,再计算一次哈希

        // Flatten the uint32 mix into a binary one and return
        for i, val := range intMix {
            binary.LittleEndian.PutUint32(mix[i*4:], val)
        }
        keccak512(mix, mix)
    

    这里用到了FNV哈希算法,这是一种不需要使用密钥的哈希算法,以它的三位发明者的名字命名:Glenn Fowler, Landon Curt Noll, Kiem-Phong Vo。
    这个FNV算法很简单:a乘以FNV质数0x01000193,然后再和b异或。
    首先用这个算法算出一个索引值,利用这个索引从cache中选出一个值(data),然后对mix中的每个字节都计算一次FNV,得到最终的哈希值:

    func fnv(a, b uint32) uint32 {
        return a*0x01000193 ^ b
    }
    
    func fnvHash(mix []uint32, data []uint32) {
        for i := 0; i < len(mix); i++ {
            mix[i] = mix[i]*0x01000193 ^ data[i]
        }
    }
    

    从这里可以看出,dataset的每个值都是根据对应的cache中的值生成的,因此轻客户端无需存储dataset,只需要在验证的时候按需生成即可。

    2.4 矿工挖矿

    挖矿流程参见下图:
    这里写图片描述

    具体代码参见consensus/ethash/algorithm.go中的hashimotoFull()函数:

    func hashimotoFull(dataset []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
        lookup := func(index uint32) []uint32 {
            offset := index * hashWords
            return dataset[offset : offset+hashWords]
        }
        return hashimoto(hash, nonce, uint64(len(dataset))*4, lookup)
    }
    

    首先提供了一个lookup()函数,用于从dataset中查找数据。接着就是调用hashimoto()函数计算哈希了:首先根据hash和nonce生成一个seed,填充到mix数组中,然后用lookup()函数获取data,最后把mix和data送入fnvHash()函数中计算哈希值。具体代码这里就不分析了。

    2.5 工作量验证

    在节点收到新区块时,需要验证根据区块头的hash和nonce计算出来的FNV哈希值是否确实小于设定的难度值。入口位于core/blockchain.go的insertChain()方法:

    func (bc *BlockChain) insertChain(chain types.Blocks) (int, []interface{}, []*types.Log, error) {
        ... ...
        for i, block := range chain {
            headers[i] = block.Header()
            seals[i] = true
        }
        abort, results := bc.engine.VerifyHeaders(bc, headers, seals)
        ... ...
    }
    

    继续跟踪consensus/ethash/consensus.go中的VerifyHeaders()方法,最终会调用verifyHeader():

    func (ethash *Ethash) verifyHeader(chain consensus.ChainReader, header, parent *types.Header, uncle bool, seal bool) error {
        ... ...
        if seal {
            if err := ethash.VerifySeal(chain, header); err != nil {
                return err
            }
        }
    
        ... ...
    }
    

    这里会调用VerifySeal()方法验证区块头是否符合要求:

    func (ethash *Ethash) VerifySeal(chain consensus.ChainReader, header *types.Header) error {
        ... ...
        digest, result := hashimotoLight(size, cache.cache, header.HashNoNonce().Bytes(), header.Nonce.Uint64())
    
        ... ...
        target := new(big.Int).Div(maxUint256, header.Difficulty)
        if new(big.Int).SetBytes(result).Cmp(target) > 0 {
            return errInvalidPoW
        }
        return nil
    }
    

    可以看到,这里调用hashimotoLight()函数计算FNV哈希值,然后跟目标难度比较,确认是否低于目标难度。这个hashimotoLight()就是为轻客户端节点计算FNV哈希值的,会根据需要通过cache生成少量dataset的值完成计算,有兴趣的同学可以再仔细研究一下具体细节。

    3. 总结

    Ethash是一种“memory-hard计算”和“memory-easy验证”的哈希算法,通过内存访问速度的瓶颈抵抗ASIC矿机,同时利用两级数据集实现挖矿和轻客户端验证的分离。

    参考:
    https://github.com/ethereum/wiki/wiki/Dagger-Hashimoto
    https://github.com/ethereum/wiki/wiki/Ethash
    https://github.com/ethereum/wiki/wiki/Ethash-Design-Rationale
    https://www.vijaypradeep.com/blog/2017-04-28-ethereums-memory-hardness-explained/

    更多文章欢迎关注“鑫鑫点灯”专栏:https://blog.csdn.net/turkeycock
    或关注飞久微信公众号:
    在这里插入图片描述

    展开全文
  • 大家平时在玩 以太坊geth时候,经常会看到Ethash DAG,比如“Disk storage enabled for ethash DAGs”,就是说允许Ethash DAG存储在磁盘中,那么它到底是什么东东?   Ethash是PoW系统,它需要一个大约1GB...

    原文https://blog.csdn.net/angciyu/article/details/80433255

    大家平时在玩 以太坊geth的时候,经常会看到Ethash DAG,比如“Disk storage enabled for ethash DAGs”,就是说允许Ethash DAG存储在磁盘中,那么它到底是什么东东?

     

    Ethash是PoW系统,它需要一个大约1GB的数据集,它就是DAG。这通常需要几个小时才能生成,所以我们倾向于在硬盘中存储它。希望将DAG存储在硬盘中的客户端应符合下面的规范,以便与其他客户端共享缓存:

    存储位置

    DAG应该存储在一个1GB的转储文件中,存储在一个文件中:

    • Mac / Linux中 $(HOME)/.ethash/full-R<REVISION>-<SEEDHASH>
    • windows: $(HOME)/Appdata/Local/Ethash/full-R<REVISION>-<SEEDHASH>

    其中:

    • <REVISION>是一个十进制整数;
    • <SEEDHASH> 是16个小写十六进制数字,指定了纪元的种子散列的前8个字节。

    这个目录中可能有多个这样的DAG文件,取决于用户是否及时删除了那些过时的。

    内容格式

    每个文件应该以8字节的幻数开始,0xfee1deadbaddcafe以little-endian格式(即字节fe ca dd ba ad de e1 fe)写入。

    Ethash算法期望DAG作为uint32s(4字节无符号整数)的二维数组,具有维数(n×16),其中n是大数。(n从16777186开始并从那里增长)。在幻数之后,DAG的行应该顺序写入文件中,在行之间没有分隔符,并且每个unint32以little-endian格式编码。

    展开全文
  • 以太坊挖矿源码:ethash算法

    千次阅读 2018-03-23 18:55:00
    本文具体分析以太坊的共识算法之一:实现了POW的以太坊共识引擎ethash。 关键字:ethash,共识算法,pow,Dagger Hashimoto,ASIC,struct{},nonce,FNV hash,位运算,epoch Ethash 前面我们分析了以太坊挖矿的...
  • ethash是目前以太坊主网(Homestead版本)POW共识算法。 目录结构 ethash模块位于以太坊项目目录下consensus/ethash目录下。 algorithm.go 实现了Dagger-Hashimoto算法的所有功能,比如生成cache和dataset、.
  • 文章目录一、内存依赖挖矿谜题(memory-hard mining puzzle)1.1 莱特币的Scrypt算法二、以太坊的挖矿算法(ethash)2.1 ethash算法介绍2.2 ethash伪代码分析2.3 总结三、以太坊的挖矿难度调整3.1 调整公式3.2 ...
  • Ethereum当前和Bitcoin...与Bitcoin不同是,Ethereum采用共识算法可以抵御ASIC矿机对挖矿工作垄断地位,这个算法叫做Ethash。 为什么要反ASIC PoW的的核心是Hash运算,谁Hash运算更快,谁就更有可能挖掘出...
  • Ethash的C / C ++实现–以太坊工作量证明算法 目录 安装 使用CMake从源代码构建。 mkdir build cd build cmake .. cmake --build . 用法 有关导出功能和文档列表,请参见 。 测试向量 最佳化 本节描述了与有关...
  • 第19讲 以太坊的挖矿算法 挖矿代码的实际演示(伪代码) ethash 算法伪代码: 汇总: 为什么全节点生成好整个dataset再算,而轻节点验算时只计算dataset中需要使用的元素: 以太坊挖矿的一些实际数据 ...
  • 以太坊目前的算法是类似POW的算法ethash。它除了和比特币一样需要消耗电脑资源外进行计算外,还考虑了对专用矿机抵制,增加了挖矿公平性。 一般POW算法思路 POW即工作量证明,也就是通过工作结果来证明你...
  • 什么是挖矿和Ethash算法

    万次阅读 2019-04-12 09:34:52
    以太坊也是这样,发行唯一办法就是挖矿。但是不像其他例子,挖矿也是通过在区块链中创建、验证、发行和传播区块来保护网络方法。 挖以太币=保护网络=验证计算 什么是挖矿? 以太坊,和所有区块链技术一样,...
  • 上文我们总结了以太坊最主要的共识算法:ethash算法,本文将重点分析以太坊的另一个共识算法:clique。 关键字:clique,共识算法,puppeth,以太坊地址原理,区块校验,认证结点,POA,选举投票,snapshot,Comma...
  • 对于没有把数学学会的同学来说,如果希望从算法层了解以太坊的工作量证明是非常困难的。一本黄皮书会难倒一大批吃瓜群众。 从Chat中,所讲内容有: 以太坊挖矿工作量证明 Ethash算法讲解; 以太坊是如何对抗ASIC1;...
  • 以太坊的共识机制

    千次阅读 2018-08-13 14:50:49
    在开始之前,我们补充一点基础知识。   第一个概念是哈希。简单理解,哈希是一个函数。它的作用是将任意长度的数据作为输入,转变为固定长度的一个字符串作为输出。...第二个补充知识是,以太坊的区块结构。...
  • 作为本系列第三篇,这篇文章介绍了以太坊中如何"挖矿"产生一个新区块完整过程,以及Ethash(PoW)和Clique(PoA)两种不同共识算法的实现方案;同时对于各处代码实现中精巧设计,也作了较详细讲解。
  • 经典比特币POW的算法原理是对blockheader加上循环更新nonce去进行hash运算,运算target是hash值前n位为0。这个计算只能通过暴力枚举来进行,验证也很容易,只要使用最终nonce代入header按照...
  • 以太坊区块链

    2018-02-03 20:36:00
    以太坊本质:一个基于交易分布式状态机,状态机类似方程,...以太坊工作证明算法Ethash,与比特币工作量证明稍微有些不同,这使得用普通硬件挖矿成为可能。 3.分叉:使用GHOST协议数学机制让参与节点可以选择...
  • 外汇天眼APP讯 : 2020年,币圈吸金且吸睛莫过于以太坊。无论是DeFi还是,以太坊作为牛市催化剂呼声越来越高。然而,对于以太坊矿工而言,留给4G显卡矿机时间不多了。悬在矿工头上达摩克里斯之剑众所周知,...
  • 2020年,币圈吸金且吸睛莫过于以太坊。无论是DeFi还是ETH2.0,以太坊作为牛市催化剂呼声越来越高。然而,对于以太坊矿工而言,留给4G显卡矿机时间不多了。悬在矿工头上达摩克里斯之剑众所周知,Ethash算法很...

空空如也

空空如也

1 2 3 4
收藏数 67
精华内容 26
关键字:

以太坊的ethash算法