`
lobin
  • 浏览: 115494 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论
阅读更多

Dagger: A Memory-Hard to Compute, Memory-Easy to Verify Scrypt Alternative

Over the past five years of experience with Bitcoin and alternative cryptocurrencies, one important property for proof of work functions that has been discovered is that of "memory-hardness" - computing a valid proof of work should require not only a large number of computations, but also a large amount of memory. Currently, two major categories of memory-hard functions, scrypt and Primecoin mining, exist, but both are imperfect; neither require nearly as much memory as an ideal memory-hard function could require, and both suffer from time-memory tradeoff attacks, where the function can be computed with significantly less memory than intended at the cost of sacrificing some computational efficiency. This paper presents Dagger, a memory-hard proof of work based on moderately connected directed acyclic graphs (DAGs, hence the name), which, while far from optimal, has much stronger memory-hardness properties than anything else in use today.

Why Be Memory-Hard?

The main reason why memory hardness is important is to make the proof of work function resistant to specialized hardware. With Bitcoin, whose mining algorithm requires only a simple SHA256 computation, companies have already existed for over a year that create specialized "application-specific integrated circuits" (ASICs) designed and configured in silicon for the sole purpose of computing billions of SHA256 hashes in an attempt to "mine" a valid Bitcoin block. These chips have no legitimate applications outside of Bitcoin mining and password cracking, and the presence of these chips, which are thousands of times more efficient per dollar and kilowatt hour at computing hashes than generic CPUs, makes it impossible for ordinary users with generic CPU and GPU hardware to compete. This dominance of specialized hardware has several detrimental effects:
  1. It negates the democratic distribution aspect of cryptocurrency mining. In a generic hardware-dominated ecosystem, the fact that everyone has a computer guarantees that everyone will have an equal opportunity to earn at least some of the initial money supply. With specialized hardware, this factor does not exist; each economic actor's mining potential is linear (in fact, slightly superlinear) in their quantity of pre-existing capital, potentially exacerbating existing wealth inequalities.
  2. It increases resource waste. In an efficient market, marginal revenue approaches marginal cost. Since mining revenue is a linear function of money spent on mining hardware and electricity, this also implies that total revenue approaches total cost. Hence, in a specialized hardware dominated ecosystem, the quantity of resources wasted is close to 100% of the security level of the network. In a CPU and GPU-dominated ecosystem, because everyone already has a computer, people do not need to buy specialized hardware for the first few hashes per second worth of mining power. Hence, revenue is sublinear in cost - everyone gets a bit of revenue "for free". This implies that the quantity of resources wasted by the network is potentially considerably lower than its security parameter.
  3. It centralizes mining in the hands of a few actors (ie. ASIC manufacturers), making 51% attacks much more likely and potentially opening the network up to regulatory pressure.
Specialized hardware is so powerful because it includes many thousands of circuits specifically designed for computing the proof of work function, allowing the hardware to compute the function thousands of times in parallel. Memory hardness alleviates this problem by making the main limiting factor not CPU power, but memory. One can also make a modest improvement by targeting CPU clock speed, but the extent to which such optimizations can be made is fundamentally limited to a very low value by technological considerations. Thus, improvement through parallelization hits a roadblock: running ten memory-hard computations in parallel requires ten times as much memory. Specialized hardware menufacturers can certainly pack terabytes of memory into their devices, but the effect of this is mitigated by two factors. First, hobbyists can achieve the same effect by simply buying many off-the-shelf memory cards. Second, memory is much more expensive to produce (if measured in laptop equivalents) than SHA256 hashing chips; the RAM used in ordinary computers is already essentially optimal.

Algorithm specification:

Essentially, the Dagger algorithm works by creating a directed acyclic graph (the technical term for a tree where each node is allowed to have multiple parents) with ten levels including the root and a total of 225 - 1 values. In levels 1 through 8, the value of each node depends on three nodes in the level above it, and the number of nodes in each level is eight times larger than in the previous. In level 9, the value of each node depends on 16 of its parents, and the level is only twice as large as the previous; the purpose of this is to make the natural time-memory tradeoff attack be artificially costly to implement at the first level, so that it would not be a viable strategy to implement any time-memory tradeoff optimizations at all. Finally, the algorithm uses the underlying data, combined with a nonce, to pseudorandomly select eight bottom-level nodes in the graph, and computes the hash of all of these nodes put together. If the miner finds a nonce such that this resulting hash is below 2256 divided by the difficulty parameter, the result is a valid proof of work. Let D be the underlying data (eg. in Bitcoin's case the block header), N be the nonce and || be the string concatenation operator (ie. 'foo' || 'bar' == 'foobar') . The entire code for the algorithm is as follows: spread(L) = 16 if L == 9 else 3 node(D,xn,0,0) = D node(D,xn,L,i) = with m = spread(L) p[k] = sha256(D || xn || L || i || k) mod 8^(L-1) for k in [0...m-1] sha256(node(L-1,p[0]) || node(L-1,p[1]) ... || node(L-1,p[m-1])) eval(D,N) = with xn = floor(n / 2^26) p[k] = sha256(D || xn || i || k) mod 8^8 * 2 for k in [0...3] sha256(node(D,xn,9,p[0]) || node(D,xn,9,p[1]) ... || node(D,xn,9,p[3])) Objective: find k such that eval(D,k) < 2^256 / diff

Properties:

  1. With 225 memory (ie. 512 MB, since each memory unit is a 32-byte hash), the optimal algorithm is to pre-compute the 224 leaf nodes run eval with all 225 possibilities. The main computational difficulty is computing SHA256 hashes. Each node in levels 1 - 8 will take two hashes, so the levels will take up 2^25 - 4 hashes in total (not -2 since the root node requires no hash). Each node in level 9 takes 16 hashes, adding 228 hashes, and then each nonce will take 8 hashes, adding 228 hashes once again. Thus, running through 226 nonces will take 229 + 225 - 4 hashes altogether.
  2. One potential problem is lazy evaluation; parts of the tree can be evaluated only as needed in order to reduce the number of hashes required. However, because a (pseudo-) random node out of 225 is taken 228 times, we can statistically estimate that each node has a 1 / e8 change of remaining unused - only about 0.03%. Hence, the benefit from lazy evaluation is insubstantial.
  3. It is possible to run the algorithm with very little memory, but one must re-compute the eight bottom leaf nodes that the proof of work result on each nonce depends on each time. Naively doing an exponential calculation, we get that 38 * 16, or 104976, steps are required to compute a single nonce. In practice, many values are reused, so only an average of almost exactly 6000 hashes is needed, but this is still a very large amount - the memory-based algorithm manages a mere 8 computations per nonce, giving low-memory hardware a 750x penalty.
  4. Verification requires computing one nonce without pre-computation, so it also takes 6000 hashes and about 160 KB of memory.
  5. Because each node in the last level has 16 parents instead of 3, the time-memory tradeoff attack is severely weakened - attempting to store 8 levels instead of 9 reduces memory usage by a factor of 2 but slows down computation by a factor of 16. Thus, no practical time-memory tradeoff attack exists; close to the full 512 MB is required for any reasonable level of efficiency.

Conclusion

This algorithm provides a proof of work mining function with memory hardness properties that are not ideal, but that are nevertheless a massive improvement over anything available previously. It takes 512 MB to evaluate, 112 KB memory and 4078 hashes to verify, and even the tinest time-memory tradeoff is not worthwhile to implement because of the bottom-level branching adjustment. These parameters allow Dagger to be much more daring in its memory requirements than Primecoin or scrypt, asking for 512 MB of RAM for a single thread. Because the primary determinant of hardness is memory, and not computation, specialized hardware has only a tiny advantage; even an optimal Dagger mining ASIC would have little to offer over a hobbyist purchasing hundreds of gigabytes of memory cards off the shelf and plugging them into a medium-power GPU. And even in such an equilibrium, mining with ordinary CPUs will likely continue to be practical.

Appendix: Why 6000 hashes?

To compute the required four values in level 9, one must look at 64 randomly selected values in level 8. With negligibly less than 100% probability, these values will all be different. From there, suppose that you have computed V[n] different values for level n. You will need to make an expected 3 * V[n]queries to level n-1. Because the queries are pseudorandom, after these queries the probability that any individual cell will remain empty is (1 - (1/8^n)) ^ (3 * V[n]). Hence, we can estimate that the expected value of V[n-1], the number of cells that will not be empty (ie. will need to be computed) is close to8^n - 8^n * (1 - (1/8^n)) ^ (3 * V[n]). We thus have a recursive computation: V[8] = 64 V[7] = 8^7 - 8^7 * (1 - 1/8^7) ^ (64 * 3) = 191.99 V[6] = 8^6 - 8^6 * (1 - 1/8^6) ^ (191.99 * 3) = 575.34 V[5] = 8^5 - 8^5 * (1 - 1/8^5) ^ (575.34 * 3) = 1681.38 V[4] = 8^4 - 8^4 * (1 - 1/8^4) ^ (1681.38 * 3) = 2900.72 V[3] = 8^3 - 8^3 * (1 - 1/8^3) ^ (2900.72 * 3) = 512.00 V[2] = 8^2 - 8^2 * (1 - 1/8^2) ^ (512.00 * 3) = 64.00 V[1] = 8^1 - 8^1 * (1 - 1/8^1) ^ (64.00 * 3) = 8.00 V[0] = 8^0 - 8^0 * (1 - 1/8^0) ^ (8.00 * 3) = 1.00 V[0] + V[1] + ... + V[8] = 5998.43 This computation is not quite accurate, since EV(f(x) is not the same as f(EV(x)) (EV = expected value) if f is not linear, as is the case here, but because we are not dealing with especially fat-tailed or skewed distributions the standard deviations are sufficiently low for this inaccuracy to have no substantial effect.

Acknowledgements

  • Thanks to Adam Back and Charles Hoskinson, for discussion and critique of earlier drafts of the protocol
  • See also: Fabien Coelho's paper, in which Fabien Coelho had independently discovered a similar algorithm in 2005.
  1、http://www.hashcash.org/papers/dagger.html 2、https://github.com/ethereum/wiki/wiki/Dagger-Hashimoto  
0
0
分享到:
评论
相关资源推荐
  • DI框架Dagger2系统性学习 目录 Home User’s Guide Android Multibinding Sets and Maps Subcomponents Producers Testing Project Pages 到底部HomeDagger是一个完全静态的编译时的Java和Android依赖注入矿建。它由Square发布的早期版本改造而来现在由Google维护
  • https://blog.csdn.net/Metal1/article/details/79996945 源代码:https://www.cnblogs.com/Evsward/p/ethash.html本文具体分析以太坊的共识算法之一:实现了POW的以太坊共识引擎ethash。关键字:ethash,共识算法,pow,Dagger Hashimoto,ASIC,struct{},nonce,FNV hash,位运算,epochEthash前面我们分析了以太坊挖矿的源码,挖了一个共识引擎的坑,研究了DA...
  • https://blog.csdn.net/F2004/article/details/45842287
  • scrypt基于密码的密钥派生函数(译) 原文地址:http://rossihwang.farbox.com/post/2014-03-25原文请参考The scrypt Password-Based Key Derivation Function[连接]1.导言在密码学中,基于密码的“密钥派生函数”(key derivation functions)被用于从一个密值(secret value)中派生出一个或多个秘钥。多年来,多种基于密码...
  • Dagger2学习笔记 Dagger需要注入依赖的地方,需要@Inject的注解,共有三种inject方式:Identifies injectable constructors, methods, and fields.  constructors首先被注入,然后是method和field,父类中的method和field会先于子类中的method和field注入,同一个类中的fields和methods注入注入不
  • https://download.csdn.net/download/lin_xiqun/10408972 xdag钱包(mac版) Dagger is part of a new wave of Distributed Ledger projects based on a DAG infrastructure. DAG, or Directed acyclic graph, is an alternative method for sending data amongst people within a distributed, decentralized environment. This is done without a blockchain, allowing for greater scalability.
  • Dagger2 彻底了解如何构建依赖关系 Dagger2 彻底了解如何构建依赖关系上两篇文章分别介绍了Dagger2的使用方式及其一些细节上的知识补充,如果没有看过的,请传送: Dagger2 这次入门就不用放弃了 Dagger2 使用正确姿势 这两篇文章知识讲解了如何使用Dagger2的方式,知其然不知其所以然,这篇文章就基于上两篇文章的例子来介绍一下Dagger2通过APT生成的代码,深入了解一下。它是如何工作的,如何注入成员变量的。本
  • Dagger2使用介绍(下篇) Dagger2官网:http://google.github.io/dagger/ Githup地址:https://github.com/google/dagger 今天,介绍Dagger2的第二种使用方式,相比上次介绍的第一种使用方式的话,会更加适用于Android工程。 使用介绍 第一步、下载jar包;配置如下: dependencies { compile 'com
  • 【Android】——单元测试、JUnit4、Mockito、Dagger2等
  • Android 低端手机使用SCrypt算法过慢之解决方法 Android 低端手机使用SCrypt算法过慢之解决方法 问题描述: 最近在做BTC钱包项目,其中会用到一个SCrypt的加密方法,but在高端机上面 运行速度还算可以,但是在低端机手机上简直不能忍,十几分钟过去了 还在算。所以得用C的代码去运行这个方法。 百度之后大部分是用编译器把C代码打成so包放进去,但是觉得这样很麻烦,而且跨Module之后需要引用 就很麻烦,不如直接把依赖中的S...
  • scrypt算法的前世今生(从零开始学区块链 192) 当我们谈论某某币使用某算法时,大部分是指其使用的hash算法,hash算法在工作量证明中是核心算法,工作量证明是维护公链免于中心化倾向的重要保证,今天介绍一下scrypt这种内存依赖型hash算法hash算法想必大家都不陌生,以前的文章有介绍,也称为散列算法,是信息技术领域非常基础也非常重要的技术。它能将任意长度的二进制值(明文)映射为较短的固定长度的二进制值(Hash 值),并且不同的明文很难映
  • Scrypt算法 看了一圈觉得还是WikiPedia的比较通俗靠谱: Overview The large memory requirements of scrypt come from a large vector of pseudorandom bit strings that are generated as part of the algorithm. Once the vector is genera...
  • 区块链都用哪几种算法?什么是Scrypt算法 区块链爱好者(QQ:53016353) Scrypt是由著名的FreeBSD黑客 Colin Percival为他的备份服务 Tarsnap开发的。 Scrypt不仅计算所需时间长,而且占用的内存也多,使得并行计算多个摘要异常困难,因此利用rainbow table进行暴力攻击更加困难。Scrypt没有在生产环境中大规模应用,并且缺乏仔细的审察和广泛的函数库支持。但是,Scrypt
  • Dagger2基础的使用 前言                Dagger2的介绍和配置        Dagger2基础的使用        Dagger2进阶-编译生成源码解读        Dagger2进阶-范围的控制(Scope和Singleton)        Dagger2进阶-Scope的源码探究        项目源代码传送门    这篇文章主要说关于Dagger的应用基础。基础的注解解释    Dag...
  • https://blog.csdn.net/wnma3mz/article/details/77366246
  • https://blog.csdn.net/iteye_13976/article/details/82443197 最近由于项目需要开始使用Drools规则引擎,花了一天时间将Drools看了个大概,整体感觉还是非常好用的。不过在使用的过程中出现了各种问题,现将遇到的一些问题及解决方法记录如下: 1.在Myeclipse中运行时,没有任何错误,当一旦打包为runnable jar file后执行,报错如下: [27,7]: [ERR 101] Line 27:7 no viable alternative ...
  • 从hash算法到scrypt算法的不可逆加密算法 本篇博客主要对从hash算法到scrypt算法的不可逆的加密算法分别进行介绍。
  • 莱特币挖矿算法Scrypt详解 Scrypt算法简介 莱特币采用的挖矿算法是Scrypt算法。第一个使用Scrypt算法的数字货币是Tenebrix,而后该算法被莱特币使用。莱特币创始人在莱特币创世帖中介绍了莱特币采用的共识机制,挖矿算法,发行总量,挖矿难度等相关重要信息。该帖中,李启威说明了莱特币所使用的挖矿算法为数字货币Tenebrix所使用的Scrypt算法,这也是一种符合PoW共识机制的算法。Scrypt算法过程中也需
  • https://blog.csdn.net/vloong/article/details/79947625 Ethash前面我们分析了以太坊挖矿的源码,挖了一个共识引擎的坑,研究了DAG有向无环图的算法,这些都是本文要研究的Ethash的基础。Ethash是目前以太坊基于POW工作量证明的一个共识引擎(也叫挖矿算法)。它的前身是Dagger Hashimoto算法。Dagger Hashimoto作为以太坊挖矿算法Ethash的前身,Dagger Hashimoto的目的是:抵制矿机(ASIC,专门用于...
  • 可能是东半球最好的dagger2文章 部分内容参考自: [Android]使用Dagger 2依赖注入 - DI介绍(翻译) [Android]使用Dagger 2依赖注入 - API(翻译) 为什么网上这么多dagger2教程,我还写了这篇文章。 找了很多Dagger2相关的博客,我看的脑浆炸裂……Dagger2给我们带来了什么,大多数博文也没有说明手动写写,加深印象,骗骗粉丝 (手动滑稽)部分Dagger2的运作机
Global site tag (gtag.js) - Google Analytics