Even out levels with existing tree nodes.
When the number of messages in a batch is not a power of two, we need to
introduce dummy nodes. Rather than filling them with zero, use other nodes at
the same level, so we are effectively padding out with more copies of other
messages.
This avoids needing to reason about preimages of the all zero hash.
Change-Id: I9913ac31f7b91064825fdef13e794018dd24e890
diff --git a/go/protocol/protocol.go b/go/protocol/protocol.go
index 9d409ef..a1f27b1 100644
--- a/go/protocol/protocol.go
+++ b/go/protocol/protocol.go
@@ -303,6 +303,11 @@
hashLeaf(&leaf, nonce)
leaves[i] = leaf
}
+ // Fill any extra leaves with an existing leaf, to simplify analysis
+ // that we are not inadvertently signing other messages.
+ for i := len(nonces); i < len(leaves); i++ {
+ leaves[i] = leaves[0]
+ }
ret.values = append(ret.values, leaves)
for i := 1; i < levels; i++ {
@@ -315,6 +320,12 @@
for j := 0; j < len(lastLevel)/2; j++ {
hashNode(&level[j], lastLevel[j*2][:], lastLevel[j*2+1][:])
}
+ // Fill the extra node with an existing node, to simplify
+ // analysis that we are not inadvertently signing other
+ // messages.
+ if len(lastLevel)/2 < len(level) {
+ level[len(lastLevel)/2] = level[0]
+ }
ret.values = append(ret.values, level)
}
diff --git a/server.cc b/server.cc
index bbbf01a..2b16deb 100644
--- a/server.cc
+++ b/server.cc
@@ -190,9 +190,11 @@
ROUGHTIME_DCHECK_GT(num_nodes, 0ul);
size_t level;
for (level = 0; num_nodes > 1; level++, num_nodes /= 2) {
- // Even out the level with a dummy node, if need be.
+ // Even out the level with a dummy node, if need be. Use an existing node
+ // in |tree_|, to simplify analysis that we are not inadvertently signing
+ // other messages.
if (num_nodes % 2 == 1) {
- memset(tree_[level][num_nodes], 0, kNonceLength);
+ memcpy(tree_[level][num_nodes], tree_[level][0], kNonceLength);
num_nodes++;
}
for (size_t i = 0; i < num_nodes; i += 2) {
