BIP324: CKey encode/decode to elligator-swift #23432

dhruv · 2021-11-03T17:14:42Z

This PR adds the ability to encode CPubKey objects to their pseudorandom elligator-swift representation. Depends on bitcoin-core/secp256k1#1129.

The first 2 commits enable the availability of that upstream code and will be removed once bitcoin-core/secp256k1#1129 is merged. Only last 3 commits need review here.

DrahtBot · 2021-11-04T08:33:39Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	stratospher

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#27445 (Update src/secp256k1 subtree to release v0.3.1 by sipa)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

hebasto · 2021-11-05T09:20:13Z

Wrt a failed Win64 cross-compiled build.

I've managed to successfully link libbitcoinconsensus.la with the following patch:

--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -507,8 +507,6 @@ libbitcoin_consensus_a_SOURCES = \
   primitives/transaction.h \
   pubkey.cpp \
   pubkey.h \
-  random.cpp \
-  random.h \
   script/bitcoinconsensus.cpp \
   script/interpreter.cpp \
   script/interpreter.h \
@@ -743,7 +741,7 @@ include_HEADERS = script/bitcoinconsensus.h
 libbitcoinconsensus_la_SOURCES = support/cleanse.cpp $(crypto_libbitcoin_crypto_base_a_SOURCES) $(libbitcoin_consensus_a_SOURCES)
 
 libbitcoinconsensus_la_LDFLAGS = $(AM_LDFLAGS) -no-undefined $(RELDFLAGS)
-libbitcoinconsensus_la_LIBADD = $(LIBSECP256K1)
+libbitcoinconsensus_la_LIBADD = $(LIBSECP256K1) $(LIBBITCOIN_UTIL) $(BOOST_LIBS)
 libbitcoinconsensus_la_CPPFLAGS = $(AM_CPPFLAGS) -I$(builddir)/obj -I$(srcdir)/secp256k1/include -DBUILD_BITCOIN_INTERNAL
 libbitcoinconsensus_la_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)

Obviously, this workaround is suboptimal:

  CXXLD    libbitcoinconsensus.la

*** Warning: Linking the shared library libbitcoinconsensus.la against the
*** static library libbitcoin_util.a is not portable!

For better approach, probably source code re-organization should be considered.

src/pubkey.cpp

dhruv · 2021-11-06T20:07:50Z

Thank you for the review and suggestions, @hebasto, @sipa. Addressed the comments, ready for further review.

dhruv · 2021-11-06T23:30:09Z

Pushed again to fix a CI issue. I had forgotten to appropriately rollback my Makefile.am changes.

Ready for review.

dhruv · 2021-11-19T22:59:27Z

Removed randomness used in a fuzz test that was not derived from the fuzz seed. Ready for further review.

stratospher

Concept ACK.

Encoding	Decoding

This PR introduces 2 pubkey functions EllSqEncode() for encoding 33 byte/65 byte pubkey to a 64 byte Elligator square encoding and a constructor CPubKey to decode the 64 byte Elligator square encoding to a 33 byte pubkey.

In the unit test, a 33 byte/65 byte public key original_pubkey is computed from the private key and is fed into EllSqEncode() along with 32 random bytes to obtain 64 bytes ellsq_encoded_pubkey
Then decoding is done on the 64 bytes ellsq_encoded_pubkey using the CPubKey constructor to obtain a 33 bytes decoded_pubkey.
Finally it is checked if original_pubkey and decoded_pubkey are the same. When original_pubkey is uncompressed, the 33 bytes decoded_pubkey needs to be uncompressed to 65 bytes before the comparison.

sipa · 2021-11-23T21:32:23Z

src/test/fuzz/key.cpp

+        return;
+    }
+
+    auto ellsq_bytes = buffer.first(64);


You could do a stronger test here: start with a pubkey drawn from the fuzz data, and if it is valid, elligator encode it (with additional randomness drawn from the fuzz data), decode it, and see if it matches the original pubkey.

Thanks. Done!

maflcko · 2021-11-23T21:38:26Z

src/test/fuzz/key.cpp

