This post describes work by Ralph Ankele, Sofia Celi, Ralph Giles and Hamed Haddadi.

Enabling verifiable advertisement interaction and reward computation with privacy-preserving cryptography

In today’s data-driven world, digital interactions are continually monitored. Many online platforms use data-driven incentive schemes to reward users for engaging with content, like watching ads or participating in surveys. However, these schemes often come with a catch: they may collect and store personal data to track engagement. This presents a problem because users are essentially sacrificing their privacy for small rewards, leaving their data vulnerable to misuse.

Privacy-preserving incentive schemes offer a solution by allowing users to receive rewards without exposing their personal information. Brave Rewards, for example, is designed to reward users for viewing ads while keeping their data private. The system respects user privacy by ensuring that ad engagement data stays on their device, never shared or stored externally. However, as demand for verifiable, decentralized systems grows, enhancing this model to provide stronger guarantees of privacy and reward accuracy is critical.

Privacy-Preserving Incentive Protocols

Privacy-preserving incentive schemes are becoming essential as digital platforms increasingly seek ways to reward users for engagement without compromising their personal information. These schemes rely on cryptographic methods to ensure that users can verify rewards and interactions without exposing sensitive data. The primary goal is to create an ecosystem where users maintain anonymity while still benefiting from their engagement.

The Boomerang protocol builds upon the following research works: The Black-Box Accumulator (BBA) scheme works by “accumulating” tokens without directly associating them with the user, creating a layer of privacy around interactions. BBA+, an improved version of BBA that optimizes cryptographic proofs, prevents double spending, and supports negative point collection, making it more efficient. Building on these foundations, Black-Box Wallets (BBW) is a privacy-preserving payment solution tailored for constrained devices. Another noteworthy protocol in the privacy-preserving incentive landscape is Privacy Pass. Originally designed as an anti-bot mechanism, Privacy Pass can be used as a versatile tool for privacy-preserving rewards.

Brave Rewards currently uses Privacy Pass as a key component of its system, enabling users to earn rewards in a privacy-respecting way. For example, when users engage with Brave Ads or perform certain actions (such as viewing an ad or clicking on one), Privacy Pass generates cryptographic tokens (not to be confused with BATs) to validate these interactions without revealing specific details about the user’s identity or browsing habits.

The Boomerang Protocol explained

The Boomerang protocol specifies a novel decentralized privacy-preserving incentive protocol to securely and privately store user interactions within an incentive system. The protocol leverages cryptographic methods to transparently compute rewards for users, ensuring verifiability while preserving their privacy.

The protocol defines four components that are interacting with each other:

• Client: This is the Brave browser with Brave Rewards enabled. The client can be on any platform, either desktop or mobile. This actor is who interacts with the advertisements, and gets rewarded in return for interacting with the ads. 

• Issuer: This is the provider of the incentive system. This actor verifies the correct computations of the client, and also initiates the rewards payment for the client. For instance, Brave can be an issuer for the Boomerang incentive system. 

• Advertiser: These are individual advertisers that promote their content, that are shown to clients that have Brave Rewards enabled within their Brave browser. Clients can interact with those advertisements and get rewarded for doing so. 

• L1 Blockchain: This can be any blockchain that offers smart contracts, and implements the Boomerang protocol. This actor publicly and transparently verifies the correctness of the rewards computation and issues the payment to the user. 

They interact as illustrated below:

Let’s consider an example, to see how Boomerang works in detail. The User, let’s call him Joe in our example, no longer wants to be left out when looking at advertisements while browsing the web. Moreover, Joe wants to see privacy-respecting advertisements and therefore enables Brave Rewards in his Brave Browser. After enabling Brave Rewards, a token is initialized by the Client he is using, either the desktop Brave browser, or on his mobile device. The issuer of the incentive system, in that case Brave, is sent a Proof of Issuance, to verify that everything was correctly initiated. 

Next, Joe is browsing the web as he normally does, interacting with some advertisements along the way. In the background, the advertisement interaction is stored on Joe’s client, and a Proof of Token Update of the regularly updated interaction state is shared in zero-knowledge with the Issuer. 

