# Reddit Hubble RollApp

## Intro

Trying to architect an optimistic rollup to make it efficient to airdrop / transfer tokens.

I am assuming 4,294,967,296 unique accounts. If it's less than this we can reduce costs. We can also have a system that grows in gas costs as new users join.

There might be some mistakes in the calculations / estimates so please take it more like a sketch of what is possible, how it is possible, and how much I think it might cost.

Optimistic rollup fraud proofs come in two parts

1. We validate that the witness the person claiming a fraud has given
2. Then we validate the state transition that was claimed by executing it using the witness that we have already proven correct.

## Airdrop Tokens

In the competition's requirement,

1. Every month Reddit proposed a Mint & distribution.
2. Subreddit approves the Mint & distribution.

The two approvals can be aggregated into a BLS signature. We also call the Mint & distribution airdrop for simplicity.

### Data Commitment

We create the data that is used for our fraud proof
| Variable | Data | Note |
| -------- | -------- | -----|
| New Merkle Root | 256 bits | Shows the new state of the system |
| Signature (bls)| 512 bits | This is Reddit's signature to prove they agreeded to this state transition|
| token | 16 bits | The token that is being airdropped. Must be the same for every airdrop in batch |
| airdrop_list[0].to | 32 bits | Who we are sending to|
| airdrop_list[0].amount | 32 bits | How much we are sending|

> TODO: BLS signature is 768 bits

$$
\text{total_bits} = 256 + 512 + 64n
$$
Where $n$ is number of airdrops

To convert this to gas it costs 16 gas per byte of data (https://eips.ethereum.org/EIPS/eip-2028) which is 2 gas per bit.

$$
\text{gas_data} = 2 \times (256 + 512 + 64n) \\
\text{gas_hashing} = n(30 + 6(64/8))
$$

Plus something else for storage, for which I am going to ignore the cost for now as it's getting pretty complicated.

def commit_airdrop(new_root, sig, message, airdrop_list):
    message = 0
    # here we commit to the witness publicaly so anyone can 
    # recreate it. 
    for drop in airdrop_list:
        # seed_message contains the recipients and their
        # amounts
        # we have to make sure this is put on chain
        message = hash(drop , message)
    new_block = block(root, new_root, sig, message)

### Fraud Proof

def fraud_proof_airdrop(airdrop_list, block_id, witness):
    # check signature
    if(!verify(sig, message)):
        slash(block_id)
        
    tmp_message = 0 
    # Check the correct airdrop_list was passed
    for drop in airdrop_list:
        tmp_message = hash(drop, tmp_message)
    # if the witness is not correct return 0 
    # don't slash as the winess must be provided by 
    # user who we don't trust
    if (tmp_message != message):
        return(0)
    tmp_root = block.mr
    # Now actually update the state    
    for i, drop in enumerate(airdrop_list):
        # load recipient into memory
        recipient = merkle_proof(drop.to,witness[i],tmp_root)
        # check token make sure I am not adding moons
        # to a brick leaf. 
        if (token != recipient.token):
            slash(block.block_id)
        # Increase the recipient's balance
        recipient.bal += drop.amount
        # note to deal with multiple tokens
        # I need to do a token check here. 
        # save the recipient's leaf back to memory
        tmp_root = merkle_root(recipient, witness[i])
    # If this not the same root it's fraud so slash
    if (tmp_root = block.new_root):
        slash(block.block_id)

Estimating the gas cost here is a little more difficult.
So we have the same gas cost as the commitment

$$
\text{merkle_proof_costs} = n \times (2(32(30 + 6(512)))) = n \times26496
$$

We also have to ensure that the fraud proof can execute inside 5 million gas. Just to ensure that if gas block limits fluctuate we can still execute fraud proofs.

You can see https://etherscan.io/chart/gaslimit that during DOS attacks in October 2016 it did fluctuate so we need to be aware and careful.

That means each batch should contain 180 transitions.

### Total gas cost and TPS for airdrop

$$
n = 180
$$

$$
\text{gas}_{\text{data}} = 2(256 + 512 + 64n) = 24000 \\
\text{gas}_{\text{hashing}} = n(30 + 6(64/8)) = 14000 \\
\text{total_gas_per_batch} = 24000 + 14000 = 38000
$$

total throughput per ETH block = 23684 airdrops per ETH block which is

We can then assume that fraud proofs will very rarely need to be executed because slashing makes it prohibitively expensive.

So our full throughput of the system is

$$
\frac{\text{gas_block_limit}}{\text{gas_per_batch}} \times n
$$

23684 / 13 seconds per block = 1821 airdrops per second.

Given current gas prices ($20\times 10^{-9}$ eth per block) the cost to fill a block is
$$
20\times 10^{-9} \frac{\text{ETH}}{\text{gas}} \times 10^{7} \text{gas} \times 200 \frac{\text{USD}}{\text{ETH}} = 40 \text{USD}
$$
or
$$
40 / 1822 = 0.022 \frac{\text{USD}}{\text{Airdrop}}
$$

This is a very rough estimate as the ETH price moves a lot over time, so actual costs may vary.

Note: I can further reduce the cost if I have some more information about the to , amount of the airdrops. For example if you airdrop everyone 1 MOON then I can get rid of the amount field. I am sure there is some repetition here that I can take advantage of and compress :)

