Turing complete language vs non-Turing complete (Ethereum vs Bitcoin)

[Mike Hearn]

Yeah, SNARKs will be fun to play with when the kit is open sourced but I am very skeptical it'd be useful for anything production for a while. For one, it's unexplainable black magic. We'd need to write good tutorials and explanations of how it all works, basic stuff like that ...

[1713573237]

1713573237

[1713573237]

1713573237

[1713573237]

1713573237

[Vitalik Buterin]

And Vitalik Buterin has gained his high reputation not by chance. He seems to be one of the brightest minds in the community.

what has he actually implemented?

You're asking for a dev resume? Here you go then:

http://github.com/vbuterin/pybitcointools
http://github.com/vbuterin/node-sx
http://github.com/vbuterin/bitcoinjs-lib
http://multisig.info
http://github.com/ethereum/pyethereum

where is the source code that does all these magical things? smarts contracts, DAC, ... all of this is simply nonsense the way it is described.

http://ethereum.org/ethereum.html , the section on "applications"

[Gavin Andresen]

How do transaction fees work in Ethereum?

One of the non-obvious reasons Bitcoin works is transaction fees are based on the size (in bytes) of the transaction. And since there are no loops executing a transaction, CPU usage is bound by transaction size.

If CPU usage to verify a transaction is NOT related to the transaction size, then you open yourself up to denial-of-service attacks. Like:

Create an Ethereum transaction with a (huge!) fee that will pay for 60 seconds of CPU execution time.
... but craft it so execution takes 61 seconds (or, heck, make it an infinite loop, maybe you'll tickle a bug in the execution termination code).

Now broadcast it.  It will be rejected for insufficient fee, but only after peers have wasted 60 seconds of CPU time. And if the transaction is rejected, the attacker won't pay the fee.

Then tweak it slightly and broadcast it again, maybe from a different IP address if you got banned for bad behavior.

I haven't thought deeply about whether or not there is a way to punish the attacker; my first thought would be to publish the attacker's transaction and take the fee but ignore any other effects of the transaction, but you'd have to be careful to design THAT mechanism so it couldn't be abused.

[coinrevo]

You're asking for a dev resume? Here you go then:

That was a bit mean from me. I appreciated the work more, before someone put in the idea of corporate control. that is not opensource/anarchism. anyway, if everyone plays fair, its a free market.

cryptocurrencies have as much to do with economics as it has to do with cryptography/computer security/etc. One problem is one can't pick up sound economic thinking from a textbook, as modern economics is mostly nonsensical drivel. And it does not help to understand how in the future human societies will be organized based on principles of cryptocurrencies.

this thread is a good example. it discusses various technical questions, but does not touch at all on the questions of contracts, and why we even would want smart contracts/DAC's and what they are good for. say for example all contracts with the government, which can be changed more or less arbitrarily by those in power, starting with control of money supply. so the question is how this new arising form of social organization fits in with the existing civilization, which is build on nation states + a rather strangely constructed institution named United Nations + other institutions like Worldbank, IMF, SWIFT, G8, etc.

[behindtext]

One of the non-obvious reasons Bitcoin works is transaction fees are based on the size (in bytes) of the transaction. And since there are no loops executing a transaction, CPU usage is bound by transaction size.

If CPU usage to verify a transaction is NOT related to the transaction size, then you open yourself up to denial-of-service attacks. Like:
...

this is precisely why a turing complete scripting language is a bad idea in the context of cryptocurrencies: it is highly non-trivial to put bounds in place to prevent or mitigate exploits.

[coinrevo]

this is precisely why a turing complete scripting language is a bad idea in the context of cryptocurrencies: it is highly non-trivial to put bounds in place to prevent or mitigate exploits.

satoshi designed the stack engine for a very good reason. it doesn't look like this will ever be done in bitcoin itself. the risk is too high for that kind of experimentation to occur now. overall the system/network has probably much more inertia than initially thought. from which I infer that there will be several serious candidates in the long term.

[Vitalik Buterin]

How do transaction fees work in Ethereum?

One of the non-obvious reasons Bitcoin works is transaction fees are based on the size (in bytes) of the transaction. And since there are no loops executing a transaction, CPU usage is bound by transaction size.

If CPU usage to verify a transaction is NOT related to the transaction size, then you open yourself up to denial-of-service attacks. Like:

Create an Ethereum transaction with a (huge!) fee that will pay for 60 seconds of CPU execution time.
... but craft it so execution takes 61 seconds (or, heck, make it an infinite loop, maybe you'll tickle a bug in the execution termination code).

Now broadcast it.  It will be rejected for insufficient fee, but only after peers have wasted 60 seconds of CPU time. And if the transaction is rejected, the attacker won't pay the fee.

Then tweak it slightly and broadcast it again, maybe from a different IP address if you got banned for bad behavior.

I haven't thought deeply about whether or not there is a way to punish the attacker; my first thought would be to publish the attacker's transaction and take the fee but ignore any other effects of the transaction, but you'd have to be careful to design THAT mechanism so it couldn't be abused.

You're (very understandably ) coming at this from too much of a Bitcoin perspective, where scripts are attached to transactions and transaction outputs and transactions can either pass or fail. That's not how Ethereum works. In Ethereum, you have entities called contracts, where contracts have their own balances, and are activated every time you send a transaction (think: money with an optional message attached) to them. The contract has 16 computational steps for free to give it wiggle room to determine whether a transaction is even worth processing; after this, every computational step that the contract takes costs it 1x BASEFEE (or more for specialized data access or crypto ops). If the contract goes bankrupt halfway through the computational process, it just stops halfway through. Here is the critical part: unlike is the case with Bitcoin, here the transaction does not "fail". The transaction still succeeds; the contract just ends up sitting there out of gas halfway through some long calculation instead of doing anything interesting. If you send a second transaction to the same contract immediately after, it will halt right after the 16 step grace period (or maybe more if the second transaction is sending some non-negligible amount of ether to refill it).

That was a bit mean from me. I appreciated the work more, before someone put in the idea of corporate control. that is not opensource/anarchism. anyway, if everyone plays fair, its a free market.

cryptocurrencies have as much to do with economics as it has to do with cryptography/computer security/etc. One problem is one can't pick up sound economic thinking from a textbook, as modern economics is mostly nonsensical drivel. And it does not help to understand how in the future human societies will be organized based on principles of cryptocurrencies.

this thread is a good example. it discusses various technical questions, but does not touch at all on the questions of contracts, and why we even would want smart contracts/DAC's and what they are good for. say for example all contracts with the government, which can be changed more or less arbitrarily by those in power, starting with control of money supply. so the question is how this new arising form of social organization fits in with the existing civilization, which is build on nation states + a rather strangely constructed institution named United Nations + other institutions like Worldbank, IMF, SWIFT, G8, etc.

Okay, time for me to put my armchair econo-socio-politico-philosopher hat on.

We're not trying to be a corporate controller. You may notice that unlike Freicoin, Devcoin and the like, the Ethereum organization is NOT collecting any kind of tax or issuance share forever; there is only a small one-time fundraise/premine at the start. This essentially sets in stone what I have come to realize is an important principle in business and social organization: small organizations, like startups, usually have to be dictatorial and have one or a few dominant players pushing a coherent vision with appropriate incentivization to help the process along. In the long term, however, structures that aim to be basic institutions of society (currency being one of the most important) should be controlled by no one. I feel like this compromise approach well represents the feelings of the Bitcoin community. The problem we have today is that organizations either try to either start decentralized, and often unfortunately fail, or start centralized, and then get drunk with power (or get co-opted by entities that are already drunk with power) and never bother actually implementing the decentralization step.

We do spend a lot of time thinking about exactly how these new decentralized structures can help either augment or replace existing systems, and how they fit into the categories of standard economics. At this point, we are still very much in the speculative fiction stage, but perhaps you might find these interesting:

http://bitcoinmagazine.com/9435/markets-institutions-currencies-new-method-social-incentivization/
http://blog.ethereum.org/2013/12/31/bootstrapping-a-decentralized-autonomous-corporation-part-i/
http://blog.ethereum.org/2013/12/31/bootstrapping-an-autonomous-decentralized-corporation-part-2-interacting-with-the-world/
http://blog.ethereum.org/2013/12/31/bootstrapping-a-decentralized-autonomous-corporation-part-3-identity-corp/
http://bitcoinmagazine.com/6528/what-proof-of-stake-is-and-why-it-matters/
http://bitcoinmagazine.com/8640/an-exploration-of-intrinsic-value-what-it-is-why-bitcoin-doesnt-have-it-and-why-bitcoin-does-have-it/
http://blog.ethereum.org/2014/02/01/on-transaction-fees-market-based-solutions/

What I like about the Ethereum community so far is precisely the level of interest in economic issues and willingness to look for solutions with a fresh eye that I'm seeing. We are all committed Bitcoiners, and believe in the principle of decentralization; however, at the same time we understand well why centralized systems have come to exist and the positive role they have often served in pushing humanity forward even while committing those evils of which we are all very aware. Thus, the emphasis is precisely on figuring out what the benefits are that centralization brings, and seeing if we can come up with incentive structures that provide most of the benefits without most of the drawbacks. A good analogy here is data structures in computer science. We have arrays, where a 1000-item array takes 1 step to modify or access a value but 500 steps to insert or delete, and we have linked lists, where a 1000-item list takes 500 steps to access a value but only 1 step to insert or delete. However, more recently we invented the concept of trees, where you can have a 1000-item tree where inserting, modifying, accessing and deleting all take no more than 10 steps -  a compromise that gives us nearly the best of both worlds. Those are the kinds of cleverly rigged and elegant solutions to problems that we are trying to seek.

[Gavin Andresen]

Okey dokey... so how do fees work in Ethereum?

Or do you have some other clever distributed way of preventing flood-the-system-with-bogus-contracts DoS attacks?

[k99]

Okey dokey... so how do fees work in Ethereum?

Or do you have some other clever distributed way of preventing flood-the-system-with-bogus-contracts DoS attacks?

Here is my understanding how it works, hope Vitalik can give a more precise answer.

A contract is associated with a balance. If the balance is 0 the contract will not be executed. A contract gets executed by sending a transaction to a contract. The tx needs to be funded, so I assume you cannot send a 0 Ether tx to a contract. That way you prevent to flood execution of unfunded contracts. So you have 2 times a fee in place to prevent attacks. The tx needs to be funded with a fee to activate a contract and the contract need to have some balance to get executed.

If you have an endless loop, the loop consumes with every step some fee and after a limited time the contract run out of balance and stop.

About fees: http://blog.ethereum.org/2014/02/01/on-transaction-fees-market-based-solutions/

[Vitalik Buterin]

Okey dokey... so how do fees work in Ethereum?

Or do you have some other clever distributed way of preventing flood-the-system-with-bogus-contracts DoS attacks?

Here's the relevant part of my post above highlighted for clarity:

In Ethereum, you have entities called contracts, where contracts have their own balances, and are activated every time you send a transaction (think: money with an optional message attached) to them. The contract has 16 computational steps for free to give it wiggle room to determine whether a transaction is even worth processing; after this, every computational step that the contract takes costs it 1x BASEFEE (or more for specialized data access or crypto ops). If the contract goes bankrupt halfway through the computational process, it just stops halfway through.

A contract is associated with a balance. If the balance is 0 the contract will not be executed. A contract gets executed by sending a transaction to a contract. The tx needs to be funded, so I assume you cannot send a 0 Ether tx to a contract.

Actually, you can send a 0 ether tx to a contract, although that tx will still cost the sender a TXFEE.

The tx needs to be funded with a fee to activate a contract and the contract need to have some balance get executed.

Precisely; although with the proviso that the first 16 computational steps in contract execution are free, so if a contract is decently written you can't involuntarily send transactions to it to bankrupt it.


Here's an example also (assume BASEFEE = 1 ether for convenience)

CONTRACT: [ PUSH 0 JMP ], balance: 1000

The contract is pretty much the simplest possible infinite loop script; it's the equivalent of "10: DO_NOTHING; 20: GOTO 10"

Now, suppose that someone sends it a transaction with value 10 ether (this tx will cost the sender 110 ether due to the TXFEE):

TX: [ ADDRESS, 10, [], v, r, s]

Step 1: { Counter: 0, Index pointer: 0, Stack: [], balance: 1010 }
Step 2: { Counter: 1, Index pointer: 2, Stack: [ 0 ], balance: 1010 }
Step 3: { Counter: 2, Index pointer: 0, Stack: [], balance: 1010 }
...
Step 16: { Counter: 15, Index pointer: 2, Stack: [ 0 ], balance: 1010 }
Step 17: { Counter: 16, Index pointer: 0, Stack: [], balance: 1009 }
Step 18: { Counter: 16, Index pointer: 2, Stack: [ 0 ], balance: 1008 }
...
Step 1025:  { Counter: 16, Index pointer: 0, Stack: [], balance: 1 }
Step 1026:  { Counter: 16, Index pointer: 2, Stack: [ 0 ], balance: 0 }
Step 1027: ERROR NOT ENOUGH FUNDS HALT

The contract now has a balance of 0 ether, so if someone tries to send that transaction again, the second time around execution will stop at step 17 rather than 1027.

[Peter Todd]

Vitalik: Is that a true fee that goes to miners, or a sacrifice?

[maaku]

Okey dokey... so how do fees work in Ethereum?

Or do you have some other clever distributed way of preventing flood-the-system-with-bogus-contracts DoS attacks?

Gavin, as far as I can tell there is no such thing as a bogus contract in Etherium. You pay a one-time fee to register a contract - setup an execution context for a script in the validation state of every node - but script representing that contract is not validated in any way. There's no way for a contract to be rejected, so there's no way to "DoS with bogus contracts".

[coinrevo]

We're not trying to be a corporate controller.
We are all committed Bitcoiners, and believe in the principle of decentralization;

What we need is a structured marketplace, where people who buy and sell cryptocurrencies meet, based on same principles. that's what I'm working on. as long as some market principles are met, demand and supply can establish a fair price of any currency. price is then the estimate of future value.

there is only a small one-time fundraise/premine at the start.

We don't have a process for tracking fundraisers. There is no way to know what happened with past funds. It would be much better to build a plattform which can be re-used and to actually build out the intermediation process. the alt-coin market is pretty fragile at the moment.

[Gavin Andresen]

Thanks, k99 and Vitalik, that helps clear it up.  I've put "On Transaction Fees, And The Fallacy of Market-Based Solutions" on my to-think-about-deeply list.

I'm curious about this, though:

Precisely; although with the proviso that the first 16 computational steps in contract execution are free, so if a contract is decently written you can't involuntarily send transactions to it to bankrupt it.

If my contract needs more than 16 computational steps to execute, then other people CAN send transactions to it to intentionally bankrupt it? That is what I was worrying about when I said "publish the attacker's transaction and take the fee but ignore any other effects of the transaction, but you'd have to be careful to design THAT mechanism so it couldn't be abused."

[coinrevo]

I've put "On Transaction Fees, And The Fallacy of Market-Based Solutions" on my to-think-about-deeply list.

..which is this article
http://blog.ethereum.org/2014/02/01/on-transaction-fees-market-based-solutions/

[Mike Hearn]

Re: the article. Saying mining is not a market because if it becomes dominated by a tiny number of players fees might go up seems backwards - surely higher prices due to lack of competition is exactly how you'd expect a market to behave? At any rate, I question whether the additional few minutes would make any real difference to most users. For all the miles of forum posts the block chain algorithm generates, there are really only two speeds that matter for the majority of cases: instant and not instant.

The fact that fees would trend towards the cost of accepting a transaction into a block is a well known issue that has been studied for a long time. The block chain is indeed a commons (as is a lot of other important aspects of the Bitcoin infrastructure). There are ways to fund public goods, fortunately.

I've expected for a long time that fees will end up being used in several different ways simultaneously:

• A tiny fee of either bitcoins (assigned to miners) or priority (burned) on every transaction, as a simple load management mechanism. I hope to see these fees largely collapse or disappear in future in favour of priority, as Bitcoin gets more sophisticated and scales better. These fees would not be large enough to support proof of work based security.
• Occasional large fees for proofs of sacrifice. These would be too rare to support proof of work based security.
• Occasional large fees for mining assurance contracts, at whatever level proves to be the best balance as determined by the market (perhaps intermediated by insurance companies).

[k99]

Thanks, k99 and Vitalik, that helps clear it up.  I've put "On Transaction Fees, And The Fallacy of Market-Based Solutions" on my to-think-about-deeply list.

I'm curious about this, though:

Precisely; although with the proviso that the first 16 computational steps in contract execution are free, so if a contract is decently written you can't involuntarily send transactions to it to bankrupt it.

If my contract needs more than 16 computational steps to execute, then other people CAN send transactions to it to intentionally bankrupt it? That is what I was worrying about when I said "publish the attacker's transaction and take the fee but ignore any other effects of the transaction, but you'd have to be careful to design THAT mechanism so it couldn't be abused."

As Vitalik mentioned a 0 Ether tx could be sent to a contract to activate it and cause some cost for the contract if it runs more then 16 steps. If the contract balance is 0 it will stop there.
A flooding with 0 Ether tx is protected due the tx fee.
As far as I understand a contract gets feeded by the tx activating it. So if a contract has been run out of its own contract funds, only tx with sufficient tx value will cause the contract to run (> 16 steps).
For me it is not clear why a contract holds balance on its own and why the tx value is not enough to control the contract execution. If a contract is funded (contract balance >0) there is no incentive to send a tx with a value there (paying for the execution).

[coinrevo]

Saying mining is not a market because if it becomes dominated by a tiny number of players fees might go up seems backwards - surely higher prices due to lack of competition is exactly how you'd expect a market to behave?

Surely mining does not suffer from lack of competition. Its rather how pools shift power from consumer to producer. much economic research is spent on studying monopols, oligopols, polypols (1, few, many). oligopols often exist in resource markets like oil and electricity, because of scaling effects. its not that surprising we see the same in bitcoin. a miners tax is probably not a bad idea to redirect excess profits.

[Come-from-Beyond]

In Ethereum, you have entities called contracts, where contracts have their own balances, and are activated every time you send a transaction (think: money with an optional message attached) to them. The contract has 16 computational steps for free to give it wiggle room to determine whether a transaction is even worth processing; after this, every computational step that the contract takes costs it 1x BASEFEE (or more for specialized data access or crypto ops). If the contract goes bankrupt halfway through the computational process, it just stops halfway through.

How r blockchain reorgs handled? Computational steps can't be rolled back nor blockchain can be re-rolled from block 0, so u r supposed to store blockchain snapshots each N-th block, which is quite expensive.
Can't a Finney attack be combined with a very long-running transactions to DoS all nodes? If a miner earns all block fees then even without a Finney attack a malicious miner could include a lot of long-running transactions into their block to slow down processing of the next block / transactions.

[crabel]

I've put "On Transaction Fees, And The Fallacy of Market-Based Solutions" on my to-think-about-deeply list.

..which is this article
http://blog.ethereum.org/2014/02/01/on-transaction-fees-market-based-solutions/

Be very careful about non market pricing mechanisms. The problem with price determination is about discovering the price. While you can set the price, ala a Pigovian tax, you are doing so without knowing the actual value of the item being assessed.

There is much more going on here than the simplistic models being proposed. I'm reminded of Bastiat's "Seen and unseen". The market possess many methods that enforce discipline. Such things are the emergence of practices of what is proper. Things like common law (written and unwritten) emerge from propriety. The complexity contained within these relationships greatly affects the price and value of action within that market.

Satoshi was very wise to leave as much up to the market and the individuals that comprise each market. Here he accessed one of the greatest information aggregators humanity ever devised. For the Etherum developers I suggest you read an article by Hayek, "The Use of Knowledge in Society". You can get a copy here: http://www.econlib.org/library/Essays/hykKnw1.html

Here is an amusing and informative video by Mike Munger explaining the information problem in externalities: http://www.learnliberty.org/videos/externalities-when-is-a-potato-chip-not-just-a-potato-chip

I am from the energy field and have dealt a great deal with understanding the impact of externalities on the production and consumption of energy. I found that invariably any policy that is founded on presuming to know the social value ALWAYS creates a net social harm. I now appreciate the Coasian approach to resolving these externalities through the creation of proerty rights (markets) even this approach is not fail proof. Please look at the work of Coase and Hazzlet. There are two parts to Coase's theorem about externalites. Both need to be understood before effective policy is developed.