tree.mx raw

   1  package mls
   2  
   3  // MLS ratchet tree types (RFC 9420 §7).
   4  // Data types and serialization only — crypto operations (sign, verify,
   5  // parentHash) go in tree_crypto.mx with the cipher suite.
   6  
   7  import "errors"
   8  
   9  var (
  10  	errInvalidLeafNodeSource = errors.New("mls: invalid leaf node source")
  11  	errInvalidNodeType       = errors.New("mls: invalid node type")
  12  )
  13  
  14  func bytesEqual(a, b []byte) bool {
  15  	if len(a) != len(b) {
  16  		return false
  17  	}
  18  	for i := range a {
  19  		if a[i] != b[i] {
  20  			return false
  21  		}
  22  	}
  23  	return true
  24  }
  25  
  26  // --- ParentNode ---
  27  
  28  type parentNode struct {
  29  	encryptionKey  hpkePublicKey
  30  	parentHash     []byte
  31  	unmergedLeaves []leafIndex
  32  }
  33  
  34  func (node *parentNode) unmarshal(r *Reader) error {
  35  	*node = parentNode{}
  36  	var ok bool
  37  	node.encryptionKey, ok = r.readOpaqueVec()
  38  	if !ok {
  39  		return errUnexpectedEOF
  40  	}
  41  	node.parentHash, ok = r.readOpaqueVec()
  42  	if !ok {
  43  		return errUnexpectedEOF
  44  	}
  45  	return r.readVector(func(r *Reader) error {
  46  		v, ok := r.readUint32()
  47  		if !ok {
  48  			return errUnexpectedEOF
  49  		}
  50  		node.unmergedLeaves = append(node.unmergedLeaves, leafIndex(v))
  51  		return nil
  52  	})
  53  }
  54  
  55  func (node *parentNode) marshal(w *Writer) {
  56  	w.writeOpaqueVec([]byte(node.encryptionKey))
  57  	w.writeOpaqueVec(node.parentHash)
  58  	w.writeVector(len(node.unmergedLeaves), func(w *Writer, i int) {
  59  		w.addUint32(uint32(node.unmergedLeaves[i]))
  60  	})
  61  }
  62  
  63  // --- LeafNodeSource ---
  64  
  65  type leafNodeSource uint8
  66  
  67  const (
  68  	leafNodeSourceKeyPackage leafNodeSource = 1
  69  	leafNodeSourceUpdate     leafNodeSource = 2
  70  	leafNodeSourceCommit     leafNodeSource = 3
  71  )
  72  
  73  func (src *leafNodeSource) unmarshal(r *Reader) error {
  74  	b, ok := r.readByte()
  75  	if !ok {
  76  		return errUnexpectedEOF
  77  	}
  78  	*src = leafNodeSource(b)
  79  	switch *src {
  80  	case leafNodeSourceKeyPackage, leafNodeSourceUpdate, leafNodeSourceCommit:
  81  		return nil
  82  	default:
  83  		return errInvalidLeafNodeSource
  84  	}
  85  }
  86  
  87  func (src leafNodeSource) marshal(w *Writer) {
  88  	w.addByte(byte(src))
  89  }
  90  
  91  // --- Capabilities ---
  92  
  93  type capabilities struct {
  94  	versions     []protocolVersion
  95  	cipherSuites []CipherSuite
  96  	extensions   []extensionType
  97  	proposals    []proposalType
  98  	credentials  []credentialType
  99  }
 100  
 101  func (caps *capabilities) unmarshal(r *Reader) error {
 102  	*caps = capabilities{}
 103  
 104  	err := r.readVector(func(r *Reader) error {
 105  		v, ok := r.readUint16()
 106  		if !ok {
 107  			return errUnexpectedEOF
 108  		}
 109  		caps.versions = append(caps.versions, protocolVersion(v))
 110  		return nil
 111  	})
 112  	if err != nil {
 113  		return err
 114  	}
 115  
 116  	err = r.readVector(func(r *Reader) error {
 117  		v, ok := r.readUint16()
 118  		if !ok {
 119  			return errUnexpectedEOF
 120  		}
 121  		caps.cipherSuites = append(caps.cipherSuites, CipherSuite(v))
 122  		return nil
 123  	})
 124  	if err != nil {
 125  		return err
 126  	}
 127  
 128  	err = r.readVector(func(r *Reader) error {
 129  		v, ok := r.readUint16()
 130  		if !ok {
 131  			return errUnexpectedEOF
 132  		}
 133  		caps.extensions = append(caps.extensions, extensionType(v))
 134  		return nil
 135  	})
 136  	if err != nil {
 137  		return err
 138  	}
 139  
 140  	err = r.readVector(func(r *Reader) error {
 141  		v, ok := r.readUint16()
 142  		if !ok {
 143  			return errUnexpectedEOF
 144  		}
 145  		caps.proposals = append(caps.proposals, proposalType(v))
 146  		return nil
 147  	})
 148  	if err != nil {
 149  		return err
 150  	}
 151  
 152  	return r.readVector(func(r *Reader) error {
 153  		v, ok := r.readUint16()
 154  		if !ok {
 155  			return errUnexpectedEOF
 156  		}
 157  		caps.credentials = append(caps.credentials, credentialType(v))
 158  		return nil
 159  	})
 160  }
 161  
 162  func (caps *capabilities) marshal(w *Writer) {
 163  	w.writeVector(len(caps.versions), func(w *Writer, i int) {
 164  		w.addUint16(uint16(caps.versions[i]))
 165  	})
 166  	w.writeVector(len(caps.cipherSuites), func(w *Writer, i int) {
 167  		w.addUint16(uint16(caps.cipherSuites[i]))
 168  	})
 169  	w.writeVector(len(caps.extensions), func(w *Writer, i int) {
 170  		w.addUint16(uint16(caps.extensions[i]))
 171  	})
 172  	w.writeVector(len(caps.proposals), func(w *Writer, i int) {
 173  		w.addUint16(uint16(caps.proposals[i]))
 174  	})
 175  	w.writeVector(len(caps.credentials), func(w *Writer, i int) {
 176  		w.addUint16(uint16(caps.credentials[i]))
 177  	})
 178  }
 179  
 180  // --- Lifetime ---
 181  
 182  type lifetime struct {
 183  	notBefore, notAfter uint64
 184  }
 185  
 186  func (lt *lifetime) unmarshal(r *Reader) error {
 187  	*lt = lifetime{}
 188  	var ok bool
 189  	lt.notBefore, ok = r.readUint64()
 190  	if !ok {
 191  		return errUnexpectedEOF
 192  	}
 193  	lt.notAfter, ok = r.readUint64()
 194  	if !ok {
 195  		return errUnexpectedEOF
 196  	}
 197  	return nil
 198  }
 199  
 200  func (lt *lifetime) marshal(w *Writer) {
 201  	w.addUint64(lt.notBefore)
 202  	w.addUint64(lt.notAfter)
 203  }
 204  
 205  // --- Extension ---
 206  
 207  type extensionType uint16
 208  
 209  const (
 210  	extensionTypeApplicationID        extensionType = 0x0001
 211  	extensionTypeRatchetTree          extensionType = 0x0002
 212  	extensionTypeRequiredCapabilities extensionType = 0x0003
 213  	extensionTypeExternalPub          extensionType = 0x0004
 214  	extensionTypeExternalSenders      extensionType = 0x0005
 215  	// Marmot: KeyPackage reusable for multiple Welcomes (MIP-00)
 216  	ExtensionTypeLastResort extensionType = 0x000a
 217  	// Marmot: Nostr group metadata (MIP-01)
 218  	ExtensionTypeNostrGroupData extensionType = 0xf2ee
 219  )
 220  
 221  type Extension = extension
 222  
 223  type extension struct {
 224  	extensionType extensionType
 225  	extensionData []byte
 226  }
 227  
 228  func NewExtension(t extensionType, data []byte) extension {
 229  	return extension{extensionType: t, extensionData: data}
 230  }
 231  
 232  type ExtensionType = extensionType
 233  
 234  func unmarshalExtensionVec(r *Reader) ([]extension, error) {
 235  	var exts []extension
 236  	err := r.readVector(func(r *Reader) error {
 237  		var ext extension
 238  		v, ok := r.readUint16()
 239  		if !ok {
 240  			return errUnexpectedEOF
 241  		}
 242  		ext.extensionType = extensionType(v)
 243  		ext.extensionData, ok = r.readOpaqueVec()
 244  		if !ok {
 245  			return errUnexpectedEOF
 246  		}
 247  		exts = append(exts, ext)
 248  		return nil
 249  	})
 250  	return exts, err
 251  }
 252  
 253  func marshalExtensionVec(w *Writer, exts []extension) {
 254  	w.writeVector(len(exts), func(w *Writer, i int) {
 255  		ext := exts[i]
 256  		w.addUint16(uint16(ext.extensionType))
 257  		w.writeOpaqueVec(ext.extensionData)
 258  	})
 259  }
 260  
 261  func findExtensionData(exts []extension, t extensionType) []byte {
 262  	for _, ext := range exts {
 263  		if ext.extensionType == t {
 264  			return ext.extensionData
 265  		}
 266  	}
 267  	return nil
 268  }
 269  
 270  // --- LeafNode ---
 271  
 272  type leafNode struct {
 273  	encryptionKey hpkePublicKey
 274  	signatureKey  signaturePublicKey
 275  	credential    Credential
 276  	capabilities  capabilities
 277  
 278  	leafNodeSource leafNodeSource
 279  	lifetime       *lifetime // for leafNodeSourceKeyPackage
 280  	parentHash     []byte    // for leafNodeSourceCommit
 281  
 282  	extensions []extension
 283  	signature  []byte
 284  }
 285  
 286  func (node *leafNode) unmarshal(r *Reader) error {
 287  	*node = leafNode{}
 288  
 289  	var ok bool
 290  	node.encryptionKey, ok = r.readOpaqueVec()
 291  	if !ok {
 292  		return errUnexpectedEOF
 293  	}
 294  	node.signatureKey, ok = r.readOpaqueVec()
 295  	if !ok {
 296  		return errUnexpectedEOF
 297  	}
 298  
 299  	if err := node.credential.unmarshal(r); err != nil {
 300  		return err
 301  	}
 302  	if err := node.capabilities.unmarshal(r); err != nil {
 303  		return err
 304  	}
 305  	if err := node.leafNodeSource.unmarshal(r); err != nil {
 306  		return err
 307  	}
 308  
 309  	var err error
 310  	switch node.leafNodeSource {
 311  	case leafNodeSourceKeyPackage:
 312  		node.lifetime = &lifetime{}
 313  		err = node.lifetime.unmarshal(r)
 314  	case leafNodeSourceCommit:
 315  		node.parentHash, ok = r.readOpaqueVec()
 316  		if !ok {
 317  			err = errUnexpectedEOF
 318  		}
 319  	}
 320  	if err != nil {
 321  		return err
 322  	}
 323  
 324  	exts, err := unmarshalExtensionVec(r)
 325  	if err != nil {
 326  		return err
 327  	}
 328  	node.extensions = exts
 329  
 330  	node.signature, ok = r.readOpaqueVec()
 331  	if !ok {
 332  		return errUnexpectedEOF
 333  	}
 334  	return nil
 335  }
 336  
 337  func (node *leafNode) marshalBase(w *Writer) {
 338  	w.writeOpaqueVec([]byte(node.encryptionKey))
 339  	w.writeOpaqueVec([]byte(node.signatureKey))
 340  	node.credential.marshal(w)
 341  	node.capabilities.marshal(w)
 342  	node.leafNodeSource.marshal(w)
 343  	switch node.leafNodeSource {
 344  	case leafNodeSourceKeyPackage:
 345  		node.lifetime.marshal(w)
 346  	case leafNodeSourceCommit:
 347  		w.writeOpaqueVec(node.parentHash)
 348  	}
 349  	marshalExtensionVec(w, node.extensions)
 350  }
 351  
 352  func (node *leafNode) marshal(w *Writer) {
 353  	node.marshalBase(w)
 354  	w.writeOpaqueVec(node.signature)
 355  }
 356  
 357  // --- LeafNodeTBS ---
 358  
 359  type leafNodeTBS struct {
 360  	node *leafNode
 361  	// for leafNodeSourceUpdate and leafNodeSourceCommit
 362  	groupID   GroupID
 363  	leafIndex leafIndex
 364  }
 365  
 366  func (tbs *leafNodeTBS) marshal(w *Writer) {
 367  	tbs.node.marshalBase(w)
 368  	switch tbs.node.leafNodeSource {
 369  	case leafNodeSourceUpdate, leafNodeSourceCommit:
 370  		w.writeOpaqueVec([]byte(tbs.groupID))
 371  		w.addUint32(uint32(tbs.leafIndex))
 372  	}
 373  }
 374  
 375  // --- UpdatePathNode ---
 376  
 377  type updatePathNode struct {
 378  	encryptionKey       hpkePublicKey
 379  	encryptedPathSecret []hpkeCiphertext
 380  }
 381  
 382  func (node *updatePathNode) unmarshal(r *Reader) error {
 383  	*node = updatePathNode{}
 384  	var ok bool
 385  	node.encryptionKey, ok = r.readOpaqueVec()
 386  	if !ok {
 387  		return errUnexpectedEOF
 388  	}
 389  	return r.readVector(func(r *Reader) error {
 390  		var ct hpkeCiphertext
 391  		if err := ct.unmarshal(r); err != nil {
 392  			return err
 393  		}
 394  		node.encryptedPathSecret = append(node.encryptedPathSecret, ct)
 395  		return nil
 396  	})
 397  }
 398  
 399  func (node *updatePathNode) marshal(w *Writer) {
 400  	w.writeOpaqueVec([]byte(node.encryptionKey))
 401  	w.writeVector(len(node.encryptedPathSecret), func(w *Writer, i int) {
 402  		node.encryptedPathSecret[i].marshal(w)
 403  	})
 404  }
 405  
 406  // --- UpdatePath ---
 407  
 408  type updatePath struct {
 409  	leafNode leafNode
 410  	nodes    []updatePathNode
 411  }
 412  
 413  func (up *updatePath) unmarshal(r *Reader) error {
 414  	*up = updatePath{}
 415  	if err := up.leafNode.unmarshal(r); err != nil {
 416  		return err
 417  	}
 418  	return r.readVector(func(r *Reader) error {
 419  		var node updatePathNode
 420  		if err := node.unmarshal(r); err != nil {
 421  			return err
 422  		}
 423  		up.nodes = append(up.nodes, node)
 424  		return nil
 425  	})
 426  }
 427  
 428  func (up *updatePath) marshal(w *Writer) {
 429  	up.leafNode.marshal(w)
 430  	w.writeVector(len(up.nodes), func(w *Writer, i int) {
 431  		up.nodes[i].marshal(w)
 432  	})
 433  }
 434  
 435  // --- NodeType ---
 436  
 437  type nodeType uint8
 438  
 439  const (
 440  	nodeTypeLeaf   nodeType = 1
 441  	nodeTypeParent nodeType = 2
 442  )
 443  
 444  func (t *nodeType) unmarshal(r *Reader) error {
 445  	b, ok := r.readByte()
 446  	if !ok {
 447  		return errUnexpectedEOF
 448  	}
 449  	*t = nodeType(b)
 450  	switch *t {
 451  	case nodeTypeLeaf, nodeTypeParent:
 452  		return nil
 453  	default:
 454  		return errInvalidNodeType
 455  	}
 456  }
 457  
 458  func (t nodeType) marshal(w *Writer) {
 459  	w.addByte(byte(t))
 460  }
 461  
 462  // --- Node ---
 463  
 464  type node struct {
 465  	nodeType   nodeType
 466  	leafNode   *leafNode   // for nodeTypeLeaf
 467  	parentNode *parentNode // for nodeTypeParent
 468  }
 469  
 470  func (n *node) unmarshal(r *Reader) error {
 471  	*n = node{}
 472  	if err := n.nodeType.unmarshal(r); err != nil {
 473  		return err
 474  	}
 475  	switch n.nodeType {
 476  	case nodeTypeLeaf:
 477  		n.leafNode = &leafNode{}
 478  		return n.leafNode.unmarshal(r)
 479  	case nodeTypeParent:
 480  		n.parentNode = &parentNode{}
 481  		return n.parentNode.unmarshal(r)
 482  	default:
 483  		panic("unreachable")
 484  	}
 485  }
 486  
 487  func (n *node) marshal(w *Writer) {
 488  	n.nodeType.marshal(w)
 489  	switch n.nodeType {
 490  	case nodeTypeLeaf:
 491  		n.leafNode.marshal(w)
 492  	case nodeTypeParent:
 493  		n.parentNode.marshal(w)
 494  	default:
 495  		panic("unreachable")
 496  	}
 497  }
 498  
 499  func (n *node) encryptionKey() hpkePublicKey {
 500  	switch n.nodeType {
 501  	case nodeTypeLeaf:
 502  		return n.leafNode.encryptionKey
 503  	case nodeTypeParent:
 504  		return n.parentNode.encryptionKey
 505  	default:
 506  		panic("unreachable")
 507  	}
 508  }
 509  
 510  // --- RatchetTree ---
 511  
 512  type ratchetTree []*node
 513  
 514  func (tree *ratchetTree) unmarshal(r *Reader) error {
 515  	*tree = ratchetTree{}
 516  	err := r.readVector(func(r *Reader) error {
 517  		present, ok := r.readOptional()
 518  		if !ok {
 519  			return errUnexpectedEOF
 520  		}
 521  		if present {
 522  			n := &node{}
 523  			if err := n.unmarshal(r); err != nil {
 524  				return err
 525  			}
 526  			*tree = append(*tree, n)
 527  		} else {
 528  			*tree = append(*tree, nil)
 529  		}
 530  		return nil
 531  	})
 532  	if err != nil {
 533  		return err
 534  	}
 535  	// Pad to next power of 2 (width + 1 must be power of 2)
 536  	for !isPowerOf2(uint(len(*tree) + 1)) {
 537  		*tree = append(*tree, nil)
 538  	}
 539  	return nil
 540  }
 541  
 542  func (tree ratchetTree) marshal(w *Writer) {
 543  	end := len(tree)
 544  	for end > 0 && tree[end-1] == nil {
 545  		end--
 546  	}
 547  	w.writeVector(len(tree[:end]), func(w *Writer, i int) {
 548  		n := tree[i]
 549  		w.writeOptional(n != nil)
 550  		if n != nil {
 551  			n.marshal(w)
 552  		}
 553  	})
 554  }
 555  
 556  func (tree ratchetTree) numLeaves() numLeaves {
 557  	return numLeavesFromWidth(uint(len(tree)))
 558  }
 559  
 560  func (tree ratchetTree) get(i nodeIndex) *node {
 561  	return tree[int(i)]
 562  }
 563  
 564  func (tree ratchetTree) set(i nodeIndex, nd *node) {
 565  	tree[int(i)] = nd
 566  }
 567  
 568  func (tree ratchetTree) getLeaf(li leafIndex) *leafNode {
 569  	nd := tree.get(li.nodeIndex())
 570  	if nd == nil {
 571  		return nil
 572  	}
 573  	return nd.leafNode
 574  }
 575  
 576  func (tree ratchetTree) resolve(x nodeIndex) []nodeIndex {
 577  	n := tree.get(x)
 578  	if n == nil {
 579  		l, r, ok := x.children()
 580  		if !ok {
 581  			return nil
 582  		}
 583  		return append(tree.resolve(l), tree.resolve(r)...)
 584  	}
 585  	res := []nodeIndex{x}
 586  	if n.nodeType == nodeTypeParent {
 587  		for _, li := range n.parentNode.unmergedLeaves {
 588  			res = append(res, li.nodeIndex())
 589  		}
 590  	}
 591  	return res
 592  }
 593  
 594  func (tree ratchetTree) copy() ratchetTree {
 595  	newTree := ratchetTree([]*node{:len(tree)})
 596  	for i, nd := range tree {
 597  		newTree[i] = nd
 598  	}
 599  	return newTree
 600  }
 601  
 602  func (tree *ratchetTree) add(ln *leafNode) {
 603  	li := leafIndex(0)
 604  	var ni nodeIndex
 605  	found := false
 606  	for {
 607  		ni = li.nodeIndex()
 608  		if int(ni) >= len(*tree) {
 609  			break
 610  		}
 611  		if tree.get(ni) == nil {
 612  			found = true
 613  			break
 614  		}
 615  		li++
 616  	}
 617  	if !found {
 618  		newLen := ((len(*tree) + 1) * 2) - 1
 619  		for len(*tree) < newLen {
 620  			*tree = append(*tree, nil)
 621  		}
 622  	}
 623  
 624  	n := tree.numLeaves()
 625  	p := ni
 626  	for {
 627  		var ok bool
 628  		p, ok = n.parent(p)
 629  		if !ok {
 630  			break
 631  		}
 632  		nd := tree.get(p)
 633  		if nd != nil {
 634  			nd.parentNode.unmergedLeaves = append(nd.parentNode.unmergedLeaves, li)
 635  		}
 636  	}
 637  
 638  	tree.set(ni, &node{
 639  		nodeType: nodeTypeLeaf,
 640  		leafNode: ln,
 641  	})
 642  }
 643  
 644  func (tree ratchetTree) update(li leafIndex, ln *leafNode) {
 645  	ni := li.nodeIndex()
 646  	tree.set(ni, &node{
 647  		nodeType: nodeTypeLeaf,
 648  		leafNode: ln,
 649  	})
 650  	n := tree.numLeaves()
 651  	for {
 652  		var ok bool
 653  		ni, ok = n.parent(ni)
 654  		if !ok {
 655  			break
 656  		}
 657  		tree.set(ni, nil)
 658  	}
 659  }
 660  
 661  func (tree *ratchetTree) remove(li leafIndex) {
 662  	ni := li.nodeIndex()
 663  	n := tree.numLeaves()
 664  	for {
 665  		tree.set(ni, nil)
 666  		var ok bool
 667  		ni, ok = n.parent(ni)
 668  		if !ok {
 669  			break
 670  		}
 671  	}
 672  
 673  	li = leafIndex(n - 1)
 674  	lastPowerOf2 := len(*tree) + 1
 675  	for {
 676  		ni = li.nodeIndex()
 677  		if tree.get(ni) != nil {
 678  			break
 679  		}
 680  		if isPowerOf2(uint(ni)) {
 681  			lastPowerOf2 = int(ni)
 682  		}
 683  		if li == 0 {
 684  			*tree = nil
 685  			return
 686  		}
 687  		li--
 688  	}
 689  	if lastPowerOf2 < len(*tree)+1 {
 690  		*tree = (*tree)[:lastPowerOf2-1]
 691  	}
 692  }
 693  
 694  func (tree *ratchetTree) apply(proposals []proposal, senders []leafIndex) {
 695  	for i, prop := range proposals {
 696  		if prop.proposalType == proposalTypeUpdate {
 697  			tree.update(senders[i], &prop.update.leafNode)
 698  		}
 699  	}
 700  	for _, prop := range proposals {
 701  		if prop.proposalType == proposalTypeRemove {
 702  			tree.remove(prop.remove.removed)
 703  		}
 704  	}
 705  	for _, prop := range proposals {
 706  		if prop.proposalType == proposalTypeAdd {
 707  			tree.add(&prop.add.keyPackage.leafNode)
 708  		}
 709  	}
 710  }
 711  
 712  func (tree ratchetTree) findLeaf(ln *leafNode) (leafIndex, bool) {
 713  	for li := leafIndex(0); li < leafIndex(tree.numLeaves()); li++ {
 714  		nd := tree.getLeaf(li)
 715  		if nd == nil {
 716  			continue
 717  		}
 718  		if !bytesEqual(nd.encryptionKey, ln.encryptionKey) {
 719  			continue
 720  		}
 721  		raw1, err1 := marshalRaw(ln)
 722  		raw2, err2 := marshalRaw(nd)
 723  		return li, err1 == nil && err2 == nil && bytesEqual(raw1, raw2)
 724  	}
 725  	return 0, false
 726  }
 727  
 728  func (tree ratchetTree) keys() (sigKeys, encKeys map[string]bool) {
 729  	sigKeys = map[string]bool{}
 730  	encKeys = map[string]bool{}
 731  	for li := leafIndex(0); li < leafIndex(tree.numLeaves()); li++ {
 732  		nd := tree.getLeaf(li)
 733  		if nd == nil {
 734  			continue
 735  		}
 736  		sigKeys[string(nd.signatureKey)] = true
 737  		encKeys[string(nd.encryptionKey)] = true
 738  	}
 739  	return sigKeys, encKeys
 740  }
 741  
 742  func (tree ratchetTree) supportedCreds() map[credentialType]bool {
 743  	numMembers := 0
 744  	counts := map[credentialType]int{}
 745  	for li := leafIndex(0); li < leafIndex(tree.numLeaves()); li++ {
 746  		nd := tree.getLeaf(li)
 747  		if nd == nil {
 748  			continue
 749  		}
 750  		numMembers++
 751  		for _, ct := range nd.capabilities.credentials {
 752  			counts[ct]++
 753  		}
 754  	}
 755  	result := map[credentialType]bool{}
 756  	for ct, c := range counts {
 757  		if c == numMembers {
 758  			result[ct] = true
 759  		}
 760  	}
 761  	return result
 762  }
 763  
 764  func (tree ratchetTree) filteredDirectPath(x nodeIndex) []nodeIndex {
 765  	n := tree.numLeaves()
 766  	var path []nodeIndex
 767  	for {
 768  		p, ok := n.parent(x)
 769  		if !ok {
 770  			break
 771  		}
 772  		s, ok := n.sibling(x)
 773  		if !ok {
 774  			panic("unreachable")
 775  		}
 776  		if len(tree.resolve(s)) > 0 {
 777  			path = append(path, p)
 778  		}
 779  		x = p
 780  	}
 781  	return path
 782  }
 783  
 784  func hasUnmergedLeaf(pn *parentNode, target leafIndex) bool {
 785  	for _, li := range pn.unmergedLeaves {
 786  		if li == target {
 787  			return true
 788  		}
 789  	}
 790  	return false
 791  }
 792  
 793  func (tree ratchetTree) findParentHash(nodeIndices []nodeIndex, ph []byte) bool {
 794  	for _, x := range nodeIndices {
 795  		nd := tree.get(x)
 796  		if nd == nil {
 797  			continue
 798  		}
 799  		var h []byte
 800  		switch nd.nodeType {
 801  		case nodeTypeLeaf:
 802  			h = nd.leafNode.parentHash
 803  		case nodeTypeParent:
 804  			h = nd.parentNode.parentHash
 805  		}
 806  		if bytesEqual(h, ph) {
 807  			return true
 808  		}
 809  	}
 810  	return false
 811  }
 812  
 813  // --- LeafNode verification ---
 814  
 815  type leafNodeVerifyOptions struct {
 816  	cipherSuite    CipherSuite
 817  	groupID        GroupID
 818  	leafIndex      leafIndex
 819  	supportedCreds map[credentialType]bool
 820  	signatureKeys  map[string]bool
 821  	encryptionKeys map[string]bool
 822  	nowUnix        int64 // 0 = skip lifetime check
 823  }
 824  
 825  func (ln *leafNode) verify(opts *leafNodeVerifyOptions) error {
 826  	if !ln.verifySignature(opts.cipherSuite, opts.groupID, opts.leafIndex) {
 827  		return errors.New("mls: leaf node signature verification failed")
 828  	}
 829  	if !opts.supportedCreds[ln.credential.credentialType] {
 830  		return errors.New("mls: credential type not supported by all members")
 831  	}
 832  	if ln.lifetime != nil && opts.nowUnix != 0 {
 833  		if !ln.lifetime.verifyAt(opts.nowUnix) {
 834  			return errors.New("mls: lifetime verification failed")
 835  		}
 836  	}
 837  	supportedExts := map[extensionType]bool{}
 838  	for _, et := range ln.capabilities.extensions {
 839  		supportedExts[et] = true
 840  	}
 841  	for _, ext := range ln.extensions {
 842  		if !supportedExts[ext.extensionType] {
 843  			return errors.New("mls: extension type not supported by leaf node")
 844  		}
 845  	}
 846  	if opts.signatureKeys[string(ln.signatureKey)] {
 847  		return errors.New("mls: duplicate signature key")
 848  	}
 849  	if opts.encryptionKeys[string(ln.encryptionKey)] {
 850  		return errors.New("mls: duplicate encryption key")
 851  	}
 852  	return nil
 853  }
 854  
 855  const maxLeafNodeLifetime = 90 * 24 * 3600 // 90 days in seconds
 856  
 857  func (lt *lifetime) verifyAt(nowUnix int64) bool {
 858  	notBefore := int64(lt.notBefore)
 859  	notAfter := int64(lt.notAfter)
 860  	duration := notAfter - notBefore
 861  	if duration <= 0 || duration > maxLeafNodeLifetime {
 862  		return false
 863  	}
 864  	return nowUnix > notBefore && notAfter > nowUnix
 865  }
 866