Epoch cadences

[bmcase]

In the Attribution spec (without safety limits considered) each site's epoch will start independently of other sites (starting for example on the first time the API is called by this site). This has the benefit that it avoids a situation where all per-site budgets are on the same cadence such that at the end of the epoch all users are out of budget at the same time. The Big Bird algorithm assumes that per-site epochs start/end on the same cadence as the epoch for the global budget and for quotas.

The following table captures several options for epoch cadences. Likely option 2 offers the best tradeoffs.

[martinthomson]

(This is not very accessible, by the way. For instance, copy+paste. You can maybe format your thing as a table instead. Use emojis to summaries +/-/? status.)

My concern with option 2 is that we've not spent a whole lot of effort protecting the epoch boundaries from sites learning where the cut point is. If we go that way, this is a piece of hard-core device-specific identifier that sites might learn through using the API (even if they only learn a little bit at a time) which is effectively a supercookie. If we took that path, we'd have to protect that information a lot more actively than we do in the current API.

I think that a version of option 3 is best. Global budgets and quotas can use a fixed cycle. Sites get their own cycle. We lose coherency about budget spent in some minor ways, mostly the single-epoch optimization might not apply, but I think that's acceptable for global budgets and quotas, which shouldn't need to be so finely accounted for.

[bmcase]

yes, that is true about option 2. But we never give a way to query this directly; they would have to try to learn about it through the DP queries. If this is a long-lived value on the device, it would be concerning that they could try to learn it. I added an Option 4 which kind of addresses that but with some worse performance tradeoffs.

Yeah, maybe option 3 is best; we keep the per-site budgets as they would ideally be which are the main privacy lever, so maybe we can relax some constraints on how we think about the quotas.

Here is an updated table in markdown

Options for epoch cadences	Practical performance considerations	Privacy properties
Option 0: Each per-site budget starts independently when that site first uses the API. No safety limits.		(+) Supported by cookie monster (-) But lacks safety limits.
Option 1: All per-site epochs and global and quota epochs on all devices are on the same cadence public cadence	(-) Problem of all devices nearing out-of budget at the same time	(+) supported by big bird theory (+) no cross-site device-specific value
Option 2 [Recommend]: For each device, there is an epoch cadence that all per-site, global and quotas use. Each device chooses a random start time for their first epoch cadence.	(+) Avoides the problem of all devices nearing out-of budget at the same time	(+) supported by big bird theory (-) is a fixed on-device value for all sites they could try to learn.
Option 3: Each per-site budget starts independently when that site first uses the API. Global budget and quotas on the same cadence across all devices but per-site budgets	(+) per-site budget privacy budgets remain the same as Option 0 (preferred).	(-) no algorithm for how to spend atomically (+) no cross-site device-specific value
Option 4: Like Option 2 but each epoch is a random length (selected randomly from some range; scale budget proportionally).	(-) would mean there is no known minimum available budget when calling the API. Makes budget management very complex.	(+) random epoch length avoids a long-lived fixed on-device value

[martinthomson]

For leakage, I'm more worried about timing and other side channels. Our implementations will be imperfect, by virtue of the nature of the API, if nothing else. Having to harden them for this makes it a lot harder.

[michaelkleber]

I think the previous discussion about this topic was in #17, but that predates the Big Bird work.

Can someone spell out why there's a need for "Global budget and quotas on the same cadence across all devices" (edit: for Option 3)? I think it would be weird for every browser in the world to reset its global budget on Wednesday at noon GMT, because it would mean that Tuesday conversion numbers and Thursday conversion numbers would be differently impacted by budget exhaustion. But if we're not assuming global and per-site epochs align, then can the global epoch time be a uniformly random per-device choice too?

[bmcase]

@michaelkleber ,

Can someone spell out why there's a need for "Global budget and quotas on the same cadence across all devices" (edit: for Option 3)?

