We need more things to come consensus on! Let's make a concurrent schedule. Essentially, imagine a blockchain but we don't enforce a total order on blocks. Instead, blocks that don't need to be ordered aren't (e.g. if they don't touch the same piece of state), and so we have a DAG of blocks/estimates rather than just a tree.
Proposed Implementation
Protocol: Calling it ConcurrentProtocol. Happy to change subject to a better idea.
Message: Calling it a Block. Better name suggestions greatly appreciated. Maybe, Rewrite (but this implies a single rewrite, there might be multiple in a block).
Estimate: It's a bit unclear what an estimate is. So an estimate has to take a set of unspent pieces of state (say - UTXOs, or actual pieces of contract state in Ethereum), and rewrites them to new unspent pieces of state. However, the estimate both a) has to say what piece of state it is consuming, and b) what new piece of state it is creating (unless there's only one way to rewrite state, but somehow this doesn't satisfy some conditions to make the protocol interesting). So I'm exactly sure what the estimate data is...
Rewrite Rules: As mentioned above, you consume a piece of state and create a new piece. The question is - should there be deterministic state rewrite rules, or should they be random. Some balance of both might be nice - or it would be good if we could specify what the rules are. This seems to make checking message validity hard though (if they aren't deterministic)...
A possible option is that the rewrites are either the first, second, or third hash of a random number. So there is some randomness, but it's possible to check message validity in some way.
View: Very similar to the blockchain_view, except it maintains a set of last finalized blocks as the last finalized estimate...or should it maintain a set of outputs? Blocks is probably easier.
Forkchoice: Walks from the last finalized estimates, eating all the blocks it can. It can eat a block if all the things a block has consumed has not been consumed yet (and then adds the blocks new ouputs to the unconsumed outputs). If it reaches a block it cannot eat (because the ouputs were eaten by another block), then this is where the forkchoice must make a decision.
It chooses the block with the highest weight on it currently, reverts eating some ouputs if necessary, and continues until it runs out of blocks to eat.
Initial Messages: We can define a genesis block, or a set of genesis messages? If we have a single genesis message, and validators rewrite all of the available inputs, then I think we will only get a blockchain that is created. Thus, for this first version, each validator will generate a message with pairwise disjoint outputs.
naterush
commented
6 years ago
Issue
We need more things to come consensus on! Let's make a concurrent schedule. Essentially, imagine a blockchain but we don't enforce a total order on blocks. Instead, blocks that don't need to be ordered aren't (e.g. if they don't touch the same piece of state), and so we have a DAG of blocks/estimates rather than just a tree.
Proposed Implementation
Protocol: Calling it
ConcurrentProtocol. Happy to change subject to a better idea.Message: Calling it a
Block. Better name suggestions greatly appreciated. Maybe,Rewrite(but this implies a single rewrite, there might be multiple in a block).Estimate: It's a bit unclear what an estimate is. So an estimate has to take a set of unspent pieces of state (say - UTXOs, or actual pieces of contract state in Ethereum), and rewrites them to new unspent pieces of state. However, the estimate both a) has to say what piece of state it is consuming, and b) what new piece of state it is creating (unless there's only one way to rewrite state, but somehow this doesn't satisfy some conditions to make the protocol interesting). So I'm exactly sure what the estimate data is...
Rewrite Rules: As mentioned above, you consume a piece of state and create a new piece. The question is - should there be deterministic state rewrite rules, or should they be random. Some balance of both might be nice - or it would be good if we could specify what the rules are. This seems to make checking message validity hard though (if they aren't deterministic)...
A possible option is that the rewrites are either the first, second, or third hash of a random number. So there is some randomness, but it's possible to check message validity in some way.
View: Very similar to the
blockchain_view, except it maintains a set of last finalized blocks as the last finalized estimate...or should it maintain a set of outputs? Blocks is probably easier.Forkchoice: Walks from the last finalized estimates, eating all the blocks it can. It can eat a block if all the things a block has consumed has not been consumed yet (and then adds the blocks new ouputs to the unconsumed outputs). If it reaches a block it cannot eat (because the ouputs were eaten by another block), then this is where the forkchoice must make a decision.
It chooses the block with the highest weight on it currently, reverts eating some ouputs if necessary, and continues until it runs out of blocks to eat.
Initial Messages: We can define a genesis block, or a set of genesis messages? If we have a single genesis message, and validators rewrite all of the available inputs, then I think we will only get a blockchain that is created. Thus, for this first version, each validator will generate a message with pairwise disjoint outputs.