Bitcoin Cash Considers Prisoner's Dilemma


The Prisoner's Dilemma

Game theory is the study of one or more actors. The actors engage in a competitive or collaborative activity. At the end of the activity each actor has a way to judge the outcome and compare the outcome to other outcomes.

Game theory applies to:

  • traders on the market

  • dating

  • mining cryptocurrency

  • Traditional games (chess, bridge, etc.)

as well as many other situations. Not every player needs to be judged the same way. For an example, consider Leslie who goes to the market and buys a peck of apples from an apple farmer, Edna, for $4. Edna most likely valued the apples sold at less than $4. As Edna has lots of apples and would like to sell them before they rot. Leslie wanted the apples so much she not only parted with $4 but decided to use her time to seek out apples.

In game theory the value that each actor puts on each outcome is called a utility function. In our example Leslie might find the utility of laving the market with a peck of apples to be more than the Edna, who has apples at home. Utility is intended to be a measure of the value, or the enjoyment, or the use of an item or situation. Utility could be a subjective concept, but is useful when comparisons can be made.

In game theory there is a very famous example of a game known as the prisoner's dilemma. This situation happens when two sisters rob an electronics store. The police find each one of them driving a van full of stolen big screen TVs. Each of the sisters is arrested and taken in for questioning without the opportunity to talk to the other sister. The police then give each sister a choice. The choice is to tell on their sister and receive a year off any prison sentence. As it stands, each sister is facing a year of jail time for possessing the stolen televisions. The table below explains the consequences of the sister's option to stay silent or defect from her family.

/images/PrisonersDilemma-sisters.png

Now, basically the best outcome for both sisters for each of them to stay silent. That's the outcome that has the least amount of total jail time. However this outcome is unstable. In the case that both sisters stay quiet either one will gain (go free) from defecting. And even if one sister defects the situation is still unstable as the other sister could serve two years instead of three by telling. In fact each sister is always better off by defecting, no matter what the other one does. If both sisters do defect then neither sister can improve their outcome by their choice alone.

This game provides some insight into why, in some cases, corporative solutions are never sought after.

A Modest Proposal of Some Bitcoin Cash Miners

A proposal of Jiang Zhuoer and signed by other miners has been made to the Bitcoin Cash community. This proposal encourages other miners to orphan blocks that do not provide for a fund for developers. The proposal has a clear begin date and end date.

The proposal claims that it is not a change in the protocol. However, it would be a change in "a set of conventions governing the treatment of data in an electronic communication system." Which is a change in protocol according to Merriam-Webster. I think the author of the proposal meant that this proposed change in protocol would not be hard coded in the client.

It is the very fact that this protocol change is not hardcoded allows for this game theoretic analysis. We hope to understand the game theoretic implications of this type of protocol change.

Miner Behavior

Clearly there is anecdotal evidence that some people support funding developers in the form of the proposal. There is also anecdotal evidence here and here that some people don't support the proposal. Even better, is the fact that SHA256 mining allocation is very well understood and miners generally go after the most profit. cite: Bissias, Levine, Thibodeau.

For our game theoretic analysis we assume that 30% of the miners are ideologically driven in favor of the proposal. They assign a high utility to all blocks funding developers. The exact amount of value they assign the dev fund does not effect this analysis. The people who support the dev fund expect that this fund will pay off in the future in the form of a higher price. Economists would say that people that support the proposal have a low time preference. Also miners that support the proposal have a higher risk tolerance, as the dev fund is, in effect, investing in a startup. As we understand miners risk tolarance to be quite low (Bissias, Levine, Thibodeau) we expect that 30% is an overestimate.

We assume that all other miners are maximizing (revenue and therefore) profit.

The Game

If the 70% of miners that are profit maximizing know that they will all act together, then they can sleep easy knowing that following the longest chain and ignoring dev funding will maximize their profit. However, just like the electronics thief sister being questioned, the miners don't know if their sister miners will defect to the other side or not. As we will see, one major advantage is that the miners can coordinate their action. They can talk to each other.

