randprog
randprog copied to clipboard
hyc
large variations in time
Here's an example
0707c7b1f0d60567d143dd0d0b600a54ed14169486b016e77266cc63bf9a79b96f9bcadd4de2c30000000052a04939ea39bfd3c8595707bd8fe4b1e7d8046ca88bfee4dc5483ad37e5758103
1000 nonces took 9892.235189 seconds
this file has the grep'd log of an infinite loop, grabbing a new block header blob every time. Format is as above, where the string is followed by the 1000 nonce timing. This is running on a CPU where the cryptonight hash is 77 h/s
https://moneroworld.com/logs/string_timings.txt
This is the offending input:
0707c7b1f0d60567d143dd0d0b600a54ed14169486b016e77266cc63bf9a79b96f9bcadd4de2c37201000052a04939ea39bfd3c8595707bd8fe4b1e7d8046ca88bfee4dc5483ad37e5758103
(nonce = 370)
It seems the nested for loops make it run for hours.
The generated program can be found here: https://pastebin.com/9YimzA3N
Thinking about this, if our output is turing complete, we can never guarantee the nonexistence of programs whose execution time is excessive.
However, the client is able to terminate those PoWs that exceed a particular threshhold...but if there's only one (or a small set) of generated algos to use for the next block (such that the miner can select one that doesn't run forever), what if by some chance statistically they all run forever? We would be forced to fork a change, I believe.
I'm making some assumptions about the system we're building from this issue, trying to see future pitfalls.
Proposal: use the previous blockhash and an index starting from zero. Generate a random program, and run it for X cycles/instructions, and determine if it halts. If so, determine if X is within a particular predetermined range. If X falls within the range, that program is the deterministically chosen algorithm for that particular block. I believe this can be done deterministically, to avoid an attacker generating programs that they can ASIC with only a subset of our instructions.
@livinginformation Sounds similar to my concept CNVM. I think the only way to make the runtime approximately equal between different programs is to execute a fixed number of instructions/statements.
The code is guaranteed not to loop infinitely, I already took care of that before making the binary available. In the meantime, it just needs a few more rules to limit loop nesting to keep the runtime more constrained.
Setting a fixed number of instructions will mean this changes from a moving target into a fixed target, one that ASIC builders can focus on. That's also a bad idea. The most we should restrict it is +/- a margin around a particular complexity level. E.g. +/-20%.
I think the simplest solution is to just throw away the nonce (kill the execution) if the program runs for more than (mean + x * sigma). It's probably acceptable if the ratio of rejected nonces is < 0.1%.