@powforge/identity - npm Package Compare versions

Comparing version 0.5.2 to 0.6.0

CHANGELOG.md

 # Changelog
 
+## 0.6.0
+
+### Added
+- `detectIndirectCycle(events, subjectPubkey, voucherPubkey, maxDepth = 4)` exported helper. Returns true when the vouch graph contains a path from subject to voucher of length >= 2 and <= maxDepth. Catches 3-cycles, 4-cycles, and 5-cycles at default settings; 6-cycles and larger require raising `maxDepth`.
+- `scoreVouch` now composes both detectors. Inbound vouches that form either a direct 2-cycle or an indirect 3+-cycle with the subject are dropped from scoring. The existing `cycleDropped` counter covers both.
+
+### Algorithm
+- Bounded DFS from the subject, depth-capped by `maxDepth`. Worst-case node expansion is O(out_degree ^ maxDepth); at default out-degree <= 5 and maxDepth = 4 this is well under 1 ms per lookup.
+- Return-check precedes the depth-bound gate so a voucher sitting exactly at `depth == maxDepth` is still caught.
+- Guarded against malformed input: non-array `events`, missing pubkeys, and `subject == voucher` short-circuit to `false` without walking.
+
+### Tests
+- 60 tests passing (10 new, 50 existing). 10 new tests cover the 3/4/5-cycle positive cases, a 6-cycle beyond default depth (intentional miss), a 6-cycle with explicit `maxDepth = 5` (catch), no-path reachability, disjoint ring that does not involve subject, direct 2-cycle being correctly out-of-scope (handled by `detectDirectCycle`), self-lookup short-circuit, and empty/malformed input guards.
+
+### Design notes
+- Chose bounded DFS over full Tarjan SCC because we only care about cycles that involve the subject, not about all strongly-connected components in the vouch graph. Cleaner test surface and identical asymptotic cost for the realistic sockpuppet-ring sizes (3-5 keys) the threat model contemplates.
+- Design: `research/vouch-cycle-indirect-design-apr21.md`
+
 ## 0.5.1
@@ -4,0 +22,0 @@

package.json

 {
   "name": "@powforge/identity",
-  "version": "0.5.2",
+  "version": "0.6.0",
   "description": "Depth-of-Identity SDK for Nostr. Measures accumulated irreversible work across five dimensions. Try it live at powforge.dev/explorer.",
@@ -18,3 +18,3 @@ "keywords": [
   "scripts": {
-    "test": "node --test tests/smoke.test.js tests/publish.test.js tests/temporal.test.js tests/zap-bolt11-dedup.test.js tests/zap-receipt-verify.test.js tests/vouch-cycle.test.js"
+    "test": "node --test tests/smoke.test.js tests/publish.test.js tests/temporal.test.js tests/zap-bolt11-dedup.test.js tests/zap-receipt-verify.test.js tests/vouch-cycle.test.js tests/indirect-vouch-cycle.test.js"
   },
@@ -21,0 +21,0 @@ "license": "MIT",

src/index.js

@@ -289,2 +289,67 @@ /**
 /**
+ * Detect an indirect vouch cycle of length ≥ 3 involving both subject and
+ * voucher.
+ *
+ * Catches `subject → X → voucher` (3-cycle), `subject → X → Y → voucher`
+ * (4-cycle), and longer up to maxDepth. Intended to compose with
+ * detectDirectCycle: run direct first, fall through to indirect if direct
+ * returns false. Direct 2-cycles are not this function's concern.
+ *
+ * Algorithm: DFS from subject along vouch edges, depth-bounded. Voucher
+ * is reported as cyclic if reachable at depth 2..maxDepth. Depth 1
+ * (direct hop) is excluded so the direct-cycle case doesn't double-count
+ * here.
+ *
+ * Design spec: research/vouch-cycle-indirect-design-apr21.md
+ *
+ * @param {Array} events - All kind:33335 vouch events in scope
+ * @param {string} subjectPubkey - The pubkey being scored
+ * @param {string} voucherPubkey - The voucher's pubkey (inbound edge)
+ * @param {number} [maxDepth=4] - DFS depth cap; 4 catches 5-cycles
+ * @returns {boolean} true when an indirect path subject → ... → voucher
+ *   of length 2..maxDepth exists
+ *
+ * Implementation notes: bounded DFS without revisit-pruning. With
+ * maxDepth=4 and typical vouch out-degrees of 1-5, the worst-case
+ * node expansion count is <= 625, well under 1ms in practice. The
+ * return-check happens before the depth-bound gate so a voucher
+ * sitting exactly at `depth === maxDepth` is still caught.
+ */
+function detectIndirectCycle(events, subjectPubkey, voucherPubkey, maxDepth = 4) {
+  if (!subjectPubkey || !voucherPubkey) return false;
+  if (subjectPubkey === voucherPubkey) return false;
+  if (!Array.isArray(events) || events.length === 0) return false;
+
+  // Build adjacency: each kind:33335 event is a vouch edge from
+  // e.pubkey (author) to each p-tag target.
+  const adj = new Map();
+  for (const e of events) {
+    if (!e || e.kind !== 33335 || !e.pubkey || !Array.isArray(e.tags)) continue;
+    let out = adj.get(e.pubkey);
+    if (!out) { out = new Set(); adj.set(e.pubkey, out); }
+    for (const t of e.tags) {
+      if (Array.isArray(t) && t[0] === 'p' && typeof t[1] === 'string' && t[1]) {
+        out.add(t[1]);
+      }
+    }
+  }
+
+  // DFS from subject. A valid indirect path must reach voucher at
+  // depth >= 2 (length-2 catches 3-cycles, length-3 catches 4-cycles,
+  // etc.). No revisit-pruning because the depth bound already caps work.
+  const stack = [[subjectPubkey, 0]];
+  while (stack.length > 0) {
+    const [node, depth] = stack.pop();
+    if (depth >= 2 && node === voucherPubkey) return true;
+    if (depth >= maxDepth) continue;
+    const neighbors = adj.get(node);
+    if (!neighbors) continue;
+    for (const next of neighbors) {
+      stack.push([next, depth + 1]);
+    }
+  }
+  return false;
+}
+
+/**
  * Compute vouch dimension (kind=33335 vouch events referencing this pubkey)
@@ -324,4 +389,8 @@ * Uses sqrt dilution: weight = voucher_depth / sqrt(voucher_total_vouches)
   for (const v of vouches) {
-    // Cycle check: did the subject vouch this voucher back?
-    if (detectDirectCycle(subjectOutboundVouches, targetPubkey, v.pubkey)) {
+    // Cycle check: did the subject vouch this voucher back? (direct 2-cycle)
+    // Or can we reach this voucher via an indirect path (3+ cycles)?
+    if (
+      detectDirectCycle(subjectOutboundVouches, targetPubkey, v.pubkey) ||
+      detectIndirectCycle(events, targetPubkey, v.pubkey)
+    ) {
       cycleDropped++;
@@ -696,2 +765,2 @@ continue;
 
-module.exports = { getIdentityDepth, queryRelay, scoreSpatial, scoreSocial, scoreAccess, scoreVouch, scoreEconomic, verifyEventFull, withinTemporalBounds, verifyZapReceipt, detectDirectCycle };
+module.exports = { getIdentityDepth, queryRelay, scoreSpatial, scoreSocial, scoreAccess, scoreVouch, scoreEconomic, verifyEventFull, withinTemporalBounds, verifyZapReceipt, detectDirectCycle, detectIndirectCycle };

No alert changes

Improved metrics

Total package byte prevSize

45289

11.64%

Lines of code

810

8.87%

No dependency changes