UB in tests: Invalid pointer comparison in secp256k1_fe_inv_all_var

[practicalswift]

Is this VERIFY_CHECK pointer comparison in secp256k1_fe_inv_all_var defined when r and a are pointing to different objects?

secp256k1/src/field_impl.h

Lines 266 to 273 in 98dac87

	static void secp256k1_fe_inv_all_var(secp256k1_fe *r, const secp256k1_fe *a, size_t len) {
	secp256k1_fe u;
	size_t i;
	if (len < 1) {
	return;
	}
	VERIFY_CHECK((r + len <= a) || (a + len <= r));

Nothing high priority of course, but perhaps worth fixing? :)

This pointer comparison was introduced as part of PR #16 ("Implement batch inversion of field elements") in f16be77 back in 2014.

[real-or-random]

Is this VERIFY_CHECK pointer comparison in secp256k1_fe_inv_all_var defined when r and a are pointing to different objects?

No. Thanks for reporting.

Note that VERIFY_CHECKs are only active in the tests.

Are you willing to open a PR? I think the right thing to check is r != a.

[real-or-random]

Are you willing to open a PR? I think the right thing to check is r != a.

Well ok, not really. We can check r != a but what the check was supposed to do is to check that the arrays are not overlapping. I believe we should add a comment to the function that states this requirement. It's not clear to me how to check this property in C (unless maybe with two loops and != checks), so I think we should just not check it.

[gmaxwell]

The non-overlapping status of the arrays is an important part of the interface.

[sipa]

So after reading a bit on cppreference.com (which also has pages about C), I believe:

• == and != on between unrelated pointers is implementation defined
• < <= > >= between unrelated pointers is UB.
• casting from pointer to a sufficiently large integer type is implementation defined, but reversible (casting the integer back to the original pointer type gives a pointer to the original object)

I believe that means that overlap can be checked by casting to intptr_t and doing the check we do now. It would rely on the assumption that subsequent array elements correspond to subsequent intptr_t values, which I expect to be universal, and even if not, wouldn't be UB.

[gmaxwell]

subsequent intptr_t values, which I expect to be universal,

It's not necessarily true on platforms with segmented memory e.g. real-mode 16-bit dos. But I don't think that's a problem, because this is just a verify check. It's probably also not true for some bizarre environments like the compcert formalism for C. But again, no problem there.

If there were come libsecp256k1 porting guide it might deserve a line in it.

[real-or-random]

I believe that means that overlap can be checked by casting to intptr_t and doing the check we do now. It would rely on the assumption that subsequent array elements correspond to subsequent intptr_t values, which I expect to be universal, and even if not, wouldn't be UB.

Ugh, yeah, I guess we can do this. I didn't expect that a pointer-to-int cast will ever "solve" a problem.

By the way, I usually look stuff up in the standard directly:
https://port70.net/~nsz/c/c89/c89-draft.html#3.3.8

subsequent intptr_t values, which I expect to be universal,

It's not necessarily true on platforms with segmented memory e.g. real-mode 16-bit dos. But I don't think that's a problem, because this is just a verify check. It's probably also not true for some bizarre environments like the compcert formalism for C. But again, no problem there.

If there were come libsecp256k1 porting guide it might deserve a line in it.

Well, the current behavior isn't universal either. I guess we should add a comment to the line, and if we want we can also add a comment to assumptions.h. This is the closest thing to a porting guide that we currently have.

[real-or-random]

Here's a simpler solution: Remove the function, it's currently unused. Was this function intended for ECDSA batch verification?

[gmaxwell]

It's for building the verify context, but its functionality was inlined into its parent function ( secp256k1_ge_set_all_gej_var ) to reduce the usage of scratch space in #553.

I agree, it should probably just be removed.

[sipa]

Haha, let's just remove it then.

[sipa]

See #878.