# Voting for Network Bootstrap Rewards

When a new network starts, it would not receive bootstrapping rewards directly. A Token weighted voting process is used to allocate rewards to an existing network. This ensures that bootstrapping rewards are provided to only networks that are beneficial to the health of the Marlin ecosystem.

We introduce a token weighted voting process that is verifiable on blockchain without locking stake of the users voting in the contract.

## Constants

Name Type Value
VOTE_RESULT_SUBMISSION_STAKE uint TBD
VOTE_RESULT_CONTRACT bytes32 TBD
VOTE_RESULT_SUBMISSION_PERIOD uint TBD
CHALLENGE_PERIOD uint TBD
MAX_CHALLENGE_COMPLETION_PERIOD uint TBD
MAX_COMPUTABLE_OPS uint 1000
COMPUTE_START_NUMBER uint 10**30
CHILDREN_PER_PARENT uint TBD

## Concepts

### Vote Merkle Tree

Vote merkle tree is a merkle tree created with hash of account that voted and the balance of the account at the vote counting block. After MAX_COMPUTABLE_OPS leaves, a calulation leaf is inserted that specifies the result of computation till the leaf before. MAX_COMPUTABLE_OPS is selected based on the maximum operations that can be safely computed on a smart contract.

The root of the vote merkle tree is submitted to contract when submitting the vote result proposal as it serves as commitment for the result provided. It can also be used by the contract to determine the correct computation of vote result and slash proposals that were incorrectly submitted.

This approach works on the principle that given enough publicly available data with the smart contract to verify a computation that can be computed by anyone in the network. There will exist atleast one honest actor in the network who will submit the correct result and it can efficiently verified that all other proofs are wrong compared to the correct result.

## Data Structures

### Type Aliases

Name Type Description Example
Level uint Level of merkle tree

### Vote

struct Vote {
bytes32 voter;
uint vote;
}


### ChallengeResponse

struct ChallengeResponse {
uint currentLevel;
uint index;
uint conflictType; // 1 - account 2 - calculation
}

struct LeafProofData {
bytes32 account;
uint balance;
bytes32[] proof;
uint challengePathRootIndexToProveAgainst;
}


## Storage

### Vote Merkle Tree

mapping(Level => bytes32[]) voteMerkleTree


### voteTreeLeaves

bytes[] voteTreeLeaves

uint noOfLeaves

### Response

ChallengeResponse response

## Stake Weighted Voting

### Reward Allocation Voting Contract

The first phase is the voting phase to determine if the relay network has to be bootstrapped with rewards. Voting contract will specify the network that is voted on and block at which voting will end.

### Voting

When the vote is sent to the smart contract, contract stores the vote and emits a log of the vote.

func vote(uint vote):
// 1- no 2 - yes
RewardAllocationVote::vote(vote).send(self.privKey);


### Start Vote Count

After the vote end block specified in the contract is over, anyone can send a transaction to the vote contract to start the counting period.

func startCountingPeriod():
RewardAllocationVote::setVoteCountBlock().send(self.privKey);


The transaction that starts the vote counting also creates a contract that accepts proposals for result of voting. Anyone can count the votes based on the account balances at the counting block in the contract.

Vote compute tree is created while counting votes. Anyone can send a proposal with the result and the root of vote compute tree by staking VOTE_RESULT_SUBMISSION_STAKE LIN.

If everyone acts honestly, there will be only one proposal. Malicious actors can challenge the correct voting result by staking LIN which will be slashed once the challenge is proved to be wrong or malicious actor gives up.

#### Vote Compute Tree

Vote compute tree is created from leaves which are calculated as hash of account of the voter appended to the balance of the voter at counting block with come compute leaves to verify computation results.

func createComputeTree(Vote[] votes, uint votingEndBlock):
voteTreeLeaves = leaves
noOfLeaves = leaves.length
voteMerkleTree = createMerkleTree(leaves, 0, ceil(log2(leaves)), CHILDREN_PER_PARENT)

func getComputeTreeLeaves(Vote[] votes, uint votingEndBlock):
result = COMPUTE_START_NUMBER // as negative numbers cannot be used in smart contracts, this is a safe limit below which number would not go
for(uint i = 0; i < votes.length; i++):
balance = getBalanceAtBlock(vote.voter, votingEndBlock)
if(vote.vote == 2) { // yes
weightedVote = balance
} else if(vote.vote == 1) { // no
weightedVote = -balance
} else {
return new Error("Invalid Vote")
}
voteComputeOps.push(vote.voter + balance)
result += weightedVote
if (i % MAX_COMPUTABLE_OPS == 0) || (i == (votes.length - 1)):
voteComputeOps.push(result)
isVoteSuccess = (result > COMPUTE_START_NUMBER) ? true : false

func createMerkleTree(uint[] leaves, int index, Level level, uint CHILDREN_PER_PARENT):
if level == 0:
if index >= leaves.length:
leaf = Keccak256(0)
else
leaf = Keccak256(leaves[index])
merkleTree[0][index] = leaf
return leaf
for(uint i = 0; i < CHILDREN_PER_PARENT; i++):
prevLevelRoot = createMerkleTree(leaves, index + i * (CHILDREN_PER_PARENT**(level - 1)), level - 1)
levelRootPreImage += prevLevelRoot
levelRoot = Keccak256(levelRootPreImage)
merkleTree[level][index/(CHILDREN_PER_PARENT**level)] = levelRoot
return levelRoot


### Proposal Period

Once the contract to accept voting proposals is created. A window of VOTE_RESULT_SUBMISSION_PERIOD blocks is provided for anyone to submit the result of the voting along with the vote compute root. Multiple entries with the same compute root are not allowed. Any proposals for the compute root have to be submitted before the period ends.

#### Submit vote result

The voting result can be submitted to blockchain once it has been calculated based on votes submitted and their token weights by staking VOTE_RESULT_SUBMISSION_STAKE LIN.

func approveStake():
LINTokenContract::approve(VOTE_RESULT_CONTRACT, VOTE_RESULT_SUBMISSION_STAKE).send(self.privKey)

func onStakeApproved(bool result, bytes32 computeRoot, bytes32[] resultProof):
resultProof = getMerkleProof(noOfLeaves - 1)
VoteResultContract::submitResult(result, computeRoot, resultProof).send(self.privKey)


### Compute Root Challenges

The proposal submitted will be matched for a challenge when another proposal is submitted. Matching for challenges will be done on an ongoing basis. As multiple challenges will run parallelly, the number of rounds of challenges will be of order O(log(noOfProposals)).

#### First unagreed leaf

In a challenge the children of the submitted voteComputeRoot are requested. Both the participants have to respond within CHALLENGE_PERIOD blocks. If both participants provide valid children then the first child that is different between both sets of children are identified. This first different child respectively for the participants acts as the root for the next round. This process is iterated till the first leaf that is different is identified.

In case of providing children that doesn't match the root, one or both participants of the challenge that provided the wrong set of children loses the challenge and the stake locked is lost.

func onChildrenRequested(event):
if event.participant != self.pubKey:
return;
if(response.currentLevel < ceil(log2(noOfLeaves))):
root = event.root
if(!response) {
response = ChallengeResponse(0, 0, 0)
} else {
response.currentLevel++
response.index = response.index*CHILDREN_PER_PARENT + event.childIndex
}
respondToChallenge(voteMerkleTree[response.currentLevel + 1][response.index*CHILDREN_PER_PARENT:(response.index + 1)*CHILDREN_PER_PARENT - 1])

func respondToChallenge(bytes[] children):
Challenge::getChallengeResponse(children)


#### Unagreed leaf verification

The first unagreed leaf can be of 2 types

1. Account Leaf
• Leaf which contains the hash of account and it's balance
2. Calculation Leaf
• Leaf which contains the calculation of previous set of MAX_COMPUTABLE_OPS leaves.
func onLeafProofRequested(event):
if(event.conflictType == 1):
respondToAccountConflict(event.path)
else if event.conflictType == 2:
respondToCalculationConflict(event.path)