As simplifying assumptions we assume that the 30% in favor of the dev plan always mine a chain consistent with the dev funding. To explain the incentives we break the profit seekers down into group A which is 30% of the hashing power and group B which is 40% of the hashing power. In such a case we have

/images/Miners-Dilemma.png

From this table we can see that if 30% (and not less than 20%) of the profit seeking miners enforce dev funding they will profit more. However, if 40% of the miners enforce dev funding then they will all collectively loose. However, if the longest chain is enforcing the dev funding then it's in everyone's interest to switch.

This analysis ignores the fact that BCH is a minority chain. Considering this fact, it's likely that hashing power would be attracted or repelled from BCH to balance out the profitability. This is asserted in the dev funding proposal, and to a very good approximation is correct.

The Sisters Talk

We're talking about miners on a public blockchain. They are not being held incommunicado like our sisters above. Mining participants could advertise the protocol they follow in the version number of a block that they mine. This could go both ways.

Miners like Jiang Zhuoer that want to fund the developers could flip a bit in their version number and if a sufficient number of blocks signal for the protocol rule at the scheduled MTP then dev funding could be safely enforced.

It works the other way as well. Miners that want to follow the longest chain could signal that with a bit in the version number. As long as a sufficient number of miners signal they are mining the longest chain then miners can safely add to the longest chain.

There is the opportunity that miners could lie. However, most of the time, lying in this circumstance does not help your cause. For more information about using the version number to signal the desired protocol to mine see BIP0009.

Conclusions

Having a consensus rule that is not enforced by the nodes leads to some very interesting game theory. If the consensus rule is enforced by all nodes than it would be in every miners interest to enforce the rule on that chain. However, if the consensus rule is controversial then there is a serious risk of forking off yet another minority chain.

Perhaps the best that can be hoped for is that both sides agree on one bit of the version number. Then use that bit to signal if funding for developers is enforced or not. As long as both sides can accept the results of the miner's vote then then the current Bitcoin Cash network does not risk a split.

To be clear, using a version bit to signal which protocol to follow may result in a genuine compromise. That is, a situation where the dev fund is only funded some of the six months that is asked for.

To me using a bit in the version is the polite way to mediate this dispute.

Darren Tapp Featured on Dash Podcast 137


Last Friday I was interviewed by Dash News, We covered topics relating to chainlocks and their security. We also talked about reducing proof of work for Dash. We discuss how SPV wallets could take advantage of chain locks to provide more security even with less work in every block.

We talked about the economics research going on right now at ASU. That is the part of research that I am involved in and most excited about. We talk about a lot of options. The hosts relate these decisions to being a central bank, and there is a parallel that can be drawn. Perhaps I didn't get across that the goal is to have a hands off economic policy. My hope is that a stable economic model can be adopted and hardcoded without intervention after the change. I lament that we did not talk about the Zero Knowledge Proof research also being worked on by the ASU blockchain research lab. I expect an update on that by the end of the school year.

I was asked about Dash's monetary inflation. It was purported that Dash's monetary inflation was high, and it is compared to other cryptocurrency projects. I'm hoping that any changes to the inflation schedule result in less issued Dash.

There is some discussion about masternode voting participation. Now that voting keys are on chain then it would be nice if a phone app allowed for voting on your phone. I think that would encourage more voting. Mark suggested that TAPPMATH could explain the calculations in the chainlocks security analysis in more detail.

If you haven't had a chance to watch this episode please find a video of it below.

A Short Introduction to LaTeX


\( \LaTeX \) is a markup language that is used for most mathematical writing. There is really no better way to communicate mathematics. The result is really polished. It doesn't matter if you're talking about Maxwell's equations: \[ \nabla \cdot E = \frac{\rho}{\varepsilon_0} \\ \nabla \cdot B = 0 \\ \nabla \times E = - \frac{\partial B}{\partial t} \\ \nabla \times B = \mu_0 \left( J + \varepsilon_0 \frac{\partial E}{\partial t} \right), \] Schrödinger's equation \[ i \hbar \frac{\partial}{\partial t} \Psi = \left[ \frac{-\hbar^2}{2m}\nabla^2 + V \right] \Psi, \] or \(L:V\to W\) a linear map from \(V\) to \(W\). I can not think of a better way of rendering mathematics than with \(\LaTeX\). Even more valuable than looking pretty, \(\LaTeX\) is typed without using the mouse. Being able to simply type mathematics really is a joy.

Now, \(\LaTeX\) is not something that you just sit down and learn. I find it best to have in mind what you want to write before you write it. Then look up what you need to write your document. The hardest part is starting. It can really help to have an example. It's even better to make changes and see what the result is. Below I believe is a good example of a document that helps explain what \(\LaTeX\) can do and how to do it. I also have linked to the resulting document below the source.

LaTeXsample.tex (Source)

\documentclass{article}
\usepackage{amssymb}
\usepackage{amsmath}
\title{Example \LaTeX\  Document}
\author{Darren Tapp}
\date{\today}
\newcommand{\RR}{{\mathbb R}}

\begin{document}
\maketitle
\LaTeX\  is a markup language that is intended to produce beautiful
mathematics.  We can display an equation;
\[
x+3 = 5.
\]
or mathematics could be in line as $x=2$.

\textbackslash\ usually preceeds a command.  \$ is also a special symbol that
denotes math mode.  One dollar sign for $\sum_{i=1}^n i$ if you want
the text inline.  Two dollar signs if you want to display
$$
\frac{\partial \psi }{\partial t} .
$$
However I prefer \textbackslash [ and \textbackslash ] to display equations.

Do you want to define a linear map $L:{\mathbb R}^2\to {\mathbb R}^3$?  We could
could let $L$ be an embedding of ${\mathbb R}^2$ into ${\mathbb R}^3$.
\[
(x,y) \mapsto (x,y,0)
\]
Note I get tired of typing \verb|{\mathbb R}| so I defined a macro above.  I
now can type about $\RR$ all day long.

For some reason I would like to give an example of a matrix.

\[
\begin{bmatrix}
1& 1& 0 \\
0& 1 & 2 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 \\
2 \\
3
\end{bmatrix}
=
\begin{bmatrix}
3 \\
8 \\
3
\end{bmatrix}
.
\]
This document uses two packages with the \verb|\usepackage| declaration above.
\verb|amssymb| is used for the blackboard bold $\RR$.  \verb|amsmath| is used
to make the matrices easier to type.



\end{document}

Here's the resulting output. If you want more information I find The Not So Short Introduction to LaTeX2e to be a close to exhaustive resource.

On Data Integrity


Digital Signatures Provide Security

In high school I read 1984 by George Orwell. You may remember that in this novel Winston Smith was employed to burn old newspapers. This was done in order to help support the ruling parties changing interpretation of events, if not to outright change the historical record. George Orwell could not have known about the digital way that information is preserved today.

Imagine what a current day Winston Smith would look like. This hypothetical Winston Smith wouldn't really need to burn anything. Simply altering the stored copies of data could drastically change people's perceptions. Just last week a librarian though it was odd that I was looking up something that wasn't digitally available. I could be very sure that the copy on the library shelf was the copy that the author intended. It would be nice if as much or more certainty could be provided for digital documents.

In fact it is possible to have a high degree of certainty that data has not changed. A digital signature provides mechanism to determine if information has changed. Once a document is signed then changing the document will invalidate the signature. It's also very difficult for anyone but the signing party to forge a signature. More difficult, in fact, than forging a handwritten signature.

There are other ways of preserving the integrity of data. The paper of Satoshi Nakamoto is perhaps one of the best digitally preserved documents. Blockchair provides a whole page that monitors this paper as hosted on several sites. They advertise the hash of the file and periodically check that it hasn't changed. There is also a copy included on the bitcoin blockchain. Embedding the document in the chain ensures the data haven't changed however it could be the case that a false copy was buried long ago. Digital signatures provide the advantage that the signer can first do their diligence and be reasonably certain that they're singing the correct copy.

As I have high certainty that I am hosting the original version of Satoshi Nakamoto's paper, I have signed this document.

Use Linux to Check the Signature

