tree

package
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 25, 2026 License: MIT Imports: 5 Imported by: 0

Documentation

Overview

Package tree implements the TreeKEM ratchet tree from RFC 9420 section 7.

The representation is array-based, following the left-balanced binary tree layout described in RFC 9420 section 7.1: a tree with n leaves has width 2*n - 1, leaves sit at even indices, and parent nodes sit at odd indices. All tree math, resolution, and direct-path operations are pure functions on NodeIndex values. Tree state (LeafNode / ParentNode contents, blanking) is layered on top in tree.go.

Index

Constants

This section is empty.

Variables

View Source 
var ErrTreeFull = errors.New("tree: no blank leaf available")

ErrTreeFull is returned by AddLeaf when no blank slot is available and the tree would need to extend but the caller asked for in-place insertion.

Functions

func HPKEKeysFromPathSecret 

func HPKEKeysFromPathSecret(pathSecret []byte) (crypto.HPKEPrivateKey, crypto.HPKEPublicKey, error)

HPKEKeysFromPathSecret derives the per-node HPKE keypair from a path secret per RFC 9420 section 7.4: 

node_secret = ExpandWithLabel(path_secret, "node", "", KDF.Nh)
(node_priv, node_pub) = DeriveKeyPair(node_secret)

func Hash 

func Hash(t *Tree) ([]byte, error)

Hash returns the tree hash of t, computed recursively per RFC 9420 section 7.8. 

struct {
    NodeType node_type;
    select (Node.node_type) {
        case leaf:   LeafNodeHashInput leaf_node_hash_input;
        case parent: ParentNodeHashInput parent_node_hash_input;
    };
} TreeHashInput;

struct {
    uint32 leaf_index;
    optional<LeafNode> leaf_node;
} LeafNodeHashInput;

struct {
    optional<ParentNode> parent_node;
    opaque               left_hash<V>;
    opaque               right_hash<V>;
} ParentNodeHashInput;

The tree's hash is the recursive hash rooted at Root(width).

func LeafCount 

func LeafCount(width uint32) uint32

LeafCount returns the number of leaf slots in a tree with the given node width. Returns 0 if width is 0.

func NextPathSecret 

func NextPathSecret(prev []byte) ([]byte, error)

NextPathSecret derives the next path_secret in the chain per RFC 9420 section 7.4: 

path_secret[n+1] = DeriveSecret(path_secret[n], "path")

func NodeWidth 

func NodeWidth(leafCount uint32) uint32

NodeWidth returns the array width (number of nodes) for a tree with the given number of leaves. Width is 2*n - 1 for n >= 1, and 0 for n == 0.

Types

type Capabilities 

type Capabilities struct {
	Versions     []ProtocolVersion
	Ciphersuites []uint16
	Extensions   []ExtensionType
	Proposals    []ProposalType
	Credentials  []CredentialType
}

Capabilities advertises the protocol features a leaf supports (RFC 9420 section 7.2). All five vectors are uint16-element variable-length vectors under the MLS wire format.

func (Capabilities) MarshalMLS 

func (c Capabilities) MarshalMLS(e *mlstls.Encoder) error

MarshalMLS encodes Capabilities. Empty vectors are valid.

func (*Capabilities) UnmarshalMLS 

func (c *Capabilities) UnmarshalMLS(d *mlstls.Decoder) error

UnmarshalMLS decodes Capabilities.

type Credential 

type Credential struct {
	Type     CredentialType
	Identity []byte
}

Credential is the basic credential payload used by a LeafNode to identify its owner (RFC 9420 section 5.3.1).

func BasicCredential 

func BasicCredential(identity []byte) Credential

BasicCredential is a convenience constructor.

func (Credential) MarshalMLS 

func (c Credential) MarshalMLS(e *mlstls.Encoder) error

MarshalMLS encodes a Credential. Only the basic credential variant is supported; richer types return an error so callers fail loudly.

func (*Credential) UnmarshalMLS 

func (c *Credential) UnmarshalMLS(d *mlstls.Decoder) error

UnmarshalMLS decodes a Credential.

type CredentialType 

type CredentialType uint16

CredentialType identifies a credential format (RFC 9420 section 5.3). 

const (
	CredentialBasic CredentialType = 1
	CredentialX509  CredentialType = 2
)

type Extension 

type Extension struct {
	Type ExtensionType
	Data []byte
}

Extension carries an extension_type plus extension_data per RFC 9420 section 13.

func (Extension) MarshalMLS 

