---
title: Brave - RFC&C submission reviews and notes
tags: rfcc, themis
---

# RFC&C submission reviews and notes

### Team submission repo

**L2 layer**
- [O1Labs submission](https://hackmd.io/@izzy/rJApOn5zu)
- [The BBA implementation](https://github.com/imeckler/bba)
- [Q&A v2](https://docs.google.com/document/d/1bQSrfDPYpNKxCYvetnIXKY2JHApIzJa-OLf6irLVD9g/edit)
- [AZTEC submission](https://hackmd.io/@jaosef/HyY2lKI-O)
- [AZTEC Q&As](https://hackmd.io/OR_Tt9qjQ6S-gXiHx8NhQQ)
- [StarkWare submission and Q&As](https://docs.google.com/document/d/1eKPQ5Y9urIQ3VHfhOXqyupBf_GtFwDZDjd0Xzol2-QY)

**L1 layer**
- [NEAR protocol + ZeroPool submission](https://hackmd.io/@zthUvKNmRheIOgHHOGf1fA/rJf273n4u)
- [PoC repo](https://github.com/zeropoolnetwork/libzeropool)
- [Solana submission](https://drive.google.com/file/d/1aEX_7G8oCgEwCkGp8jnUsTA_q2zoZCRa/view?usp=sharing)
- [THEMISv2 submission draft]( https://docs.google.com/document/d/1EKzestOCp2O4qDeI-p7yvlHrTmzR_f5jxNmN8VlJWfs)
- [THEMISv1 upper bounds](https://docs.google.com/spreadsheets/d/1-luZUGtAeivfQQJzwhV4RJaws1WukRPldReIW1TcwXM/edit#gid=0)
- [THEMISv1 benchmarking on Solana](https://docs.google.com/document/d/1fLhvHxXzNxUZy7bn6jAWa_7FOZQ9o3D28wWPhziBLSc/edit)
- [Solana fees for Brave workloads](https://docs.google.com/document/d/1mqxQ-acas17L29-9hiyTKxwGO7umNiBVQEKWGuySfpY/edit)
- [THEMISv1 implementation on Solana](https://github.com/solana-labs/solana-program-library/tree/master/themis)
- [Parity + Plasm submission](https://drive.google.com/file/d/1R523_8evyNd2TvsxqYJagmRnRBLWY42X/view?usp=sharing)
- [draft/initial ideas](https://hackmd.io/eKQKbsNxSdmhTk5pz3xH9A)
- [Plasm follow-up](https://hackmd.io/RLOgGcRiRA2766Mfl1swzQ)
- [Ava submission](https://gist.github.com/tyler-smith/5a0c5362c443d0c0a75ee8e160963806)
- [Ava sketch v1](https://gist.github.com/tyler-smith/69fdfebbb68eeefd41c598227716446c)
- [SKALE submission](https://hackmd.io/EM429T5kRdyoaGI99hQA6Q)

**Researchers/others**
- [IMDEA submission](https://drive.google.com/file/d/1-5N0Kpqpe84l4Z1Apj40dq4IXqRPxem7/view?usp=sharing)
- [eV submission](https://hackmd.io/4XaZnrs4T7SuvlADEdXOYQ)

## RFC&C submission reviews and notes

**L2 Summary Table**

| 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)||

### O1Labs

The suggested protocol is based on THEMIS, but the pairing-based BBA is replaced by a ZKP-based BBA which leverages a roll-up system to batch proofs from multiple users. In addition, we can use Mina as the payout layer for lower on-chain costs and to allow users to verify the on-chain payments without relying on a 3rd party.

- ZK-Rollup based protocol in which Brave operates the rollup prover. No privacy sensitive data is handled by this party, so any party could participate as a rollup prover (e.g. foundation);
- If the payout L1 is Mina, resource-constrained users can verify the correctness of the payout by checking one SNARK only, without the need to rely on 3rd parties.
- The pairing-friendly based BBA are replaced by a BBA constructed with Pasta curves.
- The "opening" step of the BBA is replaced by a ZKP proving that the user knows an inner product of the BBA state with the policy vector that is a particular public value (the BAT reward to receive).
- For batching the proofs, [O(1) Labs’ pickles library](https://minaprotocol.com/blog/meet-pickles-snark-enabling-smart-contracts-on-coda-protocol) implements the "wrap" and verifier circuits for merging the proofs. The programmer only needs to specify the application logic.

**Questions**
- Could you elaborate why the scheme relies on Lagrange polynomials -- I believe this is due to how PLONK encodes the program and its constraints?
- Is there any mechanism to prevent spending of the BBA update request and the proof of reward?
- Could you briefly explain our add references explaining why the scheme does not require a trusted setup?
- In the BBA update proof system, you say "Verifier efficiency. Somewhere in the neighborhood of 1ms per proof, plus 10ms per batch." Does that mean you are considering batching BBA update proofs? If so, would those proof happen at a user-level (i.e multiple update from the same user) or at the service-level (i.e. batching multiple update proofs from multiple users)?
- Is there any open source documentation of the Pickles SNARK library?
- Do you have a ballpark of how cheaper would be the batch proof verification in Mina compared to the numbers for Ethereum? (roughly)
- We've implemented a [POC of the pairing-friendly BBA](https://github.com/brave-experiments/sps-eq/blob/main/examples/bba_verification_example.rs). Is there any place where we could check an example of a Snapp similar to needed for THEMIS?
- What would the "road to production" look like? I.e. which libraries/frameworks would you recommend to develop the proof verifier, circuits, smart contracts? Are they available already? Are there any required components that are not live yet?

### AZTEC

The suggested protocol restructures the BBA encodes it as a merkle tree. The depth of the merkle tree influences the number of interactions we can store in the BBA (e.g. $depth = 10 ==> 2^{10} = 1024$ advertisers). Each BBA update is a PLONK proof (as in O(1) Labs' submission) generated by the user. The on-chain verification is performed using TurboPLONK over batched proofs. The verifier smart contract mints a AZTEC note that allows users to witdraw BAT from their on-chain proof verifications.

- The protocol scheme consists of 3 different circuits: the i) ad interaction circuit (to update the BBA); the ii) reward circuit (to calculate reward and prove its correctness); and the iii) batching circuit.
- In order to mint an AZTEC note after the reward calculation was verified on chain with lower gas costs, we assume it is possible to re-reploy (or in parallel?) a BAT token smart contract.

**Questions**
- Double speding protection (we've discussed about this before, but just making sure we are on the same page here):
- BBA update: Brave checks if Nullifier has been signed. If not, then no souble spending;
- Reward: Brave keeps a list of all signed nulifiers. Brave needs to check if the nulifier in the request has been used before.
- Do you have any example of the smart contract that would improve the gas efficiency of withdrawing rewards?
- What would the "road to production" look like? I.e. which libraries/frameworks would you recommend to develop the proof verifier, circuits, smart contracts (e.g. which libraries would you recommend to develop the native prover system and the batcher system)? Are they available already? Are there any required components that are not live yet?

### StarkWare

The proposed scheme replaces the BBAs with a proof generated by Cairo. The commitment of the state is encoded as a single Merkle tree root, where each of the leaves on the tree encodes the number of interactions each ad had (the interaction vector is represented by the leaves of the tree).

- When initializing, the root of the Merkle tree is initialized with 0 and signed by Brave;
- At each ad interaction, the user:
1. Updates the state of the tree corresponding to the event;
2. Generates a proof of correct state update with that proves the statement $${(T): Signature.Verify(T) = true Tree.Update(T, adi) = T'}$$
Where $T$ and $T'$ are the old and new merkle tree roots, respectively.
3. Sends the proof, $T$ and $T'$ to Brave alongside the event (ad interaction) through an "anonymous" channel.
- Brave checks the proof and, if it validates, signs $T'$ and sends it back to the user.
- The scheme above is optimized for batching reward proofs.
- In order to avoid double spending, Brave needs to maintain extra state (what, exactly?). The proof to avoid double spending should not increase proving time/bandwidth considerably.

**Questions**
- Re: batching of the proofs - is it correct to say that it should take about 2-10s to generate a prove of 10 updates on the client side? And a size of <60KB per proof? In production, this proof would be generated by the user daily.
- As far as we understood, to verify a batch proof would take a few minutes in an amazon ec2 instance. How big would that batch proof be? i.e. are we talking about a few minutes to verify a batched proof of 10000 proofs, or a few minutes to verify a batch with 10 proofs? We'd expect each user to send a batch proof of 10 proofs per day. Can we estimante how much compute time would take for Brave to verify the one batch proof of 10 proofs for 1M users/day on an Amazon instance (how beefy?)
- In order to prevent double spending Brave needs to maintain an extra state. What would that state be exactly?
- The scheme that we have been discussing refers to the update of the merkelized state of ad interactions that each user keeps locally and commits to Brave every day. This is the first part of THEMIS. The second part consists of the user calculating the BAT rewards based on the latest merkelized state and proof its correctness to Brave. After the reward is calculated and the proof has been generated, the user can request X BAT and Brave can prove its correctness. Eventually we'd like to batch thousands of proofs of reward calculation from multiple users and verify it on L1. How could STARKs and Cairo help here? Do you have any estimates with regards to the proof generation/batching/verification and L1 costs of such a scheme?

### Solana

Solana claims that their high throughput and low tx cost blockchain can be leveraged as a messaging bus between the users and Brave to implement the TAA broadcast channel. In addition, verifying the reward proofs in Solana does not require batching, given its scalability and low costs.

For the TAA, each ad campaign (or epoch for many ad campaigns) can be maintained by an account. Each account receives the encrypted requests from users. Once the ad campaign (or epoch) ends, it is trivial to decomission the data accumulated by the account over time.

- In Solana, transaction fees are not a significant profit source for validator operations, so there is lower pressure to increase the tx fees; "To find lower fees elsewhere would suggest that either hardware is being used more efficiently or that the network is being artificially subsidized."
- In order to enable proving proofs based on bilinear-friendly curves on Solana's VM, the Solana team can add new “runtime builtins” (or what Ethereum calls “precompiles”);