--- title: THEMIS Implementation Specs description: high level formalization of the THEMIS protocol tags: crypto, brave --- # THEMIS Implementation Specs **Context**: This document describes the cryptographic schemes and primitives necessary to implement THEMIS and it outlines how to integrate the different versions of the THEMIS protocol in the Ads infrastructure. - [THEMIS goals](#THEMIS-goals) - [THEMIS protocol in Brave Ads](#THEMIS-protocol-in-Brave-Ads) - Antifraud and reputation integration - Ad campaign analytics and reports - Client-side integration - [O1Labs scheme](#O1Labs-scheme) - Description - Cryptographic primitives - Implementation - Performance considerations - [Aztec scheme](#Aztec-scheme) - Description - Cryptographic primitives - Implementation - Performance considerations - [BBA-based scheme](#BBA-based-scheme) - Context - Requirements - Cryptographic scheme - Performance considerations - [Performance/resource comparison](#Performanceresources-comparison) - Client-side - Server-side - L1 costs ## THEMIS goals - Maintain/improve privacy and security assumptions and threat model o the current Ads protocol - *Client verifiability*: Clients can verify that their rewards are calculated as expected at every step of the process - *Reward verifiability*: Anyone (or at least participants) can verify that reward requests are valid - *Advertiser verifiability*: Advertisers can verify that their budget is being spent by clients as reported by Brave - Decentralised Reward verification and automatic on-chain settlement process - Payment upon correct reward proof verification on-chain (*future*); - Privacy-preserving on-chain KYC (*future*); - Integration with current Antifraud pipeline - Support for embedding private parameters in the token; ## THEMIS protocol in Brave Ads The Ads flow with THEMIS is similar to the current protocol: 1) Ad catalog is distributed to the user; 2) User requests the initialization of a new BBA/accumulator to Brave; 3) Brave checks reputation of the wallet and encodes result in the new BBA (as in tainted tokens). Brave ints the accumulator and returns it to User; 4) User interacts with ads and, at each interaction, requests an update on the accumulator through an "anonymous channel"; 5) Brave verifies if the accumulator and interactions are valid and the reputation on the accumulator and updates the accumulator accordingly; 6) User randomizes the accumulator; 7) At the end of an epoch (or after a reward threshold), the user calculates the reward based on the accumulator state and generates the proof of correct reward calculation; 8) User sends the reward request alongside with the accumulator state; 9) Brave checks reputation of the accumulator, verifies proofs and settles the reward if everything is ok. 10) Alternatively, the rewards may be verified on-chain; ![](https://i.imgur.com/4qzG9dw.png) *Fig 1. THEMIS request flow* ![](https://i.imgur.com/rDfLjsF.png) *Fig 2. On-chain verification* ### Antifraud and reputation integration THEMIS integrates seamlessly with the current antifraud and reputation pipeline, with the added benefit of providing the "tainted tokens" features out of the box. - **Antifraud pipeline integration** - The current antifraud pipeline can be used without any changes: - Before issuing a new accumulator to a wallet, Brave checks the reputation of the wallet in the current reputation service; - Before accepting the payment request from a user, Brave can check the current wallet's reputation; - **Tainted accumulator** - All the schemes considered allow Brave to "taint" the acccumulator to keep a reputation that is private to the user; - Brave can check if the accumulator is owned by a reputable wallet or not; - Brave can check the reputation of the wallet while verifying the reward request by the wallet; - **Reputation verification at ad interaction** - When the user requests an accumulator update through the anonymous channel, although Brave does not learn which wallet is requesting the update, it can verify whether the update is requested by a reputable wallet of not; ### Ad campaign analytics and reports THEMIS integrates seamlessly with the current way Ads does campaign analytics. Each ad interaction is reported through a privacy channel (i.e. Fastly dropping the origin IP) when the user requests the accumulator update ([Step 5](#THEMIS-protocol-in-Brave-Ads)). ### Client-side integration ## O1Labs scheme Raw submission: https://hackmd.io/@izzy/rJApOn5zu PoC implementation: https://github.com/imeckler/bba **Fundamentals** - *Scheme selling points:* - **Client side performance** (compute): proving correctness of reward computation requires about 1 second on a single core. - **Client side performance** (bandwidth): BBA updates involve a single message of about 2kB from the user plus 8 bytes per campaign to update, and a response of about 64 bytes. - The user sends an opening proof to the roll-up prover which is roughly 2kB.= - **On-chain verification**: Computation of the roll-up proof costs about $0.000446 per reward-payout (Mina) - **No trusted setup, and no pairings**: The security is based on the hardness of discrete log for the Pasta curves and the random oracle model. **High-level description of the proposal**: O(1)Labs team proposed replacing the pairing-based BBA with a Pasta-based zero knowledge proof (ZKP). Similarly to the original THEMIS design, the user maintains the state of the ad interaction encoded in an accumulator which is updated by Brave and, later, the user calculates and proves correctness of the reward computation based on the state of the accumulator. Using the Pasta curve instead of a pairing-based curve is an important optimization as it makes it cheaper to prove statements over the user’s ad interaction state and the ZK scheme does not require trusted setup. The Pasta curve is used in protocols such as PLONK to optimize the recursive proof systems. Thus, proofs from multiple users can be batched together and verified on and off-chain with amortized costs through a ZK-rollup system. In addition, the O(1)Labs team proposed to leverage the Mina blockchain as the payout layer for low on-chain payments and to allow constrained devices (e.g. Brave running on mobile phones) to verify payments without relying on a 3rd party. Based on their measurements and estimates, the proof generation, verification, batching and on-chain verification is within the requirements for THEMIS in terms of computation costs and bandwidth. ## Aztec scheme The Aztec team proposes a new BBA design that encodes the state of the ad interactions in a merkle tree. Each tree leaf keeps the state of an interaction with ads from a particular advertiser. Each leaf contains a Pedersen hash of the user’s private key and the ad interactions. This allows the user to commit to an ad state, while maintaining it private. Each BBA update is a PLONK proof generated by the user, where the user proves that the new merkle tree state consists of a state previously signed by Brave with a new leaf that represents the new event. The reward calculation consists of opening the Merkle tree-based BBA inside a ZK-SNARK circuit where every non-zero leaf (i.e. the user’s interaction with ads) is a private witness to the circuit and prove that the reward is the inner product of the private witnesses with the amount of BAT to be paid per ad interaction. Further, a ZK-rollup system such as Aztec can be used to prove to batch and verified on-chain for amortized costs. The on-chain batch verification can be performed using TurboPLONK for optimized verification performance on Ethereum. In addition, the Aztec team proposes that the verifier smart contract mints an Aztec private note that allows the users to withdraw BAT corresponding to their valid on-chain proof verifications, effectively closing the loop in the rewards protocol. Aztec team proposes to implement the proof system and the client code using the Aztec SDK. They also provide an SDK for the rollup and recursion logic and smart contract code to verify the proofs on-chain. ## BBA-based scheme ### Context **Blackbox Accumulator (BBA)**: (or updatable anonymous credentials) BBA is a cryptographic token that lets users collect and to request updates to increase/decrease embeeded counters. The token is unlikeable across user events, i.e. the issuer of token cannot link counter update requests. In addition, users cannot tamper with the counters, only issuers may do it. BBAs can be used in the context of Ads: - A BBA token keeps track of the rewards accumulated during a campaign; - Tokens are linked to wallets during issuance and redemption stage. Only the wallet owner can redeem the BAT rewards associated with the token counters; - Token update requests (to increase rewards) cannot not linked to user wallets; - Token update requests in the same token cannot be linked together; - The token mat contain additional attributes (e.g. antifraud related); The construction of the BBA scheme is based on BEKSS ([bekss](#Bibliography)) with a couple changes: i) remove the need for "partial spending" of the balance in the counter and ii) add multiple counters. The advantages of using BEKSS in THEMIS is that the proof of token ownership by the user is constant with the number of counters in the token. Thus, the BBA can encode a large number of ad interactions while the ownership proof remains constant. Most of the Algebraic MACs and other anonymous credentials require ZKPs for users to generate proof of ownership of a valid token. The BEKSS BBA scheme does not use ZKPs and, instead, it uses structure preserving signatures over equivalence classes (SPS-EQ). The issuer takes a tuple (h, g) of group elements and signs it. The exponentiation of the tuple (h^c, g^c), where c ∈ Zp, is still a valid signature. From a high level, the user can "randomize" the signature of the token by exponetiating the tuple [h, c] by adapting the signature to a different element of the equivalence class. The signatures are not linkeable. ![Interaction flow BBAs](https://i.imgur.com/UknWFLy.png) *Fig 3. Interaction flow BBA in Ads* <!--- ## Anonymous Credentials, Algebraic MACs Multi-show unlikeability: User can prove, under different pseudonyms, that she has a given capability to multiple parties. Each party cannot link multiple pseudonyms together. ---> ## Performance/resources comparison | Submissions | Proof generation computation | Proof generation bandwidth | Proof verification | Batching | On-Chain verification | | --------|--------|--------|--------|--------|--------| | O1Labs | ≈ 1sec proving time (for BBA update and reward calculation proof) | ≈ 1kB (for BBA update and reward calculation proof) | 1ms per proof + 10ms per batch (for BBA update); xxx (for BBA rewards) | 160 * N sec (N number of proofs to batch); roughly $0.000446 per proof @ GoogleCloud | on Mina: low costs (estimate); on Ethereum: $0.25/ payout for 50M batched transactions | | AZTEC | ≈ 9,300 constraints for BBA update (<1s); ≈ 250 N constrains for reward calculation (5-10s) ||| 4min to aggregate 28 tx in single rollup; aggregating 32*28tx takes 4min => ≈ 2h for building 896 tx rollup (UltraPlonk will be 2.5-3x faster)|| ## Bibliograpy - [**bekss**](https://eprint.iacr.org/2020/382): Jan Bobolz, Fabian Eidens, Stephan Krenn, Daniel Slamanig, and Christoph Striecks. Privacy-preserving incentive systems with highly efficient point- collection. In Hung-Min Sun, Shiuh-Pyng Shieh, Guofei Gu, and Giuseppe Ateniese, editors, ASIA CCS ’20: The 15th ACM Asia Conference on Com- puter and Communications Security, Taipei, Taiwan, October 5-9, 2020, pages 319–333. ACM, 2020.