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 commented at 12:20 PM on December 10, 2021: contributor

    Originally conceived many years ago now: #159 .

  4. peterdettman force-pushed on Dec 21, 2021
  5. peterdettman force-pushed on Dec 23, 2021
  6. peterdettman force-pushed on Jan 1, 2022
  7. 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.

  8. peterdettman force-pushed on Feb 23, 2022
  9. Decorate group methods with verify macros 09dbba561f
  10. Add _fe_verify_magnitude under VERIFY abd5d79431
  11. Implement current magnitude assumptions 50c0c6df39
  12. Tighten group magnitude limits
    - adjust test methods that randomize magnitudes
    e70c08ca83
  13. Save _normalize_weak calls in group add methods 0a820841f7
  14. peterdettman force-pushed on Apr 20, 2022
  15. 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?

  16. 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".

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

  18. real-or-random added the label assurance on May 11, 2023
  19. real-or-random added the label performance on May 11, 2023
  20. theStack referenced this in commit 78ef599ff0 on Jun 15, 2023
  21. theStack referenced this in commit a55902c091 on Jun 27, 2023
  22. real-or-random commented at 2:21 PM on July 3, 2023: contributor

    Closing in favor of #1348

  23. real-or-random closed this on Jul 3, 2023

  24. theStack referenced this in commit 672b1016ff on Jul 10, 2023
  25. theStack referenced this in commit 0ce5892cac on Jul 14, 2023
  26. theStack referenced this in commit 9b8aa9804d on Jul 14, 2023
  27. theStack referenced this in commit 72aa104f28 on Jul 15, 2023
  28. theStack referenced this in commit 690b0fc05a on Jul 22, 2023
  29. real-or-random referenced this in commit eedd781085 on Aug 16, 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: 2026-05-19 06:52 UTC