Issue 14431043: implement complete full hash-extending algorithm for CompactMerkleTree
|
Created:
10 years, 6 months ago by infinity0 Modified:
10 years, 6 months ago CC:
Ben Laurie (Google), ctlog-opensource-review_google.com Visibility:
Public. |
Descriptionimplement complete full hash-extending algorithm for CompactMerkleTree
depends on issue 14386045
Patch Set 1 #Patch Set 2 : #
Total comments: 12
Patch Set 3 : #Patch Set 4 : #Patch Set 5 : #
Total comments: 9
Patch Set 6 : #
MessagesTotal messages: 13
This review seems to be broken (error: old chunk mismatch). On 5 October 2013 16:27, <infinity0@gmx.com> wrote: > Reviewers: ekasper, > > Description: > implement complete full hash-extending algorithm for CompactMerkleTree > > Please review this at http://codereview.appspot.com/14431043/
Sign in to reply to this message.
It builds on top of http://codereview.appspot.com/14386045/ - you'll need to patch that in first. On 07/10/13 15:25, Ben Laurie wrote: > This review seems to be broken (error: old chunk mismatch). > > On 5 October 2013 16:27, <infinity0@gmx.com> wrote: >> Reviewers: ekasper, >> >> Description: >> implement complete full hash-extending algorithm for CompactMerkleTree >> >> Please review this at http://codereview.appspot.com/14431043/ -- GPG: 4096R/1318EFAC5FBBDBCE git://github.com/infinity0/pubkeys.git
Sign in to reply to this message.
Same here, can't view a side-by-side diff. Can you try uploading again? I've no idea why this error happens but it's been known to fix itself with a fresh upload of the same diff. On 2013/10/07 14:25:07, Ben Laurie (Google) wrote: > This review seems to be broken (error: old chunk mismatch). > > On 5 October 2013 16:27, <mailto:infinity0@gmx.com> wrote: > > Reviewers: ekasper, > > > > Description: > > implement complete full hash-extending algorithm for CompactMerkleTree > > > > Please review this at http://codereview.appspot.com/14431043/
Sign in to reply to this message.
Re-uploaded, does it work now? On 07/10/13 15:36, ekasper@google.com wrote: > Same here, can't view a side-by-side diff. > > Can you try uploading again? I've no idea why this error happens but > it's been known to fix itself with a fresh upload of the same diff. > > On 2013/10/07 14:25:07, Ben Laurie (Google) wrote: >> This review seems to be broken (error: old chunk mismatch). > >> On 5 October 2013 16:27, <mailto:infinity0@gmx.com> wrote: >> > Reviewers: ekasper, >> > >> > Description: >> > implement complete full hash-extending algorithm for > CompactMerkleTree >> > >> > Please review this at http://codereview.appspot.com/14431043/ > > > > https://codereview.appspot.com/14431043/ -- GPG: 4096R/1318EFAC5FBBDBCE git://github.com/infinity0/pubkeys.git
Sign in to reply to this message.
Ah. But d'you think you can generate a diff with that base? upload.py --rev=base_cl ... Commenting on the CL is a pain when the side-by-side diff is broken. On 2013/10/07 14:34:46, infinity0 wrote: > It builds on top of http://codereview.appspot.com/14386045/ - you'll need to > patch that in first. > > On 07/10/13 15:25, Ben Laurie wrote: > > This review seems to be broken (error: old chunk mismatch). > > > > On 5 October 2013 16:27, <mailto:infinity0@gmx.com> wrote: > >> Reviewers: ekasper, > >> > >> Description: > >> implement complete full hash-extending algorithm for CompactMerkleTree > >> > >> Please review this at http://codereview.appspot.com/14431043/ > > > -- > GPG: 4096R/1318EFAC5FBBDBCE > git://github.com/infinity0/pubkeys.git >
Sign in to reply to this message.
On 2013/10/07 14:37:07, infinity0 wrote: Works now, thanks! > Re-uploaded, does it work now? > > On 07/10/13 15:36, mailto:ekasper@google.com wrote: > > Same here, can't view a side-by-side diff. > > > > Can you try uploading again? I've no idea why this error happens but > > it's been known to fix itself with a fresh upload of the same diff. > > > > On 2013/10/07 14:25:07, Ben Laurie (Google) wrote: > >> This review seems to be broken (error: old chunk mismatch). > > > >> On 5 October 2013 16:27, <mailto:infinity0@gmx.com> wrote: > >> > Reviewers: ekasper, > >> > > >> > Description: > >> > implement complete full hash-extending algorithm for > > CompactMerkleTree > >> > > >> > Please review this at http://codereview.appspot.com/14431043/ > > > > > > > > https://codereview.appspot.com/14431043/ > > > -- > GPG: 4096R/1318EFAC5FBBDBCE > git://github.com/infinity0/pubkeys.git >
Sign in to reply to this message.
https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... File src/python/ct/crypto/merkle.py (right): https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:32: bits = bin(i)[2:] return _bits(i)[1] ? https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:155: """Returns the height of the smallest subtree, or 0 if none exists.""" Name this _mintree_height explicitly? What's a smallest subtree? My brain sort of exploded here, could you add a comment and/or an example detailing the algorithm you use to update the tree? https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... File src/python/ct/crypto/merkle_test.py (right): https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle_test.py:118: self.assertEquals(self.tree.root_hash, expected_hash) Apparently assertEquals is deprecated and you're supposed to use assertEqual. It might also be useful to encode the root_hash in hex in the assertion (rather than decode the expected_hash) - assertion failure output is easier to read.
Sign in to reply to this message.
Another drive-by review. As Emilia pointed out, a rough outline of the algorithm would be handy. https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... File src/python/ct/crypto/merkle.py (right): https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:113: bits, bits_set = _bits(tree_size) Nit: Name this size_bits or something similar to indicate these bits are the binary representation of the tree_size. https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:157: return len(self.__bits) - self.__bits.rindex('1') Using strings for bit operations feel a bit unnatural in this context. This specific value is: math.ceil(math.log(self.__tree_size, 2)) - ffs(self.__tree_size) where ffs(x) is defined as: c = 0 while (x&1 == 0): x>>=1 c += 1 return c https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:200: if max_h > 0 and size - idx >= max_size: Move this condition to the while loop? That would make understanding when the loop stops much easier.
Sign in to reply to this message.
https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... File src/python/ct/crypto/merkle.py (right): https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:32: bits = bin(i)[2:] On 2013/10/08 08:30:08, ekasper wrote: > return _bits(i)[1] ? Done, now using binary ops directly. https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:113: bits, bits_set = _bits(tree_size) On 2013/10/09 13:16:56, Eran wrote: > Nit: Name this size_bits or something similar to indicate these bits are the > binary representation of the tree_size. Done, now storing mintree_height instead of all the __bits. https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:155: """Returns the height of the smallest subtree, or 0 if none exists.""" On 2013/10/08 08:30:08, ekasper wrote: > Name this _mintree_height explicitly? > > What's a smallest subtree? My brain sort of exploded here, could you add a > comment and/or an example detailing the algorithm you use to update the tree? Done. https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:157: return len(self.__bits) - self.__bits.rindex('1') On 2013/10/09 13:16:56, Eran wrote: > Using strings for bit operations feel a bit unnatural in this context. > > This specific value is: > math.ceil(math.log(self.__tree_size, 2)) - ffs(self.__tree_size) > > where ffs(x) is defined as: > c = 0 > while (x&1 == 0): > x>>=1 > c += 1 > return c Actually, since rindex() returns a normal index (from the left), what we want is just ffs(self.__tree_size), using the 1-based indexing from [1]. I didn't know about that before, thanks. I was previously storing __bits because I thought "I might need it", but looking at the code, it's only used to calculate mintree_height so I'm now storing just that value instead, and I've changed the function to a property. [1] http://pubs.opengroup.org/onlinepubs/009695399/functions/ffs.html https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:200: if max_h > 0 and size - idx >= max_size: On 2013/10/09 13:16:56, Eran wrote: > Move this condition to the while loop? > That would make understanding when the loop stops much easier. Python doesn't let you assign inside expressions, so I would have to duplicate the max_h and max_size lines. It's usually preferred to use while True rather than repeat that code: https://wiki.python.org/moin/WhileLoop I could do it if you insist, though. https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... File src/python/ct/crypto/merkle_test.py (right): https://codereview.appspot.com/14431043/diff/11001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle_test.py:118: self.assertEquals(self.tree.root_hash, expected_hash) On 2013/10/08 08:30:08, ekasper wrote: > Apparently assertEquals is deprecated and you're supposed to use assertEqual. > > It might also be useful to encode the root_hash in hex in the assertion (rather > than decode the expected_hash) - assertion failure output is easier to read. Done.
Sign in to reply to this message.
Nice, the comments were really helpful. A few more details and it's good to go. https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... File src/python/ct/crypto/merkle.py (right): https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:186: def _mintree_height(self): That seems like an unnecessary amount of access control. Just set a self._mintree_height or self.mintree_height directly if you need access outside the class itself (do you?) Coming from C++, I'm also still adjusting to not being an access control freak myself. Apparently public members are preferrable if you need direct access from outside the class, even if that access is read-only: http://google-styleguide.googlecode.com/svn/trunk/pyguide.html#Access_Control https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:215: # highest bit set == lowest bit set, so reuse what we already have Hm, I don't follow this comment. https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:225: size, mintree_h = 1<<(subtree_h-1), self._mintree_height whitespace around << https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:236: self.__push_subtree_hash(subtree_h+1, next_hash) and here, too, whitespace around the +
Sign in to reply to this message.
https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... File src/python/ct/crypto/merkle.py (right): https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:186: def _mintree_height(self): On 2013/10/11 14:06:38, ekasper wrote: > That seems like an unnecessary amount of access control. Just set a > self._mintree_height or self.mintree_height directly if you need access outside > the class itself (do you?) > > Coming from C++, I'm also still adjusting to not being an access control freak > myself. Apparently public members are preferrable if you need direct access from > outside the class, even if that access is read-only: > > http://google-styleguide.googlecode.com/svn/trunk/pyguide.html#Access_Control Originally it was because I wanted somewhere to document the semantics of mintree_height, but now I've worked that into the docstring for _push_subtree and just use __mintree_height directly. Access isn't needed from outside the class AFAICS. Yeah the double-underscore stuff is not normal for Python code, but it's here now so I ran with it. :p https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:215: # highest bit set == lowest bit set, so reuse what we already have On 2013/10/11 14:06:38, ekasper wrote: > Hm, I don't follow this comment. Explained it a bit better, hopefully. https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:225: size, mintree_h = 1<<(subtree_h-1), self._mintree_height On 2013/10/11 14:06:38, ekasper wrote: > whitespace around << Done. https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:236: self.__push_subtree_hash(subtree_h+1, next_hash) On 2013/10/11 14:06:38, ekasper wrote: > and here, too, whitespace around the + Done.
Sign in to reply to this message.
LGTM https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... File src/python/ct/crypto/merkle.py (right): https://codereview.appspot.com/14431043/diff/16001/src/python/ct/crypto/merkl... src/python/ct/crypto/merkle.py:186: def _mintree_height(self): On 2013/10/14 16:58:42, infinity0 wrote: > On 2013/10/11 14:06:38, ekasper wrote: > > That seems like an unnecessary amount of access control. Just set a > > self._mintree_height or self.mintree_height directly if you need access > outside > > the class itself (do you?) > > > > Coming from C++, I'm also still adjusting to not being an access control freak > > myself. Apparently public members are preferrable if you need direct access > from > > outside the class, even if that access is read-only: > > > > http://google-styleguide.googlecode.com/svn/trunk/pyguide.html#Access_Control > > Originally it was because I wanted somewhere to document the semantics of > mintree_height, but now I've worked that into the docstring for _push_subtree > and just use __mintree_height directly. Access isn't needed from outside the > class AFAICS. It's generally better to avoid implementation details in docstrings but this is a protected method so it's fine. > > Yeah the double-underscore stuff is not normal for Python code, but it's here > now so I ran with it. :p Yah. I might do a global s/__/_/ at some point if I get bored :)
Sign in to reply to this message.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
