Bitcoin Forum

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

Interesting..

Please elaborate.

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

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

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.

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.

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.

calling our miner developers in the house  8)

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:

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.

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.

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

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.

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.

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.

Can someone explain to me the likely difference between a 4GB GPU vs an 8GB GPU?  I'm thinking about adding a few GPU's to my farm - the R9 390 has GB of ram which is pretty much useless when it comes to what was supposed to be memory hard PoW (Ethereum).  The newer larger memory bandwidth 4GB cards (Nano, Fury, etc) have a better hashrate.

Is more RAM per GPU going to wind up meaning better performance (allow more threads)?  Or will optimizations likely allow trading performance + bandwidth for RAM resulting in better performance from a newer lower ram

wtf you guys need Zcash for? don`t you know yet that Vcash solved all bitcoin problems already? :D :D :D

It's a proof of stake coin.  Someone hacks Poloniex and coin instantly dies.  Many wow.

The performance between the 4 and 8GB cards are similar. But when the DAG size increases furhter, you will see the difference.

In this case it turns out there is little difference between fully sorting and sorting into bins,
since the expected bin size is only 2 :-)

So equihash really seems to be all about sorting...

So can we mine this already?

Not for real.

You can mine on the zcash testnet but the current "basic" solver is un-optimized (hence rather slow)
and uses reduced parameters.

I apologize for my ignorance in understanding exactly what you're saying.

The bottleneck is going to be sorting - so it will be transfer speed between the ram and the processor and the processor speed.  Not the amount of RAM that will be the bottleneck?

Are there any plain language descriptions of equihash algo?
I tried to look at the zcash C++ code, but it is C++...

Ideally some comparable reference implementation in C would be really helpful

I believe you have the constants wrong.  n=144, k=5 means that they're finding collisions
on n/(k+1) = n/6 = 24 bits at a time, repeated 4 times, and then finding final collisions
on the remaining 144-(4*24) = 48 bits, each time from a set of approximately 2^25
candidate hashes.

It's quite intriguing algorithmically.  I think the original paper might be a little too glib about the constants, though.

You're right; I somehow managed to mess up a trivial calculation. Thanks for the correction.


Which constants are you referring to?

Btw, nice to see you back after a 10 month hiatus...

Thanks!  I'm not really back - still enjoying the heck out of my sabbatical, but I got curious about this
one this weekend.

The constants:  I think they're thinking about the design a bit wrong and should be able to get the
peak tuple length down to 150 bits, or about 600MB, plus perhaps another ~50MB of ancillary
data structures, without incurring more than a constant number of additional hash calculations.
But I could be wrong - I'm just handwaving in my head about how I'd solve it and haven't
tried writing it down carefully.  That wouldn't substantially change their view of their memory
use.

I think they slightly overcount (again, small things - maybe 20%) the number of rows that
need to be sorted in main memory, because they're ignoring some of the things that can
hit in L3 cache.  As above, though, it's a minor difference.

As others already noted, their analysis ignores HBM / stacked DRAM, which, unlike last year,
is now distinctly real (though still expensive).

None of that is particularly important from an algorithmic standpoint.

dga or tromp, any desire to make 1 BTC and help jl777?

https://bitcointalk.org/index.php?topic=1524143.msg15334660#msg15334660

I haven't taken the time to digest Equihash well enough to articulate an algorithm in pseudo-code.

I realize 1 BTC is probably insufficient for your time.

P.S. I am not involved in that in any way other than being aware that jl777 wants it.

I will donate some money to the guy who makes a GPU-based miner for Zcash.

It was said in their forum that there still could be changes in their algorithm. Nothing was specifically said what they were. So it would be safe to wait and let everything be finalized before committing in something. You can only mine in their testnet now and the official release has been pushed back with no date mentioned.

Zcash just announced their Open Source Miner Contest

https://z.cash/blog/announcing-miner-contest.html

Does a $30k prize fund tempt you into entering?

https://coins.newbium.com/post/1917-zcash-30-000-miner-bounty

Right you are; I managed to implement some substantial optimizations for Equihash; see

https://forum.z.cash/t/breaking-equihash-in-solutions-per-gb-second/1995

i think wolfo will win this lol, he is a great dev in programming for mining, but there should be already a testnet version out there, pc only? so it's only a  matter of time before there is a porting for the gpu world

I've got an other question.

Does anybody know or has a link where I can find all of the coins that use 'equihash'. Im thinking of buying another mining contract over at Genesis. Because my Dash and the Lights are doing pretty well.
Or should I buy an Ether contract or a Monero contract?

I would love to hear from you guys

Greetz,