Development Update #35

Research Update

Incredible breakthrough on consensus. We have been discussing methods for distributed consensus, creating terminology for understanding the consensus process. We think we have a good formal mathematical model now.

We drew out a finite state machine diagram for client transition states and found a new way of reasoning about state. We discovered that there are security measures that can be layered on to coins, which provably only improve the security of the coin without possibility of introducing a new attack. The coin client has a finite state machine and there is an operator that composes with the finite state machine, creating a new finite state machine. If a mapping from the new state machine back into the original state machine, exists, which satisfies a property, then no sequence of input exists where the new state machine fails where the original state machine did not also fail with respect to a security property.

The property was originally proven using a state machine and constructing a binomial lattice type diagram of the transitions for the state machine for a single input. The result generalized to machine with arbitrary sequence of input.

We are looking at Harel Statecharts and Hierarchical Moore Machines models now, for modeling the Skycoin consensus process and proving properties. We have very good results so far. If this works we can implement the Skycoin consensus system as a formal state machine being emulated by a golang program to ensure we get the mathematical guarantees on the security properties (such as state unreachability).

Types of Double Spending Attacks:

Bitcoin is susceptible to double spending from Public Chain fork attacks, where a fork is public and eventually grows to overcome the main chain. Skycoin is not. The Skycoin client tries to be aware of alternate chains and for older history its impossible to create a public chain fork from blocks past a certain number of confirmations, which can become a consensus chain. The only issue left is ruling out chains that were mined in secret and then published to network.

We have identified two types of client behavior with respect to forks:

We show that public chain forks are benign. They cannot result in double spending with a properly designed client.

We show that timestamping can be used to eliminate the Private Chains from being accepted. This is the last challenge to eliminating economically significant double spending attacks in Bitcoin like systems. For simplicity, we examine different centralized solutions, then will discuss decentralized alternatives.

Example System for Analysis:

Example 1: Insecure Time Stamping
Here we have:

Assume we have a trusted 3rd party time stamping server. The server signs each publicly announced block after it has received five confirmations. A client will use the time stamps to determine which chain is valid.

In this system:

This system is not stronger than hashing. It introduces a new attack state transition (compromising the timestamp server).

Diagrams

To simplify analysis, we will gloss over network state and focus on individual clients. We will also simplify issue of orphan chains. To simplify analysis and diagrams, we assume that - The client has a consensus chain (the longest chain the client knows about) - We ignore issues of orphans and assume blocks are either successors to consensus chain or an unpublished side chain, that is being published in a 51% attack. - This analysis for simplicity is client level, not network level

Some of these nodes are “State nodes” which represent changes in state of the client chain. The state nodes are the symbols the model emits in each round in response to an input. Other nodes are decision nodes, where a node must make a decision. There is actually a series of “state nodes” in succession, an input comes in and then an output is emitted by the machine on certain nodes, then the machine resets and the next symbol comes in. The diagram over a sequence of inputs actually looks like a linked Markov model diagram. Each transition node itself, could be a program which looks at some state variables and outputs the transition.

The decision nodes, themselves may be state machines themselves (hierarchical state machines). The network enters the sub-machine and the submachine emits the transition the parent machine is to take, as an output.

These diagrams are simplifications of a more precise hierarchical state transition model which is still on paper. Issues such as netsplits, clients joining the network are ignored as special cases.

System 1

Rules:
States:

S1: Client accepts new block on existing chain S2: 51% attack. Client accepts chain that forks at a block which has more than N confirmations

Transitions:

T2: Normal operation. Addition of blocks or acceptance of new chain, which does not fork at a block with more than N confirmations T1: New chain is longer and forks at a block which has more than N confirmations

End Nodes:

S1: emits action to do nothing or extend the current consensus chain S2: changes the consensus chain

The client reaches S2 and the 51% attack succeeds only if the new chain is longer (more hashing power).

System 2:

System two is system 1 but with a developer run timestamp server, to prevent 51% attack

