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.
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!