Early this year, we announced the work our research team has been doing on THEMIS, a protocol to progressively decentralize the Brave Ads infrastructure. Over the past few months we worked actively with more than 10 teams in the Web3 and crypto ecosystem and heard their feedback on how we could integrate their tech stack in the context of THEMIS to improve scalability and performance; and to guarantee the high privacy standards our users expect from Brave. We received 10 RFC&C proposals from teams focusing on both L1 and L2 tech that brought practical insights on how to improve the original THEMISv2 protocol spec. In this blogpost, we’ll dive into each of the received proposals and provide pointers for the material each team submitted for the RFC&C. Going forward, we’ll align with the teams who submitted the most promising proposals to formalize, implement and productize the THEMIS protocol.

Outline

This blog post is a wrap up summary for the RFC&C event:

• RFC&C event is over and it was a great success
• We had 10 submitted proposals and this is the high level summary (with pointers to raw submissions)
• We outline the next steps and roadmap

The RFC&C event consisted of a hands-on event where the research team worked actively with several teams to improve the THEMIS protocol. After a couple of months of technical discussions and coding, we’re happy to announce that some of the proposals will be added to the THEMIS spec. 

Submission Overview

The teams’ proposals fall into one (or more) of the following areas within the THEMIS protocol:

1. Redesigning the Black Box Accumulator (BBA): The THEMIS protocol relies on a cryptographic accumulator that enables users to maintain and request updates of their state of ad interactions. The state of the BBA is tamper-proof and its contents and updates are verifiable to avoid fraud. Several teams have proposed improved BBA schemes that improve on our initial proposal, namely in terms of size of the accumulator, the resources required to generate and update the state of the BBA, and the cryptographic assumptions required. Teams such as Aztec, IMDEA Software Institute, O(1)Labs, Plasm and StarkWare have submitted proposals to redesign our initial design of the THEMIS BBA.
2. Scheme for proving and verifying the reward calculation (on-chain and off-chain): On THEMIS, the user can calculate locally the BAT rewards based on the state of the BBA, which accounts for the number and type of ad interactions over time. In addition, the user must prove that i) the reward was calculated based on a signed and correct BBA and ii) the reward calculation is correct. This can be achieved through a zero knowledge (ZK) scheme that allows Brave and/or a smart contract to verify that the reward calculation claimed by the user is correct. Many teams focused on proposing ZK schemes that are efficient to prove on the client-side and cost-efficient to verify on-chain at scale. Teams such as Aztec, O(1)Labs, StarkWare, and ZeroPool have submitted proposals of new schemes to prove and verify the reward computation in THEMIS.
3. On-chain scalability: The final step of THEMIS is to verify reward proofs on a blockchain and proceed to the reward payments if the reward calculation is valid. Several teams showed how their L1 can help THEMIS to scale and achieve low-cost computation and transactions. We had proposals from teams such as Ava Labs, O(1)Labs, NEAR protocol, SKALE, Parity and Polkadot  and Solana to run the on-chain computation and payments for THEMIS.

Submission Summary by the Teams

We now give a high-level summary of all the RFC&C proposals submitted by the teams. You can find the full submissions in the RFC&C github repository. 

Ava Labs: The Ava Labs team proposed a protocol where the reward state and computation are implemented by L2 off-chain using StarkEx’s STARK scheme with proof batching. The reward proofs are then verified on-chain using Avalanche’s C-Chain. In addition, the reward payouts are processed on the C-Chain due to its low gas prices compared to Ethereum. Based on estimates, the combination of StarkEx (and perhaps other ZK schemes) and C-Chain proof verification achieve the scalability and price requirements for THEMIS. The first stage of the proposed scheme is similar to that of the original THEMIS protocol, where Brave issues and updates the BBA state of the ad interactions of users across rewards. The proposal suggests to exchange the SQS-EQ commitment for a cryptographic token signed by Brave that is pairing-free, in order to reduce the complexity of computing the reward proof using StarkEx.

Key figures: StarkEx is benchmarked to handle 3000 transactions per second, which is significantly more than the 20 transactions per second required to serve 5M concurrent users. It allows, at the extreme, THEMIS to support a rewards request every 28 minutes from every user in the system. At current $AVAX prices, each reward calculation proof would cost about $0.005.

