Development Update #29

Summary:

Its July. Meshnet was promised in July. Spec is done. Implementation in progress.

We end up writing everything five times and refactoring it before its perfect. Sorry this takes so long.

Summary of Skycoin Consensus Algorithm Research to Date

We solved adversarial byzantine generals for full connected graphs with a:
We have mathematical proof that 51% attack proof is achievable with a single trusted timestamping server.

Mathematical Results:

Threat Reduction Measures

Current Skycoin Consensus System Design:

Consensus

The formal state transition diagram for network consensus for netsplit and 51% attack prevention is coming together. We are sure that if 90% of the nodes in a random graph attempt to revert block consensus, they will fail. There are three difficult conditions that must be met in succession for a block consensus reversion attack to succeed.

There were two states for nodes. A new third state for network bifurcation has been added. This third state simplifies the state transition diagram for dealing with attacks and netsplits - Converged with network (this is determined at minimum by the “Consensus Oracle” mechanism) - Not converged. This is state where the current node block consensus is on a different chain than rest of network and knows it. - A new “bifurcated network state”. This is the state a node goes into when it detects two or more divergent consensus chains on network subgraphs. This is the state the network is left in after a netsplit or consensus reversion attack attempt. This state begins conflict resolution.

There is a window of blocks. Nodes can remain in the converged state during the consensus process for this many blocks in the presence of blockchain forks while remaining in the converged state. - This is the “consensus window” in which the network has to resolve choices between alternative blockchains. - Once a block goes outside of window, it is “final” and reversion should be impossible. - It is acceptable for the network to stop until consensus is achieved if the window would be exceeded by the additional of new blocks. Stopping or slowing down the network during an attack is preferable to introducing a 51% attack. Once attacking nodes have been identified, people can remove them from their trust lists and their influence on the network eliminated. - The probability of forks decreases exponentially with block depth within the consensus window

Unconverged states happen when consensus process runs on and exceeds the window. This may indicate a pathological subgraph slowing down convergence or a DDoS attack. It may also reflect lose of connectivity between continents slowing down blockchain convergence.

Note: For the purposes of the finite state machine transition diagram, the unconvergence state is discrete. Block introduction is rejected or discouraged while pending consensus decisions are processed. As a practical matter, there may be transaction throttling, with block rate decreasing as a function of the size of the open decision set. This is called the “soft throttle”. The “hard throttle” is when nodes begin rejecting block introduction until the current backlog of consensus decisions are globally resolved.

Bifuricated network state occurs when peers announce a chain which forks before the window and which was not previously in the consensus decision set (fork introduction). This only occurs doing a netsplit when nodes rejoin the network or during a directed attack. Most nodes in the bifurcated network state resolve automatically.

There are several detectable error states, that should not occur in normal operation but will occur. Such as local node assumes a consensus state that differs from the state suggested by the consensus oracle.

Handling Bifurication State:

This state should never be reached, except in emergencies and major coordinated attacks. An attacker must have the resources and the will to attempt to put the network into this state. This will never occur on a network of non-malicious unmodified clients running on a reliable internet.

If this network state has been reached:

This is the state that triggers the 51% attack detection. This is being worked through. This state should not be triggered during normal operation.

The network is designed to never get to this point, but if it does then there are a number of possible resolution procedures we are looking at. The network will run both branches concurrently until the split is resolved. - Manual resolution (each user setting chain by hand). The honest nodes and exchanges affected by the split, will just revert the fork and their nodes will discard the bad chain. In Bitcoin the pools participating in an attack are likely to be in on the attack and the victims are the exchanges and service operators, making it difficult to revert the chain after an attack. In Skycoin, people are unlikely to use a chain that is not the consensus chain of the large exchanges and Skycoin service providers (who are the victims and targets of the double spending attack). The incentives are therefore slightly better aligned. - A developer emergency signing key with 2 out of 3 keys required. Instantly resolves deadlock. Should never get to this point.

Transaction Confirmation States and Block Depth:

There is a separate flowchart for transaction confirmation. Transactions will be reported by the client JSON API as - Pending: transaction relayed by network, but not entered into block yet - Confirmed: transaction entered into block in consensus chain with N confirmations.

N confirmations means the block in which the transaction was entered, has N successor blocks up to the first block which has 0 or more than one remaining candidate child blocks pending network consensus. Skycoin can have multiple child blocks and branches pending consensus, the network does not slow down to decide a single block and then the network block. Therefore each transaction has a “depth” with respect to the last block with more than two remaining parents and the transaction has a depth with respect to each of the pending consensus chains.

So for example, if a netsplit occurs at block 10. The netsplit chain is on block 20. A transaction is entered in netsplit chain in block 15. The transaction has five confirmations with respect to the head of the netsplit chain, but has 0 confirmations (pending state) because block 10 has two children (block 10 was last block when the local node was in the “converged” state). - If the netsplit chain and mainchain merge at block 25, if the netsplit chain becomes dominant and the other chain pruned, then the transaction now has 10 confirmations - The transaction can never go into the confirmed stated while the node is in unconverged or bifurcated state. This automatically prevents the vast majority of double spending attacks against exchanges and merchants, as most exchanges will not apply a credit to an account until the transaction has reached N confirmations. - In Bitcoin “Confirmations” are the number of blocks since the block containing the transaction, for the longest block. In Skycoin, confirmations are the number of blocks after the transaction which have

There is a closely related concept, the “confirmation min” and the “confirmation max”. If there are two chain branches open for consensus and the transaction has four confirmations on the first chain and six confirmations on the second chain, the transaction will have a minimum of 4 confirmations regardless of which chain is chosen for consensus.

Scenario

There is a calculus of blockchains. There is a min, a max, a join and a bottom. We need to develop good terminology for talking about the blockchain forks, diagrams and software examples. Documentation is low priority until its working and the wiki is up. Someone will have to make a tutorial on the wiki, make python scripts for generating diagrams and come up with terminology.

No translation bounty

Discuss this post on telegram

Skycoin Telegram