Development Update: Research for a new PoW algorithm

Guilherme Lawless
Jan 9 · 5 min read

In September and October of 2019, we shared details of a new Proof-of-Work algorithm, designed to help protect the network from spam transactions, that we were exploring for use with Nano. Subsequent evaluation by community members and experts revealed shortcuts in the algorithm that would allow PoW generation without the memory-hardness intended in the design. As a result of these discoveries, we removed the Nano PoW algorithm from potential release, and further research continued.

The results of our research have highlighted that validating a new PoW design brings higher risks and tradeoffs for the effort involved compared to adjusting the implementation of existing algorithms. Our previous analysis had ruled out many options based on specific desired characteristics, and we’ve spent time revisiting some of those requirements. We have worked to identify whether there are configurations available which provide the right set of tradeoffs to give us more effective spam prevention in the near term.

This update will provide an overview of the status of the research, which has focused heavily on Equihash as a leading candidate for a new PoW solution.


Nano’s design of replacing transaction fees with a small proof-of-work (PoW) to deter attackers from spamming the network is an elegant and user-friendly solution to a common problem in peer-to-peer value transfer networks. These issues include complicated user experience and emergent centralization problems, which are consequences of rewarding entities of a decentralized network for their active participation.

This design is challenging from the perspective of finding applicable algorithms that cover all of Nano’s requirements:

  • Lightweight proof to minimize overhead
  • Fast verification to minimize resource usage
  • Memory-hardness to ensure fairness with relation to specialized hardware
  • Free of amortization to avoid an artificially high average difficulty and centralization issues
  • Adjustable difficulty to allow transaction prioritization
  • Sufficiently fast at base difficulty
  • Use enough memory to make specialized hardware prohibitively expensive
  • Be simple and mathematically proven

Specifically, fast verification implies a high degree of asymmetry in generation/verification, which can’t be guaranteed with memory-hard algorithms and rules out most of them. Many of these algorithms also require initializing memory to verify each solution, which is not acceptable. Another requirement that many of these algorithms do not meet is fast generation at base difficulty. While this is not a problem for traditional blockchains with long block times, the Nano user does not want to wait a minute or more in-between transactions.

Regardless, some aspects of Nano are also favorable in the search for a new, fairer PoW algorithm. To be accurate, this is due to using PoW as a spam deterring mechanism and not for consensus. Competition between participants is not a race where the smallest of advantages awards the winner with more value. It is merely used for prioritization of transactions and discourages from using as many resources as are available. It means that specialized hardware (e.g., an FPGA) that achieves only small gains over general-purpose devices are not problematic.

In the past months, we have looked for an algorithm meeting all of the above requirements. The most promising candidates are Equihash and Cuckoo-Cycle variants. Here we will focus on the applicability of Equihash, which, due to being based on a well-studied topic — the generalized birthday problem — is the preference.

Equihash solves two of the above requirements: fast verification in memory-hard algorithms, and fast generation at base difficulty. Additionally, it’s also a highly tunable algorithm, with two choices of parameters that together change properties of memory and time requirements, as well as the proof size and verification costs. We encourage curious readers to check out the original Equihash paper for a full understanding of the algorithm, and it also provides an overview of some of the problems described in this article.

Equihash has been a popular algorithm and has seen usage in multiple cryptocurrencies for mining. Its tunability has led to numerous configurations appearing, each with different requirements of memory and time. Their proliferation is also attributed to specialized hardware, which provides a considerable advantage for the first configurations of Equihash, which only required about 144MB of memory. Subsequent configurations appeared requiring up to several gigabytes of memory, but also compromising on verification costs and minimum time to generate.

For the most part, existing configurations have focused on requiring enough memory that specialized hardware does not give an advantage of several orders of magnitude. This advantage would be a problem not only for cryptocurrencies with mining but also in the context of the spam-prevention purpose in Nano. Regardless, even for configurations requiring a large amount of memory, adversary solvers have been explored, which significantly increase energy efficiency, but with marginal gains in computation speed, as they are bound by memory bandwidth. Fortunately, these are most problematic for the mining use case.

The applicability of Equihash to Nano requires exploring a subspace of parameters that have mostly not yet been seen in the wild. The two parameters are n and k, and to have a sufficiently small proof size, thus minimizing overhead in blocks, we would require a maximum k of 4. Only one existing open-source implementation uses a value this low, which does not yet provide us with enough confidence to be used in a spam-prevention setting. Contacting the Equihash authors, we were also told that using this set of parameters requires additional study.

Re-engineering the Nano node to use a new PoW algorithm is a significant effort investment, which we would like to proceed with only when there is more assurance that we have selected the right algorithm and parameters. As such, we have not yet selected Equihash, despite its promise.

This update serves to open the discussion, and we hope to bring the Nano community together to discuss the applicability of Equihash for Nano. We have started a new topic in our forums to help manage the discussion and research around the possibility of Equihash, which we anticipate will take additional time to sort through.

Meanwhile, we have listened to the community’s suggestion to consider moving forward with the easier task of increasing the minimum network difficulty. Since the creation of RaiBlocks, there have been substantial hardware improvements, and, nowadays, users have more computing power available to them than some years ago. This advancement in computing power is why we are exploring a new PoW algorithm and why calls for increasing the minimum PoW difficulty in the meantime may be warranted.

However, a minimum difficulty update, just like a full algorithm update, requires the creation and propagation of a new set of epoch blocks. In our latest release, Lydia (V20), we have added most of the support necessary for new epochs. However, some more effort is still required, and this also means around 1 million blocks would be added to the ledger as of this time.

We are interested in community opinion on a new epoch block being deployed for updating the difficulty. Raising the difficulty will give us more time to discuss the applicability and assurance provided by Equihash or other options. Note that even the difficulty update will require a new node release.

The questions around whether or not we should do the minimum difficulty increase now, and if so to what degree, have been added to a new forum discussion as well. So head on over to the forums to help us find the right path to making PoW more effective on the Nano network.

Nano

The best place for all of the latest Nano updates, developments and interviews. Brought to you by the Nano Foundation.

Guilherme Lawless

Written by

Nano Developer, Roboticist

Nano

Nano

The best place for all of the latest Nano updates, developments and interviews. Brought to you by the Nano Foundation.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade