Bitcoin Forum
January 22, 2019, 07:09:51 AM *
News: Latest Bitcoin Core release: 0.17.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 »  All
  Print  
Author Topic: Turing completeness and state for smart contract  (Read 11987 times)
ilpirata79
Sr. Member
****
Offline Offline

Activity: 353
Merit: 250


View Profile
April 06, 2016, 09:59:16 AM
 #1

If ethereum technology becomes fondamental and useful, would it be wise to modify bitcoin to incorporate its fundamental changes which are the turing completeness and the possibility for contracts to have a state? (as well as a easier scripting language as serpent).

Best regards,
ilpirata79
1548140991
Hero Member
*
Offline Offline

Posts: 1548140991

View Profile Personal Message (Offline)

Ignore
1548140991
Reply with quote  #2

1548140991
Report to moderator
1548140991
Hero Member
*
Offline Offline

Posts: 1548140991

View Profile Personal Message (Offline)

Ignore
1548140991
Reply with quote  #2

1548140991
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1548140991
Hero Member
*
Offline Offline

Posts: 1548140991

View Profile Personal Message (Offline)

Ignore
1548140991
Reply with quote  #2

1548140991
Report to moderator
1548140991
Hero Member
*
Offline Offline

Posts: 1548140991

View Profile Personal Message (Offline)

Ignore
1548140991
Reply with quote  #2

1548140991
Report to moderator
1548140991
Hero Member
*
Offline Offline

Posts: 1548140991

View Profile Personal Message (Offline)

Ignore
1548140991
Reply with quote  #2

1548140991
Report to moderator
fbueller
Sr. Member
****
Offline Offline

Activity: 412
Merit: 250


View Profile
April 06, 2016, 01:12:08 PM
 #2

The simple answer is no - what you suggest will never happen. Despite both being blockchains, they have nothing to do with eachother - they have totally different designs and goals.

Bitwasp Developer.
nihilnegativum
Sr. Member
****
Offline Offline

Activity: 435
Merit: 250


––Δ͘҉̀░░


View Profile WWW
April 07, 2016, 12:02:28 PM
 #3

If it becomes useful, I imagine there will soon be a eth-like sidechain on bitcoin.
ilpirata79
Sr. Member
****
Offline Offline

Activity: 353
Merit: 250


View Profile
April 07, 2016, 12:53:14 PM
 #4

If it becomes useful, I imagine there will soon be a eth-like sidechain on bitcoin.

Maybe a sidechain which is merge-mined with bitcoin. I don't see that like an impossible outcome...
at that point, what would the usefulness of Ethereum be?



By the way, it already exists. It's called rootstock. How is it that some people see it as a joke?

ilpirata79
Sr. Member
****
Offline Offline

Activity: 353
Merit: 250


View Profile
April 07, 2016, 01:07:26 PM
Last edit: April 08, 2016, 11:00:48 AM by ilpirata79
 #5

So the "question" now might be:

is it better to have to different chains, i.e. bitcoin and rootstock, with the second being a superset, in terms of functionalities, of the first, or is it best to just have the second (so just ethereum)?

I tend to think that is better to split them, but I don't have any real evidence to support that assertion.

Some thoughts however:
pros (for splitting): two different chains can be tweaked differently (e.g. block time) to achieve different objectives.
cons (for splitting): one single chain is easier to mantain, to debug, to develop, to upgrade compared to two (this may be a strong cons).

What do you guys think however?
tucenaber
Sr. Member
****
Offline Offline

Activity: 337
Merit: 250


View Profile
April 20, 2016, 04:07:46 AM
 #6

There will be no public block chain with Turing complete scripts ever, because that would mean that absolutely any algorithm would be accepted in a script, including non-terminating ones. A smart contract with an infinite loop would be a very bad thing.

But, but Etherium is Turing complete, isn't it???  No it is not, it can't be. It would be killed by DOS in no time. The language may be Turing complete in theory, but since the system must guarantee that all scripts terminate in finite time (I think they do it by requiring that each instruction has a cost) it is not Turing complete in practice. They could have used a total language in the first place, where you have a guarantee that every program terminates.

I know this isn't really an answer to the OP question but I wanted to point it out Wink
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2632
Merit: 1855



View Profile
April 20, 2016, 04:39:09 AM
Last edit: April 20, 2016, 08:26:22 AM by gmaxwell
Merited by Last of the V8s (1)
 #7

