k is something like 'number of distinct opcodes', but I'll accept k=2 as well. n is script length you are trying to evaluate. Compute oracles will be defined in a paper I'm currently writing, which btw covers your SuperAsset design as well
Post by twetch#1784
K is bounded at most to whatever number of instructions there are (ie: a sufficient constant C)
So we can simplify in Big-O to just O(n).
All programs grow in O(n) where n is the program length.
What the chain says
- Block
- 658 159
- Time
- 2020-10-23T19:26:48Z
- Signer
- 17DJKzxx6XvzHy41vRTYU91ugMtFY1CNQ2
- App
- twetch
- Type
- post
- Content type
- text/plain
- Name in tx
- twetch#1784
Fields the transaction did not carry are omitted. Open the payload to see the bytes as stored.
Signed by
17DJKzxx6XvzHy41vRTYU91ugMtFY1CNQ2 VerifiedReplies (9)
In other words, all programs' code size by definition is length O(n).
If I take this bet, as defined, then I will win trivially.
Something's amiss.
I said k^n (simplified to 2^n), not k*n. The size of the in-script interpreter grows exponentially with the size of the longest script it can interpret. But I already think I jumped the gun here :x it'd be (2^k * n) for k ops which indeed is O(n)
- for N ops
I need to slow down
Anyway I'll send you 10 BSV anyway if you promise to give a thorough review/analysis of this short upcoming paper
Eval+reentry (eval arbitrary code read from PUSHTX) is what could cause exponential blowup. Maybe you could do the same static analysis we do for SCALL but I shudder to think how that would look in bitcoin script...
I think you could do it at runtime with O(n^2) by examining reentry stack
Yeah that's totally what I was thinking of but forgot when I had to explain myself mhmm