##### Account Leaf

There can be 2 reasons due to which account leaf can be different. Either both participants are talking about different accounts or if for the same account balances are different.

Different Accounts

If both participants have committed different accounts to the VoteComputeProof, then the accounts are compared against the previous agreed account. If either or both of them are lower than the previous agreed account, then corresponding participants will be slashed as tree should be built with leaves in ascending order. If both accounts are higher than the previous agreed account, then the vote of each of the account is verified to be valid. If invalid account without vote is provided, corresponding participant will be slashed. In case both accounts are valid, then the lower of the 2 accounts are considered valid because the accounts should be in ascending order and the participant with the lower account missed the lower account.

func createLastAccountProof(uint path):
currentAccountProof = getMerkleProof(path)
lastAccountProof = getMerkleProof(path - 1)
return shortProof, commonAncestorHeight = getPathFromCommonAncestor(currentAccountProof, lastAccountProof)

func getPathFromCommonAncestor(proof1, proof2):
for(uint i = proof2.length; i > 0  ; i--):
if(proof1[i - 1] != proof2[i - 1]) {
level = (proof2.length - i)/(CHILDREN_PER_PARENT - 1)
break;
}
return proof2[:(level + 1) * (CHILDREN_PER_PARENT - 1) - 1], level


Different Balances

In case both the pariticipants have committed different balances for the same account, then proof of balance against the state tree are requested for each of the account. As the state root at the counting block is recorded, any proofs against the state root can be verified.

// TODO: Expand getEthStateTrieProof
func createBalanceProof(bytes32 account):
proof, leaf = getEthStateTrieProof(account)
return proof, leaf

func respondToAccountConflict(uint path):
account, balance = voteTreeLeaves[path]
lastAccount, lastAccountBalance = voteTreeLeaves[path - 1]
shortLastAccountProof, commonAncestorHeight = createLastAccountProof(path)
accountEthStateProof, ethAccountLeaf = createBalanceProof(account)
Challenge::resolveAccountConflict(balance, account, lastAccount, lastAccountBalance, commonAncestorHeight, shortLastAccountProof, accountEthStateProof, ethAccountLeaf)

##### Calculation Leaf

The result of the vote computation are inserted into the vote compute tree for every MAX_COMPUTABLE_OPS leaves to make sure that it will be possible for contract to verify the validity of computations without actually performing all the computations. When there is a conflict about the result of computation, contract computes the result of the conflicting computation from the last agreed result of computation.

func respondToCalculationConflict(uint path):
currentValue = voteTreeLeaves[path]
lastCalculationPath = path - (MAX_COMPUTABLE_OPS + 1)
lastAgreedValue = voteTreeLeaves[lastCalculationPath]
currentValueProof = getMerkleProof(path)
lastAgreedValueProof = getMerkleProof(lastCalculationPath)
lastCalculationShortProof, commonAncestorIndex = getPathFromCommonAncestor(currentValueProof, lastAgreedValueProof)
for(uint i = lastCalculationProof + 1; i < path; i++):
account, balance = voteTreeLeaves[i]
proof, index = getPathFromCommonAncestor(currentValueProof, getMerkleProof(i))
leafProofs.push(LeafProofData(account, balance, proof, index))
Challenge::resolveCalculationConflict(currentValue, lastAgreedValue, commonAncestorIndex, lastCalculationShortProof, leafProofs)


#### Closing a challenge

Once the conflict is resolved by the challenge contract, contract sends a transaction to the vote result contract to close the challenge. Once the challenge is closed, the winner of the challenge if any is matched with another proposal to start a new challenge till only one challenger is left. The challenger who is finally left is considered the correct vote compute root and the result is declared as the result of vote.

If a stale challenge in which either of the participants forfieted is observed, anyone can send a transaction to closeStaleChallenge function with the challengeAddress to close the challenge after the MAX_CHALLENGE_COMPLETION_PERIOD is completed.

func closeStaleChallenge(challengeAddress)

func allocateRewards()