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

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

 
阅读更多

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
分享到:
评论

相关推荐

    dagger-compiler-2.15.jar 等关于dagger2的jar包

    dagger-compiler-2.15.jar dagger-2.15.jar javax.inject-1.jar guava-19.0.jar 等关于dagger2的jar包 附上讲解 https://blog.csdn.net/piglite/article/details/47859389

    NetEase-Dagger-v1.3-5-g4f9408f.zip

    标题"NetEase-Dagger-v1.3-5-g4f9408f.zip"中,"NetEase"是网易公司的标识,表明这可能与网易公司有关的一个项目或产品。"Dagger"是Android开发中常用的依赖注入框架,它允许开发者在代码中自动管理对象的生命周期和...

    Fratantonio-Cloak-And-Dagger-From-Two-Permissions-To-Complete-Co

    标题"Fratantonio-Cloak-And-Dagger-From-Two-Permissions-To-Complete-Co"提到了一个安全漏洞,这是关于Android系统中的“Cloak and Dagger”攻击技术。Cloak and Dagger是一种高度隐蔽的恶意软件攻击手段,由研究...

    Android代码-Dagger2-MVP-Sample

    Example Dagger 2 using MVP pattern to show how to use this library and pattern in our android applications. Inspired in googlesamples / android-topeka Do you want to learn Dagger2 ? MarioKart Kata for...

    android-hilt:Dagger Hilt的扩展

    Dagger Hilt的扩展扩展名 Kotlindependencies { implementation( " com.google.dagger:hilt-android:2.32-alpha " ) implementation( " it.czerwinski.android.hilt:hilt-extensions:[VERSION] " ) kapt( " it....

    Fratantonio-Cloak-And-Dagger-From-Two-Permissions-To-Complete-C

    【Fratantonio-Cloak-And-Dagger-From-Two-Permissions-To-Complete-Control-Of-The-UI-Feedback-Loop】 这篇论文是关于移动安全领域的一个重要研究,由Yanick Fratantonio与其他研究人员合作完成,并在2017年的...

    Fratantonio-Cloak-And-Dagger-From-Two-Permissions-To-Complete

    【Fratantonio-Cloak-And-Dagger-From-Two-Permissions-To-Complete】这篇文档探讨了Android操作系统中一个严重的安全问题,该问题源于两个特定权限:SYSTEM ALERT WINDOW和BIND ACCESSIBILITY SERVICE。作者Yanick ...

    Dagger--A fast dependency injector for Android and Java

    Dagger是一种为Android和Java平台设计的快速依赖注入框架。依赖注入(Dependency Injection,简称DI)是一种编程技术,它允许开发者实现控制反转(Inversion of Control,简称IoC),从而将应用程序中的组件(通常是...

    Python库 | python_dagger-0.0.3-py3-none-any.whl

    python库。 资源全名:python_dagger-0.0.3-py3-none-any.whl

    news-apps:带有MVVM-Retrofit和Moshi-Dagger Hilt-ROOM-Coroutines的新闻应用程序

    news-apps:带有MVVM-Retrofit和Moshi-Dagger Hilt-ROOM-Coroutines的新闻应用程序

    Android代码-dagger-intellij-plugin

    Dagger can provide a class objects without needing to know how they are constructed. The Dagger IntelliJ plugin helps demystify this behavior and creates visual connections between a @Inject object ...

    dagger-index:匕首

    匕首索引从 code.google.com/p/dagger-index 自动导出DAGGER:动态图的可达性指数该软件是论文中提出的方法的C++实现: Hilmi Yildirim、Vineet Chaoji 和 Mohammed J. Zaki:“ DAGGER:大型动态图中可达性查询的可...

    Dagger2:Kotlin Dagger2示例项目

    Google Dagger 2(演示) ... kapt ' com.google.dagger:dagger-compiler:2.9 ' } 您可以使用库或工具。 RxJava2,RxAndroid2 改造,OkHttp,OkHttp日志记录 格森 匕首2 测试框架 朱尼特 莫基托 哈科科(测试范围)

    Dagger:Android 和 Java 的快速依赖注入框架(0积分下载)

    Dagger 是一个由 Google 开发的依赖注入库,专门用于 Android 和 Java 应用程序,以其快速和高效著称。 Dagger 简介 Dagger 是一个静态的 Java 注入框架,它使用代码生成技术来创建依赖关系图,并且可以在编译时...

    domeafavor-android:爱彼迎 - Android

    【标题】"domeafavor-android: 爱彼迎 - Android" 指的是一个开源项目,它可能是一个仿造或扩展Airbnb应用程序的Android平台实现。Airbnb是一款知名的在线住宿预订和旅游服务平台,而 "domeafavor-android" 可能是...

    test-dagger2-for-simple:dagger2测试

    **Dagger 2 是一个流行的依赖注入框架,广泛应用于 Android 和 Java 开发中。这个“test-dagger2-for-simple”项目旨在提供一个简单的示例,帮助开发者了解如何在实际项目中使用 Dagger 2。** 在Java开发中,依赖...

    android_dagger_example:如何在 Android 中使用依赖注入(使用 Dagger)的快速示例

    匕首示例如何在 android 应用程序中使用依赖注入的快速示例。 将 gradle 依赖项添加到 app/build.gradle: dependencies { compile fileTree(dir: ...dagger:1.2.1' provided 'com.squareup.dagger:dagger-compiler:

    KingsCrossApp:使用 RxJava、Retrofit、Dagger 和 SnappyDB 的沙盒应用

    本文档正在建设中国王十字应用程序...使用Dagger进行依赖注入和SnappyDB进行NoSQL持久化 - 'com.etsy.android.grid:library:1.0.5'- 'com.squareup.picasso:picasso:2.3.4'- 'com.squareup.retrofit:retrofit:1.8.0'- '...

    android-devlauncher

    Android模板 Gradle插件(旧) androidx.navigation:navigation-safe-args-gradle-plugin: ://maven.google....com.google.dagger:hilt-android-gradle-

Global site tag (gtag.js) - Google Analytics