Proof-of-work - what it be? (formerly: To merge or not to merge)

[jwinterm]

That is the question.

There's already been some discussion about switching to a unique proof-of-work, either by modifying cryptonight further or by abandoning it altogether, with the intent to provide some security through obscurity from 51% attacks by large pools or nicehash. See open issue here: https://github.com/wownero/wownero/issues/15

However, another option that may provide superior security is moving to merge mining with Monero. This would mean tracking changes from their PoW algorithm, and things may get a little hairy around when they hardfork, but if a significant portion of the Monero network adopted Wownero merge mining, this would provide network security superior to the approach outlined in the previous paragraph.

This is far from a decided issue, and there are certainly other alternatives - just tracking changes to Monero's PoW without merge mining, or just sticking with cnv7, masternodes operating network, whatever, but this thread is for discussion of particularly merge mining as a possibility.

[cryptonote-social]

Hmmm, are there any other coins out there already that do merged mining w/ Monero?

[jwinterm]

No, not really. Kind of ducknote/darknote/digitalnote is merge-mineable, and monetaverde was/is merge-mineable, but there has never been an open source pool implementation, so if you want to merge mine you are basically at the mercy of minergate.

[veivavelevetto]

imo merged mining would advertise this coin a lot! Just like Elastos, its community is expecting a steep growth when merged mining with bitcoin will be launched in december. What would be the drawbacks of merged mining? Only the hardfrork related ones?

[Cactii1]

Have to remember that this is also like pegging your country's currency to the USD. Wowneo will never (or very rarely) move independently in price from Monero.

[ghost]

Although there might be better network security, one of the problems with merge mining is that it encourages “hash & dump” behavior, so the only reason to mine WOW would be to sell it off quickly, which in the long term, could be detrimental to maintaining an active community. I would prefer to track changes to Monero's PoW and when we have a large enough baseline network hash rate, fork to a unique PoW and call it something like “PoW-WOW”.

[Gingeropolous]

I'd prefer wownero push to do extremely bonkers things that really push the envelope. Merge mining seems safe. It doesn't seem wow enough. this seems wow: https://github.com/tevador/RandomJS

[mattcode55]

Alternative to @Gingeropolous' suggestion: https://github.com/hyc/randprog

[jwinterm]

I think that is an interesting option, but would probably require some heavy lifting for integration and at least some extended testing. Maybe this is something we could put a wow non forum funding system bounty together for, if most folks think this is the way to go...

On Wed, May 16, 2018, 01:09 mattcode55 notifications@github.com wrote:

Alternative to @Gingeropolous https://github.com/Gingeropolous' suggestion: https://github.com/hyc/randprog

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/wownero/meta/issues/3#issuecomment-389433125, or mute the thread https://github.com/notifications/unsubscribe-auth/AFrhk5F8t-e_tujzjcJxoFtcOuSEGlLhks5ty96ugaJpZM4T8krv .

[ghost]

FFS bounty +1

[imperdin]

@Gingeropolous I don't see any added value in using RandomJS, while it's an additional ASIC countermeasure it's far from best practice to prevent FPGAs.

It would be most effective both for development & time wise to switch to a slightly tweaked version of Heavy Which is more resistant to ASICs/FPGAs mining in addition to Bot-nets And it will not be included In Nicehash as it's a tweaked Heavy version named Crypto-WOW

[jwinterm]

@imperdin if by "more resistant to ASICs, FPGAs, and botnets" you mean takes longer to verify with CPU, I'm not sure that's the direction we should move in. I like the idea that people can CPU mine, and I definitely favor faster verification.

[ghost]

If hobbyists can build FPGAs with widely available consumer components, I have no issue with them. The main problem are ASICs built exclusively by only a handful of manufacturers. As for botnets, network administrators and Windows users need to take some personal responsibility for maintaining an up to date and secure system.

[ghost]

Extra brownie points if the PoW can incorporate computation of workunits for the BOINC project. https://boinc.berkeley.edu/trac/wiki/ProjectMain shower thought

[guystyles]

I second the opinion above that wownero should push the envelope. All or nothing! No regrets! Amaze the world, and make them say WOW