After interacting with advertisements for a while, and collecting reward points, Joe decides to ask to get rewarded for his interactions. His client sends a request for reward computation, and the Issuer creates a Reward Proof, specifying how much Joe will get paid for interacting with the incentive system. This Reward Proof is then sent to a L1 Blockchain. 

The L1 Blockchain runs a smart contract and publicly verifies in a transparent way that the rewards computation has been done correctly, and the proof is valid. Finally, the smart contract issues payment of the reward to Joe. And that’s it.    

In a nutshell, that is how the Boomerang protocol works. All the proofs mentioned above are cryptographic zero-knowledge proofs, that enable a Prover to prove the correctness of a statement, without the Verifier learning anything about the statement. Moreover, the individual advertisement interactions are collected in an unlinkable way using blinding and unblinding techniques, meaning they cannot be linked together. Finally, as the smart contract that verifies the rewards computation is public and transparent, the User can verify that the computations of the Issuer have been done correctly. This is what makes the Boomerang protocol a decentralized privacy-preserving verifiable incentive system.  

Boomerang Protocol extended

The Boomerang protocol can be split into three procedures/sub-protocols. These are:

• Issuance: This procedure initializes the token,

• Collection: This procedure updates the token with the advertisement interactions of the user,

• Spending/Verification: This procedure redeems the collected points and creates a rewards proof that can be verified on a L1 blockchain.

We will provide details about each of the procedures next.  

Issuance Procedure

The aim of this procedure is to jointly generate tokens, between the User and Issuer, that the User commits to and the Issuer can blindly sign. Boomerang leverages Pedersen commitments for the User to commit to the advertisement interactions. Moreover, we leverage the Blind Signatures with attributes (ACL) scheme so the Issuer can blindly sign the tokens. After a User verifies the blind signature, they then build a cryptographic accumulator called a CurveTree and make the root of the tree public.

Collection Procedure

The Collection procedure consists of adding positive points to the token, representing individual interactions with advertisements, in an unlinkable manner. The correctness of the token update is ensured by several zero-knowledge proofs based on Sigma protocols.The Issuer can verify the correctness of those proofs and blindly sign the tokens. In return, the User verifies the blind signature and rebuilds the accumulator.

Spending/Verification Procedure

The Spending/Verification procedure works similarly to the Collection procedure. The exception is that instead of adding positive points, this procedure will add negative points (i.e. the amount of points that should be the reward) to the token. Additionally to updating the tokens, the Issuer creates the Reward proof, where we leverage range proofs from the Bulletproof zero-knowledge proofs. This Reward proof can then be verified in a smart contract on a L1 blockchain in a transparent and public verifiable manner.

Demo Time

To illustrate further how the Boomerang protocol works, let’s put it in practice. We have implemented a simple proof of concept implementation in Rust which is available at: https://github.com/brave-experiments/Boomerang 

After cloning the git repository you can run the demo by first building using

cargo  build

Next, you can run a server instance, simulating the Issuer by running

cargo  run  --example  server

Clients can be simulated by running a client instance with

cargo  run  --example  client

The end to end demo will start up a server instance, and one client instance. Then it will go over all the three procedures of the Boomerang protocol, as explained above. Initially, the Issuance procedure will be called, that initializes the token. Next, the Collection procedure is called, which updates the token with some advertisement interactions. Finally, the SpendVerify procedure is called, which initiates a reward calculation. For the purpose of simply showcasing the proof of concept, the reward proof is verified by the client instead of being sent to a L1 blockchain.    

The output of the server instance should look like this

The output of the client instance looks like this

Conclusion

Boomerang is a novel decentralized privacy-preserving verifiable incentive protocol. The protocol leverages cryptographic methods to transparently compute rewards for users, ensuring verifiability while preserving their privacy. 

A more detailed technical description of the protocol can be found in the technical report. A demo implementation is further available at: https://github.com/brave-experiments/Boomerang