Notes/Questions AZTEC submission

--- title: Notes/Questions AZTEC submission tags: rfcc, themis --- #### Is the nullifier related to the user secret key? Or instead related to the hash root? My concern is whether a nullifier is supplied for each updated merkle root? A: The nullifier is related to the hash root. Each user will posess a 'nullifier secret key' (this can be the same as their secret key), and the nullifier will be a hash of [merkle tree root, user secret key]. For the reward circuit, only the nullifier of the complete tree being opened will need to be added into the reward circuit's 'nullifier tree' There was an error in the spec we sent you regarding the update proof. For the update proof, Brave would need to sign against the old *nullifier* and not the old tree root. This maximally preserves privacy; if Brave receives multiple requests to sign BBA nullifiers they cannot determine which users the requests come from by examining the public inputs. Assuming Brave caches a list of all nullifiers they have signed over, double spending is prevented by never signing over a nullifier more than once. #### 896 txs per rollup --- Does this consider performing the payment to each user? Yes it does #### What is the cost associated with computing the batch proof? The batch circuit will have a similar complexity to our current rollup circuit. It currently takes us 4 minutes to aggregate together 28 transactions into a rollup. These 28-tx rollups proofs are constructed in parallel. Once these proofs are made, we aggregate them together into a size-896 rollup. This takes 4 minutes. This is using TurboPlonk, however. Once we transition to UltraPlonk these proving times will be 2.5x-3x faster. (Still possible to optimize it) #### What about having in each merkle tree, instead of a pedersen commitment of ad_interaction, the pedersen commitment of the number of interactions . This way we would be happy with a merkle tree of depth 2^10, and the proof update would be “I’ve updated leaf at position n by one unit”. I don’t know if we can exploit the additive homomorphic property. Can I clarify what the desired outcome of this change would be? If I understand correctly, the BBA tree changes from an append-only UTXO style tree (1 leaf per ad interaction) to an account-based tree, where each position maps to a given ad provider and the leaf value is a count of the number of ads clicked on. The outcome is that the tree size is bounded by the number of advertisers on the platform and not the maximum number of supported user interactions (the former being smaller than the latter), is this accurate? If the circuit validates that a leaf value only increases by 1 then it should be possible to prevent the circuit from leaking information to Brave. However, the position of the leaf being updated can't be exposed to Brave without leaking information about which advertiser owns the ad the user clicked on. Is this information already sent to Brave as part of authorizing a BBA update? We might be able to change the circuit to avoid broadcasting position `n` though. If the proof merely says "I’ve updated a leaf at a hidden position one unit”, would that be sufficient? It depends on whether Brave needs to link a BBA update to a given advertiser. ### Errata I wanted to highlight that I think I made some errors when estimating how long computing a reward proof will take the user. I underestimated the likely proving times for a user using WebAssembly to compute a proof. A short analysis is below: The cost is largely determined by the size of the BBA tree. The user will need to perform 2 512-bit pedersen hashes per leaf to completely open the tree. Each 512-bit hash will cost ~90 constraints (the cost is lower than the interaction circuit because we can use larger lookup table for larger circuits). Rough costs for various tree sizes are below: | Tree size | Pedersen hash gate cost | Estimated prover time (wasm) | Estimated prover time (native) | |---------------|-------------------------|------------------------------|--------------------------------| | 1,024 (2^10) | 184,320 (2^18) | 20-40 | 3-5 | | 2,048 (2^11) | 368,640 (2^19) | 40-80 | 5-10 | | 4,096 (2^12) | 737,280 (2^20) | 80-160 | 10-20 | | 8,192 (2^13) | 1,474,560 (2^21) | 160-320 | 20-40 | | 16,384 (2^14) | 2,949,120 (2^22) | 320-640 | 40-80 | Ideally the reward proof uses a native prover built into the Brave browser, the WASM performance times are quite long. The tree size is shrunk to 2^10 this N.B. The reason the user has to open the complete tree is so that they can compute the number of tokens they have earned, by combining each ad interaction with a fee read from the fee schedule. When does this linking to the fee schedule need to occur? If we moved the fee schedule into the interaction circuit, the user could keep track of a running total of tokens they have earned, and there would be no need to open the BBA tree when computing the reward proof. In fact, if a running total of tokens earned is tracked in the interaction circuit, it might be possible to remove the BBA tree entirely. I'm happy to discuss this further on the call.