Nebula: add differential privacy sampling to P3A

[rillian]

Description

Per recent discussions, we want to add differential privacy to the STAR protocol used to report how features are used in the browser. The first phase of this is just to add sampling to the current reports: some percentage of the time the client submits a measurement with the value or tag of the outer layer replaced with some random value. This addresses some of the leakage from undecodable tags in STAR by adding plausible deniability to the threshold anonymity.

Proposed parameters, derived from differential privacy ε=1 and δ = 10^-8:

• sampling rate p = 0.105 (10.5% of measurements are submitted as before)
• aggregation threshold K = 20

By introducing sampling we enforce better privacy bounds even with the lower aggregation threshold (currently K=50).

Rough plan

• [x] Introduce sampling by perturbing encoded P3A values before they are sent to the randomness server
• [x] Mark nebula vs. constellation P3A submissions so they can be processed separately by the stats backend. Perhaps a Brave-Aggregation-Threshold http header can mark the difference.
• [x] Implement feature switches to control rollout. At first we want to try just two questions, maybe one with a large reporting cohort and one with a small. Then a second would enable Nebula submission for all P3A questions.

[rillian]

cc @AliShahin @DJAndries

[kjozwiak]

The above requires 1.68.101 or higher for 1.68.x verification 👍

[GeetaSarvadnya]

Verification PASSED on

Brave | 1.68.101 Chromium: 126.0.6478.126 (Official Build) beta (64-bit)
-- | --
Revision | ffa8411f4c8fe36c0e399f60ef7c24b3cf7d7402
OS | Windows 10 Version 22H2 (Build 19045.4529)

• Verified the test plan from https://github.com/brave/brave-core/pull/22522

Test Plan

Test plan verification_PASSED

- Confirmed that each collector request have the ` Brave-P3A-Constellation-Threshold` header value `20` or `50` slow | express | typical | slow | express | typical ------|---------|-------|------|------|------  |  |  |  |  |  To view all the collector metrics metrics Example | Example ----------|----------  | 

[GeetaSarvadnya]

Verification PASSED on Vivo X70 Pro version12 running Bravemonoarm64.apk_1.68.101

• Verified the test plan from https://github.com/brave/brave-core/pull/22522

Test Plan

Test plan verification_PASSED

- Confirmed that each collector request have the ` Brave-P3A-Constellation-Threshold` header value `20` or `50` slow | express | typical | slow | express | typical ------|---------|-------|------|------|------  |  |  |  |  |  To view all the collector metrics metrics Example | Example ----------|----------  | 

Regression test

• Verify requests are sent to star-randsrv.bsg.brave.com and collector.bsg.brave.com endpoints as usual

Step 1_PASSED

- Confirmed that JSON metrics are sent as usual to the endpoint http://p3a-json.brave.com/ - Confirmed that each metric is sent to the server and marked as "sent" = `true` in the local state file randomness metrics at `http://p3a-json.brave.com/`  - Confirmed that if the metric is in the `logs` object (in local state), then the cadence is `typical` and the same is displayed in p3a-json.brave.com endpoint in the server **Note**: `Typical` metrics are NOT listed under the `Logs` block on brave://local-state file, also few metrics are listed under `http://p3a-json.brave.com/` endpoint which is correct as `http://p3a-json.brave.com/` will be deprecated soon. We are good if all the metrics are shown under `logs_constellation_prep` block - Confirmed that, If the metric is in `logs_slow` then the `cadence` is slow and same is displayed in the p3a-json.brave.com endpoint in the server - Confirmed that, If the metric is in `logs_express` then the cadence is `express` and the same is displayed in p3a-json.brave.com endpoint in the server - Only 3 metrics are shown under the `logs_express` but in p3a-json endpoint, I could see only two cadence `express` metrics sent to the endpoint `p3a-json.brave.com` and one metric is sent to the endpoint `https://p3a-creative.brave.com` Example | Example | Example | `https://p3a-creative.brave.com` ----------|----------|----------|--------  |  |  |  - Only 4 metrics are shown under `logs_slow` both metrics are shown under https://p3a-json.brave.com as expected Example | Example | Example | Example | Example ----------|----------|----------|---------|---------  |  |  |  |  - Confirmed that the cadence field in the payload contains the correct value - The metrics `Brave.Shields.AdBlockSettings` response value is `1` in both local state file and `p3a-json...` endpoint

