Nostr Web Client

I watched the video of nostr:npub1cev2qfuqv5s9jm5a6yvhc8ne8cdl9mh459m5g8zz759s7pw9fayqnketlq's Bitcoin-Lisp-Script talk (https://brink.dev/blog/2024/12/19/eng-call-aj-towns-bll/).

Summary:

1. Lisp a the classic alternative to Forth for embedded use, so makes sense for Bitcoin Script.

2. Iteration is definitely a super power.

3. Definitely worthy of further research.

My main concern is that it requires much more broadly-defined limits. The varops work does a very limited subset of what is needed in general, *because* we operate within a 4MB max opcode limit already. varops *only* has to extend it so that large data doesn't make things worse, and we get to ignore anything which isn't proportional to data being operated on, figuring that's already possible.

An approach with iteration has to worry about more than that, requiring a general system of CPU consumption limits. That's not impossible, but I have *not* done that. For example, OP_DUP3 of three empty stack operations costs 0 varops. If you could do billions of these, this assumption that we can ignore those stack operations would be invalid.

The good news is that I am tending into that area with my OP_MULTI proposal. Prior to this, nothing operates on more than 3 stack entries, so ignore the overhead of stack operations (OP_ROLL is the exception, but in practice it's really fast, and still limited to moving 998 entries). With OP_MULTI, this needs to be taken into account, and if it can cause significant time to be spent on stack operations, the varops model will have to be extended. However, OP_MULTI is still very much limited to the stack size. To be fair, I'm considering increasing that from 1000 to 32768, because it's reasonable to have almost that many outputs (P2WPKH), so I might be forced to extend the varops model to cost that appropriately.

Now I need to go read AJ's Python code, since I have other questions about the exact nature of these limits (does space include overhead? 0 byte allocations are not free!).

So, if you're interested in extending script, I believe you should fairly consider this. I would like it to advance to a proper BIP, of course, so we could get more of an apples-to-apples comparison, and that's a lot of work!

Side note: everyone working on Bitcoin Script replacements is smarter than me. It's intimidating! 💜

Reply to this note

Please Login to reply.

Discussion

aj 6mo ago

Broadly defined limits: the way this is designed is that each element has a strictly defined memory usage (16 bytes overhead for cons' two pointers, 16+size bytes for vector, plus 8 bytes overhead for type info and refcount in both cases), and a strictly defined lifetime. bllsh currently tracks the limits (ALLOCATOR.alloc() and .free() and alloc_size() in Element subclasses). Actual implementations might use less space (4 byte pointers vs 8?) or more (allocate space in powers of 2?) but should only be a factor of 2 or 4 or so off.

Enforcement of memory and execution cost limits is pretty preliminary: there's checks in symbll/WorkItem/step for no more than 100k steps (with no weightings applied) and no more than 400kB of memory used. This really should be using Allocator/record_work and over_limit to ensure intermediate state didn't go over the limit, and it all should apply to bll as well, but currently doesn't.