mlswg / mls-implementations

Coordination of implementation and interop specific details
110 stars 14 forks source link

Add tree hash inside Tree Operations test vector #167

Closed TWal closed 1 year ago

TWal commented 1 year ago

Consider the following tree:

              R
        ______|______
       /             \
      _               _
    __|__           __|__
   /     \         /     \
  _       _       _       _
 / \     / \     / \     / \
A   _   _   _   _   _   _   H

In a test where H is removed, several implementations could have differing candidate_tree_after while having the same tree_after:

For example, if the implementation removes but forget to truncate, we would have the following tree:

              _
        ______|______
       /             \
      _               _
    __|__           __|__
   /     \         /     \
  _       _       _       _
 / \     / \     / \     / \
A   _   _   _   _   _   _   _

Or if the implementation truncate after removing, but only one level, the tree could look like this:

      _      
    __|__    
   /     \   
  _       _  
 / \     / \ 
A   _   _   _

However, in all that cases, the tree_after would only contain one node (A), because rightmost blank nodes are trimmed during the serialization.

This PR adds a tree hash, that would catch this differing behavior between the implementations.

bifurcation commented 1 year ago

LGTM modulo one nit. I filed PRs with implementations:

https://github.com/mlswg/mls-implementations/pull/168 https://github.com/cisco/mlspp/pull/352