Step 2_PASSED

1. Confirmed that requests are being made to `star-randsrv.bsg.brave.com` to prepare Constellation metrics 2. Confirmed that the URL path is `/instances//randomness` 3. Confirmed that when one request is `sent` for a particular cadence, check to see that metrics are being marked as "sent" as they are being sent to the server, by checking the correct "logs" object in local state. **46 randomness** requests are sent to this endpoint `star-randsrv.bsg.brave.com` Step 1,2 | Step 1, 2(1) ----------|-------------  |  **46 typical logs** metrics are shown under `Logs` in brave://local-state Step 3 | Step 3(1) | Step 3(2) --------|-----------|----------- No `Logs` in brave://local-state 4. There are `46 metrics` listed under `Logs` as shown in the images above `Step 3`, `Step 3(1)` and `Step 3(2)` and `46 metrics` are listed under `logs_constellation_prep` shown in the images below `Step 4(1)`, `Step 4(2)` and `Step 4(3)` All the metrics under `Logs` and `logs_constellation_prep` are marked as `sent:true`, when we look at the `https://star-randsrv.bsg.brave.com` endpoint at the server, `46 typical metrics` are sent to the server in the form of `randomness` instances as shown in the images above `Step 1,2(1)` and `Step 1,2(2)` 46 metrics are shown under `logs_constellation_prep` Step 4(1) | Step 4(2) | Step 4(3) | Step 4(4) ----------|------------|----------|------------  |  |  |  5. Confirmed that no. of metrics shown under `logs_constellation_prep_express` are same as the no. of metrics shown under `logs_express` and `express` instances at the `star-randsrv.bsg.brave.com` server endpoint as expected `logs_constellation_prep_express` | `logs_express` | `express` -------------------------------------|-----------------|-------------  |  |  6. Confirmed that no. of metrics shown under `logs_constellation_prep_slow` are same as the no. of metrics shown under `logs_slow` and `slow` instances at the `star-randsrv.bsg.brave.com` server endpoint as expected `logs_constellation_prep_slow` | `logs_slow` | `slow` -------------------------------------|-----------------|-------------  |  | 

Step 3_PASSED

``` Ensure final measurements are being sent to collector.bsg.brave.com. The URL path should be /. Before metrics are sent to this server, they should appear under constellation_logs, constellation_logs_express and constellation_logs_slow after being prepared (from the requests being made in step 2). As soon as the metrics are sent to the collector, the metric should disappear in the relevant local state object. ``` 1. Confirmed that, before the metrics are sent to server they are prepared to sent and hence appear under `logs_constellation_prep_express`, `logs_constellation_prep_slow` and `logs_constellation_prep` after that the metrics are appear under `constellation_logs`, `constellation_logs_express` and `constellation_logs_slow `. But the metrics listed under `constellation_logs`, `constellation_logs_express` and `constellation_logs_slow ` are removed once the metrics are sent to the server **_metrics prepared_** Example | Example | Example | Example | Example | Example ----------|-----------|---------|-----------|-----------|----------  |  |  |  |  |  **_constellation logs_**  2. Confirmed that the final measurements are sent to the endpoint `collector.bsg.brave.com` - Two `slow` metrics are sent to the endpoint `collector.bsg.brave.com` as expected - Two `express` metrics are sent to the endpoint `collector.bsg.brave.com` instead of three - There is one `creative` cadence type metrics are sent to the endpoint `collector.bsg.brave.com` - Not sure whether this is expected or not there is no mention of this metrics in the test plan (this is expected as per the response below) - There are `46 typical` metrics are sent to the endpoint `collector.bsg.brave.com` as there are `46 typical` metrics are listed under `Logs` in brave://local-state file Example | Example | Example ---------|------------|-------