Floor division in target calculaton #758

New Issue

2015-01-07T15:11:03+01:00

Kagami commented

2015-01-07 15:11:03 +01:00

(Migrated from github.com)

PyBitmessage currently uses floor division for target calculation and checking:
https://github.com/Bitmessage/PyBitmessage/blob/master/src/class_singleWorker.py#L773
https://github.com/Bitmessage/PyBitmessage/blob/master/src/shared.py#L343
See also: https://www.python.org/dev/peps/pep-0238/

Example:

>>> requiredAverageProofOfWorkNonceTrialsPerByte = 1000
>>> encryptedPayload = ' '*628
>>> requiredPayloadLengthExtraBytes = 1000
>>> TTL = 2418984
>>> 2 ** 64 / (requiredAverageProofOfWorkNonceTrialsPerByte*(len(encryptedPayload) + 8 + requiredPayloadLengthExtraBytes + ((TTL*(len(encryptedPayload)+8+requiredPayloadLengthExtraBytes))/(2 ** 16))))
297422593171L
>>> from __future__ import division
>>> 2 ** 64 / (requiredAverageProofOfWorkNonceTrialsPerByte*(len(encryptedPayload) + 8 + requiredPayloadLengthExtraBytes + ((TTL*(len(encryptedPayload)+8+requiredPayloadLengthExtraBytes))/(2 ** 16))))
297422525267.8102

You see, result slightly differs with true division.
Is it intentional behaviour? If it is, then should it be documented in the wiki POW article?

PyBitmessage currently uses floor division for target calculation and checking: https://github.com/Bitmessage/PyBitmessage/blob/master/src/class_singleWorker.py#L773 https://github.com/Bitmessage/PyBitmessage/blob/master/src/shared.py#L343 See also: https://www.python.org/dev/peps/pep-0238/ Example: ``` python >>> requiredAverageProofOfWorkNonceTrialsPerByte = 1000 >>> encryptedPayload = ' '*628 >>> requiredPayloadLengthExtraBytes = 1000 >>> TTL = 2418984 >>> 2 ** 64 / (requiredAverageProofOfWorkNonceTrialsPerByte*(len(encryptedPayload) + 8 + requiredPayloadLengthExtraBytes + ((TTL*(len(encryptedPayload)+8+requiredPayloadLengthExtraBytes))/(2 ** 16)))) 297422593171L >>> from __future__ import division >>> 2 ** 64 / (requiredAverageProofOfWorkNonceTrialsPerByte*(len(encryptedPayload) + 8 + requiredPayloadLengthExtraBytes + ((TTL*(len(encryptedPayload)+8+requiredPayloadLengthExtraBytes))/(2 ** 16)))) 297422525267.8102 ``` You see, result slightly differs with true division. Is it intentional behaviour? If it is, then should it be documented in the wiki [POW article](https://bitmessage.org/wiki/Proof_of_work)?

Atheros1 commented

2015-01-16 23:09:04 +01:00

(Migrated from github.com)

This is not the intended behaviour. PyBitmessage should be changed. I've added "from future import division" to shared.py and class_singleWorker.py and reviewed the places where division is used. I've tested it some and if it continues to behave just fine then I'll merge it into master.
Thank you very much for pointing out the issue.

This is not the intended behaviour. PyBitmessage should be changed. I've added "from **future** import division" to shared.py and class_singleWorker.py and reviewed the places where division is used. I've tested it some and if it continues to behave just fine then I'll merge it into master. Thank you very much for pointing out the issue.

Kagami commented

2015-01-16 23:43:58 +01:00

(Migrated from github.com)

@Atheros1 fractional part shouldn't matter? For the example above we eventually will compare POW <= 297422525267.8102 and it's the same as comparing POW <= 297422525267, right?

In fact the current behaviour is even handier for javascript implementations since JS lacks 64-bit numbers and JS big number libraries only provide floor division.
Although I've noticed that we can slightly rearrange calculations and result will still be the same as true division but without the final fractional part:

>>> L = len(encryptedPayload) + 8 + requiredPayloadLengthExtraBytes
>>> 2 ** 80 / (requiredAverageProofOfWorkNonceTrialsPerByte * L * (2**16 + TTL))
297422525267L
>>> from __future__ import division
>>> 2 ** 80 / (requiredAverageProofOfWorkNonceTrialsPerByte * L * (2**16 + TTL))
297422525267.8102

Also, I'm slightly worrying for existing Bitmessage implementations: probably some of them have already implemented current PyBitmessage behaviour and this change will break compatibility.

@Atheros1 fractional part shouldn't matter? For the example above we eventually will compare `POW <= 297422525267.8102` and it's the same as comparing `POW <= 297422525267`, right? In fact the current behaviour is even handier for javascript implementations since JS lacks 64-bit numbers and JS big number libraries only provide floor division. Although I've noticed that we can slightly rearrange calculations and result will still be the same as true division but without the final fractional part: ``` python >>> L = len(encryptedPayload) + 8 + requiredPayloadLengthExtraBytes >>> 2 ** 80 / (requiredAverageProofOfWorkNonceTrialsPerByte * L * (2**16 + TTL)) 297422525267L >>> from __future__ import division >>> 2 ** 80 / (requiredAverageProofOfWorkNonceTrialsPerByte * L * (2**16 + TTL)) 297422525267.8102 ``` Also, I'm slightly worrying for existing Bitmessage implementations: probably some of them have already implemented current PyBitmessage behaviour and this change will break compatibility.

Atheros1 commented

2015-01-21 18:31:42 +01:00

(Migrated from github.com)

The fractional part shouldn't matter. These formulas are all calculating the target. The target ends up getting compared to the trialValue in proofofwork.py. trialValue is always an integer. The loop runs until trialValue is less than or equal to target. So for example, if target = 5, and trialValue = 4 then the loop will keep going. If target = 4.1 and trialValue = 4 then the loop will end. If we use floor division to calculate target then the loop will end. So it is consistent whether or not we use floor division.

Regarding existing Bitmessage implementations, yes it is possible that it will have an effect but the probability is extremely small. The difference between 297422593171 and 297422525267 is 67904. The probability that a completed POW lands within that range by coincidence is 67904 / 297422593171 = 2.28e-7. So I'm not worried about it.

The fractional part shouldn't matter. These formulas are all calculating the _target_. The _target_ ends up getting compared to the _trialValue_ in proofofwork.py. _trialValue_ is always an integer. The loop runs until _trialValue_ is less than or equal to _target_. So for example, if target = 5, and trialValue = 4 then the loop will keep going. If target = 4.1 and trialValue = 4 then the loop will end. If we use floor division to calculate target then the loop will end. So it is consistent whether or not we use floor division. Regarding existing Bitmessage implementations, yes it is possible that it will have an effect but the probability is extremely small. The difference between 297422593171 and 297422525267 is 67904. The probability that a completed POW lands within that range by coincidence is 67904 / 297422593171 = 2.28e-7. So I'm not worried about it.

This repo is archived. You cannot comment on issues.