What are these solvers doing?


#1

So I went through the "Tromp's solvers" thread and while I was able to build and run ./equi, I'm not quite sure what it is doing. I'm getting 3 solutions, but what are those solutions, what am I solving? I have not really looked at equihash in detail, but in bitcoin for example you take a block of transactions add some nonce, hash it, and make sure it is less than some value. If it's not pick a new nonce, rinse and repeat. Then when you have a solution you advertise it to the network and hopefully it gets accepted. So now, is equihash doing something similar or is this completely different. Can someone briefly explain what equihash is doing to the block of transactions? What does running ./equi in Tromp's solver actually do and how can it be used instead of the default miner?


#2

Basics

Bitcoins POW, is like reaching in to a bowl with trillions of marbles, most are black, and very few are white. The white marbles are the solutions, and the nonce is like getting a new set or marbles.

When I was doing laundry today I realized an analogy for equihash. You have millions of socks, and very small percentage are pairs. The rest are singletons. The POW is finding the average two pairs of matching socks. The socks are just a special type of Blake2b hash.

Why socks? For Bitcoin the probability of finding white marbles goes up quite a bit by simply getting really fast at sorting marbles. ASICs are like super fast marble sorting machines, beyond the reach of normal humans (CPUs GPUs). They don't need a lot of space since they can just have one marble in hand at a time.

But there is an interesting paradox that makes finding pairs of socks much tougher unless you lay out tons of socks (in memory). It's called the birthday paradox. If I choose one sock from the dryer as my chosen design, and then start taking them out of the dryer one at a time, and putting them back in, it takes forever to find pairs.

But if I lay out all the socks in front of me, it's very easy to find the pairs. That's because I'm no longer looking for a single matching sock, just any matching pairs. FYI the nonce increment is like getting a new dryer load of socks, much like Bitcoin. The key is that this requires a lot of memory. So it is ASIC resistant because it would make the ASICs very expensive carrying all that memory per chip.

The solvers you see come up with the matching socks but are not full miners. I suspect very soon they will or already have been integrated in to some miners.


Breaking the Analogy

Now, the POW is a bit more particular about how we find pairs to make sure we don't use some crafty optimizations that break the POW's resistance to ASICS and vast miner farms that could amortize their work.

First, you have to find the sock pairs by sorting on only a part of the sock, kind of like bands. You have to record the positions of the pairs after every round of sorting. Then, and this one kind of breaks the sock anaology, you blend the colors of the matching socks so that the colors that match become white and the parts that didn't become black. At the end of these sorts you will have a small collection of totally blended white socks tagged with their sorting order after every sort step. Those socks and the positions are the Equihash solution.

There is also a binding condition, which states that the tips of the socks must be totally white, we can't skip around sorting by the heel first. This is to prevent solvers from getting additional pairs by sorting out of order.

Finally, there is a difficulty condition, just like bitcoin, where the solution is hashed with the last block hash, and there must be a certain number of zeros to be accepted.


Reality

Most of the solvers in the contest right now are still experimental and don't quite yet plug right in to miners. The solvers are just the code that does the sock finding, but the machinery around getting the block headers, interacting with the network, stratums, payments, and all that are on the miner, not the solver. There are tons of people working right now to implement miners that use the existing solvers so I doubt you will have to wait long.


#3

Awesome explanation thanks mate


#4

Thanks, I appreciate you taking the time to explain. I'm still a little bit confused though. You say that with bitcoin a nonce is like getting a new set of marbles, but isn't the nonce one of the white marbles we are looking for? I mean, the goal of bitcoin is the find a nonce that works, once you have that you have the solution. Or are you saying that for each nonce we only grab one marble (perform the hash with the current nonce) if it's black we take a new set of marbles (new nonce), if it's white, success (hash is below some tolerance)?

I'm a bit lost on the second part "Breaking the Analogy". But essentially from what I understand, instead of picking one thing (the nonce in bitcoin's case) we are now matching, which obviously requires more memory. Then, the PoW algorithm is forcing us to perform the match in a certain way to keep things even more fair. So we are not trying to just find any match, but a specific match? And, after we get that specific match using some random dryer (nonce), we then hash the block including that nonce with equihash and pass that onto the network for verification?

Side question: Would it be beneficial if I had multiple machines running to all be using different nonces? If I am using the same nonces those machines will be doing the same work correct? Or will there be other differences that would prevent it from being the same work. I ask this because when I was doing some debugging with the miner I noticed that it kept starting from nonce=0 increasing till it found a block, then went back to 0, which seems wasteful. Why not start at a random nonce?

Again, thank you for your help.


#5

Regarding your side question, unlike Bitcoin nonce in zcash is 256bit. In log you see last 32 bits.
Remaining bits are randomly selected. So running parallel miners is not waste of time. They are searching for solution in different set.

You could ask why 256 bit not 32 bit nonce like Bitcoin.
AFAIK after completing entire 32 bit nonce universe, Bitcoin miners adjust transactions/time to get different hashes. With 256 nonce in zcash it takes considerable amount of time to verify all 2^256 combinations.


#6

The nonce is actually used to generate the black and white marbles. The hash function could be thought of as a pseudo-random machine that vends a marble given a nonce and the last block hash. It's pseudo random because if you give it the exact same input, it generates the exact same output. So if we didn't increment the nonce, we could never reach the criteria of having a white marble if 0 generated a black marble. On the other hand equihash uses the nonce to create a large number of hashes, not just one.

It's very much like minecraft if you have ever played with the seed value for worlds. If you give it the same seed number, the same exact world is generated every time, but that one seed generates billions of minecraft "blocks".

For "Breaking the Analogy", we actually increment the nonce in both bitcoin and equihash. The difference is that in bitcoin, the nonce is used to generate one marble we check, while in equihash it's used to generate an entire load of socks. So we get the last block hash, increment the nonce, create the socks, and find the matching socks. If there were no matching socks found, we increment the nonce, create another batch of socks, and try to find pairs there. Once we find enough pairs of matching socks, we hash them with the last block hash, check if there were enough leading zeros in the resulting hash to pass the difficulty condition, and then forward the solution to the network for verification.


#7

love the explanation ! :bow down: