Topic: Zcash Equihash PoW Released - page 2. (Read 7767 times)

Coalescing patterns are variable across implementations a common point across most hardware is occupancy ratio or hardware-based, context-switch-free multi-threading of sort. Intel calls it HyperThreading®, it's guaranteed to work on two threads whereas GPUs accomodate as many threads they can fit. In my experience is considerably more consistent and easy to use than exploiting coalescing patterns.

The GPU uses some coalescing to minimize latency and maximize utilization of memory bandwidth. Isn't that likely to merge accesses and thus amortize?

Excuse me we are getting in area of hardware that I am not well researched.

I didn't measure that. I estimated that doing 90 64-bit operations (one siphash call) is cheaper than operating the (typically 16k)
sense amplifiers to read a new bitline. But I could be wrong about that...
I'm assuming a Cuckoo size much larger than 16k of course.


If they share the same memory bank then they likely cause more row switches and there is negligible amortization.


That puzzled me too. I don't see a need for sorting, just for binning to find collisions on the next chunk of n/(k+1) bits...,
and I will only believe sorting is more performant when I see it (i.e. when optimised code for that is made public).


Their stated goal is a 1GB memory footprint, so we can rule out fitting in cache.

I'm interested to give this a test drive and get this working on some rigs.

Sorry not trying to make more work for you, but would you happen to have a reference for that claim? I am curious how you measured that? I remember you told smooth and I that you don't have a Kill-A-Watt meter to measure GPU power consumption.

What about multiple processors sharing the same memory to amortize the memory electrical cost?


I thought Wagner's algorithm sorted. I'll have to reread the paper more carefully.

If lookup is in the static RAM cache, then ratio of computation to memory power consumption should increase.

Yeah we need to analyze the specifics, which is why I am thinking their white paper is myopic. They didn't present any of this analysis afaics on quick perusal. Perhaps they just assumed a memory bandwidth bound.

Cuckoo spends only 1/3 of its time doing hash computations, which take little power compared to DRAM switching rows.
So the possible gain by ASIC hashing is less than 33%.


Again, we must wait to see the final parameters and optimized implementations. It seems likely they'll pick
n=144 and k=5, which means they need to find collisions on 16 bits at a time. That is just a lookup in a 64K entry table;
I don't expect to see any real sorting there. It's less clear how the actual items are represented, and if they are moved
themselves, or by pointer.

1. You didn't address my electrical efficiency point, which I think is probably the most damning. I very much doubt that the memory power consumption will be even 1/10 of the computational power consumption. Thus an ASIC will be at least 10 times more power efficient, Don't I remember pointing out the same issue with your Cuckoo hash? What was your retort again?

2. I also very much doubt it will be latency bound (even after the 10X speed up of the computation), because optimized sorting doesn't have to be random access.

For any memory bandwidth bound, there is this:

calling our miner developers in the house 

You seem to have have misinterpreted the book. Page 115 says

That says there is *no* known quantum speedup for the Generalized Birthday Problem.


There is no publicly available optimized code for Equihash, so we don't really know to what extent it
is bandwidth or latency bound. There may be subtle trade offs between the two. We really need to see the memory behaviour of actual running optimized code.

Even once zcash gets around to publishing more optimized cpu and gpu code,
it won't be clear for a while whether further optimizations are possible, considering that the mining
algorithm is rather nontrivial.

I'm somewhat worried by this statement on their optimization page at https://github.com/zcash/zcash/issues/857


Leaving optimizations on the table means that some miners will be able to run more efficiently than others.

Re: Zcash Equihash PoW Released

https://z.cash/blog/why-equihash.html

Well some Monero folks seem to very interested, so I decided to take a look because I suddenly remembered something from Iota's whitepaper:

http://188.138.57.93/tangle.pdf#page=20 (4.3 Resistance to quantum computations)

If you look on page 115 of Bernstein's Post Quantum Cryptography, it confirms a sqrt(N) speedup for Wagner's solution to the Generalized Birthday Problem for the hypothetical quantum computer. So if Equihash is using a large list of values to be sorted, then the speedup could be so great that a quantum computer could rewrite the entire block chain quite easily by redoing the past proof-of-work exponentially faster than it was originally done.

It appears that a memory hard algorithm such as Cryptonite would not have this problem.

I am just rushing and have not reread the Equihash white paper carefully, so I may have a mistake in my analysis.

Additionally I was thinking that this Equihash can be trivially sped up on an ASIC because the Equihash algorithm is not memory latency bound and thus is bound on the sorting and computation speed and/or the memory bandwidth, which can be optimized with specialized hardware.

Have I missed something in my haste Surely the Z.cash folks are not this myopic.

The following assumption from the Equihash white paper seems to be wrong:


I am thinking faster memory bandwidth can be obtained by reading and writing to multiple, redundant independent memory banks simultaneously that are interleaved differently to have disjoint collisions on banks.

Or even if not faster, then perhaps orders-of-magnitude more electrically efficient, since the electric consumption will be primarily in the computation and not in the memory. And computation can be radically optimized on an ASIC.

As I predicted when I wrote in the Monero thread about this the other day, it appears the white paper didn't consider electricity as the most important factor. Duh.

I can't right now. Sorry. tromp is also qualified, but he is opinionated about the value of asymmetric proof-of-work versus memory hard hash algorithms.

I understand very little about PoW and I understand my capacity enough to know that learning will be less fruitful than reading from educated observers.  Wolf0, tbtb_need_war, claymore, Gregory Maxwell, etc would all be able to give good insight

Well on page 6 part of the equation is infected with HIV and a first glance with out reading everything  it seems they propose a band aid to solve the problem

Interesting..

Please elaborate.

https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf