generator: massively speed up serialization #294

apoelstra · 2024-05-10T13:26:53Z

secp256k1_pedersen_commit_serialize would call _load (which does a sqrt to fully decompress the key, then a conditional negation based on the flag), then check the Jacobian symbol of the resulting y-coordinate, then re-serialize based on this.

Instead, don't do any of this stuff. Copy the flag directly out of the internal representation and copy the x-coordinate directly out of the internal representation.

Checked that none of the other _serialize methods in the modules do this.

Fixes #293

real-or-random

Concept ACK

real-or-random · 2024-05-16T07:10:03Z

src/modules/generator/main_impl.h

+    output[0] = 8 ^ (commit->data[0] & 1);
+    memcpy(&output[1], &commit->data[1], 32);


Couldn't you even memcpy the entire 33 bytes?

Couldn't you even memcpy the entire 33 bytes?

I tried this, it does pass the tests :)

I see 8 ^ (commit->data[0] & 1) alternates between 1000 and 1001 binary for even/odd values of data[0].

Out of interest as a cryptography noob, what is the significance of this?

It's just a flag byte. 0x02, 0x03 (and a few others) are already used for public keys, so whoever wrote that code took 0x08 and 0x09 to distinguish commitments from public keys.

@real-or-random thanks!

apoelstra · 2024-05-16T14:11:43Z

Changed to memcpy the entire 33 bytes. Also added a commit which does the same thing for parsing.

Previously, parsing decoded the whole point, then conditionally negated it, then extracted the jacobi symbol of the y-coordinate (which is entirely determined by the ge_set_xquad followed by conditional negation!), then normalized and re-serialized the x-coordinate (which was parsed directly using fe32_set_b32_limit so it was already normalized).

But all we need to do is (a) check that the first byte is 8 or 9; (b) check that the remainder is a valid x-coordinate, then (c) memcpy.

Step (b) is still pretty slow, compared to serialization which is just a memcpy, but this is a big improvement.

apoelstra · 2024-05-16T14:20:09Z

CI failure appears to be some unrelated break in our macos image.

jonasnick

Concept ACK

This PR looks good.

As a sidenote (not this PR) the implementation of pedersen_commitment_load and save is quite different from pubkey_load and save. In contrast to pubkey loading, pedersen commitment loading is costly, which results in unnecessary sqrts when loading commitments in verify_tally.

jonasnick · 2024-05-20T07:32:28Z

src/modules/generator/tests_impl.h

        CHECK(secp256k1_pedersen_commit(CTX, &commits[i], &blinds[i * 32], values[i], secp256k1_generator_h));
+        CHECK(secp256k1_pedersen_commitment_serialize(CTX, result, &commits[i]));
+        CHECK(secp256k1_pedersen_commitment_parse(CTX, &parse, result));
+        CHECK(secp256k1_memcmp_var(&commits[i], result, 33) == 0);


Should also check that parse is correct?

Oh, yeah, it should be checking commits[i] against parse rather than against result :).

This code works but only because of a bunch of C weirdness. Will fix.

`secp256k1_pedersen_commit_serialize` would call `_load` (which does a sqrt to fully decompress the key, then a conditional negation based on the flag), then check the Jacobian symbol of the resulting y-coordinate, then re-serialize based on this. Instead, don't do any of this stuff. Copy the flag directly out of the internal representation and copy the x-coordinate directly out of the internal representation. Checked that none of the other _serialize methods in the modules do this. Fixes BlockstreamResearch#293

real-or-random

We could also consider overwriting the output with zeros (or anything which is initialized but not a valid commitment) when parsing fails. We do this in upstream for other parsing functions.

Not sure, it may be a bit arbitrary to do it here now. This should maybe go to a proper PR that does it consistently in all -zkp modules.

real-or-random · 2024-05-21T08:57:20Z

src/modules/generator/main_impl.h

