FLEDGE - shuttling data from generate_bid to report_win

[mbowiewilson]

In FLEDGE, as I understand, there is not a mechanism for shuttling data computed in generate_bid to report_win, but we think this functionality would be extremely useful for buyers. This is because, a buyer may have computed interesting and useful intermediate results as a byproduct of computing the bid price. As a concrete example, a buyer may have computed the predicted probability of a click or conversion on their way to determining the bid price. Furthermore, the ability to log data from generate_bid in report_win would unlock a lot of useful monitoring of the bidding workflow.

Some benefits of having intermediate data from generate_bid logged in report_win would be:

• Spend pacing improvements -- Spend pacing doesn't only mean trying to hit a budget in a time frame. It can also mean trying to achieve a particular performance goal, without necessarily spending the entire budget. Having access to a quantity such as the predicted probability of a conversion allows buyers to very quickly get a sense of the performance their ad buying is driving, without waiting for the actual conversion events to take place. This is a win because conversion events are often very sparse, noisy and delayed from the time of impression.
• Monitoring prediction accuracy -- Logging predictions as they were in generate_bid allows buyers to compare the accuracy of the prediction used in bidding with the actual outcomes they observe. This would be a key sanity check of any machine learning pipeline that fed generate_bid.
• Monitoring inputs to generate_bid -- Logging certain portions of the input to generate_bid, such as the value of the trusted_bidding_signals, would allow buyers to sanity check, validate, and debug their bidding pipelines.

In terms of implementation, I was imagining the object returned from generate_bid having a field I'll call bidding_values_to_log in which a buyer could put some information they wanted to log, and that this new field would be passed to the report_win function.

[jeffkaufman]

We agree this would be a useful feature. Here's another use case: when a buyer (DSP) participates in an auction they're typically bidding on a CPM basis: how much would they pay for this impression? They will often be charging their advertisers, however, in a way that better matches advertiser goals. Most commonly this is charging per click (CPC), though buyers also offer products billed per active view (CPMAV) or conversion (CPA). Additionally, buyers often allow advertisers to specify a maximum amount they are willing to pay, but the buyer still attempts to spend as little as possible, passing along the savings. This makes the advertiser experience much better, but requires extra information in billing.

Imagine an advertiser is willing to spend up to $1 for a click (MaxCPC), and the buyer predicts a 3% chance of clicking (pCTR). The buyer would be willing to bid up to $0.03 ($30 CPM) but instead predicts it can win with a bid of $0.02 ($20 CPM). It does, and it wins the auction. If the user doesn't click, the advertiser is charged nothing: the buyer is taking the risk that it calculated pCTR incorrectly. If they do click, the advertiser is charged bid / pCTR ($0.02 / 3% = $0.67). This means the buyer needs to know pCTR for billing and budget enforcement.

In FLEDGE, the buyer will calculate pCTR in generate_bid. This poses a problem: a generic pipe from generate_bid to report_win would break the k-anonymity requirements, but how else can the buyer bill correctly? The same situation applies for active views to support CPMAV, and conversions to support CPA.

Stepping back, the trusted_bidding_signals call fills two roles with different privacy implications, allowing bidding decisions based on:

1. Very general real-time information. An advertiser might want to know what their current budget is.

2. Potentially quite specific information about users. An advertiser could use the exact time a user put a product in their cart as a bidding signal.

Because of the privacy implications of (2), the responses to the trusted_bidding_signals call are for generate_bid alone, and are not available in report_win.

In many cases, buyers may be willing to restrict themselves to making decisions only on the combination of (a) contextual information and (b) the interest group name or rendering_url. For example, while a buyer might be able to produce a slightly better pCTR estimate by considering additional information, a pCTR derived from just (a) and (b) might still be very accurate. In theory they could reproduce any such calculations on the server from existing event-level reporting and their knowledge about what was in the trusted server's database at the time, but this is error-prone, makes dispute resolution difficult, and puts difficult consistency requirements on the trusted server.

Instead, we could allow derived bidder information to feed into report_win if it depends only on information that is already available in report_win. Since the interest group name is available in reporting (modulo k-anonymity requirements discussed at [1]), when the interest group name or rendering_url is supplied to the trusted server, we propose the corresponding subset of the response be available to reporting. Any signals that the advertiser is able to derive only from the interest group name or rendering_url can then also be available. [2]

We could add a new function, generate_reporting_signals, called for each rendering_url in each interest group:

function generate_reporting_signals(
    interest_group_name, rendering_url, auction_signals, per_buyer_signals,
    limited_trusted_bidding_signals) {
  // limited_trusted_bidding_signals contains only the keys interest_group_name
  // and rendering_url
  return /* Arbitrary inputs for generate_bid and report_win */;
}

Note that this receives interest_group_name and not interest_group, because user_bidding_signals could be user-specific.

