Equihash as a new PoW algorithm

Protocol Design
#1

Related discussions:

Following our update on research done to find a replacement PoW algorithm, this topic is to discuss the applicability of Equihash to Nano's use-case, that is, spam prevention.

Equihash has two parameters to tune (n,k), which control the length and number of collisions that must be found. As outlined in the article, we are looking to have the lowest value possible for k, resulting in a smaller proof and easier validation (2^k hashes are required to validate a proof).

The reference implementation for a k=4 configuration I found is a (125,4) parameter configuration from ZelCash - ZelHash:

However, this implementation is only used by that coin in particular, as far as I know.

Another interesting take on Equihash is BeamHash II, which introduces the EquihashR family to have the algorithm favor more memory operations than hashing, thus reducing energy consumption.

To discuss other algorithms please create additional topics.

6 Likes
Increasing minimum work difficulty with current PoW algorithm
Work generation: Friction points
Work generation
#2

After seeking out experts on the Equihash algorithm we were finally able to get help researching a novel configuration of Equihash that appears to satisfy most of our requirements for a new PoW algorithm. This configuration is k = 3 with a few options for the n value. The most interesting from our perspective is n ~= 100 which results in a proof size of 26 bytes and requires an expected 3.1GB of memory for optimal solving. With k values lower than 3 there were some possible time memory tradeoffs that would undercut the security margin. With Equihash, lower k values are harder to solve and consume more memory but fortunately, also have smaller proof sizes.

The report is still being finalized and is expected to be published soon, but we wanted to provide the update to the community early to draw more discussion around these potential features. Actualy implementation of an efficient solver will be getting underway soon and until that is in motion, the benchmarks and other useful data for how it performs on specific hardware will not be available. But perhaps one area up for discussion is what the ideal memory requirements should be - if you're interested this thread is a good place to join the discussion.

18 Likes
Minimum memory requirement in a new PoW algorithm
#3

For comparison, the current PoW algorithm results in a proof size of 10 bytes, correct? I'm curious if the recent discussions about payment IDs are pushing block size against the limits of the UDP packet size -- what's the available ceiling for proof size?

#4

My understanding is that UDP size is not a limitation following the transition to TCP

2 Likes
#5

If there is a DoS attack in TCP/IP world, we would use firewall to block malicious traffic instead of changing actual protocol to make it hard to DoS us. Following this logic, would it not be better to create a blacklist of malicious Node IPs or nano addresses and vote for it using voting mechanism that you've already implemented? What new attack vector would this solution bring? Forgive me for my arrogance. Thank you

#6

