Rework or get rid of scratch space about secp256k1 HOT 4 OPEN

@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.

from secp256k1.

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.

from secp256k1.

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

from secp256k1.

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.

from secp256k1.