Skip to content
Permalink
master
Switch branches/tags
Go to file
 
 
Cannot retrieve contributors at this time
  DIP: 0001
  Title: Initial Scaling of the Network
  Author: Darren Tapp <darren@dash.org>
  Comments-Summary: No comments yet.
  Status: Final
  Type: Standard
  Created: 2017-07-05
  License: MIT License

Table of Contents

  1. Abstract
  2. Motivation
  3. Conventions
  4. Prior Work
  5. Quadratic Hashing
  6. Consensus Protocol Changes
  7. Observation
  8. BIP 009 Inspired Activation
  9. Calculation of thresholdreached
  10. Comments on a Spork
  11. Copyright

Abstract

We outline an initial scaling mechanism for Dash. After deployment and activation, Dash will be able to handle double the transactions it can currently handle. This means that Dash will be prepared for eight times the traffic of Bitcoin.

Motivation

Peer to peer electronic cash systems rely on the fact that they can be used with little to no trust in a third party. We have also seen scaling issues have dramatic effects on the usability of these systems. The current state of the dash network requires users to trust that developers will deliver a scaling solution when needed. Implementation of DIP1 allows users to actively participate in increasing the capacity of Dash.

In addition, scaling solutions take time to roll out. As such, developers are tasked with rolling out scaling solutions four or five months before they are needed. Forecasting network traffic growth is an impossible task. An exponential regression would estimate that the network will be at capacity around September of 2018. However, there are outside factors that could accelerate this estimate. For example, a chain fork which is being discussed for bitcoin may drive users to alternatives. Also, market actors can have a profound impact on the use of Dash, and do not necessarily announce their intentions for proprietary reasons.

One more motivation is that adopting this proposal serves as a proof of concept of Dash’s governance system. It shows that proposals voted on by masternodes do actually have real world results. It removes the need for users to trust in Dash’s proposal system.

Conventions

  • 0x20000000 is the bit sequence 00100000000000000000000000000000 and is the current version of dash blocks.
  • 0x20000002 is the version used to signal acceptance of a consensus change rule. A miner should use this version to signal acceptance of the miner and the masternode for the block of a consensus rule change.
  • We use % as it is used in C++. It is the remainder on division. So 7 % 3 is 7 modulo 3 and is equal to 1.

Prior Work

  • BIP 0009 Improvement plan that signals a consensus rule change. This allows for activation when a sufficient number of miners have upgraded.
  • BIP 0135 Alternate Improvement plan that signals a consensus rule change.
  • BIP 0113 Specification of Median Time Past (MTP).

Quadratic Hashing Challenge

Currently Dash has a size limit of 1MB per block. With this limit a miner could include a transaction that takes around 3 minutes to verify on a moderate CPU. However, with a 2MB block size the attacking miner could include a transaction that takes around 12 minutes to verify. If an attacker successfully gets an attacking block in the chain then all nodes in the future will need to verify this block when syncing. This attack is even more dramatic as block size increases. Paradoxically, this attack could get so bad that it becomes impossible because propagation would force an attacking block to be orphaned. Even if an attacking block is not included in the main chain, trying to verify attacking blocks can have negative transient effects.

This attack is quadratic with respect to transaction size. As such, limiting transaction size makes this attack impossible. Currently, transactions over a size of 100kB are nonstandard and dropped by the network. A quadratic hashing attacking transaction of size 100kB would take around 2 seconds to verify. Since transactions are processed in parallel, a 2MB block full of 100kB attacking transactions would take from 4 to 8 seconds to process. For this reason this DIP changes consensus rules so that blocks with a transaction over 100kB are ruled invalid and orphaned.

Consensus Protocol Changes

Currently there is a protocol rule as follows:

  • A block over 1MB is invalid.

To allow the network to scale we replace this rule with the two rules:

  • A block over 2MB is invalid.
  • A block with at least one transaction over 100kB is invalid.

Note the 100kB cap on transaction size will not necessarily be satisfied by old blocks. For this reason this new rule must only be enforced on blocks after activation of the protocol change.

Observation

100kB Transaction Limit

This subsection is to only point out a possible efficiency of the 100kB transaction size limit. Currently, transactions in the mempool already verified to be standard and thus satisfy the size limit. It should then be possible that only transactions not seen by the node would need to be checked to satisfy the 100kB limit. However, checking if a transaction is in the mempool might take as long as verifying the size.

BIP 009 Inspired Activation

