recursive.go raw

   1  package gnarlring
   2  
   3  import "io"
   4  
   5  // TreeNode holds the key material and state for one tree node.
   6  // Leaf nodes hold only NTRU keypairs. Internal nodes hold NTRU keypairs
   7  // and manage child epochs.
   8  type TreeNode struct {
   9  	PK *NTRUPublicKey
  10  	SK *NTRUPrivateKey
  11  
  12  	// Children is a set of child commitments (from lower tree levels).
  13  	// For leaf nodes, Children is nil.
  14  	Children *AggregatedCommitment
  15  
  16  	// Epoch counter for this node's group state.
  17  	Epoch uint64
  18  }
  19  
  20  // NewLeafNode creates a leaf tree node.
  21  func NewLeafNode() *TreeNode {
  22  	pk, sk := NTRUKeyGen()
  23  	return &TreeNode{PK: pk, SK: sk}
  24  }
  25  
  26  // NewInternalNode creates an internal tree node that coordinates children.
  27  func NewInternalNode() *TreeNode {
  28  	pk, sk := NTRUKeyGen()
  29  	return &TreeNode{
  30  		PK:       pk,
  31  		SK:       sk,
  32  		Children: NewAggregatedCommitment(),
  33  	}
  34  }
  35  
  36  // AddChild inserts a child commitment into this node.
  37  func (n *TreeNode) AddChild(index int, childPK *NTRUPublicKey, rng io.Reader) bool {
  38  	if n.Children == nil {
  39  		return false
  40  	}
  41  	w := NewChildCommitment(index, childPK, rng)
  42  	return n.Children.Add(w)
  43  }
  44  
  45  // SignChildCommitments produces an NTRU signature binding all child
  46  // commitments under this node's public key. Returns the epoch signature.
  47  // The node acts as a coordinator for its children.
  48  func (n *TreeNode) SignChildCommitments(msg []byte) *NTRUSignature {
  49  	if n.Children == nil || !n.Children.IsComplete() {
  50  		return nil
  51  	}
  52  	target := n.Children.Target(msg, n.Epoch)
  53  	return NTRUSignTarget(n.SK, target, nil)
  54  }
  55  
  56  // VerifyChildCommitments verifies the coordinator's signature on child
  57  // commitments under this node's public key.
  58  func (n *TreeNode) VerifyChildCommitments(msg []byte, sig *NTRUSignature) bool {
  59  	if n.Children == nil || !n.Children.IsComplete() {
  60  		return false
  61  	}
  62  	target := n.Children.Target(msg, n.Epoch)
  63  	return NTRUVerifyTarget(n.PK, target, sig)
  64  }
  65  
  66  // RecursiveTree is a multi-level tree of NTRU keypairs.
  67  // Level 0: root coordinator. Level 1..h: sub-coordinators. Level h+1: leaves.
  68  type RecursiveTree struct {
  69  	Root *TreeNode
  70  	Levels [][]*TreeNode // Levels[0] = [root], Levels[1] = [27 coordinators], ...
  71  }
  72  
  73  // BuildRecursiveTree creates a tree of depth h with full branching factor N.
  74  // depth=1: root + 27 leaves (total 28 nodes)
  75  // depth=2: root + 27 coordinators + 27*27 = 729 leaves
  76  func BuildRecursiveTree(depth int) *RecursiveTree {
  77  	if depth < 1 {
  78  		return nil
  79  	}
  80  	tree := &RecursiveTree{
  81  		Levels: make([][]*TreeNode, depth+1),
  82  	}
  83  
  84  	// Level 0: root.
  85  	root := NewInternalNode()
  86  	tree.Root = root
  87  	tree.Levels[0] = []*TreeNode{root}
  88  
  89  	// Build each level.
  90  	parents := []*TreeNode{root}
  91  	for d := 1; d <= depth; d++ {
  92  		numNodes := powN(d)
  93  		nodes := make([]*TreeNode, numNodes)
  94  		for i := 0; i < numNodes; i++ {
  95  			if d == depth {
  96  				// Leaf level.
  97  				nodes[i] = NewLeafNode()
  98  			} else {
  99  				nodes[i] = NewInternalNode()
 100  			}
 101  		}
 102  		tree.Levels[d] = nodes
 103  
 104  		// Wire children: each parent at level d-1 gets N children from level d.
 105  		if d > 0 {
 106  			childIdx := 0
 107  			for _, parent := range parents {
 108  				for j := 0; j < N && childIdx < len(nodes); j++ {
 109  					parent.AddChild(j, nodes[childIdx].PK, nil)
 110  					childIdx++
 111  				}
 112  			}
 113  		}
 114  
 115  		parents = nodes
 116  	}
 117  
 118  	return tree
 119  }
 120  
 121  // SignRoot signs the root epoch with all transitive child commitments.
 122  // Each internal node signs its children's commitments; the root signs
 123  // its children (level-1 coordinators' commitments).
 124  func (t *RecursiveTree) SignRoot(msg []byte) *NTRUSignature {
 125  	// Sign bottom-up: each level signs for its children.
 126  	for d := len(t.Levels) - 2; d >= 0; d-- {
 127  		for _, node := range t.Levels[d] {
 128  			if node.Children == nil {
 129  				continue
 130  			}
 131  			// Sign this node's children.
 132  			node.SignChildCommitments(msg)
 133  		}
 134  	}
 135  	return t.Root.SignChildCommitments(msg)
 136  }
 137  
 138  // VerifyRoot verifies the root signature recursively down the tree.
 139  func (t *RecursiveTree) VerifyRoot(msg []byte, rootSig *NTRUSignature) bool {
 140  	return t.Root.VerifyChildCommitments(msg, rootSig)
 141  }
 142  
 143  func powN(exp int) int {
 144  	r := 1
 145  	for i := 0; i < exp; i++ {
 146  		r *= N
 147  	}
 148  	return r
 149  }
 150