## Create Account

To airdrop token to users whose public key is not yet in the accountsTree, we need to
- add their public to the accountsTree, and
- create a empty leaf for them in stateTree

function createPublickeys(bytes32[] publicKeys) onlyReddit {
    for (_pubkey in publicKeys){
        Types.PDALeaf memory newPDALeaf;
        newPDALeaf.pubkey = _pubkey;
        accountsTree.appendLeaf(newPDALeaf);
    }

}

struct CreateAccount {
    uint256 toIndex;
}
function processBatch(txs, _to_pda_proofs, accountProofs) {
    for _tx in txs {
        ValidatePubkeyAvailability(
            _accountsRoot,
            _to_pda_proof,
            _tx.toIndex
        );
        ValidateAccountMP(_oldBalanceRoot, ZeroMP);
        ValidateAccountMP(_newBalanceRoot, accountProofs.to);
        // check nonce ==0 and bal == 0
    }
}

## Transfer commit

User can transfer amount of MOON to other user.

| Name | Bits | Note |
| ---------------------- | -------- | ----------------------------------------------------- |
| new_root | 256 bits | The merkle root after this state transition |
| Signature (bls) | 768 bits | All transactions' signatures are aggregated here |
| transaction[n] | | List of transactions |
| transactions[n].to | 32 bits | recipient of funds |
| transactions[n].from | 32 bits | sender |
| transactions[n].amount | 32 bits | the amount sent |
| transactions[n].fee | 16 bits | fee for transactions |

def commit_transfer(new_root, transactions):
    ...

## Transfer fraud proof

def fraud_proof_transfer_sig(batch_no, i, witness):
    # point a signature to me that is wrong
    sig = batches[batch_number].sig

    # load transaction
    tx = merkle_proof(i,batch[batch_no].root, witness[0])
    # load public key
    pub_key = merkle_proof(i, batch[batch_no].accounts, witness[0])
    if !verify(sig, pub_key, tx.message):
        slash(batch_no)
    # note: its probably better to replace the weird hash 
    # list with merkle tree to reduce witness size

def fraud_proof_transfer(batch_no, wit):
    # we assume all sigs are correct as the fraud proof
    # above should take care of that. 
    txs_commit = batch[block_no].txs
    new_root = batch[block_no].new_root
    tmp_root = batch[bloc_no].old_root
    tmp_fee = batch[bloc_no].fee_root_old
    fee_root = batch[bloc_no].fee_root_new
    tmp_withdraw = 0
    withdraw_root = batch[block_no].withdraw_root
    # check witness is correct 
    tmp_txs = 0
    for tx in wit.txs:
        tmp_txs = hash(tx, tmp_txs) 
    if (tmp_txs != txs_commit):
        return 0
         
    for i, tx in enumerate(wit.txs):
        # load sender from memory
        send= merkle_proof(tx.from,tmp_root,wit[i].send)
        # check underflow here
        send.amount -= tx.amount
        # update sender leaf
        tmp_root = mr_update(tx.from,sender,wit[i].send)
        # for withdraw we burn funds. This makes sure we
        # cannot unburn burned funds. 
        if (tx.from == 0):
            slash(block_no)
        # if not withdarw
        if (recv != 0):
            # load recipent from memory 
            recv = merkle_proof(tx.to,tmp_root, wit[i].recv)
            recv.amount += tx.amount - tx.fee
            # check token is the same
            if (recv.token != sender.token):
                slash(block_no)
            tmp_root = mr_update(tx.to, recv, wit[i].recv)
        #else is withdraw
        else:
            tmp_withdraw.append(tx.from,tx.amount, tx.token)
            
        # nonce check to prvent replay attack
        if (send.nonce+1 != tx.nonce):
            slash(block_no)
        # load the fee 
        fee = merkle_proof(send.token,tmp_ff, wit[i].fee)
        fee += tx.fee
        tmp_ff = mr_update(send.token, fee, wit[i].fee)
    # finally check that the final root == the commited root
    if(tmp_root != batch[block_no].mr):
        slash(block_no)
    # check that the fee == calculated fee
    if(tmp_fee != fee_root_new):
        slash(block_no)
    # check that the withdarw root is correct
    if (tmp_withdraw != withdraw_root ):
        slash(block_no)

