secp256k1_fe_set_b32_mod doesn't actually reduce anything

Coding-Enthusiast commented at 6:23 am on December 6, 2023: contributor

secp256k1_fe_set_b32_mod method name and comment suggest that it reduces the value mod p and the result is supposed to be r ≡ a (mod p)
https://github.com/bitcoin-core/secp256k1/blob/d3e29db8bbf81600fe0a6bd70b12fe57a0121b83/src/field.h#L187-L192

However looking at the implementations they don’t actually perform any reduction. It’s just a simple conversion from byte[] to uint[] in radix 26 or 52.
https://github.com/bitcoin-core/secp256k1/blob/d3e29db8bbf81600fe0a6bd70b12fe57a0121b83/src/field_impl.h#L270-L277
https://github.com/bitcoin-core/secp256k1/blob/d3e29db8bbf81600fe0a6bd70b12fe57a0121b83/src/field_10x26_impl.h#L293-L304
https://github.com/bitcoin-core/secp256k1/blob/d3e29db8bbf81600fe0a6bd70b12fe57a0121b83/src/field_5x52_impl.h#L235-L270

After this change the old method (secp256k1_fe_set_b32_limit) is still used in most places except something like this https://github.com/bitcoin-core/secp256k1/commit/5b32602295ff7ad9e1973f96b8ee8344b82f4af0#diff-6f71b0372be086d45b4f2740508c03a21835d87008840032fbb767f419fd988a
And it just assumes secp256k1_fe_set_b32_mod reduces the result while it doesn’t. @sipa

sipa commented at 1:19 pm on December 6, 2023: contributor

You’re right that the function secp256k1_fe_set_b32_mod itself doesn’t perform any modular reductions. But it doesn’t need to: the secp256k1_fe type itself does: all operations on secp255k1_fe automatically perform reductions when the integer used to represent it overflows too much.

In short, secp256k1_fe can only represent elements of the finite field “integers modulo p”. It encapsulates an integer, and that integer can (within certain bounds) exceed p, but the actual integer is hidden by the abstraction: none of the functions operating on the type let you observe the integer.

So the only difference between secp256k1_fe_set_b32_mod and secp256k1_fe_set_b32_limit is that the latter detects and fails if the input exceeds p, but then in return gives a stronger guarantee on how normalized (basically, how small the integers inside is guaranteed to be) the resulting field element is.

Coding-Enthusiast commented at 5:23 pm on December 6, 2023: contributor

So the only difference between secp256k1_fe_set_b32_mod and secp256k1_fe_set_b32_limit is that the latter detects and fails if the input exceeds p

Wouldn’t it be better to rename the methods to something like _set_b32 and set_b32_check?

real-or-random commented at 5:56 pm on December 6, 2023: contributor

Well, bike shedding is always possible, but I think the names are okay. If anything, limit is more precise than check, and mod is more precise than the empty string.

Perhaps the docs can be marginally improved. I see that this can be misleading.

Set a field element equal to a provided 32-byte big endian value, reducing it.

It’s more like this: “Set a field element equal to the element represented by a provided 32-byte big endian value interpreted modulo p.”

And the other one:

Set a field element equal to a provided 32-byte big endian value, checking for overflow.

Perhaps: “Set a field element equal to a provided 32-byte big endian value in [0..p-1].”

real-or-random commented at 8:30 am on December 7, 2023: contributor

@Coding-Enthusiast I’d be happy to review a PR which implements (variants of) these suggestions.

real-or-random added the label refactor/smell on Dec 7, 2023

Coding-Enthusiast cross-referenced this on Dec 8, 2023 from issue doc: improve secp256k1_fe_set_b32_mod doc by Coding-Enthusiast

real-or-random referenced this in commit 77af1da9f6 on Dec 11, 2023

Coding-Enthusiast closed this on Dec 11, 2023

secp256k1_fe_set_b32_mod doesn’t actually reduce anything #1453