Impressive ideas from Craig Wright, Bitcoin is Turing complete

in #bitcoin7 years ago (edited)

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
Sort:  

I REALLY appreciate your breakdowns @dana-edwards and I've always been impressed with your analysis of the Crypto world in general. I was on the Crypto show with Rodger Ver a few weeks back when this information broke. The more I learn about Bitcoin, the more fantastic the possibilities become. Thank you for the breakdown... and SteemON!

Imgur

I like forks only when it doesn't split the coin :) or when its on my plate ahaha. He has alot of great points tbh.

The reason I like his lectures is he is very logical. While I might not agree with some of his opinions, his theoretical foundation and basis are there. A lot of people criticize Craig Wright for his personality, or the way he communicates, or his politics, but one thing no one has been able to deny is that as a computer scientist, cybersecurity expert and mathematician, everything he says is based in the theory.

If you open a computer science freshman textbook you learn about pushdown automata. If you open a cybersecurity freshman textbook you learn about Bayes and risk management. If you open an economic textbook you learn about markets and if you open a networking textbook you'll learn about small world, mesh, etc.

None of what he has said is inaccurate. His ideas on PSOs aren't inaccurate, I just don't see the practicality of some of his work. I think running simulations and models using PSOs makes a lot of sense if you're thinking about multi-agent systems and how they scale via "survival of the fittest" in an economic sense but again is it practical?

thanks for your well thought out information - i am learning a lot very quickly and opinions are not facts, i like that you lay out the facts in a logical way, as you see it now. Keep well and rock on-D

Agreeing with him makes sense only if you are a miner and mining fees is your business. If you are in Bitcoin for "sound money" than none of it makes any sense even in theory. And letting miners set the rules is just disastrous idea.

Did you watch the video? What about the theory didn't make sense? Not talking about his political interests.

I was watching it live. And man, it was a disaster! His whole speech was about "how to centralize Bitcoin" and "how to present it to the public so it doesn't appear so". Except the part where he told everyone who couldn't afford the expensive hardware that is needed for his plan to fuck off. Didn't really hide it there.

You have a deep misunderstanding. The source of decentralization in Bitcoin is the market (economic incentive structure) not the devices. If you cannot afford expensive hardware then let that go because the people who can afford expensive hardware will mine. People with the most money will always have the best hardware from which to mine. Mining is always for "rich people" who can afford to burn money to support the security of the network.

If you are worried about centralization around hash power then that ultimately happens no matter what strategy you use if it's Proof of Work. You could let everyone mine on CPUs and eventually it centralizes around pools and farms, You could let everyone mine on whatever physical devices you want and the fact that it is a physical device is centralizing. Only the economic incentives control how centralized or decentralized it is, in my opinion.

Core in my opinion has the incentives wrong. For instance Craig Wright endorses unlimited forks (decentralizing), larger blocks (which could lead to a higher price as a side effect), if Bitcoin becomes more valuable (again economics) then the cost of hardware isn't an issue unless you want every user to also be a miner which doesn't make any sense or have any impact on security that I can see.

If every user is a miner or not, the security in my opinion isn't going to scale based on how many individual persons are mining with their smart watches. Diminishing returns in my opinion there, but hey I could be wrong.

Tell me why I'm wrong?

There is no right or wrong, just different outcomes. Why do you want mining to become centralized?
I don't want it to be centralized to the point where a single mining pool or even single mining farm holds more than 50% of the hash power. Why should I trust these companies to scale the Bitcoin when they can reach consensus without my vote or without anyone's to that matter. They came to be because mining Bitcoin was profitable. You think that makes them competent enough to give control to them?

My point is mining is always centralized. It's centralized around the physical devices, which means the physical device manufacturers. It's centralized in the same way plastic manufacturing companies have advantages in making shovels. The point is the economics are what provokes the decentralizing force, not "hash power" or mining.

If you get the economics right then you get an acceptable balance between security and performance. Mining itself is supposed to provide security and keep the network going but it's not by itself enough to promote decentralization. The entire incentive structure promotes decentralization or centralization according to the merits of it's game theoretical basis.

I get your point and I don't agree. Still I find it hard to believe that you want to trust these guys to get the economics right. Did you watch the full video (not only the Craig Wright part)? The points they are making make sense only coming miner's community mouths because they are in the fee market and they want what's the most profitable for them. And history is showing us that it's not the best thing for Bitcoin in the most cases.

I think of it like this, the secure information system has any security at all based not on how much hashing power but based primarily on the incentive structure. It's a game theory problem, not a technical (hashing power) problem, and because the problem is framed as some sort of technical problem, people seem to think that making the mining rigs cheaper is somehow going to change the security.

Based on what game theory?

Which problem you are talking about? You think that there is a security issue?
And mining rigs are becoming cheaper as the is technology evolving. How much hash per $100 you can get now compared to 3 years ago?

My point is if you want security to be in the amount of people who participate then you're moving security to the edges. The truth is, if you have good economic incentives then the behavior of the participants will at least in theory conform to protect the security of the network because it will be in their best interest to do it.

Mining isn't really going to ever be decentralized on the level of everyone being a miner is my point. That is a false possibility in the first place. I'm not sure anyone seriously believes grandma will be mining Bitcoins on her smart phone along with billions of people in developing countries. We have to at least be realistic about what is likely to happen and that future is extremely unlikely.

In my opinion the security of Bitcoin is based on the structure of economic incentives, not the amount of hash power miners generate or how many miners there are. You can have security with Proof of Stake greater than Bitcoin no matter what the hashrate of Bitcoin if the Proof of Stake has a better incentive structure.

Coin Marketplace

STEEM 0.35
TRX 0.12
JST 0.040
BTC 70601.11
ETH 3576.21
USDT 1.00
SBD 4.78