## Monthly Burn concent commit
Users want to burn x tokens per month in order to pay for their reddit gold services.

So they create a transaction that sets their leaf parameters

| var | size(bits) | note |
| -------- | -------- | -------- |
| signature| 512 bits| bls aggregated signature of all n users|
| user[n] | 32 bits | Which user is it|
| burn[n] | 32 bits | How much does the nth user want to burn|
| nonce[n] | 32 bits | Prevent replay|
| cancel_flag[n] | 1 bit| If this flag is set we subtract the burn[n] |

## Monthly Burn concent fraud proof

First we validate the signatures with the same fraud proof as the transfer signature.

def fraud_proof_concent_to_burn(batch_no, wit):
    #load user before
    old_root = batches[batch_no].old_root
    tmp_root = old_root
    new_root = batches[batch_no].new_root
    txs_root = batches[batch_no].txs
    tmp_tx_root = 0 
    for tx in wit.txs:
        tmp_tx_root = hash(tx, tmp_tx_root)
    if (tmp_tx_root != txs_root):
        # if the person claiming the fraud proof does not
        # give us the correct witness the the fraud proof 
        # should terminate without slashing.
        return(0)

    for tx in wit.txs:
        user = merkle_proof(tx.user, tmp_root)
        if tx.nonce != user.nonce:
            slash(block_no)
        if user.cancle_flag:
            user.burn += tx.burn
        else:
            user.burn -= tx.burn

        tmp_root = merkle_update(tx.user, user)

    if (tmp_root != new_root):
        slash(block_no)

## Monthly Burn execute commit

Then once a month we let the coordinator take money from each user and just destroy 99.9999 % the rest is a fee for them.

| var | bits | comment |
| -------- | -------- | -------- |
| user | 32 bits | which users get burned |

def commit_execute_burn(txs, new_root):
    # same as above commits
    ...

## Monthly Burn execute fraud proof

def frand_proof_execute_burn(batch_no, wit):
    old_root = batches[batch_no].old_root
    tmp_root = old_root
    new_root = batches[batch_no].new_root
    txs_root = batches[batch_no].txs

    txs_tmp = 0 

    for tx in wit.txs:
        txs_tmp = hash(tx, txs_tmp)

    if (txs_tmp != txs_root):
        return(0)

    for tx in wit.txs: 
        user = merkle_proof(tx.user, tmp_root, wit[i])
        # if the user gets burned twice in a month
        # slash the coordinator. once a month we 
        # update the monthly time stamp variable
        # in the smart contract which gets. 
        if user.last_burn == monthly_time_stamp:
            slash(batch_no)
        user.balance -= user.burn
        user.last_burn = monthly_time_stamp
        tmp_root = update_root(user, wit[i])
    # slash them if they did not commit to the correct
    # value
    if(tmp_root != new_root):
        slash(batch_no)

## Withdraw

To withdraw a user transfers their funds to a leaf that has no private key the 0 index. They can then access these funds in the smart contract after that batch has been finalized.

def withdraw(batch_id, sig, msg, destination, witness):
    # lookup the batch where we destroyed
    withdraws = batches[batch_id].withdraw
    assert(batch_id.is_finalized())
    withdraw = merkle_proof(i, withdraws, witness)
    msg = hash("withdraw to"+destination)
    assert(withdraw.sig.veirify(msg))
    destination.transfer(
        withdraw.token, 
        withdraw.amount, 
        withdraw.token,
    )

This costs

## Gas Cost Comparison

| Feature | Limit | Cost |
| -------- | -------- | -------- |
| Airdrop | 1800 tps | 0.02 usd per tx |
| Withdraw | 25 tps | 0.15 cent per tx|
| trasnfer | ~1000's tps \* rough| | |
| burn | ~1000's tps \*rough | | |

## Conclusion

1. We can use optimistic rollup to make a Reddit system that is as scalable as needed.
2. Further improvements to eth1.x data availability will help this. Such as increasing the gas block limit or reducing the cost of putting data on chain.
3. There is a scalability lockin where transfers are cheap but withdraws are so expensive such that only very few users will ever be able to leave.
4. The optimistic rollup described here you can do everything that bitcoin can do but not much more. No rich programmability.
5. We can reduce the withdraw cost with mass migrations which would allow us to make more programmable optimistic rollups which would make the system more like Ethereum which is kind of Turing complete.