Closed janx closed 10 years ago
Yes, seems like a float rounding error with Javascript. I will fix my code to do all additions using integers only. Good catch.
> 0.5 + 0.54 + 112 + 157 + 442 + 990 + 1050 + 2025 + 3988 + 7944 + 10499.19
27208.230000000003
Let's use satoshi instead of BTC to store amount ?
Will it be a little space inefficient? value: 1
becomes value: 100000000
.
Correctness is the number one priority. Using float or decimal number for financial data is a recipe for disaster. Adding a few bytes to the complete tree is not going to hurt.
Let's use satoshi instead of BTC to store amount ?
The problem is I would rather not make the standard too much Bitcoin specific as the same scheme could eventually be used to prove USD/litecoin/doge/etc. liabilities.
That being said, implementations should probably deal with integers internally to prevent this kind of bug. In Javascript, this can be done by multiplying the input numbers by 100000000 and before serializing the tree, dividing every number by 100000000 (assuming we won't have to deal with currencies that have more then 8 decimals).
I think the number in json should be kept as String. How the number is represented in memory is implementation specific issue, which should not affects the exchange format. e.g. both java and ruby provide built-in BigDecimal
type.
@janx can I have a link to your implementation, I will add it to the README. Thanks for reporting this bug. I don't think storing the number in JSON as a string will make much difference as long as it is consistent.
@olalonde it's a ruby implementation: https://github.com/peatio/liability-proof
A float value in JSON is usually deserialized to float by default, a future implementor may overlook this. Maybe I'm paranoid :)
Would it be possible to introduce a big number library like big.js to deal with calculations rather than making assumptions?
Yes, good idea. Putting this on my TODO list.
@olalonde it looks like there still is problem with the integer workaround. Check this pair:
root.json:
{"root":{"hash":"diCiubuuD/WYLhstG4C44zEUZzaUWZu8UehpwI0T+7w=","value":2018.79065414}}
partial_tree.json
{"partial_tree":{"data":null,"left":{"data":{"value":1019.79065414,"hash":"GFDoeqOY22s7DmNmHAApkGFpHfeUKS7UCgZ3oCKJ3QY="}},"right":{"data":null,"left":{"data":{"value":0.0,"hash":"LXu4i7wHKFAVxwcz4XAIJp6gZv3uTX4+KQRlhAtUhNY="}},"right":{"data":null,"left":{"data":{"value":0.0,"hash":"GUbUrrOeKEk7AF84IUAZzMr2PF5zrg7VEdC+s7f5MiY="}},"right":{"data":null,"left":{"data":{"value":0.0,"hash":"H0EsqWDn5q3JdKijoPMy0xzA8X2lzEyLOlzqCd7xvhM="}},"right":{"data":{"value":999.0,"hash":"+S5QsJBlPI4FHmN0BkwOEfqyxuHM8eFYIe41pL1OEBM=","user":"PEAMUWCFGC4TIO","nonce":"9da75ae5a9867fc944ddeef336a014e4"}}}}}}}
Notice the balance sum of user and his neighbor is 999.0
, after integer conversion, it becomes 999
:
Combined string before hash:
999H0EsqWDn5q3JdKijoPMy0xzA8X2lzEyLOlzqCd7xvhM=+S5QsJBlPI4FHmN0BkwOEfqyxuHM8eFYIe41pL1OEBM=
Right, Javascript removes trailing zeroes when "stringifying" a number.
> JSON.parse('{"val": 99.0 }')
Object {val: 99}
Anyways, @zw suggested (https://github.com/olalonde/blind-liability-proof/pull/18) that we should use strings for balances which should solve this issue. I'm currently working on upgrading my code to conform to this more formal specification. Will keep you updated!
Thanks. I'll update my gem too.
I'm writing a proof generate rubygem which create json files conform with the standards you proposed. However I find my generated json cannot pass the verification of blp. After a while of digging it looks like the trouble maker is Float numbers.
I use
console.log
to print combined nodes created in verification, here's the root node:As the message shows the value is represented as
27208.230000000003
in memory, which changes the generated hash.Below is the partial tree and root json I used: