Impressive ideas from Craig Wright, Bitcoin is Turing complete

I'm finding I agree with Craig Wright at least theoretically on Bitcoin. Whether or not he is Satoshi is debatable but his approach and the fact that everything he conceptualized has a theoretical basis behind it which can be followed is great.

Some of his ideas include:

• Bitcoin is Turing complete (2 stack Pushdown Automata)
• Bitcoin is a Decider
• Forks are good
• Markets and incentives should determine future growth
• Evolutionary computation via PSOs (particle swarm optimization)
• Node count has zero relevance
• Move toward unlimited uncapped forks
• The miners set the rules
• Bitcoin is not to be a mesh network but is to be a small world network
• Lightening is a mesh network (any network with a distance of 3+ can always be sybil attacked). Bitcoin has a distance under 3.

So a market based strategy seems philosophically consistent. At the same time, if we rely on the market then due to Moore's Law if it holds then scaling isn't a problem. Simply buy better hardware as newer hardware is released. By buying better hardware economy of scale encourages prices to go down and the price of Bitcoin in theory provides an incentive for miners to be able to afford it. I mean it's theoretical, in practice miners might not be able to or might not want to keep supporting the network because other networks are better to them by cost benefit.

A 2 stack pushdown automata can simulate a Turing Machine

It has been proven that a 2 stack automata can simulate a Turing Machine. If Bitcoin is 2-PDA then it's certain that a Turing machine can be simulated. This would make Bitcoin Turing complete and confirms the claim of Craig Wright. At the same time, I'm a bit skeptical about whether or not Bitcoin is a decider, but even if theoretically this is the case, the root of my skepticism is in whether or not it's practical. I'm not certain that this is something practical at least for the current Bitcoin as we know it.

2 stack PDA would at least to my understanding allow you to stimulate a 2 tape Turing machine by storing the symbols where one simulated tape is read only. PDAs are basic computer science which freshmen students understand and 2 stack PDAs are just a specific kind of PDA which has 2 stacks. There are 3 stack PDAs also. Below is a video showing what a 2 stack PDA is:

And interesting to note there is an equivalence between CFG and PDA:

CFG for those who do not know, is context free grammar.

You can convert a context free grammar into a pushdown automata. This is important because a CFG can specify a programming language and a pushdown automata can implement a compiler. See the video below:

What this equates to is the fact that Bitcoin can simulate a Turing machine. By simulating a Turing machine using 2-stack PDA it can produce a programming language specification and compiler. It can then use this programming language and compiler to do everything Ethereum is doing at least theoretically but with the Proof of Work hash power and Bitcoin brand.

My own thoughts on Bitcoin security

In my opinion the security in Bitcoin is based almost entirely on economic assumptions. These economic assumptions include for example the assumption that an attacker will attack the network by buying hash power instead of through the developers or through subversion which is much cheaper. This is a problem often in cryptography where you develop a cipher which no one can break brute force (similar to how you cannot easily break Bitcoin by brute force hash power attacks), but like with cryptography the weak links in these secure information systems is 1) the implementation and 2) the people.

Bitcoin provides a basis of security by economic assumptions. I think this is a hypothesis worth testing as a security model but I also think it's breaking down precisely because while even if you have the perfect implementation, and lots of hash power, at the end of the day cooperative game theory indicates that the individuals do form cartels (miners, developers, even users) and sooner or later politics take over (as we see now in Bitcoin), and eventually the fate of the platform becomes either a political decision decided by the same interferences that influence political decisions in countries, or if rational a technical market decision where at least some attacks could be avoided.

The problem is that people aren't rational and this includes developers. Developers, users, even miners, are vulnerable to disinformation, to tricks, to bad ideas, all which can lead to a centralization and eventual breakdown in the security assumptions. I agree with Craig Wright on the Bayesian nature of security, and the fact is no system can ever be perfect due to the probabilistic nature of security. So for Bitcoin it merely has to provide in my opinion a security which raises costs for attackers to a level where attackers no longer deem it to be "worth it".

In any secure information system that I help to design or provide input, whether it be an economic approach (based on economic assumptions such as Proof of Work) or a different approach like Proof of Stake, at the end of the day the security rests on probabilities. We know something is truly safe by understanding risks. Bitcoin only has to be more secure (from a risk perspective) than traditional money such as cash in hand, cash in a bank, Paypal, credit cards, and to be honest I think Bitcoin is already approaching that level.

While I have a preference for Proof of Stake, the reasoning behind this is due to the fact that it is my current understanding that you can get the same practical security from Proof of Stake that you can from Proof of Work (from a risk perspective). The assumptions behind Proof of Stake is that you can trust the people to always act in the self interest of the network if the incentives guide them to do so. This is to say that witnesses are just as guided by incentives as miners, only the witnesses don't have to build massive server farms and or mining rigs to achieve security. In additional, sometimes Proof of Stake is better for scaling because it makes solving certain problems a lot easier when you have the flexibility to become efficient in terms of reducing the number of witnesses or verifiers.

For certain networks I would say Proof of Stake provides greater security and performance. This is because there is a trade off where you have to decide whether you want more security or more performance in some cases. If you're trying to do Ethereum for example which is some sort of "World Computer" or even just something similar to that, then I would say Proof of Stake makes more sense. This is because rather than providing "security by hashing" with CPUs which may well be general purpose, those same hardware can be repurposed to do more useful computation. On Ethereum we could see this with Golem and iExec which can at least theoretically repurpose the mining capacity of Ethereum into a distributed computation network paid for by fees.

References

1. https://en.wikipedia.org/wiki/Pushdown_automaton
2. https://en.wikipedia.org/wiki/Machine_that_always_halts
3. https://wikivisually.com/wiki/Total_Turing_machine
4. https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/cfg.html
5. https://en.wikipedia.org/wiki/Small-world_network
6. https://en.wikipedia.org/wiki/Proof-of-work_system
7. https://en.wikipedia.org/wiki/Proof-of-stake
8. https://en.wikipedia.org/wiki/Risk_matrix
9. https://en.wikipedia.org/wiki/Risk_assessment
10. https://en.wikipedia.org/wiki/Particle_swarm_optimization
11. https://en.wikipedia.org/wiki/Cooperative_game_theory
12. https://en.wikipedia.org/wiki/Evidence_under_Bayes_theorem