7 ms·

The idea of turing complete crytocontracts is super exciting, but I understand why Satoshi didn't add a turing complete language in Bitcoin. Turing complete co

by malanj 13y ago

The idea of turing complete crytocontracts is super exciting, but I understand why Satoshi didn't add a turing complete language in Bitcoin. Turing complete contracts add a whole new level of complexity (e.g. http://en.wikipedia.org/wiki/Halting_problem http://en.wikipedia.org/wiki/Halting_problem). I guess many (most?) could be solved by limiting computation time - it it's still a scary world. If one just considers how many significant issues the much more basic Bitcoin protocol has managed to hide (e.g. transaction malleability). If implementing a "basic" protocol is that hard - the idea of a turing complete protocol is formidable!

a-priori 13y ago
In Ethereum, you need to fund a contract in order for it to perform computations, and the amount that gets charged to a contract depends on the amount of work it does. So if someone were to write an infinite loop, for example, eventually the contract would run out of money and die. The halting problem is not a practical issue with Ethereum, because the system doesn't care, in advance, whether or not a contract will halt. It will just run it to find out.
- anfedorov 13y ago
  How does this work as the network scales? If I understand it correctly, every node needs to execute every contract. This means that for some large enough number of nodes, it must either cost more for the network to perform the computation than any constant cost of execution, or the cost of contracts must vary by the size of the network executing them. Could someone more knowledgeable about the project explain more?
  - nullc 13y ago
    They propose fixed mandatory fees. https://github.com/ethereum/wiki/wiki/%5BEnglish%5D-White-Paper#fees https://github.com/ethereum/wiki/wiki/%5BEnglish%5D-White-Pa... Nodes can't be compensated for this— only the single miner who chose to burden the chain with the contract. Everyone else has to go along for the ride (or skip verifying it and hope that the anonymous miner wasn't lying). This is one of the reasons Bitcoin has very purposefully eschewed contracts which are computationally expensive to execute. You can almost always perform a computationally expensive contract externally to the system and bind it with a hashlock or multisig, in any case. The inability of the a consensus system to perform IO to outside world usually demands those techniques in any case.
    - runeks 13y ago
      It would be really cool if they could figure out a way to adapt the fees of various operations to match their costs. Fixed fees will almost certainly not do this. Imagine someone develops a chip that can calculate ECDSA operations 10 times faster, consuming 100 times less electricity. In a well-functioning market, the consequence of this would be that the price of ECDSA operations would drop, to reflect the fact that they now cost less to verify. With fixed fees, this isn't possible, and there is no financial incentive to optimize any given operation, without optimizing all operations simultaneously.
      - DennisP 13y ago
        In the latest paper, they have a fixed price in "gas" per operation, but the market determines price per unit of gas. http://gavwood.com/Paper.pdf http://gavwood.com/Paper.pdf
        runeks 13y ago
        Right, it's relative price fixing, which is what my post described a problem with.
        DennisP 13y ago
        Ah, gotcha. I guess in principle you could use a similar market approach for each type of resource. That might work out better long-term.
  - bashcoder 13y ago
    > How does this work as the network scales? If I understand it correctly, every node needs to execute every contract. Such a network can grow to some extent, but how can it truly scale? There is limited scaling, of course, but node requirements increase as traffic increases, and there is no scalability through distribution of computational resources. So the more work the system does, the stronger each node needs to be. If the answer to this is, "No problem - we'll just make it more expensive," then the required computational resources could be purchased with the very cryptocurrency that is generated from the system. At that point, it seems to me that the snake eats its own tail. Regardless, before we declare that there can be any democratization enabled by this tech, I think we need to ask the question, "How does this not transfer even more power to those with the most computational power?" Put another way, it seems this is tailor-made for Google and Amazon, not an organization of Joe Publics, each with a couple extra GPU's installed. It's still going to be about the "haves" and the "have-nots." I'm happy to be proven wrong on any of these thoughts. I just think that if we were talking about any other tech, this computational model would not be considered scalable in any meaningful way.
    - drcode 13y ago
      Yes, an ethereum contract might cost 50 cents to run. Now try calling some lawyers and ask them how much it typicaly costs to defend a contract in our traditional court system... it will probably be a number 100000% higher than 50 cents. Cryptocontracts are great for Joe Publics.
  - 3rd3 13y ago
    Would someone mind explaining the concept of contracts in Ethereum? Specifically how it’s related to paper contracts, for example my rental contract, in which all parties (me, the landlord and the jurisdiction) agree upon several rules like "appartment for money" and "violation leads to punishment by the jurisdiction". Who/what are the parties, what are the rules and what mechanisms prevent violations?
    - a-priori 13y ago
      A contract in Ethereum is a basically a software agent that runs on a Bitcoin-like blockchain. It's a computer program attached to a bank account that is triggered by, e.g., transferring money into the contract's account. The program can do calculations, read and write from memory, as well as transfer money to other accounts and a few other things. From there you can write contracts that do things similar to their paper, real-world counterparts. Say you wanted to set up a one-year rental contract. The landlord would create the contract and you, the tenant, would transfer your security deposit into it. The contract would have logic something like this whenever it is activated: if rent money was just deposited transfer the money to the landlord mark last month as paid else if payment is more than 30 days overdue transfer security deposit to landlord end contract else if one year has elapsed since contract started transfer security deposit to tenant end contract This contract will keep track of whether a tenant is up-to-date on their rent payments. As long as the contract survives, the tenant is allowed to stay in the unit. The idea is that instead of a contract being enforced by the good will of the participants, or a court if that fails, it's enforced by the logic programmed into the contract itself.
      - Andrew_Quentin 13y ago
        else if one year has elapsed since contract started transfer security deposit to tenant end contract This ignores the reason for a deposit in the first place. What if the carpets were burned in that year? Some of the deposit needs to be kept by the landlord. How does etherium know the carpet was burned? If the landlord says so, then the landlord may be lying. For simpler operation - if rent not paid - then end contract - that sounds like it adds no benefit. No need for a program to tell you the contract has ended. This is very useful to prove authenticity of a contract and for very simple contracts as well such as a bet. If there can be any sort of dispute about the contract though I don't see how it can be useful again save for authenticity.
vbuterin 13y ago
Actually, we kind of discovered that, unless we radically cripple our model (eg. by removing the first-class-citizen property) Turing-completeness is basically irrelevant either way. https://github.com/ethereum/wiki/wiki/Whitepaper-2-Draft#computation-and-turing-completeness https://github.com/ethereum/wiki/wiki/Whitepaper-2-Draft#com... I basically just chose to keep it in there because it makes a few contract types easier.
- maaku 13y ago
  Vitalik, are you aware of the construct of total functional programming languages? It is possible to have recursion without giving up solution to the halting problem.
  - vbuterin 13y ago
    Pure functional programming? Yeah. But those aren't magic. Whenever you have conditional branching, the halting problem reintroduces itself. (def (collatz-depth x) (if (= x 1) 0 (if (= (mod x 2) 0) (+ 1 (collatz-depth (/ x 2))) (+ 1 (collatz-depth (+ 1 (* x 3))))))) is intractable no matter what language you use to write it in.
    - steveklabnik 13y ago
      Total functional programming is different than purely functional programming: http://en.wikipedia.org/wiki/Total_functional_programming http://en.wikipedia.org/wiki/Total_functional_programming
      - vbuterin 13y ago
        Ah okay, interesting, thanks for the link. So it's basically a maximally powerful non-Turing-complete language. I would argue that the section in our v2 whitepaper on non-Turing-complete languages still covers the fallacy behind that: you can still have exponential blowup, so you still need a concept of maximum steps, but then once you have a concept of maximum steps there's little benefit to restricting the programming language.

by malanj 13y ago

a-priori 13y ago

In Ethereum, you need to fund a contract in order for it to perform computations, and the amount that gets charged to a contract depends on the amount of work it does. So if someone were to write an infinite loop, for example, eventually the contract would run out of money and die. The halting problem is not a practical issue with Ethereum, because the system doesn't care, in advance, whether or not a contract will halt. It will just run it to find out.

anfedorov 13y ago
How does this work as the network scales? If I understand it correctly, every node needs to execute every contract. This means that for some large enough number of nodes, it must either cost more for the network to perform the computation than any constant cost of execution, or the cost of contracts must vary by the size of the network executing them. Could someone more knowledgeable about the project explain more?
- nullc 13y ago
  They propose fixed mandatory fees. https://github.com/ethereum/wiki/wiki/%5BEnglish%5D-White-Paper#fees https://github.com/ethereum/wiki/wiki/%5BEnglish%5D-White-Pa... Nodes can't be compensated for this— only the single miner who chose to burden the chain with the contract. Everyone else has to go along for the ride (or skip verifying it and hope that the anonymous miner wasn't lying). This is one of the reasons Bitcoin has very purposefully eschewed contracts which are computationally expensive to execute. You can almost always perform a computationally expensive contract externally to the system and bind it with a hashlock or multisig, in any case. The inability of the a consensus system to perform IO to outside world usually demands those techniques in any case.
  - runeks 13y ago
    It would be really cool if they could figure out a way to adapt the fees of various operations to match their costs. Fixed fees will almost certainly not do this. Imagine someone develops a chip that can calculate ECDSA operations 10 times faster, consuming 100 times less electricity. In a well-functioning market, the consequence of this would be that the price of ECDSA operations would drop, to reflect the fact that they now cost less to verify. With fixed fees, this isn't possible, and there is no financial incentive to optimize any given operation, without optimizing all operations simultaneously.
    - DennisP 13y ago
      In the latest paper, they have a fixed price in "gas" per operation, but the market determines price per unit of gas. http://gavwood.com/Paper.pdf http://gavwood.com/Paper.pdf
      - runeks 13y ago
        Right, it's relative price fixing, which is what my post described a problem with.
        DennisP 13y ago
        Ah, gotcha. I guess in principle you could use a similar market approach for each type of resource. That might work out better long-term.
