Bug in RFv2

[itwysgsl]

Hello @bschn2, @djm34 just messaged me and told that apparently this https://github.com/bschn2/rainforest/pull/7#issuecomment-476557064 bug from v1 "successfully" migrated to v2.

Quote: It is still there (has far as I understand the code), there is just before 100's or so loop over the full hash. This is due to the 256bit rotation which create that in the "round" routine.

Can you check it?

[bschn2]

Hello Sir, and please accept my apologizes for the delay.

I don't see how it would still be there : the previous problem is that the known hash of resulting from the previous round was only disturbed by the CRC32 for the last block and allowed to guess the trailing word from the desired block by undoing the CRC and xoring it with the known hash. That doesn't work as soon as you have at least 2 loops since the initial hash and context are affected by the whole message, thus the starting point for the second loop depends on every single bit of the message. If you want to undo the CRC in the 100th loop, it will require the hash value from the 99th which itself depends on the whole message. So the nonce you would compute based on this would be valid for a fixed initial (hash,crc) couple, but this initial couple will itself be different if you change the nonce.

If that makes you feel safer, I'm fine with adding one extra round in the padding, but I can assure you I'm absolutely positive it is safe the way it currently is.

I'm obviously humbly open to any comment on this subject, as I could have overlooked anything but even after reading it again I don't see what.

[djm34]

It isn't exactly to what I am refering: What I mean is that to decide in a miner if a nonce, is a solution we compare the final hash to the target. but usually we don't compare the full hash but only the last 32bit or 64bit of the hash to the last 32bit or 64bit of the target

However because of the way rounds are computed. We know the last 32bit directly before running rfv2_final. the last 64bit are themselve known after the first rounds which is rfv2_final and so on...

So basically in order to decide if a nonce is solution, we could just stop the calculation right before rfv2_final, depending how high or low is the difficulty.

I understand that it doesn't give a huge advantage since the algorithm performs many loop, but in my opinion it would be better if every pieces are required to be run.

This could be avoided by simply performing the rotation rfv2_rot32x256 the other way around (doing a left rotation rather than a right rotation of 32bit)

[bschn2]

Hello Sir, Rest assured that this is exactly what I understood. What I mean is that thank to the loops you can only optimize one round of the last loop in the best case, which is useless when you've already ran 100 loops. I agree it could be addressed different ways (including rotating in the other direction). As I previously said, given that this hash round successfully passed all the smhasher tests (which took one week) I feel a little bit nervous about touching anything in the loop that might introduce a bias considering that this issue is addressed by the loops (on average you can save less than 1% performance by skipping the last round once you have multiple loops since you're forced to redo the first ones entirely anyway).

However as mentioned, I'm fine with adding one extra padding round which will take care of this 20th word and mix the output with the rest of the hash as it ought to have been. The problem v1 suffers from only exists for messages between 77 and 80 bytes long, and the padding was there to make sure the full rounds are run for all lengths except that I counted off by one.

[itwysgsl]

@bschn2 so, what you think about adding extra padding as percussion in final version of RFv2? Just in case :)

[bschn2]

Yes definitely. I wanted to be sure not to break your setup given you're the primary user right now. I'll add it this week-end and will finish polishing the comments in the code.

[itwysgsl]

@bschn2 got it, looking forward for final polishing. I'm also peparing new release of MicroBitcoin with switch code for RFv2 on this weekends :)

[itwysgsl]

I think now we can close this issue :)