Easy to follow description of the equihash algorithm

Please, somebody explain this part for Dummies.
I can not figure out what the tree should look like.
How to store values and indexes …

You may find some clues in the presentation https://www.cryptolux.org/images/3/3b/Equihash-ndss.pdf slides 15-19, and in the other resources from https://www.cryptolux.org/index.php/Equihash

1 Like

Hello, I’m new to this forum. I’am a programmer with 20 years of experience and I’am very good in code optimizations. Just started to write my own Equihash solver. I am writing it in other less common language Pascal (Lazarus). Pascal is manny times much more faster than other languages in case of speed, so I want to try my coding skills. Firstly I started to write methods to communicate with pool, it is done now, secondly i have written my own Blake2b algo in pure assembler. It is faster or at least as fast as other implementations. Now I’m attempting to write Wagner’s part of Equihash but stuck on Blake2b result. I have read many of papers about Equihash but they are not clear for me or there are some omissions in these publications.

Can someone direct me to proper way of executing Blake2b?

Let’s assume that I have an input given on this page:
040000007003225F30E1015EE14609B222E6036B7572963E18355688A966BB0E00000000E53B8DC142BBF69584F26B5F1D2125B79F238E77D04A37CDFAE64D3CFE9B2E730000000000000000000000000000000000000000000000000000000000000000C85BDA595DB6121C4FFFFFFF05000000000000000000000000000000000000000000000000000000

@mtve says that input should be concatenated with 4 Bytes of hash index. So I assume it will be 144 Bytes long (140 base + 4 index) giving input to Blake2b like this?:
040000007003225F30E1015EE14609B222E6036B7572963E18355688A966BB0E00000000E53B8DC142BBF69584F26B5F1D2125B79F238E77D04A37CDFAE64D3CFE9B2E730000000000000000000000000000000000000000000000000000000000000000C85BDA595DB6121C4FFFFFFF0500000000000000000000000000000000000000000000000000000000000001

Should index strat with 0 or 1 (above is 1) ?
One of parameters in Blake2 method is output length. What should I set in this param?
If it is Blake2b-256, should I set 32 (32 bytes x 8 bits = 256). Am I right to this point?
Can someone provide result of fist Blake2b first iteration with given header?

I understand from papers that I have to truncate result to 25 Bytes? Am I right? Truncate left or right?

Can someone give me a proper explanation to this point what should be done with header, parameters to Blake2B and finally result of this function? Maybe someone has a EXE with debug mode giving also results of Blake2b?

Thanks in advance.
Lukas.

4 bytes of index should be in little-endian order, “01000000” for index 1.

index starts with 0.

BLAKE2b output length should be 50, and don’t forget so-called “personal” parameter of BLAKE2b instance which is string “ZcashPoW” and Zcash parameters N=200 and K=9 again as 4-bytes intereges in little-endian order.

Resulting 50 bytes of each BLAKE2b hash you split in the middle, which gives you two 25 bytes strings.

I believe first correct strings for this blockhead are given earlier in this thread, i can recheck if you get another strings.

1 Like

I managed to retrieve good hashes. Thanks for help. Moving on forward with miner.

Hi
I’m a little confuse
with this header
040000007003225F30E1015EE14609B222E6036B7572963E18355688A966BB0E00000000E53B8DC142BBF69584F26B5F1D2125B79F238E77D04A37CDFAE64D3CFE9B2E730000000000000000000000000000000000000000000000000000000000000000C85BDA595DB6121C4FFFFFFF05000000000000000000000000000000000000000000000000000000
and after + 00000000 and 01000000 and 02000000 then compute blake2b(50) I received these , that are different with your result

index 0 ====> aad5e0ace4562e371912fd1b2660f6e10e4456093e1f8a6ad8d4bdbe46accc087f636a1abcaab319abb85bfd4cfe987cf077

index 1 ===> bfd3bcba82f35bd49d3551bef1ce1d0cd7bf01a32ee43a36eac11cd627fbc5499cf8d1714fd4b63c96d5519ae3e5c99c3423

