---
title: O1Labs - server-side costs
tags: rfcc, themis, o1labs
---
**Context**: This document estimates the infrastructure costs required to run THEMIS instatiated with the [O(1) Labs scheme](https://hackmd.io/@izzy/rJApOn5zu). The on-chain reward verification is out of scope of this document -- costs and potential infrastructure cost savings associated with running the reward verification on-chain will be considered on another document.

### Document outline
- [2nd Round of Feedback](https://hackmd.io/1fZEaydPTlmL0t01jOoJ0g#2nd-Round-of-Feedback)
- [1st Round of Feedback](https://hackmd.io/1fZEaydPTlmL0t01jOoJ0g#1st-Round-of-Feedback)

## 2nd Round of Feedback

The following tables consider the cryptography and engineering (batching operation) optimized code of the PoC implementation.

**Accumulator Issuance**
| | 1 user | 100 users | 1000 users
| --------|--------|--------|--------|
| 1 accumulator |6ms |1.05ms | 0.82ms |

*Table 1. Operation costs per user when issuing 1 accumulator for 1, 100 and 1000 batches of users.*

**Accumulator Update**
| | 1 user | 100 users | 1000 users
| --------|--------|--------|--------|
| 1 ad update | 3.7ms | 1.05ms | 0.92ms |
| 10 ad update | 3.3ms (0.33ms/ad) | 0.95 ms (0.095ms/ad) | 0.96ms (0.0096ms/ad) |
| 30 ad update | 3.3ms (0.11ms/ad) | 0.95ms (0.0032ms/ad) | 0.82ms (0.0027ms/ad) |

*Table 2. Operation costs per user when updating 1, 10 and 30 ads for 1, 100 and 1000 batches of users.*

**Reward Verification**
| | 1 user | 100 users | 1000 users
| --------|--------|--------|--------|
| 1 ad update | 2.83ms | 0.875ms | 0.8ms |

*Table 3. Operation costs per user when verifying 1 reward proof for 1, 100 and 1000 batches of users.*

**Estimates per user for monthly max request flow**
We assume that, each month, a user requests one accumulator issuance, requests 150 ad updates and, finally, requests one reward verification. Given the figures in Tables 1, 2 and 3, the processing time necessary for handing the user requests are:

- **Users requests accumulator update with per ad interaction (i.e no batching)**

i) No user batching
`6 + 150 * 3.7 + 2.83ms = 563.83ms /user`

ii) 100 user requests operation batching
`1.05 + 150 * 1.05 + 0.875ms = 159ms /user`

i) 1000 user requests operation batching
`0.82 + 150 * 0.92 + 0.80ms = 138ms /user`

- **Users requests accumulator update with 10 ads**

i) No user batching
`6 + 15 * 3.3 + 2.83ms = 58.3ms /user`

ii) 100 user requests operation batching
`1.05 + 15 * 0.95 + 0.875ms = 16.176ms /user`

i) 1000 user requests operation batching
`0.82 + 15 * 0.96 + 0.80ms = 16ms /user`

- **Users requests accumulator update with 30 ads**

i) No user batching
`6 + 5 * 3.3 + 2.83ms = 25.33ms /user`

ii) 100 user requests operation batching
`1.05 + 5 * 0.95 + 0.875ms = ms 6.675ms /user`

i) 1000 user requests operation batching
`0.82 + 5 * 0.82 + 0.80ms = 5.72ms /user`

---

## 1st Round of Feedback
For the infrastructure cost we take into consideration how much time to does the baseline machine (`2.4 GHz Intel Core i5, single-threaded, 16 GB memory`) takes to compute the relevant cryptographic operations. We use the baseline machine to compare the different THEMIS schemes and extrapolate costs.

| | Time to init accumulator `issue()` | Time to update accumulator `update()` | Time to verify reward calculation `verify()`
| --------|--------|--------|--------|
|[PoC implementation](https://github.com/imeckler/bba) |17ms |13ms |13ms |
|Optimized (4x faster)|4.25sm |3.25ms |3.25ms |

*Table 4. Operation costs (time, ms) per core*

### System assumptions
- One accumulator per user;
- Each accumulator is valid for a period of 1 month (epoch);
- Each user interacts with up to 150 ads per epoch;
- The reward calculation and settlement happens at the end of the epoch;

### Time to compute ad interactions per user/epoch

When estimating the time to update the accumulator, we assume the computation time to update a single polynomial is the same as computing the updates of `n` polynomials;

- *(optimized, single ad update)*: `4.25 +(150 * 3.25) + 3.25 ms = 453.5 ms`
- *(optimized, batch update size 10)*: `4.25 +(15 * 3.25) + 3.25 ms = 56.25 ms`
- *(optimized, batch update size 30)*: `4.25 +(5 * 3.25) + 3.25 ms = 24 ms`

### Questions/ Discussion

#### Tainted accumulators

For reputation/antifraud purposes, we need to embed 1 bit of private metadata in the accumulator. The goal to to encode 1 private bit that represents whether the user requesting the issuing is reputable or not, based on our internal privacy-preserving reputation system.

This private bit needs to be checked when the BBA is updated, to make sure we don't report ad-click/interaction to advertisers when the accumulator is non-reputable at update time. In addition, we’d like the bit to be encoded in the reward calculation proof, to make sure we don't pay rewards to non-reputable users. The user should not be aware of the state of the bit at any step of the protocol.

#### Storage requirements

In the off-chain mode, Brave needs to store the set of `id` of spent accumulators. In order to save storage costs and speed up processing requirements we looking at using bloom filter to store spent `ids` and check for set membership. The problem with this approach is that false positives are critical -- users won't be able to be rewarded as their accumulator is considered spent.

#### Expiring accumulators

Instead of using bloom filters, we can reduce the set of `ids` to store if the accumulator (or the `id` itself) had an expiration date. There are a couple ways to implement this:
- if an `id` was a scalar which `n` bits would encode the month/year representing the epoch while the accumulator is valid;
- encode the valid epoch in one of the accumulator parameters (this would probably be more expensive when generating/verifying the reward proof, as the user would have to prove that the accumulator e valid).

Both options above would allow Brave to drop the accumulator `ids` from the double-spending protection set once they've been expired.

**Questions:**
- Can we assume that batch update of `n` polynomials takes the same server-side resources as a single update? If not, how to factor in that in the cost calculations?
- How do you estimate that the tainted token feature would impact token issuance, update and reward verification costs? (compared to Table 1.)
- Could you elaborate where the 4x performance improvements come from?