Figure 1. A high-level visual overview of the progressive decentralization steps of THEMIS. While StrawTHEMIS (left) relies on the Campaign manager to orchestrate the campaign, in THEMIS (right), a sidechain orchestrates the protocol. In THEMIS, users using the Brave Browser interact with privacy preserving ads and request rewards from a smart contract deployed on a sidechain.

THEMIS Protocol

To address the open problems regarding trust in StrawTHEMIS, we use a proof-of-authority (PoA) blockchain, where the protocol logic and payments are orchestrated by smart contracts. All participants can independently verify that the protocol runs correctly, thus requiring zero trust from one another. In particular, we define two smart contracts:

• The  Policy Smart Contract (PSC), which is responsible for the billing of users’ rewards and validating the payment requests. Furthermore, it is in this smart contract where [[\encpolicy]] (as introduced in part 1 of the blogpost) is stored. 
• The Fund Smart Contract (FSC), which receives and escrows the funds needed to run the campaign. The FSC is responsible for releasing (i) the funds needed for the payment of the users rewards, (ii) the advertisers refunds, and (iii) the processing fees for the campaign manager. 

In THEMIS, instead of relying on a trusted central trusted authority, we introduce the role of the untrusted campaign facilitator (CF). In the context of BAT Ads, the natural CF is Brave, as it is the party that maintains a relationship with the advertisers and the means to distribute the ads to the users through the Brave Browser. However, the THEMIS protocol supports multiple CFs running multiple campaigns in the same sidechain.

The responsibilities of the CF are: 

• To negotiate the policies (e.g. rewards per ad, impressions per ad) with the advertisers;
• To deploy smart contracts in the PoA ledger; and, lastly, 
• To handle on-chain payments. 

In THEMIS, the CF is an authorized entity by the blockchain’s PoA consortium. This entity could be an independent third party like the Electronic Frontier Foundation (EFF) [10] or a non-profit trade foundation of applications and developers of BAT applications. In addition, the BAT SDK [21] could provide the tools and APIs for developers to easily develop and join the network as a CF. The independent CFs can join the network as CFs after being vetted by the PoA consortium to act as a CF. Similar to existing successful volunteer networks (e.g., Tor [11] nodes, Gnutella [12] peers, etc.), in THEMIS anyone can act as a CF. 

Brave can play the role of the CF, as it has the means for negotiating ad policies with advertisers. In addition, the Brave Browser is in a great position to successfully deliver ads served by THEMIS, as it currently happens with Brave Ads. It is important to point out that by playing this role, Brave or any other entity do not receive any “special powers.” 

THEMIS ensures that everybody can audit and verify the behaviour of the different CFs, so advertisers can pick the CF they prefer to collaborate with based on their reputation. The CF is incentivized to perform the tasks required to facilitate the ad catalog, by receiving processing fees from advertisers. 

Although THEMIS supports multiple CF, for sake of simplicity we assume there is a single CF when explaining the protocol in this blogpost.

Figure 1. High-level overview of the user rewards claiming procedure in THEMIS. This operation of THEMIS consists of 4 different phases: (1) Definition of Ad Rewards and set policies, (2) Ad Reward claiming, (3) Payment Request, (4) Settlement of user payments and advertiser refunds.

Phase 1: Defining ad rewards

In Figure 1, we present a high-level overview of THEMIS. Similarly to StrawTHEMIS, in order for an advertiser to include their ad campaign in the next ad catalog facilitated by the CF of their preference, they need to transmit the ad policies (i.e. reward per ad) to the campaign facilitator (step 1a in Figure 1). In order to achieve this, each advertiser exchanges a symmetric key with the CF [footnote: For the creation of this key, they may follow an authenticated Diffie-Hellman key exchange protocol], [[\seckey_i]], for ad campaign [[i]].

The advertiser then encrypts the corresponding ad campaign and sends it, together with the appropriate ad creatives, to the CF. On its end, the CF 

• decrypts and checks the policies are as agreed; 
• merges the encrypted policies of the different advertisers into the encrypted policy vector, [[\encpolicy]];  and 
• deploys the two public smart contracts for this ad-catalog version (step~1b in Figure 1).

In addition, the CF creates a vector [[\seckey]] with all the advertisers’ secret keys [[\seckey_i]]: 

