implement a proper representation of the compact tree

implement a proper representation of the compact tree

does book-keeping and maintenance of data structures and state in the monitor. the actual hashing algorithm for extending existing trees will be in a separate patch after this one, and likely only affect merkle.py (plus the FLAG pruning).

[infinity0, 2013-10-04 17:26:59]

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle.py
File src/python/ct/crypto/merkle.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:50: return "%s(%r)" % (self.__class__.__name__,
self.hashfunc)
The reason why I changed this, was because repr() in python is supposed to
output (close to) raw python code that can be eval()d to the original object.

[ekasper, 2013-10-08 08:17:11]

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
File src/python/ct/client/monitor.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
src/python/ct/client/monitor.py:61: if self.__verified_tree:
When would this be false?

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
File src/python/ct/client/monitor_test.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
src/python/ct/client/monitor_test.py:104: except:
Assert methods can directly accept an optional message argument, like so:

self.assertEqual(a, b, msg="Boom")

But isn't it default behaviour to output the two states anyway?

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle.py
File src/python/ct/crypto/merkle.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:31: def count_bits_set(i):
Can you explain what this does? Why [2:]?

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:35: def foldr(binop, ll):
Use reduce().

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:50: return "%s(%r)" % (self.__class__.__name__,
self.hashfunc)
On 2013/10/04 17:26:59, infinity0 wrote:
> The reason why I changed this, was because repr() in python is supposed to
> output (close to) raw python code that can be eval()d to the original object.

Ack, thanks.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:75: return self.hash_empty(), []
Can you add a docstring for this method, please?

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:103: self.__hashes = []
self__hashes is presumably the list of hashes that are still mutable? Add a
comment?

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:116: """Load this tree from a dumb data object
for serialisation."""
Describe the dumb data object :)

Also, looks like you create a copy twice? Once here and once in _update.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:140: def hashes(self):
Hm, properties are supposed to be very lightweight accessors - not sure if
creating a copy of a list is lightweight.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:144: def root_hash(self):
Same here, probably shouldn't disguise it as a property if it involves a
significant amount of work.

[Eran, 2013-10-09 12:42:13]

drive-by review.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle.py
File src/python/ct/crypto/merkle.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:31: def count_bits_set(i):
On 2013/10/08 08:17:11, ekasper wrote:
> Can you explain what this does? Why [2:]?

It seems that the number is converted to a binary string '0b...' so [2:] is used
to truncate the string.
A much more traditional way of counting the bits set to 1 is to increment a
counter with the result of (i & 1), then shifting i by one bit.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:140: def hashes(self):
On 2013/10/08 08:17:11, ekasper wrote:
> Hm, properties are supposed to be very lightweight accessors - not sure if
> creating a copy of a list is lightweight.

Consider returning a tuple rather than a mutable list.

[infinity0, 2013-10-10 11:42:54]

Will do some tests re the bit-counting stuff.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
File src/python/ct/client/monitor.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
src/python/ct/client/monitor.py:61: if self.__verified_tree:
On 2013/10/08 08:17:11, ekasper wrote:
> When would this be false?

This would ignore empty trees, which was otherwise causing a test to fail.

Instead, now I've fixed the test to match against an empty tree instead of no
tree, and removed this conditional here.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
File src/python/ct/client/monitor_test.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
src/python/ct/client/monitor_test.py:104: except:
On 2013/10/08 08:17:11, ekasper wrote:
> Assert methods can directly accept an optional message argument, like so:
> 
> self.assertEqual(a, b, msg="Boom")
> 
> But isn't it default behaviour to output the two states anyway?
> 

Done - default behaviour of assertEquals() is to use repr() not str() which
looks like 

AssertionError: <ct.proto.client_pb2.MonitorState object at 0x140d258> !=
<ct.proto.client_pb2.MonitorState object at 0x13fd940>

which isn't very useful.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle.py
File src/python/ct/crypto/merkle.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:31: def count_bits_set(i):
On 2013/10/09 12:42:13, Eran wrote:
> On 2013/10/08 08:17:11, ekasper wrote:
> > Can you explain what this does? Why [2:]?
> 
> It seems that the number is converted to a binary string '0b...' so [2:] is
used
> to truncate the string.
> A much more traditional way of counting the bits set to 1 is to increment a
> counter with the result of (i & 1), then shifting i by one bit.

It feels dirty to do bit operations in python. I'll run some tests...

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:35: def foldr(binop, ll):
On 2013/10/08 08:17:11, ekasper wrote:
> Use reduce().

Done.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:75: return self.hash_empty(), []
On 2013/10/08 08:17:11, ekasper wrote:
> Can you add a docstring for this method, please?

Done.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:103: self.__hashes = []
On 2013/10/08 08:17:11, ekasper wrote:
> self__hashes is presumably the list of hashes that are still mutable? Add a
> comment?

The opposite, *immutable* :p.

Done, added to class docstring.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:116: """Load this tree from a dumb data object
for serialisation."""
On 2013/10/08 08:17:11, ekasper wrote:
> Describe the dumb data object :)
> 
> Also, looks like you create a copy twice? Once here and once in _update.

Done, changing to tuple representation gets rid of this problem - tuple(x) just
returns x instead of allocating a new tuple, if x is already a tuple.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:140: def hashes(self):
On 2013/10/09 12:42:13, Eran wrote:
> On 2013/10/08 08:17:11, ekasper wrote:
> > Hm, properties are supposed to be very lightweight accessors - not sure if
> > creating a copy of a list is lightweight.
> 
> Consider returning a tuple rather than a mutable list.