On the pedantic points, I echo what tucenaber just said-- and I could not say it better.  (Also, see #bitcoin-wizards past logs for commentary about total languages. I also consider that a major useful point for languages for this kind of system).

People looking for "turing complete" smart contracts inside a public cryptocurrency network are deeply and fundamentally confused about what task is actually being performed by these systems.

It's akin to asking for "turing complete floor wax".   'What does that? I don't even.'

Smart contracts in a public ledger system are a predicate-- Bitcoin's creator understood this. They take input-- about the transaction, and perhaps the chain-- and they accept or reject the update to the system.   The network of thousands of nodes all around the world doesn't give a _darn_ about the particulars of the computation,  they care only that it was accepted.  The transaction is free to provide arbitrary side information to help it make its decision.

Deciding if an arbitrarily complex condition was met doesn't require a turing complete language or what not-- the verification of a is in P not NP.

In Bitcoin Script, we do use straight up 'computation' to answer these questions; because that is the simplest thing to do, and for trivial rule sets, acceptably efficient.  But when we think about complex rule-- having thousands and thousands of computers all around the world replicate the exact same computation becomes obviously ludicrous, it just doesn't scale.

Fortunately, we're not limited to the non-scalablity-- and non-privacy-- of making the public network repeat computation just to verify it.  All we have to do is reconize that computation wasn't what we were doing from the very beginning, verification was!

This immediately gives a number of radical improvements:

"The program is big and I don't want to have to put it in the blockchain in advance." ->  P2SH, hash of the program goes into the public key, the program itself ends up being side information.

"The program is big but we're only going to normally use one Nth of it-- the branches related to everything going right"  -> MAST, the program is decomposed into a tree of ORs ans the tree is merkelized. Only the taken OR branches ever need to be made public; most of the program is never published which saves capacity and improves confidentiality.

"The program is big, and there are fixed number of parties to the contract. They'll likely cooperate so long as the threat of the program execution exists."  -> Coinswap transformation; the entire contract stays outside of the blockchain entirely so long as the parties cooperate.

"The program is big, and there are fixed number of parties to the contract, and I don't care if everything just gets put back to the beginning if things fail." -> ZKCP; run _arbitrary_  programs, which _never_ hit the blockchain,  and are not limited by its expressive power (so long as it supports hash-locked transactions and refunds.)

"The program is kinda big, and we don't mind economic incentives for enforcement in the non-cooperative case"  -> challenge/response verification; someone says "I assert this contract accepts," and puts up a bond. If someone disagrees, they show up and put up a bond to say it doesn't. Now the first party has to prove it (e.g. but putting the contract on the chain) or they lose their bond to the second party, if they're successful they get the bond from the second party to pay the cost of revealing the contract.

"The program is too big for the chain, but I don't want to depend on economic incentives and I want my contract to be private." ->  ZKP smart contracts; PCP theorem proves that a program can be proved probabilisticly with no more data than log the size of its transcript.  SNARKS use strong cryptographic assumptions to get non-interactive proofs for arbitrary programs which are constant size (a few hundred bytes). Slowness of the prover (and in the case of snarks, trusted setup of the public key-- though for fixed sets of participants, this can be avoided) limit the usefulness today but the tech is maturing.

All of these radical improvements in scalablity, privacy, and flexibility show up when you realize that "turing complete" is the wrong tool, that what our systems do is verification, not computation.  This cognitive error confers no advantage, outside of marketing to people with a fuzzy idea of what smart contracts might be good for in the first place.

More powerful smart contracting in the world of Bitcoin will absolutely be a thing, I don't doubt. But the marketing blather around ethereum isn't power, it's a boat anchor-- a vector for consensus inconsistency and decentralization destroying resource exhaustion and incentives mismatches. Fortunately, the cognitive framework I've described here is well understood in the community of Bitcoin experts.
JackH
Sr. Member
****
Offline Offline

Activity: 381
Merit: 250


View Profile
April 21, 2016, 12:20:59 PM
 #8

gmaxwell is the point of payment channels/level-2 layers not to enable more advanced uses of "smart-contracts" ?

From my understanding the Script language will be used to form contracts, but all computation of such will sit outside the blockchain itself.

What I am missing is however the smart-contract construction on this layer and how it will look exactly. Is MAST going to be required before we have a "real" smart contract interface?

<helo> funny that this proposal grows the maximum block size to 8GB, and is seen as a compromise
<helo> oh, you don't like a 20x increase? well how about 8192x increase?
<JackH> lmao
go1111111
Full Member
***
Offline Offline

Activity: 185
Merit: 100


View Profile
April 23, 2016, 07:18:37 AM
 #9

I thought Greg's description above was really good and was curious how Vitalik would reply so I posted it over in the Ethereum subreddit. For anyone else interested, he gave a detailed response at https://www.reddit.com/r/ethereum/comments/4g1bh6/greg_maxwells_critique_of_ethereum_blockchains/d2e24sy

Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2072
Merit: 1007

Newbie


View Profile
April 23, 2016, 08:00:16 AM
 #10

There was (is?) a limit on number of ops in a Bitcoin block, looks like predicates are not as efficient as some Bitcoin devs think.
marcelus
Sr. Member
****
Offline Offline

Activity: 297
Merit: 250


View Profile
April 23, 2016, 09:12:06 AM
 #11

I thought Greg's description above was really good and was curious how Vitalik would reply so I posted it over in the Ethereum subreddit. For anyone else interested, he gave a detailed response at https://www.reddit.com/r/ethereum/comments/4g1bh6/greg_maxwells_critique_of_ethereum_blockchains/d2e24sy



It's state that matters. You can't have true interoperability without it.
mmitech
Legendary
*
Offline Offline

Activity: 1106
Merit: 1000


things you own end up owning you


View Profile
April 23, 2016, 11:04:35 AM
 #12

Really interesting read, still my biggest fear about Ethereum is if their scaling plans fails, then we will have just another fancy "dead horse". 
KoinMaster
Sr. Member
****
Offline Offline

Activity: 323
Merit: 250


View Profile
April 23, 2016, 12:19:09 PM
 #13

Really interesting read, still my biggest fear about Ethereum is if their scaling plans fails, then we will have just another fancy "dead horse". 

However if ETH will succeed in its scaling plans(which I am sure it will) then we will end up having an even bigger corpse than a "dead horse" in the crypto-universe: a dead dinosaur called BTC....


 
 
           ▄████▄
         ▄████████▄
       ▄████████████▄
     ▄████████████████▄
    ████████████████████      ▄█▄                 ▄███▄                 ▄███▄                 ▄████████████████▀   ▄██████████

  ▄▄▄▀█████▀▄▄▄▄▀█████▀▄▄▄     ▀██▄             ▄██▀ ▀██▄             ▄██▀ ▀██▄             ▄██▀                   ██
▄█████▄▀▀▀▄██████▄▀▀▀▄█████▄     ▀██▄         ▄██▀     ▀██▄         ▄██▀     ▀██▄         ▄██▀        ▄█▄          ▀██████████████▄
████████████████████████████       ▀██▄     ▄██▀         ▀██▄     ▄██▀         ▀██▄     ▄██▀          ▀█▀                        ██
 ▀████████████████████████▀          ▀██▄ ▄██▀             ▀██▄ ▄██▀     ▄█▄     ▀██▄ ▄██▀                                       ██
   ▀████████████████████▀              ▀███▀                 ▀███▀       ▀█▀       ▀███▀      ▄███████████████████████████████████▀
     ▀████████████████▀
       ▀████████████▀
         ▀████████▀
           ▀████▀
║║


║║
.
.

║║
██
║║
.
.

║║
██
║║
.
║║


║║
ilpirata79
Sr. Member
****
Offline Offline

Activity: 353
Merit: 250


View Profile
April 23, 2016, 02:01:32 PM
Last edit: April 23, 2016, 05:33:43 PM by ilpirata79
 #14

Really interesting read, still my biggest fear about Ethereum is if their scaling plans fails, then we will have just another fancy "dead horse".  

However if ETH will succeed in its scaling plans(which I am sure it will) then we will end up having an even bigger corpse than a "dead horse" in the crypto-universe: a dead dinosaur called BTC....

Don't forget BTC has a reasonable network effect at its advantage and can incorporate ethereum features through merge-mined sidechains. I bet that this will be the outcome:
Bitcoin used for monetary transactions and a sidechain used for smart-contracts/bots.


Best regards,
ilpirata79
KoinMaster
Sr. Member
****
Offline Offline

Activity: 323
Merit: 250


View Profile
April 23, 2016, 07:39:26 PM
 #15

Really interesting read, still my biggest fear about Ethereum is if their scaling plans fails, then we will have just another fancy "dead horse".  

However if ETH will succeed in its scaling plans(which I am sure it will) then we will end up having an even bigger corpse than a "dead horse" in the crypto-universe: a dead dinosaur called BTC....

Don't forget BTC has a reasonable network effect at its advantage and can incorporate ethereum features through merge-mined sidechains. I bet that this will be the outcome:
Bitcoin used for monetary transactions and a sidechain used for smart-contracts/bots.


Best regards,
ilpirata79

Sorry no offense, but ETH is better in every possible regard: speed, scalability, encryption, smart contracts etc. ETH will encorporate BTC ultimately as a side-chain out of respect for historical purposes.


 
 
           ▄████▄
         ▄████████▄
       ▄████████████▄
     ▄████████████████▄
    ████████████████████      ▄█▄                 ▄███▄                 ▄███▄                 ▄████████████████▀   ▄██████████

  ▄▄▄▀█████▀▄▄▄▄▀█████▀▄▄▄     ▀██▄             ▄██▀ ▀██▄             ▄██▀ ▀██▄             ▄██▀                   ██
▄█████▄▀▀▀▄██████▄▀▀▀▄█████▄     ▀██▄         ▄██▀     ▀██▄         ▄██▀     ▀██▄         ▄██▀        ▄█▄          ▀██████████████▄
████████████████████████████       ▀██▄     ▄██▀         ▀██▄     ▄██▀         ▀██▄     ▄██▀          ▀█▀                        ██
 ▀████████████████████████▀          ▀██▄ ▄██▀             ▀██▄ ▄██▀     ▄█▄     ▀██▄ ▄██▀                                       ██
   ▀████████████████████▀              ▀███▀                 ▀███▀       ▀█▀       ▀███▀      ▄███████████████████████████████████▀
     ▀████████████████▀
       ▀████████████▀
         ▀████████▀
           ▀████▀
║║


║║
.
.

║║
██
║║
.
.

║║
██
║║
.
║║


║║
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2632
Merit: 1855



View Profile
April 23, 2016, 10:01:15 PM
 #16

It's state that matters. You can't have true interoperability without it.
That also seems confused to me. Bitcoin and Bitcoin smart contracts have state-- if they didn't they wouldn't work at all. But rather than having sprawling state that requires random access to the system and hiding the true cost of providing this state, Bitcoin transactions flow state information from inputs to output.

The result is a model which is more like monads in purely functional languages: A transaction collects some state (txin selection), creates new state (new txouts), and the scriptsig/witness proves that the state transition was permitted.

Similarly to the move to thinking in terms of verification instead of computation, this insight often permits transformations that improve scalablity.  E.g. instead of storing the state explicitly in outputs, in some applications you can store a hash tree over the state; then subsequent actions can simply show access and update proofs. This kind of compaction can't be used in all cases, but where it can it's very efficient.  I spoke some of these advantages on the subject of code above (e.g. MAST), but they apply no less for state.

An example of elided state, a simple one without state updates, is https://blockstream.com/2015/08/24/treesignatures/ which shows the construction of fairly efficient, pretty private, accountable multisig that avoids putting all of the applicable public keys into the blockchain.

The advantages of this kind of construction will be more clear to more people as future script enhancements restore functionality in Bitcoin script that was disabled; which will bring back the ability to enforce constraints on state carried from inputs to outputs.
go1111111
Full Member
***
Offline Offline

Activity: 185
Merit: 100


View Profile
April 24, 2016, 04:59:46 AM
 #17

There is one area where I think Ethereum might have a smart contract advantage, that I haven't seen Bitcoiners discuss. It looks to me like writing Ethereum contracts is more 'natural' to developers than writing complex script constructions using Bitcoin. I haven't written scripts in either, but as a dev this is the sense I get by looking at their scripts. Is this a legit problem? If so, have the Bitcoin devs thought much about how to make Bitcoin script construction more accessible for normal devs (maybe either via dev tools, or by some simplified declarative language that compiles into Script)?
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2632
Merit: 1855



View Profile
April 24, 2016, 06:53:47 AM
 #18

Writing smart contracts is inherently not 'natural' software development similar to how writing legal contracts are not 'natural' prose. The requirements and implications are quite different.

The kinds of data the software works with is different. The resource costs are radically different. The execution environment is necessarily very different-- how often do you write ordinary programs whos execution gets rolled back in a reorg or could "run out of gas"? The implications of failure are typical fairly different. The interactions with privacy are very different than ordinary software development.

Often the "simply written" smart contracts are grievously insecure-- I guess you could say that they're not that smart. Smiley

There can be cases for wanting to use legacy software in a smart contract context, for interoperability or rapid prototyping-- but the ethereum model isn't particular good for that either (it imposes enormous overheads on software compiled from traditional languages).

Effectively, when you create a de novo smart contract you are designing a cryptographic protocol. It turns out that it's fiendishly hard to do this, even for experts, and the science of creating good tools for it is yet unsolved. (Though it's one of the long term problem areas that I'm funding people to work on.)

I think the Bitcoin technical community has some good starting premises about what kinds of constructs facilitate making tools that make it more feasible to construct new smart contracts with less than super-human effort-- things like having top level building blocks that work like monotone boolean functions, so that you can safely compose standardized parts without understanding the internals and your software can reliably analyze the space of possible outcomes.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2072
Merit: 1007

Newbie


View Profile
April 24, 2016, 07:20:25 AM
 #19

programs whos execution gets rolled back in a reorg

This problem doesn't arise when we write smart-contracts for Bitcoin/Ethereum.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2632
Merit: 1855



View Profile
April 24, 2016, 07:42:18 AM
 #20

This problem doesn't arise when we write smart-contracts for Bitcoin/Ethereum.
Yes it does. A 'smart contract' that never interacts with anything outside the network (including users) is pointless. The smart contract itself may not set the history rewrite, but the possibility of them must be accounted for in the design of the contract.
Pages: [1] 2 3 »  All
  Print  
 
Jump to:  

Bitcointalk.org is not available or authorized for sale. Do not believe any fake listings.
Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!