$$ \seckey = \left[\seckey_1, \seckey_2 , \ldots, \seckey_{\nrads} \right] $$

and generates a vector, [[\encseckey]], that includes each of the elements in [[\seckey]], encrypted with the public key, [[\valikey]], of the PoA validator nodes: 

$$ \encseckey =  \left[ \enc(\valikey, \seckey_1), \ldots, \code{Enc}(\valikey, \seckey_{\nrads}) \right]. $$

This should be seen as a Hybrid Public Key Encryption scheme [13]. Then, the CFstores [[\encseckey]] in PSC to allow the  PoA validators to decrypt and apply the corresponding policies on users’ ad interaction vectors.

Once PSC is deployed, the advertisers must verify if [[\encpolicy]] encodes the policies agreed with CF (step 1c in Figure 1). More specifically:

• First, the advertisers fetches [[\encpolicy]] vector from the public storage of the  PSC and decrypts the policy, [[\encpolicy[i]]], using the corresponding symmetric key, [[\seckey_i]], and verifies it is the agreed value.
• Second, they fetch the escrow account address from FSC and transfer funds to the escrow account. The amount of funds needed is determined by the number of impressions they want per ad (which is part of the agreed policy [[\policyvector[i]]]), and the processing fees to pay CF. Once the campaign is over, the advertisers may get a refund based on the final number of impressions viewed/clicked by users. By escrowing the campaign’s funds, the advertiser implicitly validates the deployed ad policies.

Once the FSC verifies that advertisers have transferred to the escrow account the correct amount of funds, the campaign is initialized and verified. 

Policy Agreement

The campaign facilitator and advertisers agree on the policy vector [[\policyvector]] for a campaign set (see step 1 in Figure 1). The policies are discussed and agreed between CF and the advertisers through a private and secure channel. For the sake of simplicity, we define an ad policy as the amount of tokens that users should receive after clicking an ad. In practice, the policies can be arbitrarily complex to better represent the user interaction of ads. The campaign facilitator encodes the ad policies agreed with all advertisers in the campaign similarly as described in the first blog post of the series.

Phase 2: Claiming ad rewards

Similar to what we illustrated in StrawTHEMIS, in order to claim their ad rewards, each user creates an ephemeral key pair [[(\pk, \sk)]]

and obtains the public threshold key, [[\distpk]], generated by the consensus pool which is published on a blockchain (see section on the selection of participants pool above where we give an overview of how the consensus pool is generated). By using these two keys, each user encrypts their ad interaction vector to generate two ciphertexts: 

1. the [[\encryptedvector]] that is used to claim ad rewards and 
2. the [[\encvecpublic]] that is used for the advertisers reporting. 

Contrary to our centralized StrawTHEMIS design, the aggregate calculation in THEMIS is performed by the policy smart contract (as can be seen in step 2b in Figure 1). The user calls a public endpoint on the PSC with both ciphertexts mentioned above. To calculate the encrypted sum of the rewards the user can call (step 2b in Figure 1) the smart contract (running by the PoA consortium validators) which performs the following computations: 

• it decrypts each policy [[\policyvector[i]]] using [[\encseckey]] (see section Private input transactions on PoA blockchains); 
• it leverages the additively-homomorphic property of the underlying encryption scheme of [[\encryptedvector]]to apply the policy (computed following the steps described in StrawTHEMIS), and finally,
• it stores the result, [[\encryptedaggregatedresult]], in the policy smart contract native storage. Note that given that the user’s public key was used for encrypting [[\encryptedvector]], only the user can decrypt [[\encryptedaggregatedresult]] and retrieve the aggregate.

Phase 3: Payment request

Once the PSC has calculated the aggregate result (step 3 in Figure 1), the user generates a payment request, [[\payreq]], that, if valid, is published in the fund smart contract (FSC). More specifically, the user performs the following steps:

• Creates an ephemeral blockchain account (used only once per request) with address [[\addr]].
• Fetches and decrypts the encrypted aggregate result, [[\encryptedaggregatedresult]], to get the decrypted reward, [[\decryptedaggr]], and generates the proof of correct decryption, [[\aggrproofdec]].
• Generates the payment request which consists of the following~3-tuple: 

   $$ \payreq = \left[\decryptedaggr,\aggrproofdec, \addr \right]. $$

