New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
merkle.CompactMerkleTree.Hashes() doesn't return [] for "perfect tree sizes" #200
Comments
Example data: tree_size:1 hashes:"n4\013\234\377\263z\230\234\245D\346\273x\n,x\220\035?\26378v\205\021\243\006\027\257\240\035" root_hash:"n4\013\234\377\263z\230\234\245D\346\273x\n,x\220\035?\26378v\205\021\243\006\027\257\240\035" tree_size:2 hashes:"" hashes:"\372\305B\003\347\314il\360\337\313B\311_\035\235\272\367\n\331\346!\364\275\215\230f/\000\343\301%" root_hash:"\372\305B\003\347\314il\360\337\313B\311_\035\235\272\367\n\331\346!\364\275\215\230f/\000\343\301%" tree_size:3 hashes:"\002\230\321"\220m\317\301\010\222\313S\2479\222\374[\237I>\244\311\272\333'\267\221\264\022z\177\347" hashes:"\372\305B\003\347\314il\360\337\313B\311*\035\235\272\367\n\331\346!\364\275\215\230f/\000\343\301%" root_hash:"\256\266\274\376'Kp\241O\260g\245\345W\202d\333\017\251\265\032\365\340\272\025\221X\363)\340nw" tree_size:4 hashes:"" hashes:"" hashes:"\323~\344\030\227m\331WS\301\3078b\2719\217\242\242\317\233O\360\375\376\2130\315\225 \226\024\267" root_hash:"\323~\344\030\227m\331WS\301\3078b\2719\217\242\242\317\233O\360\375\376\2130\315\225 \226\024\267" tree_size:5 hashes:"\274\032\006C\261.M-|w\221\217D\340\364\367\232\203\213l\371\354[(>\037M\210Y\236k" hashes:"" hashes:"\323~\344\030\227m\331WS\301\3078b\2719\217\242\242\317\233O\360\375\376\2130\315\225 \226\024\267" root_hash:"N;\273\037{G\215\317\347\037\2661c\025\031\243\274\241,\232\357\312\026\022\277\316L\023\250bd\324" tree_size:6 hashes:"" hashes:"\016\274]47\373\342\333\025\213\237\022j\035\021\2160\201\201\003\035\n\224\237\215\355\355\353\305X\357j" hashes:"\323~\344\030\227m\331WS\301\3078b\2719\217\242\242\317\233O\360\375\376\2130\315\225 \226\024\267" root_hash:"v\346}\255\274\337\036\020\341\267M\334`\212\275/\230\337\261o\274\347Rw\265#*\022\177 \207\357" tree_size:7 hashes:"\260\206\223\354.r\025\227\023\006A\350!\036~\355\314\264\302d\023\226>\356l\036.\321o\373\032_" hashes:"\016\274]47\373\342\333\025\213\237\022j\035\021\2160\201\201\003\035\n\224\237\215\355\355\353\305X\357j" hashes:"\323~\344\030\227m\331WS\301\3078b\2719\217\242\242\317\233O\360\375\376\2130\315\225 \226\024\267" root_hash:"\335\270\233\344\003\200\2362WP\323\322c\315x\222\234)B\267\224*4\267~\022,\225\224\247L\214" tree_size:8 hashes:"" hashes:"" hashes:"" hashes:"]\311\332y\247\006Y\251\255U\234\267\001\336\331\242\253\235\202:\255/I The general pattern is that for 'perfect' trees sized 2^n, the Hashes() func returns 'n' nil hashes followed by a hash equal to the root hash. |
Updates made to CompactMerkleTree in d1ee609 (PR #180) to return a copy of the internal Node state, have not properly covered the edge case where the tree is perfectly balanced (i.e. has 2^n leaf nodes).
In that situation the set of nodes should be empty: the size & root hash alone describe the tree, as evidenced by the fact that when merkle.NewCompactMerkleTreeWithState() is called it will make 0 calls to the backing store via its getNodeFunc to retrieve hashes.
The text was updated successfully, but these errors were encountered: