WIP Group verification #1032

pull peterdettman wants to merge 5 commits into bitcoin-core:master from peterdettman:group_verify changing 5 files +205 −45
  1. peterdettman commented at 11:21 am on December 5, 2021: contributor

    Sets up pre- and post- method verification of _ge and _gej group elements. At the moment, this is concerned mainly with imposing a tighter limit (than the default) on the magnitudes of field elements x, y (,z).

    Having guarantees about the magnitudes in input group elements can let us avoid some of the normalization calls needed at the start of several group addition methods, and perhaps e.g. use an alternative double algorithm. There may be a trade-off between the effort needed to get outputs to meet lower limits vs the benefits that provides to other methods.

  2. peterdettman commented at 12:17 pm on December 5, 2021: contributor
    Removing _normalize_weak from several group add methods gives 2-3% speedup across major benchmarks (64 bit).
  3. peterdettman cross-referenced this on Dec 6, 2021 from issue Reduce stratch space needed by ecmult_strauss_wnaf. by roconnor-blockstream
  4. peterdettman commented at 12:20 pm on December 10, 2021: contributor
    Originally conceived many years ago now: #159 .
  5. peterdettman force-pushed on Dec 21, 2021
  6. peterdettman cross-referenced this on Dec 23, 2021 from issue Add _fe_half and use in _gej_add_ge and _gej_double by peterdettman
  7. peterdettman force-pushed on Dec 23, 2021
  8. peterdettman cross-referenced this on Dec 24, 2021 from issue Try a non-uniform group law (e.g., for ecmult_gen)? by real-or-random
  9. peterdettman force-pushed on Jan 1, 2022
  10. peterdettman commented at 12:42 pm on January 1, 2022: contributor

    Rebased and added some missing verify calls.

    I’ve noted that there are several places where code directly manipulates the fields of group elements without calling a group method to do so. So the group structs are a bit too “open” at the moment. It should be possible to add suitable methods so that the group structs act more like abstract data types, and in particular so that we have a definite boundary at which to be able to place VERIFY calls in relation to group internals.

  11. peterdettman cross-referenced this on Jan 11, 2022 from issue Separate magnitude/normalization/... checking/propagation from implementations by sipa
  12. peterdettman force-pushed on Feb 23, 2022
  13. Decorate group methods with verify macros 09dbba561f
  14. Add _fe_verify_magnitude under VERIFY abd5d79431
  15. Implement current magnitude assumptions 50c0c6df39
  16. Tighten group magnitude limits
    - adjust test methods that randomize magnitudes
    e70c08ca83
  17. Save _normalize_weak calls in group add methods 0a820841f7
  18. peterdettman force-pushed on Apr 20, 2022
  19. real-or-random commented at 2:04 pm on April 23, 2022: contributor
    @peterdettman This has “WIP” in the title but it looks pretty mature already. Can you comment on the status?
  20. peterdettman commented at 6:13 am on April 25, 2022: contributor
    @real-or-random See my previous comment; basically there are still quite a few unguarded local operations on group structs (i.e. not abstracted as group methods). These are not too difficult to track down comprehensively, but it occurs to me that, even once committed, we might need to allow some time for the abstraction to sink in to developers’ minds before trying to exploit it (as per the “Save _normalize_weak…” commit) - there might be some backsliding. We could discuss ways of enforcing the abstraction in the language (or tooling), but the field implementations are in the same boat and just rely on “it being understood”.
  21. sipa commented at 8:31 pm on May 10, 2023: contributor
    A notion of group verification was introduced through #1299. The later commits here will need to be redone on top of that.
  22. real-or-random added the label assurance on May 11, 2023
  23. real-or-random added the label performance on May 11, 2023
  24. sipa cross-referenced this on Jun 14, 2023 from issue group: save normalize_weak calls in `secp256k1_ge_is_valid_var`/`secp256k1_gej_eq_x_var` by theStack
  25. theStack referenced this in commit 78ef599ff0 on Jun 15, 2023
  26. theStack cross-referenced this on Jun 15, 2023 from issue tighten group magnitude limits, save normalize_weak calls in group add methods (revival of #1032) by theStack
  27. theStack referenced this in commit a55902c091 on Jun 27, 2023
  28. real-or-random commented at 2:21 pm on July 3, 2023: contributor
    Closing in favor of #1348
  29. real-or-random closed this on Jul 3, 2023

  30. theStack referenced this in commit 672b1016ff on Jul 10, 2023
  31. theStack referenced this in commit 0ce5892cac on Jul 14, 2023
  32. theStack referenced this in commit 9b8aa9804d on Jul 14, 2023
  33. theStack referenced this in commit 72aa104f28 on Jul 15, 2023
  34. theStack referenced this in commit 690b0fc05a on Jul 22, 2023

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-22 02:15 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me