This produces an arbitrary reporting_signals, available to report_win:

function report_win(
    auction_signals, per_buyer_signals, seller_signals, browser_signals,
    reporting_signals) { ... }

For the CPC case, while this information isn't technically needed until the click, having it in report_win both allows joining with an eventual click and also provides additional visibility for debugging and calibration.

Since generate_bid can consider multiple rendering_urls, it receives a map from rendering_url to reporting_signals:

function generate_bid(
    interest_group, auction_signals, per_buyer_signals, trusted_bidding_signals,
    browser_signals, reporting_signals_map) { ... }

It would be possible for generate_bid to operate without reporting_signals_map, since it could re-derive everything from information it already has, but passing the signals from generate_reporting_signals into generate_bid simplifies the code and avoids duplicate computations.

We do acknowledge that this is temporary, and is based on distinctions that will not make sense after the transition to aggregate reporting. Still, we think it provides a critical feature for buyers in migrating to FLEDGE.

[1] In some cases rendering_url might pass k-anonymity checks while the interest group name does not. In these cases, reporting_signals should be available to generate_bid but dropped instead of being provided to report_win. Buyers who wanted to use this functionality would likely structure their usage of interest groups to make this case uncommon.

[2] The trusted server url is currently per-user, which would additionally be a hole in the privacy model. This is already a hole for bidding_logic_url, where nothing prevents buyers from using a per-user url and then reporting a user id in report_win. There is no reason for either of these to vary by user, so we propose moving them to be listed on the buyer's origin at .well-known/turtledove-config.

[jeffkaufman]

@michaelkleber would a PR to integrate generateReportingSignals into the main FLEDGE proposal be welcome?

[michaelkleber]

It sounds like you're not proposing any change in how data is retrieved from the key-value server, but rather treating some of the retrieved values differently from others.

I think this would be a substantial change in the assumptions we're making about the K-V server. In the current design, as long as the K-V server only sends information back to the browser that asked it a question, privacy is preserved; no matter what logic in the K-V server implements in picking the returned values, it can't affect FLEDGE's privacy properties, only which ad shows. But in the model you're proposing, the K-V server has a channel to return arbitrary data through the browser and to event-level logging.

Aggregate logging really seems like the right solution for the problems being described here.

[jeffkaufman]

@michaelkleber The idea behind the proposal above was that in any case where it is safe to report X it's safe to report key_value_server(X), if you have a key-value server that follows the spec. It sounds like you're saying that FLEDGE, as currently designed, is more robust to misbehaving key-value servers? And perhaps makes it easier to verify that they're behaving correctly?

Here's an alternative proposal which gets most of the benefits of generateReportingSignals without creating a channel where a non-compliant key-value server could invisibly sneak arbitrary data out via the browser. The operator of a fleet of key-value servers could use a versioned database, incrementing the version number each time they modify the data. For practical reasons they won't be able to ensure that the version is completely synchronized across their fleet, because rollouts will reach different servers at different times, but it should generally be close. This version number would only increment, not depend on any properties of the request, and be identical across the fleet, again modulo skew in rolling out new versions.

In every response the key-value server could include the version number as a header:

HTTP/1.1 200 OK
Content-Type: application/json
…
X-Allow-FLEDGE: true
X-Data-Version: 12345

{key1: value1, key2: value2}

Then the browser would make this number available to reporting via browserSignals:

{
   topWindowHostname: 'www.example-publisher.com',
   dataVersion: 12345,
   …
}

A key and version number are sufficient to determine what the server would have responded with. In cases where the key is already available in reporting, such as interestGroupName in reportWin and renderUrl in reportResult, this would allow the ad tech vendor to accurately reconstruct the key-value server response used in an auction.

To take the example of pCTR above, since all the inputs to the calculation are either (a) already available in reporting or (b) coming from the key-value server, then the calculation can be re-run on the server after reporting.

One risk with this proposal is that a key-value server could attempt to smuggle extra information back through the version number. Because in standard usage the version number would gradually increment and the version for one request would match contemporaneous requests, abusive usage would be easily identifiable externally. Additionally, whatever method is chosen for validating that the key-value server is spec-compliant general should be able to validate that version numbers do not depend on request-specific data.

[michaelkleber]

Thank you @jeffkaufman, this makes a ton of sense. Reporting a slowly-incrementing version number sent back by the KV server does seem like a great way to be useful while making any attempted abuse easily visible.

Of course you're quite right that there is a risk of version skew during updates. But honestly that was a risk all along, with a single KV server response including the values for multiple keys! So including an explicit version number probably makes that risk smaller, since it forces the server to think about skew instead of sweeping it under the rug.

@MattMenke2 and @brusshamilton PTAL?

[michaelkleber]

Yup, looks good. Jeff, want to send a PR to add this to the FLEDGE explainer? Or else we'll get to it when someone has time.