Rules:
States:

S1: Normal Functioning (stop node) S2: A new longer chain has been presented to client. The presented chain forks current consensus chain before a block that has N confirmations. The client needs to decide between the old consensus chain and newly presented chain. The client accepts the chain based upon time stamps S3: Attacker succeeds and attack chain was accepted

Transitions:

T1: Normal operation. Extension of current consensus chain. Block must extend the current chain. If addition of the new block to the chain would cause the block to go over N confirmations, then it must be timestamped by the server. T2: New longer chain presented to client T3: Client accepts chain which is potential 51% attack T5: Client rejects 51% attack chain and maintains current consensus chain T4: 51% attack without majority hash power. Attacker compromises timestamp server and client rejects the legitimate chain for the attack chain. The client will reject blocks with more than N confirmations, which do not have timestamps. The attacker simply only timestamps the attack chain, until it becomes longer than the current consensus chain.

State Nodes:

S1: emits action to do nothing or extend the current consensus chain S3 changes the consensus chain

Decision Nodes:

S2: checks time stamping server to determine whether to reject the 51% attack chain (T5), or accept the chain (T3)

The machine starts at S1. Under normal operation (a new block extending the current consensus chain) T1 is taken and the consensus chain is extended uneventfully.

There are 4 conditions:
  1. Normal operation (no 51% attack and working timestamp server)
  2. 51% attack and non-compromised timestamp server (attack fails)
  3. Attacker does not have enough hash power to create a longer chain, but compromises the timestamp server to get clients to reject the legitimize chain (attack succeeds)
  4. Attack has majority hash rate and controls time stamp server (attack succeeds)
This system is interesting:

System 3:

Here we use a timestamp server to rule out chains that were mined in secret and later published. However, we only fallback or even look at the timestamps if a switch over between chains is being considered. The timestamp server can prevent a double spending attack, but cannot be used to cause one.

Rules:

End States:

S1: Extend current chain by one block or do nothing S3: Accept new consensus chain (accept fork)

Decision States:

S2: Check timestamps on forked blocks and decide to accept the chain as the new consensus chain(S3) or reject the chain and keep the current chain (S1)

Transitions:

T2: A new longer chain has appeared that would change the consensus chain. Move to S2 T5: The timestamps of the new chain were examined and the new chain was determined to be a 51% attack attempt (someone mined an unpublished chain until it was longer than current public chain and then published it). The new chain was rejected. T3: The attack chain was accepted

In this system:

Challenges:

Assumptions:

Implications:

By using a honest third party service which timestamps each block we can eliminate the Private Chain Fork attack. The timestamp acts as a proof of publication of the block. Blocks mined in secret and then later published will not have timestamps and therefore can be identified as 51% attack attempts.

Fair Timestamping:

The original Skycoin consensus system, gives each user a personal blockchain. The users publish blocks and subscribe to other user’s blockchains. When a user becomes aware of a block, they publish the hash of the block in the next block published to their personal blockchain. Each published block is timestamped and therefore attests to the existence and publication of the block.

Alternatives:

Proof-of-Stake with Delegated Timestamping:

Bitcoin combines three separate things in a single entity in the block headers:

In Bitcoin these separate functions are combined into a single block header. - The group of miners with the most hash power determines which chain is valid - The miners choose what is in each block - Difficulty rate limits block creation rate

However, it does not have to be designed that way. In Skycoin these functions are separated out in a more fine grained way.

We could imagine a system where:
In these systems the questions to ask are:

There can be different groups of people serving these functions

The consensus mechanism can be complex, can be outside of the blockchain and can contain multiple factors or mechanisms. Hashing is the weakest mechanism and most expensive per unit of security. Proof of stake is second mechanism but also imperfect. An ideal system would combine Proof of Stake with a second mechanism indepedent of coin ownership, where even a majority coin holder could not attack the system without also compromising the independent mechanism.

No translation bounty

Discuss this post on telegram

Skycoin Telegram