Colordag

[xuechao2]

Colordag

• Colordag is an incentive-compatible reward scheme, where the equilibrium (honest) strategy that is almost always a best response.
• Colordag forms a directed acyclic graph (DAG), where every block has multiple parents. The recommended/honest strategy is taking the parent set to consist of all leaves in the DAG (of course this will include the tip of the longest chain in the DAG).
• In Colordag, each block is randomly assigned a color, actually a number chosen uniformly at random in some range (0, …, k-1), using hash sortition (a.k.a. k-for-1 mining).
• A graph minor is derived from the full DAG by taking all vertices of a certain color, and placing an edge between two vertices if there is a directed path between them that does not include another block of that color (see example below). The forking rate of each minor can be made arbitrarily small by increasing the number of colors.
  
• Block reward/penalty: if two blocks have the same depth in a graph minor, both receive zero rewards.
• However, an attacker could cause honest blocks to be penalized by simply creating a sibling block. To prevent this, Colordag ignores blocks unless, roughly speaking, they are on a path that is almost as long as the longest path (see example below).
  
• Remark: the ledger formation rule in the paper is using the longest chain of one specific color. However, I think it makes more sense to use the global longest chain in the full DAG, otherwise there is no point to have multiple colors. In this way, Colordag will have the same performance and security as the longest chain.