@martinthomson has raised the concern that if each device as its own unique global budget epoch cadence, then that is a unique device-specific value which sites could try to extract via side channels and timing attacks to use as a supercookie.

I agree having the global role over on all devices at the same time would be weird if it is observable, but I think the hope is that the global and quotas are configured loosely enough that this isn't very noticeable. In contrast if we were having the per-site privacy budgets all role over at the same time each week that would be very noticeable.

[michaelkleber]

@martinthomson has raised the concern that if each device as its own unique global budget epoch cadence, then that is a unique device-specific value which sites could try to extract via side channels and timing attacks to use as a supercookie.

Ah thanks, I get it now.

Could we address both of these concerns by having each device's global epoch time chosen uniformly at random but then rounded to an hour boundary? Then with 1-week epochs there would only be 168 device classes. Or make it a 6-hour boundary (in either the device's local time zone or GMT, don't think it matters which) and then there are 24 28 device classes.

[bmcase]

yeah, that would make it worst case a weak key not like a cookie. What do you think @martinthomson would that be enough to mitigate the risk or you think we need to avoid adding even a weak key like this?

[martinthomson]

I think I'd need a stronger reason to do that than the Tuesday/Wednesday/Thursday thing @michaelkleber raises.

Our expectation is that quotas and global budgets are effectively never hit when people use the web normally and sites are generally well-behaved. The quotas further ensure that it takes sustained bad behavior from multiple sites to hit limits. So I don't think we should be concerned about skew resulting from how those epochs are aligned.

I'd rather not have to think about defending any fingerprinting entropy, if possible. But I agree that we can adjust it.

[michaelkleber]

Our expectation is that quotas and global budgets are effectively never hit when people use the web normally and sites are generally well-behaved.

Sure, but we're talking about a global quota — so if there is one sufficiently-misbehaving party, then everyone's data gets weird Tuesday != Thursday effects.

If we don't require alignment, then does Big Bird even require that the global epoch is the same length as the per-site ones? Can we have one-day global and one-week per-site epochs?

[bmcase]

If we don't require alignment, then does Big Bird even require that the global epoch is the same length as the per-site ones? Can we have one-day global and one-week per-site epochs?

Big Bird assumes all epochs -- per-site, global, quotas -- are all on the same cadence and same length. So to support Option 3 above or what you suggested @michaelkleber (coarsening the available start time to hourly or every 6 hrs) we would be going outside of the current theoretical understanding.

I think that's okay to go outside the theory for the safety limits (we should call it out though). It will still be the case that the per-site budgeting with Cookie Monster theory would be intact for the primary privacy guarantee of the per-site budgets.

[martinthomson]

Despite challenges in matching theory to this, it's an interesting idea. It has the benefit of isolating spikes.

And it's no worse than trying to match the uneven cycling of per-site budgets to a fixed cycle of the global budget.

The main reason against it from my perspective is a general preference to have a longer refresh period for budgets because it allowed for a better privacy/utility balance. Spikes can be spread out better if you have a longer cycle, despite a lower privacy budget release per unit of time. Shorter budget intervals have the benefit of isolating spikes. Switching to a daily budget probably can't be as simple as taking a limit and dividing by seven. The spikes are real, so you might only be able to divide by three.

As far as our exposure to misbehaving sites, I continue to maintain that hitting the global budget is something to be avoided. That makes the cyclical anomaly you are concerned about less worrying to me. Is there any way we can understand that risk better?

[michaelkleber]

I feel like your "general preference to have a longer refresh period" is quite right for the per-site limit. But for the global limit that's an anti-abuse measure, I think a sharp spike is a very plausible abuse vector. So maybe the shorter global epoch is actually a better fallback mechanism in some ways? I don't see much downside to it honestly.

And yes, I agree that it's hard to predict how the global-budget-depletion risk will play out in practice. Maybe you're right and I'm overly pessimistic and we won't actually need to worry about the API's behavior for some parties in the regime where other parties are attacking it.