index 2 ===> 1fcb2423d9d5717712af4ffd5f5b95b6b5e230a896b8eb706d865dcfa6ac309d5a6ab50dbcd3162a818d5e1710bad0d36d9b

I used this implementation https://github.com/metadings/Blake2B.cs

What did I do wrong?
thanks.

I can edit my post I post wrong value the correct is

index 0 ====> f4ad238782320cc409c974795a1e117df01149a1f1068b0bd9863bb88e67f276f41c83e358d1d92842978fb53cc3eab0d184

index 1 ===> 5ce08e3f788e241fa87d2be5618c09538f7815fe1137b1d05c3a5da1957254b1e302291025c0011246ed923024b784d1c9e3

index 2 ===> 24fb72d01d3e1bd4cc69cd1ef3783b285159fb8a036b0e0fd8bdfbb062bd6e3f3add331bb474eccfd999188a20408d88a23d

i’ve managed to reproduce your result, when “personal” initialisation parameter of BLAKE2b is missed.

it’s called Personalization in that implementation:
https://github.com/metadings/Blake2B.cs/blob/master/Blake2B.cs#L157

it must be equal to string “ZcashPoW” followed by N=200 and K=9 parameters, or 5a63617368506f57c800000009000000 as byte string.

2 Likes

Thanks it is correct now, so we have this indexes and hashes

0 302b73bb4f258cf918ad9d9555321f5f7a9e88392a1a4b674e
1 4c420c5ecba665b5c412edda230dc93a4fce4956bc8f8dce74
2 016ee597094962b6410ecd9d23eaf4f513d84746e956facfae
3 9ce8cb1147f17ac3c44113d59e471b9d4c05f5f431894a9f91
4 ed141f007be5df50dc2bd9160eac96768257196a35b1361200
5 5d83aa700ee391015da178ff48e2a6797610891772b9896cfe
6 aaeae37ac85690fb3d523a9f8620555f945711416bfa54c3e9
7 ce78ce97072f416ab1654d1671d004cebba0e6fdaaf642379a
8 a594b8f6d3c71658a668256510423d66d6a1eba2bd572350fb
9 94399347c41cf339fbb347aeed0222bf97f78d91d0ff9a5e7b
 .
 .
 .
2097151    421f6e06f91109b7c2d82a1ac39da0e059597c32fae49d0190
2097152    a73ced94afd667fe4a9370dd2d1fbcb9cf58662d80285bd4f6

now we have to select 512 of them that make xor of them 0 and also this 2 rules

1-“on each split by two of your indexes the left ones must be ordered"
2-” on each split by two of your indexes resulting XOR of strings must have 20*height zero bits from the left. More on algorithm is in the part II."

Could you please explain a little more about this 2 rules?

and also if it possible for you please solve this and give those 512 indexes that satisfy these rules ,it really helps me to understand more.

thanks.

if i’m not mistaken, that block header gives only one solution
https://gist.github.com/mtve/f35c090f4d93e4e71b74a6544fa5255f

rule 1 means that on any branch of index tree - branches are ordered, so the tree is uniquely (deterministicaly) represents the solution, and you can not easily get another solutions by permutation of branches.

rule 2 means that Wagner’s algorithm (or similar) must be used, and tree branches as they grow xored give more and more zeroes, i.e. original_string[solution_idx[0]] ^ original_string[solution_idx[1]] as well as 2^3 will give 20 zero bits from the left, (0^1)^(2^3) will give 40 zeroes etc.

1 Like

thanks,

ok now we have index and hashes like

920===> d6458dc189a897947610eade622854d2bcabeb3f7090dcc43a
1c3ff8===> d6458149a64d9e5bc98a3c9f71b3b73a1facf1c02ca4552761
301ef ===>4f3e1495f585c70f2003cca153b56006e8b0fd59b90fc54bfb
527cc ===>4f3e181ddaa2e9812d0efc267736e0a94bdb266f43258b7cbf
135926===> f6831f45ab45dac968b67b101616e4ebaeee7a3c0057830e31
13f94c===> f683137d906d11dfaeab4653664338c799b33d9b6399ad4667
14e9d0 ===>f17effdf42832b71adad0a3c4878dffe5ef57e44af33ae90fd