[mbowiewilson]

@jeffkaufman Maybe I am missing something, but I don't see how this #243 addresses my original comment that opened this issue. In particular, how does this help buyers pace spend or monitor prediction accuracy?

[jeffkaufman]

@mbowiewilson let's say you're using the name of the interest group as your key. That value is available in reporting, assuming it passes a k-anonymity threshold. Combine that with data-version, and you can figure out what the contents of the key-value response would have been. Then you can, for example, re-run your production code on the server, to calculate what it would have generated on the client, letting you check its accuracy.

[mbowiewilson]

Gotcha, thanks for explaining @jeffkaufman. I think this is a step in the right direction, but I am not yet convinced it totally solves the issues I raised.

I say this because generate_bid is a function of more than just the response of the key-value server. In particular, the probabilities a buyer might predict in generate_bid might depend on the interest group object (and not just its name). Please correct me if I am mistaken, but it seems to me that if a buyer wants their bids to depend on data in the interest group object, they won't be able to determine what generate_bid did or would have output even with #243. This conversation is closely related to issue #145.

[jeffkaufman]

@mbowiewilson that makes sense! If the buyer is willing to restrict themselves to the interest group name and information from the trusted server that is keyed on the name, then they can fully reconstruct things, but not if they want to depend on additional information.

Unfortunately, this is not easy to fix: the information you're talking about is potentially specific to a single user, so I don't see how it could be made available to event level reporting. I wonder if this might be a better fit for aggregate reporting?

[mbowiewilson]

Thanks for the quick responses @jeffkaufman, I understand your point about this being difficult from a privacy perspective.

I think this mechanism mostly achieves the third use-case I list above ("Monitoring inputs to generate bid"). Probably the second bullet point ("monitoring prediction accuracy") can be done with aggregate reporting since that isn't time-sensitive. Regarding aggregate reporting and the first use-case ("spend pacing improvements") there have already been concerns about the utility of aggregate reporting for spend pacing (especially for smaller campaigns), and the same concerns would apply to the performance-based spend pacing approach I brought up. So, depending on the details of the aggregate reporting API, that use-case may still be an unresolved issue.

[jeffkaufman]

Do you want me to modify my PR so it doesn't claim this issue is fixed?

I think of it as being as fixed as it is going to get, since I don't think there's any practical way to modify the spec to supply an arbitrary pipe from generateBid to reportWin, but you're the one who filed so I'll defer to you.

[mbowiewilson]

I don't mind if you want to call this issue fixed/resolved. The remaining part of this issue is mostly related to #145.

[michaelkleber]

Thanks for the discussion, both of you! I agree that handling non-personalized inputs, as in the PR, is an easier case, and general access to personalized signals is a better fit for aggregated reporting, which will need more discussion.

[palenica]

I'd like to comment on this issue in light of my current understanding of requirements placed on the key-value server.

The idea behind the Data-Version header presumes that there are discrete versions of the data set served by the KV server, and that transitioning from one version to the next happens in well defined discrete steps.

1. Consider use cases that require low-latency incremental updates, such as budgeting. For the budgeting use case, one wants to be able to make updates to individual keys that get reflected in serving within a few minutes. It is not practical to implement this via versioned snapshots.
2. In practical deployments, we expect the KV server to hold data that consists of multiple independent logical data sets (e.g. a data set related to ad campaign budgets and a data set related to ad candidates/creatives) that will have independent life cycles and update schedules. Even if one can define a version for an individual logical data set, versions for different logical data sets might be incremented independently.

I think that in deployments that need to support incremental updates and/or heterogenoeus data, the Data-Version header will be of limited utility (or impossible to populate in a way that provides acceptable privacy, low update latency and decent scalability).

[palenica]

To summarize my proposal presented in yesterday's call:

It is difficult to meaningfully enforce that an untrusted key-value server is behaving correctly; that is, it is not leaking information about the user (learned from the request) via the data-version field. In current state, a malicious untrusted server could leak 64 bits of user's identity via the data-version mechanism into event-level reporting.

We heard feedback that data-version is useful for certain use cases. To address the privacy risk, we propose to reduce the resolution of data-version to ~8 bits, enforced by the browser. We propose this restriction to remain in place for as long as an untrusted ("bring your own") key-value server is used.

With a trusted key-value server (where the code is open source, the server runs on suitable secure hardware that supports remote code attestation), it will be possible to verify by code inspection that the returned data-version value is independent of the request's content. With such a trusted server, restrictions on the resolution of data-version can most likely be removed.

Reduction to 8 bits of entropy can be acheved in two ways:

• only accept numbers between 0 and 2^8
• for use cases where it is convenient to interpret data-version as a timestamp, we can accept data-versions that look like a unix timestamp, suitably rounded (say to whole minutes) and clipped to be within some reasonable range (say +/-2 hours) of current time on the client device.