Aztec: 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 privately. 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 proves 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-verify 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. The 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.

Key figures: 5-10s sec proving time (client-side). Max 1024 proofs aggregation (degrees of magnitude more expensive than Mina); ≈ 2h for building 896 tx rollup (UltraPlonk will be 2.5-3x faster)

IMDEA Software Institute: The IMDEA crypto research group submitted a proposal for a cryptographic scheme that allows the clients to swap the bilinear-friendly commitments of the BBA for a bilinear-free commitment. The commitment swap will make the reward proof generation, verification and batching more resource efficient, since to use bilinear-friendly curves in a ZK circuit is expensive. The proposal consists of a non-interactive Σ-protocol to allow the user to prove that two vectors with multi-Pedersen commitments in different groups contain the same values. The non-interactiveness is achieved using fiat-shamir heuristics, to prove equality between two different groups. The near-term goal is to work on a paper and publish it in a cryptography venue.

NEAR & ZeroPool: The ZeroPool and NEAR teams submitted a joint proposal. Their proposal consists of replacing the BBA-based design with a scheme similar to the ZCash transaction model, where each ad interaction results in a randomized proof that allows the users to request the payment later for the ad interaction in a privacy-preserving manner. For each ad interaction, the user and Brave interact through an anonymous channel, which results in a signed transaction receipt per ad interaction that can be exchanged for BAT. This interaction flow is similar to the current Privacy Pass-based protocol used in Brave Ads. The transaction receipts are then batched together using ZeroPool rollups, which guarantees the privacy of the user interaction with ads. They suggest that the rollup data can be made publicly available either on a PoA L2, on an optimistic validium or optimistic rollup with on-chain availability. The advantages to using ZeroPool payment channels are that the user can use the earned BAT without exiting the payment channel (e.g. for tipping creators, etc). The proposed scheme includes fraud-proof exit mechanisms for the payment channel. Finally, NEAR L1 could be used for maintaining the data publicly available with reasonable costs and, in addition, NEAR could be used as a scalable and cost efficient settlement layer for Rewards.  

Key figures: 1907ms and 6915ms time to generate proofs by Brave and on the client, respectively; 0.0001 – 0.0005 $N cost per transaction in NEAR (estimate, and it can be further optimized);~2TB space for data availability annually.

O(1) Labs: The 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 are within the requirements for THEMIS in terms of computation costs and bandwidth.

Key figures:  1 sec proving time (client-side). 1kB on-the-wire accumulator state; 1ms * N + 10ms proof verification per proof verification off-chain; No limitation in increasing the number of attributes, low bandwidth requirements as number of attributes increase.

Parity, Polkadot & Plasm: The Parity and Plasm teams submitted three proposals that leverage Substrate and the Polkadot ecosystem to implement THEMIS. Proposal 1 consists of using Substrate to verify BBA proofs and parallelize reward verifications of pairing processes of the BBA. In addition, proposal 1 suggests implementing Aztec 2.0 scheme on Substrate to achieve privacy-preserving payments with lower costs and higher scalability than currently enabled by Ethereum. This solution leverages Polkadot as the data availability layer and computation layer for reward proof verification. Proposal 2 consists of using one-way HTLC payments channels with ZK proofs to cut costs associated with reward payments. In this scheme, advertisers and/or Brave deposit BAT on the campaign payment channel with ZK-UTXO and set the HTLC payment to be dependent on submitting a valid proof of reward calculation. In addition, this proposal relies on fraud proofs to prevent double rewards attempts. Finally, the 3rd proposal consists of introducing TEE on the server-side to prevent malicious ads provider (i.e. Brave). In all proposals, both Substrate and Polkadot have a key role in ensuring that THEMIS runs correctly, at scale and in a decentralized manner.

SKALE: The SKALE team proposes using their PoS blockchain to run the on-chain reward proof verification and rewards payouts. The on-chain computation and transactions required by THEMIS run on a zero cost Proof-of-Stake chain distributed across multiple nodes, each running containerized EVM. The SKALE team proposes to store data resulting from the THEMIS protocol on the SKALE Network, which would remove the per transaction gas cost, remove the requirement for batching data prior to storing on chain, and provide fast finality in less than 3 seconds per transaction. In addition, there exists an Ethereum bridge for integrating SKL with the current ERC-20 BAT token.

