diff options
Diffstat (limited to 'src')
83 files changed, 2068 insertions, 1121 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index 8c12aee217..389be6c058 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -61,6 +61,7 @@ EXTRA_LIBRARIES += \ lib_LTLIBRARIES = $(LIBBITCOINCONSENSUS) bin_PROGRAMS = +noinst_PROGRAMS = TESTS = BENCHMARKS = diff --git a/src/Makefile.test.include b/src/Makefile.test.include index a14adc7876..c754eebf9a 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -4,6 +4,7 @@ TESTS += test/test_bitcoin bin_PROGRAMS += test/test_bitcoin +noinst_PROGRAMS += test/test_bitcoin_fuzzy TEST_SRCDIR = test TEST_BINARY=test/test_bitcoin$(EXEEXT) @@ -38,6 +39,7 @@ RAW_TEST_FILES = GENERATED_TEST_FILES = $(JSON_TEST_FILES:.json=.json.h) $(RAW_TEST_FILES:.raw=.raw.h) +# test_bitcoin binary # BITCOIN_TESTS =\ test/arith_uint256_tests.cpp \ test/scriptnum10.h \ @@ -53,6 +55,7 @@ BITCOIN_TESTS =\ test/coins_tests.cpp \ test/compress_tests.cpp \ test/crypto_tests.cpp \ + test/cuckoocache_tests.cpp \ test/DoS_tests.cpp \ test/getarg_tests.cpp \ test/hash_tests.cpp \ @@ -119,6 +122,25 @@ test_test_bitcoin_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) -s if ENABLE_ZMQ test_test_bitcoin_LDADD += $(ZMQ_LIBS) endif +# + +# test_bitcoin_fuzzy binary # +test_test_bitcoin_fuzzy_SOURCES = test/test_bitcoin_fuzzy.cpp +test_test_bitcoin_fuzzy_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) +test_test_bitcoin_fuzzy_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) +test_test_bitcoin_fuzzy_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) + +test_test_bitcoin_fuzzy_LDADD = \ + $(LIBUNIVALUE) \ + $(LIBBITCOIN_SERVER) \ + $(LIBBITCOIN_COMMON) \ + $(LIBBITCOIN_UTIL) \ + $(LIBBITCOIN_CONSENSUS) \ + $(LIBBITCOIN_CRYPTO) \ + $(LIBSECP256K1) + +test_test_bitcoin_fuzzy_LDADD += $(BOOST_LIBS) $(CRYPTO_LIBS) +# nodist_test_test_bitcoin_SOURCES = $(GENERATED_TEST_FILES) diff --git a/src/bench/crypto_hash.cpp b/src/bench/crypto_hash.cpp index 168006154f..737d3572ae 100644 --- a/src/bench/crypto_hash.cpp +++ b/src/bench/crypto_hash.cpp @@ -22,7 +22,7 @@ static void RIPEMD160(benchmark::State& state) uint8_t hash[CRIPEMD160::OUTPUT_SIZE]; std::vector<uint8_t> in(BUFFER_SIZE,0); while (state.KeepRunning()) - CRIPEMD160().Write(begin_ptr(in), in.size()).Finalize(hash); + CRIPEMD160().Write(in.data(), in.size()).Finalize(hash); } static void SHA1(benchmark::State& state) @@ -30,7 +30,7 @@ static void SHA1(benchmark::State& state) uint8_t hash[CSHA1::OUTPUT_SIZE]; std::vector<uint8_t> in(BUFFER_SIZE,0); while (state.KeepRunning()) - CSHA1().Write(begin_ptr(in), in.size()).Finalize(hash); + CSHA1().Write(in.data(), in.size()).Finalize(hash); } static void SHA256(benchmark::State& state) @@ -38,7 +38,7 @@ static void SHA256(benchmark::State& state) uint8_t hash[CSHA256::OUTPUT_SIZE]; std::vector<uint8_t> in(BUFFER_SIZE,0); while (state.KeepRunning()) - CSHA256().Write(begin_ptr(in), in.size()).Finalize(hash); + CSHA256().Write(in.data(), in.size()).Finalize(hash); } static void SHA256_32b(benchmark::State& state) @@ -46,7 +46,7 @@ static void SHA256_32b(benchmark::State& state) std::vector<uint8_t> in(32,0); while (state.KeepRunning()) { for (int i = 0; i < 1000000; i++) { - CSHA256().Write(begin_ptr(in), in.size()).Finalize(&in[0]); + CSHA256().Write(in.data(), in.size()).Finalize(&in[0]); } } } @@ -56,7 +56,7 @@ static void SHA512(benchmark::State& state) uint8_t hash[CSHA512::OUTPUT_SIZE]; std::vector<uint8_t> in(BUFFER_SIZE,0); while (state.KeepRunning()) - CSHA512().Write(begin_ptr(in), in.size()).Finalize(hash); + CSHA512().Write(in.data(), in.size()).Finalize(hash); } static void SipHash_32b(benchmark::State& state) diff --git a/src/bench/verify_script.cpp b/src/bench/verify_script.cpp index dc3940cdbd..91b8c44472 100644 --- a/src/bench/verify_script.cpp +++ b/src/bench/verify_script.cpp @@ -91,7 +91,7 @@ static void VerifyScriptBench(benchmark::State& state) CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); stream << txSpend; int csuccess = bitcoinconsensus_verify_script_with_amount( - begin_ptr(txCredit.vout[0].scriptPubKey), + txCredit.vout[0].scriptPubKey.data(), txCredit.vout[0].scriptPubKey.size(), txCredit.vout[0].nValue, (const unsigned char*)&stream[0], stream.size(), 0, flags, nullptr); diff --git a/src/cuckoocache.h b/src/cuckoocache.h new file mode 100644 index 0000000000..efd6a820b5 --- /dev/null +++ b/src/cuckoocache.h @@ -0,0 +1,457 @@ +// Copyright (c) 2016 Jeremy Rubin +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef _BITCOIN_CUCKOOCACHE_H_ +#define _BITCOIN_CUCKOOCACHE_H_ + +#include <array> +#include <algorithm> +#include <atomic> +#include <cstring> +#include <cmath> +#include <memory> +#include <vector> + + +/** namespace CuckooCache provides high performance cache primitives + * + * Summary: + * + * 1) bit_packed_atomic_flags is bit-packed atomic flags for garbage collection + * + * 2) cache is a cache which is performant in memory usage and lookup speed. It + * is lockfree for erase operations. Elements are lazily erased on the next + * insert. + */ +namespace CuckooCache +{ +/** bit_packed_atomic_flags implements a container for garbage collection flags + * that is only thread unsafe on calls to setup. This class bit-packs collection + * flags for memory efficiency. + * + * All operations are std::memory_order_relaxed so external mechanisms must + * ensure that writes and reads are properly synchronized. + * + * On setup(n), all bits up to n are marked as collected. + * + * Under the hood, because it is an 8-bit type, it makes sense to use a multiple + * of 8 for setup, but it will be safe if that is not the case as well. + * + */ +class bit_packed_atomic_flags +{ + std::unique_ptr<std::atomic<uint8_t>[]> mem; + +public: + /** No default constructor as there must be some size */ + bit_packed_atomic_flags() = delete; + + /** + * bit_packed_atomic_flags constructor creates memory to sufficiently + * keep track of garbage collection information for size entries. + * + * @param size the number of elements to allocate space for + * + * @post bit_set, bit_unset, and bit_is_set function properly forall x. x < + * size + * @post All calls to bit_is_set (without subsequent bit_unset) will return + * true. + */ + bit_packed_atomic_flags(uint32_t size) + { + // pad out the size if needed + size = (size + 7) / 8; + mem.reset(new std::atomic<uint8_t>[size]); + for (uint32_t i = 0; i < size; ++i) + mem[i].store(0xFF); + }; + + /** setup marks all entries and ensures that bit_packed_atomic_flags can store + * at least size entries + * + * @param b the number of elements to allocate space for + * @post bit_set, bit_unset, and bit_is_set function properly forall x. x < + * b + * @post All calls to bit_is_set (without subsequent bit_unset) will return + * true. + */ + inline void setup(uint32_t b) + { + bit_packed_atomic_flags d(b); + std::swap(mem, d.mem); + } + + /** bit_set sets an entry as discardable. + * + * @param s the index of the entry to bit_set. + * @post immediately subsequent call (assuming proper external memory + * ordering) to bit_is_set(s) == true. + * + */ + inline void bit_set(uint32_t s) + { + mem[s >> 3].fetch_or(1 << (s & 7), std::memory_order_relaxed); + } + + /** bit_unset marks an entry as something that should not be overwritten + * + * @param s the index of the entry to bit_unset. + * @post immediately subsequent call (assuming proper external memory + * ordering) to bit_is_set(s) == false. + */ + inline void bit_unset(uint32_t s) + { + mem[s >> 3].fetch_and(~(1 << (s & 7)), std::memory_order_relaxed); + } + + /** bit_is_set queries the table for discardability at s + * + * @param s the index of the entry to read. + * @returns if the bit at index s was set. + * */ + inline bool bit_is_set(uint32_t s) const + { + return (1 << (s & 7)) & mem[s >> 3].load(std::memory_order_relaxed); + } +}; + +/** cache implements a cache with properties similar to a cuckoo-set + * + * The cache is able to hold up to (~(uint32_t)0) - 1 elements. + * + * Read Operations: + * - contains(*, false) + * + * Read+Erase Operations: + * - contains(*, true) + * + * Erase Operations: + * - allow_erase() + * + * Write Operations: + * - setup() + * - setup_bytes() + * - insert() + * - please_keep() + * + * Synchronization Free Operations: + * - invalid() + * - compute_hashes() + * + * User Must Guarantee: + * + * 1) Write Requires synchronized access (e.g., a lock) + * 2) Read Requires no concurrent Write, synchronized with the last insert. + * 3) Erase requires no concurrent Write, synchronized with last insert. + * 4) An Erase caller must release all memory before allowing a new Writer. + * + * + * Note on function names: + * - The name "allow_erase" is used because the real discard happens later. + * - The name "please_keep" is used because elements may be erased anyways on insert. + * + * @tparam Element should be a movable and copyable type + * @tparam Hash should be a function/callable which takes a template parameter + * hash_select and an Element and extracts a hash from it. Should return + * high-entropy hashes for `Hash h; h<0>(e) ... h<7>(e)`. + */ +template <typename Element, typename Hash> +class cache +{ +private: + /** table stores all the elements */ + std::vector<Element> table; + + /** size stores the total available slots in the hash table */ + uint32_t size; + + /** The bit_packed_atomic_flags array is marked mutable because we want + * garbage collection to be allowed to occur from const methods */ + mutable bit_packed_atomic_flags collection_flags; + + /** epoch_flags tracks how recently an element was inserted into + * the cache. true denotes recent, false denotes not-recent. See insert() + * method for full semantics. + */ + mutable std::vector<bool> epoch_flags; + + /** epoch_heuristic_counter is used to determine when a epoch might be aged + * & an expensive scan should be done. epoch_heuristic_counter is + * decremented on insert and reset to the new number of inserts which would + * cause the epoch to reach epoch_size when it reaches zero. + */ + uint32_t epoch_heuristic_counter; + + /** epoch_size is set to be the number of elements supposed to be in a + * epoch. When the number of non-erased elements in a epoch + * exceeds epoch_size, a new epoch should be started and all + * current entries demoted. epoch_size is set to be 45% of size because + * we want to keep load around 90%, and we support 3 epochs at once -- + * one "dead" which has been erased, one "dying" which has been marked to be + * erased next, and one "living" which new inserts add to. + */ + uint32_t epoch_size; + + /** hash_mask should be set to appropriately mask out a hash such that every + * masked hash is [0,size), eg, if floor(log2(size)) == 20, then hash_mask + * should be (1<<20)-1 + */ + uint32_t hash_mask; + + /** depth_limit determines how many elements insert should try to replace. + * Should be set to log2(n)*/ + uint8_t depth_limit; + + /** hash_function is a const instance of the hash function. It cannot be + * static or initialized at call time as it may have internal state (such as + * a nonce). + * */ + const Hash hash_function; + + /** compute_hashes is convenience for not having to write out this + * expression everywhere we use the hash values of an Element. + * + * @param e the element whose hashes will be returned + * @returns std::array<uint32_t, 8> of deterministic hashes derived from e + */ + inline std::array<uint32_t, 8> compute_hashes(const Element& e) const + { + return {{hash_function.template operator()<0>(e) & hash_mask, + hash_function.template operator()<1>(e) & hash_mask, + hash_function.template operator()<2>(e) & hash_mask, + hash_function.template operator()<3>(e) & hash_mask, + hash_function.template operator()<4>(e) & hash_mask, + hash_function.template operator()<5>(e) & hash_mask, + hash_function.template operator()<6>(e) & hash_mask, + hash_function.template operator()<7>(e) & hash_mask}}; + } + + /* end + * @returns a constexpr index that can never be inserted to */ + constexpr uint32_t invalid() const + { + return ~(uint32_t)0; + } + + /** allow_erase marks the element at index n as discardable. Threadsafe + * without any concurrent insert. + * @param n the index to allow erasure of + */ + inline void allow_erase(uint32_t n) const + { + collection_flags.bit_set(n); + } + + /** please_keep marks the element at index n as an entry that should be kept. + * Threadsafe without any concurrent insert. + * @param n the index to prioritize keeping + */ + inline void please_keep(uint32_t n) const + { + collection_flags.bit_unset(n); + } + + /** epoch_check handles the changing of epochs for elements stored in the + * cache. epoch_check should be run before every insert. + * + * First, epoch_check decrements and checks the cheap heuristic, and then does + * a more expensive scan if the cheap heuristic runs out. If the expensive + * scan suceeds, the epochs are aged and old elements are allow_erased. The + * cheap heuristic is reset to retrigger after the worst case growth of the + * current epoch's elements would exceed the epoch_size. + */ + void epoch_check() + { + if (epoch_heuristic_counter != 0) { + --epoch_heuristic_counter; + return; + } + // count the number of elements from the latest epoch which + // have not been erased. + uint32_t epoch_unused_count = 0; + for (uint32_t i = 0; i < size; ++i) + epoch_unused_count += epoch_flags[i] && + !collection_flags.bit_is_set(i); + // If there are more non-deleted entries in the current epoch than the + // epoch size, then allow_erase on all elements in the old epoch (marked + // false) and move all elements in the current epoch to the old epoch + // but do not call allow_erase on their indices. + if (epoch_unused_count >= epoch_size) { + for (uint32_t i = 0; i < size; ++i) + if (epoch_flags[i]) + epoch_flags[i] = false; + else + allow_erase(i); + epoch_heuristic_counter = epoch_size; + } else + // reset the epoch_heuristic_counter to next do a scan when worst + // case behavior (no intermittent erases) would exceed epoch size, + // with a reasonable minimum scan size. + // Ordinarily, we would have to sanity check std::min(epoch_size, + // epoch_unused_count), but we already know that `epoch_unused_count + // < epoch_size` in this branch + epoch_heuristic_counter = std::max(1u, std::max(epoch_size / 16, + epoch_size - epoch_unused_count)); + } + +public: + /** You must always construct a cache with some elements via a subsequent + * call to setup or setup_bytes, otherwise operations may segfault. + */ + cache() : table(), size(), collection_flags(0), epoch_flags(), + epoch_heuristic_counter(), epoch_size(), depth_limit(0), hash_function() + { + } + + /** setup initializes the container to store no more than new_size + * elements. setup rounds down to a power of two size. + * + * setup should only be called once. + * + * @param new_size the desired number of elements to store + * @returns the maximum number of elements storable + **/ + uint32_t setup(uint32_t new_size) + { + // depth_limit must be at least one otherwise errors can occur. + depth_limit = static_cast<uint8_t>(std::log2(static_cast<float>(std::max((uint32_t)2, new_size)))); + size = 1 << depth_limit; + hash_mask = size-1; + table.resize(size); + collection_flags.setup(size); + epoch_flags.resize(size); + // Set to 45% as described above + epoch_size = std::max((uint32_t)1, (45 * size) / 100); + // Initially set to wait for a whole epoch + epoch_heuristic_counter = epoch_size; + return size; + } + + /** setup_bytes is a convenience function which accounts for internal memory + * usage when deciding how many elements to store. It isn't perfect because + * it doesn't account for any overhead (struct size, MallocUsage, collection + * and epoch flags). This was done to simplify selecting a power of two + * size. In the expected use case, an extra two bits per entry should be + * negligible compared to the size of the elements. + * + * @param bytes the approximate number of bytes to use for this data + * structure. + * @returns the maximum number of elements storable (see setup() + * documentation for more detail) + */ + uint32_t setup_bytes(size_t bytes) + { + return setup(bytes/sizeof(Element)); + } + + /** insert loops at most depth_limit times trying to insert a hash + * at various locations in the table via a variant of the Cuckoo Algorithm + * with eight hash locations. + * + * It drops the last tried element if it runs out of depth before + * encountering an open slot. + * + * Thus + * + * insert(x); + * return contains(x, false); + * + * is not guaranteed to return true. + * + * @param e the element to insert + * @post one of the following: All previously inserted elements and e are + * now in the table, one previously inserted element is evicted from the + * table, the entry attempted to be inserted is evicted. + * + */ + inline void insert(Element e) + { + epoch_check(); + uint32_t last_loc = invalid(); + bool last_epoch = true; + std::array<uint32_t, 8> locs = compute_hashes(e); + // Make sure we have not already inserted this element + // If we have, make sure that it does not get deleted + for (uint32_t loc : locs) + if (table[loc] == e) { + please_keep(loc); + epoch_flags[loc] = last_epoch; + return; + } + for (uint8_t depth = 0; depth < depth_limit; ++depth) { + // First try to insert to an empty slot, if one exists + for (uint32_t loc : locs) { + if (!collection_flags.bit_is_set(loc)) + continue; + table[loc] = std::move(e); + please_keep(loc); + epoch_flags[loc] = last_epoch; + return; + } + /** Swap with the element at the location that was + * not the last one looked at. Example: + * + * 1) On first iteration, last_loc == invalid(), find returns last, so + * last_loc defaults to locs[0]. + * 2) On further iterations, where last_loc == locs[k], last_loc will + * go to locs[k+1 % 8], i.e., next of the 8 indicies wrapping around + * to 0 if needed. + * + * This prevents moving the element we just put in. + * + * The swap is not a move -- we must switch onto the evicted element + * for the next iteration. + */ + last_loc = locs[(1 + (std::find(locs.begin(), locs.end(), last_loc) - locs.begin())) & 7]; + std::swap(table[last_loc], e); + // Can't std::swap a std::vector<bool>::reference and a bool&. + bool epoch = last_epoch; + last_epoch = epoch_flags[last_loc]; + epoch_flags[last_loc] = epoch; + + // Recompute the locs -- unfortunately happens one too many times! + locs = compute_hashes(e); + } + } + + /* contains iterates through the hash locations for a given element + * and checks to see if it is present. + * + * contains does not check garbage collected state (in other words, + * garbage is only collected when the space is needed), so: + * + * insert(x); + * if (contains(x, true)) + * return contains(x, false); + * else + * return true; + * + * executed on a single thread will always return true! + * + * This is a great property for re-org performance for example. + * + * contains returns a bool set true if the element was found. + * + * @param e the element to check + * @param erase + * + * @post if erase is true and the element is found, then the garbage collect + * flag is set + * @returns true if the element is found, false otherwise + */ + inline bool contains(const Element& e, const bool erase) const + { + std::array<uint32_t, 8> locs = compute_hashes(e); + for (uint32_t loc : locs) + if (table[loc] == e) { + if (erase) + allow_erase(loc); + return true; + } + return false; + } +}; +} // namespace CuckooCache + +#endif diff --git a/src/init.cpp b/src/init.cpp index 71971a7642..73f885a1bb 100644 --- a/src/init.cpp +++ b/src/init.cpp @@ -1103,6 +1103,8 @@ bool AppInitMain(boost::thread_group& threadGroup, CScheduler& scheduler) LogPrintf("Using config file %s\n", GetConfigFile(GetArg("-conf", BITCOIN_CONF_FILENAME)).string()); LogPrintf("Using at most %i connections (%i file descriptors available)\n", nMaxConnections, nFD); + InitSignatureCache(); + LogPrintf("Using %u threads for script verification\n", nScriptCheckThreads); if (nScriptCheckThreads) { for (int i=0; i<nScriptCheckThreads-1; i++) diff --git a/src/net_processing.cpp b/src/net_processing.cpp index 0137108cf0..74da788ca8 100644 --- a/src/net_processing.cpp +++ b/src/net_processing.cpp @@ -1518,7 +1518,8 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, } CBlock block; - assert(ReadBlockFromDisk(block, it->second, chainparams.GetConsensus())); + bool ret = ReadBlockFromDisk(block, it->second, chainparams.GetConsensus()); + assert(ret); BlockTransactions resp(req); for (size_t i = 0; i < req.indexes.size(); i++) { @@ -1951,7 +1952,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, bool fNewBlock = false; // Since we requested this block (it was in mapBlocksInFlight), force it to be processed, // even if it would not be a candidate for new tip (missing previous block, chain not long enough, etc) - ProcessNewBlock(chainparams, pblock, true, NULL, &fNewBlock); + ProcessNewBlock(chainparams, pblock, true, &fNewBlock); if (fNewBlock) pfrom->nLastBlockTime = GetTime(); } @@ -2133,7 +2134,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, mapBlockSource.emplace(hash, std::make_pair(pfrom->GetId(), true)); } bool fNewBlock = false; - ProcessNewBlock(chainparams, pblock, forceProcessing, NULL, &fNewBlock); + ProcessNewBlock(chainparams, pblock, forceProcessing, &fNewBlock); if (fNewBlock) pfrom->nLastBlockTime = GetTime(); } @@ -2730,7 +2731,8 @@ bool SendMessages(CNode* pto, CConnman& connman) vHeaders.front().GetHash().ToString(), pto->id); //TODO: Shouldn't need to reload block from disk, but requires refactor CBlock block; - assert(ReadBlockFromDisk(block, pBestIndex, consensusParams)); + bool ret = ReadBlockFromDisk(block, pBestIndex, consensusParams); + assert(ret); CBlockHeaderAndShortTxIDs cmpctblock(block, state.fWantsCmpctWitness); int nSendFlags = state.fWantsCmpctWitness ? 0 : SERIALIZE_TRANSACTION_NO_WITNESS; connman.PushMessage(pto, msgMaker.Make(nSendFlags, NetMsgType::CMPCTBLOCK, cmpctblock)); diff --git a/src/netbase.cpp b/src/netbase.cpp index 9118584b80..da94fd4d13 100644 --- a/src/netbase.cpp +++ b/src/netbase.cpp @@ -292,7 +292,7 @@ static bool Socks5(const std::string& strDest, int port, const ProxyCredentials vSocks5Init.push_back(0x01); // # METHODS vSocks5Init.push_back(0x00); // X'00' NO AUTHENTICATION REQUIRED } - ssize_t ret = send(hSocket, (const char*)begin_ptr(vSocks5Init), vSocks5Init.size(), MSG_NOSIGNAL); + ssize_t ret = send(hSocket, (const char*)vSocks5Init.data(), vSocks5Init.size(), MSG_NOSIGNAL); if (ret != (ssize_t)vSocks5Init.size()) { CloseSocket(hSocket); return error("Error sending to proxy"); @@ -317,7 +317,7 @@ static bool Socks5(const std::string& strDest, int port, const ProxyCredentials vAuth.insert(vAuth.end(), auth->username.begin(), auth->username.end()); vAuth.push_back(auth->password.size()); vAuth.insert(vAuth.end(), auth->password.begin(), auth->password.end()); - ret = send(hSocket, (const char*)begin_ptr(vAuth), vAuth.size(), MSG_NOSIGNAL); + ret = send(hSocket, (const char*)vAuth.data(), vAuth.size(), MSG_NOSIGNAL); if (ret != (ssize_t)vAuth.size()) { CloseSocket(hSocket); return error("Error sending authentication to proxy"); @@ -347,7 +347,7 @@ static bool Socks5(const std::string& strDest, int port, const ProxyCredentials vSocks5.insert(vSocks5.end(), strDest.begin(), strDest.end()); vSocks5.push_back((port >> 8) & 0xFF); vSocks5.push_back((port >> 0) & 0xFF); - ret = send(hSocket, (const char*)begin_ptr(vSocks5), vSocks5.size(), MSG_NOSIGNAL); + ret = send(hSocket, (const char*)vSocks5.data(), vSocks5.size(), MSG_NOSIGNAL); if (ret != (ssize_t)vSocks5.size()) { CloseSocket(hSocket); return error("Error sending to proxy"); diff --git a/src/primitives/transaction.h b/src/primitives/transaction.h index 66fefafef5..b594cab458 100644 --- a/src/primitives/transaction.h +++ b/src/primitives/transaction.h @@ -363,7 +363,7 @@ class CTransaction { public: // Default transaction version. - static const int32_t CURRENT_VERSION=1; + static const int32_t CURRENT_VERSION=2; // Changing the default transaction version requires a two step process: first // adapting relay policy by bumping MAX_STANDARD_VERSION, and then later date diff --git a/src/qt/guiutil.cpp b/src/qt/guiutil.cpp index 3feb781db5..8132e4fe0d 100644 --- a/src/qt/guiutil.cpp +++ b/src/qt/guiutil.cpp @@ -117,7 +117,7 @@ static std::string DummyAddress(const CChainParams ¶ms) std::vector<unsigned char> sourcedata = params.Base58Prefix(CChainParams::PUBKEY_ADDRESS); sourcedata.insert(sourcedata.end(), dummydata, dummydata + sizeof(dummydata)); for(int i=0; i<256; ++i) { // Try every trailing byte - std::string s = EncodeBase58(begin_ptr(sourcedata), end_ptr(sourcedata)); + std::string s = EncodeBase58(sourcedata.data(), sourcedata.data() + sourcedata.size()); if (!CBitcoinAddress(s).IsValid()) return s; sourcedata[sourcedata.size()-1] += 1; diff --git a/src/qt/paymentrequestplus.cpp b/src/qt/paymentrequestplus.cpp index 20e1f79ffa..82be4d831f 100644 --- a/src/qt/paymentrequestplus.cpp +++ b/src/qt/paymentrequestplus.cpp @@ -159,14 +159,24 @@ bool PaymentRequestPlus::getMerchant(X509_STORE* certStore, QString& merchant) c std::string data_to_verify; // Everything but the signature rcopy.SerializeToString(&data_to_verify); - EVP_MD_CTX ctx; +#if OPENSSL_VERSION_NUMBER >= 0x10100000L + EVP_MD_CTX *ctx = EVP_MD_CTX_new(); + if (!ctx) throw SSLVerifyError("Error allocating OpenSSL context."); +#else + EVP_MD_CTX _ctx; + EVP_MD_CTX *ctx; + ctx = &_ctx; +#endif EVP_PKEY *pubkey = X509_get_pubkey(signing_cert); - EVP_MD_CTX_init(&ctx); - if (!EVP_VerifyInit_ex(&ctx, digestAlgorithm, NULL) || - !EVP_VerifyUpdate(&ctx, data_to_verify.data(), data_to_verify.size()) || - !EVP_VerifyFinal(&ctx, (const unsigned char*)paymentRequest.signature().data(), (unsigned int)paymentRequest.signature().size(), pubkey)) { + EVP_MD_CTX_init(ctx); + if (!EVP_VerifyInit_ex(ctx, digestAlgorithm, NULL) || + !EVP_VerifyUpdate(ctx, data_to_verify.data(), data_to_verify.size()) || + !EVP_VerifyFinal(ctx, (const unsigned char*)paymentRequest.signature().data(), (unsigned int)paymentRequest.signature().size(), pubkey)) { throw SSLVerifyError("Bad signature, invalid payment request."); } +#if OPENSSL_VERSION_NUMBER >= 0x10100000L + EVP_MD_CTX_free(ctx); +#endif // OpenSSL API for getting human printable strings from certs is baroque. int textlen = X509_NAME_get_text_by_NID(certname, NID_commonName, NULL, 0); diff --git a/src/qt/rpcconsole.cpp b/src/qt/rpcconsole.cpp index fef15a32c6..4ba2f2615f 100644 --- a/src/qt/rpcconsole.cpp +++ b/src/qt/rpcconsole.cpp @@ -650,13 +650,18 @@ void RPCConsole::clear(bool clearHistory) "td.message { font-family: %1; font-size: %2; white-space:pre-wrap; } " "td.cmd-request { color: #006060; } " "td.cmd-error { color: red; } " + ".secwarning { color: red; }" "b { color: #006060; } " ).arg(fixedFontInfo.family(), QString("%1pt").arg(consoleFontSize)) ); message(CMD_REPLY, (tr("Welcome to the %1 RPC console.").arg(tr(PACKAGE_NAME)) + "<br>" + tr("Use up and down arrows to navigate history, and <b>Ctrl-L</b> to clear screen.") + "<br>" + - tr("Type <b>help</b> for an overview of available commands.")), true); + tr("Type <b>help</b> for an overview of available commands.")) + + "<br><span class=\"secwarning\">" + + tr("WARNING: Scammers have been active, telling users to type commands here, stealing their wallet contents. Do not use this console without fully understanding the ramification of a command.") + + "</span>", + true); } void RPCConsole::keyPressEvent(QKeyEvent *event) diff --git a/src/random.cpp b/src/random.cpp index aa027e49c4..c2605b45bd 100644 --- a/src/random.cpp +++ b/src/random.cpp @@ -11,7 +11,6 @@ #include "compat.h" // for Windows API #include <wincrypt.h> #endif -#include "serialize.h" // for begin_ptr(vec) #include "util.h" // for LogPrint() #include "utilstrencodings.h" // for GetTime() @@ -72,15 +71,15 @@ static void RandAddSeedPerfmon() const size_t nMaxSize = 10000000; // Bail out at more than 10MB of performance data while (true) { nSize = vData.size(); - ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", NULL, NULL, begin_ptr(vData), &nSize); + ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", NULL, NULL, vData.data(), &nSize); if (ret != ERROR_MORE_DATA || vData.size() >= nMaxSize) break; vData.resize(std::max((vData.size() * 3) / 2, nMaxSize)); // Grow size of buffer exponentially } RegCloseKey(HKEY_PERFORMANCE_DATA); if (ret == ERROR_SUCCESS) { - RAND_add(begin_ptr(vData), nSize, nSize / 100.0); - memory_cleanse(begin_ptr(vData), nSize); + RAND_add(vData.data(), nSize, nSize / 100.0); + memory_cleanse(vData.data(), nSize); LogPrint("rand", "%s: %lu bytes\n", __func__, nSize); } else { static bool warned = false; // Warn only once diff --git a/src/rpc/mining.cpp b/src/rpc/mining.cpp index cb22dec342..73797e2019 100644 --- a/src/rpc/mining.cpp +++ b/src/rpc/mining.cpp @@ -132,7 +132,7 @@ UniValue generateBlocks(boost::shared_ptr<CReserveScript> coinbaseScript, int nG continue; } std::shared_ptr<const CBlock> shared_pblock = std::make_shared<const CBlock>(*pblock); - if (!ProcessNewBlock(Params(), shared_pblock, true, NULL, NULL)) + if (!ProcessNewBlock(Params(), shared_pblock, true, NULL)) throw JSONRPCError(RPC_INTERNAL_ERROR, "ProcessNewBlock, block not accepted"); ++nHeight; blockHashes.push_back(pblock->GetHash().GetHex()); @@ -760,7 +760,7 @@ UniValue submitblock(const JSONRPCRequest& request) submitblock_StateCatcher sc(block.GetHash()); RegisterValidationInterface(&sc); - bool fAccepted = ProcessNewBlock(Params(), blockptr, true, NULL, NULL); + bool fAccepted = ProcessNewBlock(Params(), blockptr, true, NULL); UnregisterValidationInterface(&sc); if (fBlockPresent) { diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index a6403f9363..1410d0b73f 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -856,15 +856,15 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, un valtype& vch = stacktop(-1); valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32); if (opcode == OP_RIPEMD160) - CRIPEMD160().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash)); + CRIPEMD160().Write(vch.data(), vch.size()).Finalize(vchHash.data()); else if (opcode == OP_SHA1) - CSHA1().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash)); + CSHA1().Write(vch.data(), vch.size()).Finalize(vchHash.data()); else if (opcode == OP_SHA256) - CSHA256().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash)); + CSHA256().Write(vch.data(), vch.size()).Finalize(vchHash.data()); else if (opcode == OP_HASH160) - CHash160().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash)); + CHash160().Write(vch.data(), vch.size()).Finalize(vchHash.data()); else if (opcode == OP_HASH256) - CHash256().Write(begin_ptr(vch), vch.size()).Finalize(begin_ptr(vchHash)); + CHash256().Write(vch.data(), vch.size()).Finalize(vchHash.data()); popstack(stack); stack.push_back(vchHash); } diff --git a/src/script/sigcache.cpp b/src/script/sigcache.cpp index bdc0bfdc1c..b78d7b607f 100644 --- a/src/script/sigcache.cpp +++ b/src/script/sigcache.cpp @@ -11,20 +11,29 @@ #include "uint256.h" #include "util.h" +#include "cuckoocache.h" #include <boost/thread.hpp> -#include <boost/unordered_set.hpp> namespace { /** * We're hashing a nonce into the entries themselves, so we don't need extra * blinding in the set hash computation. + * + * This may exhibit platform endian dependent behavior but because these are + * nonced hashes (random) and this state is only ever used locally it is safe. + * All that matters is local consistency. */ -class CSignatureCacheHasher +class SignatureCacheHasher { public: - size_t operator()(const uint256& key) const { - return key.GetCheapHash(); + template <uint8_t hash_select> + uint32_t operator()(const uint256& key) const + { + static_assert(hash_select <8, "SignatureCacheHasher only has 8 hashes available."); + uint32_t u; + std::memcpy(&u, key.begin()+4*hash_select, 4); + return u; } }; @@ -38,11 +47,10 @@ class CSignatureCache private: //! Entries are SHA256(nonce || signature hash || public key || signature): uint256 nonce; - typedef boost::unordered_set<uint256, CSignatureCacheHasher> map_type; + typedef CuckooCache::cache<uint256, SignatureCacheHasher> map_type; map_type setValid; boost::shared_mutex cs_sigcache; - public: CSignatureCache() { @@ -56,58 +64,51 @@ public: } bool - Get(const uint256& entry) + Get(const uint256& entry, const bool erase) { boost::shared_lock<boost::shared_mutex> lock(cs_sigcache); - return setValid.count(entry); + return setValid.contains(entry, erase); } - void Erase(const uint256& entry) + void Set(uint256& entry) { boost::unique_lock<boost::shared_mutex> lock(cs_sigcache); - setValid.erase(entry); + setValid.insert(entry); } - - void Set(const uint256& entry) + uint32_t setup_bytes(size_t n) { - size_t nMaxCacheSize = GetArg("-maxsigcachesize", DEFAULT_MAX_SIG_CACHE_SIZE) * ((size_t) 1 << 20); - if (nMaxCacheSize <= 0) return; - - boost::unique_lock<boost::shared_mutex> lock(cs_sigcache); - while (memusage::DynamicUsage(setValid) > nMaxCacheSize) - { - map_type::size_type s = GetRand(setValid.bucket_count()); - map_type::local_iterator it = setValid.begin(s); - if (it != setValid.end(s)) { - setValid.erase(*it); - } - } - - setValid.insert(entry); + return setValid.setup_bytes(n); } }; +/* In previous versions of this code, signatureCache was a local static variable + * in CachingTransactionSignatureChecker::VerifySignature. We initialize + * signatureCache outside of VerifySignature to avoid the atomic operation per + * call overhead associated with local static variables even though + * signatureCache could be made local to VerifySignature. +*/ +static CSignatureCache signatureCache; } -bool CachingTransactionSignatureChecker::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const +// To be called once in AppInit2/TestingSetup to initialize the signatureCache +void InitSignatureCache() { - static CSignatureCache signatureCache; + size_t nMaxCacheSize = GetArg("-maxsigcachesize", DEFAULT_MAX_SIG_CACHE_SIZE) * ((size_t) 1 << 20); + if (nMaxCacheSize <= 0) return; + size_t nElems = signatureCache.setup_bytes(nMaxCacheSize); + LogPrintf("Using %zu MiB out of %zu requested for signature cache, able to store %zu elements\n", + (nElems*sizeof(uint256)) >>20, nMaxCacheSize>>20, nElems); +} +bool CachingTransactionSignatureChecker::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const +{ uint256 entry; signatureCache.ComputeEntry(entry, sighash, vchSig, pubkey); - - if (signatureCache.Get(entry)) { - if (!store) { - signatureCache.Erase(entry); - } + if (signatureCache.Get(entry, !store)) return true; - } - if (!TransactionSignatureChecker::VerifySignature(vchSig, pubkey, sighash)) return false; - - if (store) { + if (store) signatureCache.Set(entry); - } return true; } diff --git a/src/script/sigcache.h b/src/script/sigcache.h index 44551ec2bc..5243fc0a42 100644 --- a/src/script/sigcache.h +++ b/src/script/sigcache.h @@ -10,9 +10,10 @@ #include <vector> -// DoS prevention: limit cache size to less than 40MB (over 500000 -// entries on 64-bit systems). -static const unsigned int DEFAULT_MAX_SIG_CACHE_SIZE = 40; +// DoS prevention: limit cache size to 32MB (over 1000000 entries on 64-bit +// systems). Due to how we count cache size, actual memory usage is slightly +// more (~32.25 MB) +static const unsigned int DEFAULT_MAX_SIG_CACHE_SIZE = 32; class CPubKey; @@ -27,4 +28,6 @@ public: bool VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const; }; +void InitSignatureCache(); + #endif // BITCOIN_SCRIPT_SIGCACHE_H diff --git a/src/secp256k1/.gitignore b/src/secp256k1/.gitignore index efb277d347..87fea161ba 100644 --- a/src/secp256k1/.gitignore +++ b/src/secp256k1/.gitignore @@ -6,6 +6,7 @@ bench_schnorr_verify bench_recover bench_internal tests +exhaustive_tests gen_context *.exe *.so diff --git a/src/secp256k1/.travis.yml b/src/secp256k1/.travis.yml index 2c5c63adad..2439529242 100644 --- a/src/secp256k1/.travis.yml +++ b/src/secp256k1/.travis.yml @@ -11,7 +11,7 @@ cache: - src/java/guava/ env: global: - - FIELD=auto BIGNUM=auto SCALAR=auto ENDOMORPHISM=no STATICPRECOMPUTATION=yes ASM=no BUILD=check EXTRAFLAGS= HOST= ECDH=no schnorr=no RECOVERY=no EXPERIMENTAL=no + - FIELD=auto BIGNUM=auto SCALAR=auto ENDOMORPHISM=no STATICPRECOMPUTATION=yes ASM=no BUILD=check EXTRAFLAGS= HOST= ECDH=no RECOVERY=no EXPERIMENTAL=no - GUAVA_URL=https://search.maven.org/remotecontent?filepath=com/google/guava/guava/18.0/guava-18.0.jar GUAVA_JAR=src/java/guava/guava-18.0.jar matrix: - SCALAR=32bit RECOVERY=yes @@ -22,15 +22,14 @@ env: - FIELD=64bit ENDOMORPHISM=yes ECDH=yes EXPERIMENTAL=yes - FIELD=64bit ASM=x86_64 - FIELD=64bit ENDOMORPHISM=yes ASM=x86_64 - - FIELD=32bit SCHNORR=yes EXPERIMENTAL=yes - FIELD=32bit ENDOMORPHISM=yes - BIGNUM=no - - BIGNUM=no ENDOMORPHISM=yes SCHNORR=yes RECOVERY=yes EXPERIMENTAL=yes + - BIGNUM=no ENDOMORPHISM=yes RECOVERY=yes EXPERIMENTAL=yes - BIGNUM=no STATICPRECOMPUTATION=no - BUILD=distcheck - EXTRAFLAGS=CPPFLAGS=-DDETERMINISTIC - EXTRAFLAGS=CFLAGS=-O0 - - BUILD=check-java ECDH=yes SCHNORR=yes EXPERIMENTAL=yes + - BUILD=check-java ECDH=yes EXPERIMENTAL=yes matrix: fast_finish: true include: @@ -66,5 +65,5 @@ before_script: ./autogen.sh script: - if [ -n "$HOST" ]; then export USE_HOST="--host=$HOST"; fi - if [ "x$HOST" = "xi686-linux-gnu" ]; then export CC="$CC -m32"; fi - - ./configure --enable-experimental=$EXPERIMENTAL --enable-endomorphism=$ENDOMORPHISM --with-field=$FIELD --with-bignum=$BIGNUM --with-scalar=$SCALAR --enable-ecmult-static-precomputation=$STATICPRECOMPUTATION --enable-module-ecdh=$ECDH --enable-module-schnorr=$SCHNORR --enable-module-recovery=$RECOVERY $EXTRAFLAGS $USE_HOST && make -j2 $BUILD + - ./configure --enable-experimental=$EXPERIMENTAL --enable-endomorphism=$ENDOMORPHISM --with-field=$FIELD --with-bignum=$BIGNUM --with-scalar=$SCALAR --enable-ecmult-static-precomputation=$STATICPRECOMPUTATION --enable-module-ecdh=$ECDH --enable-module-recovery=$RECOVERY $EXTRAFLAGS $USE_HOST && make -j2 $BUILD os: linux diff --git a/src/secp256k1/Makefile.am b/src/secp256k1/Makefile.am index 3d130bdcbd..e5657f7f31 100644 --- a/src/secp256k1/Makefile.am +++ b/src/secp256k1/Makefile.am @@ -12,9 +12,11 @@ noinst_HEADERS = noinst_HEADERS += src/scalar.h noinst_HEADERS += src/scalar_4x64.h noinst_HEADERS += src/scalar_8x32.h +noinst_HEADERS += src/scalar_low.h noinst_HEADERS += src/scalar_impl.h noinst_HEADERS += src/scalar_4x64_impl.h noinst_HEADERS += src/scalar_8x32_impl.h +noinst_HEADERS += src/scalar_low_impl.h noinst_HEADERS += src/group.h noinst_HEADERS += src/group_impl.h noinst_HEADERS += src/num_gmp.h @@ -87,13 +89,23 @@ bench_internal_LDADD = $(SECP_LIBS) $(COMMON_LIB) bench_internal_CPPFLAGS = -DSECP256K1_BUILD $(SECP_INCLUDES) endif +TESTS = if USE_TESTS noinst_PROGRAMS += tests tests_SOURCES = src/tests.c tests_CPPFLAGS = -DSECP256K1_BUILD -DVERIFY -I$(top_srcdir)/src -I$(top_srcdir)/include $(SECP_INCLUDES) $(SECP_TEST_INCLUDES) tests_LDADD = $(SECP_LIBS) $(SECP_TEST_LIBS) $(COMMON_LIB) tests_LDFLAGS = -static -TESTS = tests +TESTS += tests +endif + +if USE_EXHAUSTIVE_TESTS +noinst_PROGRAMS += exhaustive_tests +exhaustive_tests_SOURCES = src/tests_exhaustive.c +exhaustive_tests_CPPFLAGS = -DSECP256K1_BUILD -DVERIFY -I$(top_srcdir)/src $(SECP_INCLUDES) +exhaustive_tests_LDADD = $(SECP_LIBS) +exhaustive_tests_LDFLAGS = -static +TESTS += exhaustive_tests endif JAVAROOT=src/java @@ -154,10 +166,6 @@ if ENABLE_MODULE_ECDH include src/modules/ecdh/Makefile.am.include endif -if ENABLE_MODULE_SCHNORR -include src/modules/schnorr/Makefile.am.include -endif - if ENABLE_MODULE_RECOVERY include src/modules/recovery/Makefile.am.include endif diff --git a/src/secp256k1/build-aux/m4/bitcoin_secp.m4 b/src/secp256k1/build-aux/m4/bitcoin_secp.m4 index b25d8adb92..b74acb8c13 100644 --- a/src/secp256k1/build-aux/m4/bitcoin_secp.m4 +++ b/src/secp256k1/build-aux/m4/bitcoin_secp.m4 @@ -46,6 +46,10 @@ if test x"$has_libcrypto" = x"yes" && test x"$has_openssl_ec" = x; then ECDSA_sign(0, NULL, 0, NULL, NULL, eckey); ECDSA_verify(0, NULL, 0, NULL, 0, eckey); EC_KEY_free(eckey); + ECDSA_SIG *sig_openssl; + sig_openssl = ECDSA_SIG_new(); + (void)sig_openssl->r; + ECDSA_SIG_free(sig_openssl); ]])],[has_openssl_ec=yes],[has_openssl_ec=no]) AC_MSG_RESULT([$has_openssl_ec]) fi diff --git a/src/secp256k1/configure.ac b/src/secp256k1/configure.ac index 0743c36690..ec50ffe3a2 100644 --- a/src/secp256k1/configure.ac +++ b/src/secp256k1/configure.ac @@ -104,6 +104,11 @@ AC_ARG_ENABLE(experimental, [use_experimental=$enableval], [use_experimental=no]) +AC_ARG_ENABLE(exhaustive_tests, + AS_HELP_STRING([--enable-exhaustive-tests],[compile exhaustive tests (default is yes)]), + [use_exhaustive_tests=$enableval], + [use_exhaustive_tests=yes]) + AC_ARG_ENABLE(endomorphism, AS_HELP_STRING([--enable-endomorphism],[enable endomorphism (default is no)]), [use_endomorphism=$enableval], @@ -119,11 +124,6 @@ AC_ARG_ENABLE(module_ecdh, [enable_module_ecdh=$enableval], [enable_module_ecdh=no]) -AC_ARG_ENABLE(module_schnorr, - AS_HELP_STRING([--enable-module-schnorr],[enable Schnorr signature module (experimental)]), - [enable_module_schnorr=$enableval], - [enable_module_schnorr=no]) - AC_ARG_ENABLE(module_recovery, AS_HELP_STRING([--enable-module-recovery],[enable ECDSA pubkey recovery module (default is no)]), [enable_module_recovery=$enableval], @@ -381,9 +381,6 @@ fi if test x"$use_jni" != x"no"; then AX_JNI_INCLUDE_DIR have_jni_dependencies=yes - if test x"$enable_module_schnorr" = x"no"; then - have_jni_dependencies=no - fi if test x"$enable_module_ecdh" = x"no"; then have_jni_dependencies=no fi @@ -392,7 +389,7 @@ if test x"$use_jni" != x"no"; then fi if test "x$have_jni_dependencies" = "xno"; then if test x"$use_jni" = x"yes"; then - AC_MSG_ERROR([jni support explicitly requested but headers/dependencies were not found. Enable ECDH and Schnorr and try again.]) + AC_MSG_ERROR([jni support explicitly requested but headers/dependencies were not found. Enable ECDH and try again.]) fi AC_MSG_WARN([jni headers/dependencies not found. jni support disabled]) use_jni=no @@ -413,7 +410,7 @@ if test x"$use_endomorphism" = x"yes"; then AC_DEFINE(USE_ENDOMORPHISM, 1, [Define this symbol to use endomorphism optimization]) fi -if test x"$use_ecmult_static_precomputation" = x"yes"; then +if test x"$set_precomp" = x"yes"; then AC_DEFINE(USE_ECMULT_STATIC_PRECOMPUTATION, 1, [Define this symbol to use a statically generated ecmult table]) fi @@ -421,10 +418,6 @@ if test x"$enable_module_ecdh" = x"yes"; then AC_DEFINE(ENABLE_MODULE_ECDH, 1, [Define this symbol to enable the ECDH module]) fi -if test x"$enable_module_schnorr" = x"yes"; then - AC_DEFINE(ENABLE_MODULE_SCHNORR, 1, [Define this symbol to enable the Schnorr signature module]) -fi - if test x"$enable_module_recovery" = x"yes"; then AC_DEFINE(ENABLE_MODULE_RECOVERY, 1, [Define this symbol to enable the ECDSA pubkey recovery module]) fi @@ -442,7 +435,6 @@ AC_MSG_NOTICE([Using bignum implementation: $set_bignum]) AC_MSG_NOTICE([Using scalar implementation: $set_scalar]) AC_MSG_NOTICE([Using endomorphism optimizations: $use_endomorphism]) AC_MSG_NOTICE([Building ECDH module: $enable_module_ecdh]) -AC_MSG_NOTICE([Building Schnorr signatures module: $enable_module_schnorr]) AC_MSG_NOTICE([Building ECDSA pubkey recovery module: $enable_module_recovery]) AC_MSG_NOTICE([Using jni: $use_jni]) @@ -451,12 +443,8 @@ if test x"$enable_experimental" = x"yes"; then AC_MSG_NOTICE([WARNING: experimental build]) AC_MSG_NOTICE([Experimental features do not have stable APIs or properties, and may not be safe for production use.]) AC_MSG_NOTICE([Building ECDH module: $enable_module_ecdh]) - AC_MSG_NOTICE([Building Schnorr signatures module: $enable_module_schnorr]) AC_MSG_NOTICE([******]) else - if test x"$enable_module_schnorr" = x"yes"; then - AC_MSG_ERROR([Schnorr signature module is experimental. Use --enable-experimental to allow.]) - fi if test x"$enable_module_ecdh" = x"yes"; then AC_MSG_ERROR([ECDH module is experimental. Use --enable-experimental to allow.]) fi @@ -473,10 +461,10 @@ AC_SUBST(SECP_LIBS) AC_SUBST(SECP_TEST_LIBS) AC_SUBST(SECP_TEST_INCLUDES) AM_CONDITIONAL([USE_TESTS], [test x"$use_tests" != x"no"]) +AM_CONDITIONAL([USE_EXHAUSTIVE_TESTS], [test x"$use_exhaustive_tests" != x"no"]) AM_CONDITIONAL([USE_BENCHMARK], [test x"$use_benchmark" = x"yes"]) -AM_CONDITIONAL([USE_ECMULT_STATIC_PRECOMPUTATION], [test x"$use_ecmult_static_precomputation" = x"yes"]) +AM_CONDITIONAL([USE_ECMULT_STATIC_PRECOMPUTATION], [test x"$set_precomp" = x"yes"]) AM_CONDITIONAL([ENABLE_MODULE_ECDH], [test x"$enable_module_ecdh" = x"yes"]) -AM_CONDITIONAL([ENABLE_MODULE_SCHNORR], [test x"$enable_module_schnorr" = x"yes"]) AM_CONDITIONAL([ENABLE_MODULE_RECOVERY], [test x"$enable_module_recovery" = x"yes"]) AM_CONDITIONAL([USE_JNI], [test x"$use_jni" == x"yes"]) AM_CONDITIONAL([USE_EXTERNAL_ASM], [test x"$use_external_asm" = x"yes"]) diff --git a/src/secp256k1/include/secp256k1.h b/src/secp256k1/include/secp256k1.h index 7145dbcc54..f268e309d0 100644 --- a/src/secp256k1/include/secp256k1.h +++ b/src/secp256k1/include/secp256k1.h @@ -47,11 +47,8 @@ typedef struct secp256k1_context_struct secp256k1_context; * 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. - * If you need to convert to a format suitable for storage or transmission, use - * secp256k1_ec_pubkey_serialize and secp256k1_ec_pubkey_parse. - * - * Furthermore, it is guaranteed that identical public keys (ignoring - * compression) will have identical representation, so they can be memcmp'ed. + * If you need to convert to a format suitable for storage, transmission, or + * comparison, use secp256k1_ec_pubkey_serialize and secp256k1_ec_pubkey_parse. */ typedef struct { unsigned char data[64]; @@ -62,12 +59,9 @@ typedef struct { * 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. - * If you need to convert to a format suitable for storage or transmission, use - * the secp256k1_ecdsa_signature_serialize_* and + * If you need to convert to a format suitable for storage, transmission, or + * comparison, use the secp256k1_ecdsa_signature_serialize_* and * secp256k1_ecdsa_signature_serialize_* functions. - * - * Furthermore, it is guaranteed to identical signatures will have identical - * representation, so they can be memcmp'ed. */ typedef struct { unsigned char data[64]; diff --git a/src/secp256k1/include/secp256k1_schnorr.h b/src/secp256k1/include/secp256k1_schnorr.h deleted file mode 100644 index dc32fec1ea..0000000000 --- a/src/secp256k1/include/secp256k1_schnorr.h +++ /dev/null @@ -1,173 +0,0 @@ -#ifndef _SECP256K1_SCHNORR_ -# define _SECP256K1_SCHNORR_ - -# include "secp256k1.h" - -# ifdef __cplusplus -extern "C" { -# endif - -/** Create a signature using a custom EC-Schnorr-SHA256 construction. It - * produces non-malleable 64-byte signatures which support public key recovery - * batch validation, and multiparty signing. - * Returns: 1: signature created - * 0: the nonce generation function failed, or the private key was - * invalid. - * Args: ctx: pointer to a context object, initialized for signing - * (cannot be NULL) - * Out: sig64: pointer to a 64-byte array where the signature will be - * placed (cannot be NULL) - * In: msg32: the 32-byte message hash being signed (cannot be NULL) - * seckey: pointer to a 32-byte secret key (cannot be NULL) - * noncefp:pointer to a nonce generation function. If NULL, - * secp256k1_nonce_function_default is used - * ndata: pointer to arbitrary data used by the nonce generation - * function (can be NULL) - */ -SECP256K1_API int secp256k1_schnorr_sign( - const secp256k1_context* ctx, - unsigned char *sig64, - const unsigned char *msg32, - const unsigned char *seckey, - secp256k1_nonce_function noncefp, - const void *ndata -) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4); - -/** Verify a signature created by secp256k1_schnorr_sign. - * Returns: 1: correct signature - * 0: incorrect signature - * Args: ctx: a secp256k1 context object, initialized for verification. - * In: sig64: the 64-byte signature being verified (cannot be NULL) - * msg32: the 32-byte message hash being verified (cannot be NULL) - * pubkey: the public key to verify with (cannot be NULL) - */ -SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_schnorr_verify( - const secp256k1_context* ctx, - const unsigned char *sig64, - const unsigned char *msg32, - const secp256k1_pubkey *pubkey -) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4); - -/** Recover an EC public key from a Schnorr signature created using - * secp256k1_schnorr_sign. - * Returns: 1: public key successfully recovered (which guarantees a correct - * signature). - * 0: otherwise. - * Args: ctx: pointer to a context object, initialized for - * verification (cannot be NULL) - * Out: pubkey: pointer to a pubkey to set to the recovered public key - * (cannot be NULL). - * In: sig64: signature as 64 byte array (cannot be NULL) - * msg32: the 32-byte message hash assumed to be signed (cannot - * be NULL) - */ -SECP256K1_API int secp256k1_schnorr_recover( - const secp256k1_context* ctx, - secp256k1_pubkey *pubkey, - const unsigned char *sig64, - const unsigned char *msg32 -) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4); - -/** Generate a nonce pair deterministically for use with - * secp256k1_schnorr_partial_sign. - * Returns: 1: valid nonce pair was generated. - * 0: otherwise (nonce generation function failed) - * Args: ctx: pointer to a context object, initialized for signing - * (cannot be NULL) - * Out: pubnonce: public side of the nonce (cannot be NULL) - * privnonce32: private side of the nonce (32 byte) (cannot be NULL) - * In: msg32: the 32-byte message hash assumed to be signed (cannot - * be NULL) - * sec32: the 32-byte private key (cannot be NULL) - * noncefp: pointer to a nonce generation function. If NULL, - * secp256k1_nonce_function_default is used - * noncedata: pointer to arbitrary data used by the nonce generation - * function (can be NULL) - * - * Do not use the output as a private/public key pair for signing/validation. - */ -SECP256K1_API int secp256k1_schnorr_generate_nonce_pair( - const secp256k1_context* ctx, - secp256k1_pubkey *pubnonce, - unsigned char *privnonce32, - const unsigned char *msg32, - const unsigned char *sec32, - secp256k1_nonce_function noncefp, - const void* noncedata -) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3); - -/** Produce a partial Schnorr signature, which can be combined using - * secp256k1_schnorr_partial_combine, to end up with a full signature that is - * verifiable using secp256k1_schnorr_verify. - * Returns: 1: signature created successfully. - * 0: no valid signature exists with this combination of keys, nonces - * and message (chance around 1 in 2^128) - * -1: invalid private key, nonce, or public nonces. - * Args: ctx: pointer to context object, initialized for signing (cannot - * be NULL) - * Out: sig64: pointer to 64-byte array to put partial signature in - * In: msg32: pointer to 32-byte message to sign - * sec32: pointer to 32-byte private key - * pubnonce_others: pointer to pubkey containing the sum of the other's - * nonces (see secp256k1_ec_pubkey_combine) - * secnonce32: pointer to 32-byte array containing our nonce - * - * The intended procedure for creating a multiparty signature is: - * - Each signer S[i] with private key x[i] and public key Q[i] runs - * secp256k1_schnorr_generate_nonce_pair to produce a pair (k[i],R[i]) of - * private/public nonces. - * - All signers communicate their public nonces to each other (revealing your - * private nonce can lead to discovery of your private key, so it should be - * considered secret). - * - All signers combine all the public nonces they received (excluding their - * own) using secp256k1_ec_pubkey_combine to obtain an - * Rall[i] = sum(R[0..i-1,i+1..n]). - * - All signers produce a partial signature using - * secp256k1_schnorr_partial_sign, passing in their own private key x[i], - * their own private nonce k[i], and the sum of the others' public nonces - * Rall[i]. - * - All signers communicate their partial signatures to each other. - * - Someone combines all partial signatures using - * secp256k1_schnorr_partial_combine, to obtain a full signature. - * - The resulting signature is validatable using secp256k1_schnorr_verify, with - * public key equal to the result of secp256k1_ec_pubkey_combine of the - * signers' public keys (sum(Q[0..n])). - * - * Note that secp256k1_schnorr_partial_combine and secp256k1_ec_pubkey_combine - * function take their arguments in any order, and it is possible to - * pre-combine several inputs already with one call, and add more inputs later - * by calling the function again (they are commutative and associative). - */ -SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_schnorr_partial_sign( - const secp256k1_context* ctx, - unsigned char *sig64, - const unsigned char *msg32, - const unsigned char *sec32, - const secp256k1_pubkey *pubnonce_others, - const unsigned char *secnonce32 -) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5) SECP256K1_ARG_NONNULL(6); - -/** Combine multiple Schnorr partial signatures. - * Returns: 1: the passed signatures were successfully combined. - * 0: the resulting signature is not valid (chance of 1 in 2^256) - * -1: some inputs were invalid, or the signatures were not created - * using the same set of nonces - * Args: ctx: pointer to a context object - * Out: sig64: pointer to a 64-byte array to place the combined signature - * (cannot be NULL) - * In: sig64sin: pointer to an array of n pointers to 64-byte input - * signatures - * n: the number of signatures to combine (at least 1) - */ -SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_schnorr_partial_combine( - const secp256k1_context* ctx, - unsigned char *sig64, - const unsigned char * const * sig64sin, - size_t n -) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3); - -# ifdef __cplusplus -} -# endif - -#endif diff --git a/src/secp256k1/src/ecdsa_impl.h b/src/secp256k1/src/ecdsa_impl.h index d110b4bb1d..9a42e519bd 100644 --- a/src/secp256k1/src/ecdsa_impl.h +++ b/src/secp256k1/src/ecdsa_impl.h @@ -203,7 +203,9 @@ static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const secp256k1_scalar *sigr, const secp256k1_scalar *sigs, const secp256k1_ge *pubkey, const secp256k1_scalar *message) { unsigned char c[32]; secp256k1_scalar sn, u1, u2; +#if !defined(EXHAUSTIVE_TEST_ORDER) secp256k1_fe xr; +#endif secp256k1_gej pubkeyj; secp256k1_gej pr; @@ -219,6 +221,21 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const if (secp256k1_gej_is_infinity(&pr)) { return 0; } + +#if defined(EXHAUSTIVE_TEST_ORDER) +{ + secp256k1_scalar computed_r; + int overflow = 0; + secp256k1_ge pr_ge; + secp256k1_ge_set_gej(&pr_ge, &pr); + secp256k1_fe_normalize(&pr_ge.x); + + secp256k1_fe_get_b32(c, &pr_ge.x); + secp256k1_scalar_set_b32(&computed_r, c, &overflow); + /* we fully expect overflow */ + return secp256k1_scalar_eq(sigr, &computed_r); +} +#else secp256k1_scalar_get_b32(c, sigr); secp256k1_fe_set_b32(&xr, c); @@ -252,6 +269,7 @@ static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const return 1; } return 0; +#endif } static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *seckey, const secp256k1_scalar *message, const secp256k1_scalar *nonce, int *recid) { diff --git a/src/secp256k1/src/ecmult_const_impl.h b/src/secp256k1/src/ecmult_const_impl.h index 7a6a25318c..0db314c48e 100644 --- a/src/secp256k1/src/ecmult_const_impl.h +++ b/src/secp256k1/src/ecmult_const_impl.h @@ -78,7 +78,7 @@ static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w) { /* Negative numbers will be negated to keep their bit representation below the maximum width */ flip = secp256k1_scalar_is_high(&s); /* We add 1 to even numbers, 2 to odd ones, noting that negation flips parity */ - bit = flip ^ (s.d[0] & 1); + bit = flip ^ !secp256k1_scalar_is_even(&s); /* We check for negative one, since adding 2 to it will cause an overflow */ secp256k1_scalar_negate(&neg_s, &s); not_neg_one = !secp256k1_scalar_is_one(&neg_s); diff --git a/src/secp256k1/src/ecmult_gen_impl.h b/src/secp256k1/src/ecmult_gen_impl.h index b63c4d8662..35f2546077 100644 --- a/src/secp256k1/src/ecmult_gen_impl.h +++ b/src/secp256k1/src/ecmult_gen_impl.h @@ -77,7 +77,7 @@ static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context *ctx secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej, NULL); } } - secp256k1_ge_set_all_gej_var(1024, prec, precj, cb); + secp256k1_ge_set_all_gej_var(prec, precj, 1024, cb); } for (j = 0; j < 64; j++) { for (i = 0; i < 16; i++) { diff --git a/src/secp256k1/src/ecmult_impl.h b/src/secp256k1/src/ecmult_impl.h index 81ae08e100..4e40104ad4 100644 --- a/src/secp256k1/src/ecmult_impl.h +++ b/src/secp256k1/src/ecmult_impl.h @@ -7,15 +7,29 @@ #ifndef _SECP256K1_ECMULT_IMPL_H_ #define _SECP256K1_ECMULT_IMPL_H_ +#include <string.h> + #include "group.h" #include "scalar.h" #include "ecmult.h" -#include <string.h> - +#if defined(EXHAUSTIVE_TEST_ORDER) +/* We need to lower these values for exhaustive tests because + * the tables cannot have infinities in them (this breaks the + * affine-isomorphism stuff which tracks z-ratios) */ +# if EXHAUSTIVE_TEST_ORDER > 128 +# define WINDOW_A 5 +# define WINDOW_G 8 +# elif EXHAUSTIVE_TEST_ORDER > 8 +# define WINDOW_A 4 +# define WINDOW_G 4 +# else +# define WINDOW_A 2 +# define WINDOW_G 2 +# endif +#else /* optimal for 128-bit and 256-bit exponents. */ #define WINDOW_A 5 - /** larger numbers may result in slightly better performance, at the cost of exponentially larger precomputed tables. */ #ifdef USE_ENDOMORPHISM @@ -25,6 +39,7 @@ /** One table for window size 16: 1.375 MiB. */ #define WINDOW_G 16 #endif +#endif /** The number of entries a table with precomputed multiples needs to have. */ #define ECMULT_TABLE_SIZE(w) (1 << ((w)-2)) @@ -103,7 +118,7 @@ static void secp256k1_ecmult_odd_multiples_table_storage_var(int n, secp256k1_ge /* Compute the odd multiples in Jacobian form. */ secp256k1_ecmult_odd_multiples_table(n, prej, zr, a); /* Convert them in batch to affine coordinates. */ - secp256k1_ge_set_table_gej_var(n, prea, prej, zr); + secp256k1_ge_set_table_gej_var(prea, prej, zr, n); /* Convert them to compact storage form. */ for (i = 0; i < n; i++) { secp256k1_ge_to_storage(&pre[i], &prea[i]); diff --git a/src/secp256k1/src/field.h b/src/secp256k1/src/field.h index c5ba074244..bbb1ee866c 100644 --- a/src/secp256k1/src/field.h +++ b/src/secp256k1/src/field.h @@ -30,6 +30,8 @@ #error "Please select field implementation" #endif +#include "util.h" + /** Normalize a field element. */ static void secp256k1_fe_normalize(secp256k1_fe *r); @@ -50,6 +52,9 @@ static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe *r); /** Set a field element equal to a small integer. Resulting field element is normalized. */ static void secp256k1_fe_set_int(secp256k1_fe *r, int a); +/** Sets a field element equal to zero, initializing all fields. */ +static void secp256k1_fe_clear(secp256k1_fe *a); + /** Verify whether a field element is zero. Requires the input to be normalized. */ static int secp256k1_fe_is_zero(const secp256k1_fe *a); @@ -110,7 +115,7 @@ static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a); /** Calculate the (modular) inverses of a batch of field elements. Requires the inputs' magnitudes to be * at most 8. The output magnitudes are 1 (but not guaranteed to be normalized). The inputs and * outputs must not overlap in memory. */ -static void secp256k1_fe_inv_all_var(size_t len, secp256k1_fe *r, const secp256k1_fe *a); +static void secp256k1_fe_inv_all_var(secp256k1_fe *r, const secp256k1_fe *a, size_t len); /** Convert a field element to the storage type. */ static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a); diff --git a/src/secp256k1/src/field_impl.h b/src/secp256k1/src/field_impl.h index 52cd902eb3..5127b279bc 100644 --- a/src/secp256k1/src/field_impl.h +++ b/src/secp256k1/src/field_impl.h @@ -260,7 +260,7 @@ static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a) { #endif } -static void secp256k1_fe_inv_all_var(size_t len, secp256k1_fe *r, const secp256k1_fe *a) { +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) { diff --git a/src/secp256k1/src/group.h b/src/secp256k1/src/group.h index d515716744..4957b248fe 100644 --- a/src/secp256k1/src/group.h +++ b/src/secp256k1/src/group.h @@ -65,12 +65,12 @@ static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a); static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a); /** Set a batch of group elements equal to the inputs given in jacobian coordinates */ -static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_callback *cb); +static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len, const secp256k1_callback *cb); /** Set a batch of group elements equal to the inputs given in jacobian * coordinates (with known z-ratios). zr must contain the known z-ratios such * that mul(a[i].z, zr[i+1]) == a[i+1].z. zr[0] is ignored. */ -static void secp256k1_ge_set_table_gej_var(size_t len, secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zr); +static void secp256k1_ge_set_table_gej_var(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zr, size_t len); /** Bring a batch inputs given in jacobian coordinates (with known z-ratios) to * the same global z "denominator". zr must contain the known z-ratios such diff --git a/src/secp256k1/src/group_impl.h b/src/secp256k1/src/group_impl.h index 3e9c4c410d..2e192b62fd 100644 --- a/src/secp256k1/src/group_impl.h +++ b/src/secp256k1/src/group_impl.h @@ -11,6 +11,53 @@ #include "field.h" #include "group.h" +/* These points can be generated in sage as follows: + * + * 0. Setup a worksheet with the following parameters. + * b = 4 # whatever CURVE_B will be set to + * F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F) + * C = EllipticCurve ([F (0), F (b)]) + * + * 1. Determine all the small orders available to you. (If there are + * no satisfactory ones, go back and change b.) + * print C.order().factor(limit=1000) + * + * 2. Choose an order as one of the prime factors listed in the above step. + * (You can also multiply some to get a composite order, though the + * tests will crash trying to invert scalars during signing.) We take a + * random point and scale it to drop its order to the desired value. + * There is some probability this won't work; just try again. + * order = 199 + * P = C.random_point() + * P = (int(P.order()) / int(order)) * P + * assert(P.order() == order) + * + * 3. Print the values. You'll need to use a vim macro or something to + * split the hex output into 4-byte chunks. + * print "%x %x" % P.xy() + */ +#if defined(EXHAUSTIVE_TEST_ORDER) +# if EXHAUSTIVE_TEST_ORDER == 199 +const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST( + 0xFA7CC9A7, 0x0737F2DB, 0xA749DD39, 0x2B4FB069, + 0x3B017A7D, 0xA808C2F1, 0xFB12940C, 0x9EA66C18, + 0x78AC123A, 0x5ED8AEF3, 0x8732BC91, 0x1F3A2868, + 0x48DF246C, 0x808DAE72, 0xCFE52572, 0x7F0501ED +); + +const int CURVE_B = 4; +# elif EXHAUSTIVE_TEST_ORDER == 13 +const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST( + 0xedc60018, 0xa51a786b, 0x2ea91f4d, 0x4c9416c0, + 0x9de54c3b, 0xa1316554, 0x6cf4345c, 0x7277ef15, + 0x54cb1b6b, 0xdc8c1273, 0x087844ea, 0x43f4603e, + 0x0eaf9a43, 0xf6effe55, 0x939f806d, 0x37adf8ac +); +const int CURVE_B = 2; +# else +# error No known generator for the specified exhaustive test group order. +# endif +#else /** Generator for secp256k1, value 'g' defined in * "Standards for Efficient Cryptography" (SEC2) 2.7.1. */ @@ -21,8 +68,11 @@ static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST( 0xFD17B448UL, 0xA6855419UL, 0x9C47D08FUL, 0xFB10D4B8UL ); +const int CURVE_B = 7; +#endif + static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) { - secp256k1_fe zi2; + secp256k1_fe zi2; secp256k1_fe zi3; secp256k1_fe_sqr(&zi2, zi); secp256k1_fe_mul(&zi3, &zi2, zi); @@ -76,7 +126,7 @@ static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a) { r->y = a->y; } -static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_callback *cb) { +static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len, const secp256k1_callback *cb) { secp256k1_fe *az; secp256k1_fe *azi; size_t i; @@ -89,7 +139,7 @@ static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge *r, const secp } azi = (secp256k1_fe *)checked_malloc(cb, sizeof(secp256k1_fe) * count); - secp256k1_fe_inv_all_var(count, azi, az); + secp256k1_fe_inv_all_var(azi, az, count); free(az); count = 0; @@ -102,7 +152,7 @@ static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge *r, const secp free(azi); } -static void secp256k1_ge_set_table_gej_var(size_t len, secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zr) { +static void secp256k1_ge_set_table_gej_var(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zr, size_t len) { size_t i = len - 1; secp256k1_fe zi; @@ -145,9 +195,15 @@ static void secp256k1_ge_globalz_set_table_gej(size_t len, secp256k1_ge *r, secp static void secp256k1_gej_set_infinity(secp256k1_gej *r) { r->infinity = 1; - secp256k1_fe_set_int(&r->x, 0); - secp256k1_fe_set_int(&r->y, 0); - secp256k1_fe_set_int(&r->z, 0); + secp256k1_fe_clear(&r->x); + secp256k1_fe_clear(&r->y); + secp256k1_fe_clear(&r->z); +} + +static void secp256k1_ge_set_infinity(secp256k1_ge *r) { + r->infinity = 1; + secp256k1_fe_clear(&r->x); + secp256k1_fe_clear(&r->y); } static void secp256k1_gej_clear(secp256k1_gej *r) { @@ -169,7 +225,7 @@ static int secp256k1_ge_set_xquad(secp256k1_ge *r, const secp256k1_fe *x) { secp256k1_fe_sqr(&x2, x); secp256k1_fe_mul(&x3, x, &x2); r->infinity = 0; - secp256k1_fe_set_int(&c, 7); + secp256k1_fe_set_int(&c, CURVE_B); secp256k1_fe_add(&c, &x3); return secp256k1_fe_sqrt(&r->y, &c); } @@ -228,7 +284,7 @@ static int secp256k1_gej_is_valid_var(const secp256k1_gej *a) { secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x); secp256k1_fe_sqr(&z2, &a->z); secp256k1_fe_sqr(&z6, &z2); secp256k1_fe_mul(&z6, &z6, &z2); - secp256k1_fe_mul_int(&z6, 7); + secp256k1_fe_mul_int(&z6, CURVE_B); secp256k1_fe_add(&x3, &z6); secp256k1_fe_normalize_weak(&x3); return secp256k1_fe_equal_var(&y2, &x3); @@ -242,7 +298,7 @@ static int secp256k1_ge_is_valid_var(const secp256k1_ge *a) { /* y^2 = x^3 + 7 */ secp256k1_fe_sqr(&y2, &a->y); secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x); - secp256k1_fe_set_int(&c, 7); + secp256k1_fe_set_int(&c, CURVE_B); secp256k1_fe_add(&x3, &c); secp256k1_fe_normalize_weak(&x3); return secp256k1_fe_equal_var(&y2, &x3); @@ -260,7 +316,7 @@ static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, s /** For secp256k1, 2Q is infinity if and only if Q is infinity. This is because if 2Q = infinity, * Q must equal -Q, or that Q.y == -(Q.y), or Q.y is 0. For a point on y^2 = x^3 + 7 to have * y=0, x^3 must be -7 mod p. However, -7 has no cube root mod p. - * + * * Having said this, if this function receives a point on a sextic twist, e.g. by * a fault attack, it is possible for y to be 0. This happens for y^2 = x^3 + 6, * since -6 does have a cube root mod p. For this point, this function will not set diff --git a/src/secp256k1/src/java/org/bitcoin/NativeSecp256k1.java b/src/secp256k1/src/java/org/bitcoin/NativeSecp256k1.java index be67048fbe..1c67802fba 100644 --- a/src/secp256k1/src/java/org/bitcoin/NativeSecp256k1.java +++ b/src/secp256k1/src/java/org/bitcoin/NativeSecp256k1.java @@ -32,7 +32,7 @@ import static org.bitcoin.NativeSecp256k1Util.*; * <p>You can find an example library that can be used for this at https://github.com/bitcoin/secp256k1</p> * * <p>To build secp256k1 for use with bitcoinj, run - * `./configure --enable-jni --enable-experimental --enable-module-schnorr --enable-module-ecdh` + * `./configure --enable-jni --enable-experimental --enable-module-ecdh` * and `make` then copy `.libs/libsecp256k1.so` to your system library path * or point the JVM to the folder containing it with -Djava.library.path * </p> @@ -417,36 +417,6 @@ public class NativeSecp256k1 { } } - public static byte[] schnorrSign(byte[] data, byte[] sec) throws AssertFailException { - Preconditions.checkArgument(data.length == 32 && sec.length <= 32); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null) { - byteBuff = ByteBuffer.allocateDirect(32 + 32); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(data); - byteBuff.put(sec); - - byte[][] retByteArray; - - r.lock(); - try { - retByteArray = secp256k1_schnorr_sign(byteBuff, Secp256k1Context.getContext()); - } finally { - r.unlock(); - } - - byte[] sigArr = retByteArray[0]; - int retVal = new BigInteger(new byte[] { retByteArray[1][0] }).intValue(); - - assertEquals(sigArr.length, 64, "Got bad signature length."); - - return retVal == 0 ? new byte[0] : sigArr; - } - private static native long secp256k1_ctx_clone(long context); private static native int secp256k1_context_randomize(ByteBuffer byteBuff, long context); @@ -471,8 +441,6 @@ public class NativeSecp256k1 { private static native byte[][] secp256k1_ec_pubkey_parse(ByteBuffer byteBuff, long context, int inputLen); - private static native byte[][] secp256k1_schnorr_sign(ByteBuffer byteBuff, long context); - private static native byte[][] secp256k1_ecdh(ByteBuffer byteBuff, long context, int inputLen); } diff --git a/src/secp256k1/src/java/org/bitcoin/NativeSecp256k1Test.java b/src/secp256k1/src/java/org/bitcoin/NativeSecp256k1Test.java index f18ce95810..c00d08899b 100644 --- a/src/secp256k1/src/java/org/bitcoin/NativeSecp256k1Test.java +++ b/src/secp256k1/src/java/org/bitcoin/NativeSecp256k1Test.java @@ -167,22 +167,6 @@ public class NativeSecp256k1Test { assertEquals( result, true, "testRandomize"); } - /** - * This tests signSchnorr() for a valid secretkey - */ - public static void testSchnorrSign() throws AssertFailException{ - - byte[] data = BaseEncoding.base16().lowerCase().decode("CF80CD8AED482D5D1527D7DC72FCEFF84E6326592848447D2DC0B0E87DFC9A90".toLowerCase()); //sha256hash of "testing" - byte[] sec = BaseEncoding.base16().lowerCase().decode("67E56582298859DDAE725F972992A07C6C4FB9F62A8FFF58CE3CA926A1063530".toLowerCase()); - - byte[] resultArr = NativeSecp256k1.schnorrSign(data, sec); - String sigString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( sigString, "C5E929AA058B982048760422D3B563749B7D0E50C5EBD8CD2FFC23214BD6A2F1B072C13880997EBA847CF20F2F90FCE07C1CA33A890A4127095A351127F8D95F" , "testSchnorrSign"); - } - - /** - * This tests signSchnorr() for a valid secretkey - */ public static void testCreateECDHSecret() throws AssertFailException{ byte[] sec = BaseEncoding.base16().lowerCase().decode("67E56582298859DDAE725F972992A07C6C4FB9F62A8FFF58CE3CA926A1063530".toLowerCase()); @@ -216,11 +200,6 @@ public class NativeSecp256k1Test { testSignPos(); testSignNeg(); - //Test Schnorr (partial support) //TODO - testSchnorrSign(); - //testSchnorrVerify - //testSchnorrRecovery - //Test privKeyTweakAdd() 1 testPrivKeyTweakAdd_1(); diff --git a/src/secp256k1/src/java/org_bitcoin_NativeSecp256k1.c b/src/secp256k1/src/java/org_bitcoin_NativeSecp256k1.c index dba9524dd4..bcef7b32ce 100644 --- a/src/secp256k1/src/java/org_bitcoin_NativeSecp256k1.c +++ b/src/secp256k1/src/java/org_bitcoin_NativeSecp256k1.c @@ -5,7 +5,6 @@ #include "include/secp256k1.h" #include "include/secp256k1_ecdh.h" #include "include/secp256k1_recovery.h" -#include "include/secp256k1_schnorr.h" SECP256K1_API jlong JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ctx_1clone @@ -333,39 +332,6 @@ SECP256K1_API jlong JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdsa_1p return 0; } -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1schnorr_1sign - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - unsigned char* data = (unsigned char*) (*env)->GetDirectBufferAddress(env, byteBufferObject); - unsigned char* secKey = (unsigned char*) (data + 32); - - jobjectArray retArray; - jbyteArray sigArray, intsByteArray; - unsigned char intsarray[1]; - unsigned char sig[64]; - - int ret = secp256k1_schnorr_sign(ctx, sig, data, secKey, NULL, NULL); - - intsarray[0] = ret; - - retArray = (*env)->NewObjectArray(env, 2, - (*env)->FindClass(env, "[B"), - (*env)->NewByteArray(env, 1)); - - sigArray = (*env)->NewByteArray(env, 64); - (*env)->SetByteArrayRegion(env, sigArray, 0, 64, (jbyte*)sig); - (*env)->SetObjectArrayElement(env, retArray, 0, sigArray); - - intsByteArray = (*env)->NewByteArray(env, 1); - (*env)->SetByteArrayRegion(env, intsByteArray, 0, 1, (jbyte*)intsarray); - (*env)->SetObjectArrayElement(env, retArray, 1, intsByteArray); - - (void)classObject; - - return retArray; -} - SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdh (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l, jint publen) { diff --git a/src/secp256k1/src/java/org_bitcoin_NativeSecp256k1.h b/src/secp256k1/src/java/org_bitcoin_NativeSecp256k1.h index 4125a1f523..fe613c9e9e 100644 --- a/src/secp256k1/src/java/org_bitcoin_NativeSecp256k1.h +++ b/src/secp256k1/src/java/org_bitcoin_NativeSecp256k1.h @@ -106,14 +106,6 @@ SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1e /* * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_schnorr_sign - * Signature: (Ljava/nio/ByteBuffer;JI)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1schnorr_1sign - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l); - -/* - * Class: org_bitcoin_NativeSecp256k1 * Method: secp256k1_ecdh * Signature: (Ljava/nio/ByteBuffer;JI)[[B */ diff --git a/src/secp256k1/src/modules/recovery/main_impl.h b/src/secp256k1/src/modules/recovery/main_impl.h index ec42f4bb6c..86f2f0cb2b 100644..100755 --- a/src/secp256k1/src/modules/recovery/main_impl.h +++ b/src/secp256k1/src/modules/recovery/main_impl.h @@ -138,16 +138,15 @@ int secp256k1_ecdsa_sign_recoverable(const secp256k1_context* ctx, secp256k1_ecd secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Fail if the secret key is invalid. */ if (!overflow && !secp256k1_scalar_is_zero(&sec)) { + unsigned char nonce32[32]; unsigned int count = 0; secp256k1_scalar_set_b32(&msg, msg32, NULL); while (1) { - unsigned char nonce32[32]; ret = noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count); if (!ret) { break; } secp256k1_scalar_set_b32(&non, nonce32, &overflow); - memset(nonce32, 0, 32); if (!secp256k1_scalar_is_zero(&non) && !overflow) { if (secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid)) { break; @@ -155,6 +154,7 @@ int secp256k1_ecdsa_sign_recoverable(const secp256k1_context* ctx, secp256k1_ecd } count++; } + memset(nonce32, 0, 32); secp256k1_scalar_clear(&msg); secp256k1_scalar_clear(&non); secp256k1_scalar_clear(&sec); diff --git a/src/secp256k1/src/modules/schnorr/Makefile.am.include b/src/secp256k1/src/modules/schnorr/Makefile.am.include deleted file mode 100644 index f1af8e8325..0000000000 --- a/src/secp256k1/src/modules/schnorr/Makefile.am.include +++ /dev/null @@ -1,10 +0,0 @@ -include_HEADERS += include/secp256k1_schnorr.h -noinst_HEADERS += src/modules/schnorr/main_impl.h -noinst_HEADERS += src/modules/schnorr/schnorr.h -noinst_HEADERS += src/modules/schnorr/schnorr_impl.h -noinst_HEADERS += src/modules/schnorr/tests_impl.h -if USE_BENCHMARK -noinst_PROGRAMS += bench_schnorr_verify -bench_schnorr_verify_SOURCES = src/bench_schnorr_verify.c -bench_schnorr_verify_LDADD = libsecp256k1.la $(SECP_LIBS) $(COMMON_LIB) -endif diff --git a/src/secp256k1/src/modules/schnorr/main_impl.h b/src/secp256k1/src/modules/schnorr/main_impl.h deleted file mode 100644 index fa176a1767..0000000000 --- a/src/secp256k1/src/modules/schnorr/main_impl.h +++ /dev/null @@ -1,164 +0,0 @@ -/********************************************************************** - * Copyright (c) 2014-2015 Pieter Wuille * - * Distributed under the MIT software license, see the accompanying * - * file COPYING or http://www.opensource.org/licenses/mit-license.php.* - **********************************************************************/ - -#ifndef SECP256K1_MODULE_SCHNORR_MAIN -#define SECP256K1_MODULE_SCHNORR_MAIN - -#include "include/secp256k1_schnorr.h" -#include "modules/schnorr/schnorr_impl.h" - -static void secp256k1_schnorr_msghash_sha256(unsigned char *h32, const unsigned char *r32, const unsigned char *msg32) { - secp256k1_sha256_t sha; - secp256k1_sha256_initialize(&sha); - secp256k1_sha256_write(&sha, r32, 32); - secp256k1_sha256_write(&sha, msg32, 32); - secp256k1_sha256_finalize(&sha, h32); -} - -static const unsigned char secp256k1_schnorr_algo16[17] = "Schnorr+SHA256 "; - -int secp256k1_schnorr_sign(const secp256k1_context* ctx, unsigned char *sig64, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) { - secp256k1_scalar sec, non; - int ret = 0; - int overflow = 0; - unsigned int count = 0; - VERIFY_CHECK(ctx != NULL); - ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); - ARG_CHECK(msg32 != NULL); - ARG_CHECK(sig64 != NULL); - ARG_CHECK(seckey != NULL); - if (noncefp == NULL) { - noncefp = secp256k1_nonce_function_default; - } - - secp256k1_scalar_set_b32(&sec, seckey, NULL); - while (1) { - unsigned char nonce32[32]; - ret = noncefp(nonce32, msg32, seckey, secp256k1_schnorr_algo16, (void*)noncedata, count); - if (!ret) { - break; - } - secp256k1_scalar_set_b32(&non, nonce32, &overflow); - memset(nonce32, 0, 32); - if (!secp256k1_scalar_is_zero(&non) && !overflow) { - if (secp256k1_schnorr_sig_sign(&ctx->ecmult_gen_ctx, sig64, &sec, &non, NULL, secp256k1_schnorr_msghash_sha256, msg32)) { - break; - } - } - count++; - } - if (!ret) { - memset(sig64, 0, 64); - } - secp256k1_scalar_clear(&non); - secp256k1_scalar_clear(&sec); - return ret; -} - -int secp256k1_schnorr_verify(const secp256k1_context* ctx, const unsigned char *sig64, const unsigned char *msg32, const secp256k1_pubkey *pubkey) { - secp256k1_ge q; - VERIFY_CHECK(ctx != NULL); - ARG_CHECK(secp256k1_ecmult_context_is_built(&ctx->ecmult_ctx)); - ARG_CHECK(msg32 != NULL); - ARG_CHECK(sig64 != NULL); - ARG_CHECK(pubkey != NULL); - - secp256k1_pubkey_load(ctx, &q, pubkey); - return secp256k1_schnorr_sig_verify(&ctx->ecmult_ctx, sig64, &q, secp256k1_schnorr_msghash_sha256, msg32); -} - -int secp256k1_schnorr_recover(const secp256k1_context* ctx, secp256k1_pubkey *pubkey, const unsigned char *sig64, const unsigned char *msg32) { - secp256k1_ge q; - - VERIFY_CHECK(ctx != NULL); - ARG_CHECK(secp256k1_ecmult_context_is_built(&ctx->ecmult_ctx)); - ARG_CHECK(msg32 != NULL); - ARG_CHECK(sig64 != NULL); - ARG_CHECK(pubkey != NULL); - - if (secp256k1_schnorr_sig_recover(&ctx->ecmult_ctx, sig64, &q, secp256k1_schnorr_msghash_sha256, msg32)) { - secp256k1_pubkey_save(pubkey, &q); - return 1; - } else { - memset(pubkey, 0, sizeof(*pubkey)); - return 0; - } -} - -int secp256k1_schnorr_generate_nonce_pair(const secp256k1_context* ctx, secp256k1_pubkey *pubnonce, unsigned char *privnonce32, const unsigned char *sec32, const unsigned char *msg32, secp256k1_nonce_function noncefp, const void* noncedata) { - int count = 0; - int ret = 1; - secp256k1_gej Qj; - secp256k1_ge Q; - secp256k1_scalar sec; - - VERIFY_CHECK(ctx != NULL); - ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); - ARG_CHECK(msg32 != NULL); - ARG_CHECK(sec32 != NULL); - ARG_CHECK(pubnonce != NULL); - ARG_CHECK(privnonce32 != NULL); - - if (noncefp == NULL) { - noncefp = secp256k1_nonce_function_default; - } - - do { - int overflow; - ret = noncefp(privnonce32, sec32, msg32, secp256k1_schnorr_algo16, (void*)noncedata, count++); - if (!ret) { - break; - } - secp256k1_scalar_set_b32(&sec, privnonce32, &overflow); - if (overflow || secp256k1_scalar_is_zero(&sec)) { - continue; - } - secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Qj, &sec); - secp256k1_ge_set_gej(&Q, &Qj); - - secp256k1_pubkey_save(pubnonce, &Q); - break; - } while(1); - - secp256k1_scalar_clear(&sec); - if (!ret) { - memset(pubnonce, 0, sizeof(*pubnonce)); - } - return ret; -} - -int secp256k1_schnorr_partial_sign(const secp256k1_context* ctx, unsigned char *sig64, const unsigned char *msg32, const unsigned char *sec32, const secp256k1_pubkey *pubnonce_others, const unsigned char *secnonce32) { - int overflow = 0; - secp256k1_scalar sec, non; - secp256k1_ge pubnon; - VERIFY_CHECK(ctx != NULL); - ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); - ARG_CHECK(msg32 != NULL); - ARG_CHECK(sig64 != NULL); - ARG_CHECK(sec32 != NULL); - ARG_CHECK(secnonce32 != NULL); - ARG_CHECK(pubnonce_others != NULL); - - secp256k1_scalar_set_b32(&sec, sec32, &overflow); - if (overflow || secp256k1_scalar_is_zero(&sec)) { - return -1; - } - secp256k1_scalar_set_b32(&non, secnonce32, &overflow); - if (overflow || secp256k1_scalar_is_zero(&non)) { - return -1; - } - secp256k1_pubkey_load(ctx, &pubnon, pubnonce_others); - return secp256k1_schnorr_sig_sign(&ctx->ecmult_gen_ctx, sig64, &sec, &non, &pubnon, secp256k1_schnorr_msghash_sha256, msg32); -} - -int secp256k1_schnorr_partial_combine(const secp256k1_context* ctx, unsigned char *sig64, const unsigned char * const *sig64sin, size_t n) { - ARG_CHECK(sig64 != NULL); - ARG_CHECK(n >= 1); - ARG_CHECK(sig64sin != NULL); - return secp256k1_schnorr_sig_combine(sig64, n, sig64sin); -} - -#endif diff --git a/src/secp256k1/src/modules/schnorr/schnorr.h b/src/secp256k1/src/modules/schnorr/schnorr.h deleted file mode 100644 index de18147bd5..0000000000 --- a/src/secp256k1/src/modules/schnorr/schnorr.h +++ /dev/null @@ -1,20 +0,0 @@ -/*********************************************************************** - * Copyright (c) 2014-2015 Pieter Wuille * - * Distributed under the MIT software license, see the accompanying * - * file COPYING or http://www.opensource.org/licenses/mit-license.php. * - ***********************************************************************/ - -#ifndef _SECP256K1_MODULE_SCHNORR_H_ -#define _SECP256K1_MODULE_SCHNORR_H_ - -#include "scalar.h" -#include "group.h" - -typedef void (*secp256k1_schnorr_msghash)(unsigned char *h32, const unsigned char *r32, const unsigned char *msg32); - -static int secp256k1_schnorr_sig_sign(const secp256k1_ecmult_gen_context* ctx, unsigned char *sig64, const secp256k1_scalar *key, const secp256k1_scalar *nonce, const secp256k1_ge *pubnonce, secp256k1_schnorr_msghash hash, const unsigned char *msg32); -static int secp256k1_schnorr_sig_verify(const secp256k1_ecmult_context* ctx, const unsigned char *sig64, const secp256k1_ge *pubkey, secp256k1_schnorr_msghash hash, const unsigned char *msg32); -static int secp256k1_schnorr_sig_recover(const secp256k1_ecmult_context* ctx, const unsigned char *sig64, secp256k1_ge *pubkey, secp256k1_schnorr_msghash hash, const unsigned char *msg32); -static int secp256k1_schnorr_sig_combine(unsigned char *sig64, size_t n, const unsigned char * const *sig64ins); - -#endif diff --git a/src/secp256k1/src/modules/schnorr/schnorr_impl.h b/src/secp256k1/src/modules/schnorr/schnorr_impl.h deleted file mode 100644 index e13ab6db7c..0000000000 --- a/src/secp256k1/src/modules/schnorr/schnorr_impl.h +++ /dev/null @@ -1,207 +0,0 @@ -/*********************************************************************** - * Copyright (c) 2014-2015 Pieter Wuille * - * Distributed under the MIT software license, see the accompanying * - * file COPYING or http://www.opensource.org/licenses/mit-license.php. * - ***********************************************************************/ - -#ifndef _SECP256K1_SCHNORR_IMPL_H_ -#define _SECP256K1_SCHNORR_IMPL_H_ - -#include <string.h> - -#include "schnorr.h" -#include "num.h" -#include "field.h" -#include "group.h" -#include "ecmult.h" -#include "ecmult_gen.h" - -/** - * Custom Schnorr-based signature scheme. They support multiparty signing, public key - * recovery and batch validation. - * - * Rationale for verifying R's y coordinate: - * In order to support batch validation and public key recovery, the full R point must - * be known to verifiers, rather than just its x coordinate. In order to not risk - * being more strict in batch validation than normal validation, validators must be - * required to reject signatures with incorrect y coordinate. This is only possible - * by including a (relatively slow) field inverse, or a field square root. However, - * batch validation offers potentially much higher benefits than this cost. - * - * Rationale for having an implicit y coordinate oddness: - * If we commit to having the full R point known to verifiers, there are two mechanism. - * Either include its oddness in the signature, or give it an implicit fixed value. - * As the R y coordinate can be flipped by a simple negation of the nonce, we choose the - * latter, as it comes with nearly zero impact on signing or validation performance, and - * saves a byte in the signature. - * - * Signing: - * Inputs: 32-byte message m, 32-byte scalar key x (!=0), 32-byte scalar nonce k (!=0) - * - * Compute point R = k * G. Reject nonce if R's y coordinate is odd (or negate nonce). - * Compute 32-byte r, the serialization of R's x coordinate. - * Compute scalar h = Hash(r || m). Reject nonce if h == 0 or h >= order. - * Compute scalar s = k - h * x. - * The signature is (r, s). - * - * - * Verification: - * Inputs: 32-byte message m, public key point Q, signature: (32-byte r, scalar s) - * - * Signature is invalid if s >= order. - * Signature is invalid if r >= p. - * Compute scalar h = Hash(r || m). Signature is invalid if h == 0 or h >= order. - * Option 1 (faster for single verification): - * Compute point R = h * Q + s * G. Signature is invalid if R is infinity or R's y coordinate is odd. - * Signature is valid if the serialization of R's x coordinate equals r. - * Option 2 (allows batch validation and pubkey recovery): - * Decompress x coordinate r into point R, with odd y coordinate. Fail if R is not on the curve. - * Signature is valid if R + h * Q + s * G == 0. - */ - -static int secp256k1_schnorr_sig_sign(const secp256k1_ecmult_gen_context* ctx, unsigned char *sig64, const secp256k1_scalar *key, const secp256k1_scalar *nonce, const secp256k1_ge *pubnonce, secp256k1_schnorr_msghash hash, const unsigned char *msg32) { - secp256k1_gej Rj; - secp256k1_ge Ra; - unsigned char h32[32]; - secp256k1_scalar h, s; - int overflow; - secp256k1_scalar n; - - if (secp256k1_scalar_is_zero(key) || secp256k1_scalar_is_zero(nonce)) { - return 0; - } - n = *nonce; - - secp256k1_ecmult_gen(ctx, &Rj, &n); - if (pubnonce != NULL) { - secp256k1_gej_add_ge(&Rj, &Rj, pubnonce); - } - secp256k1_ge_set_gej(&Ra, &Rj); - secp256k1_fe_normalize(&Ra.y); - if (secp256k1_fe_is_odd(&Ra.y)) { - /* R's y coordinate is odd, which is not allowed (see rationale above). - Force it to be even by negating the nonce. Note that this even works - for multiparty signing, as the R point is known to all participants, - which can all decide to flip the sign in unison, resulting in the - overall R point to be negated too. */ - secp256k1_scalar_negate(&n, &n); - } - secp256k1_fe_normalize(&Ra.x); - secp256k1_fe_get_b32(sig64, &Ra.x); - hash(h32, sig64, msg32); - overflow = 0; - secp256k1_scalar_set_b32(&h, h32, &overflow); - if (overflow || secp256k1_scalar_is_zero(&h)) { - secp256k1_scalar_clear(&n); - return 0; - } - secp256k1_scalar_mul(&s, &h, key); - secp256k1_scalar_negate(&s, &s); - secp256k1_scalar_add(&s, &s, &n); - secp256k1_scalar_clear(&n); - secp256k1_scalar_get_b32(sig64 + 32, &s); - return 1; -} - -static int secp256k1_schnorr_sig_verify(const secp256k1_ecmult_context* ctx, const unsigned char *sig64, const secp256k1_ge *pubkey, secp256k1_schnorr_msghash hash, const unsigned char *msg32) { - secp256k1_gej Qj, Rj; - secp256k1_ge Ra; - secp256k1_fe Rx; - secp256k1_scalar h, s; - unsigned char hh[32]; - int overflow; - - if (secp256k1_ge_is_infinity(pubkey)) { - return 0; - } - hash(hh, sig64, msg32); - overflow = 0; - secp256k1_scalar_set_b32(&h, hh, &overflow); - if (overflow || secp256k1_scalar_is_zero(&h)) { - return 0; - } - overflow = 0; - secp256k1_scalar_set_b32(&s, sig64 + 32, &overflow); - if (overflow) { - return 0; - } - if (!secp256k1_fe_set_b32(&Rx, sig64)) { - return 0; - } - secp256k1_gej_set_ge(&Qj, pubkey); - secp256k1_ecmult(ctx, &Rj, &Qj, &h, &s); - if (secp256k1_gej_is_infinity(&Rj)) { - return 0; - } - secp256k1_ge_set_gej_var(&Ra, &Rj); - secp256k1_fe_normalize_var(&Ra.y); - if (secp256k1_fe_is_odd(&Ra.y)) { - return 0; - } - return secp256k1_fe_equal_var(&Rx, &Ra.x); -} - -static int secp256k1_schnorr_sig_recover(const secp256k1_ecmult_context* ctx, const unsigned char *sig64, secp256k1_ge *pubkey, secp256k1_schnorr_msghash hash, const unsigned char *msg32) { - secp256k1_gej Qj, Rj; - secp256k1_ge Ra; - secp256k1_fe Rx; - secp256k1_scalar h, s; - unsigned char hh[32]; - int overflow; - - hash(hh, sig64, msg32); - overflow = 0; - secp256k1_scalar_set_b32(&h, hh, &overflow); - if (overflow || secp256k1_scalar_is_zero(&h)) { - return 0; - } - overflow = 0; - secp256k1_scalar_set_b32(&s, sig64 + 32, &overflow); - if (overflow) { - return 0; - } - if (!secp256k1_fe_set_b32(&Rx, sig64)) { - return 0; - } - if (!secp256k1_ge_set_xo_var(&Ra, &Rx, 0)) { - return 0; - } - secp256k1_gej_set_ge(&Rj, &Ra); - secp256k1_scalar_inverse_var(&h, &h); - secp256k1_scalar_negate(&s, &s); - secp256k1_scalar_mul(&s, &s, &h); - secp256k1_ecmult(ctx, &Qj, &Rj, &h, &s); - if (secp256k1_gej_is_infinity(&Qj)) { - return 0; - } - secp256k1_ge_set_gej(pubkey, &Qj); - return 1; -} - -static int secp256k1_schnorr_sig_combine(unsigned char *sig64, size_t n, const unsigned char * const *sig64ins) { - secp256k1_scalar s = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); - size_t i; - for (i = 0; i < n; i++) { - secp256k1_scalar si; - int overflow; - secp256k1_scalar_set_b32(&si, sig64ins[i] + 32, &overflow); - if (overflow) { - return -1; - } - if (i) { - if (memcmp(sig64ins[i - 1], sig64ins[i], 32) != 0) { - return -1; - } - } - secp256k1_scalar_add(&s, &s, &si); - } - if (secp256k1_scalar_is_zero(&s)) { - return 0; - } - memcpy(sig64, sig64ins[0], 32); - secp256k1_scalar_get_b32(sig64 + 32, &s); - secp256k1_scalar_clear(&s); - return 1; -} - -#endif diff --git a/src/secp256k1/src/modules/schnorr/tests_impl.h b/src/secp256k1/src/modules/schnorr/tests_impl.h deleted file mode 100644 index 5bd14a03e3..0000000000 --- a/src/secp256k1/src/modules/schnorr/tests_impl.h +++ /dev/null @@ -1,175 +0,0 @@ -/********************************************************************** - * Copyright (c) 2014-2015 Pieter Wuille * - * Distributed under the MIT software license, see the accompanying * - * file COPYING or http://www.opensource.org/licenses/mit-license.php.* - **********************************************************************/ - -#ifndef SECP256K1_MODULE_SCHNORR_TESTS -#define SECP256K1_MODULE_SCHNORR_TESTS - -#include "include/secp256k1_schnorr.h" - -void test_schnorr_end_to_end(void) { - unsigned char privkey[32]; - unsigned char message[32]; - unsigned char schnorr_signature[64]; - secp256k1_pubkey pubkey, recpubkey; - - /* Generate a random key and message. */ - { - secp256k1_scalar key; - random_scalar_order_test(&key); - secp256k1_scalar_get_b32(privkey, &key); - secp256k1_rand256_test(message); - } - - /* Construct and verify corresponding public key. */ - CHECK(secp256k1_ec_seckey_verify(ctx, privkey) == 1); - CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, privkey) == 1); - - /* Schnorr sign. */ - CHECK(secp256k1_schnorr_sign(ctx, schnorr_signature, message, privkey, NULL, NULL) == 1); - CHECK(secp256k1_schnorr_verify(ctx, schnorr_signature, message, &pubkey) == 1); - CHECK(secp256k1_schnorr_recover(ctx, &recpubkey, schnorr_signature, message) == 1); - CHECK(memcmp(&pubkey, &recpubkey, sizeof(pubkey)) == 0); - /* Destroy signature and verify again. */ - schnorr_signature[secp256k1_rand_bits(6)] += 1 + secp256k1_rand_int(255); - CHECK(secp256k1_schnorr_verify(ctx, schnorr_signature, message, &pubkey) == 0); - CHECK(secp256k1_schnorr_recover(ctx, &recpubkey, schnorr_signature, message) != 1 || - memcmp(&pubkey, &recpubkey, sizeof(pubkey)) != 0); -} - -/** Horribly broken hash function. Do not use for anything but tests. */ -void test_schnorr_hash(unsigned char *h32, const unsigned char *r32, const unsigned char *msg32) { - int i; - for (i = 0; i < 32; i++) { - h32[i] = r32[i] ^ msg32[i]; - } -} - -void test_schnorr_sign_verify(void) { - unsigned char msg32[32]; - unsigned char sig64[3][64]; - secp256k1_gej pubkeyj[3]; - secp256k1_ge pubkey[3]; - secp256k1_scalar nonce[3], key[3]; - int i = 0; - int k; - - secp256k1_rand256_test(msg32); - - for (k = 0; k < 3; k++) { - random_scalar_order_test(&key[k]); - - do { - random_scalar_order_test(&nonce[k]); - if (secp256k1_schnorr_sig_sign(&ctx->ecmult_gen_ctx, sig64[k], &key[k], &nonce[k], NULL, &test_schnorr_hash, msg32)) { - break; - } - } while(1); - - secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pubkeyj[k], &key[k]); - secp256k1_ge_set_gej_var(&pubkey[k], &pubkeyj[k]); - CHECK(secp256k1_schnorr_sig_verify(&ctx->ecmult_ctx, sig64[k], &pubkey[k], &test_schnorr_hash, msg32)); - - for (i = 0; i < 4; i++) { - int pos = secp256k1_rand_bits(6); - int mod = 1 + secp256k1_rand_int(255); - sig64[k][pos] ^= mod; - CHECK(secp256k1_schnorr_sig_verify(&ctx->ecmult_ctx, sig64[k], &pubkey[k], &test_schnorr_hash, msg32) == 0); - sig64[k][pos] ^= mod; - } - } -} - -void test_schnorr_threshold(void) { - unsigned char msg[32]; - unsigned char sec[5][32]; - secp256k1_pubkey pub[5]; - unsigned char nonce[5][32]; - secp256k1_pubkey pubnonce[5]; - unsigned char sig[5][64]; - const unsigned char* sigs[5]; - unsigned char allsig[64]; - const secp256k1_pubkey* pubs[5]; - secp256k1_pubkey allpub; - int n, i; - int damage; - int ret = 0; - - damage = secp256k1_rand_bits(1) ? (1 + secp256k1_rand_int(4)) : 0; - secp256k1_rand256_test(msg); - n = 2 + secp256k1_rand_int(4); - for (i = 0; i < n; i++) { - do { - secp256k1_rand256_test(sec[i]); - } while (!secp256k1_ec_seckey_verify(ctx, sec[i])); - CHECK(secp256k1_ec_pubkey_create(ctx, &pub[i], sec[i])); - CHECK(secp256k1_schnorr_generate_nonce_pair(ctx, &pubnonce[i], nonce[i], msg, sec[i], NULL, NULL)); - pubs[i] = &pub[i]; - } - if (damage == 1) { - nonce[secp256k1_rand_int(n)][secp256k1_rand_int(32)] ^= 1 + secp256k1_rand_int(255); - } else if (damage == 2) { - sec[secp256k1_rand_int(n)][secp256k1_rand_int(32)] ^= 1 + secp256k1_rand_int(255); - } - for (i = 0; i < n; i++) { - secp256k1_pubkey allpubnonce; - const secp256k1_pubkey *pubnonces[4]; - int j; - for (j = 0; j < i; j++) { - pubnonces[j] = &pubnonce[j]; - } - for (j = i + 1; j < n; j++) { - pubnonces[j - 1] = &pubnonce[j]; - } - CHECK(secp256k1_ec_pubkey_combine(ctx, &allpubnonce, pubnonces, n - 1)); - ret |= (secp256k1_schnorr_partial_sign(ctx, sig[i], msg, sec[i], &allpubnonce, nonce[i]) != 1) * 1; - sigs[i] = sig[i]; - } - if (damage == 3) { - sig[secp256k1_rand_int(n)][secp256k1_rand_bits(6)] ^= 1 + secp256k1_rand_int(255); - } - ret |= (secp256k1_ec_pubkey_combine(ctx, &allpub, pubs, n) != 1) * 2; - if ((ret & 1) == 0) { - ret |= (secp256k1_schnorr_partial_combine(ctx, allsig, sigs, n) != 1) * 4; - } - if (damage == 4) { - allsig[secp256k1_rand_int(32)] ^= 1 + secp256k1_rand_int(255); - } - if ((ret & 7) == 0) { - ret |= (secp256k1_schnorr_verify(ctx, allsig, msg, &allpub) != 1) * 8; - } - CHECK((ret == 0) == (damage == 0)); -} - -void test_schnorr_recovery(void) { - unsigned char msg32[32]; - unsigned char sig64[64]; - secp256k1_ge Q; - - secp256k1_rand256_test(msg32); - secp256k1_rand256_test(sig64); - secp256k1_rand256_test(sig64 + 32); - if (secp256k1_schnorr_sig_recover(&ctx->ecmult_ctx, sig64, &Q, &test_schnorr_hash, msg32) == 1) { - CHECK(secp256k1_schnorr_sig_verify(&ctx->ecmult_ctx, sig64, &Q, &test_schnorr_hash, msg32) == 1); - } -} - -void run_schnorr_tests(void) { - int i; - for (i = 0; i < 32*count; i++) { - test_schnorr_end_to_end(); - } - for (i = 0; i < 32 * count; i++) { - test_schnorr_sign_verify(); - } - for (i = 0; i < 16 * count; i++) { - test_schnorr_recovery(); - } - for (i = 0; i < 10 * count; i++) { - test_schnorr_threshold(); - } -} - -#endif diff --git a/src/secp256k1/src/scalar.h b/src/secp256k1/src/scalar.h index b590ccd6dd..27e9d8375e 100644 --- a/src/secp256k1/src/scalar.h +++ b/src/secp256k1/src/scalar.h @@ -13,7 +13,9 @@ #include "libsecp256k1-config.h" #endif -#if defined(USE_SCALAR_4X64) +#if defined(EXHAUSTIVE_TEST_ORDER) +#include "scalar_low.h" +#elif defined(USE_SCALAR_4X64) #include "scalar_4x64.h" #elif defined(USE_SCALAR_8X32) #include "scalar_8x32.h" diff --git a/src/secp256k1/src/scalar_4x64_impl.h b/src/secp256k1/src/scalar_4x64_impl.h index aa2703dd23..56e7bd82af 100644 --- a/src/secp256k1/src/scalar_4x64_impl.h +++ b/src/secp256k1/src/scalar_4x64_impl.h @@ -282,8 +282,8 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "movq 56(%%rsi), %%r14\n" /* Initialize r8,r9,r10 */ "movq 0(%%rsi), %%r8\n" - "movq $0, %%r9\n" - "movq $0, %%r10\n" + "xorq %%r9, %%r9\n" + "xorq %%r10, %%r10\n" /* (r8,r9) += n0 * c0 */ "movq %8, %%rax\n" "mulq %%r11\n" @@ -291,7 +291,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "adcq %%rdx, %%r9\n" /* extract m0 */ "movq %%r8, %q0\n" - "movq $0, %%r8\n" + "xorq %%r8, %%r8\n" /* (r9,r10) += l1 */ "addq 8(%%rsi), %%r9\n" "adcq $0, %%r10\n" @@ -309,7 +309,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "adcq $0, %%r8\n" /* extract m1 */ "movq %%r9, %q1\n" - "movq $0, %%r9\n" + "xorq %%r9, %%r9\n" /* (r10,r8,r9) += l2 */ "addq 16(%%rsi), %%r10\n" "adcq $0, %%r8\n" @@ -332,7 +332,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "adcq $0, %%r9\n" /* extract m2 */ "movq %%r10, %q2\n" - "movq $0, %%r10\n" + "xorq %%r10, %%r10\n" /* (r8,r9,r10) += l3 */ "addq 24(%%rsi), %%r8\n" "adcq $0, %%r9\n" @@ -355,7 +355,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "adcq $0, %%r10\n" /* extract m3 */ "movq %%r8, %q3\n" - "movq $0, %%r8\n" + "xorq %%r8, %%r8\n" /* (r9,r10,r8) += n3 * c1 */ "movq %9, %%rax\n" "mulq %%r14\n" @@ -387,8 +387,8 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "movq %q11, %%r13\n" /* Initialize (r8,r9,r10) */ "movq %q5, %%r8\n" - "movq $0, %%r9\n" - "movq $0, %%r10\n" + "xorq %%r9, %%r9\n" + "xorq %%r10, %%r10\n" /* (r8,r9) += m4 * c0 */ "movq %12, %%rax\n" "mulq %%r11\n" @@ -396,7 +396,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "adcq %%rdx, %%r9\n" /* extract p0 */ "movq %%r8, %q0\n" - "movq $0, %%r8\n" + "xorq %%r8, %%r8\n" /* (r9,r10) += m1 */ "addq %q6, %%r9\n" "adcq $0, %%r10\n" @@ -414,7 +414,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "adcq $0, %%r8\n" /* extract p1 */ "movq %%r9, %q1\n" - "movq $0, %%r9\n" + "xorq %%r9, %%r9\n" /* (r10,r8,r9) += m2 */ "addq %q7, %%r10\n" "adcq $0, %%r8\n" @@ -472,7 +472,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "movq %%rax, 0(%q6)\n" /* Move to (r8,r9) */ "movq %%rdx, %%r8\n" - "movq $0, %%r9\n" + "xorq %%r9, %%r9\n" /* (r8,r9) += p1 */ "addq %q2, %%r8\n" "adcq $0, %%r9\n" @@ -483,7 +483,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "adcq %%rdx, %%r9\n" /* Extract r1 */ "movq %%r8, 8(%q6)\n" - "movq $0, %%r8\n" + "xorq %%r8, %%r8\n" /* (r9,r8) += p4 */ "addq %%r10, %%r9\n" "adcq $0, %%r8\n" @@ -492,7 +492,7 @@ static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) "adcq $0, %%r8\n" /* Extract r2 */ "movq %%r9, 16(%q6)\n" - "movq $0, %%r9\n" + "xorq %%r9, %%r9\n" /* (r8,r9) += p3 */ "addq %q4, %%r8\n" "adcq $0, %%r9\n" diff --git a/src/secp256k1/src/scalar_impl.h b/src/secp256k1/src/scalar_impl.h index c5baf4df41..f5b2376407 100644 --- a/src/secp256k1/src/scalar_impl.h +++ b/src/secp256k1/src/scalar_impl.h @@ -14,7 +14,9 @@ #include "libsecp256k1-config.h" #endif -#if defined(USE_SCALAR_4X64) +#if defined(EXHAUSTIVE_TEST_ORDER) +#include "scalar_low_impl.h" +#elif defined(USE_SCALAR_4X64) #include "scalar_4x64_impl.h" #elif defined(USE_SCALAR_8X32) #include "scalar_8x32_impl.h" @@ -31,17 +33,37 @@ static void secp256k1_scalar_get_num(secp256k1_num *r, const secp256k1_scalar *a /** secp256k1 curve order, see secp256k1_ecdsa_const_order_as_fe in ecdsa_impl.h */ static void secp256k1_scalar_order_get_num(secp256k1_num *r) { +#if defined(EXHAUSTIVE_TEST_ORDER) + static const unsigned char order[32] = { + 0,0,0,0,0,0,0,0, + 0,0,0,0,0,0,0,0, + 0,0,0,0,0,0,0,0, + 0,0,0,0,0,0,0,EXHAUSTIVE_TEST_ORDER + }; +#else static const unsigned char order[32] = { 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE, 0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B, 0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41 }; +#endif secp256k1_num_set_bin(r, order, 32); } #endif static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x) { +#if defined(EXHAUSTIVE_TEST_ORDER) + int i; + *r = 0; + for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) + if ((i * *x) % EXHAUSTIVE_TEST_ORDER == 1) + *r = i; + /* If this VERIFY_CHECK triggers we were given a noninvertible scalar (and thus + * have a composite group order; fix it in exhaustive_tests.c). */ + VERIFY_CHECK(*r != 0); +} +#else secp256k1_scalar *t; int i; /* First compute x ^ (2^N - 1) for some values of N. */ @@ -233,9 +255,9 @@ static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar } SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) { - /* d[0] is present and is the lowest word for all representations */ return !(a->d[0] & 1); } +#endif static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x) { #if defined(USE_SCALAR_INV_BUILTIN) @@ -259,6 +281,18 @@ static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_sc } #ifdef USE_ENDOMORPHISM +#if defined(EXHAUSTIVE_TEST_ORDER) +/** + * Find k1 and k2 given k, such that k1 + k2 * lambda == k mod n; unlike in the + * full case we don't bother making k1 and k2 be small, we just want them to be + * nontrivial to get full test coverage for the exhaustive tests. We therefore + * (arbitrarily) set k2 = k + 5 and k1 = k - k2 * lambda. + */ +static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) { + *r2 = (*a + 5) % EXHAUSTIVE_TEST_ORDER; + *r1 = (*a + (EXHAUSTIVE_TEST_ORDER - *r2) * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER; +} +#else /** * The Secp256k1 curve has an endomorphism, where lambda * (x, y) = (beta * x, y), where * lambda is {0x53,0x63,0xad,0x4c,0xc0,0x5c,0x30,0xe0,0xa5,0x26,0x1c,0x02,0x88,0x12,0x64,0x5a, @@ -331,5 +365,6 @@ static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar secp256k1_scalar_add(r1, r1, a); } #endif +#endif #endif diff --git a/src/secp256k1/src/scalar_low.h b/src/secp256k1/src/scalar_low.h new file mode 100644 index 0000000000..5574c44c7a --- /dev/null +++ b/src/secp256k1/src/scalar_low.h @@ -0,0 +1,15 @@ +/********************************************************************** + * Copyright (c) 2015 Andrew Poelstra * + * Distributed under the MIT software license, see the accompanying * + * file COPYING or http://www.opensource.org/licenses/mit-license.php.* + **********************************************************************/ + +#ifndef _SECP256K1_SCALAR_REPR_ +#define _SECP256K1_SCALAR_REPR_ + +#include <stdint.h> + +/** A scalar modulo the group order of the secp256k1 curve. */ +typedef uint32_t secp256k1_scalar; + +#endif diff --git a/src/secp256k1/src/scalar_low_impl.h b/src/secp256k1/src/scalar_low_impl.h new file mode 100644 index 0000000000..4f94441f49 --- /dev/null +++ b/src/secp256k1/src/scalar_low_impl.h @@ -0,0 +1,114 @@ +/********************************************************************** + * Copyright (c) 2015 Andrew Poelstra * + * Distributed under the MIT software license, see the accompanying * + * file COPYING or http://www.opensource.org/licenses/mit-license.php.* + **********************************************************************/ + +#ifndef _SECP256K1_SCALAR_REPR_IMPL_H_ +#define _SECP256K1_SCALAR_REPR_IMPL_H_ + +#include "scalar.h" + +#include <string.h> + +SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) { + return !(*a & 1); +} + +SECP256K1_INLINE static void secp256k1_scalar_clear(secp256k1_scalar *r) { *r = 0; } +SECP256K1_INLINE static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v) { *r = v; } + +SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count) { + if (offset < 32) + return ((*a >> offset) & ((((uint32_t)1) << count) - 1)); + else + return 0; +} + +SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) { + return secp256k1_scalar_get_bits(a, offset, count); +} + +SECP256K1_INLINE static int secp256k1_scalar_check_overflow(const secp256k1_scalar *a) { return *a >= EXHAUSTIVE_TEST_ORDER; } + +static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) { + *r = (*a + *b) % EXHAUSTIVE_TEST_ORDER; + return *r < *b; +} + +static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag) { + if (flag && bit < 32) + *r += (1 << bit); +#ifdef VERIFY + VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0); +#endif +} + +static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b32, int *overflow) { + const int base = 0x100 % EXHAUSTIVE_TEST_ORDER; + int i; + *r = 0; + for (i = 0; i < 32; i++) { + *r = ((*r * base) + b32[i]) % EXHAUSTIVE_TEST_ORDER; + } + /* just deny overflow, it basically always happens */ + if (overflow) *overflow = 0; +} + +static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a) { + memset(bin, 0, 32); + bin[28] = *a >> 24; bin[29] = *a >> 16; bin[30] = *a >> 8; bin[31] = *a; +} + +SECP256K1_INLINE static int secp256k1_scalar_is_zero(const secp256k1_scalar *a) { + return *a == 0; +} + +static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a) { + if (*a == 0) { + *r = 0; + } else { + *r = EXHAUSTIVE_TEST_ORDER - *a; + } +} + +SECP256K1_INLINE static int secp256k1_scalar_is_one(const secp256k1_scalar *a) { + return *a == 1; +} + +static int secp256k1_scalar_is_high(const secp256k1_scalar *a) { + return *a > EXHAUSTIVE_TEST_ORDER / 2; +} + +static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) { + if (flag) secp256k1_scalar_negate(r, r); + return flag ? -1 : 1; +} + +static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) { + *r = (*a * *b) % EXHAUSTIVE_TEST_ORDER; +} + +static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n) { + int ret; + VERIFY_CHECK(n > 0); + VERIFY_CHECK(n < 16); + ret = *r & ((1 << n) - 1); + *r >>= n; + return ret; +} + +static void secp256k1_scalar_sqr(secp256k1_scalar *r, const secp256k1_scalar *a) { + *r = (*a * *a) % EXHAUSTIVE_TEST_ORDER; +} + +static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) { + *r1 = *a; + *r2 = 0; +} + +SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b) { + return *a == *b; +} + +#endif diff --git a/src/secp256k1/src/secp256k1.c b/src/secp256k1/src/secp256k1.c index 7973d60c36..fb8b882faa 100644..100755 --- a/src/secp256k1/src/secp256k1.c +++ b/src/secp256k1/src/secp256k1.c @@ -359,16 +359,15 @@ int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Fail if the secret key is invalid. */ if (!overflow && !secp256k1_scalar_is_zero(&sec)) { + unsigned char nonce32[32]; unsigned int count = 0; secp256k1_scalar_set_b32(&msg, msg32, NULL); while (1) { - unsigned char nonce32[32]; ret = noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count); if (!ret) { break; } secp256k1_scalar_set_b32(&non, nonce32, &overflow); - memset(nonce32, 0, 32); if (!overflow && !secp256k1_scalar_is_zero(&non)) { if (secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, NULL)) { break; @@ -376,6 +375,7 @@ int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature } count++; } + memset(nonce32, 0, 32); secp256k1_scalar_clear(&msg); secp256k1_scalar_clear(&non); secp256k1_scalar_clear(&sec); diff --git a/src/secp256k1/src/tests.c b/src/secp256k1/src/tests.c index b32cb90813..9ae7d30281 100644 --- a/src/secp256k1/src/tests.c +++ b/src/secp256k1/src/tests.c @@ -520,7 +520,7 @@ void test_num_mod(void) { secp256k1_num order, n; /* check that 0 mod anything is 0 */ - random_scalar_order_test(&s); + random_scalar_order_test(&s); secp256k1_scalar_get_num(&order, &s); secp256k1_scalar_set_int(&s, 0); secp256k1_scalar_get_num(&n, &s); @@ -535,7 +535,7 @@ void test_num_mod(void) { CHECK(secp256k1_num_is_zero(&n)); /* check that increasing the number past 2^256 does not break this */ - random_scalar_order_test(&s); + random_scalar_order_test(&s); secp256k1_scalar_get_num(&n, &s); /* multiply by 2^8, which'll test this case with high probability */ for (i = 0; i < 8; ++i) { @@ -568,7 +568,7 @@ void test_num_jacobi(void) { /* we first need a scalar which is not a multiple of 5 */ do { secp256k1_num fiven; - random_scalar_order_test(&sqr); + random_scalar_order_test(&sqr); secp256k1_scalar_get_num(&fiven, &five); secp256k1_scalar_get_num(&n, &sqr); secp256k1_num_mod(&n, &fiven); @@ -587,7 +587,7 @@ void test_num_jacobi(void) { /** test with secp group order as order */ secp256k1_scalar_order_get_num(&order); - random_scalar_order_test(&sqr); + random_scalar_order_test(&sqr); secp256k1_scalar_sqr(&sqr, &sqr); /* test residue */ secp256k1_scalar_get_num(&n, &sqr); @@ -1733,18 +1733,18 @@ void run_field_inv_all_var(void) { secp256k1_fe x[16], xi[16], xii[16]; int i; /* Check it's safe to call for 0 elements */ - secp256k1_fe_inv_all_var(0, xi, x); + secp256k1_fe_inv_all_var(xi, x, 0); for (i = 0; i < count; i++) { size_t j; size_t len = secp256k1_rand_int(15) + 1; for (j = 0; j < len; j++) { random_fe_non_zero(&x[j]); } - secp256k1_fe_inv_all_var(len, xi, x); + secp256k1_fe_inv_all_var(xi, x, len); for (j = 0; j < len; j++) { CHECK(check_fe_inverse(&x[j], &xi[j])); } - secp256k1_fe_inv_all_var(len, xii, xi); + secp256k1_fe_inv_all_var(xii, xi, len); for (j = 0; j < len; j++) { CHECK(check_fe_equal(&x[j], &xii[j])); } @@ -1930,7 +1930,7 @@ void test_ge(void) { zs[i] = gej[i].z; } } - secp256k1_fe_inv_all_var(4 * runs + 1, zinv, zs); + secp256k1_fe_inv_all_var(zinv, zs, 4 * runs + 1); free(zs); } @@ -2050,8 +2050,8 @@ void test_ge(void) { secp256k1_fe_mul(&zr[i + 1], &zinv[i], &gej[i + 1].z); } } - secp256k1_ge_set_table_gej_var(4 * runs + 1, ge_set_table, gej, zr); - secp256k1_ge_set_all_gej_var(4 * runs + 1, ge_set_all, gej, &ctx->error_callback); + secp256k1_ge_set_table_gej_var(ge_set_table, gej, zr, 4 * runs + 1); + secp256k1_ge_set_all_gej_var(ge_set_all, gej, 4 * runs + 1, &ctx->error_callback); for (i = 0; i < 4 * runs + 1; i++) { secp256k1_fe s; random_fe_non_zero(&s); diff --git a/src/secp256k1/src/tests_exhaustive.c b/src/secp256k1/src/tests_exhaustive.c new file mode 100644 index 0000000000..bda6ee475c --- /dev/null +++ b/src/secp256k1/src/tests_exhaustive.c @@ -0,0 +1,329 @@ +/*********************************************************************** + * Copyright (c) 2016 Andrew Poelstra * + * Distributed under the MIT software license, see the accompanying * + * file COPYING or http://www.opensource.org/licenses/mit-license.php.* + **********************************************************************/ + +#if defined HAVE_CONFIG_H +#include "libsecp256k1-config.h" +#endif + +#include <stdio.h> +#include <stdlib.h> + +#include <time.h> + +#undef USE_ECMULT_STATIC_PRECOMPUTATION + +#ifndef EXHAUSTIVE_TEST_ORDER +/* see group_impl.h for allowable values */ +#define EXHAUSTIVE_TEST_ORDER 13 +#define EXHAUSTIVE_TEST_LAMBDA 9 /* cube root of 1 mod 13 */ +#endif + +#include "include/secp256k1.h" +#include "group.h" +#include "secp256k1.c" +#include "testrand_impl.h" + +/** stolen from tests.c */ +void ge_equals_ge(const secp256k1_ge *a, const secp256k1_ge *b) { + CHECK(a->infinity == b->infinity); + if (a->infinity) { + return; + } + CHECK(secp256k1_fe_equal_var(&a->x, &b->x)); + CHECK(secp256k1_fe_equal_var(&a->y, &b->y)); +} + +void ge_equals_gej(const secp256k1_ge *a, const secp256k1_gej *b) { + secp256k1_fe z2s; + secp256k1_fe u1, u2, s1, s2; + CHECK(a->infinity == b->infinity); + if (a->infinity) { + return; + } + /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */ + secp256k1_fe_sqr(&z2s, &b->z); + secp256k1_fe_mul(&u1, &a->x, &z2s); + u2 = b->x; secp256k1_fe_normalize_weak(&u2); + secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z); + s2 = b->y; secp256k1_fe_normalize_weak(&s2); + CHECK(secp256k1_fe_equal_var(&u1, &u2)); + CHECK(secp256k1_fe_equal_var(&s1, &s2)); +} + +void random_fe(secp256k1_fe *x) { + unsigned char bin[32]; + do { + secp256k1_rand256(bin); + if (secp256k1_fe_set_b32(x, bin)) { + return; + } + } while(1); +} +/** END stolen from tests.c */ + +int secp256k1_nonce_function_smallint(unsigned char *nonce32, const unsigned char *msg32, + const unsigned char *key32, const unsigned char *algo16, + void *data, unsigned int attempt) { + secp256k1_scalar s; + int *idata = data; + (void)msg32; + (void)key32; + (void)algo16; + /* Some nonces cannot be used because they'd cause s and/or r to be zero. + * The signing function has retry logic here that just re-calls the nonce + * function with an increased `attempt`. So if attempt > 0 this means we + * need to change the nonce to avoid an infinite loop. */ + if (attempt > 0) { + (*idata)++; + } + secp256k1_scalar_set_int(&s, *idata); + secp256k1_scalar_get_b32(nonce32, &s); + return 1; +} + +#ifdef USE_ENDOMORPHISM +void test_exhaustive_endomorphism(const secp256k1_ge *group, int order) { + int i; + for (i = 0; i < order; i++) { + secp256k1_ge res; + secp256k1_ge_mul_lambda(&res, &group[i]); + ge_equals_ge(&group[i * EXHAUSTIVE_TEST_LAMBDA % EXHAUSTIVE_TEST_ORDER], &res); + } +} +#endif + +void test_exhaustive_addition(const secp256k1_ge *group, const secp256k1_gej *groupj, int order) { + int i, j; + + /* Sanity-check (and check infinity functions) */ + CHECK(secp256k1_ge_is_infinity(&group[0])); + CHECK(secp256k1_gej_is_infinity(&groupj[0])); + for (i = 1; i < order; i++) { + CHECK(!secp256k1_ge_is_infinity(&group[i])); + CHECK(!secp256k1_gej_is_infinity(&groupj[i])); + } + + /* Check all addition formulae */ + for (j = 0; j < order; j++) { + secp256k1_fe fe_inv; + secp256k1_fe_inv(&fe_inv, &groupj[j].z); + for (i = 0; i < order; i++) { + secp256k1_ge zless_gej; + secp256k1_gej tmp; + /* add_var */ + secp256k1_gej_add_var(&tmp, &groupj[i], &groupj[j], NULL); + ge_equals_gej(&group[(i + j) % order], &tmp); + /* add_ge */ + if (j > 0) { + secp256k1_gej_add_ge(&tmp, &groupj[i], &group[j]); + ge_equals_gej(&group[(i + j) % order], &tmp); + } + /* add_ge_var */ + secp256k1_gej_add_ge_var(&tmp, &groupj[i], &group[j], NULL); + ge_equals_gej(&group[(i + j) % order], &tmp); + /* add_zinv_var */ + zless_gej.infinity = groupj[j].infinity; + zless_gej.x = groupj[j].x; + zless_gej.y = groupj[j].y; + secp256k1_gej_add_zinv_var(&tmp, &groupj[i], &zless_gej, &fe_inv); + ge_equals_gej(&group[(i + j) % order], &tmp); + } + } + + /* Check doubling */ + for (i = 0; i < order; i++) { + secp256k1_gej tmp; + if (i > 0) { + secp256k1_gej_double_nonzero(&tmp, &groupj[i], NULL); + ge_equals_gej(&group[(2 * i) % order], &tmp); + } + secp256k1_gej_double_var(&tmp, &groupj[i], NULL); + ge_equals_gej(&group[(2 * i) % order], &tmp); + } + + /* Check negation */ + for (i = 1; i < order; i++) { + secp256k1_ge tmp; + secp256k1_gej tmpj; + secp256k1_ge_neg(&tmp, &group[i]); + ge_equals_ge(&group[order - i], &tmp); + secp256k1_gej_neg(&tmpj, &groupj[i]); + ge_equals_gej(&group[order - i], &tmpj); + } +} + +void test_exhaustive_ecmult(const secp256k1_context *ctx, const secp256k1_ge *group, const secp256k1_gej *groupj, int order) { + int i, j, r_log; + for (r_log = 1; r_log < order; r_log++) { + for (j = 0; j < order; j++) { + for (i = 0; i < order; i++) { + secp256k1_gej tmp; + secp256k1_scalar na, ng; + secp256k1_scalar_set_int(&na, i); + secp256k1_scalar_set_int(&ng, j); + + secp256k1_ecmult(&ctx->ecmult_ctx, &tmp, &groupj[r_log], &na, &ng); + ge_equals_gej(&group[(i * r_log + j) % order], &tmp); + + if (i > 0) { + secp256k1_ecmult_const(&tmp, &group[i], &ng); + ge_equals_gej(&group[(i * j) % order], &tmp); + } + } + } + } +} + +void r_from_k(secp256k1_scalar *r, const secp256k1_ge *group, int k) { + secp256k1_fe x; + unsigned char x_bin[32]; + k %= EXHAUSTIVE_TEST_ORDER; + x = group[k].x; + secp256k1_fe_normalize(&x); + secp256k1_fe_get_b32(x_bin, &x); + secp256k1_scalar_set_b32(r, x_bin, NULL); +} + +void test_exhaustive_verify(const secp256k1_context *ctx, const secp256k1_ge *group, int order) { + int s, r, msg, key; + for (s = 1; s < order; s++) { + for (r = 1; r < order; r++) { + for (msg = 1; msg < order; msg++) { + for (key = 1; key < order; key++) { + secp256k1_ge nonconst_ge; + secp256k1_ecdsa_signature sig; + secp256k1_pubkey pk; + secp256k1_scalar sk_s, msg_s, r_s, s_s; + secp256k1_scalar s_times_k_s, msg_plus_r_times_sk_s; + int k, should_verify; + unsigned char msg32[32]; + + secp256k1_scalar_set_int(&s_s, s); + secp256k1_scalar_set_int(&r_s, r); + secp256k1_scalar_set_int(&msg_s, msg); + secp256k1_scalar_set_int(&sk_s, key); + + /* Verify by hand */ + /* Run through every k value that gives us this r and check that *one* works. + * Note there could be none, there could be multiple, ECDSA is weird. */ + should_verify = 0; + for (k = 0; k < order; k++) { + secp256k1_scalar check_x_s; + r_from_k(&check_x_s, group, k); + if (r_s == check_x_s) { + secp256k1_scalar_set_int(&s_times_k_s, k); + secp256k1_scalar_mul(&s_times_k_s, &s_times_k_s, &s_s); + secp256k1_scalar_mul(&msg_plus_r_times_sk_s, &r_s, &sk_s); + secp256k1_scalar_add(&msg_plus_r_times_sk_s, &msg_plus_r_times_sk_s, &msg_s); + should_verify |= secp256k1_scalar_eq(&s_times_k_s, &msg_plus_r_times_sk_s); + } + } + /* nb we have a "high s" rule */ + should_verify &= !secp256k1_scalar_is_high(&s_s); + + /* Verify by calling verify */ + secp256k1_ecdsa_signature_save(&sig, &r_s, &s_s); + memcpy(&nonconst_ge, &group[sk_s], sizeof(nonconst_ge)); + secp256k1_pubkey_save(&pk, &nonconst_ge); + secp256k1_scalar_get_b32(msg32, &msg_s); + CHECK(should_verify == + secp256k1_ecdsa_verify(ctx, &sig, msg32, &pk)); + } + } + } + } +} + +void test_exhaustive_sign(const secp256k1_context *ctx, const secp256k1_ge *group, int order) { + int i, j, k; + + /* Loop */ + for (i = 1; i < order; i++) { /* message */ + for (j = 1; j < order; j++) { /* key */ + for (k = 1; k < order; k++) { /* nonce */ + secp256k1_ecdsa_signature sig; + secp256k1_scalar sk, msg, r, s, expected_r; + unsigned char sk32[32], msg32[32]; + secp256k1_scalar_set_int(&msg, i); + secp256k1_scalar_set_int(&sk, j); + secp256k1_scalar_get_b32(sk32, &sk); + secp256k1_scalar_get_b32(msg32, &msg); + + secp256k1_ecdsa_sign(ctx, &sig, msg32, sk32, secp256k1_nonce_function_smallint, &k); + + secp256k1_ecdsa_signature_load(ctx, &r, &s, &sig); + /* Note that we compute expected_r *after* signing -- this is important + * because our nonce-computing function function might change k during + * signing. */ + r_from_k(&expected_r, group, k); + CHECK(r == expected_r); + CHECK((k * s) % order == (i + r * j) % order || + (k * (EXHAUSTIVE_TEST_ORDER - s)) % order == (i + r * j) % order); + } + } + } + + /* We would like to verify zero-knowledge here by counting how often every + * possible (s, r) tuple appears, but because the group order is larger + * than the field order, when coercing the x-values to scalar values, some + * appear more often than others, so we are actually not zero-knowledge. + * (This effect also appears in the real code, but the difference is on the + * order of 1/2^128th the field order, so the deviation is not useful to a + * computationally bounded attacker.) + */ +} + +int main(void) { + int i; + secp256k1_gej groupj[EXHAUSTIVE_TEST_ORDER]; + secp256k1_ge group[EXHAUSTIVE_TEST_ORDER]; + + /* Build context */ + secp256k1_context *ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); + + /* TODO set z = 1, then do num_tests runs with random z values */ + + /* Generate the entire group */ + secp256k1_gej_set_infinity(&groupj[0]); + secp256k1_ge_set_gej(&group[0], &groupj[0]); + for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) { + /* Set a different random z-value for each Jacobian point */ + secp256k1_fe z; + random_fe(&z); + + secp256k1_gej_add_ge(&groupj[i], &groupj[i - 1], &secp256k1_ge_const_g); + secp256k1_ge_set_gej(&group[i], &groupj[i]); + secp256k1_gej_rescale(&groupj[i], &z); + + /* Verify against ecmult_gen */ + { + secp256k1_scalar scalar_i; + secp256k1_gej generatedj; + secp256k1_ge generated; + + secp256k1_scalar_set_int(&scalar_i, i); + secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &generatedj, &scalar_i); + secp256k1_ge_set_gej(&generated, &generatedj); + + CHECK(group[i].infinity == 0); + CHECK(generated.infinity == 0); + CHECK(secp256k1_fe_equal_var(&generated.x, &group[i].x)); + CHECK(secp256k1_fe_equal_var(&generated.y, &group[i].y)); + } + } + + /* Run the tests */ +#ifdef USE_ENDOMORPHISM + test_exhaustive_endomorphism(group, EXHAUSTIVE_TEST_ORDER); +#endif + test_exhaustive_addition(group, groupj, EXHAUSTIVE_TEST_ORDER); + test_exhaustive_ecmult(ctx, group, groupj, EXHAUSTIVE_TEST_ORDER); + test_exhaustive_sign(ctx, group, EXHAUSTIVE_TEST_ORDER); + test_exhaustive_verify(ctx, group, EXHAUSTIVE_TEST_ORDER); + + return 0; +} + diff --git a/src/serialize.h b/src/serialize.h index e28ca548c0..2be6f005e3 100644 --- a/src/serialize.h +++ b/src/serialize.h @@ -59,34 +59,6 @@ inline T* NCONST_PTR(const T* val) return const_cast<T*>(val); } -/** - * Important: Do not use the following functions in new code, but use v.data() - * and v.data() + v.size() respectively directly. They were once introduced to - * have a compatible, safe way to get the begin and end pointer of a vector. - * However with C++11 the language has built-in functionality for this and it's - * more readable to just use that. - */ -template <typename V> -inline typename V::value_type* begin_ptr(V& v) -{ - return v.data(); -} -template <typename V> -inline const typename V::value_type* begin_ptr(const V& v) -{ - return v.data(); -} -template <typename V> -inline typename V::value_type* end_ptr(V& v) -{ - return v.data() + v.size(); -} -template <typename V> -inline const typename V::value_type* end_ptr(const V& v) -{ - return v.data() + v.size(); -} - /* * Lowest-level serialization and conversion. * @note Sizes of these types are verified in the tests @@ -390,14 +362,14 @@ public: template <class T, class TAl> explicit CFlatData(std::vector<T,TAl> &v) { - pbegin = (char*)begin_ptr(v); - pend = (char*)end_ptr(v); + pbegin = (char*)v.data(); + pend = (char*)(v.data() + v.size()); } template <unsigned int N, typename T, typename S, typename D> explicit CFlatData(prevector<N, T, S, D> &v) { - pbegin = (char*)begin_ptr(v); - pend = (char*)end_ptr(v); + pbegin = (char*)v.data(); + pend = (char*)(v.data() + v.size()); } char* begin() { return pbegin; } const char* begin() const { return pbegin; } diff --git a/src/test/base58_tests.cpp b/src/test/base58_tests.cpp index ac3ab4c83f..04a6506655 100644 --- a/src/test/base58_tests.cpp +++ b/src/test/base58_tests.cpp @@ -39,7 +39,7 @@ BOOST_AUTO_TEST_CASE(base58_EncodeBase58) std::vector<unsigned char> sourcedata = ParseHex(test[0].get_str()); std::string base58string = test[1].get_str(); BOOST_CHECK_MESSAGE( - EncodeBase58(begin_ptr(sourcedata), end_ptr(sourcedata)) == base58string, + EncodeBase58(sourcedata.data(), sourcedata.data() + sourcedata.size()) == base58string, strTest); } } diff --git a/src/test/cuckoocache_tests.cpp b/src/test/cuckoocache_tests.cpp new file mode 100644 index 0000000000..1bc50d5ea9 --- /dev/null +++ b/src/test/cuckoocache_tests.cpp @@ -0,0 +1,394 @@ +// Copyright (c) 2012-2016 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. +#include <boost/test/unit_test.hpp> +#include "cuckoocache.h" +#include "test/test_bitcoin.h" +#include "random.h" +#include <thread> +#include <boost/thread.hpp> + + +/** Test Suite for CuckooCache + * + * 1) All tests should have a deterministic result (using insecure rand + * with deterministic seeds) + * 2) Some test methods are templated to allow for easier testing + * against new versions / comparing + * 3) Results should be treated as a regression test, ie, did the behavior + * change significantly from what was expected. This can be OK, depending on + * the nature of the change, but requires updating the tests to reflect the new + * expected behavior. For example improving the hit rate may cause some tests + * using BOOST_CHECK_CLOSE to fail. + * + */ +FastRandomContext insecure_rand(true); + +BOOST_AUTO_TEST_SUITE(cuckoocache_tests); + + +/** insecure_GetRandHash fills in a uint256 from insecure_rand + */ +void insecure_GetRandHash(uint256& t) +{ + uint32_t* ptr = (uint32_t*)t.begin(); + for (uint8_t j = 0; j < 8; ++j) + *(ptr++) = insecure_rand.rand32(); +} + +/** Definition copied from /src/script/sigcache.cpp + */ +class uint256Hasher +{ +public: + template <uint8_t hash_select> + uint32_t operator()(const uint256& key) const + { + static_assert(hash_select <8, "SignatureCacheHasher only has 8 hashes available."); + uint32_t u; + std::memcpy(&u, key.begin() + 4 * hash_select, 4); + return u; + } +}; + + +/* Test that no values not inserted into the cache are read out of it. + * + * There are no repeats in the first 200000 insecure_GetRandHash calls + */ +BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes) +{ + insecure_rand = FastRandomContext(true); + CuckooCache::cache<uint256, uint256Hasher> cc{}; + cc.setup_bytes(32 << 20); + uint256 v; + for (int x = 0; x < 100000; ++x) { + insecure_GetRandHash(v); + cc.insert(v); + } + for (int x = 0; x < 100000; ++x) { + insecure_GetRandHash(v); + BOOST_CHECK(!cc.contains(v, false)); + } +}; + +/** This helper returns the hit rate when megabytes*load worth of entries are + * inserted into a megabytes sized cache + */ +template <typename Cache> +double test_cache(size_t megabytes, double load) +{ + insecure_rand = FastRandomContext(true); + std::vector<uint256> hashes; + Cache set{}; + size_t bytes = megabytes * (1 << 20); + set.setup_bytes(bytes); + uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); + hashes.resize(n_insert); + for (uint32_t i = 0; i < n_insert; ++i) { + uint32_t* ptr = (uint32_t*)hashes[i].begin(); + for (uint8_t j = 0; j < 8; ++j) + *(ptr++) = insecure_rand.rand32(); + } + /** We make a copy of the hashes because future optimizations of the + * cuckoocache may overwrite the inserted element, so the test is + * "future proofed". + */ + std::vector<uint256> hashes_insert_copy = hashes; + /** Do the insert */ + for (uint256& h : hashes_insert_copy) + set.insert(h); + /** Count the hits */ + uint32_t count = 0; + for (uint256& h : hashes) + count += set.contains(h, false); + double hit_rate = ((double)count) / ((double)n_insert); + return hit_rate; +} + +/** The normalized hit rate for a given load. + * + * The semantics are a little confusing, so please see the below + * explanation. + * + * Examples: + * + * 1) at load 0.5, we expect a perfect hit rate, so we multiply by + * 1.0 + * 2) at load 2.0, we expect to see half the entries, so a perfect hit rate + * would be 0.5. Therefore, if we see a hit rate of 0.4, 0.4*2.0 = 0.8 is the + * normalized hit rate. + * + * This is basically the right semantics, but has a bit of a glitch depending on + * how you measure around load 1.0 as after load 1.0 your normalized hit rate + * becomes effectively perfect, ignoring freshness. + */ +double normalize_hit_rate(double hits, double load) +{ + return hits * std::max(load, 1.0); +} + +/** Check the hit rate on loads ranging from 0.1 to 2.0 */ +BOOST_AUTO_TEST_CASE(cuckoocache_hit_rate_ok) +{ + /** Arbitrarily selected Hit Rate threshold that happens to work for this test + * as a lower bound on performance. + */ + double HitRateThresh = 0.98; + size_t megabytes = 32; + for (double load = 0.1; load < 2; load *= 2) { + double hits = test_cache<CuckooCache::cache<uint256, uint256Hasher>>(megabytes, load); + BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); + } +} + + +/** This helper checks that erased elements are preferentially inserted onto and + * that the hit rate of "fresher" keys is reasonable*/ +template <typename Cache> +void test_cache_erase(size_t megabytes) +{ + double load = 1; + insecure_rand = FastRandomContext(true); + std::vector<uint256> hashes; + Cache set{}; + size_t bytes = megabytes * (1 << 20); + set.setup_bytes(bytes); + uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); + hashes.resize(n_insert); + for (uint32_t i = 0; i < n_insert; ++i) { + uint32_t* ptr = (uint32_t*)hashes[i].begin(); + for (uint8_t j = 0; j < 8; ++j) + *(ptr++) = insecure_rand.rand32(); + } + /** We make a copy of the hashes because future optimizations of the + * cuckoocache may overwrite the inserted element, so the test is + * "future proofed". + */ + std::vector<uint256> hashes_insert_copy = hashes; + + /** Insert the first half */ + for (uint32_t i = 0; i < (n_insert / 2); ++i) + set.insert(hashes_insert_copy[i]); + /** Erase the first quarter */ + for (uint32_t i = 0; i < (n_insert / 4); ++i) + set.contains(hashes[i], true); + /** Insert the second half */ + for (uint32_t i = (n_insert / 2); i < n_insert; ++i) + set.insert(hashes_insert_copy[i]); + + /** elements that we marked erased but that are still there */ + size_t count_erased_but_contained = 0; + /** elements that we did not erase but are older */ + size_t count_stale = 0; + /** elements that were most recently inserted */ + size_t count_fresh = 0; + + for (uint32_t i = 0; i < (n_insert / 4); ++i) + count_erased_but_contained += set.contains(hashes[i], false); + for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i) + count_stale += set.contains(hashes[i], false); + for (uint32_t i = (n_insert / 2); i < n_insert; ++i) + count_fresh += set.contains(hashes[i], false); + + double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0); + double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0); + double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0); + + // Check that our hit_rate_fresh is perfect + BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0); + // Check that we have a more than 2x better hit rate on stale elements than + // erased elements. + BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained); +} + +BOOST_AUTO_TEST_CASE(cuckoocache_erase_ok) +{ + size_t megabytes = 32; + test_cache_erase<CuckooCache::cache<uint256, uint256Hasher>>(megabytes); +} + +template <typename Cache> +void test_cache_erase_parallel(size_t megabytes) +{ + double load = 1; + insecure_rand = FastRandomContext(true); + std::vector<uint256> hashes; + Cache set{}; + size_t bytes = megabytes * (1 << 20); + set.setup_bytes(bytes); + uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); + hashes.resize(n_insert); + for (uint32_t i = 0; i < n_insert; ++i) { + uint32_t* ptr = (uint32_t*)hashes[i].begin(); + for (uint8_t j = 0; j < 8; ++j) + *(ptr++) = insecure_rand.rand32(); + } + /** We make a copy of the hashes because future optimizations of the + * cuckoocache may overwrite the inserted element, so the test is + * "future proofed". + */ + std::vector<uint256> hashes_insert_copy = hashes; + boost::shared_mutex mtx; + + { + /** Grab lock to make sure we release inserts */ + boost::unique_lock<boost::shared_mutex> l(mtx); + /** Insert the first half */ + for (uint32_t i = 0; i < (n_insert / 2); ++i) + set.insert(hashes_insert_copy[i]); + } + + /** Spin up 3 threads to run contains with erase. + */ + std::vector<std::thread> threads; + /** Erase the first quarter */ + for (uint32_t x = 0; x < 3; ++x) + /** Each thread is emplaced with x copy-by-value + */ + threads.emplace_back([&, x] { + boost::shared_lock<boost::shared_mutex> l(mtx); + size_t ntodo = (n_insert/4)/3; + size_t start = ntodo*x; + size_t end = ntodo*(x+1); + for (uint32_t i = start; i < end; ++i) + set.contains(hashes[i], true); + }); + + /** Wait for all threads to finish + */ + for (std::thread& t : threads) + t.join(); + /** Grab lock to make sure we observe erases */ + boost::unique_lock<boost::shared_mutex> l(mtx); + /** Insert the second half */ + for (uint32_t i = (n_insert / 2); i < n_insert; ++i) + set.insert(hashes_insert_copy[i]); + + /** elements that we marked erased but that are still there */ + size_t count_erased_but_contained = 0; + /** elements that we did not erase but are older */ + size_t count_stale = 0; + /** elements that were most recently inserted */ + size_t count_fresh = 0; + + for (uint32_t i = 0; i < (n_insert / 4); ++i) + count_erased_but_contained += set.contains(hashes[i], false); + for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i) + count_stale += set.contains(hashes[i], false); + for (uint32_t i = (n_insert / 2); i < n_insert; ++i) + count_fresh += set.contains(hashes[i], false); + + double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0); + double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0); + double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0); + + // Check that our hit_rate_fresh is perfect + BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0); + // Check that we have a more than 2x better hit rate on stale elements than + // erased elements. + BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained); +} +BOOST_AUTO_TEST_CASE(cuckoocache_erase_parallel_ok) +{ + size_t megabytes = 32; + test_cache_erase_parallel<CuckooCache::cache<uint256, uint256Hasher>>(megabytes); +} + + +template <typename Cache> +void test_cache_generations() +{ + // This test checks that for a simulation of network activity, the fresh hit + // rate is never below 99%, and the number of times that it is worse than + // 99.9% are less than 1% of the time. + double min_hit_rate = 0.99; + double tight_hit_rate = 0.999; + double max_rate_less_than_tight_hit_rate = 0.01; + // A cache that meets this specification is therefore shown to have a hit + // rate of at least tight_hit_rate * (1 - max_rate_less_than_tight_hit_rate) + + // min_hit_rate*max_rate_less_than_tight_hit_rate = 0.999*99%+0.99*1% == 99.89% + // hit rate with low variance. + + // We use deterministic values, but this test has also passed on many + // iterations with non-deterministic values, so it isn't "overfit" to the + // specific entropy in FastRandomContext(true) and implementation of the + // cache. + insecure_rand = FastRandomContext(true); + + // block_activity models a chunk of network activity. n_insert elements are + // adde to the cache. The first and last n/4 are stored for removal later + // and the middle n/2 are not stored. This models a network which uses half + // the signatures of recently (since the last block) added transactions + // immediately and never uses the other half. + struct block_activity { + std::vector<uint256> reads; + block_activity(uint32_t n_insert, Cache& c) : reads() + { + std::vector<uint256> inserts; + inserts.resize(n_insert); + reads.reserve(n_insert / 2); + for (uint32_t i = 0; i < n_insert; ++i) { + uint32_t* ptr = (uint32_t*)inserts[i].begin(); + for (uint8_t j = 0; j < 8; ++j) + *(ptr++) = insecure_rand.rand32(); + } + for (uint32_t i = 0; i < n_insert / 4; ++i) + reads.push_back(inserts[i]); + for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i) + reads.push_back(inserts[i]); + for (auto h : inserts) + c.insert(h); + } + }; + + const uint32_t BLOCK_SIZE = 10000; + // We expect window size 60 to perform reasonably given that each epoch + // stores 45% of the cache size (~472k). + const uint32_t WINDOW_SIZE = 60; + const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2; + const double load = 10; + const size_t megabytes = 32; + const size_t bytes = megabytes * (1 << 20); + const uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); + + std::vector<block_activity> hashes; + Cache set{}; + set.setup_bytes(bytes); + hashes.reserve(n_insert / BLOCK_SIZE); + std::deque<block_activity> last_few; + uint32_t out_of_tight_tolerance = 0; + uint32_t total = n_insert / BLOCK_SIZE; + // we use the deque last_few to model a sliding window of blocks. at each + // step, each of the last WINDOW_SIZE block_activities checks the cache for + // POP_AMOUNT of the hashes that they inserted, and marks these erased. + for (uint32_t i = 0; i < total; ++i) { + if (last_few.size() == WINDOW_SIZE) + last_few.pop_front(); + last_few.emplace_back(BLOCK_SIZE, set); + uint32_t count = 0; + for (auto& act : last_few) + for (uint32_t k = 0; k < POP_AMOUNT; ++k) { + count += set.contains(act.reads.back(), true); + act.reads.pop_back(); + } + // We use last_few.size() rather than WINDOW_SIZE for the correct + // behavior on the first WINDOW_SIZE iterations where the deque is not + // full yet. + double hit = (double(count)) / (last_few.size() * POP_AMOUNT); + // Loose Check that hit rate is above min_hit_rate + BOOST_CHECK(hit > min_hit_rate); + // Tighter check, count number of times we are less than tight_hit_rate + // (and implicityly, greater than min_hit_rate) + out_of_tight_tolerance += hit < tight_hit_rate; + } + // Check that being out of tolerance happens less than + // max_rate_less_than_tight_hit_rate of the time + BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < max_rate_less_than_tight_hit_rate); +} +BOOST_AUTO_TEST_CASE(cuckoocache_generations) +{ + test_cache_generations<CuckooCache::cache<uint256, uint256Hasher>>(); +} + +BOOST_AUTO_TEST_SUITE_END(); diff --git a/src/test/data/bitcoin-util-test.json b/src/test/data/bitcoin-util-test.json index 98be75919b..ab1a1385a3 100644 --- a/src/test/data/bitcoin-util-test.json +++ b/src/test/data/bitcoin-util-test.json @@ -1,24 +1,24 @@ [ { "exec": "./bitcoin-tx", - "args": ["-create"], - "output_cmp": "blanktx.hex", - "description": "Creates a blank transaction" + "args": ["-create", "nversion=1"], + "output_cmp": "blanktxv1.hex", + "description": "Creates a blank v1 transaction" }, { "exec": "./bitcoin-tx", "args": ["-json","-create"], - "output_cmp": "blanktx.json", + "output_cmp": "blanktxv2.json", "description": "Creates a blank transaction (output in json)" }, { "exec": "./bitcoin-tx", "args": ["-"], - "input": "blanktx.hex", - "output_cmp": "blanktx.hex", + "input": "blanktxv2.hex", + "output_cmp": "blanktxv2.hex", "description": "Creates a blank transaction when nothing is piped into bitcoin-tx" }, { "exec": "./bitcoin-tx", "args": ["-json","-"], - "input": "blanktx.hex", - "output_cmp": "blanktx.json", + "input": "blanktxv2.hex", + "output_cmp": "blanktxv2.json", "description": "Creates a blank transaction when nothing is piped into bitcoin-tx (output in json)" }, { "exec": "./bitcoin-tx", @@ -103,37 +103,48 @@ "description": "Creates a new transaction with a single empty output script (output in json)" }, { "exec": "./bitcoin-tx", - "args": ["01000000000100000000000000000000000000"], + "args": ["02000000000100000000000000000000000000"], "output_cmp": "txcreate2.hex", "description": "Parses a transation with no inputs and a single output script" }, { "exec": "./bitcoin-tx", - "args": ["-json", "01000000000100000000000000000000000000"], + "args": ["-json", "02000000000100000000000000000000000000"], "output_cmp": "txcreate2.json", "description": "Parses a transation with no inputs and a single output script (output in json)" }, { "exec": "./bitcoin-tx", "args": - ["-create", + ["-create", "nversion=1", "in=4d49a71ec9da436f71ec4ee231d04f292a29cd316f598bb7068feccabdc59485:0", "set=privatekeys:[\"5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf\"]", "set=prevtxs:[{\"txid\":\"4d49a71ec9da436f71ec4ee231d04f292a29cd316f598bb7068feccabdc59485\",\"vout\":0,\"scriptPubKey\":\"76a91491b24bf9f5288532960ac687abb035127b1d28a588ac\"}]", "sign=ALL", "outaddr=0.001:193P6LtvS4nCnkDvM9uXn1gsSRqh4aDAz7"], - "output_cmp": "txcreatesign.hex", - "description": "Creates a new transaction with a single input and a single output, and then signs the transaction" + "output_cmp": "txcreatesignv1.hex", + "description": "Creates a new v1 transaction with a single input and a single output, and then signs the transaction" }, { "exec": "./bitcoin-tx", "args": ["-json", - "-create", + "-create", "nversion=1", "in=4d49a71ec9da436f71ec4ee231d04f292a29cd316f598bb7068feccabdc59485:0", "set=privatekeys:[\"5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf\"]", "set=prevtxs:[{\"txid\":\"4d49a71ec9da436f71ec4ee231d04f292a29cd316f598bb7068feccabdc59485\",\"vout\":0,\"scriptPubKey\":\"76a91491b24bf9f5288532960ac687abb035127b1d28a588ac\"}]", "sign=ALL", "outaddr=0.001:193P6LtvS4nCnkDvM9uXn1gsSRqh4aDAz7"], - "output_cmp": "txcreatesign.json", - "description": "Creates a new transaction with a single input and a single output, and then signs the transaction (output in json)" + "output_cmp": "txcreatesignv1.json", + "description": "Creates a new v1 transaction with a single input and a single output, and then signs the transaction (output in json)" + }, + { "exec": "./bitcoin-tx", + "args": + ["-create", + "in=4d49a71ec9da436f71ec4ee231d04f292a29cd316f598bb7068feccabdc59485:0", + "set=privatekeys:[\"5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf\"]", + "set=prevtxs:[{\"txid\":\"4d49a71ec9da436f71ec4ee231d04f292a29cd316f598bb7068feccabdc59485\",\"vout\":0,\"scriptPubKey\":\"76a91491b24bf9f5288532960ac687abb035127b1d28a588ac\"}]", + "sign=ALL", + "outaddr=0.001:193P6LtvS4nCnkDvM9uXn1gsSRqh4aDAz7"], + "output_cmp": "txcreatesignv2.hex", + "description": "Creates a new transaction with a single input and a single output, and then signs the transaction" }, { "exec": "./bitcoin-tx", "args": @@ -163,12 +174,12 @@ { "exec": "./bitcoin-tx", "args": ["-json", - "-create", + "-create", "nversion=1", "in=5897de6bd6027a475eadd57019d4e6872c396d0716c4875a5f1a6fcfdf385c1f:0", "outaddr=0.18:13tuJJDR2RgArmgfv6JScSdreahzgc4T6o", "outdata=4:54686973204f505f52455455524e207472616e73616374696f6e206f7574707574207761732063726561746564206279206d6f646966696564206372656174657261777472616e73616374696f6e2e"], "output_cmp": "txcreatedata1.json", - "description": "Creates a new transaction with one input, one address output and one data output (output in json)" + "description": "Creates a new v1 transaction with one input, one address output and one data output (output in json)" }, { "exec": "./bitcoin-tx", "args": diff --git a/src/test/data/blanktx.hex b/src/test/data/blanktxv1.hex index 36b6f00fb6..36b6f00fb6 100644 --- a/src/test/data/blanktx.hex +++ b/src/test/data/blanktxv1.hex diff --git a/src/test/data/blanktxv2.hex b/src/test/data/blanktxv2.hex new file mode 100644 index 0000000000..22d830eda1 --- /dev/null +++ b/src/test/data/blanktxv2.hex @@ -0,0 +1 @@ +02000000000000000000 diff --git a/src/test/data/blanktxv2.json b/src/test/data/blanktxv2.json new file mode 100644 index 0000000000..266919f445 --- /dev/null +++ b/src/test/data/blanktxv2.json @@ -0,0 +1,11 @@ +{ + "txid": "4ebd325a4b394cff8c57e8317ccf5a8d0e2bdf1b8526f8aad6c8e43d8240621a", + "hash": "4ebd325a4b394cff8c57e8317ccf5a8d0e2bdf1b8526f8aad6c8e43d8240621a", + "version": 2, + "locktime": 0, + "vin": [ + ], + "vout": [ + ], + "hex": "02000000000000000000" +} diff --git a/src/test/data/tx_valid.json b/src/test/data/tx_valid.json index 27acb2f16a..a3f47fcee2 100644 --- a/src/test/data/tx_valid.json +++ b/src/test/data/tx_valid.json @@ -478,7 +478,7 @@ ["1b2a9a426ba603ba357ce7773cb5805cb9c7c2b386d100d1fc9263513188e680", 0, "0x00 0x20 0xd9bbfbe56af7c4b7f960a70d7ea107156913d9e5a26b0a71429df5e097ca6537", 16777215]], "01000000000102e9b542c5176808107ff1df906f46bb1f2583b16112b95ee5380665ba7fcfc0010000000000ffffffff80e68831516392fcd100d186b3c2c7b95c80b53c77e77c35ba03a66b429a2a1b0000000000ffffffff0280969800000000001976a914de4b231626ef508c9a74a8517e6783c0546d6b2888ac80969800000000001976a9146648a8cd4531e1ec47f35916de8e259237294d1e88ac02483045022100f6a10b8604e6dc910194b79ccfc93e1bc0ec7c03453caaa8987f7d6c3413566002206216229ede9b4d6ec2d325be245c5b508ff0339bf1794078e20bfe0babc7ffe683270063ab68210392972e2eb617b2388771abe27235fd5ac44af8e61693261550447a4c3e39da98ac024730440220032521802a76ad7bf74d0e2c218b72cf0cbc867066e2e53db905ba37f130397e02207709e2188ed7f08f4c952d9d13986da504502b8c3be59617e043552f506c46ff83275163ab68210392972e2eb617b2388771abe27235fd5ac44af8e61693261550447a4c3e39da98ac00000000", "P2SH,WITNESS"], -["BIP143 example: Same as the previous example with input-output paris swapped"], +["BIP143 example: Same as the previous example with input-output pairs swapped"], [[["1b2a9a426ba603ba357ce7773cb5805cb9c7c2b386d100d1fc9263513188e680", 0, "0x00 0x20 0xd9bbfbe56af7c4b7f960a70d7ea107156913d9e5a26b0a71429df5e097ca6537", 16777215], ["01c0cf7fba650638e55eb91261b183251fbb466f90dff17f10086817c542b5e9", 0, "0x00 0x20 0xba468eea561b26301e4cf69fa34bde4ad60c81e70f059f045ca9a79931004a4d", 16777215]], "0100000000010280e68831516392fcd100d186b3c2c7b95c80b53c77e77c35ba03a66b429a2a1b0000000000ffffffffe9b542c5176808107ff1df906f46bb1f2583b16112b95ee5380665ba7fcfc0010000000000ffffffff0280969800000000001976a9146648a8cd4531e1ec47f35916de8e259237294d1e88ac80969800000000001976a914de4b231626ef508c9a74a8517e6783c0546d6b2888ac024730440220032521802a76ad7bf74d0e2c218b72cf0cbc867066e2e53db905ba37f130397e02207709e2188ed7f08f4c952d9d13986da504502b8c3be59617e043552f506c46ff83275163ab68210392972e2eb617b2388771abe27235fd5ac44af8e61693261550447a4c3e39da98ac02483045022100f6a10b8604e6dc910194b79ccfc93e1bc0ec7c03453caaa8987f7d6c3413566002206216229ede9b4d6ec2d325be245c5b508ff0339bf1794078e20bfe0babc7ffe683270063ab68210392972e2eb617b2388771abe27235fd5ac44af8e61693261550447a4c3e39da98ac00000000", "P2SH,WITNESS"], diff --git a/src/test/data/txcreate1.hex b/src/test/data/txcreate1.hex index e2981a51c9..9ec6ee3531 100644 --- a/src/test/data/txcreate1.hex +++ b/src/test/data/txcreate1.hex @@ -1 +1 @@ -01000000031f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff7cca453133921c50d5025878f7f738d1df891fd359763331935784cf6b9c82bf1200000000fffffffffccd319e04a996c96cfc0bf4c07539aa90bd0b1a700ef72fae535d6504f9a6220100000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0084d717000000001976a914f2d4db28cad6502226ee484ae24505c2885cb12d88ac00000000 +02000000031f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff7cca453133921c50d5025878f7f738d1df891fd359763331935784cf6b9c82bf1200000000fffffffffccd319e04a996c96cfc0bf4c07539aa90bd0b1a700ef72fae535d6504f9a6220100000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0084d717000000001976a914f2d4db28cad6502226ee484ae24505c2885cb12d88ac00000000 diff --git a/src/test/data/txcreate1.json b/src/test/data/txcreate1.json index 567e8026a3..f83e036f33 100644 --- a/src/test/data/txcreate1.json +++ b/src/test/data/txcreate1.json @@ -1,7 +1,7 @@ { - "txid": "f70f0d6c71416ed538e37549f430ab3665fee2437a42f10238c1bd490e782231", - "hash": "f70f0d6c71416ed538e37549f430ab3665fee2437a42f10238c1bd490e782231", - "version": 1, + "txid": "fe7d174f42dce0cffa7a527e9bc8368956057619ec817648f6138b98f2533e8f", + "hash": "fe7d174f42dce0cffa7a527e9bc8368956057619ec817648f6138b98f2533e8f", + "version": 2, "locktime": 0, "vin": [ { @@ -60,5 +60,5 @@ } } ], - "hex": "01000000031f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff7cca453133921c50d5025878f7f738d1df891fd359763331935784cf6b9c82bf1200000000fffffffffccd319e04a996c96cfc0bf4c07539aa90bd0b1a700ef72fae535d6504f9a6220100000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0084d717000000001976a914f2d4db28cad6502226ee484ae24505c2885cb12d88ac00000000" + "hex": "02000000031f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff7cca453133921c50d5025878f7f738d1df891fd359763331935784cf6b9c82bf1200000000fffffffffccd319e04a996c96cfc0bf4c07539aa90bd0b1a700ef72fae535d6504f9a6220100000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0084d717000000001976a914f2d4db28cad6502226ee484ae24505c2885cb12d88ac00000000" } diff --git a/src/test/data/txcreate2.hex b/src/test/data/txcreate2.hex index 5243c2d02e..38bb7b1046 100644 --- a/src/test/data/txcreate2.hex +++ b/src/test/data/txcreate2.hex @@ -1 +1 @@ -01000000000100000000000000000000000000 +02000000000100000000000000000000000000 diff --git a/src/test/data/txcreate2.json b/src/test/data/txcreate2.json index a70c1d302a..fb5e177db7 100644 --- a/src/test/data/txcreate2.json +++ b/src/test/data/txcreate2.json @@ -1,7 +1,7 @@ { - "txid": "cf90229625e9eb10f6be8156bf6aa5ec2eca19a42b1e05c11f3029b560a32e13", - "hash": "cf90229625e9eb10f6be8156bf6aa5ec2eca19a42b1e05c11f3029b560a32e13", - "version": 1, + "txid": "0481afb29931341d0d7861d8a2f6f26456fa042abf54a23e96440ed7946e0715", + "hash": "0481afb29931341d0d7861d8a2f6f26456fa042abf54a23e96440ed7946e0715", + "version": 2, "locktime": 0, "vin": [ ], @@ -16,5 +16,5 @@ } } ], - "hex": "01000000000100000000000000000000000000" + "hex": "02000000000100000000000000000000000000" } diff --git a/src/test/data/txcreatedata1.hex b/src/test/data/txcreatedata1.hex index eccc7604e6..cefd1a05a6 100644 --- a/src/test/data/txcreatedata1.hex +++ b/src/test/data/txcreatedata1.hex @@ -1 +1 @@ -01000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0084d71700000000526a4c4f54686973204f505f52455455524e207472616e73616374696f6e206f7574707574207761732063726561746564206279206d6f646966696564206372656174657261777472616e73616374696f6e2e00000000 +02000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0084d71700000000526a4c4f54686973204f505f52455455524e207472616e73616374696f6e206f7574707574207761732063726561746564206279206d6f646966696564206372656174657261777472616e73616374696f6e2e00000000 diff --git a/src/test/data/txcreatedata2.hex b/src/test/data/txcreatedata2.hex index 3c7644c297..d69cf58ba1 100644 --- a/src/test/data/txcreatedata2.hex +++ b/src/test/data/txcreatedata2.hex @@ -1 +1 @@ -01000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0000000000000000526a4c4f54686973204f505f52455455524e207472616e73616374696f6e206f7574707574207761732063726561746564206279206d6f646966696564206372656174657261777472616e73616374696f6e2e00000000 +02000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0000000000000000526a4c4f54686973204f505f52455455524e207472616e73616374696f6e206f7574707574207761732063726561746564206279206d6f646966696564206372656174657261777472616e73616374696f6e2e00000000 diff --git a/src/test/data/txcreatedata2.json b/src/test/data/txcreatedata2.json index 56dfe4a1b0..3c6da40f90 100644 --- a/src/test/data/txcreatedata2.json +++ b/src/test/data/txcreatedata2.json @@ -1,7 +1,7 @@ { - "txid": "4ed17118f5e932ba8c75c461787d171bc02a016d8557cb5bcf34cd416c27bb8b", - "hash": "4ed17118f5e932ba8c75c461787d171bc02a016d8557cb5bcf34cd416c27bb8b", - "version": 1, + "txid": "c14b007fa3a6c1e7765919c1d14c1cfc2b8642c3a5d3be4b1fa8c4ccfec98bb0", + "hash": "c14b007fa3a6c1e7765919c1d14c1cfc2b8642c3a5d3be4b1fa8c4ccfec98bb0", + "version": 2, "locktime": 0, "vin": [ { @@ -38,5 +38,5 @@ } } ], - "hex": "01000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0000000000000000526a4c4f54686973204f505f52455455524e207472616e73616374696f6e206f7574707574207761732063726561746564206279206d6f646966696564206372656174657261777472616e73616374696f6e2e00000000" + "hex": "02000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000ffffffff0280a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac0000000000000000526a4c4f54686973204f505f52455455524e207472616e73616374696f6e206f7574707574207761732063726561746564206279206d6f646966696564206372656174657261777472616e73616374696f6e2e00000000" } diff --git a/src/test/data/txcreatedata_seq0.hex b/src/test/data/txcreatedata_seq0.hex index db02b5e4a4..54b89d2381 100644 --- a/src/test/data/txcreatedata_seq0.hex +++ b/src/test/data/txcreatedata_seq0.hex @@ -1 +1 @@ -01000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000fdffffff0180a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac00000000 +02000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000fdffffff0180a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac00000000 diff --git a/src/test/data/txcreatedata_seq0.json b/src/test/data/txcreatedata_seq0.json index 9bc0ed4593..d272a4c447 100644 --- a/src/test/data/txcreatedata_seq0.json +++ b/src/test/data/txcreatedata_seq0.json @@ -1,7 +1,7 @@ { - "txid": "71603ccb1cd76d73d76eb6cfd5f0b9df6d65d90d76860ee52cb461c4be7032e8", - "hash": "71603ccb1cd76d73d76eb6cfd5f0b9df6d65d90d76860ee52cb461c4be7032e8", - "version": 1, + "txid": "8df6ed527472542dd5e137c242a7c5a9f337ac34f7b257ae4af886aeaebb51b0", + "hash": "8df6ed527472542dd5e137c242a7c5a9f337ac34f7b257ae4af886aeaebb51b0", + "version": 2, "locktime": 0, "vin": [ { @@ -29,5 +29,5 @@ } } ], - "hex": "01000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000fdffffff0180a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac00000000" + "hex": "02000000011f5c38dfcf6f1a5f5a87c416076d392c87e6d41970d5ad5e477a02d66bde97580000000000fdffffff0180a81201000000001976a9141fc11f39be1729bf973a7ab6a615ca4729d6457488ac00000000" } diff --git a/src/test/data/txcreatesign.hex b/src/test/data/txcreatesignv1.hex index a46fcc88cb..a46fcc88cb 100644 --- a/src/test/data/txcreatesign.hex +++ b/src/test/data/txcreatesignv1.hex diff --git a/src/test/data/txcreatesignv1.json b/src/test/data/txcreatesignv1.json new file mode 100644 index 0000000000..ff39e71b40 --- /dev/null +++ b/src/test/data/txcreatesignv1.json @@ -0,0 +1,33 @@ +{ + "txid": "977e7cd286cb72cd470d539ba6cb48400f8f387d97451d45cdb8819437a303af", + "hash": "977e7cd286cb72cd470d539ba6cb48400f8f387d97451d45cdb8819437a303af", + "version": 1, + "locktime": 0, + "vin": [ + { + "txid": "4d49a71ec9da436f71ec4ee231d04f292a29cd316f598bb7068feccabdc59485", + "vout": 0, + "scriptSig": { + "asm": "304502210096a75056c9e2cc62b7214777b3d2a592cfda7092520126d4ebfcd6d590c99bd8022051bb746359cf98c0603f3004477eac68701132380db8facba19c89dc5ab5c5e2[ALL] 0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", + "hex": "48304502210096a75056c9e2cc62b7214777b3d2a592cfda7092520126d4ebfcd6d590c99bd8022051bb746359cf98c0603f3004477eac68701132380db8facba19c89dc5ab5c5e201410479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8" + }, + "sequence": 4294967295 + } + ], + "vout": [ + { + "value": 0.001, + "n": 0, + "scriptPubKey": { + "asm": "OP_DUP OP_HASH160 5834479edbbe0539b31ffd3a8f8ebadc2165ed01 OP_EQUALVERIFY OP_CHECKSIG", + "hex": "76a9145834479edbbe0539b31ffd3a8f8ebadc2165ed0188ac", + "reqSigs": 1, + "type": "pubkeyhash", + "addresses": [ + "193P6LtvS4nCnkDvM9uXn1gsSRqh4aDAz7" + ] + } + } + ], + "hex": "01000000018594c5bdcaec8f06b78b596f31cd292a294fd031e24eec716f43dac91ea7494d000000008b48304502210096a75056c9e2cc62b7214777b3d2a592cfda7092520126d4ebfcd6d590c99bd8022051bb746359cf98c0603f3004477eac68701132380db8facba19c89dc5ab5c5e201410479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8ffffffff01a0860100000000001976a9145834479edbbe0539b31ffd3a8f8ebadc2165ed0188ac00000000" +} diff --git a/src/test/data/txcreatesignv2.hex b/src/test/data/txcreatesignv2.hex new file mode 100644 index 0000000000..ee425cd98c --- /dev/null +++ b/src/test/data/txcreatesignv2.hex @@ -0,0 +1 @@ +02000000018594c5bdcaec8f06b78b596f31cd292a294fd031e24eec716f43dac91ea7494d000000008a473044022079c7aa014177a2e973caf6df7c7b8f15399083b91eba370ea1e19c4caed9181e02205f8f8763505ce8e6cbdd2cd28fab3fd407a75003e7d0dc04e6bebb0a3c89e7cb01410479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8ffffffff01a0860100000000001976a9145834479edbbe0539b31ffd3a8f8ebadc2165ed0188ac00000000 diff --git a/src/test/hash_tests.cpp b/src/test/hash_tests.cpp index fa9624f13d..8be9c580c4 100644 --- a/src/test/hash_tests.cpp +++ b/src/test/hash_tests.cpp @@ -124,7 +124,11 @@ BOOST_AUTO_TEST_CASE(siphash) } CHashWriter ss(SER_DISK, CLIENT_VERSION); - ss << CTransaction(); + CMutableTransaction tx; + // Note these tests were originally written with tx.nVersion=1 + // and the test would be affected by default tx version bumps if not fixed. + tx.nVersion = 1; + ss << tx; BOOST_CHECK_EQUAL(SipHashUint256(1, 2, ss.GetHash()), 0x79751e980c2a0a35ULL); } diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp index bdd6eaf538..84871600b2 100644 --- a/src/test/mempool_tests.cpp +++ b/src/test/mempool_tests.cpp @@ -390,7 +390,12 @@ BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest) pool.addUnchecked(tx6.GetHash(), entry.Fee(0LL).FromTx(tx6)); BOOST_CHECK_EQUAL(pool.size(), 6); - sortedOrder.push_back(tx6.GetHash().ToString()); + // Ties are broken by hash + if (tx3.GetHash() < tx6.GetHash()) + sortedOrder.push_back(tx6.GetHash().ToString()); + else + sortedOrder.insert(sortedOrder.end()-1,tx6.GetHash().ToString()); + CheckSort<ancestor_score>(pool, sortedOrder); CMutableTransaction tx7 = CMutableTransaction(); @@ -417,7 +422,11 @@ BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest) pool.removeForBlock(vtx, 1); sortedOrder.erase(sortedOrder.begin()+1); - sortedOrder.pop_back(); + // Ties are broken by hash + if (tx3.GetHash() < tx6.GetHash()) + sortedOrder.pop_back(); + else + sortedOrder.erase(sortedOrder.end()-2); sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString()); CheckSort<ancestor_score>(pool, sortedOrder); } diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp index bc1bdd8874..892e731a7a 100644 --- a/src/test/miner_tests.cpp +++ b/src/test/miner_tests.cpp @@ -224,7 +224,7 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity) pblock->hashMerkleRoot = BlockMerkleRoot(*pblock); pblock->nNonce = blockinfo[i].nonce; std::shared_ptr<const CBlock> shared_pblock = std::make_shared<const CBlock>(*pblock); - BOOST_CHECK(ProcessNewBlock(chainparams, shared_pblock, true, NULL, NULL)); + BOOST_CHECK(ProcessNewBlock(chainparams, shared_pblock, true, NULL)); pblock->hashPrevBlock = pblock->GetHash(); } diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp index eb324d5a6b..d7f3a3a657 100644 --- a/src/test/script_tests.cpp +++ b/src/test/script_tests.cpp @@ -176,10 +176,10 @@ void DoTest(const CScript& scriptPubKey, const CScript& scriptSig, const CScript int libconsensus_flags = flags & bitcoinconsensus_SCRIPT_FLAGS_VERIFY_ALL; if (libconsensus_flags == flags) { if (flags & bitcoinconsensus_SCRIPT_FLAGS_VERIFY_WITNESS) { - BOOST_CHECK_MESSAGE(bitcoinconsensus_verify_script_with_amount(begin_ptr(scriptPubKey), scriptPubKey.size(), txCredit.vout[0].nValue, (const unsigned char*)&stream[0], stream.size(), 0, libconsensus_flags, NULL) == expect, message); + BOOST_CHECK_MESSAGE(bitcoinconsensus_verify_script_with_amount(scriptPubKey.data(), scriptPubKey.size(), txCredit.vout[0].nValue, (const unsigned char*)&stream[0], stream.size(), 0, libconsensus_flags, NULL) == expect, message); } else { - BOOST_CHECK_MESSAGE(bitcoinconsensus_verify_script_with_amount(begin_ptr(scriptPubKey), scriptPubKey.size(), 0, (const unsigned char*)&stream[0], stream.size(), 0, libconsensus_flags, NULL) == expect, message); - BOOST_CHECK_MESSAGE(bitcoinconsensus_verify_script(begin_ptr(scriptPubKey), scriptPubKey.size(), (const unsigned char*)&stream[0], stream.size(), 0, libconsensus_flags, NULL) == expect,message); + BOOST_CHECK_MESSAGE(bitcoinconsensus_verify_script_with_amount(scriptPubKey.data(), scriptPubKey.size(), 0, (const unsigned char*)&stream[0], stream.size(), 0, libconsensus_flags, NULL) == expect, message); + BOOST_CHECK_MESSAGE(bitcoinconsensus_verify_script(scriptPubKey.data(), scriptPubKey.size(), (const unsigned char*)&stream[0], stream.size(), 0, libconsensus_flags, NULL) == expect,message); } } #endif diff --git a/src/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp index 139389117a..2a5a78de02 100644 --- a/src/test/test_bitcoin.cpp +++ b/src/test/test_bitcoin.cpp @@ -20,6 +20,7 @@ #include "ui_interface.h" #include "rpc/server.h" #include "rpc/register.h" +#include "script/sigcache.h" #include "test/testutil.h" @@ -40,6 +41,7 @@ BasicTestingSetup::BasicTestingSetup(const std::string& chainName) ECC_Start(); SetupEnvironment(); SetupNetworking(); + InitSignatureCache(); fPrintToDebugLog = false; // don't want to write to debug.log file fCheckBlockIndex = true; SelectParams(chainName); @@ -128,7 +130,7 @@ TestChain100Setup::CreateAndProcessBlock(const std::vector<CMutableTransaction>& while (!CheckProofOfWork(block.GetHash(), block.nBits, chainparams.GetConsensus())) ++block.nNonce; std::shared_ptr<const CBlock> shared_pblock = std::make_shared<const CBlock>(block); - ProcessNewBlock(chainparams, shared_pblock, true, NULL, NULL); + ProcessNewBlock(chainparams, shared_pblock, true, NULL); CBlock result = block; return result; diff --git a/src/test/test_bitcoin_fuzzy.cpp b/src/test/test_bitcoin_fuzzy.cpp new file mode 100644 index 0000000000..e1abde16f4 --- /dev/null +++ b/src/test/test_bitcoin_fuzzy.cpp @@ -0,0 +1,256 @@ +// Copyright (c) 2009-2015 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#if defined(HAVE_CONFIG_H) +#include "config/bitcoin-config.h" +#endif + +#include "consensus/merkle.h" +#include "primitives/block.h" +#include "script/script.h" +#include "addrman.h" +#include "chain.h" +#include "coins.h" +#include "compressor.h" +#include "net.h" +#include "protocol.h" +#include "streams.h" +#include "undo.h" +#include "version.h" + +#include <stdint.h> +#include <unistd.h> + +#include <algorithm> +#include <vector> + +enum TEST_ID { + CBLOCK_DESERIALIZE=0, + CTRANSACTION_DESERIALIZE, + CBLOCKLOCATOR_DESERIALIZE, + CBLOCKMERKLEROOT, + CADDRMAN_DESERIALIZE, + CBLOCKHEADER_DESERIALIZE, + CBANENTRY_DESERIALIZE, + CTXUNDO_DESERIALIZE, + CBLOCKUNDO_DESERIALIZE, + CCOINS_DESERIALIZE, + CNETADDR_DESERIALIZE, + CSERVICE_DESERIALIZE, + CMESSAGEHEADER_DESERIALIZE, + CADDRESS_DESERIALIZE, + CINV_DESERIALIZE, + CBLOOMFILTER_DESERIALIZE, + CDISKBLOCKINDEX_DESERIALIZE, + CTXOUTCOMPRESSOR_DESERIALIZE, + TEST_ID_END +}; + +bool read_stdin(std::vector<char> &data) { + char buffer[1024]; + ssize_t length=0; + while((length = read(STDIN_FILENO, buffer, 1024)) > 0) { + data.insert(data.end(), buffer, buffer+length); + + if (data.size() > (1<<20)) return false; + } + return length==0; +} + +int main(int argc, char **argv) +{ + std::vector<char> buffer; + if (!read_stdin(buffer)) return 0; + + if (buffer.size() < sizeof(uint32_t)) return 0; + + uint32_t test_id = 0xffffffff; + memcpy(&test_id, &buffer[0], sizeof(uint32_t)); + buffer.erase(buffer.begin(), buffer.begin() + sizeof(uint32_t)); + + if (test_id >= TEST_ID_END) return 0; + + CDataStream ds(buffer, SER_NETWORK, INIT_PROTO_VERSION); + try { + int nVersion; + ds >> nVersion; + ds.SetVersion(nVersion); + } catch (const std::ios_base::failure& e) { + return 0; + } + + switch(test_id) { + case CBLOCK_DESERIALIZE: + { + try + { + CBlock block; + ds >> block; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CTRANSACTION_DESERIALIZE: + { + try + { + CTransaction tx(deserialize, ds); + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CBLOCKLOCATOR_DESERIALIZE: + { + try + { + CBlockLocator bl; + ds >> bl; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CBLOCKMERKLEROOT: + { + try + { + CBlock block; + ds >> block; + bool mutated; + BlockMerkleRoot(block, &mutated); + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CADDRMAN_DESERIALIZE: + { + try + { + CAddrMan am; + ds >> am; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CBLOCKHEADER_DESERIALIZE: + { + try + { + CBlockHeader bh; + ds >> bh; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CBANENTRY_DESERIALIZE: + { + try + { + CBanEntry be; + ds >> be; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CTXUNDO_DESERIALIZE: + { + try + { + CTxUndo tu; + ds >> tu; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CBLOCKUNDO_DESERIALIZE: + { + try + { + CBlockUndo bu; + ds >> bu; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CCOINS_DESERIALIZE: + { + try + { + CCoins block; + ds >> block; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CNETADDR_DESERIALIZE: + { + try + { + CNetAddr na; + ds >> na; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CSERVICE_DESERIALIZE: + { + try + { + CService s; + ds >> s; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CMESSAGEHEADER_DESERIALIZE: + { + CMessageHeader::MessageStartChars pchMessageStart = {0x00, 0x00, 0x00, 0x00}; + try + { + CMessageHeader mh(pchMessageStart); + ds >> mh; + if (!mh.IsValid(pchMessageStart)) {return 0;} + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CADDRESS_DESERIALIZE: + { + try + { + CAddress a; + ds >> a; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CINV_DESERIALIZE: + { + try + { + CInv i; + ds >> i; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CBLOOMFILTER_DESERIALIZE: + { + try + { + CBloomFilter bf; + ds >> bf; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CDISKBLOCKINDEX_DESERIALIZE: + { + try + { + CDiskBlockIndex dbi; + ds >> dbi; + } catch (const std::ios_base::failure& e) {return 0;} + break; + } + case CTXOUTCOMPRESSOR_DESERIALIZE: + { + CTxOut to; + try + { + ds >> to; + } catch (const std::ios_base::failure& e) {return 0;} + + CTxOutCompressor toc(to); + break; + } + default: + return 0; + } + return 0; +} + diff --git a/src/test/txvalidationcache_tests.cpp b/src/test/txvalidationcache_tests.cpp index 55b4d28fb2..9f58f004d5 100644 --- a/src/test/txvalidationcache_tests.cpp +++ b/src/test/txvalidationcache_tests.cpp @@ -39,6 +39,7 @@ BOOST_FIXTURE_TEST_CASE(tx_mempool_block_doublespend, TestChain100Setup) spends.resize(2); for (int i = 0; i < 2; i++) { + spends[i].nVersion = 1; spends[i].vin.resize(1); spends[i].vin[0].prevout.hash = coinbaseTxns[0].GetHash(); spends[i].vin[0].prevout.n = 0; diff --git a/src/torcontrol.cpp b/src/torcontrol.cpp index ffb9993f90..67a69363f0 100644 --- a/src/torcontrol.cpp +++ b/src/torcontrol.cpp @@ -501,10 +501,10 @@ static std::vector<uint8_t> ComputeResponse(const std::string &key, const std::v { CHMAC_SHA256 computeHash((const uint8_t*)key.data(), key.size()); std::vector<uint8_t> computedHash(CHMAC_SHA256::OUTPUT_SIZE, 0); - computeHash.Write(begin_ptr(cookie), cookie.size()); - computeHash.Write(begin_ptr(clientNonce), clientNonce.size()); - computeHash.Write(begin_ptr(serverNonce), serverNonce.size()); - computeHash.Finalize(begin_ptr(computedHash)); + computeHash.Write(cookie.data(), cookie.size()); + computeHash.Write(clientNonce.data(), clientNonce.size()); + computeHash.Write(serverNonce.data(), serverNonce.size()); + computeHash.Finalize(computedHash.data()); return computedHash; } diff --git a/src/util.cpp b/src/util.cpp index 014013d214..60701e7949 100644 --- a/src/util.cpp +++ b/src/util.cpp @@ -704,13 +704,13 @@ void ShrinkDebugFile() // Restart the file with some of the end std::vector <char> vch(200000,0); fseek(file, -((long)vch.size()), SEEK_END); - int nBytes = fread(begin_ptr(vch), 1, vch.size(), file); + int nBytes = fread(vch.data(), 1, vch.size(), file); fclose(file); file = fopen(pathLog.string().c_str(), "w"); if (file) { - fwrite(begin_ptr(vch), 1, nBytes, file); + fwrite(vch.data(), 1, nBytes, file); fclose(file); } } diff --git a/src/validation.cpp b/src/validation.cpp index 7163b99a67..02c047f1d4 100644 --- a/src/validation.cpp +++ b/src/validation.cpp @@ -2100,7 +2100,8 @@ bool static DisconnectTip(CValidationState& state, const CChainParams& chainpara CCoinsViewCache view(pcoinsTip); if (!DisconnectBlock(block, state, pindexDelete, view)) return error("DisconnectTip(): DisconnectBlock %s failed", pindexDelete->GetBlockHash().ToString()); - assert(view.Flush()); + bool flushed = view.Flush(); + assert(flushed); } LogPrint("bench", "- Disconnect block: %.2fms\n", (GetTimeMicros() - nStart) * 0.001); // Write the chain state to disk, if necessary. @@ -2189,7 +2190,8 @@ bool static ConnectTip(CValidationState& state, const CChainParams& chainparams, } nTime3 = GetTimeMicros(); nTimeConnectTotal += nTime3 - nTime2; LogPrint("bench", " - Connect total: %.2fms [%.2fs]\n", (nTime3 - nTime2) * 0.001, nTimeConnectTotal * 0.000001); - assert(view.Flush()); + bool flushed = view.Flush(); + assert(flushed); } int64_t nTime4 = GetTimeMicros(); nTimeFlush += nTime4 - nTime3; LogPrint("bench", " - Flush: %.2fms [%.2fs]\n", (nTime4 - nTime3) * 0.001, nTimeFlush * 0.000001); @@ -3114,7 +3116,7 @@ static bool AcceptBlock(const CBlock& block, CValidationState& state, const CCha return true; } -bool ProcessNewBlock(const CChainParams& chainparams, const std::shared_ptr<const CBlock> pblock, bool fForceProcessing, const CDiskBlockPos* dbp, bool *fNewBlock) +bool ProcessNewBlock(const CChainParams& chainparams, const std::shared_ptr<const CBlock> pblock, bool fForceProcessing, bool *fNewBlock) { { LOCK(cs_main); @@ -3123,7 +3125,7 @@ bool ProcessNewBlock(const CChainParams& chainparams, const std::shared_ptr<cons CBlockIndex *pindex = NULL; if (fNewBlock) *fNewBlock = false; CValidationState state; - bool ret = AcceptBlock(*pblock, state, chainparams, &pindex, fForceProcessing, dbp, fNewBlock); + bool ret = AcceptBlock(*pblock, state, chainparams, &pindex, fForceProcessing, NULL, fNewBlock); CheckBlockIndex(chainparams.GetConsensus()); if (!ret) { GetMainSignals().BlockChecked(*pblock, state); diff --git a/src/validation.h b/src/validation.h index 28e81d21c6..e50a82b9dd 100644 --- a/src/validation.h +++ b/src/validation.h @@ -229,11 +229,10 @@ static const uint64_t MIN_DISK_SPACE_FOR_BLOCK_FILES = 550 * 1024 * 1024; * * @param[in] pblock The block we want to process. * @param[in] fForceProcessing Process this block even if unrequested; used for non-network block sources and whitelisted peers. - * @param[out] dbp The already known disk position of pblock, or NULL if not yet stored. * @param[out] fNewBlock A boolean which is set to indicate if the block was first received via this call * @return True if state.IsValid() */ -bool ProcessNewBlock(const CChainParams& chainparams, const std::shared_ptr<const CBlock> pblock, bool fForceProcessing, const CDiskBlockPos* dbp, bool* fNewBlock); +bool ProcessNewBlock(const CChainParams& chainparams, const std::shared_ptr<const CBlock> pblock, bool fForceProcessing, bool* fNewBlock); /** * Process incoming block headers. diff --git a/src/wallet/test/crypto_tests.cpp b/src/wallet/test/crypto_tests.cpp index ce35c53c48..c64c76244e 100644 --- a/src/wallet/test/crypto_tests.cpp +++ b/src/wallet/test/crypto_tests.cpp @@ -42,15 +42,19 @@ bool OldEncrypt(const CKeyingMaterial& vchPlaintext, std::vector<unsigned char> int nCLen = nLen + AES_BLOCK_SIZE, nFLen = 0; vchCiphertext = std::vector<unsigned char> (nCLen); - EVP_CIPHER_CTX ctx; + EVP_CIPHER_CTX *ctx = EVP_CIPHER_CTX_new(); + + if (!ctx) return false; bool fOk = true; - EVP_CIPHER_CTX_init(&ctx); - if (fOk) fOk = EVP_EncryptInit_ex(&ctx, EVP_aes_256_cbc(), NULL, chKey, chIV) != 0; - if (fOk) fOk = EVP_EncryptUpdate(&ctx, &vchCiphertext[0], &nCLen, &vchPlaintext[0], nLen) != 0; - if (fOk) fOk = EVP_EncryptFinal_ex(&ctx, (&vchCiphertext[0]) + nCLen, &nFLen) != 0; - EVP_CIPHER_CTX_cleanup(&ctx); + EVP_CIPHER_CTX_init(ctx); + if (fOk) fOk = EVP_EncryptInit_ex(ctx, EVP_aes_256_cbc(), NULL, chKey, chIV) != 0; + if (fOk) fOk = EVP_EncryptUpdate(ctx, &vchCiphertext[0], &nCLen, &vchPlaintext[0], nLen) != 0; + if (fOk) fOk = EVP_EncryptFinal_ex(ctx, (&vchCiphertext[0]) + nCLen, &nFLen) != 0; + EVP_CIPHER_CTX_cleanup(ctx); + + EVP_CIPHER_CTX_free(ctx); if (!fOk) return false; @@ -66,15 +70,19 @@ bool OldDecrypt(const std::vector<unsigned char>& vchCiphertext, CKeyingMaterial vchPlaintext = CKeyingMaterial(nPLen); - EVP_CIPHER_CTX ctx; + EVP_CIPHER_CTX *ctx = EVP_CIPHER_CTX_new(); + + if (!ctx) return false; bool fOk = true; - EVP_CIPHER_CTX_init(&ctx); - if (fOk) fOk = EVP_DecryptInit_ex(&ctx, EVP_aes_256_cbc(), NULL, chKey, chIV) != 0; - if (fOk) fOk = EVP_DecryptUpdate(&ctx, &vchPlaintext[0], &nPLen, &vchCiphertext[0], nLen) != 0; - if (fOk) fOk = EVP_DecryptFinal_ex(&ctx, (&vchPlaintext[0]) + nPLen, &nFLen) != 0; - EVP_CIPHER_CTX_cleanup(&ctx); + EVP_CIPHER_CTX_init(ctx); + if (fOk) fOk = EVP_DecryptInit_ex(ctx, EVP_aes_256_cbc(), NULL, chKey, chIV) != 0; + if (fOk) fOk = EVP_DecryptUpdate(ctx, &vchPlaintext[0], &nPLen, &vchCiphertext[0], nLen) != 0; + if (fOk) fOk = EVP_DecryptFinal_ex(ctx, (&vchPlaintext[0]) + nPLen, &nFLen) != 0; + EVP_CIPHER_CTX_cleanup(ctx); + + EVP_CIPHER_CTX_free(ctx); if (!fOk) return false; diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 00e97d3c7f..4c6916c04a 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -1542,9 +1542,11 @@ void CWallet::ReacceptWalletTransactions() bool CWalletTx::RelayWalletTransaction(CConnman* connman) { assert(pwallet->GetBroadcastTransactions()); - if (!IsCoinBase()) + if (!IsCoinBase() && !isAbandoned() && GetDepthInMainChain() == 0) { - if (GetDepthInMainChain() == 0 && !isAbandoned() && InMempool()) { + CValidationState state; + /* GetDepthInMainChain already catches known conflicts. */ + if (InMempool() || AcceptToMemoryPool(maxTxFee, state)) { LogPrintf("Relaying wtx %s\n", GetHash().ToString()); if (connman) { CInv inv(MSG_TX, GetHash()); @@ -2584,11 +2586,11 @@ bool CWallet::CommitTransaction(CWalletTx& wtxNew, CReserveKey& reservekey, CCon { // Broadcast if (!wtxNew.AcceptToMemoryPool(maxTxFee, state)) { - // This must not fail. The transaction has already been signed and recorded. - LogPrintf("CommitTransaction(): Error: Transaction not valid, %s\n", state.GetRejectReason()); - return false; + LogPrintf("CommitTransaction(): Transaction cannot be broadcast immediately, %s\n", state.GetRejectReason()); + // TODO: if we expect the failure to be long term or permanent, instead delete wtx from the wallet and return failure. + } else { + wtxNew.RelayWalletTransaction(connman); } - wtxNew.RelayWalletTransaction(connman); } } return true; |