title: Data structure used in Log server implementation for Certificate Transparency
body: <p>I attended a security seminar recently which talked about creating log servers to catch any inconsistencies in certificates distributed by the various CAs. Here: <a href="http://www.certificate-transparency.org/log-proofs-work" rel="nofollow">http://www.certificate-transparency.org/log-proofs-work</a>
  The logs will be append-only hash-based merkle trees. Whenever any CA issues a new certificate it will pass the infromation to the log server which will appended the certificate to the original tree. As is described in the link, new certificates will be added on a daily or better weekly basis. Whenever a group of new certificates has to be added, it will be added as a right node of the root. The left node of the root will be the original merkle tree. The root will be a hash of the left and right sub-trees. Given this approach this tree will become highly unbalanced to the left over time. My question is: Is there any better data structure to implement this functionality so that the tree remains balanced as it grows?</p>