Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Rework or get rid of scratch space #1302

Open
real-or-random opened this issue May 10, 2023 · 8 comments
Open

Rework or get rid of scratch space #1302

real-or-random opened this issue May 10, 2023 · 8 comments
Labels
assurance feature

Comments

@real-or-random
Copy link
Contributor

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:
@apoelstra
Copy link
Contributor

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.

@jonasnick jonasnick mentioned this issue May 11, 2023
Merged
@sipa
Copy link
Contributor

sipa commented May 11, 2023 •
edited
Loading

@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
Copy link
Contributor

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

@real-or-random real-or-random mentioned this issue Aug 1, 2023
Merged
@jonasnick
Copy link
Contributor

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.

@jonasnick jonasnick mentioned this issue Dec 18, 2023
Closed
@jonasnick jonasnick added this to the 0.5.0 milestone Jan 5, 2024
@jonasnick jonasnick mentioned this issue Jan 6, 2024
Merged
real-or-random added a commit that referenced this issue Oct 7, 2024
@real-or-random
Merge #1479: Add module "musig" that implements MuSig2 multi-signatur…
3660fe5 
…es (BIP 327)

168c920 build: allow enabling the musig module in cmake (Jonas Nick)
f411841 Add module "musig" that implements MuSig2 multi-signatures (BIP 327) (Jonas Nick)
0be7966 util: add constant-time is_zero_array function (Jonas Nick)
c8fbdb1 group: add ge_to_bytes_ext and ge_from_bytes_ext (Jonas Nick)
85e224d group: add ge_to_bytes and ge_from_bytes (Jonas Nick)

Pull request description:

  EDIT: based on #1518. Closes #1452. Most of the code is a copy from [libsecp256k1-zkp](https://github.com/BlockstreamResearch/secp256k1-zkp). The API added in this PR is identical with the exception of two modifications:

  1. I removed the unused `scratch_space` argument from `secp256k1_musig_pubkey_agg`. This argument was intended to allow using `ecmult_multi` algorithms for key aggregation in the future. But at this point it's unclear whether the `scratch_space` object will remain in its current form (see #1302).
  2. Support for adaptor signatures was removed and therefore the `adaptor` argument of `musig_nonce_process` was also removed.

  In contrast to the module in libsecp256k1-zkp, the module is non-experimental. I slightly cleaned up parts of the module, adjusted the code to the new definition of the VERIFY_CHECK macro and applied some simplifications that were possible because the module is now in the upstream repo (`ge_from_bytes`, `ge_to_bytes`). You can follow the changes I made to the libsecp256k1-zkp module at https://github.com/jonasnick/secp256k1-zkp/commits/musig2-upstream/.

ACKs for top commit:
  sipa:
    reACK 168c920
  real-or-random:
    reACK 168c920
  theStack:
    re-ACK 168c920

Tree-SHA512: e3a599a8d5a466107b9a86f76582b8fb9dc87ec95416c784c3ef39d1c64686e6c739806ed6ba62c91793eb7fa418a6270cf999027ee7bd3dd85c67bc2c74f677
@jonasnick
Copy link
Contributor

The scratch space has been removed from the public API in #1620.

@jonasnick jonasnick removed this from the 0.6.0 milestone Oct 30, 2024
@real-or-random
Copy link
Contributor Author

The scratch space has been removed from the public API in #1620.

Should we close this then? AFAIU there's nothing actionable for this particular issue. Of course, we still need to think about this when work on #1087 or MuSig2 key aggregation is continue.

@jonasnick
Copy link
Contributor

I didn't close this yet because we still have a scratch space in the code base that we intend to rework.

@real-or-random
Copy link
Contributor Author

I didn't close this yet because we still have a scratch space in the code base that we intend to rework.

Ok, sure, it's still in the code, just not in the public API. Nevermind.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
assurance feature
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@sipa @real-or-random @apoelstra @jonasnick