This PR adds the ability to encode CPubKey objects to their pseudorandom elligator-swift representation. Depends on https://github.com/bitcoin-core/secp256k1/pull/1129.
The first 2 commits enable the availability of that upstream code and will be removed once https://github.com/bitcoin-core/secp256k1/pull/1129 is merged. Only last 3 commits need review here.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--021abf342d371248e50ceaed478a90ca-->
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.
<!--174a7506f384e20aa4161008e828411d-->
Reviewers, this pull request conflicts with the following ones:
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.
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.
343 | + if (!secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, vch, size())) { 344 | + return {}; 345 | + } 346 | + 347 | + uint8_t r32[32]; 348 | + GetStrongRandBytes(r32, 32);
It's a pretty unfortunate I think that the whole random module needs to be included in libbitcoinconsensus just because it include pubkey (which then wouldn't be part of libbitcoinconsensus), and this adds a dependency on randomness to pubkey.
Alternatives are putting the conversion between pubkey and ellsq encoding in a different modulo than pubkey, or passing in randomness explicitly as argument to EllSqEncode.
Also, it's overkill to use strong random bytes here.
Done. Passing in random bytes to EllSqEncode now.
350 | + EllSqPubKey encoded_pubkey; 351 | + secp256k1_ellsq_encode(secp256k1_context_verify, encoded_pubkey.data(), r32, &pubkey); 352 | + return encoded_pubkey; 353 | +} 354 | + 355 | +CPubKey::CPubKey(const EllSqPubKey& encoded_pubkey, bool compressed) {
There is no reason to support uncompressed public keys here I think.
EDIT: added a missing negation
Done.
Pushed again to fix a CI issue. I had forgotten to appropriately rollback my Makefile.am changes.
Ready for review.
Removed randomness used in a fuzz test that was not derived from the fuzz seed. Ready for further review.
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.
original_pubkey is computed from the private key and is fed into EllSqEncode() along with 32 random bytes to obtain 64 bytes ellsq_encoded_pubkeyellsq_encoded_pubkey using the CPubKey constructor to obtain a 33 bytes decoded_pubkey.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.318 | +{ 319 | + if(buffer.size() < 64) { 320 | + return; 321 | + } 322 | + 323 | + 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!
305 | @@ -305,4 +306,25 @@ FUZZ_TARGET_INIT(key, initialize_key) 306 | assert(key == loaded_key); 307 | } 308 | } 309 | + 310 | + { 311 | + std::array<uint8_t, 32> rnd32; 312 | + 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.
314 | + } 315 | +} 316 | + 317 | +FUZZ_TARGET_INIT(ellsq, initialize_key) 318 | +{ 319 | + 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.
Done.
Addressed review comments from @sipa and @MarcoFalke. Ready for further review.
Rebased and updated src/secp256k1 to be up to date with the rebase on https://github.com/bitcoin-core/secp256k1/pull/982
Ready for further review.
The Win64 build failure is due to bringing in https://github.com/bitcoin-core/secp256k1/pull/982 (that is ahead of the subtree secp version) in the first two commits (which will not be merged with this PR). I'll continue to investigate and ask for help on that, but it should go away when elligator-squared is brought into secp/master and updated in our subtree.
We can continue review here in the meantime.
The Win64 build failure...
can be fixed with the following patch
--- a/build_msvc/libsecp256k1/libsecp256k1.vcxproj
+++ b/build_msvc/libsecp256k1/libsecp256k1.vcxproj
@@ -8,6 +8,10 @@
<ConfigurationType>StaticLibrary</ConfigurationType>
</PropertyGroup>
<ItemGroup>
+ <ClCompile Include="..\..\src\secp256k1\src\precomputed_ecmult.c" />
+ <ClCompile Include="..\..\src\secp256k1\src\precomputed_ecmult_gen.c" />
+ <ClCompile Include="..\..\src\secp256k1\src\precompute_ecmult.c" />
+ <ClCompile Include="..\..\src\secp256k1\src\precompute_ecmult_gen.c" />
<ClCompile Include="..\..\src\secp256k1\src\secp256k1.c" />
</ItemGroup>
<ItemDefinitionGroup>
which was suggested by @sipsorcery.
The precompute_ecmult.c and precompute_ecmult_gen.c shouldn't be needed; they are for computing the tables, but the tables are checked into the repository. In fact, I'm surprised it even works with those added, as they result in multiple main() functions.
In fact, I'm surprised it even works with those added, as they result in multiple main() functions.
The msvc compiler did generate a warning about multiple main()'s. I assume it chooses the first one it finds, which of course will be problematic it it's the wrong one.
Thank you for your help @sipsorcery @hebasto! I definitely would not have figured this out on my own. The suggested diff worked.
@sipa, I added only precomputed_* compilation units and did not need precompute_* for the Win64 test to pass.
Ready for further review.
Rebased. Moved to new spec's elligator-swift instead of elligator-squared resulting in >2x speedup. Ready for further review. The linter failure will be resolved once the upstream code is in secp.
With the new integrated XDH in libsecp256k1, we no longer need to decode the elligator-swift pubkey representation in bitcoin core. In addition, this push depends on a new branch which has a modified version of elligator-swift that can encode/decode the parity of the y-coordinate while still using only 64 bytes.
Ready for further review.
344 | + if (!secp256k1_ec_pubkey_parse(secp256k1_context_verify, &pubkey, vch, size())) { 345 | + return {}; 346 | + } 347 | + 348 | + EllSwiftPubKey encoded_pubkey; 349 | + secp256k1_ellswift_encode(secp256k1_context_verify, encoded_pubkey.data(), &pubkey, rnd32.data());
I left this also as a comment on a different PR, perhaps the wrong one.
There shouldn't be a need to invoke secp256k1_ellswift_encode here, or have this as a method on CPubKey. The new secp256k1_ellswift_create function can go directly from private key to ellswift encoding, without needing to convert to a normal public key in the mean time. I think this would be preferable to have as a function on CKey instead, and not involve any CPubKey at all.
secp256k1_ellswift_create is safer (doesn't need additional randomness) and there are some (currently unimplemented) optimizations that may make it faster than the combination of secp256k1_ec_pubkey_create + secp256k1_ellswift_encode.
Done! Thanks for the reminder.
Addressed comment, ready for further review.
Pushed to fix a clang-tidy error discovered in a downstream PR. Ready for further review.
Latest push:
EllSqPubKey to be an array of std::byte instead of uint8_t to be similar to the other objects in the project.
Latest push:
secp256k1_ellswift_create() does not need to be supplied auxrnd32 when the private key is unpredictable.
Latest push:
Latest push:
Latest push:
Rebased. Brought in latest from https://github.com/bitcoin-core/secp256k1/pull/1129
Rebased.
332 | @@ -332,6 +333,17 @@ bool CKey::Derive(CKey& keyChild, ChainCode &ccChild, unsigned int nChild, const 333 | return ret; 334 | } 335 | 336 | +std::optional<EllSwiftPubKey> CKey::EllSwiftEncode() const 337 | +{ 338 | + EllSwiftPubKey encoded_pubkey; 339 | + if (!secp256k1_ellswift_create(secp256k1_context_sign, 340 | + reinterpret_cast<unsigned char*>(encoded_pubkey.data()), 341 | + keydata.data(), nullptr)) {
This should probably pass in 32 bytes of randomness still. The algorithm should yield an encoding indistinguishable from random without it, but it's certainly better to provide it if we can.
In order to make fuzzing useful, the randomness would need to be passed in explicitly (e.g. as a const uint256& argument to CKey::EllSwiftEncode).
Done.
346 | @@ -344,4 +347,40 @@ BOOST_AUTO_TEST_CASE(bip340_test_vectors) 347 | } 348 | } 349 | 350 | +CPubKey EllSwiftDecode(const EllSwiftPubKey& encoded_pubkey) 351 | +{ 352 | + auto secp256k1_context_verify = secp256k1_context_static;
These first 3 lines are superfluous I think. The static context always exists, and an encoded_pubkey is a 64-byte array, it can only be 64 bytes.
You're right that was left over from older code where it was a vector instead of an array. Thanks for the catch. Fixed.
369 | + for (const auto& secret : {strSecret1, strSecret2, strSecret1C, strSecret2C}) { 370 | + CKey key = DecodeSecret(secret); 371 | + BOOST_CHECK(key.IsValid()); 372 | + 373 | + auto ellswift_encoded_pubkey = key.EllSwiftEncode(); 374 | +
This probably needs a BOOST_CHECK(ellswift_encoded_pubkey.has_value());, otherwise you'd hit UB if somehow nullopt is returned.
EDIT: unless the std::optional is dropped.
dropped std::optional
312 | + auto key_bytes = fdp.ConsumeBytes<uint8_t>(32); 313 | + key_bytes.resize(32); 314 | + CKey key; 315 | + key.Set(key_bytes.begin(), key_bytes.end(), fdp.ConsumeBool()); 316 | + 317 | + (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.
332 | @@ -332,6 +333,17 @@ bool CKey::Derive(CKey& keyChild, ChainCode &ccChild, unsigned int nChild, const 333 | return ret; 334 | } 335 | 336 | +std::optional<EllSwiftPubKey> CKey::EllSwiftEncode() const
No need to return an std::optional here. If the CKey is valid, the encoding will always succeed. You could e.g. assert(fValid); to require a valid CKey as object to operate on.
Fixed
Rebased. Brought in changes from https://github.com/bitcoin-core/secp256k1/pull/1129.
Rebased. Brought in changes from https://github.com/bitcoin-core/secp256k1/pull/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
427bc3cdcf Merge bitcoin-core/secp256k1#1236: Update comment for secp256k1_modinv32_inv256
647f0a5cb1 Update comment for secp256k1_modinv32_inv256
5658209459 Merge bitcoin-core/secp256k1#1228: release cleanup: bump version after 0.3.0
28e63f7ea7 release cleanup: bump version after 0.3.0
git-subtree-dir: src/secp256k1
git-subtree-split: 8034c67a48dc1334bc74ee4ba239111a23d9789e
Rebased.
<!--cf906140f33d8803c4a75a2196329ecb-->
🐙 This pull request conflicts with the target branch and needs rebase.
