dp.nx source
↩ module page · 151 lines · 5394 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
30import "syscalls.nx"
31import "rand.nx"
32
33// Budget stored as integer thousandths of an epsilon to avoid
34// floating point. epsilon = 0.500 -> budget_thou = 500.
35struct DPBudget {
36 eps_thou: i64, // total budget
37 eps_thou_used: i64, // accumulated cost
38 // delta-component is separate: stored as scaled by 1e9 so
39 // values like 1e-5 are representable.
40 delta_nano: i64,
41 delta_nano_used: i64,
42}
43
44const DP_ERR_BUDGET: i64 = -1
45const DP_ERR_PENDING: i64 = -2
46
47func dp_budget_new(eps_thou: i64, delta_nano: i64) -> *DPBudget {
48 let raw: *u8 = sys_mmap(32)
49 let b: *DPBudget = raw as *DPBudget
50 b.eps_thou = eps_thou
51 b.eps_thou_used = 0
52 b.delta_nano = delta_nano
53 b.delta_nano_used = 0
54 return b
55}
56
57// Charge eps_thou of budget. Returns 0 on OK, DP_ERR_BUDGET if
58// exhausted. No data leaked -- caller doesn't learn which query
59// failed beyond the return code.
60func dp_charge(b: *DPBudget, eps_thou: i64) -> i64 {
61 if b.eps_thou_used + eps_thou > b.eps_thou {
62 return DP_ERR_BUDGET
63 }
64 b.eps_thou_used = b.eps_thou_used + eps_thou
65 return 0
66}
67
68// Query helpers. Each adds noise calibrated to the query's
69// sensitivity + caller's budget.
70//
71// Laplace noise generation: sample u ~ Uniform(-0.5, 0.5), then
72// noise = -scale * sign(u) * ln(1 - 2|u|). We approximate the
73// logarithm via a lookup / polynomial; full-precision ln ships
74// with math.nx (pending). For now we provide a CRUDE Laplace
75// approximation + a sentinel for callers to know it's bounded.
76
77// Laplace-noised count query. Sensitivity = 1 for count-type.
78// Returns noisy count or DP_ERR_BUDGET.
79func dp_noisy_count(b: *DPBudget, true_count: i64,
80 eps_thou: i64) -> i64 {
81 if dp_charge(b, eps_thou) != 0 { return DP_ERR_BUDGET }
82 // CRUDE placeholder: symmetric binomial noise of scale
83 // 1000/eps_thou. Real impl uses inverse-CDF sampling of
84 // Laplace(0, sensitivity/eps). scale = 1000/eps_thou.
85 let scale: i64 = 1000 / eps_thou
86 if scale == 0 { return true_count }
87 // Pull 8 bytes of entropy + collapse into a signed offset.
88 let noise_buf: *u8 = sys_mmap(16)
89 rand_bytes(noise_buf, 8)
90 var noise: i64 = 0
91 var i: i64 = 0
92 while i < 8 {
93 noise = (noise << 8) | noise_buf[i]
94 i = i + 1
95 }
96 // Map to symmetric range [-scale, +scale].
97 let range: i64 = scale * 2 + 1
98 let pos: i64 = noise & 0x7FFFFFFFFFFFFFFF
99 let offset: i64 = (pos % range) - scale
100 return true_count + offset
101}
102
103// Noisy sum with sensitivity declared by caller.
104func dp_noisy_sum(b: *DPBudget, true_sum: i64,
105 sensitivity: i64, eps_thou: i64) -> i64 {
106 if dp_charge(b, eps_thou) != 0 { return DP_ERR_BUDGET }
107 let scale: i64 = (sensitivity * 1000) / eps_thou
108 if scale == 0 { return true_sum }
109 let noise_buf: *u8 = sys_mmap(16)
110 rand_bytes(noise_buf, 8)
111 var noise: i64 = 0
112 var i: i64 = 0
113 while i < 8 {
114 noise = (noise << 8) | noise_buf[i]
115 i = i + 1
116 }
117 let range: i64 = scale * 2 + 1
118 let pos: i64 = noise & 0x7FFFFFFFFFFFFFFF
119 let offset: i64 = (pos % range) - scale
120 return true_sum + offset
121}
122
123// Budget query: how much epsilon remains?
124func dp_remaining(b: *DPBudget) -> i64 {
125 return b.eps_thou - b.eps_thou_used
126}
127
128// Compile-only smoke.
129func main() -> i64 {
130 let b: *DPBudget = dp_budget_new(1000, 0)
131 if dp_remaining(b) != 1000 { return 1 }
132
133 // Query with eps=0.1 (100 thou) should succeed.
134 let c1: i64 = dp_noisy_count(b, 42, 100)
135 // Noisy around 42; can't test exact but should be finite.
136 if c1 < -10000 { return 2 }
137 if c1 > 10000 { return 3 }
138 if dp_remaining(b) != 900 { return 4 }
139
140 // Drain the budget with 9 more 100-thou queries.
141 var k: i64 = 0
142 while k < 9 {
143 dp_noisy_count(b, 42, 100)
144 k = k + 1
145 }
146 if dp_remaining(b) != 0 { return 5 }
147
148 // One more should fail.
149 if dp_noisy_count(b, 42, 1) != DP_ERR_BUDGET { return 6 }
150 return 0
151}