Add Rewards

[ineiti]

Discussing with Lefteris, we should start using rewards for ByzCoin:

• Look at MOTOR paper https://eprint.iacr.org/2019/676.pdf

• Signing rewards

  • Leader rotation? -> regular basis
  • Quick finish of BLS? -> collect later signatures and append them to future blocks. Actual reward is calculated in block + 10 or so, in order to account for these messages, too

• Proof-of-Personhood

  • One party-line defines stake
  • People can vote for nodes -> split vote possible
  • Reward is split between nodes & people -> smart contract for each node

• Transaction costs

  • Creation / Update of instances
  • BEVM Contract
  • -> like ETH, separate reward and gas, where the gas can be scaled

• PoP-example

  • DEDIS: 2 votes, C4DT: 2 votes, Ineiti: 1 vote
    • DEDIS has 2 identities and proposes twice as many blocks as Ineiti

[calctopian]

Being a little more specific, I've found the following lines in the codebase where rewards should be minted:

• spawning, invoking, or deleting instances of contracts (BEVM or not)
• leader rotation
• block proposals

Would you mint rewards somewhere else?

Your opinion about this also important: @cgrigis, @Gilthoniel, @gnarula, @jeffallen, @nkcr, @tharvik

[calctopian]

Quick finish of BLS? -> collect later signatures and append them to future blocks. Actual reward is calculated in block + 10 or so, in order to account for these messages, too

There are multiple ways to implement this feature, not clear what is intended because it's under-specified. For example:

• a leaf fails to send a signature to the sub-leader because the sub-leader closed the channel or there was a timeout: shall the leaf enqueue said signature to send it later to next sub-leader, or to the next leader?
• if the leaf must send a delayed signature to next sub-leader, what are the incentives of the next sub-leader to collect previous signatures and send them to the current leader? Should delayed signatures be broadcasted to prevent malicious sub-leaders?
• would it be more elegant to create another channel for delayed signatures?
• it's easier to deny rewards to leaves or sub-leaders that aren't responding, why isn't this contemplated?

[ineiti]

The Quick finish means that the sub-leaders will forward signatures from their leaves if already a threshold are available. So if a sub-leader has 4 leaves, he will already forward the signatures if it received only 3, and the 4th once it is available.
This allows the leader to finish the block with the minimum required number of signatures, instead of having to wait for more.

But this poses a problem for rewarding slow nodes, because they would not receive any rewards, as they are always late.

We could also rotate the leader much more often (like every 10 blocks), and then the new leader could add all his missing signatures in his first block.

Would you have time working on this? You would have to add some description how this should work, and once @LefKok is OK with it, I can show you how to implement it.

[calctopian]

Thank you Linus, now I understand what you mean by "Quick finish of BLS" and how it fits the "Liveness Incentives" in the MOTOR paper, Section IV. E. 2)

Nonetheless, there is an issue with the "Reward Allocation Incentives" (Section IV. E. 1): all nodes defecting is a Nash equilibrium.

Assume that every type of node has a different cost: c^l for leaders, c^sl for sub-leaders and c^leaf for leaves (s.t. c^l > c^sl > c^leaf).

Theorem. In each round of MOTOR with n nodes (i.e., where there are leaders, sub-leaders and leaves), the strategy of all nodes defecting is a Nash Equilibrium.
Proof. When all nodes defect, there are no added blocks, no costs are incurred and no rewards are minted. Therefore:

1. Leaves will not increase their payoff by unilaterally deviating from defection to cooperation, as each leaf would have to incur cost c^leaf and thus their payoff would be negative (i.e., -c^leaf)
2. A sub-leader will not increase their payoff by unilaterally deviating from defection to cooperation, because each sub-leader requires a positive threshold of cooperative sub-leaders and a cooperative leader to earn a reward, otherwise their payoff is negative (i.e., -c^sl)
3. Leaders will not increase their payoff by unilaterally deviating from defection to cooperation, because each leader requires a positive threshold of cooperative sub-leaders and cooperative leaves to earn a reward, otherwise their payoff is negative (i.e., -c^l).

Therefore, all nodes defecting is a Nash Equilibrium. QED.

An analogous result can be obtained for a strategy in which leaves do not sign/gossip transactions, sub-leaders do not collect/aggregate transactions from leaves and leaders create empty blocks, while everyone collects their reward: their payoff is maximised by ignoring transactions, not incurring costs and collecting rewards.

@LefKok, all-defection strategies are profitable when there are no penalties associated to non-cooperative strategies, and rewards are the same for different types of nodes in spite of their different costs: a proper reward allocation must take into account all these details. For a proper example, an incentive compatible reward mechanism where cooperation is a Nash equilibrium (Theorem 7) is described in my zk-PoI paper at Section 5.1.

[LefKok]

"Assume that every type of node has a different cost: c^l for leaders, c^sl for sub-leaders and c^leaf for leaves (s.t. c^l > c^sl > c^leaf)."

I would say that this cost is so marginal that modelling to 0 is practical enough to circumvent the problem that appears in asynchronous distributed systems that doing nothing is always the best thing (since your messages might be dropped by the network)

[calctopian]

Far from it, the empirical costs of running a node aren’t cheap:

• $30k for an EOS full history node
• $2500/month for a Cosmos/Tendermint validator node
• $3000/month for Algorand

A stronger impossibility result prevent us from achieving cooperation between the nodes.

Theorem. In each round of MOTOR with n nodes (i.e., where there are leaders, sub-leaders and leaves), with rewards shared proportionally according to , the strategy of all nodes cooperating can never be a Nash equilibrium.
Proof. Start with all nodes cooperating paying their respective costs, the payoff for each node is given by:

• for each leaf
• for each sub-leader
• for each leader

Assuming that nodes deviate unilaterally, we can reason that:

• leaves are better off defecting and staying silent, bilking their cost and increasing their payoff to , greater than their previous payoff.
• likewise, sub-leaders are better off by defecting and increasing their payoff
• finally, leaders also defect and increase their payoff . Consensus can be reached because there are no transactions on the network.

Therefore, all nodes cooperating can never be a Nash Equilibrium. QED.

@LefKok, the theoretical point here is that it’s an indispensable requirement for any reward allocation mechanism to prove that cooperation is a Nash equilibrium (e.g., Theorem 7 of my zk-PoI paper at Section 5.1), otherwise the mechanism could get broken.