• Finally, the user calls a public endpoint on PSC with the [[\payreq]] encrypted with the validators keys, [[\enc(\valikey, \payreq)]] as input. The function then fetches the user’s aggregate, [[\encryptedaggregatedresult]], decrypts the request, and verifies the zero-knowledge proof, [[\aggrproofdec]]. If the proof is valid, PSC stores [[\addr]] in the FSC, which keeps a list of buffered user payments until they are marked as paid. 

Phase 4: Payment settlement

The final step of the protocol regards the settlement of the user payment and advertiser refund. 

Specifically, the settlement of the user rewards in THEMIS needs to happen in a confidential way to preserve the privacy of the total of earned reward. To achieve this, the CF fetches the pending payments requests from FSC, and calculates the total amount of funds required to settle all pending payments. 

As a next step (step 4a in Figure 1), the CF calls a public function of FSC requesting to transfer (to an operational account owned by CF) a given amount of tokens needed to cover the payments. If the CF misbehaves (by requesting an incorrect amount of tokens), it will be detected, and either advertisers or users will be able to prove its misbehaviour.

Finally, CF settles each of the pending reward payments by using a confidential payment scheme. After finalizing the payments correctly (and if there are no complaints frоm either users or advertisers), the CF receives the processing fees from FSC.

In case of unused escrowed funds, the advertisers need to be refunded. To achieve this (step~4c in Figure 1), FSC utilizes the aggregate clicks per ad vector that the consensus pool has computed during the advertisers reporting. Based on this vector and the agreed rewards, the FSC proceeds with returning to the advertisers the unused funds. Note that a campaign ends when either i) the ads budget has been fulfilled or ii) the ad campaign has expired. Both the PSC and FSC are deployed with an expiration timer, which ensures that the ad campaign terminates eventually.  

Implementation Details, Performance, and Scalability

In this section we discuss the end-to-end measurements of THEMIS, with a focus on overall performance and scalability of the protocol. We implemented a client and the smart contracts implementing the reward calculation and proof verification. For the purposes of measurements and experimentation, we deployed a Quorum [quorum] sidechain on a production-like environment in AWS. 

Our main focus in this section is to present the client-side performance and scalability of the protocol. We also explore the possibility of resource overload when running the encryption, decryption, and plaintext recovery necessary to run the protocol on the client side. 

The measurements focus on i) client-side resource consumption, ii) end-to-end performance and scalability of the protocol, and iii) the scalability of the anonymous payment protocol used by THEMIS. More specifically, we answer the following questions:

1. How much time – and resources – does the client consume to perform the necessary computation when generating a reward request and corresponding proofs?
2. How many payment requests can a sidechain process per day, considering catalog sizes of 256 ads?
3. How many anonymous payments can we perform per month on the sidechain?
4. Finally, does THEMIS scale to the number of users and reward requests expected by Brave Ads?

Implementation details and measurement setup

We implemented the client side of THEMIS in Rust and the policy smart contract in Solidity. All the code can be found on github and it is widely documented, so feel free to join the conversation and  contribute to the project!

The client-side implementation uses the web3-rust [ref: web3-rust] crate to interact with the sidechain. We leveraged the curve25519-dalek [15] and the elgamal_ristretto [16] crates for implementing the underlying public key cryptography that generates the key pairs and performs the encryption and decryption required by THEMIS. The policy smart contracts used a precompiled smart contract [17] to perform addition and scalar multiplication in alt_bn128 curve.

We used Mjolnir [18] to easily deploy 4x Quorum nodes running on AWS EC2 t.2xlarge instances (8 vCPUs, 32 GB) all in the same region (us-east-2) and same subnet. For the purpose of the measurements, the network communication is considered negligible. This setup can be easily emulated in production by setting up peering among different AWS Virtual Private Clouds across validator organizations. 

In order to test how many concurrent users the sidechain can cope with, we’ve deployed several AWS EC2 t2.large instances (2 vCPUs, 8 GB RAM), running the client-side logic. We performed end-to-end performance measurements by running  10, 30, 60 and 100 concurrent clients which request reward from the sidechain at roughly the same time.

System Performance

Latency and resource consumption are important factors to provide a good user experience, especially when the client runs on low-end devices and browsers. One of the main goals of THEMIS is to be practical and scalable for large-scale ad systems. Thus, we implemented a prototype of the core protocol of THEMIS [22] and measured the performance and scalability in production-like environments. This section outlines the results obtained from those measurements.

