https://www.cryptolux.org/api.php?action=feedcontributions&user=Dmitry.khovratovich&feedformat=atomCryptoLUX - User contributions [en]2020-07-05T03:36:46ZUser contributionsMediaWiki 1.30.0https://www.cryptolux.org/index.php?title=Argon2&diff=2747Argon22017-05-17T15:35:02Z<p>Dmitry.khovratovich: /* Implementations */</p>
<hr />
<div>=Argon2= <br />
'''Argon2''' is a new hash function, which summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memory filling rate and effective use of multiple computing units, while still<br />
providing defense against tradeoff attacks. '''Argon2''' is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. <br />
<br />
==Modes==<br />
<br />
'''Argon2''' has one primary variant: '''Argon2id''', and two supplementary variants: '''Argon2d''' and<br />
Argon2i. '''Argon2d'''uses data-depending memory<br />
access, which makes it suitable for cryptocurrencies and<br />
proof-of-work applications with no threats from side-channel<br />
timing attacks. '''Argon2i'''uses data-independent memory access,<br />
which is preferred for password hashing and password-based key<br />
derivation. '''Argon2id'''works as '''Argon2i''' for the first half of the first iteration over the<br />
memory, and as '''Argon2d'''for the rest, thus providing both side-channel attack protection and <br />
brute-force cost savings due to time-memory tradeoffs. '''Argon2i'''makes more passes over the<br />
memory to protect from tradeoff attacks.<br />
<br />
==Winner of PHC==<br />
<br />
Argon2 (version 1.3) is the winner of the [http://password-hashing.net Password Hashing Competition].<br />
<br />
==Specification==<br />
<br />
[[Media:Argon2.pdf | Specification of Argon2 v 1.3 (24.03.2017)]]<br />
<br />
<br />
<br />
[https://tools.ietf.org/html/draft-irtf-cfrg-argon2-02 IRTF draft of Argon2]<br />
<br />
==Implementations==<br />
<br />
[https://github.com/P-H-C/phc-winner-argon2 Reference implementation in C89 (''PHC release'')]<br />
<br />
[https://github.com/P-H-C/phc-winner-argon2/blob/master/README.md Links to bindings in other languages]<br />
<br />
[https://github.com/khovratovich/Argon2 Original implementations in C99 and C++11]<br />
<br />
==Research==<br />
<br />
===Design===<br />
[http://eprint.iacr.org/2015/430.pdf A. Biryukov and D. Khovratovich "Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing"]. Introduces Argon2 and its fast-verification feature.<br />
<br />
[[Media:Argon2ESP.pdf | A. Biryukov, D. Dinu, and D. Khovratovich "Argon2, new generation of memory-hard functions for password hashing and other applications"]], Euro S&P 2016.<br />
<br />
[[Media:PHC-overview.pdf | A. Biryukov and D. Khovratovich "Design Rationality and Security Analysis of PHC Candidates: Overview"]]<br />
<br />
===Attacks===<br />
<br />
[http://eprint.iacr.org/2016/759.pdf J. Alwen and J. Blocki, "Towards Practical Attacks on Argon2i and Balloon Hashing"]<br />
<br />
[http://eprint.iacr.org/2016/115.pdf J. Alwen and J. Blocki "Efficiently Computing Data-Independent Memory-Hard Functions" (Crypto 2016)]<br />
<br />
[http://eprint.iacr.org/2015/227.pdf Research paper "Tradeoff cryptanalysis of memory-hard functions" (Asiacrypt 2015)], [[Media:Tradeoffs.pdf | Talk at PasswordsCon'14]], [[Media:Tradeoff-slides.pdf | extended version]], <br />
<br />
===Argon1 (deprecated)===<br />
[[Media:Argon-slides.pdf | Argon1 Presentation Slides]]<br />
<br />
[[Media:Argon-v1.pdf | Argon1 Reference Guide]]<br />
<br />
==Other resources==<br />
<br />
[http://argon2hash.nl/ Online hash generator]<br />
<br />
[https://github.com/xebia/argon2-go Go wrapper]<br />
<br />
[https://github.com/khovratovich/Argon Reference and optimized implementations of Argon1]<br />
<br />
=Egalitarian Computing=<br />
<br />
It is a new concept that to remedy the disparity between hardware-equipped attackers and legitimate security engineers one has to amalgamate computing for security with a memory-hard function.<br />
<br />
[[Media:Rwc-slides.pdf | "Argon2 and Egalitarian Computing" at Real World Cryptography 2016]] <br />
<br />
[[Media:Egalitarian-rump.pdf | Asiacrypt 2015 rump session slides]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Argon2&diff=2746Argon22017-05-17T15:32:33Z<p>Dmitry.khovratovich: </p>
<hr />
<div>=Argon2= <br />
'''Argon2''' is a new hash function, which summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memory filling rate and effective use of multiple computing units, while still<br />
providing defense against tradeoff attacks. '''Argon2''' is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. <br />
<br />
==Modes==<br />
<br />
'''Argon2''' has one primary variant: '''Argon2id''', and two supplementary variants: '''Argon2d''' and<br />
Argon2i. '''Argon2d'''uses data-depending memory<br />
access, which makes it suitable for cryptocurrencies and<br />
proof-of-work applications with no threats from side-channel<br />
timing attacks. '''Argon2i'''uses data-independent memory access,<br />
which is preferred for password hashing and password-based key<br />
derivation. '''Argon2id'''works as '''Argon2i''' for the first half of the first iteration over the<br />
memory, and as '''Argon2d'''for the rest, thus providing both side-channel attack protection and <br />
brute-force cost savings due to time-memory tradeoffs. '''Argon2i'''makes more passes over the<br />
memory to protect from tradeoff attacks.<br />
<br />
==Winner of PHC==<br />
<br />
Argon2 (version 1.3) is the winner of the [http://password-hashing.net Password Hashing Competition].<br />
<br />
==Specification==<br />
<br />
[[Media:Argon2.pdf | Specification of Argon2 v 1.3 (24.03.2017)]]<br />
<br />
<br />
<br />
[https://tools.ietf.org/html/draft-irtf-cfrg-argon2-02 IRTF draft of Argon2]<br />
<br />
==Implementations==<br />
<br />
[https://github.com/khovratovich/Argon2 Reference and optimized extended implementations in C99 and C++11]<br />
<br />
[https://github.com/P-H-C/phc-winner-argon2 Reference implementation in C89 (''PHC release'')]<br />
<br />
[https://github.com/bwesterb/argon2pure Python implementation]<br />
<br />
==Research==<br />
<br />
===Design===<br />
[http://eprint.iacr.org/2015/430.pdf A. Biryukov and D. Khovratovich "Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing"]. Introduces Argon2 and its fast-verification feature.<br />
<br />
[[Media:Argon2ESP.pdf | A. Biryukov, D. Dinu, and D. Khovratovich "Argon2, new generation of memory-hard functions for password hashing and other applications"]], Euro S&P 2016.<br />
<br />
[[Media:PHC-overview.pdf | A. Biryukov and D. Khovratovich "Design Rationality and Security Analysis of PHC Candidates: Overview"]]<br />
<br />
===Attacks===<br />
<br />
[http://eprint.iacr.org/2016/759.pdf J. Alwen and J. Blocki, "Towards Practical Attacks on Argon2i and Balloon Hashing"]<br />
<br />
[http://eprint.iacr.org/2016/115.pdf J. Alwen and J. Blocki "Efficiently Computing Data-Independent Memory-Hard Functions" (Crypto 2016)]<br />
<br />
[http://eprint.iacr.org/2015/227.pdf Research paper "Tradeoff cryptanalysis of memory-hard functions" (Asiacrypt 2015)], [[Media:Tradeoffs.pdf | Talk at PasswordsCon'14]], [[Media:Tradeoff-slides.pdf | extended version]], <br />
<br />
===Argon1 (deprecated)===<br />
[[Media:Argon-slides.pdf | Argon1 Presentation Slides]]<br />
<br />
[[Media:Argon-v1.pdf | Argon1 Reference Guide]]<br />
<br />
==Other resources==<br />
<br />
[http://argon2hash.nl/ Online hash generator]<br />
<br />
[https://github.com/xebia/argon2-go Go wrapper]<br />
<br />
[https://github.com/khovratovich/Argon Reference and optimized implementations of Argon1]<br />
<br />
=Egalitarian Computing=<br />
<br />
It is a new concept that to remedy the disparity between hardware-equipped attackers and legitimate security engineers one has to amalgamate computing for security with a memory-hard function.<br />
<br />
[[Media:Rwc-slides.pdf | "Argon2 and Egalitarian Computing" at Real World Cryptography 2016]] <br />
<br />
[[Media:Egalitarian-rump.pdf | Asiacrypt 2015 rump session slides]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Argon2&diff=2745Argon22017-05-17T14:59:49Z<p>Dmitry.khovratovich: /* Winner of PHC */</p>
<hr />
<div>=Argon2= <br />
'''Argon2''' is a new hash function, which summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memory filling rate and effective use of multiple computing units, while still<br />
providing defense against tradeoff attacks. '''Argon2''' is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. <br />
<br />
==Modes==<br />
<br />
'''Argon2''' has one primary variant: '''Argon2id''', and two supplementary variants: '''Argon2d''' and<br />
Argon2i. '''Argon2d'''uses data-depending memory<br />
access, which makes it suitable for cryptocurrencies and<br />
proof-of-work applications with no threats from side-channel<br />
timing attacks. '''Argon2i'''uses data-independent memory access,<br />
which is preferred for password hashing and password-based key<br />
derivation. '''Argon2id'''works as '''Argon2i''' for the first half of the first iteration over the<br />
memory, and as '''Argon2d'''for the rest, thus providing both side-channel attack protection and <br />
brute-force cost savings due to time-memory tradeoffs. '''Argon2i'''makes more passes over the<br />
memory to protect from tradeoff attacks.<br />
<br />
==Winner of PHC==<br />
<br />
Argon2 (version 1.3) is the winner of the [http://password-hashing.net Password Hashing Competition].<br />
<br />
==Specification==<br />
<br />
[[Media:Argon2.pdf | Specification of Argon2 v 1.3 (24.03.2017)]]<br />
<br />
[[Media:Argon2ESP.pdf | "Argon2, new generation of memory-hard functions for password hashing and other applications"]], Euro S&P 2016.<br />
<br />
[https://tools.ietf.org/html/draft-irtf-cfrg-argon2-02 IRTF draft of Argon2]<br />
<br />
==Implementations==<br />
<br />
[https://github.com/khovratovich/Argon2 Reference and optimized extended implementations in C99 and C++11]<br />
<br />
[https://github.com/P-H-C/phc-winner-argon2 Reference implementation in C89 (''PHC release'')]<br />
<br />
[https://github.com/bwesterb/argon2pure Python implementation]<br />
<br />
==Research==<br />
<br />
[http://eprint.iacr.org/2015/430.pdf Research paper "Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing"]. Introduces Argon2 and its fast-verification feature.<br />
<br />
[[Media:PHC-overview.pdf | Design Rationality and Security Analysis of PHC Candidates: Overview]]<br />
<br />
[http://eprint.iacr.org/2015/227.pdf Research paper "Tradeoff cryptanalysis of memory-hard functions" (Asiacrypt 2015)], [[Media:Tradeoffs.pdf | Talk at PasswordsCon'14]], [[Media:Tradeoff-slides.pdf | extended version]], <br />
<br />
[[Media:Argon-slides.pdf | Argon1 Presentation Slides]]<br />
<br />
[[Media:Argon-v1.pdf | Argon1 Reference Guide]]<br />
<br />
==Other resources==<br />
<br />
[http://argon2hash.nl/ Online hash generator]<br />
<br />
[https://github.com/xebia/argon2-go Go wrapper]<br />
<br />
[https://github.com/khovratovich/Argon Reference and optimized implementations of Argon1]<br />
<br />
=Egalitarian Computing=<br />
<br />
It is a new concept that to remedy the disparity between hardware-equipped attackers and legitimate security engineers one has to amalgamate computing for security with a memory-hard function.<br />
<br />
[[Media:Rwc-slides.pdf | "Argon2 and Egalitarian Computing" at Real World Cryptography 2016]] <br />
<br />
[[Media:Egalitarian-rump.pdf | Asiacrypt 2015 rump session slides]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Argon2&diff=2744Argon22017-05-17T14:59:29Z<p>Dmitry.khovratovich: /* Modes */</p>
<hr />
<div>=Argon2= <br />
'''Argon2''' is a new hash function, which summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memory filling rate and effective use of multiple computing units, while still<br />
providing defense against tradeoff attacks. '''Argon2''' is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. <br />
<br />
==Modes==<br />
<br />
'''Argon2''' has one primary variant: '''Argon2id''', and two supplementary variants: '''Argon2d''' and<br />
Argon2i. '''Argon2d'''uses data-depending memory<br />
access, which makes it suitable for cryptocurrencies and<br />
proof-of-work applications with no threats from side-channel<br />
timing attacks. '''Argon2i'''uses data-independent memory access,<br />
which is preferred for password hashing and password-based key<br />
derivation. '''Argon2id'''works as '''Argon2i''' for the first half of the first iteration over the<br />
memory, and as '''Argon2d'''for the rest, thus providing both side-channel attack protection and <br />
brute-force cost savings due to time-memory tradeoffs. '''Argon2i'''makes more passes over the<br />
memory to protect from tradeoff attacks.<br />
<br />
==Winner of PHC==<br />
<br />
Argon2 (version 1.3) is the winner of the [http://password-hashing.net Password Hashing Competition]. In addition to the PHC release, the Argon2 specification also defines two specific modes '''Argon2id''' and '''Argon2ds'''.<br />
<br />
==Specification==<br />
<br />
[[Media:Argon2.pdf | Specification of Argon2 v 1.3 (24.03.2017)]]<br />
<br />
[[Media:Argon2ESP.pdf | "Argon2, new generation of memory-hard functions for password hashing and other applications"]], Euro S&P 2016.<br />
<br />
[https://tools.ietf.org/html/draft-irtf-cfrg-argon2-02 IRTF draft of Argon2]<br />
<br />
==Implementations==<br />
<br />
[https://github.com/khovratovich/Argon2 Reference and optimized extended implementations in C99 and C++11]<br />
<br />
[https://github.com/P-H-C/phc-winner-argon2 Reference implementation in C89 (''PHC release'')]<br />
<br />
[https://github.com/bwesterb/argon2pure Python implementation]<br />
<br />
==Research==<br />
<br />
[http://eprint.iacr.org/2015/430.pdf Research paper "Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing"]. Introduces Argon2 and its fast-verification feature.<br />
<br />
[[Media:PHC-overview.pdf | Design Rationality and Security Analysis of PHC Candidates: Overview]]<br />
<br />
[http://eprint.iacr.org/2015/227.pdf Research paper "Tradeoff cryptanalysis of memory-hard functions" (Asiacrypt 2015)], [[Media:Tradeoffs.pdf | Talk at PasswordsCon'14]], [[Media:Tradeoff-slides.pdf | extended version]], <br />
<br />
[[Media:Argon-slides.pdf | Argon1 Presentation Slides]]<br />
<br />
[[Media:Argon-v1.pdf | Argon1 Reference Guide]]<br />
<br />
==Other resources==<br />
<br />
[http://argon2hash.nl/ Online hash generator]<br />
<br />
[https://github.com/xebia/argon2-go Go wrapper]<br />
<br />
[https://github.com/khovratovich/Argon Reference and optimized implementations of Argon1]<br />
<br />
=Egalitarian Computing=<br />
<br />
It is a new concept that to remedy the disparity between hardware-equipped attackers and legitimate security engineers one has to amalgamate computing for security with a memory-hard function.<br />
<br />
[[Media:Rwc-slides.pdf | "Argon2 and Egalitarian Computing" at Real World Cryptography 2016]] <br />
<br />
[[Media:Egalitarian-rump.pdf | Asiacrypt 2015 rump session slides]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Argon2&diff=2743Argon22017-05-17T14:59:17Z<p>Dmitry.khovratovich: /* Argon2 */</p>
<hr />
<div>=Argon2= <br />
'''Argon2''' is a new hash function, which summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memory filling rate and effective use of multiple computing units, while still<br />
providing defense against tradeoff attacks. '''Argon2''' is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. <br />
<br />
==Modes==<br />
<br />
'''Argon2''' has one primary variant: '''Argon2id''', and two supplementary variants: '''Argon2d''' and<br />
Argon2i. '''Argon2d'''uses data-depending memory<br />
access, which makes it suitable for cryptocurrencies and<br />
proof-of-work applications with no threats from side-channel<br />
timing attacks. '''Argon2i'''uses data-independent memory access,<br />
which is preferred for password hashing and password-based key<br />
derivation. '''Argon2id'''works as '''Argon2i''' for the first half of the first iteration over the<br />
memory, and as '''Argon2d'''for the rest, thus providing both side-channel attack protection and <br />
brute-force cost savings due to time-memory tradeoffs. '''Argon2i'''makes more passes over the<br />
memory to protect from tradeoff attacks.<br />
<br />
<br />
'''Argon2''' has two variants: '''Argon2d''' and '''Argon2i'''. '''Argon2d''' is faster and uses data-depending memory access, which makes it suitable for cryptocurrencies and applications with no threats from side-channel timing attacks. '''Argon2i''' uses data-independent memory access, which is preferred for password hashing and password-based key derivation. '''Argon2i''' is slower as it makes more passes over the memory to protect from tradeoff attacks. It summarizes the research our group has done in the concept of memory-hard functions and uses a number of novel ideas to achieve very high performance.<br />
<br />
==Winner of PHC==<br />
<br />
Argon2 (version 1.3) is the winner of the [http://password-hashing.net Password Hashing Competition]. In addition to the PHC release, the Argon2 specification also defines two specific modes '''Argon2id''' and '''Argon2ds'''.<br />
<br />
==Specification==<br />
<br />
[[Media:Argon2.pdf | Specification of Argon2 v 1.3 (24.03.2017)]]<br />
<br />
[[Media:Argon2ESP.pdf | "Argon2, new generation of memory-hard functions for password hashing and other applications"]], Euro S&P 2016.<br />
<br />
[https://tools.ietf.org/html/draft-irtf-cfrg-argon2-02 IRTF draft of Argon2]<br />
<br />
==Implementations==<br />
<br />
[https://github.com/khovratovich/Argon2 Reference and optimized extended implementations in C99 and C++11]<br />
<br />
[https://github.com/P-H-C/phc-winner-argon2 Reference implementation in C89 (''PHC release'')]<br />
<br />
[https://github.com/bwesterb/argon2pure Python implementation]<br />
<br />
==Research==<br />
<br />
[http://eprint.iacr.org/2015/430.pdf Research paper "Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing"]. Introduces Argon2 and its fast-verification feature.<br />
<br />
[[Media:PHC-overview.pdf | Design Rationality and Security Analysis of PHC Candidates: Overview]]<br />
<br />
[http://eprint.iacr.org/2015/227.pdf Research paper "Tradeoff cryptanalysis of memory-hard functions" (Asiacrypt 2015)], [[Media:Tradeoffs.pdf | Talk at PasswordsCon'14]], [[Media:Tradeoff-slides.pdf | extended version]], <br />
<br />
[[Media:Argon-slides.pdf | Argon1 Presentation Slides]]<br />
<br />
[[Media:Argon-v1.pdf | Argon1 Reference Guide]]<br />
<br />
==Other resources==<br />
<br />
[http://argon2hash.nl/ Online hash generator]<br />
<br />
[https://github.com/xebia/argon2-go Go wrapper]<br />
<br />
[https://github.com/khovratovich/Argon Reference and optimized implementations of Argon1]<br />
<br />
=Egalitarian Computing=<br />
<br />
It is a new concept that to remedy the disparity between hardware-equipped attackers and legitimate security engineers one has to amalgamate computing for security with a memory-hard function.<br />
<br />
[[Media:Rwc-slides.pdf | "Argon2 and Egalitarian Computing" at Real World Cryptography 2016]] <br />
<br />
[[Media:Egalitarian-rump.pdf | Asiacrypt 2015 rump session slides]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Argon2.pdf&diff=2742File:Argon2.pdf2017-05-17T14:56:54Z<p>Dmitry.khovratovich: Dmitry.khovratovich uploaded a new version of &quot;File:Argon2.pdf&quot;</p>
<hr />
<div>Specification of Argon2</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Argon2&diff=2741Argon22017-05-17T14:55:02Z<p>Dmitry.khovratovich: /* Specification */</p>
<hr />
<div>=Argon2= <br />
'''Argon2''' is a new hash function, which summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memory filling rate and effective use of multiple computing units, while still<br />
providing defense against tradeoff attacks. '''Argon2''' is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. <br />
<br />
==Modes==<br />
<br />
'''Argon2''' has two variants: '''Argon2d''' and '''Argon2i'''. '''Argon2d''' is faster and uses data-depending memory access, which makes it suitable for cryptocurrencies and applications with no threats from side-channel timing attacks. '''Argon2i''' uses data-independent memory access, which is preferred for password hashing and password-based key derivation. '''Argon2i''' is slower as it makes more passes over the memory to protect from tradeoff attacks. It summarizes the research our group has done in the concept of memory-hard functions and uses a number of novel ideas to achieve very high performance.<br />
<br />
==Winner of PHC==<br />
<br />
Argon2 (version 1.3) is the winner of the [http://password-hashing.net Password Hashing Competition]. In addition to the PHC release, the Argon2 specification also defines two specific modes '''Argon2id''' and '''Argon2ds'''.<br />
<br />
==Specification==<br />
<br />
[[Media:Argon2.pdf | Specification of Argon2 v 1.3 (24.03.2017)]]<br />
<br />
[[Media:Argon2ESP.pdf | "Argon2, new generation of memory-hard functions for password hashing and other applications"]], Euro S&P 2016.<br />
<br />
[https://tools.ietf.org/html/draft-irtf-cfrg-argon2-02 IRTF draft of Argon2]<br />
<br />
==Implementations==<br />
<br />
[https://github.com/khovratovich/Argon2 Reference and optimized extended implementations in C99 and C++11]<br />
<br />
[https://github.com/P-H-C/phc-winner-argon2 Reference implementation in C89 (''PHC release'')]<br />
<br />
[https://github.com/bwesterb/argon2pure Python implementation]<br />
<br />
==Research==<br />
<br />
[http://eprint.iacr.org/2015/430.pdf Research paper "Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing"]. Introduces Argon2 and its fast-verification feature.<br />
<br />
[[Media:PHC-overview.pdf | Design Rationality and Security Analysis of PHC Candidates: Overview]]<br />
<br />
[http://eprint.iacr.org/2015/227.pdf Research paper "Tradeoff cryptanalysis of memory-hard functions" (Asiacrypt 2015)], [[Media:Tradeoffs.pdf | Talk at PasswordsCon'14]], [[Media:Tradeoff-slides.pdf | extended version]], <br />
<br />
[[Media:Argon-slides.pdf | Argon1 Presentation Slides]]<br />
<br />
[[Media:Argon-v1.pdf | Argon1 Reference Guide]]<br />
<br />
==Other resources==<br />
<br />
[http://argon2hash.nl/ Online hash generator]<br />
<br />
[https://github.com/xebia/argon2-go Go wrapper]<br />
<br />
[https://github.com/khovratovich/Argon Reference and optimized implementations of Argon1]<br />
<br />
=Egalitarian Computing=<br />
<br />
It is a new concept that to remedy the disparity between hardware-equipped attackers and legitimate security engineers one has to amalgamate computing for security with a memory-hard function.<br />
<br />
[[Media:Rwc-slides.pdf | "Argon2 and Egalitarian Computing" at Real World Cryptography 2016]] <br />
<br />
[[Media:Egalitarian-rump.pdf | Asiacrypt 2015 rump session slides]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Argon2ESP.pdf&diff=2740File:Argon2ESP.pdf2017-05-17T14:51:31Z<p>Dmitry.khovratovich: Argon2: Euro S&P 2016 version</p>
<hr />
<div>Argon2: Euro S&P 2016 version</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2613Equihash2016-11-02T09:10:06Z<p>Dmitry.khovratovich: /* Instances */</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Source || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.2 s <br />
| (3)<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 0.5 s <br />
| (3)<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 95,4<br />
| rowspan="1" | 1 s <br />
| (3)<br />
| 13 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 100,4<br />
| rowspan="1" | 4 s <br />
| (3)<br />
| 26 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 120,5<br />
| rowspan="1" | 4 s <br />
| (3)<br />
| 42 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 s <br />
| (3)<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 s <br />
| (3)<br />
| 500 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 0.1 s <br />
| (2)<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the [[Media:Equihash.pdf| paper]].<br />
<br />
(2) [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
(3) Reference implementation<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: [https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf PDF]<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: [[Media:Equihash-ndss.pdf| PDF]] <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github].<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2612Equihash2016-10-31T16:53:19Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.2 s<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 0.5 s<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 95,4<br />
| rowspan="1" | 1 s<br />
| 13 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 100,4<br />
| rowspan="1" | 4 s<br />
| 26 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 120,5<br />
| rowspan="1" | 4 s<br />
| 42 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the [[Media:Equihash.pdf| paper]].<br />
<br />
(2) [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: [https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf PDF]<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: [[Media:Equihash-ndss.pdf| PDF]] <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github].<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2611Equihash2016-10-31T16:52:16Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.2 s<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 0.5 s<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 95,4<br />
| rowspan="1" | 1 s<br />
| 13 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 100,4<br />
| rowspan="1" | 4 s<br />
| 26 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 120,5<br />
| rowspan="1" | 4 s<br />
| 42 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the [[Media:Equihash.pdf| paper]].<br />
<br />
(2) [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: [https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf PDF]<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: [[Media:Equihash-ndss.pdf| PDF]<br />
* Reference implementation: [https://github.com/khovratovich/equihash at github].<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2610Equihash2016-10-31T16:51:39Z<p>Dmitry.khovratovich: /* Resources */</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.2 s<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 0.5 s<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 95,4<br />
| rowspan="1" | 1 s<br />
| 13 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 100,4<br />
| rowspan="1" | 4 s<br />
| 26 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 120,5<br />
| rowspan="1" | 4 s<br />
| 42 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the [[Media:Equihash.pdf| paper]].<br />
<br />
(2) [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: [https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf PDF]<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: [[Media:Equihash-ndss.pdf|PDF]<br />
* Reference implementation: [https://github.com/khovratovich/equihash at github].<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2609Equihash2016-10-31T16:51:24Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.2 s<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 0.5 s<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 95,4<br />
| rowspan="1" | 1 s<br />
| 13 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 100,4<br />
| rowspan="1" | 4 s<br />
| 26 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 120,5<br />
| rowspan="1" | 4 s<br />
| 42 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the [[Media:Equihash.pdf| paper]].<br />
<br />
(2) [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: [https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf PDF]<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: [[Media:Equihash-ndss.pdf PDF]<br />
* Reference implementation: [https://github.com/khovratovich/equihash at github].<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2608Equihash2016-10-31T16:51:02Z<p>Dmitry.khovratovich: /* Resources */</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.2 s<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 0.5 s<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 95,4<br />
| rowspan="1" | 1 s<br />
| 13 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 100,4<br />
| rowspan="1" | 4 s<br />
| 26 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 120,5<br />
| rowspan="1" | 4 s<br />
| 42 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the [[Media:Equihash.pdf| paper]].<br />
<br />
(2) [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: [https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf PDF]<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: [[File:Equihash-ndss.pdf PDF]<br />
* Reference implementation: [https://github.com/khovratovich/equihash at github].<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Equihash-ndss.pdf&diff=2607File:Equihash-ndss.pdf2016-10-31T16:50:31Z<p>Dmitry.khovratovich: Equihash slides</p>
<hr />
<div>Equihash slides</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2606Equihash2016-10-31T16:32:35Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.2 s<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 0.5 s<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 95,4<br />
| rowspan="1" | 1 s<br />
| 13 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 100,4<br />
| rowspan="1" | 4 s<br />
| 26 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 120,5<br />
| rowspan="1" | 4 s<br />
| 42 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the [[Media:Equihash.pdf| paper]].<br />
<br />
(2) [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: [https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf PDF]<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github].<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2605Equihash2016-10-31T16:31:13Z<p>Dmitry.khovratovich: /* Instances */</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.2 s<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 0.5 s<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 95,4<br />
| rowspan="1" | 1 s<br />
| 13 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 100,4<br />
| rowspan="1" | 4 s<br />
| 26 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 120,5<br />
| rowspan="1" | 4 s<br />
| 42 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the paper.<br />
(2) ZCash mining contest.<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github]<br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2604Equihash2016-10-31T16:22:35Z<p>Dmitry.khovratovich: /* Instances */</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation, though it is not memory-efficient. We also provide the memory requirements of the most memory-efficient implementation that is known to us. Any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Source<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | 0.5 s<br />
| 2.5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 102,5<br />
| rowspan="1" | 1 s<br />
| 5 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 700 MB<br />
| (1)<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 10 sec<br />
| 150 MB<br />
| (2) <br />
|-<br />
|}<br />
<br />
(1) Proposition 2 of the paper.<br />
(2) ZCash mining contest.<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github]<br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2603Equihash2016-10-31T16:10:42Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub>, all smaller than 2<sup>n/(k+1)+1</sup>, such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem (GBP). Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Equihash time-space tradeoffs ==<br />
<br />
The time-space tradeoffs for Equihash apply if the Equihash puzzle is solved using the memory-reduced Wagner's algorithm. The memory-full Wagner's algorithm works with the list of about 2<sup>n/(k+1)+1</sup> entries and is oblivious to the entry size (though for large k it inevitably grows). A memory-reduced Wagner's algorithm generates fewer entries per list and is also somewhat oblivious to the entry size. The best such memory-reduced Wagner's algorithms require about O(q<sup>k/2</sup>) times as much computation per solution if there are q times as few entries per list.<br />
<br />
Thus we conjecture that Equihash is a memory-hard PoW because:<br />
* The optimizations in the list entry size are limited and have been largely discovered by the [https://zcashminers.org/submissions Zcash Mining Contest];<br />
* For the same number of entries per list the fastest algorithms are memory-reduced Wagner's algorithms.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
The [https://github.com/khovratovich/equihash reference implementation] solves the puzzle via several consecutive invocations of the bucket sort, at each step finding all partial collisions within a single bucket and placing them into a bucket for the next iteration. The links between iterations are stored in a tree-like structure which grows linearly as iteration increases.<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide timing benchmarks of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | <br />
| 10 MB<br />
| 2.5 MB<br />
|-<br />
! rowspan="1" | 72,4<br />
| rowspan="1" | <br />
| 16 MB<br />
| 4 MB<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github]<br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2602Equihash2016-10-27T09:49:01Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub> such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the length and order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem. Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 96,5<br />
| rowspan="1" | <br />
| 10 MB<br />
| 2.5 MB<br />
|-<br />
! rowspan="1" | 72,4<br />
| rowspan="1" | <br />
| 16 MB<br />
| 4 MB<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github]<br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2601Equihash2016-10-27T09:34:44Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub> such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the length and order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem. Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
== Equihash as a Proof of Work ==<br />
<br />
Equihash is progress- and amortization-free as the solution cost is not amortized over time or multiple solutions. It has steep time-memory tradeoffs as the reductions in the list size in<br />
Wagner's algorithm by the factor of q increases the computational complexity by O(q<sup>k/2</sup>).<br />
It is expected to have large area-time cost on hardware, as the only parallel implementations known to us require either much larger area or much higher memory bandwidth that is now possible. <br />
Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
<br />
== Implementation ==<br />
<br />
Wagner's algorithm for Equihash-n/k/d makes k iterations over a large list. The list entries vary in size from one iteration to another, and various heuristic optimizations <br />
can be applied to reduce the memory overhead or to speed up the solution search. Examples of such optimized imlementations can be found at [https://zcashminers.org/submissions Zcash Mining Contest].<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: [https://eprint.iacr.org/2015/946.pdf PDF]<br />
* Presentation slides: <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github]<br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2600Equihash2016-10-27T07:35:21Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== Full paper ==<br />
<br />
[[Media:Equihash.pdf| Equihash original paper]].<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub> such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the length and order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem. Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Implementation ==<br />
<br />
<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github]<br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Equihash.pdf&diff=2599File:Equihash.pdf2016-10-27T07:33:24Z<p>Dmitry.khovratovich: Dmitry.khovratovich uploaded a new version of &quot;File:Equihash.pdf&quot;</p>
<hr />
<div>Equihash paper</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2595Equihash2016-10-16T20:00:31Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub> such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the length and order of i<sub>j</sub>.<br />
<br />
A solution for an Equihash puzzle can be found with Wagner's algorithm for the Generalized Birthday problem. Wagner's algorithm requires O(2<sup>n/(k+1)</sup>) memory, and any memory reduction increases the time complexity. That's why Equihash is claimed to be a ''memory-hard'' proof-of-work.<br />
<br />
Equihash is ''asymmetric'' as a solution can be verified memoryless in only 2<sup>k</sup> calls to H.<br />
<br />
== Implementation ==<br />
<br />
<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty.<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: [https://github.com/khovratovich/equihash at github]<br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2594Equihash2016-10-16T19:38:38Z<p>Dmitry.khovratovich: /* High Level View */</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub> such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub>) xor ...xor H( i<sub>2<sup>k</sup></sub>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub>|| ...|| i<sub>2<sup>k</sup></sub>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the length and order of i<sub>j</sub>.<br />
<br />
== Properties ==<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2593Equihash2016-10-16T19:37:03Z<p>Dmitry.khovratovich: /* High Level View */</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub> such that<br />
H(i<sub>1</sub>) xor H(i<sub>2</sub) xor ...xor H( i<sub>2<sup>k</sup>) = 0 and H(i<sub>1</sub>|| i<sub>2</sub|| ...|| i<sub>2<sup>k</sup>) has d leading zeros, where H is the Blake2b hash function. There are also certain restrictions on the length and order of i<sub>j</sub>.<br />
<br />
== Properties ==<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2592Equihash2016-10-16T14:27:34Z<p>Dmitry.khovratovich: /* High Level View */</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub> such that<br />
<math>H(i_1)\oplus H(i_2)\oplus \ldots \oplus H(i_{2^k}) = 0</math> and H(i<sub>1</sub>|| i<sub>2</sub|| ...|| i<sub>2<sup>k</sup>) has d leading zeros.<br />
<br />
== Properties ==<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2586Equihash2016-10-15T14:07:06Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub><br />
<br />
== Properties ==<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" | | <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2585Equihash2016-10-15T14:05:11Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash-pic.png|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub><br />
<br />
== Properties ==<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" || <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Equihash.png&diff=2584File:Equihash.png2016-10-15T14:04:53Z<p>Dmitry.khovratovich: Equihash: proof-of-work based on the generalized birthday problem</p>
<hr />
<div>Equihash: proof-of-work based on the generalized birthday problem</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2583Equihash2016-10-15T14:04:03Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[Media:Equihash-pic.pdf|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub><br />
<br />
== Properties ==<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" || <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2582Equihash2016-10-15T14:03:12Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Equihash-pic.pdf|thumb|Equihash overview.]] ||<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub><br />
<br />
== Properties ==<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" || <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Equihash-pic.pdf&diff=2581File:Equihash-pic.pdf2016-10-15T14:02:25Z<p>Dmitry.khovratovich: Equihash: proof-of-work based on the generalized birthday problem</p>
<hr />
<div>Equihash: proof-of-work based on the generalized birthday problem</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2580Equihash2016-10-15T14:00:33Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Sparx-A.png|thumb|SPECKEY, denoted A<sub>k</sub>.]] || [[File:Sparx-64-round-function.png|thumb|Round function of SPARX-64/128]]<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
The puzzle for Equihash-n/k/d is to find i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>2<sup>k</sup></sub><br />
<br />
== Properties ==<br />
<br />
== Instances ==<br />
<br />
Here, we list several Equihash instances with d=0, and provide time and memory requirements of our reference implementation. We also provide lower bounds on the memory requirements such that any ASIC implementation using less memory should incur a significant penalty<br />
<br />
{| border="1" class="wikitable"<br />
! n,k|| Time || Memory || Minimum memory<br />
|-<br />
! rowspan="1" | 144,5<br />
| rowspan="1" | 15 sec<br />
| 2 GB<br />
| 500 MB<br />
|-<br />
! rowspan="1" | 200,9<br />
| rowspan="1" | 5 sec<br />
| <br />
| <br />
|-<br />
! rowspan="1" |<br />
| rowspan="1" || <br />
| <br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Equihash&diff=2579Equihash2016-10-15T13:38:35Z<p>Dmitry.khovratovich: Created page with "Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources. {| class="floa..."</p>
<hr />
<div>Equihash is a memory-hard proof-of-work scheme. It solves a computational puzzle, best algorithms for which require certain computational and memory resources.<br />
<br />
{| class="floatright"<br />
|-<br />
| [[File:Sparx-A.png|thumb|SPECKEY, denoted A<sub>k</sub>.]] || [[File:Sparx-64-round-function.png|thumb|Round function of SPARX-64/128]]<br />
|-<br />
|}<br />
<br />
== High Level View ==<br />
<br />
* Article: ''"Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''<ref name=BK16></ref><br />
* Authors: Alex Biryukov and Dmitry Khovratovich<br />
<br />
Equihash is a family of proof-of-work schemes with three parameters n, k, and d, which determine the scheme Equihash-n/k/d and the time and memory complexity of the puzzle solver for it, and seed S, which makes every puzzle unique and solutions incompatible. <br />
The best algorithms for Equihash-n/k/d require O(2<sup>n/(k+1)+d</sup>) time and O(2<sup>n/(k+1)</sup>) memory, though implementations of this algorithms differ in both metrics, see below.<br />
<br />
== Strengths ==<br />
<br />
== Cryptanalysis ==<br />
<br />
Here, we list the different cryptanalyses against the SPARX ciphers we are aware of, including those by its designers.<br />
<br />
{| border="1" class="wikitable"<br />
! Instance || Rounds || Attack || Authors<br />
|-<br />
! rowspan="1" | SPARX-64/128<br />
| rowspan="1" | 24<br />
| 15 rounds (Integral)<br />
| Designers<ref name=DPUVGB16></ref><br />
|-<br />
! rowspan="1" | SPARX-128/128<br />
| rowspan="1" | 32<br />
| 22 rounds (Integral)<br />
| Designers<ref name=DPUVGB16></ref><br />
|-<br />
! rowspan="1" | SPARX-128/256<br />
| rowspan="1" | 40<br />
| 24 rounds (Integral)<br />
| Designers<ref name=DPUVGB16></ref><br />
|-<br />
|}<br />
<br />
== Resources ==<br />
<br />
* NDSS'16 paper: To appear<br />
* Eprint version: To appear<br />
* <br />
* Bibtex entry: To appear<br />
* Presentation slides: <br />
* Reference implementation: <br />
* Optimized implementations: .<br />
<br />
== References ==<br />
<br />
<references><br />
<ref name=BK16>Biryukov, A. and Khovratovich, D. (2016). ''Equihash: asymmetric proof-of-work based on the Generalized Birthday problem''. In Network and Distributed System Security Symposium (NDSS) 2016. <!-- [https://eprint.iacr.org/2015/946.pdf pdf at eprint.iacr.org] --></ref><br />
</references></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Cryptocurrency_FinTech&diff=2578Cryptocurrency FinTech2016-10-15T13:21:30Z<p>Dmitry.khovratovich: </p>
<hr />
<div>==Privacy and Anonymity==<br />
<br />
* [[Alex Biryukov]], [[Dmitry Khovratovich]], [[Ivan Pustogarov]], "Deanonymisation of clients in Bitcoin P2P network", ACM CCS 2014, Arizona, USA ([http://arxiv.org/abs/1405.7418 early version in archive], [[Media:Ccsfp614s-biryukovATS.pdf| revised paper]])<br />
<br />
[[Informal description of the Bitcoin deanonymization attack]].<br />
<br />
* [[Alex Biryukov]], [[Ivan Pustogarov]], "Proof-of-Work as Anonymous Micropayment: Rewarding a Tor Relay", Financial Cryptography 2015, Puerto-Rico, USA. ([[Media:Alex-ivan-tor-micropayments.pdf| paper]])<br />
<br />
[[Press release on secure, anonymous, easy way to pay for online content]]<br />
<br />
* [[Alex Biryukov]], [[Ivan Pustogarov]], "Bitcoin over Tor isn't a good idea", IEEE Security and Privacy Symposium 2015, ([[Media:1410.6079v2.pdf| paper]], [[Media:SnP-2015-pustogarov.pdf|slides]])<br />
<br />
==New Proofs of Work==<br />
<br />
* [[Alex Biryukov]], [[Dmitry Khovratovich]], "[[Equihash]]: asymmetric proof-of-work based on the Generalized Birthday problem", NDSS 2016, San Diego, USA ([http://eprint.iacr.org/2015/946.pdf ePrint version])<br />
<br />
* [[Alex Biryukov]], [[Dmitry Khovratovich]], "Egalitarian computing", USENIX 2016, Austin, USA ([http://orbilu.uni.lu/handle/10993/27654 preprint])</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Argon2&diff=2497Argon22016-06-17T05:49:39Z<p>Dmitry.khovratovich: /* Specification */</p>
<hr />
<div>=Argon2= <br />
'''Argon2''' is a new hash function, which summarizes the state of the art in the design of memory-hard functions. It is a streamlined and simple design. It aims at the highest memory filling rate and effective use of multiple computing units, while still<br />
providing defense against tradeoff attacks. '''Argon2''' is optimized for the x86 architecture and exploits the cache and memory organization of the recent Intel and AMD processors. <br />
<br />
==Modes==<br />
<br />
'''Argon2''' has two variants: '''Argon2d''' and '''Argon2i'''. '''Argon2d''' is faster and uses data-depending memory access, which makes it suitable for cryptocurrencies and applications with no threats from side-channel timing attacks. '''Argon2i''' uses data-independent memory access, which is preferred for password hashing and password-based key derivation. '''Argon2i''' is slower as it makes more passes over the memory to protect from tradeoff attacks. It summarizes the research our group has done in the concept of memory-hard functions and uses a number of novel ideas to achieve very high performance.<br />
<br />
==Winner of PHC==<br />
<br />
Argon2 (version 1.3) is the winner of the [http://password-hashing.net Password Hashing Competition]. In addition to the PHC release, the Argon2 specification also defines two specific modes '''Argon2id''' and '''Argon2ds'''.<br />
<br />
==Specification==<br />
<br />
[[Media:Argon2.pdf | Specification of Argon2]]<br />
[[Media:Draft-irtf-cfrg-argon2.txt | IRTF draft of Argon2]]<br />
<br />
==Implementations==<br />
<br />
[https://github.com/khovratovich/Argon2 Reference and optimized extended implementations in C99 and C++11]<br />
<br />
[https://github.com/P-H-C/phc-winner-argon2 Reference implementation in C89 (''PHC release'')]<br />
<br />
[https://github.com/bwesterb/argon2pure Python implementation]<br />
<br />
==Research==<br />
<br />
[http://eprint.iacr.org/2015/430.pdf Research paper "Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing"]. Introduces Argon2 and its fast-verification feature.<br />
<br />
[[Media:PHC-overview.pdf | Design Rationality and Security Analysis of PHC Candidates: Overview]]<br />
<br />
[http://eprint.iacr.org/2015/227.pdf Research paper "Tradeoff cryptanalysis of memory-hard functions" (Asiacrypt 2015)], [[Media:Tradeoffs.pdf | Talk at PasswordsCon'14]], [[Media:Tradeoff-slides.pdf | extended version]], <br />
<br />
[[Media:Argon-slides.pdf | Argon1 Presentation Slides]]<br />
<br />
[[Media:Argon-v1.pdf | Argon1 Reference Guide]]<br />
<br />
==Other resources==<br />
<br />
[http://argon2hash.nl/ Online hash generator]<br />
<br />
[https://github.com/xebia/argon2-go Go wrapper]<br />
<br />
[https://github.com/khovratovich/Argon Reference and optimized implementations of Argon1]<br />
<br />
=Egalitarian Computing=<br />
<br />
It is a new concept that to remedy the disparity between hardware-equipped attackers and legitimate security engineers one has to amalgamate computing for security with a memory-hard function.<br />
<br />
[[Media:Rwc-slides.pdf | "Argon2 and Egalitarian Computing" at Real World Cryptography 2016]] <br />
<br />
[[Media:Egalitarian-rump.pdf | Asiacrypt 2015 rump session slides]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Draft-irtf-cfrg-argon2.txt&diff=2496File:Draft-irtf-cfrg-argon2.txt2016-06-17T05:48:57Z<p>Dmitry.khovratovich: IRTF draft of Argon2</p>
<hr />
<div>IRTF draft of Argon2</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Cryptocurrency_FinTech&diff=2495Cryptocurrency FinTech2016-06-11T13:23:01Z<p>Dmitry.khovratovich: </p>
<hr />
<div>==Privacy and Anonymity==<br />
<br />
* [[Alex Biryukov]], [[Dmitry Khovratovich]], [[Ivan Pustogarov]], "Deanonymisation of clients in Bitcoin P2P network", ACM CCS 2014, Arizona, USA ([http://arxiv.org/abs/1405.7418 early version in archive], [[Media:Ccsfp614s-biryukovATS.pdf| revised paper]])<br />
<br />
[[Informal description of the Bitcoin deanonymization attack]].<br />
<br />
* [[Alex Biryukov]], [[Ivan Pustogarov]], "Proof-of-Work as Anonymous Micropayment: Rewarding a Tor Relay", Financial Cryptography 2015, Puerto-Rico, USA. ([[Media:Alex-ivan-tor-micropayments.pdf| paper]])<br />
<br />
[[Press release on secure, anonymous, easy way to pay for online content]]<br />
<br />
* [[Alex Biryukov]], [[Ivan Pustogarov]], "Bitcoin over Tor isn't a good idea", IEEE Security and Privacy Symposium 2015, ([[Media:1410.6079v2.pdf| paper]], [[Media:SnP-2015-pustogarov.pdf|slides]])<br />
<br />
==New Proofs of Work==<br />
<br />
* [[Alex Biryukov]], [[Dmitry Khovratovich]], "Equihash: asymmetric proof-of-work based on the Generalized Birthday problem", NDSS 2016, San Diego, USA ([http://eprint.iacr.org/2015/946.pdf ePrint version])<br />
<br />
* [[Alex Biryukov]], [[Dmitry Khovratovich]], "Egalitarian computing", USENIX 2016, Austin, USA ([http://orbilu.uni.lu/handle/10993/27654 preprint])</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Dmitry_Khovratovich&diff=2470Dmitry Khovratovich2016-06-09T10:05:24Z<p>Dmitry.khovratovich: </p>
<hr />
<div>Dmitry Khovratovich is a post-doctoral researcher since January 2013. He specializes in the design and cryptanalysis of symmetric primitives, e.g. hash functions and block ciphers. Dmitry is also interested in the practical aspects of cryptography: electronic currencies, tamper-proof designs, etc.. Dmitry is an author of the first attacks on the AES block cipher in various models, the best attacks on Skein, SHA-1 and SHA-2 hash functions, the attacks on the full versions of ALE, Grindahl-512, Luffa, and many others.<br />
<br />
===Main publications===<br />
* [[Media:Egalitarian.pdf| '''Egalitarian computing''']], USENIX 2016, with Alex Biryukov<br />
* [[Media:Argon2-euro.pdf| '''Argon2: new generation of memory-hard functions for password hashing and other applications''']], Euro S&P 2016, with Alex Biryukov and Daniel Dinu<br />
* [[Media:Equihash.pdf| '''Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem''']], NDSS 2016, with Alex Biryukov<br />
* [[Media:Tradeoff.pdf| '''Tradeoff Cryptanalysis of Memory-Hard Functions''']], Asiacrypt 2015, with Alex Biryukov<br />
* [[Media:Rotarx.pdf| '''Rotational Cryptanalysis of ARX Revisited''']], FSE 2015, with Ivica Nikolic, Josef Pieprzyk, Przemyslaw Sokolowski, Ron Steinfeld<br />
* [[Media:White-proc.pdf| '''Cryptographic Schemes Based on the ASASA Structure: Black-Box, White-Box, and Public-Key''']], Asiacrypt 2014, with Alex Biryukov and Charles Bouillaguet<br />
* [[Media:Bitcoin.pdf| '''Deanonymisation of Clients in Bitcoin P2P Network''']], ACM CCS 2014 with Alex Biryukov and Ivan Pustogarov<br />
* ''Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64'', FSE 2014, with Leo Perrin<br />
* [[Media:Paeq-full.pdf| '''PAEQ: Parallelizable Permutation-Based Authenticated Encryption''']], ISC 2014, with Alex Biryukov<br />
* ''Key Wrapping with a Fixed Permutation'', CT-RSA 2014.<br />
* ''The LOCAL attack: Cryptanalysis of the Authenticated Encryption Scheme ALE'', SAC'13, 2013. With Christian Rechberger.<br />
* ''Bicliques for Permutations: Collision and Preimage Attacks in Stronger Settings'', Asiacrypt'12, 2012.<br />
* ''New Preimage Attacks against Reduced SHA-1'', Crypto'12, 2012. With Simon Knellwolf.<br />
* ''Narrow-Bicliques: Cryptanalysis of the Full IDEA'', Eurocrypt'12, 2012. With Gaetan Leurent and Christian Rechberger.<br />
* ''Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 Family'', FSE'12, 2012. With Christian Rechberger and Alexandra Savelieva.<br />
* ''Biclique Cryptanalysis of the Full AES'', Asiacrypt'11, 2011. With Andrey Bogdanov and Christian Rechberger.<br />
* ''Rotational Rebound Attacks on Reduced Skein'', Asiacrypt'10, 2010. With Ivica Nikolic and Christian Rechberger. BEST PAPER AWARD.<br />
* ''Rotational Cryptanalysis of ARX'', FSE'10, 2010. With Ivica Nikolic.<br />
* ''Cryptanalysis of Luffa v2 Components'', SAC'10, 2010. With María Naya-Plasencia, Andrea Röck, and Martin Schläffer.<br />
* [[Media:AES Practical V12.pdf| '''Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds''']]. With [[Alex Biryukov|Alex Biryukov]], Orr Dunkelman, Nathan Keller, and Adi Shamir. <br />
* [[Media:aes-boom-revised.pdf| '''Related-Key Attack on the Full AES-192 and AES-256'''.]] With [[Alex Biryukov]].<br />
* [[Media:aes-256-ext.pdf| '''Distinguisher and Related-Key Attack on the Full AES-256'''.]] CRYPTO'2009. With [[Alex Biryukov]] and [[Ivica Nikolić]].<br />
* [[Media:Struct2.pdf| '''Cryptanalysis of hash functions with structures'''.]] SAC'2009. <br />
* ''Speeding up Collision Search for Byte-Oriented Hash Functions'', CT-RSA'09. With [[Alex Biryukov]] and [[Ivica Nikolić]]<br />
* '''Meet-in-the-Middle Attacks on SHA-3 Candidates'''. FSE'2009. With [[Ralf-Philipp Weinmann]] and [[Ivica Nikolić]].<br />
<br />
===Presentations===<br />
<br />
* [[Media:Aes-msu-2.pdf| '''Cryptanalysis of AES]], Moscow State University, 21 October 2009.<br />
* [[Media:Aes-attacks.pdf| '''Recent attacks on AES]], Leuven, SymLab meeting, 15 September 2009.<br />
<br />
==Program Committees==<br />
* FSE 2015, 2014, 2013, 2012<br />
* EUROCRYPT 2013<br />
* Indocrypt 2014<br />
* CT-RSA 2015<br />
<br />
===See also===<br />
<br />
*PhD thesis [[Media:Thesis.pdf | New Approaches to the Cryptanalysis of Symmetric Primitives]]<br />
<br />
*Structural cryptanalysis of [[Media:Struct.pdf | Grindahl and RadioGatun]]<br />
<br />
*Аnalysis of Keccak: [[Media:FAnalysisKeccak.pdf | paper]], [[Media:Keccak-tool.zip | tool]], [[Media:Slides.pdf | slides]]<br />
<br />
*Nonrandomness of 33 rounds of [[Media:Nonrandomness_of_the_33-round_MD6-analysis.pdf | MD6]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Egalitarian.pdf&diff=2469File:Egalitarian.pdf2016-06-09T10:04:52Z<p>Dmitry.khovratovich: </p>
<hr />
<div></div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Dmitry_Khovratovich&diff=2459Dmitry Khovratovich2016-05-22T08:28:11Z<p>Dmitry.khovratovich: /* Main publications */</p>
<hr />
<div>Dmitry Khovratovich is a post-doctoral researcher since January 2013. He specializes in the design and cryptanalysis of symmetric primitives, e.g. hash functions and block ciphers. Dmitry is also interested in the practical aspects of cryptography: electronic currencies, tamper-proof designs, etc.. Dmitry is an author of the first attacks on the AES block cipher in various models, the best attacks on Skein, SHA-1 and SHA-2 hash functions, the attacks on the full versions of ALE, Grindahl-512, Luffa, and many others.<br />
<br />
===Main publications===<br />
* ''Egalitarian computing'', USENIX 2016, with Alex Biryukov<br />
* [[Media:Argon2-euro.pdf| '''Argon2: new generation of memory-hard functions for password hashing and other applications''']], Euro S&P 2016, with Alex Biryukov and Daniel Dinu<br />
* [[Media:Equihash.pdf| '''Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem''']], NDSS 2016, with Alex Biryukov<br />
* [[Media:Tradeoff.pdf| '''Tradeoff Cryptanalysis of Memory-Hard Functions''']], Asiacrypt 2015, with Alex Biryukov<br />
* [[Media:Rotarx.pdf| '''Rotational Cryptanalysis of ARX Revisited''']], FSE 2015, with Ivica Nikolic, Josef Pieprzyk, Przemyslaw Sokolowski, Ron Steinfeld<br />
* [[Media:White-proc.pdf| '''Cryptographic Schemes Based on the ASASA Structure: Black-Box, White-Box, and Public-Key''']], Asiacrypt 2014, with Alex Biryukov and Charles Bouillaguet<br />
* [[Media:Bitcoin.pdf| '''Deanonymisation of Clients in Bitcoin P2P Network''']], ACM CCS 2014 with Alex Biryukov and Ivan Pustogarov<br />
* ''Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64'', FSE 2014, with Leo Perrin<br />
* [[Media:Paeq-full.pdf| '''PAEQ: Parallelizable Permutation-Based Authenticated Encryption''']], ISC 2014, with Alex Biryukov<br />
* ''Key Wrapping with a Fixed Permutation'', CT-RSA 2014.<br />
* ''The LOCAL attack: Cryptanalysis of the Authenticated Encryption Scheme ALE'', SAC'13, 2013. With Christian Rechberger.<br />
* ''Bicliques for Permutations: Collision and Preimage Attacks in Stronger Settings'', Asiacrypt'12, 2012.<br />
* ''New Preimage Attacks against Reduced SHA-1'', Crypto'12, 2012. With Simon Knellwolf.<br />
* ''Narrow-Bicliques: Cryptanalysis of the Full IDEA'', Eurocrypt'12, 2012. With Gaetan Leurent and Christian Rechberger.<br />
* ''Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 Family'', FSE'12, 2012. With Christian Rechberger and Alexandra Savelieva.<br />
* ''Biclique Cryptanalysis of the Full AES'', Asiacrypt'11, 2011. With Andrey Bogdanov and Christian Rechberger.<br />
* ''Rotational Rebound Attacks on Reduced Skein'', Asiacrypt'10, 2010. With Ivica Nikolic and Christian Rechberger. BEST PAPER AWARD.<br />
* ''Rotational Cryptanalysis of ARX'', FSE'10, 2010. With Ivica Nikolic.<br />
* ''Cryptanalysis of Luffa v2 Components'', SAC'10, 2010. With María Naya-Plasencia, Andrea Röck, and Martin Schläffer.<br />
* [[Media:AES Practical V12.pdf| '''Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds''']]. With [[Alex Biryukov|Alex Biryukov]], Orr Dunkelman, Nathan Keller, and Adi Shamir. <br />
* [[Media:aes-boom-revised.pdf| '''Related-Key Attack on the Full AES-192 and AES-256'''.]] With [[Alex Biryukov]].<br />
* [[Media:aes-256-ext.pdf| '''Distinguisher and Related-Key Attack on the Full AES-256'''.]] CRYPTO'2009. With [[Alex Biryukov]] and [[Ivica Nikolić]].<br />
* [[Media:Struct2.pdf| '''Cryptanalysis of hash functions with structures'''.]] SAC'2009. <br />
* ''Speeding up Collision Search for Byte-Oriented Hash Functions'', CT-RSA'09. With [[Alex Biryukov]] and [[Ivica Nikolić]]<br />
* '''Meet-in-the-Middle Attacks on SHA-3 Candidates'''. FSE'2009. With [[Ralf-Philipp Weinmann]] and [[Ivica Nikolić]].<br />
<br />
===Presentations===<br />
<br />
* [[Media:Aes-msu-2.pdf| '''Cryptanalysis of AES]], Moscow State University, 21 October 2009.<br />
* [[Media:Aes-attacks.pdf| '''Recent attacks on AES]], Leuven, SymLab meeting, 15 September 2009.<br />
<br />
==Program Committees==<br />
* FSE 2015, 2014, 2013, 2012<br />
* EUROCRYPT 2013<br />
* Indocrypt 2014<br />
* CT-RSA 2015<br />
<br />
===See also===<br />
<br />
*PhD thesis [[Media:Thesis.pdf | New Approaches to the Cryptanalysis of Symmetric Primitives]]<br />
<br />
*Structural cryptanalysis of [[Media:Struct.pdf | Grindahl and RadioGatun]]<br />
<br />
*Аnalysis of Keccak: [[Media:FAnalysisKeccak.pdf | paper]], [[Media:Keccak-tool.zip | tool]], [[Media:Slides.pdf | slides]]<br />
<br />
*Nonrandomness of 33 rounds of [[Media:Nonrandomness_of_the_33-round_MD6-analysis.pdf | MD6]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Dmitry_Khovratovich&diff=2458Dmitry Khovratovich2016-05-22T08:27:57Z<p>Dmitry.khovratovich: /* Main publications */</p>
<hr />
<div>Dmitry Khovratovich is a post-doctoral researcher since January 2013. He specializes in the design and cryptanalysis of symmetric primitives, e.g. hash functions and block ciphers. Dmitry is also interested in the practical aspects of cryptography: electronic currencies, tamper-proof designs, etc.. Dmitry is an author of the first attacks on the AES block cipher in various models, the best attacks on Skein, SHA-1 and SHA-2 hash functions, the attacks on the full versions of ALE, Grindahl-512, Luffa, and many others.<br />
<br />
===Main publications===<br />
* ''Egalitarian computing'', USENIX 2016, with Alex Biryukov<br />
* [[Media:Argon2-euro.pdf| '''Argon2: new generation of memory-hard functions for password hashing and other applications''']], Euro S&P 2016, with Alex Biryukov and Daniel Dinu<br />
* [[Media:Equihash.pdf| '''Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem''']], NDSS 2016, with Alex Biryukov<br />
* [[Media:Tradeoff.pdf| '''Tradeoff Cryptanalysis of Memory-Hard Functions''']], Asiacrypt 2015, with Alex Biryukov<br />
* [[Media:Rotarx.pdf| '''Rotational Cryptanalysis of ARX Revisited''']], FSE 2015, with Ivica Nikolic, Josef Pieprzyk, Przemyslaw Sokolowski, Ron Steinfeld<br />
* [[Media:White-proc.pdf| '''Cryptographic Schemes Based on the ASASA Structure: Black-Box, White-Box, and Public-Key''']], Asiacrypt 2014, with Alex Biryukov and Charles Bouillaguet<br />
* [[Media:Bitcoin.pdf| '''Deanonymisation of Clients in Bitcoin P2P Network'''], ACM CCS 2014 with Alex Biryukov and Ivan Pustogarov<br />
* ''Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64'', FSE 2014, with Leo Perrin<br />
* [[Media:Paeq-full.pdf| '''PAEQ: Parallelizable Permutation-Based Authenticated Encryption''']], ISC 2014, with Alex Biryukov<br />
* ''Key Wrapping with a Fixed Permutation'', CT-RSA 2014.<br />
* ''The LOCAL attack: Cryptanalysis of the Authenticated Encryption Scheme ALE'', SAC'13, 2013. With Christian Rechberger.<br />
* ''Bicliques for Permutations: Collision and Preimage Attacks in Stronger Settings'', Asiacrypt'12, 2012.<br />
* ''New Preimage Attacks against Reduced SHA-1'', Crypto'12, 2012. With Simon Knellwolf.<br />
* ''Narrow-Bicliques: Cryptanalysis of the Full IDEA'', Eurocrypt'12, 2012. With Gaetan Leurent and Christian Rechberger.<br />
* ''Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 Family'', FSE'12, 2012. With Christian Rechberger and Alexandra Savelieva.<br />
* ''Biclique Cryptanalysis of the Full AES'', Asiacrypt'11, 2011. With Andrey Bogdanov and Christian Rechberger.<br />
* ''Rotational Rebound Attacks on Reduced Skein'', Asiacrypt'10, 2010. With Ivica Nikolic and Christian Rechberger. BEST PAPER AWARD.<br />
* ''Rotational Cryptanalysis of ARX'', FSE'10, 2010. With Ivica Nikolic.<br />
* ''Cryptanalysis of Luffa v2 Components'', SAC'10, 2010. With María Naya-Plasencia, Andrea Röck, and Martin Schläffer.<br />
* [[Media:AES Practical V12.pdf| '''Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds''']]. With [[Alex Biryukov|Alex Biryukov]], Orr Dunkelman, Nathan Keller, and Adi Shamir. <br />
* [[Media:aes-boom-revised.pdf| '''Related-Key Attack on the Full AES-192 and AES-256'''.]] With [[Alex Biryukov]].<br />
* [[Media:aes-256-ext.pdf| '''Distinguisher and Related-Key Attack on the Full AES-256'''.]] CRYPTO'2009. With [[Alex Biryukov]] and [[Ivica Nikolić]].<br />
* [[Media:Struct2.pdf| '''Cryptanalysis of hash functions with structures'''.]] SAC'2009. <br />
* ''Speeding up Collision Search for Byte-Oriented Hash Functions'', CT-RSA'09. With [[Alex Biryukov]] and [[Ivica Nikolić]]<br />
* '''Meet-in-the-Middle Attacks on SHA-3 Candidates'''. FSE'2009. With [[Ralf-Philipp Weinmann]] and [[Ivica Nikolić]].<br />
<br />
===Presentations===<br />
<br />
* [[Media:Aes-msu-2.pdf| '''Cryptanalysis of AES]], Moscow State University, 21 October 2009.<br />
* [[Media:Aes-attacks.pdf| '''Recent attacks on AES]], Leuven, SymLab meeting, 15 September 2009.<br />
<br />
==Program Committees==<br />
* FSE 2015, 2014, 2013, 2012<br />
* EUROCRYPT 2013<br />
* Indocrypt 2014<br />
* CT-RSA 2015<br />
<br />
===See also===<br />
<br />
*PhD thesis [[Media:Thesis.pdf | New Approaches to the Cryptanalysis of Symmetric Primitives]]<br />
<br />
*Structural cryptanalysis of [[Media:Struct.pdf | Grindahl and RadioGatun]]<br />
<br />
*Аnalysis of Keccak: [[Media:FAnalysisKeccak.pdf | paper]], [[Media:Keccak-tool.zip | tool]], [[Media:Slides.pdf | slides]]<br />
<br />
*Nonrandomness of 33 rounds of [[Media:Nonrandomness_of_the_33-round_MD6-analysis.pdf | MD6]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Bitcoin.pdf&diff=2457File:Bitcoin.pdf2016-05-22T08:24:19Z<p>Dmitry.khovratovich: Deanonymization</p>
<hr />
<div>Deanonymization</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:White-proc.pdf&diff=2456File:White-proc.pdf2016-05-22T08:22:53Z<p>Dmitry.khovratovich: ASASA</p>
<hr />
<div>ASASA</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=Dmitry_Khovratovich&diff=2455Dmitry Khovratovich2016-05-22T08:19:49Z<p>Dmitry.khovratovich: /* Main publications */</p>
<hr />
<div>Dmitry Khovratovich is a post-doctoral researcher since January 2013. He specializes in the design and cryptanalysis of symmetric primitives, e.g. hash functions and block ciphers. Dmitry is also interested in the practical aspects of cryptography: electronic currencies, tamper-proof designs, etc.. Dmitry is an author of the first attacks on the AES block cipher in various models, the best attacks on Skein, SHA-1 and SHA-2 hash functions, the attacks on the full versions of ALE, Grindahl-512, Luffa, and many others.<br />
<br />
===Main publications===<br />
* ''Egalitarian computing'', USENIX 2016, with Alex Biryukov<br />
* [[Media:Argon2-euro.pdf| '''Argon2: new generation of memory-hard functions for password hashing and other applications''']], Euro S&P 2016, with Alex Biryukov and Daniel Dinu<br />
* [[Media:Equihash.pdf| '''Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem''']], NDSS 2016, with Alex Biryukov<br />
* [[Media:Tradeoff.pdf| '''Tradeoff Cryptanalysis of Memory-Hard Functions''']], Asiacrypt 2015, with Alex Biryukov<br />
* [[Media:Rotarx.pdf| '''Rotational Cryptanalysis of ARX Revisited''']], FSE 2015, with Ivica Nikolic, Josef Pieprzyk, Przemyslaw Sokolowski, Ron Steinfeld<br />
* ''Cryptographic Schemes Based on the ASASA Structure: Black-Box, White-Box, and Public-Key'', Asiacrypt 2014, with Alex Biryukov and Charles Bouillaguet<br />
* [[Media:Ccsfp614s-biryukovATS.pdf| '''Deanonymisation of Clients in Bitcoin P2P Network'''], ACM CCS 2014 with Alex Biryukov and Ivan Pustogarov<br />
* ''Collision Spectrum, Entropy Loss, T-Sponges, and Cryptanalysis of GLUON-64'', FSE 2014, with Leo Perrin<br />
* ''PAEQ: Parallelizable Permutation-Based Authenticated Encryption'', ISC 2014, with Alex Biryukov<br />
* ''Key Wrapping with a Fixed Permutation'', CT-RSA 2014.<br />
* ''The LOCAL attack: Cryptanalysis of the Authenticated Encryption Scheme ALE'', SAC'13, 2013. With Christian Rechberger.<br />
* ''Bicliques for Permutations: Collision and Preimage Attacks in Stronger Settings'', Asiacrypt'12, 2012.<br />
* ''New Preimage Attacks against Reduced SHA-1'', Crypto'12, 2012. With Simon Knellwolf.<br />
* ''Narrow-Bicliques: Cryptanalysis of the Full IDEA'', Eurocrypt'12, 2012. With Gaetan Leurent and Christian Rechberger.<br />
* ''Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 Family'', FSE'12, 2012. With Christian Rechberger and Alexandra Savelieva.<br />
* ''Biclique Cryptanalysis of the Full AES'', Asiacrypt'11, 2011. With Andrey Bogdanov and Christian Rechberger.<br />
* ''Rotational Rebound Attacks on Reduced Skein'', Asiacrypt'10, 2010. With Ivica Nikolic and Christian Rechberger. BEST PAPER AWARD.<br />
* ''Rotational Cryptanalysis of ARX'', FSE'10, 2010. With Ivica Nikolic.<br />
* ''Cryptanalysis of Luffa v2 Components'', SAC'10, 2010. With María Naya-Plasencia, Andrea Röck, and Martin Schläffer.<br />
* [[Media:AES Practical V12.pdf| '''Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds''']]. With [[Alex Biryukov|Alex Biryukov]], Orr Dunkelman, Nathan Keller, and Adi Shamir. <br />
* [[Media:aes-boom-revised.pdf| '''Related-Key Attack on the Full AES-192 and AES-256'''.]] With [[Alex Biryukov]].<br />
* [[Media:aes-256-ext.pdf| '''Distinguisher and Related-Key Attack on the Full AES-256'''.]] CRYPTO'2009. With [[Alex Biryukov]] and [[Ivica Nikolić]].<br />
* [[Media:Struct2.pdf| '''Cryptanalysis of hash functions with structures'''.]] SAC'2009. <br />
* ''Speeding up Collision Search for Byte-Oriented Hash Functions'', CT-RSA'09. With [[Alex Biryukov]] and [[Ivica Nikolić]]<br />
* '''Meet-in-the-Middle Attacks on SHA-3 Candidates'''. FSE'2009. With [[Ralf-Philipp Weinmann]] and [[Ivica Nikolić]].<br />
<br />
===Presentations===<br />
<br />
* [[Media:Aes-msu-2.pdf| '''Cryptanalysis of AES]], Moscow State University, 21 October 2009.<br />
* [[Media:Aes-attacks.pdf| '''Recent attacks on AES]], Leuven, SymLab meeting, 15 September 2009.<br />
<br />
==Program Committees==<br />
* FSE 2015, 2014, 2013, 2012<br />
* EUROCRYPT 2013<br />
* Indocrypt 2014<br />
* CT-RSA 2015<br />
<br />
===See also===<br />
<br />
*PhD thesis [[Media:Thesis.pdf | New Approaches to the Cryptanalysis of Symmetric Primitives]]<br />
<br />
*Structural cryptanalysis of [[Media:Struct.pdf | Grindahl and RadioGatun]]<br />
<br />
*Аnalysis of Keccak: [[Media:FAnalysisKeccak.pdf | paper]], [[Media:Keccak-tool.zip | tool]], [[Media:Slides.pdf | slides]]<br />
<br />
*Nonrandomness of 33 rounds of [[Media:Nonrandomness_of_the_33-round_MD6-analysis.pdf | MD6]]</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Argon2-euro.pdf&diff=2454File:Argon2-euro.pdf2016-05-22T08:19:20Z<p>Dmitry.khovratovich: Argon2 EuroS&P16</p>
<hr />
<div>Argon2 EuroS&P16</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Tradeoff.pdf&diff=2453File:Tradeoff.pdf2016-05-22T08:16:18Z<p>Dmitry.khovratovich: Tradeoff cryptanalysis</p>
<hr />
<div>Tradeoff cryptanalysis</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Rotarx.pdf&diff=2452File:Rotarx.pdf2016-05-22T08:11:50Z<p>Dmitry.khovratovich: Rotational ARX revisited</p>
<hr />
<div>Rotational ARX revisited</div>Dmitry.khovratovichhttps://www.cryptolux.org/index.php?title=File:Equihash.pdf&diff=2451File:Equihash.pdf2016-05-22T08:10:10Z<p>Dmitry.khovratovich: Equihash paper</p>
<hr />
<div>Equihash paper</div>Dmitry.khovratovich