You do not want to track IPs, privacy issues and they can be changed easily (what's the point than?)
You do not want to block addresses (Some addresses might have valid use cases to send many transactions).

Essentially what you need to do is allow all transactions to go through (including possible spam transactions) as long as they have no / minimum impact on other transactions.

1 Like
#7

novel configuration of Equihash that appears to satisfy most of our requirements

Which points from below do you think Equihash does not address in a satisfying way?

  • 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

And any ETA on when this will hit testnet/mainnet?

#8

Will this allow PoW to be done on mobile devices locally more efficiently or it has no impact compared to existing algo?

I realize that currently, mobile devices do dPoW (mainly because app stores do not allow it as it is considered mining) but is there a plan to allow mobile devices to do their own PoW as an option? (Maybe a separate app to be downloaded and side loaded? not ideal but I think it will be beneficial long-term to not rely on centralized servers to do dPoW)

#9

I have not deeply researched Equihash yet, especially not the Wagner algorithm, but I am curious on which underlying hash function are you planning to use?

If the intention is to use Blake2b or say, SHA3, my question is, have you considered that using a non hardware-accelerated hash function would indefinetly put PCs and mobile devices at a disadvantage against specialized hardware?

I have suggested the idea of investigating AES instead. Yes! it may sound crazy at first but if you think about it, AES is the single most important crypto algorithm for network server hardware. An efficient, non GPU-based implementation is critical to run any server or data center. This means that hardware designers would put a lot of research efforts to optimize it to have servers support secure network speeds in the Terabit scale and more. For example: A Ryzen 9 3950x can get to about 22GByte/s in the TrueCrypt AES benchmark.

Yes, it's not trivial to effectively adapt an encryption algorithm as a hash and might require a lot of care and specialized knowldege. But if you do manage to do it, it could be very effecive in the long run.

As an example I gave a simple, non memory-hard approach based on two keys where you have to find an i such that E_k1(i) ~= E_k2(i). Seeding a cipher with two different keys is (roughly) equivalent to defining two different hash functions, and the comparison I'm performing is equivalent to finding a partial collision between two different hash functions (over the same inputs). I believe this approach should be secure (reversibility of encryption may not be of any help here) but I am not a cryptographer. BTW I have asked about this several years ago in Crypto StackExchange and the response was that it is most likely secure.

Reading a bit about Equihash I suspect that it is possible to adapt AES to be used as its underlying hash function though it might require some bigger changes to the algorithm. This seems like a lot of work but it might be worth it.

In any case I think that in general, changing a PoW is a big change and also a special opporunity to try improve over the conventional so this kind of research may turn out to be fruitful in the long run.

#10

That's a good idea. I'm less sure about using an encryption algorithm as a hashing function but we should test the sha256 x86 opcodes. Intel® SHA Extensions

#11

Conceptually it should be easier for mobile devices to generate the proofs, idle memory cells consume less power than active CPU gates though really we need to run benchmarks to see where different hardware lands.

I wouldn't refer to offloading PoW generation as centralized as it could be offloading to another device owned by the same person e.g. your mobile phone could make a request to your home computer for generating proofs.

3 Likes
#12

I intentionally concentrate on AES and not SHA acceleration because I believe that hardware manufacturers will have more incentive to optimize it in the future (for example having less and less clock cycles per AES instruction and more instruction parallelism). Encryption is something that is absolutely critical to do at high speed for server and client hardware (and the demand keeps growing at a possibly exponential rate). Hashing is not. Even if SHA is accelerated (like in many newer CPUs), I don't think it would compare with with the amount of engineering given to encryption, especially for server hardware.

I feel like the current Nano approach to provide specialzed services for PoW might actually be a good idea in the long run. But with greater adoption, it is might be eventually inevitable these services would need to start collecting fees. So transactions may still be free but PoW would be "rented" from server farms and payed for using Nanos. Even if using memory-hard PoW might prove to be more effective, it may still turn out to be preferrable to do on the server side, because most users wouldn't care to pay a couple of cents for the PoW service. Also PoW will become more expensive (in terms of CPU) when the network becomes more popular.

I understand using encryption doesn't "feel" right. It's not supposed to feel right! that's exactly why I'm suggesting to consider it. It doesn't feel right because professional cryptograpers are dedicated to proofs and peer-reviewed research, and asking them to use a Cipher as a hash would seem to them like a waste of time and opening up to unexpected "holes". But in practice, Nano only uses PoW to prevent spam, not to secure transactions, so having the possibility of some obscure theoretical attack might not matter at all in practice.

I do feel it would be better to consult with professional cryptographers for this (I'm not one of them).

1 Like
#13

I think I need to clarify a bit where I'm coming from:

My reasoning is:

  1. PoW should ideally run as efficiently on CPUs as on GPUs and ASICs.

  2. I don't think that mobile devices would ever be able to compete with PCs and servers when it comes to PoW. Even if using the most effective methods, it would still be a battery drain and inconvenience to most users.

  3. I accept the fact that data centers provide better energy efficiency and cost-effective processing.

  4. I predict that mobile users would most likely prefer to pay (though very little, with Nanos) to run PoW on datacenters (the payments wouldn't be immediate, per-transaction as that wouldn't make sense, more likely per x transactions).

  5. I prefer that PoW services would not require GPUs on the server side. This would lower the barrier of entry to any commodity server hardware.

  6. Even better: it would be great that end-users could run PoW on their PCs or even browsers (in exchange for Nanos) and sell it.

  7. One promising approach I can think of that may satisfy these requirements is using encryption as a basis for PoW. There might be others though.

So it's mostly about preferring CPUs to GPUs, not GPUs to ASICs.

BTW: I've actually spent several hours trying to find benchmarks for AES on many types of devices and it turned out surprisingly hard to find up-to-date results. Especially on mobile. I've read research about GPU and FPGAs but most of it seemed out-of-date. There are also TLS acceleration cards but I couldn't find hard benchmarks.

2 Likes
#14

Early on in research we were looking for a proof size that was no larger than the current one, so the lightweight proof is the main tradeoff. Thankfully Equihash options aren't significantly larger with options in the 20-30 bytes range. Other requirements seems to be fine, although an actual implementation will be needed to ultimately validate them.

We don't currently have an ETA for this implementation yet.

1 Like
#15

Here's a possible one-way hash function defined using only the encryption operation (no need for key scheduling - this is an intentional design choice because I don't believe key scheduling instructions would be as optimized as encryption and decryption instructions):

let k1 and k2 be nothing-up-my-sleeve keys (arbitrary constants like "foo" and "bar").

The hash is defined as:
H(x) = E_k1(x) xor E_k2(x)

I would be highly grateful if you could forward this to cryptography experts that are patient enough to try to make constructive suggestions (and even suggest alternatives if they find faults).

If the issues with this are mainly theoretical, and for purposes of PoW don't matter (we're not signing or authenticating documents here) then problem might be solved. Just use this in place of a hash function and you've got hardware acceleration on virtually all devices (including mobile), and on some servers supporting TLS acceleration (like with Intel QuickAssist) the hashing may possibly approach ASIC performance.

#16

At the very least, the selection of the hashing function doesn't need to be decided with the move to equihash. We can move to equihash and then change the internal hashing function for performance gains.

