Add x-only ECDH support to ecdh module

sipa commented at 6:32 pm on January 27, 2023: contributor

Built on top of #1118, this adds API calls to the ecdh module to support x-only ECDH. When pubkey decompression is included in the ECDH benchmark, it’s roughly 10% faster to do x-only ECDH.

The default hash function included uses SHA256(shared_x_coordinate) as output function.

sipa cross-referenced this on Jan 27, 2023 from issue x-only ECDH support by rustyrussell

sipa force-pushed on Jan 27, 2023

real-or-random commented at 9:33 am on January 28, 2023: contributor

Tried to fix the MSVC issues… let’s see what CI says.

See commit messages. I verified locally that static linking doesn’t break and just outputs a warning.

hebasto commented at 9:46 am on January 28, 2023: member

Tried to fix the MSVC issues… let’s see what CI says.

See commit messages. I verified locally that static linking doesn’t break and just outputs a warning.

FWIW, the last commit fixes this branch build with MSVC when using CMake-based build system as well: https://cirrus-ci.com/build/6082649656131584

sipa force-pushed on Jan 28, 2023

sipa commented at 5:29 pm on January 28, 2023: contributor

@real-or-random Thanks for the fixes. I’ve removed my earlier attempt from the commit history. If this works, I’ll extract the non-ECDH-related parts from this PR and submit them separately.

in include/secp256k1.h:150 in e7e86fe514 outdated

159+#if defined(_WIN32) && !defined(__GNUC__)
160+# ifdef SECP256K1_BUILD
161+#  ifdef DLL_EXPORT
162+#   define SECP256K1_API            __declspec (dllexport)
163+#   define SECP256K1_API_VAR extern __declspec (dllexport)
164 #  endif

sipa commented at 5:39 pm on January 28, 2023:

What if defined(SECP256K1_BUILD) && !defined(DLL_EXPORT), then SECP256K1_API{,_VAR} will be undefined?

real-or-random commented at 7:01 pm on January 28, 2023:

This is handled in #ifndef block in line 163. Maybe the same logic can be written in a more readable structure, feel free to reorganize if you see a better method.

real-or-random commented at 7:20 pm on January 28, 2023: contributor

We should probably move my two build/ci commits in a separate commit. At least the build commit fixes a real build issue that we simply haven’t encountered so far, because none of our “user” binaries (bench+examples) have used variables exported from the variable so far (but just functions).

(I can take care of that, and I still want to rethink one detail here.)

sipa commented at 7:52 pm on January 28, 2023: contributor

@real-or-random Yeah, I think both of your commits should be submitted as a separate PR. Perhaps the benchmark change here should also (as ECDH benchmarking without including pubkey decoding is misleading), so I was planning to do those 3. It won’t be before tonight though, so if you want to, go ahead.

sipa commented at 3:07 am on January 29, 2023: contributor

@real-or-random Actually since both of the commits are yours, and perhaps you want to make some changes, perhaps you should open a PR for them?

I’ll rebase this and/or open the ECDH benchmark change as a follow-up then.

real-or-random commented at 10:10 am on January 30, 2023: contributor

@real-or-random Actually since both of the commits are yours, and perhaps you want to make some changes, perhaps you should open a PR for them?

Yep, I’ll take care of that!

sipa commented at 3:07 pm on February 6, 2023: contributor

@real-or-random Ping?

Yep, I’ll take care of that!

real-or-random commented at 3:54 pm on February 6, 2023: contributor

@real-or-random Ping?

Yep, I’ll take care of that!

Will do today or tomorrow!

real-or-random cross-referenced this on Feb 6, 2023 from issue build: Add SECP256K1_API_VAR to fix importing variables from DLLs by real-or-random

real-or-random referenced this in commit cbd2555934 on Feb 21, 2023

sipa cross-referenced this on May 8, 2023 from issue ECDH from compressed points with "free" sqrt by peterdettman

real-or-random cross-referenced this on May 11, 2023 from issue x-only ECDH without sqrt by peterdettman

real-or-random added the label feature on May 11, 2023

real-or-random added the label performance on May 11, 2023

Add x-only ECDH functionality to ecdh module b66e0d1ea2

Update ECDH benchmarks to include pubkey decode and add x-only b62b7b72fa

Add X-only ECDH unit tests 0e8602cd5f

Add x-only ECDH ctime tests a732222f9a

sipa force-pushed on Sep 19, 2023

sipa commented at 4:58 pm on September 19, 2023: contributor

@real-or-random

Will do today or tomorrow!

Never mind, rebased.

jonasnick added this to the milestone 0.4.1 or 0.5.0 on Sep 20, 2023

real-or-random commented at 5:18 pm on September 20, 2023: contributor

Concept ACK

Not entirely sure if there’s demand for this, but we have it in the code base, and we have an ECDH module already, so I think it’s pragmatic to expose this.

But this should hash both public keys into the shared secret. :)

real-or-random removed this from the milestone 0.4.1 or 0.5.0 on Nov 20, 2023