func (x Extension) MarshalMLS(e *mlstls.Encoder) error

MarshalMLS encodes an Extension.

func (*Extension) UnmarshalMLS 

func (x *Extension) UnmarshalMLS(d *mlstls.Decoder) error

UnmarshalMLS decodes an Extension.

type ExtensionType 

type ExtensionType uint16

ExtensionType is the registry identifier for an MLS extension (RFC 9420 section 13).

type LeafIndex 

type LeafIndex uint32

LeafIndex identifies a leaf slot. A LeafIndex of L corresponds to NodeIndex(2*L).

func (LeafIndex) ToNode 

func (l LeafIndex) ToNode() NodeIndex

ToNode returns the NodeIndex for the leaf.

type LeafNode 

type LeafNode struct {
	EncryptionKey crypto.HPKEPublicKey
	SignatureKey  crypto.SignaturePublicKey
	Credential    Credential
	Capabilities  Capabilities
	Source        LeafNodeSource
	Lifetime      Lifetime
	ParentHash    []byte
	Extensions    []Extension
	Signature     []byte
}

LeafNode is a member's public state in the ratchet tree (RFC 9420 section 7.2). 

struct {
    HPKEPublicKey       encryption_key;
    SignaturePublicKey  signature_key;
    Credential          credential;
    Capabilities        capabilities;
    LeafNodeSource      leaf_node_source;
    select (LeafNode.leaf_node_source) {
        case key_package: Lifetime  lifetime;
        case update:      struct{};
        case commit:      opaque    parent_hash<V>;
    };
    Extension           extensions<V>;
    opaque              signature<V>;
} LeafNode;

func (*LeafNode) MarshalLeafTBS 

func (l *LeafNode) MarshalLeafTBS(e *mlstls.Encoder, groupID []byte, leafIndex uint32) error

MarshalLeafTBS encodes the to-be-signed form of LeafNode for use with crypto.SignWithLabel ("LeafNodeTBS"). It is the same as MarshalMLS up to (but not including) the signature, with extra context appended for the update / commit sources per RFC 9420 section 7.2: 

select (LeafNode.leaf_node_source) {
    case key_package: struct{};
    case update:      opaque group_id<V>;
                      uint32 leaf_index;
    case commit:      opaque group_id<V>;
                      uint32 leaf_index;
};

groupID and leafIndex are ignored for source=key_package.

func (*LeafNode) MarshalMLS 

func (l *LeafNode) MarshalMLS(e *mlstls.Encoder) error

MarshalMLS encodes the full LeafNode including the signature.

func (*LeafNode) UnmarshalMLS 

func (l *LeafNode) UnmarshalMLS(d *mlstls.Decoder) error

UnmarshalMLS decodes a LeafNode written by MarshalMLS.

type LeafNodeSource 

type LeafNodeSource uint8

LeafNodeSource identifies how a LeafNode came to occupy its slot (RFC 9420 section 7.2). 

const (
	LeafNodeSourceKeyPackage LeafNodeSource = 1
	LeafNodeSourceUpdate     LeafNodeSource = 2
	LeafNodeSourceCommit     LeafNodeSource = 3
)

type Lifetime 

type Lifetime struct {
	NotBefore uint64
	NotAfter  uint64
}

Lifetime bounds when a KeyPackage is considered valid (RFC 9420 section 7.2).

func (Lifetime) MarshalMLS 

func (l Lifetime) MarshalMLS(e *mlstls.Encoder) error

MarshalMLS encodes a Lifetime as two big-endian uint64.

func (*Lifetime) UnmarshalMLS 

func (l *Lifetime) UnmarshalMLS(d *mlstls.Decoder) error

UnmarshalMLS decodes a Lifetime.

type Node 

type Node struct {
	Leaf   *LeafNode
	Parent *ParentNode
}

Node is an inhabitant of one slot in the ratchet tree array. Exactly one of Leaf or Parent is non-nil for a populated slot; both are nil for a blank slot.

func (*Node) IsBlank 

func (n *Node) IsBlank() bool

IsBlank reports whether the slot is unpopulated.

type NodeIndex 

type NodeIndex uint32

NodeIndex identifies a position in the array layout of a ratchet tree (RFC 9420 section 7.1). Even indices are leaves, odd indices are parents.

func CommonAncestor 

func CommonAncestor(x, y NodeIndex) NodeIndex

CommonAncestor returns the lowest node that has both x and y in its subtree.

func Root 

func Root(width uint32) NodeIndex

