--- Log opened Fri Oct 06 00:00:48 2023
00:40 -!- salvatoshi [~salvatosh@genymobile-2-6-86.fib.nerim.net] has joined ##miniscript
03:25 -!- MatrixBot123 [~matrixbot@2001:bc8:1820:284::1] has joined ##miniscript
03:27 -!- MatrixBot123 [~matrixbot@2001:bc8:1820:284::1] has quit [Client Quit]
03:28 -!- MatrixBot123 [~matrixbot@2001:bc8:1820:284::1] has joined ##miniscript
05:20 -!- jon_atack [~jonatack@user/jonatack] has joined ##miniscript
05:20 -!- jonatack [~jonatack@user/jonatack] has quit [Read error: Connection reset by peer]
05:31 < darosior> sipa: i'm trying to wrap my head around your idea in https://github.com/bitcoin/bitcoin/pull/27255#discussion_r1348132869. You state "From that endpoint, it seems possible to me to reason backwards through all possible execution paths and compute their maximal stack size at every point". Do you mean in practice reasoning backward from the leaf
05:31 < darosior> fragments? But you can't know the maximal stack size by starting from a leaf fragment, it depends on the execution of previous fragments which is "a moving target" so to say. (Which is why my commit implements the net difference, but i must be missing something from your comment.) Could you expand a little bit?
05:33 < darosior> Also i'm not sure what "first" and "second part" refer to. Is that the first and second subs in  a fragment which concatenates those?
05:35 <@sipa> darosior: forget how to actually compute it
05:36 <@sipa> just observe that if you have a script, in opcode form... you know you end with 1 element on the stack, reasoning backwards through the opcodes will give you the exact stack size at that point
05:37 <@sipa> if there are branches, you can try all of them
05:37 <@sipa> makes sense?
05:38 < darosior> That makes sense to me, yes
05:40 <@sipa> so to compute that, we can determine for every piece of script (a) how many elements it "adds" (going backwards) going from its end to its start and (b) how many elements more than the end point it ever reaches
05:41 <@sipa> if you call those netdiff and exec
05:41 < darosior> Yes
05:41 <@sipa> then concatenating two pieces of script a + script b, the overall netdiff is a.netdiff + b.netdiff, and the overall exec is max(b.exec, b+netdiff + a.exec)
05:41 < darosior> Ooh and you just add the netdiff instead of substracting it like i do?
05:42 < darosior> Yes
05:42 <@sipa> so you can recursively compute this for the entire miniscript, and then just add (1,1) for the final state
05:42 <@sipa> and the result should give you both the max initial stack, and the max exec stack
05:44 < darosior> So that's where i'm not following anymore
05:44 < darosior> It seems to me there can be occurences where the max initial stack gets larger in one branch, but the max exec stack is larger on the other. Which one do you choose?
05:45 <@sipa> you don't choose
05:45 <@sipa> the computation determines the worst for both, independently
05:47 <@sipa> if you perform this netdiff/exec computation for the entire miniscript, you know both the max how much higher initial stack is than final stack
05:48 <@sipa> and you know the maximum for how much higher the stack size can get above the final stack
05:48 <@sipa> add 1 to both, and you get the max initial stack size, and the max execution
05:49 <@sipa> maybe i'm missing something, because i haven't implemented it
05:49 <@sipa> but it seems to me the core of the inaccuracy is due to the fact that you're computing the max exec compared to the *initial* stack, but you don't know what the initial stack will be in that worst execution case
05:50 <@sipa> if you compute the max exec compared to the *final* stack, this problem disappears, because the final stack has known size (1), independent of execution
05:50 < darosior> I don't want to bother you any longer before i understand it correctly. I'll try to come up with an example of what i mean. My point though is: there may be another branch for which the initial stack is higher, although the exec diff is lower. And you need to figure out which one is worse. I'll work on finding out an example and maybe it'll make me
05:50 < darosior> get what i'm missing.
05:51 <@sipa> i'm happy to try to implement it too
05:52 < darosior> That would definitely help, if it doesn't take too long
05:52 <@sipa> i predict that it'll take longer than i'm predicting now
05:52 < darosior> And the fuzz testing to test correctness is already there so
05:52 < darosior> Haha :)
06:03 < darosior> So a c:pk_k consumes 1 "external" element, pushes 1 element during its execution. In your going backwards calculation, it would have a netdiff of 1 and an exec of 2?
06:05 <@sipa> netdiff 0, exec 1
06:06 <@sipa> you
06:06 < darosior> The exec should be 2? Right before executing the CHECKSIG there is both the signature and the pubkey on the stack
06:06 <@sipa> netdiff is compared to the final state
06:07 <@sipa> and exec too
06:07 < darosior> Ok, gotcha
06:07 <@sipa> netdiff+1 gives you max initial stack size
06:07 <@sipa> exec+1 gives you max execution stack size
06:28 -!- ssou_ed [~superai_e@85.22.27.171] has joined ##miniscript
06:28 -!- ssou_ed [~superai_e@85.22.27.171] has left ##miniscript [Glined: User has been banned from the network.]
08:46 -!- salvatoshi [~salvatosh@genymobile-2-6-86.fib.nerim.net] has quit [Ping timeout: 258 seconds]
10:14 -!- kalle [~quassel@user/kallewoof] has quit [Ping timeout: 272 seconds]
10:14 -!- kalle [~quassel@user/kallewoof] has joined ##miniscript
11:44 <@sipa> darosior: i think i've gotten it to work (fuzz tests pass), but i'm getting lower exec limits in 3 unit tests:
11:44 <@sipa> test/miniscript_tests.cpp(470): error: in "miniscript_tests/fixed_tests": Stack execution limit mismatch: 
11:44 <@sipa> or_d(multi(1,02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9),or_b(multi(3,022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a01,032fa2104d6b38d11b0230010559879124e42ab8dfeff5ff29dc9cdadd4ecacc3f,03d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a),su:after(500000))) (10 vs 11)
11:44 <@sipa> test/miniscript_tests.cpp(470): error: in "miniscript_tests/fixed_tests": Stack execution limit mismatch: or_d(nd:and_v(v:older(4252898),v:older(4252898)),sha256(38df1c1f64a24a77b23393bca50dff872e31edc4f3b5aa3b90ad0b82f4f089b6)) (3 vs 4)
11:44 <@sipa> test/miniscript_tests.cpp(470): error: in "miniscript_tests/fixed_tests": Stack execution limit mismatch: or_d(nd:and_v(v:older(4252898),v:older(4252898)),sha256(38df1c1f64a24a77b23393bca50dff872e31edc4f3b5aa3b90ad0b82f4f089b6)) (3 vs 4)
12:06 <@sipa> for the last one, that looks correct
14:55 < darosior> Back now, will take a look
15:01 < darosior> .. It feels much cleaner already
16:05 < darosior> Ok so your approach is more accurate, and (much) cleaner. But it's still an overestimation: for instance take an `or_i(X,Y)`, for which `X`'s exec_size = 5, net_diff = 0  and `Y`'s exec_size = 0, net_diff = 5. It will account for `or_i(X,Y)` as having exec_size = 5, net_diff = 5 while there is no actual reachable path with such properties.
16:05 < darosior> That's what i was mentioning above with "there may be another branch for which the initial stack is higher, although the exec diff is lower. And you need to figure out which one is worse."
16:07 < darosior> (I'm talking about the '|' operator in the implem https://github.com/sipa/bitcoin/commit/40d438f5e440534e3df2d982f46049deab8a5cb6#diff-a55760aaec4bce216663f5ebf65823516347356a8320d30459427149f7bbc2c5R372-R378)
16:08 < darosior> Actually have you ever claimed this was an exact estimation or i just made this up
16:09 < darosior> " More accurate stack size limit calculation " is the name of your commit. I guess i just made this up.
16:11 < darosior> So i get it now, i'm playing a bit more with the fuzzer by introducing underestimations and i'll pull your commit in my PR. Thanks for taking the time to implement it.
16:20 <@sipa> darosior: actually, no, i believe(d) it is exact 
16:21 < darosior> I need to know how to branch on these parenthesis, do you still believe it's exact?
16:22 <@sipa> darosior: does it matter that there is no single path that has both net_diff 5 and exec_size 5?
16:22 <@sipa> they're both accurate assessments of a particular property of the script
16:24 <@sipa> but two different propertied
16:32 < darosior> sipa: i don't think it matters since you can get this with real fragments, i made these values up
16:35 < darosior> Actually i'm not sure you can..
16:49 < darosior> I was wrong. You cannot have a fragment which executes one of two branches (or_i, andor) such as one branch has a higher exec and the other has a higher net diff. Simply because both branches are required to be of the same type and therefore always have the same net diff.
16:52 <@sipa> darosior: both branches do not need to have the same net diff
16:54 < darosior> ... I'm starting to really confuse myself, i guess i'll just go to bed.
16:54 < darosior> sipa: then how comes that you can't have a fragment which executes one of two branches (or_i, andor) such as one branch has a higher exec and the other one has a higher net diff?
17:38 <@sipa> darosior: that's perfectly possible
17:39 <@sipa> just think of the max input stack computation and the max exec stack computation as completely independent
17:40 <@sipa> the fact that both are in one struct does not mean that they originate from the same branch
18:19 <@sipa> darosior: the fact tbat or_i(X,Y) has netdiff 5 and exec 5 simply means that this fragment has *some* (set of) branches through it with netdiff 5, and *some* branches through it with exec 5; but those two are not necessarily the same branches
18:20 <@sipa> but we don't care about identifying actual branches with those properties - we just care about the highest possible netdiff (to compute initial stack size) for P2WSH, and the highest possible exec (to compute max stack size during execution) for p2tr
18:20 <@sipa> for the overall script
--- Log closed Sat Oct 07 00:00:50 2023