Sjors commented at 11:41 am on January 5, 2024: member

Concept ACK.

Stratum v2 uses x-only ECDH (but not ElligatorSwift), so this would be quite useful.

I’ll try if I can get this PR to work with https://github.com/bitcoin/bitcoin/pull/28983

sipa commented at 1:00 pm on January 5, 2024: contributor

@Sjors This reminds me to pick this up again. We agreed that the interface needed a rewrite to use the safer approach the ellswift module uses (with a default hasher that includes the two pubkeys). I’m sure that whatever Sv2 uses can be adapted to fit in that model.

Sjors commented at 1:38 pm on January 5, 2024: member

When naively performing ECDH with x-only keys, by just converting it to a compressed key that starts with 0x02, are the two sides supposed to get the same result?

ECDH(Alice_priv, Bob_pub_x) == ECDH(Bob_priv, Alice_pub_x)

Or only if Alice_priv and Bob_priv are chosen such that their public key has even Y, i.e. the compressed key starts with 0x02? Or is that not guaranteed at all?

sipa commented at 2:27 pm on January 5, 2024: contributor

@Sjors That will work. In other words, negating the private key of one of the sides (or of both sides) won’t change the resulting shared X coordinate. It will change the Y coordinate of the resulting shared point, but in x-only ECDH you normally ignore that Y coordinate.

Sjors commented at 2:48 pm on January 5, 2024: member

Mmm, but when using secp256k1_ecdh it does matter, doesn’t it? Because the default ecdh_hash_function_sha256 uses the y-coordinate (version = (y32[31] & 0x01) | 0x02;).

Is that function based on any RFC or existing standard?

sipa commented at 2:50 pm on January 5, 2024: contributor

@Sjors Not that I know of. What does Sv2 use?

Sjors commented at 3:01 pm on January 5, 2024: member

@sipa the spec is ambiguous on the ECDH details: https://github.com/stratum-mining/sv2-spec/blob/main/04-Protocol-Security.md#4311-ec-point-encoding-remarks

The Template Provider PR above uses ecdh_hash_function_sha256: https://github.com/bitcoin/bitcoin/pull/28983/commits/27928dba41bb0186bfe82e6668c0f1024f056772 (link to commit since I’m about to refactor this)

When you call that with a private key that has an odd corresponding public key, then both sides of the connection will generate a different output for CKey::ECDH(). That in turns breaks the cypher.

sipa commented at 3:07 pm on January 5, 2024: contributor

@Sjors Heh, it’s not specified how the shared point is serialized? That’s worth addressing in the spec if possible (… or if it can still be changed, use ellswift?).

In any case, yes, if the full compressed point serialization of the shared point is used as secret, then you need to make sure the private key matches the (full) public key. That means it’s not actually x-only ECDH, and this PR (or its envisioned successor) won’t be usable, as it doesn’t even compute the resulting shared Y coordinate.

Sjors commented at 3:43 pm on January 5, 2024: member

I think the spec can still be modified / clarified. It should probably only use the x-component of the shared point. That seems more consistent with the use of x-only public keys in the rest of the sv2 spec.

sipa commented at 5:43 pm on January 5, 2024: contributor

@Sjors Is it an option to use ellswift negotiation instead? It’s effectively a drop-in replacement for ECDH, except the public keys are 64 bytes instead of 32. Depending on how exactly Noise is being used to encode messages boundaries, that may actually be sufficient to make Sv2 have a pseudorandom bytestream.

Sjors commented at 10:55 am on January 6, 2024: member

On the Bitcoin Core side that would be trivial to add support for. The Stratum Reference Implementation is written in Rust, is there already a library for that? Or I guess it would use libsecp indirectly anyway?

sipa commented at 2:27 pm on January 7, 2024: contributor

@Sjors rust-secp256k1 appears to have ellswift bindings, but I don’t know anything about Rust myself.

Sjors cross-referenced this on Jan 9, 2024 from issue ECDH is underspecified and not x-only by Sjors

in include/secp256k1_ecdh.h:95 in a732222f9a

90+ *                       secp256k1_ecdh_xonly+hash_function_sha256 is used
91+ *                       (in which case, 32 bytes will be written to output).
92+ *           data:       arbitrary data pointer that is passed through to hashfp
93+ *                       (can be NULL for secp256k1_ecdh_xonly_hash_function_sha256).
94+ *
95+ * The function is constant time in seckey. It is not constant time in xpubkey, hashfp, or the output.

real-or-random commented at 10:55 pm on February 6, 2024:

I truly hope that it’s constant time in the output (if hashfp is constant time).

real-or-random cross-referenced this on Feb 6, 2024 from issue RecPedPop: use ECDH between hostkeys to drop the enckeys round by jonasnick

Sjors commented at 8:19 am on February 7, 2024: member

There’s pretty good progress in Stratum v2 on switching to EllSwift for both encoding the key on the wire and performing ECDH, so we probably won’t need this.

Add x-only ECDH support to ecdh module #1198