khovratovich / equihash Goto Github PK

Equihash: memory-hard PoW with fast verification

License: Creative Commons Zero v1.0 Universal

Makefile 0.21% C 26.25% C++ 73.54%

equihash's Introduction

Equihash

This is an optimized C++ implementation of Equihash, the memory-hard Proof-of-Work with fast verification. Equihash is designed by Alex Biryukov and Dmitry Khovratovich, cryptographers at the University of Luxembourg.

Equihash is an asymmetric proof-of-work algorithm based on a computationally hard generalized birthday problem, which requires a lot of memory to generate a proof, but is instant to verify. Equihash is adapted as the PoW in Zcash a public implementation of the cryptocurrency protocol Zerocash. It is possible to use Equihash in TLS as a client puzzle.

Equihash has two parameters: N (width in bits) and K (length), which determine the complexity of the underlying problem and thus the memory and time complexity of the Equihash PoW. The underlying hash function is Blake2b, but any collision-resistant hash function would work too.

The time complexity is proportional to K2^{N/(K+1)}, and memory complexity to 2^{K+N/(K+1)}. The proof size is 2^{K}(1+N/(K+1))+192 bits. Verification requires 2^K hashes and XORs.

Please report bugs as issues on this repository.

Recommended parameters (N,K)

For cryptocurrencies: (100/110/120,4), (108/114/120/126,5).

For client puzzles: (60/70/80/90,4), (90/96/102,5).

Usage

make builds the executable equihash.

Command-line utility

equihash is a command-line utility to test specific Equihash instances on your system. To show usage instructions, run ./equihash without arguments as

Usage:  ./equihash -n N -k K -s Seed
Parameters:
        N               The width (number of bits) of the generalized birthday problem, integer divisible by (K+1) 
        K               The length of the generalized birthday problem, small integer
        Seed            Seed for the problem, to distinguish between solutions. Integer.

For example, to compute Equihash using N=120 and k=5, consuming at least 32 MB of RAM

$ ./equihash -n 120 -k 5 -s 3

Alternative implementations

Zcash by @str4d

Intellectual property

The license is GPL-compatible.

equihash's People

Contributors

Stargazers

Watchers

Forkers

tjade273 renling bitcartel yz89 luke-jr optiminer collects wran621104 packetlost njlr pbbhopp staffman76 msporny jwthanh argospam duvitech-llc sailor32 jellohuang omegayalfa xyloeric diantaowang wix-alex bruce-bitcoinquark xiaoyang-zhu burneyivy prodef-tl sylvek-com samadsajanlal mstroehle sycomix linuxperia joticajulian liangma stef robertdigital blocktechbuild askflight wizardofcodes kelvinzer0

equihash's Issues

equihash integration

@khovratovich
Not, sure if I can phrase my query right. I'm not that technical into C ++, just wondering how can we implement and integrate equihash algo into our mining application? Any hint, guide or reference will be appreciated to achieve this.

Why right-shift after generating blake2b hash?

I want to adapt this algorithm in order to implement a ZCash miner. However, analysing the code I have some doubts about how XOR is computed in the various steps of the algorithm.
In function void Equihash::FillMemory(uint32_t length) hashes are generated in the following way:

equihash/Source/C++11/pow.cc

Lines 67 to 79 in 4140bd6

    
           for (unsigned i = 0; i < length; ++i, ++input[SEED_LENGTH + 1]) { 
        
               blake2b((uint8_t*)buf, &input, NULL, sizeof(buf), sizeof(input), 0); 
        
               uint32_t index = buf[0] >> (32 - n / (k + 1)); 
        
               unsigned count = filledList[index]; 
        
               if (count < LIST_LENGTH) { 
        
                   for (unsigned j = 1; j < (k + 1); ++j) { 
        
                       //select j-th block of n/(k+1) bits 
        
                       tupleList[index][count].blocks[j - 1] = buf[j] >> (32 - n / (k + 1)); 
        
                   } 
        
                   tupleList[index][count].reference = i; 
        
                   filledList[index]++; 
        
               } 
        
           }

Why, at row 74, only the most significant n/(k + 1) bits of buf[j] are stored and why the remaining 32-n/(k+1) bits are not considered?