Key figures: Depending on the network’s configuration, the chain could achieve 16 TPS, 125 TPS or 2000 TPS with costs of 600 SKL, 4,625 SKL, 74,000 SKL per year, respectively.

Solana: The Solana team proposes using the Solana blockchain to run the on-chain proof verification phase. In addition, Solana’s team proposes to replace the current BBA-based scheme for a Bulletproofs proof scheme, which would remove the need for pairing-based curves in THEMIS. This enables cheaper and more performant ZK proof generation and on-chain verification. Solana L1 can, theoretically, perform 270K reward proof verifications per second when using the proposed Bulletproofs proof scheme. These numbers are way above the requirements for THEMIS and Brave Rewards. Thus, using Solana as the verification layer for THEMIS means that there is no requirement for proof batching and, perhaps, relying on L2 schemes altogether ー instead, the reward verification can be achieved using Bulletproofs to prove the correctness of the inner product necessary for the reward calculation and each proof can be submitted directly by the user to L1 without aggregation. In addition to providing the L1 layer for verifying reward requests and to perform reward payouts, Solana could implement the secure broadcast encryption channel necessary to implement the verifiable analytics for THEMIS, due to its low costs and high throughput network.

Key figures: Solana validators can theoretically process ≈ 270k payout verifications per second; ≈ 4 on-chain reward verifications per second without batching;

StarkWare: The StarkWare team proposes to replace the pairing-friendly based BBA with a ZK proof. The circuits can be easily developed using the Cairo language. The commitment of the ad interaction state is encoded as a single tree root and each of the leaves encodes the number of interactions with the ads. The interaction vector is represented by the leaves of the tree. At every ad interaction, the user proves to Brave (through an “anonymous channel”) that the new tree state is the correct state considering a previously signed tree by Brave. Once Brave validates the proof, it signs the new merkle root and returns it to the user. The user may generate and batch many update proofs. Similarly, the reward calculation proof is generated using Cairo by the client and it consists of proving the correctness of the inner product of the leaves from a signed merkle tree commitment that the user maintains. Note: StarkWare did not submit a formal proposal, and the information provided in this summary and in the RFC&C repository is the output of back-of-envelope calculations and discussions between the teams.

Key figures: 2-10s sec proving time (client-side). 60kB for 10 on-the-wire accumulator updates; 120K updates could be batched in a single STARK proof; The batch proof would take a few minutes in an amazon machine; Estimate of gas cost per transaction is 50 gwei/update

What’s Next for THEMIS

Based on the quality of the RFC&C proposals and the work we did with the different teams, we consider that the event was very productive and useful. A great deal of the event’s success was due to the stellar teams and their commitment to pushing the Web3 ecosystem forward! We look forward to continuing to work with the teams on THEMIS and other relevant projects in the future, specially around the Brave Wallet, BAT utility, the BAT DEX Aggregator, and privacy-preserving P2P transaction workstreams recently announced in the BAT 2.0 roadmap.

As for THEMIS, we’ve entered a new phase of development: currently the team is focused on formalizing, developing and productizing the protocol, as shown below:

Development Phase	Goals and Deliverables
Phase 0  Warm up	a. Cryptographic formalization of the BBA and ZKP scheme; b. Security review of the scheme and infrastructure integration;
Phase 1 Privacy-Pass scheme replacement	a. BBA implementation; b. Reward calculation and proof generation; c. Off-chain reward proof verification; d. Replace the current Privacy-Pass protocol with THEMIS in Brave Ads;
Phase 2 On-Chain computation	a. On-chain reward proof verification

Conclusions

This post is the last post in a series that covered the ongoing work on the THEMIS RFC&C event. We outlined the submissions by the teams who participated and discussed how the proposals could be integrated in THEMIS. In addition, we’ve outlined the next steps towards productization of the THEMIS protocol.

Once again, we wanted to express a warm thank you to all the teams who participated, Ava Labs, Aztec, IMDEA Software Institute, NEAR protocol, O(1)Labs, Parity and Polkadot, SKALE network, Solana, Stake Technologies, StarkWare, and ZeroPool, and every other participant that helped make the event a great success.