[tevador]

https://github.com/tevador/RandomJS/issues/2

All features of the RandomJS generator have been implemented. I need help with testing.

Also the decision should be made if my proposed DoS resistant algorithm is to be implemented (this requires a modification of the block format) or we just replace Cryptonight with RandomJS directly.

[Gingeropolous]

@tevador ,

if my proposed DoS resistant algorithm

You mean the asymmetric algorithm design? that makes sense to me. I haven't heard any negatives about an asymemetric design, and indeed I think its been a common criticism of cryptonight. So I'd be for modifying the block format to make it work.

[tevador]

You mean the asymmetric algorithm design? that makes sense to me. I haven't heard any negatives about an asymemetric design, and indeed I think its been a common criticism of cryptonight. So I'd be for modifying the block format to make it work.

Actually, the DoS resistance and asymmetry are separate options.

1. Asymmetry just restricts what a valid solution is. It only affects mining and validation code, so it doesn't need any additional effort to implement since we are already changing the PoW.
2. The DoS resistance requires additional 32 bytes of data in the block, so it needs more effort to implement (for example, block format, daemon and blockchain database has to be modified).

The DoS resistance is not strictly necessary, but rather a nice-to-have since PoW validation will be roughly as slow as Cryptonight (~10 ms).

[binaryFate]

Besides the joke and fun, the interest of Wownero for me is to test crazy things (but crazy things that may one day be incorporated in Monero). For instance right now it incorporates bulletproof (so does the Monero testnet) but provides a more interesting incentive to attack it, as contrary to Monero testnet it holds some value. Arguably very little, but still more than zero. This makes it a cool test bed to push cutting-edge ideas into production and learn from it.

Hence, I also really would like to see a randomJS approach.

[jwinterm]

@tevador can you expand a bit on how the DoS prevention would work.

I'll try to find Windows machine to build and test on this week.

Personally I think it would probably be better to implement PoW change first and then DoS later/separately, if that doesn't cause additional complications, so that we're only breaking one thing at a time.

[ghost]

Agree with @jwinterm. If DoS resistance is considered more of an optimization, then tinkering with the new PoW should be looked at first.

[tevador]

@jwinterm I tried to make a diagram to explain the algorithm.

A network node can quickly verify the PoW of a new block by following the green arrows. This requires just two Blake2b hash calculations. Therefore even if an attacker can saturate the network connection with invalid blocks, the node can check and discard all of them.

If the intermediate result is not stored in the block, then the whole algorithm must be run to obtain the PoW hash (just like Cryptonight).

Also this is a good time to review the algorithm if we can find any obvious weak points. Comments are appreciated.

[binaryFate]

@tevador Are you going to rewrite it in C++?

[tevador]

@binaryFate Yes, after the optimal generator options are found so the code can be better optimized.

[binaryFate]

The optimization should be done after so it is based on the performance and timing of the C++ version.

I am one of the authors of this software package to optimize algorithm parameters. It has produced many state-of-the-art algorithms (from a handful of parameters to hundreds of them) in different fields. http://iridia.ulb.ac.be/irace/ Would be easy to plug with your algo and optimize for whatever metric you want. I can help with that.

[tevador]

The optimization should be done after so it is based on the performance and timing of the C++ version.

I'm timing only the program execution and for that I use NodeJS, which already natively includes Chrome V8. I think the overhead is minimal.

I am one of the authors of this software package to optimize algorithm parameters. It has produced many state-of-the-art algorithms (from a handful of parameters to hundreds of them) in different fields. http://iridia.ulb.ac.be/irace/ Would be easy to plug with your algo and optimize for whatever metric you want. I can help with that.

Sounds interesting. I've never heard of iterated race. How do you specify the goals that the optimizer should try to meet? Is there something like a fitness function like in GA?

[binaryFate]

Sounds interesting. I've never heard of iterated race. How do you specify the goals that the optimizer should try to meet? Is there something like a fitness function like in GA?