Done.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:144: def root_hash(self):
On 2013/10/08 08:17:11, ekasper wrote:
> Same here, probably shouldn't disguise it as a property if it involves a
> significant amount of work.

Added a cache for the value, is this better?

[infinity0, 2013-10-10 14:32:39]

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle.py
File src/python/ct/crypto/merkle.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:31: def count_bits_set(i):
On 2013/10/09 12:42:13, Eran wrote:
> On 2013/10/08 08:17:11, ekasper wrote:
> > Can you explain what this does? Why [2:]?
> 
> It seems that the number is converted to a binary string '0b...' so [2:] is
used
> to truncate the string.
> A much more traditional way of counting the bits set to 1 is to increment a
> counter with the result of (i & 1), then shifting i by one bit.

Done - lifted an even more efficient one off the python wiki.

[ekasper, 2013-10-11 11:54:09]

Only a few minor comments left.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
File src/python/ct/client/monitor_test.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/client/monito...
src/python/ct/client/monitor_test.py:104: except:
On 2013/10/10 11:42:54, infinity0 wrote:
> On 2013/10/08 08:17:11, ekasper wrote:
> > Assert methods can directly accept an optional message argument, like so:
> > 
> > self.assertEqual(a, b, msg="Boom")
> > 
> > But isn't it default behaviour to output the two states anyway?
> > 
> 
> Done - default behaviour of assertEquals() is to use repr() not str() which
> looks like 
> 
> AssertionError: <ct.proto.client_pb2.MonitorState object at 0x140d258> !=
> <ct.proto.client_pb2.MonitorState object at 0x13fd940>
> 
> which isn't very useful.

Ah, I see! Thanks for explaining.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle.py
File src/python/ct/crypto/merkle.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:35: def foldr(binop, ll):
On 2013/10/10 11:42:54, infinity0 wrote:
> On 2013/10/08 08:17:11, ekasper wrote:
> > Use reduce().
> 
> Done.

I've meanwhile learned that you should use a for loop instead of reduce (linter
will nag). Sorry.

Since this foldr is only used with hash_children to fold hashes (I think), make
it an explicit fold_hashes() method of the TreeHasher?

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:144: def root_hash(self):
On 2013/10/10 11:42:54, infinity0 wrote:
> On 2013/10/08 08:17:11, ekasper wrote:
> > Same here, probably shouldn't disguise it as a property if it involves a
> > significant amount of work.
> 
> Added a cache for the value, is this better?

Hm, well, the cache is a good idea but I would still remove the @property, which
suggests it's a read-only op.

I think it's fine to have to call root_hash(), and you could add a comment that
this triggers computation if the tree has changed.

[infinity0, 2013-10-14 16:55:27]

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle.py
File src/python/ct/crypto/merkle.py (right):

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:35: def foldr(binop, ll):
On 2013/10/11 11:54:09, ekasper wrote:
> On 2013/10/10 11:42:54, infinity0 wrote:
> > On 2013/10/08 08:17:11, ekasper wrote:
> > > Use reduce().
> > 
> > Done.
> 
> I've meanwhile learned that you should use a for loop instead of reduce
(linter
> will nag). Sorry.
> 
> Since this foldr is only used with hash_children to fold hashes (I think),
make
> it an explicit fold_hashes() method of the TreeHasher?
> 

Done.

https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
src/python/ct/crypto/merkle.py:144: def root_hash(self):
On 2013/10/11 11:54:09, ekasper wrote:
> On 2013/10/10 11:42:54, infinity0 wrote:
> > On 2013/10/08 08:17:11, ekasper wrote:
> > > Same here, probably shouldn't disguise it as a property if it involves a
> > > significant amount of work.
> > 
> > Added a cache for the value, is this better?
> 
> Hm, well, the cache is a good idea but I would still remove the @property,
which
> suggests it's a read-only op.
> 
> I think it's fine to have to call root_hash(), and you could add a comment
that
> this triggers computation if the tree has changed.
> 

Done.

[ekasper, 2013-10-16 13:51:00]

LGTM

Job well done. I'm out of office atm so it may take a day or two before I get to
pushing this upstream.

On 2013/10/14 16:55:27, infinity0 wrote:
>
https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle.py
> File src/python/ct/crypto/merkle.py (right):
> 
>
https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
> src/python/ct/crypto/merkle.py:35: def foldr(binop, ll):
> On 2013/10/11 11:54:09, ekasper wrote:
> > On 2013/10/10 11:42:54, infinity0 wrote:
> > > On 2013/10/08 08:17:11, ekasper wrote:
> > > > Use reduce().
> > > 
> > > Done.
> > 
> > I've meanwhile learned that you should use a for loop instead of reduce
> (linter
> > will nag). Sorry.
> > 
> > Since this foldr is only used with hash_children to fold hashes (I think),
> make
> > it an explicit fold_hashes() method of the TreeHasher?
> > 
> 
> Done.
> 
>
https://codereview.appspot.com/14386045/diff/3001/src/python/ct/crypto/merkle...
> src/python/ct/crypto/merkle.py:144: def root_hash(self):
> On 2013/10/11 11:54:09, ekasper wrote:
> > On 2013/10/10 11:42:54, infinity0 wrote:
> > > On 2013/10/08 08:17:11, ekasper wrote:
> > > > Same here, probably shouldn't disguise it as a property if it involves a
> > > > significant amount of work.
> > > 
> > > Added a cache for the value, is this better?
> > 
> > Hm, well, the cache is a good idea but I would still remove the @property,
> which
> > suggests it's a read-only op.
> > 
> > I think it's fine to have to call root_hash(), and you could add a comment
> that
> > this triggers computation if the tree has changed.
> > 
> 
> Done.