secp256k1 icon indicating copy to clipboard operation
secp256k1 copied to clipboard

WIP Group verification

Open peterdettman opened this issue 2 years ago • 5 comments

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.

peterdettman avatar Dec 05 '21 11:12 peterdettman

Removing _normalize_weak from several group add methods gives 2-3% speedup across major benchmarks (64 bit).

peterdettman avatar Dec 05 '21 12:12 peterdettman

Originally conceived many years ago now: https://github.com/bitcoin-core/secp256k1/issues/159 .

peterdettman avatar Dec 10 '21 12:12 peterdettman

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 avatar Jan 01 '22 12:01 peterdettman

@peterdettman This has "WIP" in the title but it looks pretty mature already. Can you comment on the status?

real-or-random avatar Apr 23 '22 14:04 real-or-random

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

peterdettman avatar Apr 25 '22 06:04 peterdettman