Solution for Loops(for, foreach) in RIDE – Ilya Smagin
It’s not uncommon that RIDE doesn’t have any cycle/for/goto primitives. That fact constantly frustrates developers who need to traverse a collection, calculate the sum of an array, filter list of items of match an array of signatures against an array of public keys. However, this limitation does not come from an oversight or unwilingness to devilver proper developer experience: it’s a matter of environment limitation: the execution engine(not the programming language) needs to stay Non-Turing Complete.
But first, a bit of history.
Turing Completeness
The definition of the term is tied to a mysterious Turing machine which manipulates symbols on a strip of tape according to a table of rules. But what’s in that for 2019? Simply put, turing completeness of a language means the ability to encode any algorithm within the language’s primitives. Any means any — including brutforce hacking an ellipic-curve signatures, or even an infinite one, that will never provide result, like:
while(true)
Blockchain, RIDE
Virtually all languages you can find are turing complete, including, of course Solidity. The problem is the environment, namely blockchain. Noone wants decentralized network to evaluate an infinite algorigthm — that will break many things, to say the least.
That’s why Ethereum has Gas — the ability to charge executor on a per-instruction basis at runtime. This is a solid plain-simple solution, but when it meets environment with neccessary gas limit, it results in failed transactions due to either underprovided gas or even gaslimit, frustrating users which still need to pay for it.
Within Waves, we adopt different model: RIDE is explicitly non-turing complete, doesn’t have cycles and loops in a language, no backward-GOTO-like operator in its bytecode. That allows us to calclulate computation costs upfront and reject not even the execution, but the deployment of a dApp itself.
Inheritetnly, given an array of an elements without knowing its size at compile time, you can’t estimate compleixty.
let arr = getString(this,"key").extract().split("|")
arr.foreach(a => a + "A") # imaginary code
In this example the complier hits last line and has no idea what arr is and therefore can’t estimate the execution cost of the line, and neither do you, by the way.
If you put a list traversal inside a list traversal, things get ugly polynomyally faster. Let’s also get an intense computation in a map
let arr = getString(this,"key").extract().split("|")
arr.map
}
}
That’s N³ signature verifications with N being unknown. You might say something like “Just don’t allow loops in a loops!” or “Just don’t allow sigVerify in a loop!”, but if you think carefully, you’ll see how poor decision that is. Regardless of the fact that it doesn’t solve any problem, doesn’t allow for proper cost estimation, it makes the language non-context free, which makes it very poor design decision. Global problems need global solutions.
If we could estimate the cost of every expression, we are good. So, let’s add the parameter: amount of iterations:
let arr = ...
arr.map(10, )
What if the array is bigger than 10? Let’s throw exception then.
But if the paratemer is of type Integer, that is also unknown:
let arr = ...
let steps = arr.size()arr.map(steps, )
Therefore, we need something different.
But unless you are MIT Professor in Computer Science and you try to invent a solution for computation problem, there’s a great chance you are reinventing a wheel. Even worse, you can be on a path of inventing a square one.
Macros for a programming language are syntactic sugar on steroids. When a compiler sees a macros, it rewrites the code it encloses and then compiles the actual output. They are extremely useful due to inability to express things within existing language constructions, but also extremely hard to debug when things do wrong. It’s so great that we don’t have a debugger.
One higher-order functon existing in tons of languages is a family of fold , foldLeft and foldRight . Scala’s one looks like this:
def fold[A](col: List[A], z: A, op: (A, A) ⇒ A): A
def foldLeft[B](col: List[A], z: B, op: (B, A) ⇒ B): B
def foldRight[B](col: List[A], z: B, op: (A, B) ⇒ B): B
where z is the value we start folding with, and then subsequently “modify” it with op function and the next element in collection.
These functions are extremely powerful: One can define sum , filter , zip , exists— almost anything — just with them. No need for foreach .
Fist, some intuition on how to use it:
func sum(a:Int, b:Int) = a + b
let arr = [1,2,3,4,5]
let sum = FOLD<5>(arr, 0, sum) # result: 15
This reads: make up to 5 steps, on each step take an accumulation result, the next element, apply sum function to the pair, return accumulation restult.
The filter function:
func filterStep(a: Int, accumulated: List[Int]) =
if (a % 2 == 0) then a :: acumulated else accumulatedlet arr = [1,2,3,4,5]
let evens = FOLD<5>(arr, 0, filterStep) # result: [2,4]*
* You will actually get [4,2], but this is solveable
When compiling this, the compiler could simply unwrap:
let result = FOLD<5>(arr, acc0, function)
to something like(mind the * above):
let restult = }}}}}
Again, you will never see this code. Well, that’s exaclty what you’ll see in Decompiler at least at first, but if you decompile stuff, this means you are a developer and therefore you should be able to understand the trade-offs.
Pros:
sum,mult,filter,contains,exists,average— anything that can be expressed withfold- No need to change Estimator or Evaluator — everything happens offchain
- For that reason, no hardforks are needed to get the new functionality.
Cons:
- You have to know the max size of your collection.
- If you get more elements than expected, you get Exception
- Computation cost will be linear to that max value
- Script size will be linear to that max value
Multisig
For an unknown reason, one of the top questions on our multisig example is “How to make requirement for signature positions in proofs array non-strict so that one could shovel signatures to the transaction as they come?” Anyway, here’s how:
# array of 8 public keys
let pks = [ ... ]
# inner fold step for each signature
def pkStep(sig: ByteVector, pk:ByteVector, acc: Boolean)
= acc || sigVerify(tx.bodyBytes, sig, pk)
# is signed by the public key or not
def signedBy(pk:ByteVector) = FOLD<8>(sigs, false, pkStep)
# outer fold step for each public key
def signedFoldStep(pk:ByteVector, acc:Int)
= acc + (if(signedBy(pk)) then 1 else 0)
# comparing total number of correct signatures to required number of correct signatures
FOLD<8>(pks, 0, signedFoldStep) == 8
A bit cryptic an too short to understand at first glance, but this should work.
So what, Turing Complete now?
Almost, the missing piece is FOLD<INFINITY> . But in dApps, this should never happen anyway. Let’s say it’s Turing-Complete Enough.
Let’s discuss
At the moment of writing, this is a proposal, but it looks solid(to me). What do you think? Maybe some model of predictable gas in Turing-Complete-Enough setup is a worthy idea?
Published at Sat, 03 Aug 2019 11:49:15 +0000
Bitcoin Pic Of The Moment
DAVOS/SWITZERLAND, 23JAN15 – David Kirkpatrick , Founder, Chief Executive Officer and Chief Techonomist, Techonomy Media, USA captured during the session From Bucks to Bitcoins in the congress centre at the Annual Meeting 2015 of the World Economic Forum in Davos, January 23, 2015.
WORLD ECONOMIC FORUM/Benedikt von Loebell
By World Economic Forum on 2015-01-23 14:47:52