Root returns the NodeIndex of the root of a tree with the given node width. Panics on width == 0.

For a left-balanced tree with width w = 2*n - 1, the root sits at index 2^(ceil(log2(n))) - 1. In binary terms it is the largest "all ones" value that fits in w, equivalently (1 << (bits.Len32(w) - 1)) - 1.

func (NodeIndex) Copath 

func (n NodeIndex) Copath(width uint32) []NodeIndex

Copath returns the siblings of every node on n's direct path. The result is parallel to DirectPath: copath[i] is the sibling of the i-th direct-path node's predecessor (i.e., the sibling encountered while climbing from n to the root).

Concretely: the first copath entry is n's sibling; the next is the sibling of n's parent; and so on up to (but not including) the root.

func (NodeIndex) DirectPath 

func (n NodeIndex) DirectPath(width uint32) []NodeIndex

DirectPath returns the nodes between n's parent and the root, inclusive, in order. For the root, returns an empty slice.

func (NodeIndex) IsLeaf 

func (n NodeIndex) IsLeaf() bool

IsLeaf reports whether n addresses a leaf.

func (NodeIndex) Left 

func (n NodeIndex) Left() (NodeIndex, bool)

Left returns the left child of n. Returns (0, false) if n is a leaf.

func (NodeIndex) Level 

func (n NodeIndex) Level() uint32

Level returns the height of n in the tree. Leaves are at level 0.

Per RFC 9420 section 7.1, level(x) is the number of trailing 1-bits in x's binary representation. Equivalently it is the count of trailing zeros of x + 1.

func (NodeIndex) Parent 

func (n NodeIndex) Parent(width uint32) (NodeIndex, bool)

Parent returns the parent of n in a tree of the given width. Returns (0, false) if n is the root.

func (NodeIndex) Right 

func (n NodeIndex) Right() (NodeIndex, bool)

Right returns the right child of n. Returns (0, false) if n is a leaf.

func (NodeIndex) Sibling 

func (n NodeIndex) Sibling(width uint32) (NodeIndex, bool)

Sibling returns n's sibling in a tree of the given width. Returns (0, false) if n is the root.

func (NodeIndex) ToLeaf 

func (n NodeIndex) ToLeaf() (LeafIndex, bool)

ToLeaf returns the LeafIndex for the node if it is a leaf, and false otherwise.

type ParentNode 

type ParentNode struct {
	EncryptionKey  crypto.HPKEPublicKey
	ParentHash     []byte
	UnmergedLeaves []LeafIndex
}

ParentNode is the public state of a populated inner ratchet-tree node (RFC 9420 section 7.6). 

struct {
    HPKEPublicKey encryption_key;
    opaque        parent_hash<V>;
    LeafIndex     unmerged_leaves<V>;
} ParentNode;

func (*ParentNode) MarshalMLS 

func (p *ParentNode) MarshalMLS(e *mlstls.Encoder) error

MarshalMLS encodes a ParentNode.

func (*ParentNode) UnmarshalMLS 

func (p *ParentNode) UnmarshalMLS(d *mlstls.Decoder) error

UnmarshalMLS decodes a ParentNode.

type ProposalType 

type ProposalType uint16

ProposalType is the registry identifier for an MLS proposal (RFC 9420 section 12.1). 

const (
	ProposalAdd     ProposalType = 1
	ProposalUpdate  ProposalType = 2
	ProposalRemove  ProposalType = 3
	ProposalPSK     ProposalType = 4
	ProposalReinit  ProposalType = 5
	ProposalExtJoin ProposalType = 6
	ProposalGCE     ProposalType = 7
)

type ProtocolVersion 

type ProtocolVersion uint16

ProtocolVersion identifies the MLS protocol version (RFC 9420 section 6). 

const ProtocolVersionMLS10 ProtocolVersion = 1

ProtocolVersionMLS10 is the only version currently defined.

type Tree 

type Tree struct {
	// contains filtered or unexported fields
}

Tree is an array-backed ratchet tree. The Nodes slice has length NodeWidth(LeafCount()), even indices are leaf slots, odd indices are parent slots. A nil entry indicates a blank slot.

func FromNodes 

func FromNodes(snap []*Node) (*Tree, error)

FromNodes constructs a tree from a snapshot of node slots, validating that the width corresponds to a valid left-balanced layout (width = 2*n - 1 for some n >= 1). Nil entries are treated as blank slots. The returned tree owns its own slice; the caller is free to reuse or modify the snapshot afterwards.

func New 

func New(creator *LeafNode) *Tree

