网络建设文章网站安徽省工程信息网官网

网络建设文章网站,安徽省工程信息网官网,英文网站建设390,福州市有哪些制作网站公司综述1.1 简介Equihash是一种基于广义生日问题#xff08;Generalized Birthday Problem#xff09;的内存密集型工作量证明#xff08;PoW#xff09;算法#xff0c;算法核心目标是抵抗 ASIC 专用挖矿设备#xff0c;让普通GPU/CPU更易参与挖矿#xff0c;同时保证安全…综述1.1 简介Equihash是一种基于广义生日问题Generalized Birthday Problem的内存密集型工作量证明PoW算法算法核心目标是抵抗 ASIC 专用挖矿设备让普通GPU/CPU更易参与挖矿同时保证安全性与效率。其最著名的应用是 Zcash主网参数 n200, k9也被 ZenCash、Horizen 等加密货币采用。1. 普通生日问题在一个房间里至少需要有多少人才能使得“至少有两个人生日相同”的概率大于50%通常通过计算“所有人生日都不同”的互补事件概率来求解。假设一年有365天忽略润年每个人的生日在365天中是等可能的生日之间相互独立计算过程设房间里有n个人则第1个人的任取一天都不会出现生日相同碰撞的情况所以不同的概率是1第2个人只有生日和第1个人生日不同时才能满足生日不同所以与之前人不同的概率是364/365第3个人要满足和前两个人都生日都不同才行所以与之前人不同的概率是363/365...第n个人与前n−1个人生日都不同的概率是(365-(n-1))/365所以所有人生日都不同的概率p(n)为image那么至少有两个人生日相同的概率 P(n)就是image著名结论当n23时image也就是说只需要23个人至少两人生日相同的概率就超过了50%。当n57时这个概率会超过99%。在密码学中的应用生日攻击在密码学中生日问题揭示了哈希函数碰撞的概率。假设一个哈希函数有N中可能的输出比如N2m那么只需要计算大约sqrt(N)次哈希就有相当大的概率找到两个不同的输入产生相同的输出即发生碰撞。2. 广义生日问题“至少需要有多少人才能使得‘至少有一组k个人生日相同’的概率超过50%”普通生日问题是广义生日问题在k2时的特例。例如k3时至少有三个人生日相同k4时至少有四个人生日相同。这个问题比普通生日问题复杂得多没有简单的闭合公式通常需要近似或者数值计算。解决广义生日问题的一个著名近似要使一组k个人共享同一个生日的概率超过50%大约需要的人数为image其中N是可能的天数例如365k是要求的人数还以N365为例k2普通生日问题image这与之前精确计算的23人非常接近。k3image这意味着大约需要82人才有超过50%的概率找到至少三个人生日相同。3. Equihash中广义生日问题在Equihash算法中涉及的广义生日问题可以归纳如下1由区块头数据通过Blake2b哈希生成长度为N的哈希串列表2在列表中找到2k个哈希串的异或结果为 0注意这里异或为0并不是表示2k个完全相同的哈希串这里的异或为零是更宽松的组合约束3最终解为满足条件的2k个哈希值的索引组合索引互不相同且最终需转换为字节流作为区块的 nSolution 字段。1.2 算法及数据结构tromp给出equihash算法工程实现https://github.com/tromp/equihash1. 关键参数在Zcash中使用的参数N200K9这意味着NWidth产生的哈希值总宽度为200bits50字节KSteps算法分为9轮实际上是K步碰撞对应算法输出的29个索引HEADERNONCELEN140字节Blake2b哈希函数的输入数据长度通常由Block Header区块头 Nonce随机数组成。在Zcash中这个总长度通常固定为140字节NDIGITK110在算法实现中会将N位哈希输出切分成10个小块Digit分轮逐层解决DIGITBITSN/NDIGITS200/1020bits每个Digit的位宽也就是每一轮碰撞的长度LPROOFSIZE1K512解包含的索引数量即最终需要提交这512个索引作为工作量证明BASE1DIGITBITS2201048576碰撞空间大小因为每一轮要检查20bits的碰撞那么就有220种可能的数据可以把该值想象成有1048576个“理论上的抽屉”后续需要把初始哈希串放入这些抽屉里NHASHES2*BASE2097152200百万算法第一步生成的初始哈希串总数如果只生成 BASE个数据那么平均每个抽屉里只有1个数据这时无法和其他串发生碰撞找不到配对算法就无法继续为了保证每一轮都能顺利进行需要让每个“理论抽屉”里平均至少有2个数据HASHESPERBLAKE512/N2标准Blake2b输出是512bitsequihash算法中需要的是200bits的哈希串所以512bits可以切出2个200bits哈希串剩下的112位被丢弃HASHOUTHASHESPERBLAKE*N/850字节Blake2b算法输出50字节即可2x200bits在Tromp的Equihash工程实现中引入了Bucket桶和Slot槽两个用于管理内存和数据的关键概念在Equihash算法中有几百万个数据需要处理如果把它们放在一个大数组里排序速度太慢所以要使用“分治法”。Bucket (桶) —— 数据的“大分组”定义Bucket 是内存中的一块逻辑区域用于存放具有相同前缀Prefix的哈希串。决定因素BUCKBITS如果 BUCKBITS 10说明有210 1024个桶。数据的前10位决定了它去哪个桶。物理形态在 C 代码中Bucket 通常不是一个复杂的 class而仅仅是计算出的内存偏移量 (Offset)。Bucket_0 的内存地址 起始地址 0Bucket_1 的内存地址 起始地址 (每个桶的大小)作用减少碰撞搜索范围。数据一旦进入不同的桶它们在当前轮次绝对不可能碰撞所以后续计算完全不需要考虑跨桶的情况这对 CPU 缓存非常友好。Slot (槽) —— 数据的“具体容器”定义Slot是Bucket内部的一个最小存储单元。决定因素SLOTBITS如果SLOTBITS 12说明每个桶最多能容纳212 4096个数据Slot。存储内容Slot里不存完整的哈希值浪费空间只存必要的压缩信息1索引 (Index)这组数据最初是来自哪个或哪些原始输入。2剩余位 (Rest Bits)除去桶编号前缀后剩下的哈希位。固定大小 (Flat Memory)在Tromp的代码中并没有使用链表Linked List来动态增加 Slot因为指针跳转太慢。他预先分配了固定大小的内存总内存 桶数量 × 每个桶的Slot数量 × Slot大小。风险如果运气不好某个哈希前缀出现太多次导致对应桶的数据超过了 Slot 的上限就会发生溢出 (Overflow)这部分多余的数据通常会被丢弃为了性能牺牲一点点求解概率。结合以上内容给出和桶和槽相关参数RESTBITS10对于20位的Digit来说前10位用于确定它属于哪个Bucket则还有10位是剩余的数据位BUCKBITSDIGITBITS-RESTBITS10210是桶的总数Digit前10位确定“桶号”SLOTBITSRESTBITS1112这个参数定义了一个桶最多能装多少个数据Slot总数据量是NHASHES2x220桶的总数是210则平均每个桶会分到2x220/2102112048个数据11正好对应RESTBITS1而定义中的第2个1是除于安全冗余考虑由于哈希分布是随机的有的桶数据少有的桶数据多。为了防止数据多的桶溢出Overflow这里多给了1位空间即容量翻倍允许一个桶最多装212 4096个数据。2. Wagner算法Equihash要求找到2K个不同的输入xi使得H(x1) XOR H(x2) XOR ... XOR H(x2^k) 0例如在K9时需要有512个不同索引的哈希XOR 0。此时直接暴力找512个XOR0的组合不现实因此引入了Wagners algorithm。Wagner的思路非常简单但很强大把“求2K个数XOR0”转换成K轮“两两XOR消除部分前缀”的逐层合并。首先对备选哈希数据按前缀不同进行分桶每个桶中都是有相同前缀的哈希数据相当于抹掉部分哈希前缀位之后流程结构如下image最终XOR被零掉的bit (k1) × N/(k1) N ⇒ 全部 XOR 为 0。在Wagner算法中每轮处理主要做以下操作1依次处理每个桶桶内为以消除部分相同前缀的哈希串2进一步查找桶内具有特定位相同前缀的哈希对能产生碰撞的两个哈希3将碰撞哈希对进行异或产生新的哈希数据会消除相同前缀同时将之前桶号及索引桶内位置进行数据组合最后进行解回溯时使用4根据异或哈希数据按特定位前缀再次进行分桶前缀相同分入到相同桶再上述过程中查找碰撞对儿其实就是在搜索前缀相同的哈希保证之后的异或操作会消除相应的bit而之后根据哈希前缀进行分桶也是类似也是保证在同一个桶内的哈希都是前缀相同的便于在进行多线程处理时都是在同一桶内进行的。2 源码解析2.1 内存结构1. 关键宏定义首先看如下宏定义复制代码#if RESTBITS 8// cant save much memory in such small buckets#define SAVEMEM 1#else// an expected size of at least 512 has such relatively small// standard deviation that we can reduce capacity with negligible discarding// this value reduces (200,9) memory to under 144MB// must be under sqrt(2)/2 with -DCANTOR#define SAVEMEM 9/14 // 容量缩减因子#endif // RESTBITS 4#endif // ifndef SAVEMEMstatic const u32 NBUCKETS 1BUCKBITS; // number of bucketsstatic const u32 BUCKMASK NBUCKETS-1; // corresponding bucket maskstatic const u32 SLOTRANGE 1SLOTBITS; // default bucket capacitystatic const u32 SLOTMASK SLOTRANGE-1; // corresponding SLOTBITS maskstatic const u32 SLOTMSB 1(SLOTBITS-1); // most significat bit in SLOTMASKstatic const u32 NSLOTS SLOTRANGE * SAVEMEM; // number of slots per bucketstatic const u32 NRESTS 1RESTBITS; // number of possible values of RESTBITS bitsstatic const u32 MAXSOLS 8; // more than 8 solutions are rare复制代码SAVEMEM定义内存容量缩减因子根据桶内数据密度在保证求解率的前提下减少每个桶的槽位Slot数量从而降低整体内存占用。默认的SLOTRANGE (2124096) 包含了大量的冗余空间。当RESTBITS足够大8时意味着每个桶的元素足够多可以安全地将容量从默认的SLOTRANGE缩减到9/14以节省内存。2. 存储结构体定义复制代码// each bucket slot occupies a variable number of hash/tree units,// all but the last of which hold the xor over all leaf hashes,// or whats left of it after stripping the initial i*n 0s// the last unit holds the tree node itself// the hash is sometimes accessed 32 bits at a time (word)// and sometimes 8 bits at a time (bytes)union htunit {tree tag;tree_t word;uchar bytes[sizeof(tree_t)];};#define WORDS(bits) ((bits TREEBITS-1) / TREEBITS)#define HASHWORDS0 WORDS(WN - DIGITBITS RESTBITS)#define HASHWORDS1 WORDS(WN - 2*DIGITBITS RESTBITS)// A slot is up to HASHWORDS0 hash units followed by a tagtypedef htunit slot0[HASHWORDS01];typedef htunit slot1[HASHWORDS11];// a bucket is NSLOTS treenodestypedef slot0 bucket0[NSLOTS];typedef slot1 bucket1[NSLOTS];// the N-bit hash consists of K1 n-bit digits// each of which corresponds to a layer of NBUCKETS bucketstypedef bucket0 digit0[NBUCKETS];typedef bucket1 digit1[NBUCKETS];typedef au32 bsizes[NBUCKETS];复制代码1htunit类型htunit联合体类型是Equihash求解器中存储数据的最小通用单元联合体的特性是它内部的所有成员共享一块内存空间这意味着tag、word和bytes都是对同一32/64位内存的不同解释。image引入联合体的目的提高代码的灵活性和性能。当进行复杂的位操作时使用 word当处理索引时使用tag当进行底层内存操作时使用 bytes。2槽定义Slot是存储一个碰撞数据项的容器它是一个定长数组用于存储哈希数据和树节点信息。typedef htunit slot0[HASHWORDS0 1];大小HASHWORDS0 1个htunit位数WN - DIGITBITS RESTBITS 200 - 20 10 190则HASHWORDS0值为6个WORDS再1最终为7个WORDS。用途用于第0轮的输出即digit0输出的存储结构。结构数组的前HASHWORDS0个单元存储压缩后的哈希数据最后一个单元1存储该数据项的树节点tag。即slot0对应的类型为大小为7个htunit的数组。typedef htunit slot1[HASHWORDS1 1];大小HASHWORDS1 1 个 htunit位数WN - 2*DIGITBITS RESTBITS 200 - 2*20 10 170则HASHWORDS1值也为6个WORDS再1最终也为7个WORDS。用途用于第1轮的输出即digit1输出的存储结构。压缩由于HASHWORDS1 HASHWORDS0因为第1轮又消除了20位slot1通常比slot0更小从而可能会节省些许内存在N200情况下这两个值是相同的。在后续的乒乓操作中会复用这两个内存结构。3桶定义桶是相同类型槽的集合。typedef slot0 bucket0[NSLOTS];保存slot0类型数据的数组型桶结构它是包含NSLOTS2633个slot0类型数据的定长数组。typedef slot1 bucket1[NSLOTS];保存slot1类型数据的数组型桶结构它是包含NSLOTS2633个slot1类型数据的定长数组。4内存堆定义digit结构定义了整个内存堆对应于乒乓机制的中一个“球台”。typedef bucket0 digit0[NBUCKETS];用于存储初始轮次数据的内存堆结构通常是乒乓机制中的heap0它由NBUCKETS1024个bucket0组成其中每个桶都使用slot0存储数据。typedef bucket1 digit1[NBUCKETS];用于存储后续轮次数据的内存堆结构通常是乒乓机制中的heap1它由NBUCKETS1024个bucket1组成其中每个桶都使用slot1存储数据。5辅助结构typedef au32 bsizes[NBUCKETS];含义桶大小数组Bucket Sizes。用途au32通常是原子32位无符号整数。这个数组用于在多线程环境中安全地追踪每个桶当前实际存储了多少个数据项。这是多线程无锁写入的关键每个线程写入数据后原子性地增加对应桶的计数器。3. 内存分配在进行碰撞检测前首先进行必要的内存分配主要内容如下复制代码void alloctrees() {static_assert(2*DIGITBITS TREEBITS, needed to ensure hashes shorten by 1 unit every 2 digits);heap0 (bucket0 *)alloc(NBUCKETS, sizeof(bucket0));heap1 (bucket1 *)alloc(NBUCKETS, sizeof(bucket1));}equi(const u32 n_threads) {static_assert(sizeof(htunit) sizeof(tree_t), );static_assert(WK1, K assumed odd in candidate() calling indices1());nthreads n_threads;//const int err pthread_barrier_init(barry, NULL, nthreads);//assert(!err);hta.alloctrees();nslots (bsizes *)hta.alloc(2 * NBUCKETS, sizeof(au32));sols (proof *)hta.alloc(MAXSOLS, sizeof(proof));}复制代码