Calculate solutionSize

hi, reading this post “Easy to follow description of the equihash algorithm” who could me please explain this “solution length (3 bytes in special encoding always the same value 1344)” ?

Block header
nVersion + hashPrevBlock + hashMerkleRoot +hashReserved + nTime + nBits +nNonce = 140 Bytes

sa-solver give me solution of 140 bytes = 1344 bytes

to do sha256 hash how i have 140 and 1344, but i cannot retrive solutionSize
( 3 bytes | solutionSize | compactSize uint | The size of an Equihash solution in bytes always 1344)
how do I get solutionSize ?
how can do this special encoding ?

Cheers

An Equihash instance has two parameters: (n, k). An Equihash solution is a list of numbers of length 2k. For Zcash’s current Equihash parameters (200, 9) that means a solution is a list of 512 numbers.

Now, if we stored those directly in the solution header, we’d need to pick a “size of number” that fitted all possible values for these numbers. A reasonable guess might be a standard 32-bit number (4 bytes long). However, that would have made the solution stored in the block header 2048 bytes, containing a lot of wasted space (many zeroes).

Instead, what we did was store the numbers in “minimal form”, by leveraging the fact that we know what the largest possible number in an Equihash solution can be. Part of the way Equihash works is that we start with a list of 2(n/(k+1))+1 hashes. The numbers in an Equihash solution correspond to these hashes, which means that the largest number in an Equihash solution will be 2(n/(k+1))+1-1, which can be stored in (n/k+1)+1 bits. Therefore, the minimal size of an Equihash solution in bytes is:

2k((n/k+1)+1)/8 = 2k-3((n/k+1)+1)

If we plug in the current Equihash parameters for Zcash, we get:

29-3((200/9+1)+1) = 64*21 = 1344

Now, we could have just stored those 1344 bytes directly in the Zcash block header, but we might want to change the Equihash parameters in future. So, we instead store it as a C++ vector of bytes, which includes a length. The Bitcoin codebase we built Zcash on already has a way of encoding vectors: a CompactSize containing the size, followed by that many bytes. Here’s how you read a CompactSize:

  • Read the first byte.
  • If the first byte is less than 253, that byte contains the size.
  • If the first byte equals 253, read the next two bytes as a 16-bit little-endian integer.
  • If the first byte equals 254, read the next four bytes as a 32-bit little-endian integer.
  • If the first byte equals 255, read the next eight bytes as a 64-bit little-endian integer.

Since the current Equihash minimal size is 1344 bytes, that gets encoded as fd4005, making the total encoded length of an Equihash solution 1347 bytes for Zcash’s current parameters.

tl;dr

To parse the Equihash solution field in a Zcash block header, parse the first few bytes as a CompactSize, then read that many bytes in as the solution itself. Do not assume it is always 1347 bytes!

2 Likes

ur reply helped me a lot, but where is the 3-byte stored ? when I count the size of nSolution, I only get 1344 bytes.