Equihash as a new PoW algorithm

The Equihash report mentioned in our forum update a few weeks ago is now available for review: http://content.nano.org/ABDK-Nano-Equihash-Report.pdf. We were lucky to be able to work with the authors of the original Equihash paper, Alex Biryukov and Dmitry Khovratovich, to review some low k value configurations for potential use in the Nano protocol.

As previously noted the results of this research pointed at a configuration of k = 3 and n ~= 100 being secure enough and requiring enough memory to be worthwhile candidates to explore. The next steps involve validating the memory requirements we could be targeting based on the n values and getting started on implementing an efficient solver for this configuration. Any community members who are interested in assisting in any way are encouraged to give a shout here or in the #pow channel on our Discord server.

15 Likes

The report states that the current Nano proof size is 16 bytes — I thought the current proof size was only 8 bytes (ie. 16 hex characters), or is this referring to a different PoC algorithm?

You're right it is 8, I think that was an oversight in the document.

The Equihash algorithm can be rolled independent from a new Node version, am I right? If that is the case, is it planned to be rolled out during v22 lifetime?

Primarily we need a solver, I've been eyeing up SyCL as the language to do that in. We also need a patch to widen the field in the block.

No one's stood up to make those patches yet so it's unlikely any changes will be in V22.

1 Like

Hello,

I am a C++ developer in my day job. Saw a Reddit post that mentioned needing one link

Been wanting to contribute code to a crypto for a long time. :slight_smile: Recently posted in the development discord channel and just read the white paper. Could I please have more information on this problem? Is it related to the PoW alg?

4 Likes

Yes, it's related to the new PoW algorithm. Colin selected Equihash as the best fit. I suggest you speak with @clemahieu for more info.

Yes, the thing I'm looking for right now is a GPU solver for the Equihash algorithm with a configuration of k = 3 and n ~= 100.

I want to know whether this can be implemented in SYCL as it looks to be easier to integrate in to c++17 code than separate OpenCL, CUDA, or C++ source files.

Adding this support can be done in a few steps:

  • Research the SYCL support matrix of hardware/os across SYCL versions. I see v2 was just released this year but I don't know if it's widely supported yet.
  • Integrate a basic kernel into the node and work out all the build plumbing there.
  • Implement a solver that works on the above parameters so we can get performance metrics on both CPUs and GPUs to quantify its solution rate and memory consumption.
2 Likes

Thank you for the information! May be a bit slow with these initial responses. Taking some time to get the dev environment building on my local machine... Do you have any recommendations on files/lines that I should take a look in to first for getting up to speed?

4 Likes

https://chat.nano.org/ People in the discord might also be a help

1 Like

Have you considered using Verifiable Delay Functions as PoW? I'm not sure how it compares to Equihash but apparently VDFs are hard to run in parallel and you don't gain much from trying to do so.

Edit: Seems like the proof is too large to be practical for Nano.

1 Like