@@ -288,10 +288,8 @@ int secp256k1_pedersen_commitment_parse(const secp256k1_context* ctx, secp256k1_
        !secp256k1_ge_set_xquad(&ge, &x)) {


Suggested change

!secp256k1_ge_set_xquad(&ge, &x)) {

!secp256k1_ge_x_on_curve_var(&x)) {

and we can drop ge entirely.

Force-pushed to do this.

Similar to speeding up serialization; in our parsing logic we did a bunch of expensive stuff then expensively inverted it. Drop everything except the essential checks and then memcpy.

real-or-random

utACK 6361266

I think I know how to fix CI, I'll open a PR later today or tomorrow

real-or-random · 2024-05-21T22:23:34Z

The CI issue should be resolved once the GitHub Actions image is updated to have brew 4.3.1, which has the fix (Homebrew/brew#17336). The images are updated every week, so the issue should just disappear in a few days.

jonasnick · 2024-05-22T11:50:19Z

I am surprised that the last 31 bytes of the pedersen commitment struct are uninitialized preventing something like

memcpy(&com1, &com2, sizeof(secp256k1_pedersen_commitment));

However, that is already the case without this PR.

jonasnick

ACK 6361266

real-or-random · 2024-05-22T12:30:17Z

I am surprised that the last 31 bytes of the pedersen commitment struct are uninitialized preventing something like
memcpy(&com1, &com2, sizeof(secp256k1_pedersen_commitment));

Yes, that's a bit strange. That means we can always switch to an uncompressed internal representation. I haven't thought about the performance implications, but uncompressed should usually be faster (unless you only deserialize and serialize again without doing actual computations, but why should you do this...)

This dates back to edb879f (see also the parent commit fca4c3b which does the same for secp256k1_generator), but I can't find the corresponding PR. @apoelstra Do you remember why you changed this?

apoelstra · 2024-05-22T13:30:56Z

Yes, that's a bit strange. That means we can always switch to an uncompressed internal representation. I haven't thought about the performance implications, but uncompressed should usually be faster (unless you only deserialize and serialize again without doing actual computations, but why should you do this...)

This is a somewhat common thing to do with Elements transactions, where you parse the whole transaction (including decompressing the points, because this is how you obtain valid pubkey-type objects) and then only manipulate non-crypto parts before re-serializing.

With normal pubkeys serialization is (almost) just as fast with a compressed vs uncompressed representation because you just need to check the lsb of the y coordinate. But with secp-zkp keys, recompressing an uncompressed key requires recomputing the jacobi symbol :/.

This dates back to edb879f (see also the parent commit fca4c3b which does the same for secp256k1_generator), but I can't find the corresponding PR. @apoelstra Do you remember why you changed this?

Afraid not. And I also cannot find the corresponding PR.

real-or-random · 2024-05-22T13:35:37Z

I see, so you're saying it makes sense to keep the internal representation compressed for performance reasons?

If we keep this, then we should at least write all 64 bytes to avoid passing uninitialized memory to the user. Or simply switch back to an opaque type that has just 33 bytes. The latter is cleaner and simpler IMO.

apoelstra · 2024-05-22T13:39:53Z

Honestly I'm tempted to switch to 65 bytes before switching to 33. So we'd have the uncompressed representation which can be efficiently manipulated by the actual crypto functions, and also an xquad flag bit (probably also useful for crypto actually) so we can quickly serialize.

real-or-random · 2024-05-22T14:09:36Z

Ok, sure, that's also possible and nicer.

The issue with switching either to 33 or 65 is that it's a breaks ABI compatibility for any code copying or moving structs. We say this:

secp256k1-zkp/include/secp256k1_generator.h

Lines 14 to 16 in 1683772

    
            *  The exact representation of data inside is implementation defined and not 
        
            *  guaranteed to be portable between different platforms or versions. It is 
        
            *  however guaranteed to be 64 bytes in size, and can be safely copied/moved.

Strictly speaking, all of this is in an experimental module, but yeah, not sure if we want to risk breaking things.

apoelstra · 2024-05-22T14:13:28Z

Agreed. I think for now we should leave it alone. Maybe if/when we implement BP++ and switch to it in Elements, we can consider also breaking the generator API.

real-or-random reviewed May 16, 2024

View reviewed changes

apoelstra force-pushed the 2024-04--fast-serialize branch from bafe257 to 820fc6a Compare May 16, 2024 13:58

jonasnick reviewed May 20, 2024

View reviewed changes

apoelstra force-pushed the 2024-04--fast-serialize branch from 57bf3c9 to 2fb01fe Compare May 20, 2024 12:40

real-or-random reviewed May 21, 2024

View reviewed changes

generator: speed up parsing

6361266

Similar to speeding up serialization; in our parsing logic we did a bunch of expensive stuff then expensively inverted it. Drop everything except the essential checks and then memcpy.

apoelstra force-pushed the 2024-04--fast-serialize branch from 2fb01fe to 6361266 Compare May 21, 2024 13:52

real-or-random approved these changes May 21, 2024

View reviewed changes

jonasnick approved these changes May 22, 2024

View reviewed changes

jonasnick merged commit 1683772 into BlockstreamResearch:master May 22, 2024
97 of 107 checks passed

apoelstra deleted the 2024-04--fast-serialize branch May 22, 2024 14:13

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

generator: massively speed up serialization #294

generator: massively speed up serialization #294

apoelstra commented May 10, 2024

real-or-random left a comment

real-or-random May 16, 2024

delta1 May 16, 2024 •

edited

real-or-random May 16, 2024

delta1 May 16, 2024

apoelstra commented May 16, 2024

apoelstra commented May 16, 2024

jonasnick left a comment

jonasnick May 20, 2024

apoelstra May 20, 2024

apoelstra May 20, 2024

real-or-random left a comment

real-or-random May 21, 2024

apoelstra May 21, 2024

apoelstra May 21, 2024

real-or-random left a comment

real-or-random commented May 21, 2024

jonasnick commented May 22, 2024

jonasnick left a comment

real-or-random commented May 22, 2024

apoelstra commented May 22, 2024

real-or-random commented May 22, 2024

apoelstra commented May 22, 2024

real-or-random commented May 22, 2024 •

edited

apoelstra commented May 22, 2024

		output[0] = 8 ^ (commit->data[0] & 1);
		memcpy(&output[1], &commit->data[1], 32);

		@@ -288,10 +288,8 @@ int secp256k1_pedersen_commitment_parse(const secp256k1_context* ctx, secp256k1_
		!secp256k1_ge_set_xquad(&ge, &x)) {

	!secp256k1_ge_set_xquad(&ge, &x)) {
	!secp256k1_ge_x_on_curve_var(&x)) {

generator: massively speed up serialization #294

generator: massively speed up serialization #294

Conversation

apoelstra commented May 10, 2024

real-or-random left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

delta1 May 16, 2024 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

apoelstra commented May 16, 2024

apoelstra commented May 16, 2024

jonasnick left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

real-or-random left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

real-or-random left a comment

Choose a reason for hiding this comment

real-or-random commented May 21, 2024

jonasnick commented May 22, 2024

jonasnick left a comment

Choose a reason for hiding this comment

real-or-random commented May 22, 2024

apoelstra commented May 22, 2024

real-or-random commented May 22, 2024

apoelstra commented May 22, 2024

real-or-random commented May 22, 2024 • edited

apoelstra commented May 22, 2024

delta1 May 16, 2024 •

edited

real-or-random commented May 22, 2024 •

edited