New constructs a tree containing a single populated leaf at index 0. Width is 1; there are no parent nodes.

func (*Tree) AddLeaf 

func (t *Tree) AddLeaf(leaf *LeafNode) (LeafIndex, error)

AddLeaf inserts leaf at the lowest blank LeafIndex, extending the tree if necessary. The new leaf's direct path is blanked. Returns the LeafIndex where the leaf was placed.

func (*Tree) At 

func (t *Tree) At(idx NodeIndex) *Node

At returns the slot at the given node index. Out-of-range indices panic because callers should derive indices from the tree math functions, which are bounded by Width().

func (*Tree) BlankDirectPath 

func (t *Tree) BlankDirectPath(from NodeIndex) error

BlankDirectPath blanks every parent on the direct path from from to the root. Used after an Add or Remove to invalidate the affected subtree secrets (RFC 9420 section 7.3).

func (*Tree) BlankLeaf 

func (t *Tree) BlankLeaf(li LeafIndex) error

BlankLeaf blanks the leaf slot at li.

func (*Tree) BlankParent 

func (t *Tree) BlankParent(idx NodeIndex) error

BlankParent blanks the slot at idx; idx must be a parent index.

func (*Tree) Leaf 

func (t *Tree) Leaf(li LeafIndex) (*LeafNode, error)

Leaf returns the leaf at the given LeafIndex, or nil if the slot is blank. Returns an error if the leaf index is out of range.

func (*Tree) LeafCount 

func (t *Tree) LeafCount() uint32

LeafCount returns the number of leaf slots (populated or blank).

func (*Tree) Parent 

func (t *Tree) Parent(idx NodeIndex) *ParentNode

Parent returns the parent node at the given NodeIndex, or nil if blank.

func (*Tree) PopulatedLeaves 

func (t *Tree) PopulatedLeaves() []LeafIndex

PopulatedLeaves returns the leaf indices of all populated leaves in ascending order.

func (*Tree) Resolution 

func (t *Tree) Resolution(idx NodeIndex) []NodeIndex

Resolution implements RFC 9420 section 7.5. 

resolution(x) =
    [x] + unmerged_leaves(x)   if x is a non-blank parent
    [x]                        if x is a non-blank leaf
    []                         if x is a blank leaf
    resolution(left) ++ resolution(right)
                                if x is a blank parent

The returned slice lists node indices in left-to-right order.

func (*Tree) SetLeaf 

func (t *Tree) SetLeaf(li LeafIndex, leaf *LeafNode) error

SetLeaf replaces the leaf at li.

func (*Tree) SetParent 

func (t *Tree) SetParent(idx NodeIndex, p *ParentNode) error

SetParent replaces the parent at idx.

func (*Tree) Width 

func (t *Tree) Width() uint32

Width returns the current array width.

type UpdatePath 

type UpdatePath struct {
	LeafNode LeafNode
	Nodes    []UpdatePathNode
}

UpdatePath is the cryptographic side of a Commit: the committer's new LeafNode plus an UpdatePathNode for every parent on the committer's direct path. 

struct {
    LeafNode       leaf_node;
    UpdatePathNode nodes<V>;
} UpdatePath;

func (*UpdatePath) MarshalMLS 

func (u *UpdatePath) MarshalMLS(e *mlstls.Encoder) error

MarshalMLS encodes an UpdatePath.

func (*UpdatePath) UnmarshalMLS 

func (u *UpdatePath) UnmarshalMLS(d *mlstls.Decoder) error

UnmarshalMLS decodes an UpdatePath.

type UpdatePathNode 

type UpdatePathNode struct {
	EncryptionKey        crypto.HPKEPublicKey
	EncryptedPathSecrets []crypto.HPKECiphertext
}

UpdatePathNode is one entry in an UpdatePath: the new public key for a parent node on the committer's direct path, plus an HPKE ciphertext for every recipient in the resolution of that parent's copath sibling (RFC 9420 section 7.6). 

struct {
    HPKEPublicKey  encryption_key;
    HPKECiphertext encrypted_path_secret<V>;
} UpdatePathNode;

func (*UpdatePathNode) MarshalMLS 

func (n *UpdatePathNode) MarshalMLS(e *mlstls.Encoder) error

MarshalMLS encodes an UpdatePathNode.

func (*UpdatePathNode) UnmarshalMLS 

func (n *UpdatePathNode) UnmarshalMLS(d *mlstls.Decoder) error

UnmarshalMLS decodes an UpdatePathNode.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.