Yes. You need to return a single number to the optimizer. The program is launched through a wrapper (typically a bash script) which can aggregate all returned values into a single number. For instance a weighted sum of the difference to the target runtime (5ms?) plus an optional penalty if the time varies too much across executions, or the amount of RAM, etc. Up to you. The iterated race is just a very quick effective way to scrap bad candidates and sample new ones from promising ones, it converges faster than what typical GA would do for algorithm configuration problems. It samples around several promising candidates so you focus on several local optima at the same time. The software is designed to sample new candidates differently depending on the type of parameters. For instance if you have a discrete parameter (whose value can be "use_component_a", "use_component_b", "use_component_c"), the values will be sampled differently than if a parameter is an integer or has any logical progresion (say, possible values "high", "medium", "low"), or if it's just a float within [X,Y]. In practice, you write a simple definition of the parameters types and ranges in a text file, your experimental budget, and it does the rest to give you in the end a handful of winning configurations for your particular fitness function.

[tevador]

@binaryFate Perfect, that's exactly what we need. RandomJS currently has 113 configurable parameters. I can prepare a script for the optimization. Is there some specification available what format to expect on input/output?

[cryptonote-social]

Pretty risky move I think; this is a significant departure from existing PoW approaches that have proven hardness properties. It's likely there will be clever folks who can implement dramatically faster Javascript engines for these sorts of simple programs than whatever the regular miners will rely on.

[jwinterm]

Are there really more clever folks than the google javascript folks? What exactly is the simplification beyond total google js engine?

[tevador]

Pretty risky move I think; this is a significant departure from existing PoW approaches that have proven hardness properties.

Every single existing PoW approach turned out to be susceptible to ASIC implementation. In my opinion, we need to try something radically different.

It's likely there will be clever folks who can implement dramatically faster Javascript engines for these sorts of simple programs than whatever the regular miners will rely on.

There might be some room for improvements, but something dramatical is unlikely, The randomly generated program is not so simple. I tried to use as many features of the language as possible. Actually it's an impressive performance from the V8 to parse, compile and execute 40 kilobytes of javascript source code in under 10 milliseconds.

[cryptonote-social]

"Are there really more clever folks than the google javascript folks? What exactly is the simplification beyond total google js engine?"

The Google javascript folks, the Apple javascript folks, the Mozilla ones, all have been optimizing Javascript for actual web workloads. There are undoubtedly optimizations they either have yet to pursue or have abandoned because they weren't worth it for this use case, but might very well apply to these artificial programs. Even the Cuckoo cycle folks were surprised by some of the optimizations folks came up with for their very simple problem. They were smart about this though and offered big bounties for faster implementations before advocating it be adopted. If you are to go this route, you should do the same. I will bet you a good chunk of $TRTL that someone will find something faster!

[guystyles]

What’s the worse thing that can happen if someone does?

[cryptonote-social]

"What’s the worse thing that can happen if someone does?"

51% attack.

Though most likely outcome is one (or a few) miners making bank at the expense of everyone else.

[Gingeropolous]

@cryptonote-social , yeah I would hope there would be a bug bounty for whatever comes out of the effort. I mean, thats sort of the benefit of implementing it on a working network - hashrate spikes can be observed, and optimizations get out there - see XMR.

[Gingeropolous]

@tevador , can you comment on @hyc 's comment:

https://github.com/monero-project/monero/issues/3545#issuecomment-379979949

(unless you have already)

specifically,

Why change on every nonce? Because we already know that companies like Bitmain have automatic tools to turn e.g. C code into e.g. RTL - Someone using FPGAs could easily reconfigure if you only use one algorithm per block. Generating a new program for every nonce eliminates any such advantage. It also eliminates a lot of compiler advantage too - both AOT and JIT compilation trade off compile time for run time on code that executes more than once. Since the generated code will only ever execute once, complex AOT or JIT optimization are pointless.

does your random generator do one random program per block, and then send nonces through that program?

[tevador]

Even Monero has a history of major performance improvements. See this blog post. They wrote a 100x faster miner and at one point controlled about 60% of the network hashrate. Eventually the optimizations were published and now everyone is hashing at the improved speed.

I don't think anyone will be able to find a 100x faster javascript VM.