In function void Equihash::ResolveCollisions(bool store) tuples' blocks are XORed generating a new tupleList. Neveretheless, in this way, if I have correctly understood, in each step of the algorithm, every n/(k+1) bits are not considered sequentially.

I try to make an example:
k=9, n=200

On each step I'm interested in the next 20 bits i.e. bits from 0 to 19 on first step, 0 to 39 on second etc.
In this algorithm it seems to me that in the first step are considered bits from 0 to 19, 32 to 52 on second etc because the shift register operation cut off the bits from 20 to 31

Allow CXX and CXXFLAGS specified by user

A small feature request:

$ git diff > equihash.diff
$ cat equihash.diff 
diff --git a/Source/C++11/Makefile b/Source/C++11/Makefile
index 48dd431..d26d9d4 100644
--- a/Source/C++11/Makefile
+++ b/Source/C++11/Makefile
@@ -1,3 +1,3 @@
 #paeq64 optimized
 all: 
-	g++ -m64 -maes -mavx -O3 -std=c++11 "pow.cc" "pow-test.cc" "./blake/blake2b.cpp" -o equihash
+	$(CXX) -m64 -maes -mavx -O3 -std=c++11 $(CXXFLAGS) "pow.cc" "pow-test.cc" "./blake/blake2b.cpp" -o equihash

Now things work on OS X with a modern GCC/MacPorts compiler:

$ uname -a
Darwin riemann.local 12.6.0 Darwin Kernel Version 12.6.0: Wed Mar 18 16:23:48 PDT 2015; root:xnu-2050.48.19~1/RELEASE_X86_64 x86_64

$ CXX=/opt/local/bin/g++-mp-5 CXXFLAGS="-Wa,-q" make
/opt/local/bin/g++-mp-5 -m64 -maes -mavx -O3 -std=c++11 -Wa,-q "pow.cc" "pow-test.cc" "./blake/blake2b.cpp" -o equihash
$
$ time ./equihash -n 120 -k 5 -s 3
N:	120 
K:	5 
SEED:  	3  	3  	3  	3 
Memory:		102400KiB
Testing nonce 2
Filling 2900.88  Mcycles 
Resolving 3059.88  Mcycles 
Resolving 2848.09  Mcycles 
Resolving 2651.73  Mcycles 
Resolving 2394.58  Mcycles 
Resolving 1418.71  Mcycles 
Time spent for n=120 k=5  102400 KiB: 15274.12  Mcycles 
Solution found:
 47e0c  52478  1afd2  1e6c5c  d27b8  1ce199  1ac442  1e663c  e3081  e3a5e  8cfea  1ef496  a4268  104c14  1b987e  1bf135  85696  fd07d  8938d  18961c  12f68  bb139  1980dc  1a5928  1b23c8  1cbca9  39831  15955c  72ac1  1a5ed1  18887  1cf8c8 

real	0m6.907s
user	0m6.219s
sys	0m0.655s

And a modern Clang/MacPorts compiler:

$ CXX=/opt/local/bin/clang++-mp-3.7 CXXFLAGS="-stdlib=libc++" make
/opt/local/bin/clang++-mp-3.7 -m64 -maes -mavx -O3 -std=c++11 -stdlib=libc++ "pow.cc" "pow-test.cc" "./blake/blake2b.cpp" -o equihash
pow-test.cc:102:43: warning: format specifies type 'unsigned long long' but the
      argument has type 'unsigned long' [-Wformat]
  ...%" PRIu64 "KiB\n", ((((uint32_t)1) << (n / (k + 1)))*LIST_LENGTH*k*sizeof(uint32_t)) / (1UL << 10));
     ~~~                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 warning generated.
