Add parent hash test vector

bifurcation commented 1 year ago

A few observations on trying to verify:

Leaf node hashes appear to be using node index instead of leaf index (== node / 2). With that change, I successfully verify all of the leaf node hashes.
Parent node verifications are all failing, but I don't have a good guess as to why. It will probably become immediately apparent on comparing hash inputs. FWIW, the hash input I see for node 1 in the first test case is as follows (with my decoding annotations) (which looks correct based on my manual decoding of the tree (?)):

02 // node_type = parent
01 // optional is present 
  20 bb36393642a89107834af9e11f46a390aee605dc764331d911a5079df4fe1b4b // public_key
  00 // parent_hash
  00 // unmerged_leaves
20 5dcd9c08cec65920684cea11427ff12ba539b3ab59f57464b99481c461322805 // left_hash
20 dddbb4c93114e03cb5b22195a48a6440d7bf33500e1ec6c22baa24a5ecb1cbec // right_hash

It looks like tree hashes are not provided for all nodes. In scenarios 2 and 5 (counting from 0; thus test cases, 2, 5, 8, 11, ...), I see 13 != 15 and 17 != 31 nodes, respectively. I suspect this is because you're suppressing output for blank nodes on the right of the tree. But those nodes do have tree hashes, and they feed into higher-level tree hashes. So it seems important to test them as well.

mulmarta commented 1 year ago

Thank you for debugging! I feel bad, all bugs were mine here. (FWIW I had a node index in all hash inputs for some reason, hence the failure). Should be better now.

bifurcation commented 1 year ago

OK, current status with MLSpp is getting close:

Test	?
Tree Hash	✅
Parent Hash	✅
Resolutions	✅
Leaf Signatures

This caught a bug in MLSpp, where I was not properly binding in the LeafIndex in the context. But even after fixing that, it still fails. Here's the signature input I see for the first leaf in the first test vector (with my manual decoding annotations):

13 // label
  4d4c5320312e30204c6561664e6f6465544253 // "MLS 1.0 LeafNodeTBS"

40a9 // content
  20 b6c7a68f026bc6c2ef34ddce96eb66e8696c4589159ec742c12e3730d4a2976c // encryption_key
  20 2d12c931152dbee44b56ecbbd6ca987a1fab43b2c03794e85bf7f261f9e0a4fc // signature_key

  0001 // credential_type = basic
    05 416c696365 // "Alice"

  // capabilities
  02 0001
  0e 0001 0002 0003 0004 0005 0006 0007
  00
  00
  02 0001

  03 // leaf_node_source = commit
    20 0efe32f430eb2ef87842c54cfb7135ee91ee99b3d7ac71c4bf69dddf43c05f27 // parent_hash

  00 // extensions

  20 18ebfe41f12445f09a5fe5f864136d150d53f655c9d8824fce06c92990db2d69 // group_id
  00000000 // leaf_index

That looks right to me according to the LeafNodeTBS struct in the spec. I verified that the public key and signature decoded properly. Maybe you're encoding the LeafNodeTBS differently?

mulmarta commented 1 year ago

Maybe you're encoding the LeafNodeTBS differently?

Good guess! We weren't using variable length encoding properly. I grepped the whole repo now, and this seems to be the last instance where it was wrong.

bifurcation commented 1 year ago

This verifies with MLSpp now!

mlswg / mls-implementations

Add parent hash test vector #91