New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Select feasible Equihash Parameters #856

Closed
defuse opened this Issue Apr 11, 2016 · 16 comments

Comments

Projects
None yet
8 participants
@defuse
Contributor

defuse commented Apr 11, 2016

We're using reduced parameters at the moment because of an unoptimized implementation.

@nathan-at-least nathan-at-least added this to the Non-Spec Consensus Features milestone Apr 11, 2016

@nathan-at-least nathan-at-least changed the title from Change Equihash Parameters to Select Equihash Parameters Apr 12, 2016

@str4d

This comment has been minimized.

Contributor

str4d commented May 26, 2016

@zookozcash wondered about selecting parameters that fit into a 64 kiB L1 cache. Calculating the theoretical peaks (and assuming the peak is still in the final round), I get the following:

n k Index truncation Peak memory
64 7 4 bits 17 kiB
64 7 8 bits 33 kiB
80 9 4 bits 65 kiB
80 9 8 bits 129 kiB
@nathan-at-least

This comment has been minimized.

Contributor

nathan-at-least commented Jun 20, 2016

We have a new goal for this z6 release which is to be backwards compatible with the z5 testnet (except for a blocksize increase). Because of this, we cannot change proof-of-work in any way that will cause z6 clients to fail to validate z5 proof-of-work, so we're postponing this to the next milestone.

@nathan-at-least nathan-at-least modified the milestones: Consensus Code Security Freeze, Consensus Parameter Tuning / Optimization Jun 20, 2016

@nathan-at-least nathan-at-least modified the milestones: Consensus Code Security Freeze, Temporary overflow Jul 14, 2016

@Cryptoslave

This comment has been minimized.

Cryptoslave commented Jul 18, 2016

What about trying in the next release different parameters like k=10, n=198 which is 19.2 times faster like daira proposed here #1055 (comment) ?

@nathan-at-least nathan-at-least changed the title from Select Equihash Parameters to Select feasible Equihash Parameters Jul 25, 2016

@nathan-at-least

This comment has been minimized.

Contributor

nathan-at-least commented Jul 25, 2016

I changed the title because we'll make this selection prior to having @solardiz's report about Equihash optimizations. After we receive that report, we may alter the parameters, but that's a separate ticket.

@daira

This comment has been minimized.

Contributor

daira commented Jul 25, 2016

@Cryptoslave: the obstacle to that is #1142 -- it appears as though there's either a bug in our Equihash implementation, or an oversimplification in the Equihash paper's analysis of the expected number of solutions per run for higher k (in practice for k > 5).

@tromp

This comment has been minimized.

tromp commented Jul 27, 2016

The problem with k>5 is the exploding variance in the number of solutions,
an issue that is ignored in the whitepaper.

@daira

This comment has been minimized.

Contributor

daira commented Jul 27, 2016

I originally thought that was the case, but my experiments don't support that hypothesis. Even if you increase the number of initial rows (which causes the number of rows to expand exponentially with the round number, so that only a small increase can be made to result in the number of rows being around double after about 7 rounds, say), then the number will still invariably collapse by round 10. I don't understand why, but it's not as simple as the variance being too high.

@tromp

This comment has been minimized.

tromp commented Jul 27, 2016

How can I reproduce your experiment showing a solution space collapse by round 10?

@aniemerg

This comment has been minimized.

Contributor

aniemerg commented Jul 27, 2016

I've simulated this using @str4d 's python Equihash implementation. I think the problem is the large number of duplicate indexes. Using n=96, k = 11, I saw the following the number of rows per step:
[0, 510, 487, 466, 362, 124, 2, 0, 0, 0, 0]

We see the number of rows peak and begin to decline and we can see that by step 7, the number of rows is zero. Ok, here's the number of duplicate indexes that were found and discarded at each step:

[0, 0, 5, 50, 305, 1874, 5202, 402, 0, 0, 0]

So, I guess the problem is that as the number of indices becomes large, the probability of any matching rows having at least one pair of duplicate indices explodes? This seems to limit the ability to use large numbers for k.

@str4d

This comment has been minimized.

Contributor

str4d commented Aug 5, 2016

In a local test branch containing the commits from both #1172 and #1173, I can obtain the following for n = 200, k = 9:

Generating first list
- Time: 1.13095s
Round 1:
- Sorting list
- Finding collisions
- Time: 2.06647s
Round 2:
- Sorting list
- Finding collisions
- Time: 1.87671s
Round 3:
- Sorting list
- Finding collisions
- Time: 2.01371s
Round 4:
- Sorting list
- Finding collisions
- Time: 1.86506s
Round 5:
- Sorting list
- Finding collisions
- Time: 1.94379s
Round 6:
- Sorting list
- Finding collisions
- Time: 1.78502s
Round 7:
- Sorting list
- Finding collisions
- Time: 1.82637s
Round 8:
- Sorting list
- Finding collisions
- Time: 1.56148s
Final round:
- Sorting list
- Finding collisions
- Time: 1.13898s
Found 2 partial solutions
Culling solutions
- Time: 14.6234s
- Time: 14.6356s
- Number of invalid solutions found: 0
[
    {
        "runningtime" : 46.47790800
    }
]

The memory usage (RES) starts at ~563 MB and creeps up every round from there (sometimes to less than 600 MB, sometimes to more than 700 MB). Most interestingly, the time to regenerate the truncated indices is about the same amount of time as to find the solutions in the first place, indicating that the elimination step is currently sub-optimal.

The up-shot is: with n = 200, k = 9, we can hit ~600 MB of memory, with the partial solutions found in 15s, and the first solution found in 30s (assuming all partials are valid, which is much more likely given #1173).

(For comparison, BasicSolve takes about 102s. It starts around ~2096 MB and I saw it get as high as 2.3 GB if the list length is increasing.)

@str4d

This comment has been minimized.

Contributor

str4d commented Aug 5, 2016

For 200,9 the solution size in each block header will be 2051 bytes (3-byte compact int (set to 512), followed by that many 4-byte ints). If we used a maximally-compact (and thus less-easily parse-able) representation, it would be 1280 bytes.

@daira

This comment has been minimized.

Contributor

daira commented Aug 5, 2016

Good work @str4d!

I think we do want to save those 771 bytes/block, but we don't need to do so for z8. Can you open a separate ticket for that please?

@Ban44n

This comment has been minimized.

Ban44n commented Aug 5, 2016

I am kind of worried about the statement made by @tromp. If what @tromp says is true, that would imply that the variance in the difficulty of the network also increases.

@tromp argues that when k>5, the variance in the number solutions after each equihash run increases. Basically that would imply that the average number of solutions is still 2, but the chance of finding 3,4,5,.. solutions per run increases. In more mathematical words, the variance in the propability distribution of finding x solutions scales with k.

Correct me if I am wrong, but wouldnt that imply that the variance in the average difficulty of the network also increases? My thought experiment is as follows: imagine a network in which we have a constant amount of miners with a constant network hashrate. Now if each miner would on average find two solutions on every equihash run and the variance is very small (k<5), the time it would take for the network to find a solution matching the network's difficulty is approximately constant and fluctuates with the same (small) variance as the equihash algorithm. In this case, we would not observe any issues.

However when there is a huge fluctuation in finding x solutions per equihash run (increase in variance that apparently scales with k, if we believe @tromp). This would inherently imply that the difficulty of the network is going to fluctuate with the same order of magnitude. This is of course only true when the difficulty of the network is adjusted on the same timescale. Which is the case, currently the difficulty of the network is adjusted after each block right? This would mean that we would observe the same fluctuations in the difficulty of the network.

In general I dont really think that this is an issue, however if one would plot the difficulty of the network over time these would show huge fluctuations on small timescales. I would say that this is not something that you would like to have in your cryptocurrency. The task of the difficulty adjustment algorithm is not to fix issues that come from the PoW, but it should focus only on the increase in network hashrate.

I would say that a mathematical study in the variance would help us here, atleast that way we understand the correct scaling behavior with k.

@str4d

This comment has been minimized.

Contributor

str4d commented Aug 5, 2016

@daira I've opened #1175.

@tromp

This comment has been minimized.

tromp commented Aug 5, 2016

@daira

This comment has been minimized.

Contributor

daira commented Aug 6, 2016

@ampyx: even if it were the case that the variance in the number of solutions increases with k (and I don't think we have any evidence for that), it would not lead to large variations in time-to-next-block. The reason why the Equihash authors designed the variance to be low, if I understand correctly, is that a high variance allows more room for implementation strategies that abandon less-productive solution runs early, which leads to a more complicated security analysis.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment