diff --git a/src/amount.cpp b/src/amount.cpp index 21f5f18fdd..4f3390e856 100644 --- a/src/amount.cpp +++ b/src/amount.cpp @@ -1,16 +1,16 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers -// Copyright (c) 2017-2018 The Bitcoin developers +// Copyright (c) 2017-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include const std::string CURRENCY_UNIT = "BCH"; std::string Amount::ToString() const { return strprintf("%d.%08d %s", *this / COIN, (*this % COIN) / SATOSHI, CURRENCY_UNIT); } diff --git a/src/amount.h b/src/amount.h index 0400a4c6df..69b7ca77a1 100644 --- a/src/amount.h +++ b/src/amount.h @@ -1,173 +1,173 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers -// Copyright (c) 2017-2018 The Bitcoin developers +// Copyright (c) 2017-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_AMOUNT_H #define BITCOIN_AMOUNT_H #include #include #include #include #include struct Amount { private: int64_t amount; explicit constexpr Amount(int64_t _amount) : amount(_amount) {} public: constexpr Amount() : amount(0) {} constexpr Amount(const Amount &other) : amount(other.amount) {} /** * Assignement operator. */ constexpr Amount &operator=(const Amount &other) { amount = other.amount; return *this; } static constexpr Amount zero() { return Amount(0); } static constexpr Amount satoshi() { return Amount(1); } /** * Implement standard operators */ Amount &operator+=(const Amount a) { amount += a.amount; return *this; } Amount &operator-=(const Amount a) { amount -= a.amount; return *this; } /** * Equality */ friend constexpr bool operator==(const Amount a, const Amount b) { return a.amount == b.amount; } friend constexpr bool operator!=(const Amount a, const Amount b) { return !(a == b); } /** * Comparison */ friend constexpr bool operator<(const Amount a, const Amount b) { return a.amount < b.amount; } friend constexpr bool operator>(const Amount a, const Amount b) { return b < a; } friend constexpr bool operator<=(const Amount a, const Amount b) { return !(a > b); } friend constexpr bool operator>=(const Amount a, const Amount b) { return !(a < b); } /** * Unary minus */ constexpr Amount operator-() const { return Amount(-amount); } /** * Addition and subtraction. */ friend constexpr Amount operator+(const Amount a, const Amount b) { return Amount(a.amount + b.amount); } friend constexpr Amount operator-(const Amount a, const Amount b) { return a + -b; } /** * Multiplication */ friend constexpr Amount operator*(const int64_t a, const Amount b) { return Amount(a * b.amount); } friend constexpr Amount operator*(const int a, const Amount b) { return Amount(a * b.amount); } /** * Division */ constexpr int64_t operator/(const Amount b) const { return amount / b.amount; } constexpr Amount operator/(const int64_t b) const { return Amount(amount / b); } constexpr Amount operator/(const int b) const { return Amount(amount / b); } Amount &operator/=(const int64_t n) { amount /= n; return *this; } /** * Modulus */ constexpr Amount operator%(const Amount b) const { return Amount(amount % b.amount); } constexpr Amount operator%(const int64_t b) const { return Amount(amount % b); } constexpr Amount operator%(const int b) const { return Amount(amount % b); } /** * Do not implement double ops to get an error with double and ensure * casting to integer is explicit. */ friend constexpr Amount operator*(const double a, const Amount b) = delete; constexpr Amount operator/(const double b) const = delete; constexpr Amount operator%(const double b) const = delete; // ostream support friend std::ostream &operator<<(std::ostream &stream, const Amount &ca) { return stream << ca.amount; } std::string ToString() const; // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(amount); } }; static constexpr Amount SATOSHI = Amount::satoshi(); static constexpr Amount CASH = 100 * SATOSHI; static constexpr Amount COIN = 100000000 * SATOSHI; static constexpr Amount CENT = COIN / 100; extern const std::string CURRENCY_UNIT; /** * No amount larger than this (in satoshi) is valid. * * Note that this constant is *not* the total money supply, which in Bitcoin * currently happens to be less than 21,000,000 BCH for various reasons, but * rather a sanity check. As this sanity check is used by consensus-critical * validation code, the exact value of the MAX_MONEY constant is consensus * critical; in unusual circumstances like a(nother) overflow bug that allowed * for the creation of coins out of thin air modification could lead to a fork. */ static const Amount MAX_MONEY = 21000000 * COIN; inline bool MoneyRange(const Amount nValue) { return nValue >= Amount::zero() && nValue <= MAX_MONEY; } #endif // BITCOIN_AMOUNT_H diff --git a/src/avalanche.cpp b/src/avalanche.cpp index 72160e70e2..27ac43363a 100644 --- a/src/avalanche.cpp +++ b/src/avalanche.cpp @@ -1,494 +1,494 @@ -// Copyright (c) 2018 The Bitcoin developers +// Copyright (c) 2018-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include #include #include #include #include #include /** * Run the avalanche event loop every 10ms. */ static const int64_t AVALANCHE_TIME_STEP_MILLISECONDS = 10; /** * Maximum item count that can be polled at once. */ static const size_t AVALANCHE_MAX_ELEMENT_POLL = 4096; bool VoteRecord::registerVote(NodeId nodeid, uint32_t error) { // We just got a new vote, so there is one less inflight request. clearInflightRequest(); // We want to avoid having the same node voting twice in a quorum. if (!addNodeToQuorum(nodeid)) { return false; } /** * The result of the vote is determined from the error code. If the error * code is 0, there is no error and therefore the vote is yes. If there is * an error, we check the most significant bit to decide if the vote is a no * (for instance, the block is invalid) or is the vote inconclusive (for * instance, the queried node does not have the block yet). */ votes = (votes << 1) | (error == 0); consider = (consider << 1) | (int32_t(error) >= 0); /** * We compute the number of yes and/or no votes as follow: * * votes: 1010 * consider: 1100 * * yes votes: 1000 using votes & consider * no votes: 0100 using ~votes & consider */ bool yes = countBits(votes & consider & 0xff) > 6; if (!yes) { bool no = countBits(~votes & consider & 0xff) > 6; if (!no) { // The round is inconclusive. return false; } } // If the round is in agreement with previous rounds, increase confidence. if (isAccepted() == yes) { confidence += 2; return getConfidence() == AVALANCHE_FINALIZATION_SCORE; } // The round changed our state. We reset the confidence. confidence = yes; return true; } bool VoteRecord::addNodeToQuorum(NodeId nodeid) { if (nodeid == NO_NODE) { // Helpful for testing. return true; } // MMIX Linear Congruent Generator. const uint64_t r1 = 6364136223846793005 * uint64_t(nodeid) + 1442695040888963407; // Fibonacci hashing. const uint64_t r2 = 11400714819323198485ull * (nodeid ^ seed); // Combine and extract hash. const uint16_t h = (r1 + r2) >> 48; /** * Check if the node is in the filter. */ for (size_t i = 1; i < nodeFilter.size(); i++) { if (nodeFilter[(successfulVotes + i) % nodeFilter.size()] == h) { return false; } } /** * Add the node which just voted to the filter. */ nodeFilter[successfulVotes % nodeFilter.size()] = h; successfulVotes++; return true; } bool VoteRecord::registerPoll() const { uint8_t count = inflight.load(); while (count < AVALANCHE_MAX_INFLIGHT_POLL) { if (inflight.compare_exchange_weak(count, count + 1)) { return true; } } return false; } static bool IsWorthPolling(const CBlockIndex *pindex) { AssertLockHeld(cs_main); if (pindex->nStatus.isInvalid()) { // No point polling invalid blocks. return false; } if (IsBlockFinalized(pindex)) { // There is no point polling finalized block. return false; } return true; } bool AvalancheProcessor::addBlockToReconcile(const CBlockIndex *pindex) { bool isAccepted; { LOCK(cs_main); if (!IsWorthPolling(pindex)) { // There is no point polling this block. return false; } isAccepted = chainActive.Contains(pindex); } return vote_records.getWriteView() ->insert(std::make_pair(pindex, VoteRecord(isAccepted))) .second; } bool AvalancheProcessor::isAccepted(const CBlockIndex *pindex) const { auto r = vote_records.getReadView(); auto it = r->find(pindex); if (it == r.end()) { return false; } return it->second.isAccepted(); } int AvalancheProcessor::getConfidence(const CBlockIndex *pindex) const { auto r = vote_records.getReadView(); auto it = r->find(pindex); if (it == r.end()) { return -1; } return it->second.getConfidence(); } bool AvalancheProcessor::registerVotes( NodeId nodeid, const AvalancheResponse &response, std::vector &updates) { { // Save the time at which we can query again. auto w = peerSet.getWriteView(); auto it = w->find(nodeid); if (it != w->end()) { w->modify(it, [&response](Peer &p) { // FIXME: This will override the time even when we received an // old stale message. This should check that the message is // indeed the most up to date one before updating the time. p.nextRequestTime = std::chrono::steady_clock::now() + std::chrono::milliseconds(response.getCooldown()); }); } } std::vector invs; { // Check that the query exists. auto w = queries.getWriteView(); auto it = w->find(std::make_tuple(nodeid, response.getRound())); if (it == w.end()) { // NB: The request may be old, so we don't increase banscore. return false; } invs = std::move(it->invs); w->erase(it); } // Verify that the request and the vote are consistent. const std::vector &votes = response.GetVotes(); size_t size = invs.size(); if (votes.size() != size) { // TODO: increase banscore for inconsistent response. // NB: This isn't timeout but actually node misbehaving. return false; } for (size_t i = 0; i < size; i++) { if (invs[i].hash != votes[i].GetHash()) { // TODO: increase banscore for inconsistent response. // NB: This isn't timeout but actually node misbehaving. return false; } } std::map responseIndex; { LOCK(cs_main); for (auto &v : votes) { BlockMap::iterator mi = mapBlockIndex.find(BlockHash(v.GetHash())); if (mi == mapBlockIndex.end()) { // This should not happen, but just in case... continue; } CBlockIndex *pindex = mi->second; if (!IsWorthPolling(pindex)) { // There is no point polling this block. continue; } responseIndex.insert(std::make_pair(pindex, v)); } } { // Register votes. auto w = vote_records.getWriteView(); for (auto &p : responseIndex) { CBlockIndex *pindex = p.first; const AvalancheVote &v = p.second; auto it = w->find(pindex); if (it == w.end()) { // We are not voting on that item anymore. continue; } auto &vr = it->second; if (!vr.registerVote(nodeid, v.GetError())) { // This vote did not provide any extra information, move on. continue; } if (!vr.hasFinalized()) { // This item has note been finalized, so we have nothing more to // do. updates.emplace_back( pindex, vr.isAccepted() ? AvalancheBlockUpdate::Status::Accepted : AvalancheBlockUpdate::Status::Rejected); continue; } // We just finalized a vote. If it is valid, then let the caller // know. Either way, remove the item from the map. updates.emplace_back(pindex, vr.isAccepted() ? AvalancheBlockUpdate::Status::Finalized : AvalancheBlockUpdate::Status::Invalid); w->erase(it); } } return true; } bool AvalancheProcessor::addPeer(NodeId nodeid, int64_t score) { return peerSet.getWriteView() ->insert({nodeid, score, std::chrono::steady_clock::now()}) .second; } bool AvalancheProcessor::startEventLoop(CScheduler &scheduler) { LOCK(cs_running); if (running) { // Do not start the event loop twice. return false; } running = true; // Start the event loop. scheduler.scheduleEvery( [this]() -> bool { runEventLoop(); if (!stopRequest) { return true; } LOCK(cs_running); running = false; cond_running.notify_all(); // A stop request was made. return false; }, AVALANCHE_TIME_STEP_MILLISECONDS); return true; } bool AvalancheProcessor::stopEventLoop() { WAIT_LOCK(cs_running, lock); if (!running) { return false; } // Request avalanche to stop. stopRequest = true; // Wait for avalanche to stop. cond_running.wait(lock, [this]() EXCLUSIVE_LOCKS_REQUIRED(cs_running) { return !running; }); stopRequest = false; return true; } std::vector AvalancheProcessor::getInvsForNextPoll(bool forPoll) const { std::vector invs; auto r = vote_records.getReadView(); for (const std::pair &p : reverse_iterate(r)) { const CBlockIndex *pindex = p.first; { LOCK(cs_main); if (!IsWorthPolling(pindex)) { // Obviously do not poll if the block is not worth polling. continue; } } // Check if we can run poll. const bool shouldPoll = forPoll ? p.second.registerPoll() : p.second.shouldPoll(); if (!shouldPoll) { continue; } // We don't have a decision, we need more votes. invs.emplace_back(MSG_BLOCK, pindex->GetBlockHash()); if (invs.size() >= AVALANCHE_MAX_ELEMENT_POLL) { // Make sure we do not produce more invs than specified by the // protocol. return invs; } } return invs; } NodeId AvalancheProcessor::getSuitableNodeToQuery() { auto r = peerSet.getReadView(); auto it = r->get().begin(); if (it == r->get().end()) { return NO_NODE; } if (it->nextRequestTime <= std::chrono::steady_clock::now()) { return it->nodeid; } return NO_NODE; } void AvalancheProcessor::clearTimedoutRequests() { auto now = std::chrono::steady_clock::now(); std::map timedout_items{}; { // Clear expired requests. auto w = queries.getWriteView(); auto it = w->get().begin(); while (it != w->get().end() && it->timeout < now) { for (auto &i : it->invs) { timedout_items[i]++; } w->get().erase(it++); } } if (timedout_items.empty()) { return; } // In flight request accounting. for (const auto &p : timedout_items) { const CInv &inv = p.first; assert(inv.type == MSG_BLOCK); CBlockIndex *pindex; { LOCK(cs_main); BlockMap::iterator mi = mapBlockIndex.find(BlockHash(inv.hash)); if (mi == mapBlockIndex.end()) { continue; } pindex = mi->second; } auto w = vote_records.getWriteView(); auto it = w->find(pindex); if (it == w.end()) { continue; } it->second.clearInflightRequest(p.second); } } void AvalancheProcessor::runEventLoop() { // First things first, check if we have requests that timed out and clear // them. clearTimedoutRequests(); while (true) { NodeId nodeid = getSuitableNodeToQuery(); if (nodeid == NO_NODE) { return; } /** * If we lost contact to that node, then we remove it from nodeids, but * never add the request to queries, which ensures bad nodes get cleaned * up over time. */ std::vector invs; bool hasSent = connman->ForNode(nodeid, [this, &invs](CNode *pnode) { invs = getInvsForNextPoll(); if (invs.empty()) { return false; } uint64_t current_round = round++; { // Compute the time at which this requests times out. auto timeout = std::chrono::steady_clock::now() + queryTimeoutDuration; // Register the query. queries.getWriteView()->insert( {pnode->GetId(), current_round, timeout, invs}); // Set the timeout. auto w = peerSet.getWriteView(); auto it = w->find(pnode->GetId()); if (it != w->end()) { w->modify(it, [&timeout](Peer &p) { p.nextRequestTime = timeout; }); } } // Send the query to the node. connman->PushMessage( pnode, CNetMsgMaker(pnode->GetSendVersion()) .Make(NetMsgType::AVAPOLL, AvalanchePoll(current_round, std::move(invs)))); return true; }); // Success! if (hasSent || invs.empty()) { return; } // This node is obsolete, delete it. peerSet.getWriteView()->erase(nodeid); } } diff --git a/src/avalanche.h b/src/avalanche.h index bed0467a57..90c1dec3fe 100644 --- a/src/avalanche.h +++ b/src/avalanche.h @@ -1,354 +1,354 @@ -// Copyright (c) 2018 The Bitcoin developers +// Copyright (c) 2018-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_AVALANCHE_H #define BITCOIN_AVALANCHE_H #include #include #include // for CInv #include #include #include #include #include #include #include #include #include #include #include #include #include class Config; class CBlockIndex; class CScheduler; namespace { /** * Finalization score. */ static const int AVALANCHE_FINALIZATION_SCORE = 128; /** * How long before we consider that a query timed out. */ static const int AVALANCHE_DEFAULT_QUERY_TIMEOUT_DURATION_MILLISECONDS = 10000; /** * How many inflight requests can exist for one item. */ static const int AVALANCHE_MAX_INFLIGHT_POLL = 10; /** * Special NodeId that represent no node. */ static const NodeId NO_NODE = -1; } // namespace /** * Vote history. */ struct VoteRecord { private: // confidence's LSB bit is the result. Higher bits are actual confidence // score. uint16_t confidence = 0; // Historical record of votes. uint8_t votes = 0; // Each bit indicate if the vote is to be considered. uint8_t consider = 0; // How many in flight requests exists for this element. mutable std::atomic inflight{0}; // Seed for pseudorandom operations. const uint32_t seed = 0; // Track how many successful votes occured. uint32_t successfulVotes = 0; // Track the nodes which are part of the quorum. std::array nodeFilter{{0, 0, 0, 0, 0, 0, 0, 0}}; public: VoteRecord(bool accepted) : confidence(accepted) {} /** * Copy semantic */ VoteRecord(const VoteRecord &other) : confidence(other.confidence), votes(other.votes), consider(other.consider), inflight(other.inflight.load()), successfulVotes(other.successfulVotes), nodeFilter(other.nodeFilter) { } /** * Vote accounting facilities. */ bool isAccepted() const { return confidence & 0x01; } uint16_t getConfidence() const { return confidence >> 1; } bool hasFinalized() const { return getConfidence() >= AVALANCHE_FINALIZATION_SCORE; } /** * Register a new vote for an item and update confidence accordingly. * Returns true if the acceptance or finalization state changed. */ bool registerVote(NodeId nodeid, uint32_t error); /** * Register that a request is being made regarding that item. * The method is made const so that it can be accessed via a read only view * of vote_records. It's not a problem as it is made thread safe. */ bool registerPoll() const; /** * Return if this item is in condition to be polled at the moment. */ bool shouldPoll() const { return inflight < AVALANCHE_MAX_INFLIGHT_POLL; } /** * Clear `count` inflight requests. */ void clearInflightRequest(uint8_t count = 1) { inflight -= count; } private: /** * Add the node to the quorum. * Returns true if the node was added, false if the node already was in the * quorum. */ bool addNodeToQuorum(NodeId nodeid); }; class AvalancheVote { uint32_t error; uint256 hash; public: AvalancheVote() : error(-1), hash() {} AvalancheVote(uint32_t errorIn, uint256 hashIn) : error(errorIn), hash(hashIn) {} const uint256 &GetHash() const { return hash; } uint32_t GetError() const { return error; } // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(error); READWRITE(hash); } }; class AvalancheResponse { uint64_t round; uint32_t cooldown; std::vector votes; public: AvalancheResponse(uint64_t roundIn, uint32_t cooldownIn, std::vector votesIn) : round(roundIn), cooldown(cooldownIn), votes(votesIn) {} uint64_t getRound() const { return round; } uint32_t getCooldown() const { return cooldown; } const std::vector &GetVotes() const { return votes; } // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(round); READWRITE(cooldown); READWRITE(votes); } }; class AvalanchePoll { uint64_t round; std::vector invs; public: AvalanchePoll(uint64_t roundIn, std::vector invsIn) : round(roundIn), invs(invsIn) {} const std::vector &GetInvs() const { return invs; } // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(round); READWRITE(invs); } }; class AvalancheBlockUpdate { union { CBlockIndex *pindex; uintptr_t raw; }; static const size_t STATUS_BITS = 2; static const uintptr_t MASK = (1 << STATUS_BITS) - 1; static_assert( alignof(CBlockIndex) >= (1 << STATUS_BITS), "CBlockIndex alignement doesn't allow for Status to be stored."); public: enum Status : uint8_t { Invalid, Rejected, Accepted, Finalized, }; AvalancheBlockUpdate(CBlockIndex *pindexIn, Status statusIn) : pindex(pindexIn) { raw |= statusIn; } Status getStatus() const { return Status(raw & MASK); } CBlockIndex *getBlockIndex() { return reinterpret_cast(raw & ~MASK); } const CBlockIndex *getBlockIndex() const { return const_cast(this)->getBlockIndex(); } }; typedef std::map BlockVoteMap; struct next_request_time {}; struct query_timeout {}; class AvalancheProcessor { private: CConnman *connman; std::chrono::milliseconds queryTimeoutDuration; /** * Blocks to run avalanche on. */ RWCollection vote_records; /** * Keep track of peers and queries sent. */ std::atomic round; typedef std::chrono::time_point TimePoint; struct Peer { NodeId nodeid; int64_t score; TimePoint nextRequestTime; }; typedef boost::multi_index_container< Peer, boost::multi_index::indexed_by< // index by nodeid boost::multi_index::hashed_unique< boost::multi_index::member>, // sorted by nextRequestTime boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::member>>> PeerSet; RWCollection peerSet; struct Query { NodeId nodeid; uint64_t round; TimePoint timeout; /** * We declare this as mutable so it can be modified in the multi_index. * This is ok because we do not use this field to index in anyway. * * /!\ Do not use any mutable field as index. */ mutable std::vector invs; }; typedef boost::multi_index_container< Query, boost::multi_index::indexed_by< // index by nodeid/round boost::multi_index::ordered_unique< boost::multi_index::composite_key< Query, boost::multi_index::member, boost::multi_index::member>>, // sorted by timeout boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::member>>> QuerySet; RWCollection queries; /** * Start stop machinery. */ std::atomic stopRequest; bool running GUARDED_BY(cs_running); Mutex cs_running; std::condition_variable cond_running; public: AvalancheProcessor(CConnman *connmanIn) : connman(connmanIn), queryTimeoutDuration( AVALANCHE_DEFAULT_QUERY_TIMEOUT_DURATION_MILLISECONDS), round(0), stopRequest(false), running(false) {} ~AvalancheProcessor() { stopEventLoop(); } void setQueryTimeoutDuration(std::chrono::milliseconds d) { queryTimeoutDuration = d; } bool addBlockToReconcile(const CBlockIndex *pindex); bool isAccepted(const CBlockIndex *pindex) const; int getConfidence(const CBlockIndex *pindex) const; bool registerVotes(NodeId nodeid, const AvalancheResponse &response, std::vector &updates); bool addPeer(NodeId nodeid, int64_t score); bool startEventLoop(CScheduler &scheduler); bool stopEventLoop(); private: void runEventLoop(); void clearTimedoutRequests(); std::vector getInvsForNextPoll(bool forPoll = true) const; NodeId getSuitableNodeToQuery(); friend struct AvalancheTest; }; #endif // BITCOIN_AVALANCHE_H diff --git a/src/bench/cashaddr.cpp b/src/bench/cashaddr.cpp index c3cab8c3fd..fa907242fd 100644 --- a/src/bench/cashaddr.cpp +++ b/src/bench/cashaddr.cpp @@ -1,32 +1,32 @@ -// Copyright (c) 2018 The Bitcoin developers +// Copyright (c) 2018-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include #include static void CashAddrEncode(benchmark::State &state) { std::vector buffer = {17, 79, 8, 99, 150, 189, 208, 162, 22, 23, 203, 163, 36, 58, 147, 227, 139, 2, 215, 100, 91, 38, 11, 141, 253, 40, 117, 21, 16, 90, 200, 24}; while (state.KeepRunning()) { cashaddr::Encode("bitcoincash", buffer); } } static void CashAddrDecode(benchmark::State &state) { const char *addrWithPrefix = "bitcoincash:qprnwmr02d7ky9m693qufj5mgkpf4wvssv0w86tkjd"; const char *addrNoPrefix = "qprnwmr02d7ky9m693qufj5mgkpf4wvssv0w86tkjd"; while (state.KeepRunning()) { cashaddr::Decode(addrWithPrefix, "bitcoincash"); cashaddr::Decode(addrNoPrefix, "bitcoincash"); } } BENCHMARK(CashAddrEncode, 800 * 1000); BENCHMARK(CashAddrDecode, 800 * 1000); diff --git a/src/blockfileinfo.h b/src/blockfileinfo.h index 7d37eecfa7..c4b9219866 100644 --- a/src/blockfileinfo.h +++ b/src/blockfileinfo.h @@ -1,75 +1,75 @@ -// Copyright (c) 2018 The Bitcoin developers +// Copyright (c) 2018-2020 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_BLOCKFILEINFO_H #define BITCOIN_BLOCKFILEINFO_H #include #include #include class CBlockFileInfo { public: //! number of blocks stored in file unsigned int nBlocks; //! number of used bytes of block file unsigned int nSize; //! number of used bytes in the undo file unsigned int nUndoSize; //! lowest height of block in file unsigned int nHeightFirst; //! highest height of block in file unsigned int nHeightLast; //! earliest time of block in file uint64_t nTimeFirst; //! latest time of block in file uint64_t nTimeLast; ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(VARINT(nBlocks)); READWRITE(VARINT(nSize)); READWRITE(VARINT(nUndoSize)); READWRITE(VARINT(nHeightFirst)); READWRITE(VARINT(nHeightLast)); READWRITE(VARINT(nTimeFirst)); READWRITE(VARINT(nTimeLast)); } void SetNull() { nBlocks = 0; nSize = 0; nUndoSize = 0; nHeightFirst = 0; nHeightLast = 0; nTimeFirst = 0; nTimeLast = 0; } CBlockFileInfo() { SetNull(); } std::string ToString() const; /** update statistics (does not update nSize) */ void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn) { if (nBlocks == 0 || nHeightFirst > nHeightIn) { nHeightFirst = nHeightIn; } if (nBlocks == 0 || nTimeFirst > nTimeIn) { nTimeFirst = nTimeIn; } nBlocks++; if (nHeightIn > nHeightLast) { nHeightLast = nHeightIn; } if (nTimeIn > nTimeLast) { nTimeLast = nTimeIn; } } }; #endif // BITCOIN_BLOCKFILEINFO_H diff --git a/src/blockindexworkcomparator.h b/src/blockindexworkcomparator.h index 32a61b8849..3894d7bbee 100644 --- a/src/blockindexworkcomparator.h +++ b/src/blockindexworkcomparator.h @@ -1,43 +1,43 @@ -// Copyright (c) 2018 The Bitcoin developers +// Copyright (c) 2018-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_BLOCKINDEXWORKCOMPARATOR_H #define BITCOIN_BLOCKINDEXWORKCOMPARATOR_H // TODO: Split chain.h apart and only include CBlockIndex #include struct CBlockIndexWorkComparator { bool operator()(const CBlockIndex *pa, const CBlockIndex *pb) const { // First sort by most total work, ... if (pa->nChainWork > pb->nChainWork) { return false; } if (pa->nChainWork < pb->nChainWork) { return true; } // ... then by earliest time received, ... if (pa->nSequenceId < pb->nSequenceId) { return false; } if (pa->nSequenceId > pb->nSequenceId) { return true; } // Use pointer address as tie breaker (should only happen with blocks // loaded from disk, as those all have id 0). if (pa < pb) { return false; } if (pa > pb) { return true; } // Identical blocks. return false; } }; #endif // BITCOIN_BLOCKINDEXWORKCOMPARATOR_H diff --git a/src/blockstatus.h b/src/blockstatus.h index 2859bac3c5..8cd1a2a241 100644 --- a/src/blockstatus.h +++ b/src/blockstatus.h @@ -1,128 +1,128 @@ -// Copyright (c) 2018 The Bitcoin developers +// Copyright (c) 2018-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_BLOCKSTATUS_H #define BITCOIN_BLOCKSTATUS_H #include #include #include struct BlockStatus { private: uint32_t status; explicit constexpr BlockStatus(uint32_t nStatusIn) : status(nStatusIn) {} static const uint32_t VALIDITY_MASK = 0x07; // Full block available in blk*.dat static const uint32_t HAS_DATA_FLAG = 0x08; // Undo data available in rev*.dat static const uint32_t HAS_UNDO_FLAG = 0x10; // The block is invalid. static const uint32_t FAILED_FLAG = 0x20; // The block has an invalid parent. static const uint32_t FAILED_PARENT_FLAG = 0x40; // Mask used to check if the block failed. static const uint32_t INVALID_MASK = FAILED_FLAG | FAILED_PARENT_FLAG; // The block is being parked for some reason. It will be reconsidered if its // chains grows. static const uint32_t PARKED_FLAG = 0x80; // One of the block's parent is parked. static const uint32_t PARKED_PARENT_FLAG = 0x100; // Mask used to check for parked blocks. static const uint32_t PARKED_MASK = PARKED_FLAG | PARKED_PARENT_FLAG; public: explicit constexpr BlockStatus() : status(0) {} BlockValidity getValidity() const { return BlockValidity(status & VALIDITY_MASK); } BlockStatus withValidity(BlockValidity validity) const { return BlockStatus((status & ~VALIDITY_MASK) | uint32_t(validity)); } bool hasData() const { return status & HAS_DATA_FLAG; } BlockStatus withData(bool hasData = true) const { return BlockStatus((status & ~HAS_DATA_FLAG) | (hasData ? HAS_DATA_FLAG : 0)); } bool hasUndo() const { return status & HAS_UNDO_FLAG; } BlockStatus withUndo(bool hasUndo = true) const { return BlockStatus((status & ~HAS_UNDO_FLAG) | (hasUndo ? HAS_UNDO_FLAG : 0)); } bool hasFailed() const { return status & FAILED_FLAG; } BlockStatus withFailed(bool hasFailed = true) const { return BlockStatus((status & ~FAILED_FLAG) | (hasFailed ? FAILED_FLAG : 0)); } bool hasFailedParent() const { return status & FAILED_PARENT_FLAG; } BlockStatus withFailedParent(bool hasFailedParent = true) const { return BlockStatus((status & ~FAILED_PARENT_FLAG) | (hasFailedParent ? FAILED_PARENT_FLAG : 0)); } bool isParked() const { return status & PARKED_FLAG; } BlockStatus withParked(bool parked = true) const { return BlockStatus((status & ~PARKED_FLAG) | (parked ? PARKED_FLAG : 0)); } bool hasParkedParent() const { return status & PARKED_PARENT_FLAG; } BlockStatus withParkedParent(bool parkedParent = true) const { return BlockStatus((status & ~PARKED_PARENT_FLAG) | (parkedParent ? PARKED_PARENT_FLAG : 0)); } /** * Check whether this block index entry is valid up to the passed validity * level. */ bool isValid(enum BlockValidity nUpTo = BlockValidity::TRANSACTIONS) const { if (isInvalid()) { return false; } return getValidity() >= nUpTo; } bool isInvalid() const { return status & INVALID_MASK; } BlockStatus withClearedFailureFlags() const { return BlockStatus(status & ~INVALID_MASK); } bool isOnParkedChain() const { return status & PARKED_MASK; } BlockStatus withClearedParkedFlags() const { return BlockStatus(status & ~PARKED_MASK); } ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(VARINT(status)); } friend constexpr bool operator==(const BlockStatus a, const BlockStatus b) { return a.status == b.status; } friend constexpr bool operator!=(const BlockStatus a, const BlockStatus b) { return !(a == b); } }; #endif // BITCOIN_BLOCKSTATUS_H diff --git a/src/cashaddr.cpp b/src/cashaddr.cpp index 3dcb71f891..63b4aba647 100644 --- a/src/cashaddr.cpp +++ b/src/cashaddr.cpp @@ -1,299 +1,299 @@ // Copyright (c) 2017 Pieter Wuille -// Copyright (c) 2017 The Bitcoin developers +// Copyright (c) 2017-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include namespace { typedef std::vector data; /** * The cashaddr character set for encoding. */ const char *CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"; /** * The cashaddr character set for decoding. */ const int8_t CHARSET_REV[128] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15, -1, 10, 17, 21, 20, 26, 30, 7, 5, -1, -1, -1, -1, -1, -1, -1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, 31, 27, 19, -1, 1, 0, 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, -1, -1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, 31, 27, 19, -1, 1, 0, 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, -1}; /** * Concatenate two byte arrays. */ data Cat(data x, const data &y) { x.insert(x.end(), y.begin(), y.end()); return x; } /** * This function will compute what 8 5-bit values to XOR into the last 8 input * values, in order to make the checksum 0. These 8 values are packed together * in a single 40-bit integer. The higher bits correspond to earlier values. */ uint64_t PolyMod(const data &v) { /** * The input is interpreted as a list of coefficients of a polynomial over F * = GF(32), with an implicit 1 in front. If the input is [v0,v1,v2,v3,v4], * that polynomial is v(x) = 1*x^5 + v0*x^4 + v1*x^3 + v2*x^2 + v3*x + v4. * The implicit 1 guarantees that [v0,v1,v2,...] has a distinct checksum * from [0,v0,v1,v2,...]. * * The output is a 40-bit integer whose 5-bit groups are the coefficients of * the remainder of v(x) mod g(x), where g(x) is the cashaddr generator, x^8 * + {19}*x^7 + {3}*x^6 + {25}*x^5 + {11}*x^4 + {25}*x^3 + {3}*x^2 + {19}*x * + {1}. g(x) is chosen in such a way that the resulting code is a BCH * code, guaranteeing detection of up to 4 errors within a window of 1025 * characters. Among the various possible BCH codes, one was selected to in * fact guarantee detection of up to 5 errors within a window of 160 * characters and 6 erros within a window of 126 characters. In addition, * the code guarantee the detection of a burst of up to 8 errors. * * Note that the coefficients are elements of GF(32), here represented as * decimal numbers between {}. In this finite field, addition is just XOR of * the corresponding numbers. For example, {27} + {13} = {27 ^ 13} = {22}. * Multiplication is more complicated, and requires treating the bits of * values themselves as coefficients of a polynomial over a smaller field, * GF(2), and multiplying those polynomials mod a^5 + a^3 + 1. For example, * {5} * {26} = (a^2 + 1) * (a^4 + a^3 + a) = (a^4 + a^3 + a) * a^2 + (a^4 + * a^3 + a) = a^6 + a^5 + a^4 + a = a^3 + 1 (mod a^5 + a^3 + 1) = {9}. * * During the course of the loop below, `c` contains the bitpacked * coefficients of the polynomial constructed from just the values of v that * were processed so far, mod g(x). In the above example, `c` initially * corresponds to 1 mod (x), and after processing 2 inputs of v, it * corresponds to x^2 + v0*x + v1 mod g(x). As 1 mod g(x) = 1, that is the * starting value for `c`. */ uint64_t c = 1; for (uint8_t d : v) { /** * We want to update `c` to correspond to a polynomial with one extra * term. If the initial value of `c` consists of the coefficients of * c(x) = f(x) mod g(x), we modify it to correspond to * c'(x) = (f(x) * x + d) mod g(x), where d is the next input to * process. * * Simplifying: * c'(x) = (f(x) * x + d) mod g(x) * ((f(x) mod g(x)) * x + d) mod g(x) * (c(x) * x + d) mod g(x) * If c(x) = c0*x^5 + c1*x^4 + c2*x^3 + c3*x^2 + c4*x + c5, we want to * compute * c'(x) = (c0*x^5 + c1*x^4 + c2*x^3 + c3*x^2 + c4*x + c5) * x + d * mod g(x) * = c0*x^6 + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d * mod g(x) * = c0*(x^6 mod g(x)) + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + * c5*x + d * If we call (x^6 mod g(x)) = k(x), this can be written as * c'(x) = (c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d) + c0*k(x) */ // First, determine the value of c0: uint8_t c0 = c >> 35; // Then compute c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d: c = ((c & 0x07ffffffff) << 5) ^ d; // Finally, for each set bit n in c0, conditionally add {2^n}k(x): if (c0 & 0x01) { // k(x) = {19}*x^7 + {3}*x^6 + {25}*x^5 + {11}*x^4 + {25}*x^3 + // {3}*x^2 + {19}*x + {1} c ^= 0x98f2bc8e61; } if (c0 & 0x02) { // {2}k(x) = {15}*x^7 + {6}*x^6 + {27}*x^5 + {22}*x^4 + {27}*x^3 + // {6}*x^2 + {15}*x + {2} c ^= 0x79b76d99e2; } if (c0 & 0x04) { // {4}k(x) = {30}*x^7 + {12}*x^6 + {31}*x^5 + {5}*x^4 + {31}*x^3 + // {12}*x^2 + {30}*x + {4} c ^= 0xf33e5fb3c4; } if (c0 & 0x08) { // {8}k(x) = {21}*x^7 + {24}*x^6 + {23}*x^5 + {10}*x^4 + {23}*x^3 + // {24}*x^2 + {21}*x + {8} c ^= 0xae2eabe2a8; } if (c0 & 0x10) { // {16}k(x) = {3}*x^7 + {25}*x^6 + {7}*x^5 + {20}*x^4 + {7}*x^3 + // {25}*x^2 + {3}*x + {16} c ^= 0x1e4f43e470; } } /** * PolyMod computes what value to xor into the final values to make the * checksum 0. However, if we required that the checksum was 0, it would be * the case that appending a 0 to a valid list of values would result in a * new valid list. For that reason, cashaddr requires the resulting checksum * to be 1 instead. */ return c ^ 1; } /** * Convert to lower case. * * Assume the input is a character. */ inline uint8_t LowerCase(uint8_t c) { // ASCII black magic. return c | 0x20; } /** * Expand the address prefix for the checksum computation. */ data ExpandPrefix(const std::string &prefix) { data ret; ret.resize(prefix.size() + 1); for (size_t i = 0; i < prefix.size(); ++i) { ret[i] = prefix[i] & 0x1f; } ret[prefix.size()] = 0; return ret; } /** * Verify a checksum. */ bool VerifyChecksum(const std::string &prefix, const data &payload) { return PolyMod(Cat(ExpandPrefix(prefix), payload)) == 0; } /** * Create a checksum. */ data CreateChecksum(const std::string &prefix, const data &payload) { data enc = Cat(ExpandPrefix(prefix), payload); // Append 8 zeroes. enc.resize(enc.size() + 8); // Determine what to XOR into those 8 zeroes. uint64_t mod = PolyMod(enc); data ret(8); for (size_t i = 0; i < 8; ++i) { // Convert the 5-bit groups in mod to checksum values. ret[i] = (mod >> (5 * (7 - i))) & 0x1f; } return ret; } } // namespace namespace cashaddr { /** * Encode a cashaddr string. */ std::string Encode(const std::string &prefix, const data &payload) { data checksum = CreateChecksum(prefix, payload); data combined = Cat(payload, checksum); std::string ret = prefix + ':'; ret.reserve(ret.size() + combined.size()); for (uint8_t c : combined) { ret += CHARSET[c]; } return ret; } /** * Decode a cashaddr string. */ std::pair Decode(const std::string &str, const std::string &default_prefix) { // Go over the string and do some sanity checks. bool lower = false, upper = false, hasNumber = false; size_t prefixSize = 0; for (size_t i = 0; i < str.size(); ++i) { uint8_t c = str[i]; if (c >= 'a' && c <= 'z') { lower = true; continue; } if (c >= 'A' && c <= 'Z') { upper = true; continue; } if (c >= '0' && c <= '9') { // We cannot have numbers in the prefix. hasNumber = true; continue; } if (c == ':') { // The separator cannot be the first character, cannot have number // and there must not be 2 separators. if (hasNumber || i == 0 || prefixSize != 0) { return {}; } prefixSize = i; continue; } // We have an unexpected character. return {}; } // We can't have both upper case and lowercase. if (upper && lower) { return {}; } // Get the prefix. std::string prefix; if (prefixSize == 0) { prefix = default_prefix; } else { prefix.reserve(prefixSize); for (size_t i = 0; i < prefixSize; ++i) { prefix += LowerCase(str[i]); } // Now add the ':' in the size. prefixSize++; } // Decode values. const size_t valuesSize = str.size() - prefixSize; data values(valuesSize); for (size_t i = 0; i < valuesSize; ++i) { uint8_t c = str[i + prefixSize]; // We have an invalid char in there. if (c > 127 || CHARSET_REV[c] == -1) { return {}; } values[i] = CHARSET_REV[c]; } // Verify the checksum. if (!VerifyChecksum(prefix, values)) { return {}; } return {std::move(prefix), data(values.begin(), values.end() - 8)}; } } // namespace cashaddr diff --git a/src/cashaddr.h b/src/cashaddr.h index 0a8e697a62..18010c33e2 100644 --- a/src/cashaddr.h +++ b/src/cashaddr.h @@ -1,31 +1,31 @@ // Copyright (c) 2017 Pieter Wuille -// Copyright (c) 2017 The Bitcoin developers +// Copyright (c) 2017-2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_CASHADDR_H #define BITCOIN_CASHADDR_H // Cashaddr is an address format inspired by bech32. #include #include #include namespace cashaddr { /** * Encode a cashaddr string. Returns the empty string in case of failure. */ std::string Encode(const std::string &prefix, const std::vector &values); /** * Decode a cashaddr string. Returns (prefix, data). Empty prefix means failure. */ std::pair> Decode(const std::string &str, const std::string &default_prefix); } // namespace cashaddr #endif // BITCOIN_CASHADDR_H diff --git a/src/cashaddrenc.cpp b/src/cashaddrenc.cpp index 5eced16796..d75d3668e8 100644 --- a/src/cashaddrenc.cpp +++ b/src/cashaddrenc.cpp @@ -1,190 +1,190 @@ -// Copyright (c) 2017 The Bitcoin developers +// Copyright (c) 2017-2019 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include #include #include