I took a look at the instruction groups, it looks like there are sha256 instructions that get between 10-15cycles/byte. https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/sha-256-implementations-paper.pdf. The AES instructions are 3-4 cycles per byte, which is faster than I expected, I don't know why hashing would be a more difficult operation than encryption. https://software.intel.com/content/dam/develop/public/us/en/documents/10tb-24-breakthrough-aes-performance-with-intel-aes-new-instructions-final-secure.pdf. Blake2 already costs 5-6 cycles per byte https://eprint.iacr.org/2013/322.pdf.

We should consider the gains / risk ratio. Using an established hashing function means we don't need to verify a custom method.

#17

The construction I'm trying to produce is called a One-way compression function.

Here's a quote from Wikipedia:

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output.

One-way compression functions are for instance used in the Merkle–Damgård construction inside cryptographic hash functions.

One-way compression functions are often built from block ciphers. Some methods to turn any normal block cipher into a one-way compression function are Davies–Meyer , Matyas–Meyer–Oseas , Miyaguchi–Preneel (single-block-length compression functions) and MDC-2/Meyer–Schilling , MDC-4 , Hirose (double-block-length compression functions).

Most of these constructions (as far as I've checked) make use of key scheduling (they initialize a different key for each hash).

I'm trying to find one which doesn't (only encrypts/decrypts).

The special characteristic here is that hash collisions are not very important for PoW (There's no issue of, say, a document being faked because someone was able to find some other document that hashes to the same value).

It could be that the method I suggested works well but is slightly more prone to hash collisions than the above constructions (or not). That's what I'm trying to find out.

It is likely that someone already published (or at least researched) something of this sort (possibly more than 20 years ago).

An expert who is familiar with the research may be able to identify the suitable papers.

Honestly, most of the risk I'm seeing is just the embarrassment might be flawed in some way. So if you ask in my name ("Some random person on the interwebs sent me this. Is it good enough for PoW?) it may save us both the embarrassment.

As for the measures for HW acceleration. I think a reasonable metric would be simply the ratio of the performance of the best accelerated version to the best unaccelerated version of the hash. The instructions themselves are for one round, this means ciphers or hashes with different number of rounds can't be compared to each other (I'm not a hardware expert though).

The most comprehensive benchmark database I've found so far for various CPUs are the SiSoftware benchmarks which seem up-to-date. Top score for non-engineering sample CPU is 88 GByte/s - 2x AMD EPYC 7542 32-Core = 1.375GByte/s per core (I don't know which cipher is used but I assume it's AES-128).

Edit: AMD EPYC 7F72 24-Core gives 57.07GByte/s. That's 2.375 GByte/s per core. The stock clock speed is 3.70GHz (assuming it's not overclocked). That averages as 1.55 cycles per clock (I'm still not 100% sure which cipher is being used here though).

1 Like
#18

I have opened a question on Cryptography StackExchange:

As well as Reddit r/cryptography:

1 Like
#19

Based on an answer I received on Cryptography StackExchange (from a user who noticed my Reddit post) the construction I describe is called "XOR of independent permutations" (XORP) and is considered very secure.

The earliest cited paper is a 1998 paper called Luby-Rackoff Backwards: Increasing Security by Making Block Ciphers Non-invertible (which cites a 1988 paper called How to Construct Pseudorandom Permutations from Pseudorandom Functions by Luby and Rackoff that describes the inverse problem: PRF -> PRP).

The 2018 paper cited in the answer (containing several proofs that are a bit beyond my abilities) is called Full Indifferentiable Security of the XOR of Two or More Random Permutations Using the χ2
Method. It builds on several papers providing proofs for various cases where the construction is generalized to n XORs (apparently even and odd values of n seem to matter) and make a distinction between the case where the keys are public and when they are private (kept as a secret).

This construction has also been proven to be secure beyond the birthday bound (from the SE answer):

Notably, XORP is secure beyond the birthday bound. If the permutations are on n-bit strings, then an adversary who makes q oracle queries can distinguish XORP from a random oracle with probability at most q/2^n, instead of q^2/2^n.

I have to say I'm a bit surprised. I did not expect it to be a very strong hash.

I am also surprised this technique hasn't been proposed for PoW (as far as I know). Maybe it just isn't very well-known (there is no Wikipedia page as far as I know). Maybe because a 128 bit hash (when used with AES) is seen as slightly less "marketable" despite the fact it provides sufficient security for preimage attacks. My personal feeling is that this extra sense of security might be justifiable when the PoW is used for securing transactions, but I'm not sure about its value for preventing spam.

I've also made a long comment on the Reddit post that attempts to summarize the reasons I'm fighting so hard to have the option of AES-based hashing considered.

2 Likes
Time-as-a-Currency & PoS4QoS - PoS-based Anti-spam via Timestamping
#20

Regarding the underlying hash function, MeowHash, an AES-NI-based hash function, came up with a quick google search; I know nothing about cryptography, but I hope it can be helpful somehow.

1 Like