[HN Gopher] Turing Machines on Bitcoin
___________________________________________________________________
Turing Machines on Bitcoin
Author : GBiT
Score : 39 points
Date : 2021-09-18 08:12 UTC (1 days ago)
(HTM) web link (xiaohuiliu.medium.com)
(TXT) w3m dump (xiaohuiliu.medium.com)
| truth_machine wrote:
| So it looks like a better title would have been "saving the state
| of the turing machine on the bitcoin blockchain", as the claim of
| Turing completeness[1] seems disingenious - bitcoin script itself
| has no looping constructs and is decidedly non turing complete.
| The user has to call the contract as many times as necessary to
| ensure that Turning machine transitions between states, and the
| same user checks that the computation terminated.
|
| 1: The claim is "It is straightforward to adapt the Turing
| machine contract above to implement any other Turing machines, by
| simply changing the states, the symbols and transition function.
| Thus, any Turing machine can be simulated on Bitcoin,
| conclusively proving Bitcoin is Turing-Complete by definition.
| QED."
| shilch wrote:
| The presented solution does *not* loop inside bitcoin script
| itself, as you suggest, but outside whereby bitcoin
| transactions perform the state transfer. The machine runs for
| as long as someone pays for it (or it goes into accepting
| state) - which makes sense because if there was a one-time-fee
| for unbounded or potentially infinite runtime, you could create
| a program that never terminates. This can be compared to
| Ethereum where every step in execution costs fees and the
| caller needs to ensure that a sufficient amount of fees (gas)
| is paid.
| truth_machine wrote:
| Well, in Etherium, provided that sufficient amount of gas is
| paid for, I could have a contract that implements several
| (many?) iterations of the Turing machine - or any other
| computation.
|
| With the approach proposed in the article I need to have an
| external Turing-complete "controller" that would keep calling
| the contract.
|
| At this point, what is the benefit I am getting from having
| this "contract" at all? I would be better off with a just
| serializing the state of my machine and putting it into
| OP_RETURN, getting a much smaller blob to store on the chain.
| So I will save on the fees, could implement my Turing machine
| (or anything else, really) in the language of my choice, not
| constrained by the absence of loops and function calls.
|
| Article essentially uses bitcoin blockchain as a database (I
| hesitate to use the word "ledger"), and the use of "contract"
| is just a gimmick, seemingly introduced just to prop the
| absurd claim that bitcoin somehow becomes turing-complete
| when external turing-complete controller performs "contract
| calls".
| shilch wrote:
| In Ethereum, the caller specifies the gas amount beforehand
| to ensure that the execution finishes. In the presented
| bitcoin-based solution, the caller prepares the
| transactions beforehand that finish the execution; it then
| publishes the transactions.
|
| > At this point, what is the benefit I am getting from
| having this "contract" at all? I would be better off with a
| just serializing the state of my machine and putting it
| into OP_RETURN, getting a much smaller blob to store on the
| chain. > Article essentially uses bitcoin blockchain as a
| database
|
| This is just plain wrong and not at all what this article
| is about. In the article, a script is developed that
| enforces state transfer by the specified transition table,
| i.e. only a specific set of bitcoin transactions are
| allowed on the state, namely the ones from the transition
| table.
| truth_machine wrote:
| > This is just plain wrong and not at all what this
| article is about. In the article, a script is developed
| that enforces state transfer by the specified transition
| table, i.e. only a specific set of bitcoin transactions
| are allowed on the state, namely the ones from the
| transition table.
|
| So what is the article about, then? I started this thread
| disagreeing with the claim that material presented in the
| article somehow makes bitcoin turing complete and
| claiming that it, in fact, is not. You seem to be arguing
| this point with me, but I am not exactly sure what your
| (counter)arguments are.
| wildsatchmo wrote:
| This is true but the conclusion is over simplified. There is of
| course no looping constructs in script. This is by design as it
| guarantees the script can be executed without consuming
| excessive resources. Of course it can represent a single
| iteration of a larger program which is the point not being
| acknowledged.
|
| Interesting this account is 2 hours old and seems to have been
| created specifically to discredit this post. At the same time,
| another commenter here nullc is Greg Maxwell of Blockstream
| fame who has become notorious for this exact behavior. These
| fresh accounts with long winded explanations of the same
| opinion tend to appear when Greg is near.
| tromp wrote:
| With a separate transaction (over 6KB in size in their small
| example TM) needed for every TM transition, this can get rather
| expensive in fees. Except when you run it on Bitcoin BSV as they
| did.
| truth_machine wrote:
| Interesting to note that since sCrypt's "loop" construct simply
| unrolls the loop the constant number of times, proposed
| implementation will grow in size proportionally to the number
| of state transition rules (8 in the example in the article).
|
| So a contract with 50 transition rules (or just carelessly
| bumped up constant N in the source code) would be much larger
| as it has to repeat its inner loop N times -- and there is
| nothing you can do about it, as functions and function calls
| are syntactic sugar as well, and function bodies are
| immediately inlined at the call site.
| nullc wrote:
| This post is making fraudulent claims for the purpose of
| promoting the court adjudicated conman Craig Wright and his scam
| Bitcoin knockoff, "Bitcoin Satoshi Vision".
|
| Wright isn't particularly technically sophisticated and early on
| he made the error of claiming Bitcoin Script was turing complete
| on the basis of it having "multiple stacks". It transparently is
| not-- for it can only execute a number of operations fixed in
| advance, and lacks any looping, recursion, or similar and any
| script using the altstack can be turned into a slightly larger
| one that doesn't. Rather than retracting or recontextualizing the
| false claim, he's since just continued to double down on it,
| presumably because doing so helps further isolate the victims of
| his fraud from people who are technically competent.
|
| To support these repeated false claims, Wright eventually
| published "A Proof of Turing Completeness in Bitcoin Script",
| which turned out to be almost entirely plagiarized from a 1964
| paper by Corrado Bohm, the discovery of which apparently result
| in Wright being kicked out of CNAM.
| https://samwill102244.medium.com/anatomy-of-a-fraud-a-deep-d...
|
| Publications like the one here are intended to confuse the reader
| about the definition of turing completeness, and are instead just
| pointing out the same points that were made that turing
| completeness was unnecessary in the context of Bitcoin (
| https://www.youtube.com/watch?v=TGE6jrVmt_I /
| https://cyber.stanford.edu/sites/default/files/russelloconno...
| )which had been pointed out by the community back even before
| Wright ever knew of Bitcoin.
|
| The whole matter is doubly absurd because it would be completely
| trivial to make Bitcoin script actually turing complete and could
| be done without breaking compatibility with the existing network.
| But it is generally considered _expressly_ undesirable to do so
| by technical experts, because it would remove the existing
| guarantee that the runtime of all scripts can be determined and
| limited statically and because it wouldn 't actually increase the
| utility of the system.
|
| Recent court documents have exposed that Wright's activities are
| being funded by an advanced fee fraud scheme where he promises
| wealthy investors large amounts of "satoshi's bitcoins" in
| exchange for loans. Based on their own reports it appears the the
| total amounts taken are in the hundreds of millions of dollars
| now, or even more. This would all mostly just be sad and amusing
| except for Wright's propensity to file lawsuits against people
| who point out his fraud (such as myself-- he's sued me demanding
| 6 billion dollars in damages!)
|
| For more information on the BSV scam and Wright's fraudulent
| claims checkout https://www.reddit.com/r/bsvscam/ and
| https://bitcoinmagazine.com/business/op-ed-how-many-wrongs-m...
| xiphias2 wrote:
| ,, because it would remove the existing guarantee that the
| runtime of all scripts can be determined and limited statically
| and because it wouldn't actually increase the utility of the
| system.''
|
| While most of what you write is true (and I believe that the
| article was written in bad faith), as the article uses state
| changes in the Turing machine as Bitcoin transactions, it is
| trivial to statically check the runtime of a state change
| itself. Whether it's a useful addition to Bitcoin or not is
| another question though.
| nullc wrote:
| What the article is describing-- explicitly unrolling
| operations in advance and checking them in script-- has
| always been possible in Bitcoin and doesn't have anything to
| do with Turing completeness. It's only being promoted as
| something new or inventive as an element of a very strange
| con.
| cllun wrote:
| It's actually not possible on BTC
| ValiumMm wrote:
| It's just a crazy coincidence this 'con' man has the best
| scaling protocol. What are the chances of that. 1MegGreg.
| Honestly dude, just grow up and move on with something else in
| your life. Your dedication to just try and discredit BSV and
| CSW at this stage is just getting sad as every time BSV
| continuously climbs to new heights and proves you wrong by
| proving BSV actually works and scales. He's never asked for any
| money and only educated others. your toxic behavior will not go
| down in history well. get a life.
| cllun wrote:
| At least I can multiply numbers on BSV and fees are like
| 100.000 times lower then BTC fees. All thanks to Craig Wright.
| Guys, don't listen to the bullshit from nullc, he has a serious
| mental illness and is super pissed because Craig trolled him
| many times.
|
| What's an r-puzzle again? Some fancy reversed math?! Mh mh ...
| Hahahahahah.
| lolthishuman wrote:
| What's the point?
| reginold wrote:
| Could someone who likes this article share what they liked about
| it?
|
| I'm getting the idea that it's either 1. A fun proof of principle
| project 2. entertains more "compute" ideas on blockchains, kinda
| like Ethereum
| shilch wrote:
| I was aware of xhliu's work before. It's actually a big thing
| because Ethereum was created with the assumption that bitcoin's
| scripting language does not allow for state transfers (stateful
| contracts) and turing-complete computations. The advantage over
| account-based systems like Ethereum is scalability: Ethereum
| contracts are one central entity identified by their address,
| any access on the contracts must be serialised which leads to
| scaling issues with popular contracts. Bitcoin's UTXO model on
| the other hand is rather easy to parallelize; but scalable
| UTXO-based contracts also require a different design.
| [deleted]
| etaioinshrdlu wrote:
| The loop only has 8 iterations. Doesn't look particularly turing
| complete.
| truth_machine wrote:
| If you go over older posts on that medium blog, it seems to be
| a pattern with that particular author. He also has Conway's
| Game of Life implementation for 7x7 board, Rule 110
| implementation for the tape of 5 elements, "machine learning"
| article with matrices that are 5x5 -- all because his language
| has to unroll loops (as Bitcoin script cannot loop), and loops
| with more iterations are therefore either unfeasible or straigh
| up impossible in sCrypt.
|
| Despite that, he seems to be insistent that "Bitcoin is turing
| complete". Most curious.
| shilch wrote:
| I don't know what you're up to; your account is 30min old,
| was created just for commenting on this post, you appear to
| be very aware of this project and your comments show that you
| didn't understand the solution presented in the article. I
| already commented on the parent comment: The `loop` in sCrypt
| is a compile-time loop and just an implementation detail for
| the lookup in the transition table. The *actual looping*
| happens outside via bitcoin transactions whereby each
| transaction is a transition in the TM.
| https://news.ycombinator.com/item?id=28587465
| truth_machine wrote:
| I am very familiar with Bitcoin script, and it was rather
| easy to confirm that BSV is using the same set of opcodes,
| and sCrypt compiles to bitcoin script, with obvious
| conclusions. So I think that I actually understand the
| topic (and the article) very well, thank you very much.
|
| What am I up to? My beef with the article is quite simple:
| the article is clearly written with a singular goal in
| mind, to claim that "Bitcoin is turing complete", with is
| trivially verifiable falsehood, so I failed to resist
| "someone is wrong on the internet" impulse. Are you
| implying that I am arguing in the bad faith?
|
| There seem to be many other article by the same author
| making the same claim, with equally tenuous "proofs":
| https://xiaohuiliu.medium.com/play-conways-game-of-life-
| on-b... and https://xiaohuiliu.medium.com/turing-complete-
| rule-110-on-bi...
|
| So the question should rather be "what is he up to?".
| Probably just a promotion for his language or clickbait
| titles.
| shilch wrote:
| Then you either misunderstand or (intentionally?)
| misrepresent the article. The `loop` construct you're
| talking about has nothing to do with the author's proof,
| and neither does it "essentially use bitcoin blockchain
| as a database" as you have written somewhere else in the
| thread. For the interested reader, I have commented on
| these points where they were brought up.
|
| To explain the Game of Life contract you're linking to:
| The `loop`, again, is just an implementation detail to go
| over each field on the board in a *single* transaction.
| It's not part of any proof. The actual turing-complete
| element - letting the GoL run - happens outside: Each
| generation state transfer happens via a bitcoin
| transaction.
| truth_machine wrote:
| It seems to me that we actually agree on the main points.
|
| I do agree with you that single contract transaction is
| not turing-complete. I also agree that turing-complete
| element happens outside.
|
| My disagreement is with the following:
|
| 1. I disagree that "loop is just an implementation detail
| and is not part of any proof". In the GoL article there
| is a claim that (a)Game of Life board could simulate a
| turing machine and (b)article provides implementation of
| GoL board in sCrypt, therefore "Bitcoin in turing-
| complete". However, the board in article is limited (due
| to loop inlining) and cannot be made 1000s x 1000s (as
| required for the simulation of the turing machine)
| precisely because of the loop unrolling. I also note that
| author does not point out this limitation (in any of his
| articles, it seems) - the claims are always "we can
| simulate Game of Life, we can do Machine Learning, we can
| simulate Rule 110 automata" without any mention that
| these are toy examples that hardly do anything and can't
| scale even by an order of magnitude. So loop is indeed an
| implementation detail, but quite essential one, it seems.
|
| 2. More broadly, I am agruing against the claim that
| "Bitcoin is turing complete" made in this and other
| articles by the same author. But, again, it seems that on
| this point we are actually in agreement
| shilch wrote:
| These are two separate things. The `loop` construction /
| function or whatever it is called in the sCrypt language is a
| compile-time loop. That is, the body gets unrolled N times (8
| in this example). It's just an implementation detail for the
| lookup in the transition table. However, that is not part of a
| proof. The author is pretty clear that each transition in the
| TM is implemented as a bitcoin transaction.
| davidcbc wrote:
| This is the perfect representative of blockchain technology
| because it's a convoluted way to do something that is better done
| with existing technologies without using a blockchain.
| p4bl0 wrote:
| I'm glad I hit the reload button before writing my comment, I
| was going to say the exact same thing.
|
| EDIT: Okay blockchain zealots, downvote and flag my comment all
| you want, but if for once one of you could actually show a
| project that uses a blockchain (other than so-called
| "cryptocurrencies" which are essentially used as a speculation
| asset) and which cannot be implemented better and more
| efficiently with other technologies, that might be a little
| more interesting.
| fogof wrote:
| For what it's worth I think that if people were downvoting
| you because of your position, they would be downvoting the
| parent as well. They're downvoting you because saying "I was
| going to say the same thing" doesn't contribute to the
| conversation.
| burnished wrote:
| Two things: 1) 'me-too' comments tend to get downvoted here
| in an effort to promote substantive discussion. I think
| something gets lost in the gulf between an upvote and stating
| you agree but thems the breaks and 2) cryptocurrencies
| actually do get used by people that lack access to stable
| currencies. I asked about this myself. I don't think it
| changes the original assessment, but it is heartening to know
| that there is some real utility people are getting out of
| this tech.
| toolz wrote:
| Until you want do something completely distributed that
| requires trust. The runtime isn't great, but then again, what
| runtime is better that meets those requirements? ACH is far
| slower than many blockchain solutions, for example.
| dmitriid wrote:
| > Until you want do something completely distributed that
| requires trust.
|
| And then a _trustless_ system helps... how exactly?
|
| Oh, it doesn't, because you'll have to recreate all the trust
| institutions of the non-blockchain world. And, look, all
| blockchain "solutions" are busy doing exactly that.
| xiphias2 wrote:
| This is about Bitcoin SV (BSV), not Bitcoin (BTC)
| dominojab wrote:
| show me where in the whitepaper there is a limit to the block
| size defined as a unchangeable spec.
| shilch wrote:
| The solution presented in the article uses the bitcoin
| protocol. BSV is just one implementation of that. It could also
| work on BCH if some default limits were lifted, and
| (theoretically, not economically) possible on BTC.
| xiphias2 wrote:
| BSV and Bitcoin (BTC) are incompatible protocols, so this is
| just a straight out lie. Sure, it can be added to BTC as long
| as there's a use case and concencus for it, but so far there
| isn't.
| shilch wrote:
| > BSV and Bitcoin (BTC) are incompatible protocols
|
| Both implementations have a large intersection. Dogecoin,
| Litecoin and Dash also use the bitcoin protocol and should
| also work.
|
| > Sure, it can be added to BTC
|
| The presented solution does not require a protocol change.
| BSV is essentially the original bitcoin protocol (with few
| small exception); nothing was added to the protocol to
| implement the turing machine. BTC has some of the scripting
| opcodes disabled but they can either be implemented using
| other opcodes (no change) or they could be reenabled as a
| new SegWit deployment (requires change). However, the issue
| you'll run into in practice is that the reference
| implementation (Bitcoin Core) has very small limits set and
| discourages scripting. You'll have to find a miner that
| mines the custom scripting transactions. And, well, fees
| are another issue.
| dane-pgp wrote:
| > It could also work on BCH if some default limits were
| lifted
|
| Can you list what those default limits are, and how big the
| needed changes are?
| shilch wrote:
| I just wrote the comment and noticed that the scripting
| limits on BCH are actually a network rule and are not
| miner-configurable. So my statement that "it could also
| work on BCH if some default limits were lifted" is only
| correct in the sense that this number needs to be increased
| in a network upgrade: https://gitlab.com/bitcoin-cash-
| node/bitcoin-cash-node/-/blo...
| bob229 wrote:
| Blockchain is for cranks
___________________________________________________________________
(page generated 2021-09-19 23:02 UTC)