A. End-to-end performance and scalability

One of the most important challenges of privacy-preserving ad platforms is scalability. In the case of THEMIS scalability consists of how many reward requests the sidechain can handle over time.

We set out to explore the execution time of the requests a client issues in THEMIS (i.e., rewards claiming (Phase 2) and payment requests (Phase 3)) and the time it takes for the sidechain to process those requests. In order to do so, we launched multiple concurrent clients which requested the reward computation concurrently from the sidechain and measured the time to completion of the different phases of the protocol (Figure 2).

In Figure 2 we saw that for an ad catalog of 256 ads and 100 concurrent users performing a payment request, it takes around 5 seconds to complete 100 concurrent payment requests. This means that under the same conditions, the sidechain can process around 1.7M concurrent payment requests per day, which translates to a total of 51M reward requests per month.

Figure 2. Cumulative time (in seconds) for the THEMIS protocol runs with 64 (yellow), 128 (blue), and 256 (green) ads. In red, the overhead caused by proving and verifying correct decryption. Results presented for a number of concurrent clients requesting the reward computation from the smart contract.

We conclude that when 100 users concurrently i) generate a reward request and ii) requests the reward calculation from the slide-chain, it takes around 5 seconds for the reward to be calculated per client. If we consider a monthly payout (i.e., users request rewards and are paid every month), we conclude that THEMIS can handle 51M users per month, under the circumstances described above.  

Horizontal scaling: The computations performed by the smart contracts in sidechain are highly parallelizable. However, the one-threaded event loop of the Ethereum Virtual Machine (EVM) does not support parallel and concurrent computations. Therefore, the EVM run-time becomes the scalability bottleneck when it has to handle more than 100 concurrent user requests. To overcome this, we tested THEMIS running on multiple, parallel sidechains. Each sidechain is responsible for one or more ad catalogs each. Although this could increase coordination complexity, the scalability gains are considerable as the number of rewards requests processed grows linearly with the number of sidechains. Thus, THEMIS can be scaled-up to support tens of millions of concurrent users per day.

B. Client-side performance and resource consumption

To measure the performance and resource impact of running the THEMIS routines in the client, we measure the time it takes for a client to generate locally a rewards claiming request for three different ad catalog sizes (64, 128 and 256 ads). In Figure 3, we present the results of the measurements, which include:

1. Interaction encryption: includes the encryption of the interaction array of the user, and
2. Request generation: includes decryption of the pay- ment aggregate, generation of the proof of correct decryption and recovery of plaintext.

As can be seen in Figure 3, the execution time to encrypt user interactions for an ad catalog of 256 ads is as low as 0.1 sec. Similarly, for the same ad catalog size, the request generation procedure takes around 0.7 sec, proving that the client computations for reward claiming can be done on a commodity laptop or mobile device, without significant impact on the user experience.

Apart from issuing reward claiming requests, a client also performs periodic rewards payment requests. However, such requests take place in relatively long intervals (e.g., monthly) and therefore the latency and resource consumption imposed to the user are practically negligible.

Figure 3:  Execution time of the client-side operations during reward claiming for different ad catalogs sizes: 64, 128, and 256. For an ad catalog with 256 ads it takes 0.1 ms when request generation takes around 0.7 sec.

Based on these results, we conclude that the resource consumption for generating reward requests on the client-side considering an ads catalog of size 256 is negligible. This observation is important, since we need to run clients on resource-constrained devices (e.g. mobile devices), without impacting user experience and energy consumption.

Performance and scalability insights

Now we are in a good position to return to the questions we set out to answer in the beginning of this section: 

1. How much time – and resources – does the client take to perform the necessary computation when generating a reward request and corresponding proofs?

Given our results, we conclude that the overhead on the client side is negligible. This result is important since we would like a client to run on resource-constrained devices (e.g. mobile devices), without impacting user experience and energy consumption.

2. How many payment requests can a sidechain process per day, considering catalog sizes of 256 ads?

Based on the results of the Figure 2, an end-to-end reward request takes about 5 seconds to finalize when 100 concurrent clients request the reward. If we assume a distributed pattern of reward requests across the network, THEMIS supports about 1.7M reward requests (end-to-end) per day, which accounts for roughly 51M reward requests processed per month. This number can be further improved by running THEMIS on multiple, parallel sidechains.

