Security Analysis of ChainLocks complete

In Satoshi Nakamoto's bitcoin paper there is section 11 with the title "Calculations". This section basically proves that bitcoin is very secure as long as at least half of the hashing power is behaving as expected.

Last year, the cryptocurrency Dash introduced a secondary consensus mechanism called ChainLocks. The technical specification of ChainLocks was explained in a document known as Dash Improvement Proposal 008 or DIP008. When this document was published I quickly went to calculate the security provided by the new specification. The large 400 node quorum means that the spread sheet I had for such calculations choked hard. So it was time to pull out the big guns, Python.

Within a half an hour I was maxing out a processor of my old laptop with calculations. I was happy that minutes later I had an answer, and the answer was affirmative. ChainLocks did provide security from purposefully malicious actors. I went back to other tasks now that I was convinced of the security of ChainLocks. Then I received a few questions about how to perform these calculations. So I shared my Python script. Thephez on github made this Python script much more efficient. It would run in seconds instead of minutes.

I then thought back to Satoshi's paper. It was really that Calculations section that was the convincing part. So in the open source spirit I formally wrote up the security analysis and submitted a pull request. Today, that pull request was merged. DIP008 now has a calculations section.

The calculations rely on binomial coefficients. As an example you can type "7 choose 5" in google and get 21. The number 7 choose 5 is written \[ _7 C_5 = {7 \choose 5} = 21\]

My main complaint is that GitHub's markdown does not out of the box render all mathematics. I used the notation \( _n C_r \) for \(n\) choose \(r\) because markdown of github supports that better. I generally think \( { n \choose r }\) is a more common notation.

My favorite quote is:

The attacker would have a less than one in 100 trillion chance of producing at least one malicious ChainLock in the next sextillion (10^21) years.

This is assuming that thirty percent or less of the Masternodes are controlled by an attacker.

The heart of the calculations is in the function pcalc below.

dip008functions.py (Source)

def binom(x, y):
    try:
        binom = fac(x) // fac(y) // fac(x - y)
    except ValueError:
        binom = 0
    return binom


###This function takes inputs and outputs the probability
#of success in one trial
#pcalc is short for probability calculation
def pcalc(masternodes,quorumsize,attacksuccess,Byznodes):
    SampleSpace = binom(masternodes,quorumsize)
    pctemp=0
    for x in range(attacksuccess, quorumsize+1):
        pctemp = pctemp + binom(Byznodes,x)*binom(masternodes-Byznodes,quorumsize-x)
    #at this juncture the answer is pctemp/SampleSpace
    #but that will produce an overflow error.  We use logarithms to
    #calculate this value
    return 10 ** (log(pctemp,10)- log(SampleSpace,10))