Update of the Equihash Algorithm

[alexcryptan]

CryptoLUX Research Group, University of Luxembourg application for Zcash foundation grants.

Our proposal is to perform a research update on ASIC-resistance of Equihash.

In the past two years since the publication of the Equihash paper there have been several relevant research and community contributions that warrant a revision of the algorithm or at least its parameters used in Zcash and several other crypto-currencies. These advances include: dedicated Equihash studies; other research on asymmetric PoWs; new studies and tradeoffs for the generalized birthday and related problems; theoretical studies of memory and bandwidth hardness; Equihash code-optimizations ( Zcash Mining Contest and further improvements); dedicated mining hardware for Equihash and other memory-hard functions. The following research questions will be studied:

• Parallel sorting algorithms and their hardware implementations
• Possible FPGA and ASIC optimizations for Equihash (200,9) and other parameters
• For which parameters Equihash offers best ASIC resistance, while still being mineable on commodity hardware (ex. most popular GPUs)
• Is Equihash still and adequate solution for ASIC-resistant mining or a new algorithm would be a better choice.

The team would consist of PI Alex Biryukov and other CryptoLUX members. The work would take 4-6 months.

[kushti]

@alexcryptan Dear Alex, thanks for the submission! Do you have milestones and dates in mind? Can you compare your proposal to the alternative approach https://github.com/ZcashFoundation/GrantProposals-2018Q2/issues/25 ?

[alexcryptan]

Sure, will do it in the next days.

[tromer]

@alexcryptan, we eagerly expect further information about the proposed milestones and research questions. In designing your milestones, please keep in mind the community's urgent need for clarity on FPGA/ASIC efficiency of the current parameters, and whether there are plausible Equihash parameters that are robustly GPU-friendly and FPGA/ASIC-resistant.

[tromer]

The grant review committee needs further information, as discussed above, in order to evaluate your proposal.

[tromer]

The Zcash Foundation Grant Review committee has reviewed your pre-proposal, including the above discussion, to evaluate its potential and competitiveness relative to other proposals. Every pre-proposal was evaluated by at least 4 committee members .

The committee's opinion is that your pre-proposal is not a leading candidate for funding in this round, and the committee therefore does not invite you to submit a full proposal. This decision is advisory, and you can still choose to submit a full proposal by June 15th, following the detailed structure described in the Call for Proposals. Note that if the full proposal is substantially the same as discussion so far reflects, then it's unlikely to be chosen for funding; and if it isn't, then we encourage you to post a draft (or at least answer any open questions) as early as possible, to allow for community feedback. Regardless of your choice, we thank you for participation thus far.

[alexcryptan]

Apologies for the delay.

An academic timeline:

• Parallel sorting algorithms and their hardware implementations:
  Survey existing algorithms to extract ideas for how to create our own list sorting algorithms. (1-2 weeks)
• Possible FPGA and ASIC optimizations for Equihash (200,9) and other parameters: a) Sorting algorithms adapted to exploit high on-chip bandwidth and reduce the effect of limited I/O capacity. (1 month)
  b) Tradeoffs in modified Wagner's algorithm to reduce its memory footprint. (1 month) c) Divide and conquer with multi-chip implementations. (1 month)

At this point (3.5 months into the project) it should be possible to provide first recommendations on:

• For which parameters Equihash offers best ASIC/FPGA resistance, while still being mineable on commodity hardware (ex. most popular GPUs) a) Exploring the parameters and their effects on our hardware optimizations as well as on software implementations. (1-2 months)

  b) Is Equihash still an adequate solution for ASIC-resistant mining or a new algorithm would be a better choice. (1 month)

Industrial timeline (taking into account "community's urgent need for clarity on FPGA/ASIC efficiency of the current parameters, and whether there are plausible Equihash parameters that are robustly GPU-friendly and FPGA/ASIC-resistant."):

• A faster preliminary feedback on (200,9), (144,5) or other parameters could be given to projects that committed to fork (from 2-4 weeks from the time of the request).

Duration: 6 months; Work effort: 9PM

[solardiz]

Dear Alex, if you don't mind answering, why is it that you're not proposing any further consideration of or work specifically on (Argon2-)MTP as an alternative to Equihash here? As I understand, your team came up with MTP later than with Equihash. Do you now consider Equihash to be superior to MTP? That's how it appears to be per @mbevand's analysis at http://blog.zorinaq.com/attacks-on-mtp/

I am asking in order to decide whether to possibly put more of my time into analysis of MTP (and e.g. its applicability to yescrypt, maybe with a ROM) or not.

[alexcryptan]

@solardiz Thanks for asking. Actually today we discussed it and were considering to include research on MTP in the proposal. It's a totally different beast though and proof size is large (ex. verification from smart contracts - expensive).

BTW answering some of your questions in #25 as far as I can see it:

Q: Is a PoW change worthwhile considering that long-term it'd only limit ASICs to "2x to 10x" advantage (and that's assuming we're "successful")? A: I think Yes, 1000 or 10 make a big difference. Putting controls on ASIC dominance is useful.

Q: Is it important that the PoW be asymmetric, and to what extent? A: Yes. To avoid DoS, lightweight clients, etc.

