Rework or get rid of scratch space

[real-or-random]

Our confidence in the scratch space code isn't particularly high. It reinvents bump allocation, but it had a few issues in the past. All the code that uses scratch space is currently unreachable from the public API (except that we have secp256k1_scratch_create and secp256k1_scratch_destroy themselves in the public API.

A much simpler alternative is to get rid of scratch spaces and just assume the existence of malloc/free and use these directly. The disadvantage of this is that it's a bit harder for platforms that don't have malloc.

Another alternative is to rework the scratch space code. It may be possible to simply it and improve its usability.

I think our future directions on this should be guided by whatever we feel is best for our cases:

• batch validation (see General batch verification API context #1087 and Add an experimental batch module #1134)
• possibly musig2 key aggregation (maybe this is something people want to do run on hardware wallets?)

[apoelstra]

In secp256k1-zkp the scratch space gets actual usage, and I find it has a much nicer API than malloc/free. The API lets us:

• Allocate a slab up-front (or rather, check that the user passed in enough memory)
• As we are writing code, bump-allocate from the slab, asserting that we have enough, which sanity checks our up-front calculation
• Before doing something branch-heavy, checkpointing the allocator, then in the end just resetting to that, rather than having to wrory about correct cleanup logic in every branch

So I think it has more benefit than just replacing malloc and free for freestanding systems. Though it may still make sense to drop the code here and have it exclusively live in secp-zkp for a while.

[sipa]

@apoelstra We've discussed this a bit IRL, and it seems to me there are just a whole lot of only vaguely-overlapping concerns:

• The fact that the scratch space API forces us to write code which has predictable (and settable) memory usage, is both very useful (but only to some users) and a large source of the complexity of accomodating the current scratch space API. However, nothing prevents us from having that property too in different ways (e.g. by passing a "max memory usage" argument to functions).
• I believe there are reasonable extensions to the scratch space API which in fact keep the API, but break the predictable memory usage property. E.g. have the ability to initialize a scratch object with "just defer to malloc whenever memory is needed".
• Just because we have a scratch space API does not necessarily imply that all memory-demanding functionality needs to use it.
• The scratch space today, as-is, is useless. It's arguably a bug it's even exposed, for two reasons:
  • It's designed so that memory-demanding code can work in environments without malloc... however, that functionality isn't currently exposed.
  • There are no APIs currently using it (though batch validation would use it, and musig might).

My thinking is that the interface at least needs to be dropped from the API today, because it serves no purpose, and it seems to be guiding our thinking for future APIs. We can keep the internal logic for now - and possibly bring it back if it makes sense for a particular use case - but it's easier to discuss all of that without being pre-biased by the scratch API.

[apoelstra]

@sipa these are all good points. concept ACK from me on removing the API from this library.

[jonasnick]

The fact that the scratch space API forces us to write code which has predictable (and settable) memory usage, is both very useful (but only to some users) and a large source of the complexity of accomodating the current scratch space API. However, nothing prevents us from having that property too in different ways (e.g. by passing a "max memory usage" argument to functions).

In the case of ecmult_multi, it can be argued that we could achieve similar predictability by adding a max_batch_size argument to ecmult_multi and the user-facing API (e.g., schnorrsig_batch_verify and musig_keyagg).
This would have the advantage of freeing us from the complexity of dealing with memory usage.

The predictability of max_batch_size is arguably similar because even with max_memory_usage and the current scratch space's size, developers concerned about memory usage should test the functions they call with a large number of inputs.
This is best practice and allows measuring actual memory usage (which is different due to overhead in the malloc implementation).
If testing with a large number of inputs is necessary anyway, developers could run the same tests to determine a suitable max_batch_size.

A downside of this approach is that adding more functions that dynamically allocate memory besides ecmult_multi risks leaking more max_... arguments to user-facing APIs in addition to max_batch_size.