+
+    {
+        std::array<uint8_t, 32> rnd32;
+        memcpy(rnd32.data(), &random_uint256, 32);


random_uint256 is uniformly distributed, making it harder for the fuzz engine to discover potential edge cases

Makes sense. Fixed. I ended up combining the encode/decode fuzzing.

maflcko · 2021-11-23T21:41:15Z

src/test/fuzz/key.cpp

+
+FUZZ_TARGET_INIT(ellsq, initialize_key)
+{
+    if(buffer.size() < 64) {


You may install clang-format and run the https://github.com/bitcoin/bitcoin/tree/master/contrib/devtools#clang-format-diffpy script to preempt whitespace nitpicking.

dhruv · 2021-11-25T17:28:39Z

Addressed review comments from @sipa and @MarcoFalke. Ready for further review.

dhruv · 2022-01-26T15:44:45Z

Rebased and updated src/secp256k1 to be up to date with the rebase on bitcoin-core/secp256k1#982

Ready for further review.

src/test/key_tests.cpp

sipa · 2023-01-14T14:31:29Z

src/test/fuzz/key.cpp

+    CKey key;
+    key.Set(key_bytes.begin(), key_bytes.end(), fdp.ConsumeBool());
+
+    (void)key.EllSwiftEncode();


This could also decode back, and test that the public keys correspond (if you move the EllSwiftDecode function to CPubKey, for example).

Added this check, but I opted to decode locally in the fuzz test so as to not add code to CPubKey that would be used only for tests.

src/key.cpp

dhruv · 2023-01-17T06:20:36Z

Latest push:

Addressed review comments from @sipa

dhruv · 2023-02-02T06:26:16Z

Rebased. Brought in changes from bitcoin-core/secp256k1#1129.

dhruv · 2023-03-08T15:27:40Z

Rebased. Brought in changes from bitcoin-core/secp256k1#1129.

8034c67a48 Add doc/ellswift.md with ElligatorSwift explanation e90aa4e62e Add ellswift testing to CI 131faedd8a Add ElligatorSwift ctime tests 198a04c058 Add tests for ElligatorSwift 9984bfe476 Add ElligatorSwift benchmarks f053da3ab7 Add ellswift module implementing ElligatorSwift 76c64be237 Add functions to test if X coordinate is valid aff948fca2 Add benchmark for key generation 5ed9314d6d Add exhaustive tests for ecmult_const_xonly b69fe88d5e Add x-only ecmult_const version for x=n/d 427bc3c Merge bitcoin-core/secp256k1#1236: Update comment for secp256k1_modinv32_inv256 647f0a5 Update comment for secp256k1_modinv32_inv256 5658209 Merge bitcoin-core/secp256k1#1228: release cleanup: bump version after 0.3.0 28e63f7 release cleanup: bump version after 0.3.0 git-subtree-dir: src/secp256k1 git-subtree-split: 8034c67a48dc1334bc74ee4ba239111a23d9789e

…llsq

dhruv · 2023-03-21T04:02:21Z

Rebased.

DrahtBot · 2023-04-15T13:20:42Z

🐙 This pull request conflicts with the target branch and needs rebase.

fanquake · 2023-04-18T00:39:33Z

Closing for now. See #27479.

3168b08 Bench test for EllSwift ECDH (Pieter Wuille) 42d759f Bench tests for CKey->EllSwift (dhruv) 2e5a8a4 Fuzz test for Ellswift ECDH (dhruv) c3ac9f5 Fuzz test for CKey->EllSwift->CPubKey creation/decoding (dhruv) aae432a Unit test for ellswift creation/decoding roundtrip (dhruv) eff72a0 Add ElligatorSwift key creation and ECDH logic (Pieter Wuille) 42239f8 Enable ellswift module in libsecp256k1 (dhruv) 901336e Squashed 'src/secp256k1/' changes from 4258c54..705ce7e (Pieter Wuille) Pull request description: This replaces #23432 and part of #23561. This PR introduces all of the ElligatorSwift-related changes (libsecp256k1 updates, generation, decoding, ECDH, tests, fuzzing, benchmarks) needed for BIP324. ElligatorSwift is a special 64-byte encoding format for public keys introduced in libsecp256k1 in bitcoin-core/secp256k1#1129. It has the property that *every* 64-byte array is a valid encoding for some public key, and every key has approximately $2^{256}$ encodings. Furthermore, it is possible to efficiently generate a uniformly random encoding for a given public key or private key. This is used for the key exchange phase in BIP324, to achieve a byte stream that is entirely pseudorandom, even before the shared encryption key is established. ACKs for top commit: instagibbs: reACK 3168b08 achow101: ACK 3168b08 theStack: re-ACK 3168b08 Tree-SHA512: 308ac3d33e9a2deecb65826cbf0390480a38de201918429c35c796f3421cdf94c5501d027a043ae8f012cfaa0584656da1de6393bfba3532ab4c20f9533f06a6

dhruv force-pushed the bip324-ellsq branch from eddca6b to 2ca1400 Compare November 3, 2021 17:18

DrahtBot added Build system Upstream Utils/log/libs labels Nov 3, 2021

dhruv force-pushed the bip324-ellsq branch 3 times, most recently from 734c97e to 3e562de Compare November 4, 2021 00:27

DrahtBot mentioned this pull request Nov 4, 2021

Update libsecp256k1 subtree to current master #23383

Merged

dhruv force-pushed the bip324-ellsq branch from 3e562de to 07568d2 Compare November 4, 2021 18:35

sipa reviewed Nov 6, 2021

View reviewed changes

src/pubkey.cpp Outdated Show resolved Hide resolved

sipa reviewed Nov 6, 2021

View reviewed changes

src/pubkey.cpp Outdated Show resolved Hide resolved

dhruv force-pushed the bip324-ellsq branch from 07568d2 to dc19ab7 Compare November 6, 2021 20:06

dhruv force-pushed the bip324-ellsq branch from dc19ab7 to 729d062 Compare November 6, 2021 21:13

laanwj added the P2P label Nov 10, 2021

fanquake mentioned this pull request Nov 19, 2021

#23432 CI #23550

Closed

dhruv force-pushed the bip324-ellsq branch from 729d062 to 405f64e Compare November 19, 2021 22:58

DrahtBot mentioned this pull request Nov 21, 2021

BIP324: Handshake prerequisites #23561

Closed

stratospher reviewed Nov 23, 2021

View reviewed changes

sipa reviewed Nov 23, 2021

View reviewed changes

maflcko reviewed Nov 23, 2021

View reviewed changes

dhruv force-pushed the bip324-ellsq branch from 405f64e to 600efe4 Compare November 25, 2021 17:27

DrahtBot added the Needs rebase label Dec 18, 2021

dhruv force-pushed the bip324-ellsq branch from 600efe4 to 67f1fc0 Compare January 26, 2022 15:19

sipa reviewed Jan 14, 2023

View reviewed changes

src/test/key_tests.cpp Show resolved Hide resolved

sipa reviewed Jan 14, 2023

View reviewed changes

src/key.cpp Outdated Show resolved Hide resolved

dhruv force-pushed the bip324-ellsq branch from 74b24f9 to 95d241d Compare January 17, 2023 06:10

DrahtBot added the Needs rebase label Jan 28, 2023

dhruv force-pushed the bip324-ellsq branch from 95d241d to 58c5a3c Compare February 2, 2023 06:22

DrahtBot removed the Needs rebase label Feb 2, 2023

dhruv force-pushed the bip324-ellsq branch from 58c5a3c to 5a8f42b Compare March 8, 2023 15:23

DrahtBot mentioned this pull request Mar 9, 2023

Update src/secp256k1 subtree to upstream release v0.3.0 #27230

Merged

DrahtBot added the Needs rebase label Mar 12, 2023

dhruv added 5 commits March 20, 2023 15:34

Merge commit '963f9a5c6159d985eb16b115a7d27027074827ed' into bip324-e…

1f0eca0

…llsq

Encode CKey to ElligatorSwift representation

13423e6

Bench tests for CKey->EllSwift

697a237

Fuzz tests for CKey->EllSwift

ae4b695

dhruv force-pushed the bip324-ellsq branch from 5a8f42b to ae4b695 Compare March 21, 2023 04:02

DrahtBot removed the Needs rebase label Mar 21, 2023

DrahtBot mentioned this pull request Apr 11, 2023

Update src/secp256k1 subtree to release v0.3.1 #27445

Merged

DrahtBot added the Needs rebase label Apr 15, 2023

sipa mentioned this pull request Apr 17, 2023

BIP324: ElligatorSwift integrations #27479

Merged

fanquake closed this Apr 18, 2023

sipa mentioned this pull request Sep 8, 2023

BIP324 tracking issue #27634

Closed

43 tasks

bitcoin locked and limited conversation to collaborators Apr 17, 2024

BIP324: CKey encode/decode to elligator-swift #23432

BIP324: CKey encode/decode to elligator-swift #23432

Uh oh!

Conversation

dhruv commented Nov 3, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Nov 4, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Reviews

Conflicts

Uh oh!

hebasto commented Nov 5, 2021

Uh oh!

Uh oh!

Uh oh!

dhruv commented Nov 6, 2021

Uh oh!

dhruv commented Nov 6, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dhruv commented Nov 19, 2021

Uh oh!

stratospher left a comment

Choose a reason for hiding this comment

Uh oh!

sipa Nov 23, 2021

Choose a reason for hiding this comment

Uh oh!

dhruv Nov 25, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Nov 23, 2021

Choose a reason for hiding this comment

Uh oh!

dhruv Nov 25, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Nov 23, 2021

Choose a reason for hiding this comment

Uh oh!

dhruv Nov 25, 2021

Choose a reason for hiding this comment

Uh oh!

dhruv commented Nov 25, 2021

Uh oh!

dhruv commented Jan 26, 2022

Uh oh!

Uh oh!

sipa Jan 14, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dhruv Jan 17, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

dhruv commented Jan 17, 2023

Uh oh!

dhruv commented Feb 2, 2023

Uh oh!

dhruv commented Mar 8, 2023

Uh oh!

dhruv commented Mar 21, 2023

Uh oh!

DrahtBot commented Apr 15, 2023

Uh oh!

fanquake commented Apr 18, 2023

Uh oh!

Uh oh!

dhruv commented Nov 3, 2021 •

edited

Loading

DrahtBot commented Nov 4, 2021 •

edited

Loading

dhruv commented Nov 6, 2021 •

edited

Loading

sipa Jan 14, 2023 •

edited

Loading