owned this note
owned this note
Published
Linked with GitHub
# 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.
``` python
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
``` python
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
```solidity
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 |
``` python
def commit_transfer(new_root, transactions):
...
```
## Transfer fraud proof
``` python
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.
``` python
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 |
``` python
def commit_execute_burn(txs, new_root):
# same as above commits
...
```
## Monthly Burn execute fraud proof
``` python
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.
``` python
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.