secp256k1
secp256k1 copied to clipboard
WIP Group verification
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.
Removing _normalize_weak from several group add methods gives 2-3% speedup across major benchmarks (64 bit).
Originally conceived many years ago now: https://github.com/bitcoin-core/secp256k1/issues/159 .
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.
@peterdettman This has "WIP" in the title but it looks pretty mature already. Can you comment on the status?
@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".