Create Test Vectors

[gdbelvin]

A set of test vectors for

• Tree hashing
• VRF
• Other crypto functions

Would be helpful for assessing cross-project and cross-language compatibility.
I've begun doing this in google/keytransparency#613

[vqhuy]

Thanks @gdbelvin, I've also begun doing this in #178.

Note that there is a difference between your tree hashing and ours: we use treeNonce []byte instead of treeID uint64.

[gdbelvin]

Would you be interested in putting a maximum length on the treeNonce for compatibility?
Would be awesome to have a common interface.

[vqhuy]

@gdbelvin

Would you be interested in putting a maximum length on the treeNonce for compatibility?

In our implementation, it is a 32-byte array. Do you have any idea how should the interface be for compatibility?

/cc @masomel @arlolra @liamsi

[gdbelvin]

Hmm, I wonder if we could hash the TreeID along with extra context onto the 32 byte nonce?

…

On Wed, Jun 21, 2017 at 5:16 PM Vu Quoc Huy ***@***.***> wrote: @gdbelvin <https://github.com/gdbelvin> Would you be interested in putting a maximum length on the treeNonce for compatibility? In our implementation, it is a 32-byte array. Do you have any idea how should the interface be for compatibility? /cc @masomel <https://github.com/masomel> @arlolra <https://github.com/arlolra> @liamsi <https://github.com/liamsi> — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#177 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAMHTtRHLPdcpYTDqRch5VR4HbqaUjtIks5sGUHbgaJpZM4N-IQH> .

[gdbelvin]

After some more thought, I'd love to jump on a call to discuss this.
An 8 byte nonce would give us 32 bits of security before two tree nonces accidentally collided with each other. 2^32 trees would indeed be a lot of CONIKS and Key Transparency servers 👍. Is there a reason for more than 32 bits of security in the tree nonce?

[liamsi]

As far as I remember this was discussed quite a while ago and we've decided to reuse HashSizeByte for simplicity (not introducing another constant) and some extra-bits of security. Another related reason was that we've decided to always hash the output of the system's randomness (and we use a 32-byte hash for that). But I agree that a 64-bit tree-nonce should be sufficient.

[vqhuy]

I think I don't want to let users (the developer/operator) supply the tree ID. As stated somewhere, maintaining the uniqueness of the counter (in this case the map/tree ID) is nontrivial.
As discussed at google/keytransparency#65 (comment), I'd love to know the reason why KT still use the tree nonce.

[gdbelvin]

Trillian (the distributed merkle tree database) generates the treeID behind the scenes - the developers don't get to pick it.

As for maintaining uniqueness of the nonce, 64 bits is enough to ensure uniqueness for up to 2^32 servers.

[liamsi]

@c633 Currently, the TreeID is generated here: https://github.com/google/trillian/blob/9d527702a6bcb53cc11fa5d2b99a115bf2d3c353/storage/tree_id.go#L23-L30

[vqhuy]

Thanks for the explanation! Let's see what others say.