Q: What's the maximum acceptable proof size? A: Good question also would like to see an answer to it.

Q: What devices would validation need to be done on? A: Mobile phones?

Q: Is it still considered important that it'd be do-able from Ethereum smart contracts. A: I guess - yes.

[solardiz]

Thank you for sharing your perspective, @alexcryptan.

[tromer]

@alexcryptan, upon further deliberation the grant review committee has changed its collective mind and decided that your your pre-proposal is a promising candidate funding in this round, and the committee therefore invites you to submit a full proposal, following the detailed structure described in the Call for Proposals.

Given this rather late notice for today's deadline, we grant you a 1 week extension and will accept your full submission by 22 May 2018.

[tromer]

@alexcryptan, a crucial issue for the proposed analysis is what are the security goals and assumptions for a PoW, reflecting real-world economics and VLSI technology. People's understanding of these has been evolving over the past few years (and months!), and it would be helpful if your proposal sketches your approach to these questions.

[alexcryptan]

@tromer we really appreciate the grant committee's decision to include our proposal into consideration. We also thank for the time extension, however this might not be fair to other submitters. So here is the link to our final proposal. Full proposal

[tromer]

Thanks, and I appreciate the promptness and consideration!

For versioning, here's an in-Github snapshot of the above link: Zcash_Equihash_analysis_2018Q2-v2.pdf

[solardiz]

This is a very interesting proposal at least academically and probably also of great relevance to Bitcoin Gold and their users (I hear they're switching to 144,5) and also in terms of the team gaining greater experience with FPGAs, which I expect will be useful later on. With the very modest requirement for funding (billing at way below commercial rates for this sort of expertise and work), I think it should be funded (although I have no say in this) even if Zcash ends up going with something other than Equihash.

[alexcryptan]

Thanks @solardiz I think BTG, ZEN and ZCL all plan to switch to 144,5 at different points in time. It might be wiser for them to switch to different parameters rather than to be in a single basket. Also I am not sure if 144,5 is the best choice now, given that it was suggested more than 2 years ago. Without doing such study it is really hard to tell.

[sonyamann]

I'm thrilled to inform you that the Grant Review Committee and the Zcash Foundation Board of Directors have approved your proposal, pending a final compliance review. Congratulations, and thank you for the excellent submission!

Next steps: Please email josh@z.cash.foundation from an email address that will be a suitable point of contact going forward. We plan to proceed with disbursements following a final confirmation that your grant is within the strictures of our 501(c)(3) status, and that our payment to you will comply with the relevant United States regulations.

We also wish to remind you of the requirement for monthly progress updates to the Foundation’s general mailing list, as noted in the call for proposals.

Before the end of this week, the Zcash Foundation plans to publish a blog post announcing grant winners to the public at large, including a lightly edited version of the Grant Review Committee’s comments on your project. The verbatim original text of the comments can be found below.

Congratulations again!

Grant Review Committee comments:

The Equihash proof-of-work function, used by Zcash and forks thereof, was motivated by ASIC-resistance. With its current parameters, it no longer achieves that goal (at least 2 ASIC mining products recently entered the market, with a huge efficiency advantage over GPU mining). This grant is motivated by several crucial concerns:

(a) What is potential ASIC advantage with the current Equihash parameters, and to what extent can GPU and FPGA catch up to mitigate the prospect of total ASIC dominance?

(b) Create better, open-source mining software for GPU and/and FPGA. This would mitigate mining hardware centralization, as well as the unfortunately current state where the state-of-the-art GPU mining software is closed-source and proprietary.

(c) How can the advantage of ASIC vs. GPU/FPGA be shrunk with better choice of Equihash parameters or alternative algorithms? This informs the ongoing discussion about PoW changes.

Interest in (b) and (c) is predicated on desire to achieve mining decentralization by enabling mining using general-purpose hardware. It has not been established or universally agreed that this is the optimal approach (appealing arguments have been made that ASIC's high cost of switching increases security due to incentives and unavailability of PoW renta)l. None the less, the research and development proposed under this grant is worthwhile both in informing that high-level discussion, and in executing a potential decision in favor of ASIC-resistance.

The proposers are well-qualified, including the author of Equiash and an expert in efficient cryptographic implementations, both of which are renown academic cryptographers. The proposal demonstrates cognizance of the state of the art, challenges and opportunities.

The budget is reasonable for the amount of work. Timing, deliverables and budgeting are well specified. We recommend for the proposal to be funded (in its full proposed scope), and may provide advice on prioritization as the community discussion and complementary research evolve.

[mms710]

@alexcryptan Hi! I'd love to help provide any support you might need from the engineers and scientists at Zcash Company. Would you be interested in getting a more regular line of communication set up between you and Zcash Company engineers/scientists so you can ask questions or get help? If so, would you be okay using a Rocketchat channel or do you have another preferred method of communication?

[alexcryptan]

Success of this project depended heavily on GPU/FPGA implementations of Equihash for different parameters. However our project collaborator Dag Arne Osvik failed to deliver such implementations for the project milestones/deadlines. Without implementations further analysis planned for the project was not possible.

The good part is that grant funds stayed with the Zcash Foundation and thus should be available for other projects.