If you don't have a linux computer you should get one. Most linux installs come with Gnu Privacy Guard gpg which is software that implements the PGP (Pretty Good Privacy) protocol. To check the signature we will need three files. You can right click the links to download them.

Download all three files and put them in the same directory. I made a fresh directory so that it's less cluttered. The command ls lists all the files

/images/ls_check_bitcoin_sig.png

That's good, all three files are there. Now I import Darren's public key.

gpg-import-bitcoin-sig.sh (Source)

$gpg --import darren_tapp_public_key.pub

When you start typing the file name, most likely, you can press tab to auto-complete.

/images/gpg--import-check-bitcoin-sig.png

The picture above is the response to this command. I used a fresh gpg install and there was a warning about it being a fresh run. This warning is not serious. It's only important if we were expecting gpg to manage our trust. Finally, we can verify the signature.

gpg-verify-bitcoin-sig.sh (Source)

$gpg --verify bitcoin.sig bitcoin.pdf

Use the --verify flag and type the file with the signature and the file that we want to verify.

/images/signature-on-bitcoin-is-good.png

In this example we have verified a detached signature. That's when the signature is separate from the file. It's also possible to have a signature as part of the file or message.

Again the display shows a warning. If we informed gpg that we trusted my key that warning will go away.

10 Reasons Why You Should Install Linux


Number 9: Impress Your Friends and Colleagues

Time for a personal story. At Purdue my advisor said there was software that would compute what he asked me to calculate. I was able to look up the program that did the calculations and bang on the keyboard until it worked. I remembered that I ran the computer in run level 1 which didn't use a graphical interface. That way I was able to devote the whole computer to these calculations. These calculations could take days if they completed at all.

Number 8: Don't Waste Your Computer

It is generally true that the proprietary operating systems basically use more and more of your computer. Eventually they become so bloated that old hardware cannot be supported anymore. With linux it generally will run on anything. For extremely old hardware you might choose a version of linux that is less demanding.

Number 7: Tools Tools and More Tools

With linux you can really set up computers to do whatever computers do. Need a print server? Linux has you covered. Want to have a shared drive in your house? The tools to do that with linux are out there. These tools could be too costly otherwise.

Number 6: Set a Good Example

If you use linux, your children will naturally have questions about what you're doing. This can be a real opportunity to teach your children about computers. Being proficient at linux is a skill that jobs are based on. Also young people can be given a device where internet access has been restricted. I don't know what's the best age to introduce the internet to children, linux provides the option of providing computer expierence without the internet. That is assuming that your kids don't hack their own computer. If they do, then pivot that into a marketable skill.

Number 5: Generally Linux Doesn't Have Malware

Linux currently doesn't have a large market penetration. This means that it's not as an attractive target for hackers. That is, exploits of other operating systems might have more penetration and therefore a larger payoff.

Number 4: Linux Has a More Secure Architecture

Linux generally is operating with restrictive privileges. This means if a hacker does get control of a part of the computer there's still another step before the hacker can completely control the computer. This architecture can prevent malware from spreading. Since the source is open, anyone can inspect the code for vulnerabilities, and anyone can fix them. With a proprietary operating system the only people who can find vulnerabilities are paid to find them.

The command sudo is used to signal that expanded privileges are to be used.

/images/sandwich.png

(source)

Number 3: Herd Immunity

These two facts that there hackers have fewer targets and that those targets are hardened against attack provides something like herd immunity. Which is what happens when a sizable proportion of a population is vaccinated. Basically a virus cannot spread through a population when a high proportion of individuals are immune.

Number 2: Linux is Really Geared for Productivity

Since Linux is a product of the open source community all the tools that are needed for open source development are included with each install. Many programming languages that aren't included are just a command away to install. Most installs include Open Office which can replace other office products.

Number 1: You Will Actually Own Your Computer

By installing linux you will have full access to all of your computer. Open source software generally have very permissive terms of use. When you use a proprietary product the license terms generally very restrictive as to what you are allowed to do with your computer, and surveillance you must accept. When the source there are no restrictions.

If your computer updates, despite your protest, who really owns that computer?

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))