- bashcoder 13y ago
  > How does this work as the network scales? If I understand it correctly, every node needs to execute every contract. Such a network can grow to some extent, but how can it truly scale? There is limited scaling, of course, but node requirements increase as traffic increases, and there is no scalability through distribution of computational resources. So the more work the system does, the stronger each node needs to be. If the answer to this is, "No problem - we'll just make it more expensive," then the required computational resources could be purchased with the very cryptocurrency that is generated from the system. At that point, it seems to me that the snake eats its own tail. Regardless, before we declare that there can be any democratization enabled by this tech, I think we need to ask the question, "How does this not transfer even more power to those with the most computational power?" Put another way, it seems this is tailor-made for Google and Amazon, not an organization of Joe Publics, each with a couple extra GPU's installed. It's still going to be about the "haves" and the "have-nots." I'm happy to be proven wrong on any of these thoughts. I just think that if we were talking about any other tech, this computational model would not be considered scalable in any meaningful way.
  - drcode 13y ago
    Yes, an ethereum contract might cost 50 cents to run. Now try calling some lawyers and ask them how much it typicaly costs to defend a contract in our traditional court system... it will probably be a number 100000% higher than 50 cents. Cryptocontracts are great for Joe Publics.
- 3rd3 13y ago
  Would someone mind explaining the concept of contracts in Ethereum? Specifically how it’s related to paper contracts, for example my rental contract, in which all parties (me, the landlord and the jurisdiction) agree upon several rules like "appartment for money" and "violation leads to punishment by the jurisdiction". Who/what are the parties, what are the rules and what mechanisms prevent violations?
  - a-priori 13y ago
    A contract in Ethereum is a basically a software agent that runs on a Bitcoin-like blockchain. It's a computer program attached to a bank account that is triggered by, e.g., transferring money into the contract's account. The program can do calculations, read and write from memory, as well as transfer money to other accounts and a few other things. From there you can write contracts that do things similar to their paper, real-world counterparts. Say you wanted to set up a one-year rental contract. The landlord would create the contract and you, the tenant, would transfer your security deposit into it. The contract would have logic something like this whenever it is activated: if rent money was just deposited transfer the money to the landlord mark last month as paid else if payment is more than 30 days overdue transfer security deposit to landlord end contract else if one year has elapsed since contract started transfer security deposit to tenant end contract This contract will keep track of whether a tenant is up-to-date on their rent payments. As long as the contract survives, the tenant is allowed to stay in the unit. The idea is that instead of a contract being enforced by the good will of the participants, or a court if that fails, it's enforced by the logic programmed into the contract itself.
    - Andrew_Quentin 13y ago
      else if one year has elapsed since contract started transfer security deposit to tenant end contract This ignores the reason for a deposit in the first place. What if the carpets were burned in that year? Some of the deposit needs to be kept by the landlord. How does etherium know the carpet was burned? If the landlord says so, then the landlord may be lying. For simpler operation - if rent not paid - then end contract - that sounds like it adds no benefit. No need for a program to tell you the contract has ended. This is very useful to prove authenticity of a contract and for very simple contracts as well such as a bet. If there can be any sort of dispute about the contract though I don't see how it can be useful again save for authenticity.

vbuterin 13y ago

Actually, we kind of discovered that, unless we radically cripple our model (eg. by removing the first-class-citizen property) Turing-completeness is basically irrelevant either way. https://github.com/ethereum/wiki/wiki/Whitepaper-2-Draft#computation-and-turing-completeness https://github.com/ethereum/wiki/wiki/Whitepaper-2-Draft#com... I basically just chose to keep it in there because it makes a few contract types easier.

maaku 13y ago
Vitalik, are you aware of the construct of total functional programming languages? It is possible to have recursion without giving up solution to the halting problem.
- vbuterin 13y ago
  Pure functional programming? Yeah. But those aren't magic. Whenever you have conditional branching, the halting problem reintroduces itself. (def (collatz-depth x) (if (= x 1) 0 (if (= (mod x 2) 0) (+ 1 (collatz-depth (/ x 2))) (+ 1 (collatz-depth (+ 1 (* x 3))))))) is intractable no matter what language you use to write it in.
  - steveklabnik 13y ago
    Total functional programming is different than purely functional programming: http://en.wikipedia.org/wiki/Total_functional_programming http://en.wikipedia.org/wiki/Total_functional_programming
    - vbuterin 13y ago
      Ah okay, interesting, thanks for the link. So it's basically a maximally powerful non-Turing-complete language. I would argue that the section in our v2 whitepaper on non-Turing-complete languages still covers the fallacy behind that: you can still have exponential blowup, so you still need a concept of maximum steps, but then once you have a concept of maximum steps there's little benefit to restricting the programming language.