@Gingeropolous My algorithm works the same way as hyc's in this regard. The hash of the block header serves as the seed for the random generator. This means that any change in the block header (different nonce, different merkle root hash, different previous block hash) will change the program.

[cryptonote-social]

With Cryptonote/Cryptonight, the bytecoin authors intentionally published a broken implementation they knew they could easily speed up in order to mine the vast majority of the coins (in addition to scamming folks into believing the network was active for 2 years when in fact they just pocketed 2 years worth of blocks). So that situation is a bit .... special.

[binaryFate]

@tevador if you're interested to optimize parameters using the dedicated research tool I mentioned, I suggest that I set up an example configuration of everything required as a starting point, but I need to discuss with you the parameter specifications. Note that I would set everything up on Linux, as running irace on Windows is a pain. But then irace would support testing candidates in parallel (on every cores or even on a larger cluster of multiple machines) out of the box.

I think the easiest is that you reach out to me on IRC (same nick).

My interest in general is to end up with a procedure to get to a new suitable PoW that would be reproducible for Monero one day, or from which we can learn useful feedback.

[tevador]

@binaryFate I followed the PDF guide on the website and managed to get it to run. Anyways, I still have some questions about the configuration. We can discuss on IRC.

[tevador]

@binaryFate I added irace configuration files into the repository: https://github.com/tevador/RandomJS/tree/master/doc/irace

You can just clone the repo, follow the installation instructions in README to install mono and NodeJS and then build it. You have to run the sandbox with node sandbox.js --complexity to enable complexity measurement. This is important.

Irace should be ready to run as-is (target-runner assumes you cloned the repo into ~/RandomJS and the machine has 32 cores), I added the result of yesterday's test run as one of the inputs in configurations.txt (my manually optimized config is still better, though).

I have increased the default runtime target to 10 ms because I found that the VM runs slower when complexity measurement is enabled (probably due to increased garbage collection) . We might have to modify it depending on the performance of the machine where it will run. You can benchmark the performance by running the default configuration: ./Tevador.RandomJS.Test.exe --count 10000 --threads 32. It will show the average runtime (I tested on Xeon E5-1660 and the average was 14 ms).

[binaryFate]

@tevador Great I'll have a look, good job on understanding how to set it up by yourself mostly :)

First comment after quick look is that the number of instances (aka seeds) must be at least in the hundreds so they do not need to repeat, currently it is testing on a tiny subset of 5 seeds over and over again.

[tevador]

the number of instances (aka seeds) must be at least in the hundreds

Is it really necessary, though? Each seed is actually 1000 seeds, because each run creates 1000 programs. Speaking of which, I modified the seeds so the sequences don't overlap (the difference must be at least 1000).

[krtschmr]

If we do merge mininig with monero, we can already test for Tari. Wownero seems to be the production testnet for M00nero.

[binaryFate]

Is it really necessary, though? Each seed is actually 1000 seeds, because each run creates 1000 programs. Speaking of which, I modified the seeds so the sequences don't overlap (the difference must be at least 1000).

Yes it is, otherwise you get 5 (at most) different measurements only for the candidates. This is way too small of a sample, and does not allow proper statistically significant discrimination between them.

[tevador]

@binaryFate I have commited a new instances file with 200 seeds.

[binaryFate]

Great. Can you merge my PR? It's just details for convenience and explanations if somebody else wants to give it a try.

I am doing some trial runs now. I'll post some advise on what configuration to use soon (mostly which statistical test to use -- makes a big difference and should be inline to what you are measuring as fitness).

[tevador]

I merged the PR. Also I did a small modification in the parameters list (2 parameters removed from optimization).

[RocksteadyTC]

Hey TurtleCoin here, we're trying to get merge mining going. Is there room for us in this discussion?

[guystyles]

Y’all should talk to Aeon too. Cryptonight unite

[ghost]

Hi @RocksteadyTC, it looks the rough consensus is to not to merge mine and go for a new POW. However, the idea of merge mining may still be of interest when [if] we incorporate a second layer protocol for digital assets. Perhaps opening a new issue to discuss merge mining on cryptonote in general would be helpful for everyone.