Cost of using complex logic in contracts

FlavienFlavien Member Posts: 7
A problem I can already see appearing from a contract design point of view, is that if you have complex operations in you contract, and by complex, I mean anything with time complexity higher than O(1), it becomes much harder to predict how many ethers it will take to run it.

Concatenating two strings of 10 characters will take more ethers than concatenating two strings of 5 characters. In practice, as a contract designer, you'll want to be able to provide an upper bound of how many ethers users to send with their transaction to be guaranteed that the contract will execute it. You might not be able to do that with anything else than trivial contracts.

I'd like to hear if the devs have a view on that.

Comments

  • arckearcke Member Posts: 34
    It seems wise as a contract developer to keep a tight check on how execution costs depend on input. The more this relation becomes unclear, the more risky the contract becomes for the contract itself or the user activating it.
  • yoyoyoyo Member Posts: 34 ✭✭✭
    An EtherUnit framework and offline debugger would be a nice community project IMO.
  • ChristianPeelChristianPeel Member Posts: 26
    edited January 2014
    Here are some things I'd love a pre-processing tool (maybe part of the debugging tools as yoyo says) to do.

    * For contract (and block chain) state X and inputs Y, what are the fees used, where X and Y are specified as input. I guess this one should be straightforward to do.
    * For random X and Y, what is the distribution of fees used. This also should be straightforward to do, since you can just create random X and Y and check the fee usage, and repeat for many random X,Y.
    * Say something more concrete, such as giving the upper bound that Flavien wants above. It seems like for certain classes of programs, this may be possible to automate. Seems like a fun CS problem.

    I'd love to understand this better; I'm sure there are details that I'm missing.
  • arckearcke Member Posts: 34
    Such a tool might work for a strict subset of contracts. In general automatically analyzing an algorithms complexity is undecidable. To calculate an exact fee distribution in an automatic way sounds even harder to do than just runtime complexity.

    https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no#comment40524_14969
  • yoyoyoyo Member Posts: 34 ✭✭✭
    A well designed contract will have to perform checks on its own balance during the processing and possibly abort the transaction midway, send an alert message out or degrade service.

    A feedback loop is a classic way to reach balance in complex systems.
  • FlavienFlavien Member Posts: 7
    >Say something more concrete, such as giving the upper bound that Flavien wants above. It seems like for certain classes of programs, this may be possible to automate. Seems like a fun CS problem.

    Well yes, it is possible to automate for programs that can be written in a non Turing-complete language. In other words, the only way to have a guaranteed upper bound on the fees for any program is by using a non Turing-complete language. With a turing complete language, it's equivalent to solving the halting problem, which means it's undecidable.

    If we have to restrict ourselves to using simple constructs that can be written without a turing complete language, why use a turing complete language in the first place?

    >A well designed contract will have to perform checks on its own balance during the processing and possibly abort the transaction midway, send an alert message out or degrade service.

    That's fine, but that's orthogonal to the issue I'm raising. I'm asking this: given a program, how can I guarantee that there exists a maximum fee F such that the contract is always ran to completion.

    Many programs don't have such number F, and fees can run to infinity.
  • PlatonicgapPlatonicgap Member Posts: 11
    edited January 2014
    Taking a step back, looking at this system, code should as a consequence become better written, as the cost that comes from decrease in efficiency will now be immediately visible as measured in units of value (Ether). A carrot/stick tight feedback loop will now be in place that was not there before. Major market incentive to write better and better code.
  • micersmicers Member Posts: 3
    Genetic algorithms solve these kinds of problems handily given enough time to find the right hill to climb.
Sign In or Register to comment.