3. How many anonymous payments can we perform per month on the sidechain?

The THEMIS protocol is agnostic to which privacy preserving payment is used for settling the valid reward requests. If we use AZTEC for privacy-preserving transactions and its proof batching verification, the time and resources required to issue payments are not a scalability and performance bottleneck for THEMIS. 

4. Finally, does THEMIS scale to the number of users and reward requests expected by Brave Ads?

Currently, Brave Ads serves catalogs to users with about 200 ads in average and it pays around 2.5M Brave Ads users per month. Thus, THEMIS could support the current Brave Ads load.

Threat Analysis

In this work, we assume computationally bounded adversaries  capable  of  (i) snooping  communications,  (ii) performing  replaying attacks, or (iii) cheating by not honestly following the protocol. 

1. One such adversary may act as CF, aiming to collect more processing  fees  than  agreed  at  the  cost  of  either user  rewards  or advertiser refunds. Such adversaries can control any  node  of  the  system  but  (following  the  limitations  of  the underlying  POA) not the majority of the validator nodes. 
2. Other  adversaries  may  aim  to  breach  privacy  of  the  user and snoop the interactions of the user with the ads. Such interactions  can  reveal  interests,  political/religious  preferences, that can later be sold or used beyond the control of the user. Such adversary can control any node in the system but cannot control all users: in a realistic scenario adversary  can control  at  most k of  the n randomly  selected users that are part of the consensus pool (consensus pool participants share a threshold key, as described in the first blog post). 
3. There  may  be  also  adversaries  that  will  try  to  break  the confidentiality of the advertisers’ agreed ad policies and disclose rewarding strategies that can give advantage to competitors. 

Participant Incentives

Incentives are important mechanisms to motivate participants in decentralized networks to cooperate and follow the protocol correctly. Participants in the THEMIS protocol are incentivized to perform their tasks successfully. BAT tokens can be used to that end.

The campaign facilitator is incentivized to behave honestly through the commission fees for running the campaign successfully. Importantly, the CF receives the processing fees if the protocol runs honestly. The fees are released by the fund smart contract logic, if by the end of the campaign there were no successful challenges to the CF behaviour. In addition, a misbehaving CF will lose trust of advertisers and users and squander the opportunity to earn commission fees in the future. In addition, the consensus pool participants and the validator nodes can be incentivized with crypto tokens (e.g. BAT) to perform useful work to keep the system running.

Summary

In this blog post, we presented a full version of the THEMIS protocol introduced in Part 1 of this blog series. THEMIS is a private-by-design ad platform that leverages a sidechain and smart contracts to eliminate centralized ad network management. Although it can be deployed by any ad network, our focus was to lay out a progressive approach to decentralize the BAT ecosystem. Brave Ads and THEMIS aim to be an alternative to the current digital advertising ecosystem, by solving the fundamental flaws in the current online ads ecosystem: trust and invasion of user privacy. In addition, BAT can be used to incentivize every participant to perform useful work to the network.

We implemented and made public the client-side and smart contract of the core blocks for running THEMIS. We used that implementation to measure client resource consumption and end-to-end scalability, and conclude that THEMIS could support the current load of Brave Ads in production. The experimental evaluation shows that the performance hit on the client side for participating in the protocol is negligible. In addition, our measurements show that THEMIS can handle over 51M  concurrent users, when serving a catalog of 256 ads on a single sidechain.

References 

[1] Zerocash Paper
[2] Bulletproofs: Short Proofs for Confidential Transactions and More
[3] Monero 
[4] Aztec Protocol
[5] Zether: Towards Privacy in a Smart Contract World
[6] Overview of Private Transactions in Quorum
[7] Verifiable Random Functions
[8] Vault: Fast Bootstrapping for the Algorand Cryptocurrency
[9] ETHDKG: Distributed Key Generation with Ethereum Smart Contracts
[10] Electronic Frontier Foundation
[11] The Tor project
[12] Regarding Gnutella
[13] Hybrid Public Key Encryption
[14] web3-rust library
[15] Curve25519 rust implementation
[16] ElGamal implementation using Curve25519
[17] EIP 196: Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128
[18] Mjölnir …the hammer of Thor.
[19] Quorum blockchain documentation
[20] ZK-Rollups 
[21] BAT SDK
[22] THEMIS – Prototype implementation (github)