$
$ time ./equihash -n 120 -k 5 -s 3
N:	120 
K:	5 
SEED:  	3  	3  	3  	3 
Memory:		102400KiB
Testing nonce 2
Filling 3059.53  Mcycles 
Resolving 3449.75  Mcycles 
Resolving 2931.11  Mcycles 
Resolving 2861.60  Mcycles 
Resolving 2593.74  Mcycles 
Resolving 1488.25  Mcycles 
Time spent for n=120 k=5  102400 KiB: 16384.22  Mcycles 
Solution found:
 47e0c  52478  1afd2  1e6c5c  d27b8  1ce199  1ac442  1e663c  e3081  e3a5e  8cfea  1ef496  a4268  104c14  1b987e  1bf135  85696  fd07d  8938d  18961c  12f68  bb139  1980dc  1a5928  1b23c8  1cbca9  39831  15955c  72ac1  1a5ed1  18887  1cf8c8 

real	0m7.379s
user	0m6.708s
sys	0m0.633s

And Fedora 24/i686:

$ CXXFLAGS="-m32" make
g++ -m64 -maes -mavx -O3 -std=c++11 -m32 "pow.cc" "pow-test.cc" "./blake/blake2b.cpp" -o equihash
$
$ time ./equihash -n 120 -k 5 -s 3
N:	120 
K:	5 
SEED:  	3  	3  	3  	3 
Memory:		17179971584KiB
Testing nonce 2
Filling 3796.96  Mcycles 
Resolving 3672.62  Mcycles 
Resolving 2116.09  Mcycles 
Resolving 1837.04  Mcycles 
Resolving 1500.28  Mcycles 
Resolving 548.57  Mcycles 
Time spent for n=120 k=5  102400 KiB: 13472.68  Mcycles 
Solution found:
 47e0c  52478  1afd2  1e6c5c  d27b8  1ce199  1ac442  1e663c  e3081  e3a5e  8cfea  1ef496  a4268  104c14  1b987e  1bf135  85696  fd07d  8938d  18961c  12f68  bb139  1980dc  1a5928  1b23c8  1cbca9  39831  15955c  72ac1  1a5ed1  18887  1cf8c8 

real	0m5.948s
user	0m3.826s
sys	0m2.069s

code parameters do not give correct memory usage

from the paper, n=144, k=5, should require 704 MB of memory, but the code does something terrifying on my linux box here. it says it will take 1.56GB, and then goes on to take somewhere between 5 and 6 GB of memory. also, due to how memory is handled/requested, this crashes my other computer (with only 8GB of memory, maybe it's running out of swap):

./equihash -n 144 -k 5 -s 1234 & while true; do free -m; sleep 1; done
N:	144 
K:	5 
SEED:  	1234  	1234  	1234  	1234 
Memory:		1638400KiB
Testing nonce 2
              total        used        free      shared  buff/cache   available
Mem:          15970        2660       10793         611        2517       12327
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        3341       10111         611        2517       11646
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        4028        9424         611        2517       10959
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        4723        8730         611        2517       10264
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        5409        8043         611        2517        9578
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        6118        7335         611        2517        8869
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        6845        6607         611        2517        8141
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        7577        5875         611        2517        7410
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        8311        5142         611        2517        6676
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        8496        4957         611        2517        6491
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        8496        4957         611        2517        6491
Swap:          4095           3        4092
              total        used        free      shared  buff/cache   available
Mem:          15970        8495        4957         611        2517        6492
Swap:          4095           3        4092

khovratovich / equihash Goto Github PK

equihash's Introduction

Equihash

Recommended parameters (N,K)

Usage

Command-line utility

Alternative implementations

Intellectual property

equihash's People

Contributors

Stargazers

Watchers

Forkers

equihash's Issues

equihash integration

Why right-shift after generating blake2b hash?

Allow CXX and CXXFLAGS specified by user

code parameters do not give correct memory usage

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	for (unsigned i = 0; i < length; ++i, ++input[SEED_LENGTH + 1]) {
	blake2b((uint8_t*)buf, &input, NULL, sizeof(buf), sizeof(input), 0);
	uint32_t index = buf[0] >> (32 - n / (k + 1));
	unsigned count = filledList[index];
	if (count < LIST_LENGTH) {
	for (unsigned j = 1; j < (k + 1); ++j) {
	//select j-th block of n/(k+1) bits
	tupleList[index][count].blocks[j - 1] = buf[j] >> (32 - n / (k + 1));
	}
	tupleList[index][count].reference = i;
	filledList[index]++;
	}
	}