From 62820c22c53b412fa6965c35795e33e5caa39e3c Mon Sep 17 00:00:00 2001
From: Nick Mathewson <nickm@torproject.org>
Date: Tue, 11 Feb 2025 09:04:53 -0500
Subject: [PATCH] nodelist: Additionally use family IDs to decide family
 membership.

This implements the client side of happy families.
---
 changes/happy-families-client   |  4 +++
 src/feature/nodelist/nodelist.c | 57 +++++++++++++++++++++++++++++++--
 2 files changed, 58 insertions(+), 3 deletions(-)
 create mode 100644 changes/happy-families-client

diff --git a/changes/happy-families-client b/changes/happy-families-client
new file mode 100644
index 0000000000..aeeb666203
--- /dev/null
+++ b/changes/happy-families-client
@@ -0,0 +1,4 @@
+  o Major features (client):
+    - Clients now respect "happy families" per proposal 321.
+      This feature will eventually allow a much more compact representation
+      for relay families, for a significant savings in directory download size.
diff --git a/src/feature/nodelist/nodelist.c b/src/feature/nodelist/nodelist.c
index 8f0f46d132..889140b408 100644
--- a/src/feature/nodelist/nodelist.c
+++ b/src/feature/nodelist/nodelist.c
@@ -2171,6 +2171,38 @@ node_has_declared_family_list(const node_t *node)
   return false;
 }
 
+/**
+ * Return the listed family IDs of `a`, if it has any.
+ */
+static const smartlist_t *
+node_get_family_ids(const node_t *node)
+{
+  if (node->ri && node->ri->family_ids) {
+    return node->ri->family_ids;
+  } else if (node->md && node->md->family_ids) {
+    return node->md->family_ids;
+  } else {
+    return NULL;
+  }
+}
+
+/**
+ * Return true iff `a` and `b` have any family ID in common.
+ **/
+static bool
+nodes_have_common_family_id(const node_t *a, const node_t *b)
+{
+  const smartlist_t *ids_a = node_get_family_ids(a);
+  const smartlist_t *ids_b = node_get_family_ids(b);
+  if (ids_a == NULL || ids_b == NULL)
+    return false;
+  SMARTLIST_FOREACH(ids_a, const char *, id, {
+      if (smartlist_contains_string(ids_b, id))
+        return true;
+    });
+  return false;
+}
+
 /**
  * Add to <b>out</b> every node_t that is listed by <b>node</b> as being in
  * its family.  (Note that these nodes are not in node's family unless they
@@ -2217,12 +2249,20 @@ nodes_in_same_family(const node_t *node1, const node_t *node2)
       return 1;
   }
 
-  /* Are they in the same family because the agree they are? */
-  if (node_family_list_contains(node1, node2) &&
+  /* Are they in the same family because they agree they are? */
+  if (use_family_lists &&
+      node_family_list_contains(node1, node2) &&
       node_family_list_contains(node2, node1)) {
     return 1;
   }
 
+  /* Are they in the same family because they have a common
+   * verified family ID? */
+  if (use_family_ids &&
+      nodes_have_common_family_id(node1, node2)) {
+    return 1;
+  }
+
   /* Are they in the same family because the user says they are? */
   if (options->NodeFamilySets) {
     SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
@@ -2279,7 +2319,8 @@ nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
 
   /* Now, add all nodes in the declared family of this node, if they
    * also declare this node to be in their family. */
-  if (node_has_declared_family_list(node)) {
+  if (use_family_lists &&
+      node_has_declared_family_list(node)) {
     smartlist_t *declared_family = smartlist_new();
     node_lookup_declared_family_list(declared_family, node);
 
@@ -2293,6 +2334,16 @@ nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
     smartlist_free(declared_family);
   }
 
+  /* Now add all the nodes that share a verified family ID with this node. */
+  if (use_family_ids &&
+      node_get_family_ids(node)) {
+    SMARTLIST_FOREACH(all_nodes, const node_t *, node2, {
+        if (nodes_have_common_family_id(node, node2)) {
+          smartlist_add(sl, (void *)node2);
+        }
+      });
+  }
+
   /* If the user declared any families locally, honor those too. */
   if (options->NodeFamilySets) {
     SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
-- 
2.47.3