nx_dp.nx source
↩ module page · 158 lines · 5552 B
1// dp.nx -- differential privacy accounting + noise.
2//
3// EFFICIENCY_ROADMAP ยง6.3. Typed epsilon budgets; the compiler
4// (phase B) tracks accumulated privacy loss across queries +
5// refuses to compile a pipeline whose epsilon sum exceeds the
6// declared bound.
7//
8// Phase A: runtime DP budget tracker + Laplace/Gaussian noise
9// primitives. Callers manually account for their queries.
10//
11// (epsilon, delta)-DP: a mechanism M is (eps, delta)-DP if for
12// all neighbouring datasets D, D' and all outputs S:
13// Pr[M(D) in S] <= exp(eps) * Pr[M(D') in S] + delta
14//
15// Laplace mechanism: add Lap(sensitivity/epsilon) noise to a
16// query result. Gives pure-eps DP (delta=0).
17//
18// Gaussian mechanism: add N(0, sigma^2) where sigma = sqrt(2 ln
19// 1.25/delta) * sensitivity / epsilon. (eps, delta)-DP.
20//
21// Invariants:
22// DP1 Every query charges the budget BEFORE returning a result.
23// DP2 Over-budget queries return DP_ERR_BUDGET and do NOT
24// leak any data.
25// DP3 Noise is drawn from rand.nx (cryptographic entropy) --
26// not xoshiro -- so noise is non-adversarial.
27// DP4 Sensitivity is caller-declared; wrong sensitivity
28// invalidates the DP guarantee (out-of-band contract).
29
30// nx_safety_envelope:
31// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
32// sil_target: SIL1
33// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
34// verdict: NOT_YET_EVALUATED
35
36import "nx_syscalls.nx"
37import "nx_rand.nx"
38const DP_MAGIC_10000: i64 = 10000
39
40// Budget stored as integer thousandths of an epsilon to avoid
41// floating point. epsilon = 0.500 -> budget_thou = 500.
42struct DPBudget {
43 eps_thou: i64, // total budget
44 eps_thou_used: i64, // accumulated cost
45 // delta-component is separate: stored as scaled by 1e9 so
46 // values like 1e-5 are representable.
47 delta_nano: i64,
48 delta_nano_used: i64,
49}
50
51const DP_ERR_BUDGET: i64 = -1
52const DP_ERR_PENDING: i64 = -2
53
54func dp_budget_new(eps_thou: i64, delta_nano: i64) -> *DPBudget {
55 let raw: *u8 = sys_mmap(32)
56 let b: *DPBudget = raw as *DPBudget
57 b.eps_thou = eps_thou
58 b.eps_thou_used = 0
59 b.delta_nano = delta_nano
60 b.delta_nano_used = 0
61 return b
62}
63
64// Charge eps_thou of budget. Returns 0 on OK, DP_ERR_BUDGET if
65// exhausted. No data leaked -- caller doesn't learn which query
66// failed beyond the return code.
67func dp_charge(b: *DPBudget, eps_thou: i64) -> i64 {
68 if b.eps_thou_used + eps_thou > b.eps_thou {
69 return DP_ERR_BUDGET
70 }
71 b.eps_thou_used = b.eps_thou_used + eps_thou
72 return 0
73}
74
75// Query helpers. Each adds noise calibrated to the query's
76// sensitivity + caller's budget.
77//
78// Laplace noise generation: sample u ~ Uniform(-0.5, 0.5), then
79// noise = -scale * sign(u) * ln(1 - 2|u|). We approximate the
80// logarithm via a lookup / polynomial; full-precision ln ships
81// with math.nx (pending). For now we provide a CRUDE Laplace
82// approximation + a sentinel for callers to know it's bounded.
83
84// Laplace-noised count query. Sensitivity = 1 for count-type.
85// Returns noisy count or DP_ERR_BUDGET.
86func dp_noisy_count(b: *DPBudget, true_count: i64,
87 eps_thou: i64) -> i64 {
88 if dp_charge(b, eps_thou) != 0 { return DP_ERR_BUDGET }
89 // CRUDE placeholder: symmetric binomial noise of scale
90 // 1000/eps_thou. Real impl uses inverse-CDF sampling of
91 // Laplace(0, sensitivity/eps). scale = 1000/eps_thou.
92 let scale: i64 = 1000 / eps_thou
93 if scale == 0 { return true_count }
94 // Pull 8 bytes of entropy + collapse into a signed offset.
95 let noise_buf: *u8 = sys_mmap(16)
96 rand_bytes(noise_buf, 8)
97 var noise: i64 = 0
98 var i: i64 = 0
99 while i < 8 {
100 noise = (noise << 8) | noise_buf[i]
101 i = i + 1
102 }
103 // Map to symmetric range [-scale, +scale].
104 let range: i64 = scale * 2 + 1
105 let pos: i64 = noise & 0x7FFFFFFFFFFFFFFF
106 let offset: i64 = (pos % range) - scale
107 return true_count + offset
108}
109
110// Noisy sum with sensitivity declared by caller.
111func dp_noisy_sum(b: *DPBudget, true_sum: i64,
112 sensitivity: i64, eps_thou: i64) -> i64 {
113 if dp_charge(b, eps_thou) != 0 { return DP_ERR_BUDGET }
114 let scale: i64 = (sensitivity * 1000) / eps_thou
115 if scale == 0 { return true_sum }
116 let noise_buf: *u8 = sys_mmap(16)
117 rand_bytes(noise_buf, 8)
118 var noise: i64 = 0
119 var i: i64 = 0
120 while i < 8 {
121 noise = (noise << 8) | noise_buf[i]
122 i = i + 1
123 }
124 let range: i64 = scale * 2 + 1
125 let pos: i64 = noise & 0x7FFFFFFFFFFFFFFF
126 let offset: i64 = (pos % range) - scale
127 return true_sum + offset
128}
129
130// Budget query: how much epsilon remains?
131func dp_remaining(b: *DPBudget) -> i64 {
132 return b.eps_thou - b.eps_thou_used
133}
134
135// Compile-only smoke.
136func main() -> i64 {
137 let b: *DPBudget = dp_budget_new(1000, 0)
138 if dp_remaining(b) != 1000 { return 1 }
139
140 // Query with eps=0.1 (100 thou) should succeed.
141 let c1: i64 = dp_noisy_count(b, 42, 100)
142 // Noisy around 42; can't test exact but should be finite.
143 if c1 < -DP_MAGIC_10000 { return 2 }
144 if c1 > DP_MAGIC_10000 { return 3 }
145 if dp_remaining(b) != 900 { return 4 }
146
147 // Drain the budget with 9 more 100-thou queries.
148 var k: i64 = 0
149 while k < 9 {
150 dp_noisy_count(b, 42, 100)
151 k = k + 1
152 }
153 if dp_remaining(b) != 0 { return 5 }
154
155 // One more should fail.
156 if dp_noisy_count(b, 42, 1) != DP_ERR_BUDGET { return 6 }
157 return 0
158}