so next step is to make sloution block as you wrote is " solution itself, which is encoded by 21 bits per index, "?

What is this mean ?how we can encoded index in 21 bit?
is it correct?==> 920+1c3ff8+301ef+…==>000000000100100100000+111000011111111111000+000110000000111101111+…

////////////////////////
Actually there is a misunderstanding for me,after making blake2b hashes we have to chose 512 of them that make xor zero for finding this 512 there is an algorithm with name of wagner ! it is no mandatory to use this algorithm yes?or no? actually we can find another way for chose this 512? am i right?

///////////////////////
those two rules steel unclear for me maybe because I have not understood wagner algorithm yet and I could not find any paper for this and most paper is just for optimizing his algorithm ,Is there any guide for wagner pure?

Equihash documents are here
https://www.cryptolux.org/index.php/Equihash

Original paper from that page explains Wagner’s algorithm, slightly academic.

When algorithm is solved and we get those indexes (920, 1c3ff8, …) we pack them into Zcash block. Since each index is between 0 and 2097151, or 21 bits width - we just encode them tightly as you’ve shown, that’s correct.

1 Like

really thanks mtve you really help me

just one point about this part

“Actually there is a misunderstanding for me,after making blake2b hashes we have to chose 512 of them that make xor zero for finding this 512 there is an algorithm with name of wagner ! it is no mandatory to use this algorithm yes?or no? actually we can find another way for chose this 512? am i right?”

we must use wagner algorithm? or we can use any other algorithm for finding 512 indexes? (Actually I want to know the goal is to find 512 indexes that make xor of them zero?)

thanks.

yep, the goal is to choose 512 strings from 2097152, such as xor of them is zero (with some additional requirements to the order of those strings).

you may invent any algorithm. however, the generally accepted view is that Wagner is the only possible (and only its optimizations matter). you are very welcome to disprove this and break zcash mining market.

1 Like

@mtve @str4d Can we choose random 512 strings from 2097152 to bring xor value of them as 0 or is there any order we need to follow?

some order is required. without an order you will get too many solutions for free by permutations.

each of 512 indexes must be unique.

xor of string[index[0]] with string[index[1]] must begin with N/(K+1)=20 zero bits, string[index[2]]^string[index[3]] the same etc. index[0] must be less then index[1], index[2] < index[3] etc. let’s call it the first step.

string[index[0]]^[[1]]^[[2]]^[[3]] must begin with 40 zero bits, etc. index[0]<index[2], index[4] < index[6], etc. it’s the second step.

repeat for other steps up to the step 8, [[0]]^…[[255]] must begin with 160 zero bits, same for [[256]]^…[[511]], index[0] < index[128], index[256] < index[384]

and at the final step 9, index[0] < index[256] and xor of all chosen strings is zero.

Thanks @mtve On each step next 20 bits should become zero or can we use any other algorithm to bring xor of 512 strings (string[0] ^ string[1] ^ string[2]^ … string[511]) to zero? Because I’m planning to write an algorithm which finds strings as the order your mentioned above and bring xor of them to zero.

yes. consider 512 indexes of strings as leafs of a binary tree with depth 9. on each branch arms are ordered, and total xor of branch has leading zeroes (20*height bits).

unfortunately this is required by Equihash and so Zcash, because it follows from Wagner’s algorithm.

perhaps natural order of indexes without intermediate xors would be more aboveboard, but it’s not our case.

anyway, even if your algorithm will not provide required order, it could be interesting, so please publish it.

@mtve Thanks again. Sure, once I find it working I will share the github URL for public :slight_smile: And how the solutions are verified by other nodes? Can you explain or share c/c++ code which does this part?

here is from Zcash itself in C++:
https://github.com/zcash/zcash/blob/master/src/crypto/equihash.cpp#L721
and here is my in perl:
https://github.com/mtve/yazecminer/blob/master/pool-emu/equihash.pm#L7