To ensure a coherent network roll-out we employ BIP9 signaling adjusted for Dash. We reserve the last bit in the version to signal for DIP1 activation. A DIP0001 enabled miner will broadcast block version 0x20000002 only if the masternode selected for that block is also DIP1 enabled. We model the 2016 block difficulty adjustment period in BIP9 with a 4032 block round. This length of a round should allow for a representative sample of masternodes to be taken.

As a block is mined the version number is determined by the miner who mined it and the masternode that is selected for that block. Note that blocks mined by non upgraded miners will broadcast version 0x20000000 without regard for the DIP1 acceptance of the masternode selected.

As in BIP9 each block is assigned a state according to the flow chart:

State Flow Chart

Above, MTP represents the median time past as in BIP113. The variables starttime and timeout are particular integers that represent the time in the current epoch. Here, threshold reached, is a particular boolean we will define below, and denote without the space, thresholdreached, in code.

The state of every block is determined by the algorithm below:

The state of the Genesis block is DEFINED as in BIP009.

State GetStateForBlock(block) {
  if (block.height == 0) {
    return DEFINED;
  }

All blocks in the same round have the same state.

if ((block.height % 4032) != 0) {
            return GetStateForBlock(block.parent);
        }

Otherwise, the next state depends on the previous state:

switch (GetStateForBlock(GetAncestorAtHeight(block, block.height - 4032))) {

We remain in the DEFINED state until we either pass the starttime or the timeout. GetMedianTimePast in the code below refers to the median nTime of a block and its 10 predecessors.

  case DEFINED:
            if (GetMedianTimePast(block.parent) >= timeout) {
                return FAILED;
            }
            if (GetMedianTimePast(block.parent) >= starttime) {
                return STARTED;
            }
            return DEFINED;

After a period in the STARTED state, if we're past the timeout, we switch to FAILED. If not, we tally the bits set, and transition to LOCKED_IN if a sufficient number of blocks in the past period have bit1 set to 1.

Note that a block's state never depends on its own nVersion; only on that of its ancestors.

    case STARTED:
            if (GetMedianTimePast(block.parent) >= timeout) {
                return FAILED;
            }
            if (thresholdreached) {
                return LOCKED_IN;
            }
            return STARTED;

The protocol change is only in force when the first block is in an ACTIVE state.

Selection of Parameters

For values of starttime and timeout, we suggest:

  • starttime= 1508025600-- turn of Oct 15 at midnight
  • timeout= 1539561600-- 52 weeks later

This is assuming the code is available mid September. If the code is available at a later release these numbers should be adjusted.

The selection of a round consisting of 4032 blocks is made based on masternodes not being randomly selected, rather they are in a queue. As such it can’t treat the sample of masternodes as a simple random sample. At current time 4032 masternodes would consist of a sample of around 87% of masternodes. This number is small enough that the sample of masternodes are unique. If this number were larger then there would be a chance that some masternodes would be sampled twice while others aren’t sampled at all. This property is maintained as long as the number of blocks in a round is under 90% of all masternodes. The number 4032 also has the property of being equal to about a week of blocks.

Calculation of thresholdreached

Determination of thresholdreached

Given a block with block.height % 4032 = 0 we can calculate thresholdreached. thresholdreached is determined by bit1 on each version of all blocks in the previous round. Note the current block is not considered to be in the previous round. We define thresholdreached to be true when and only when,

(sum(bit 1) >= 3226).

This sum is over (block.height - 4032) through (block.height - 1).

This translates to 80% of the DIP1 flags.

Expected activation conditions

Given that bit1 will be 0 if mined by a non-DIP1 miner this actually targets activation in the following cases.

  • >=80% of mining power and 100% of masternodes

OR

  • >= 89.5% of mining power and >= 89.5% of masternodes

OR

  • 100% of mining power and >= 80% of masternodes

In any case, activation is highly unlikely without at least 80% of miners and 80% of masternodes.

Comments on a Spork

It has been suggested that a spork variable be used to possibly delay activation if there is some type of hiccup with roll out. In my estimation, using a spork variable could introduce variables that might lead to unintended consequences.

This rollout requires all nodes to agree on an activation block height. DIP1 as outlined above only relies on an inspection of the chain to determine the activation block height. The blockchain was created to solve just this problem of distributed nodes agreeing on information. At this time I do not see how this level of security could be achieved with something not on chain.

It is also important that the protocol never roll back to the previous state. If this ever happened then new nodes would not be able to sync with the main chain. Also existing nodes may not agree on a chain if the spork was ever rolled back.

Copyright

Copyright (c) 2017 Dash Core Group, Inc. Licensed under MIT License