Compact Blocks #8068

TheBlueMatt commented at 1:49 AM on May 18, 2016: member

This is based on #8020 and implements the BIP 152 draft from https://github.com/TheBlueMatt/bips/blob/152/bip-0152.mediawiki.

In short, it sends blocks as a set of short transaction IDs to allow nodes to not double-relay transactions in blocks. There are lots of details in both the BIP and the discussion on the bitcoin-dev ML.

There are still some TODOs in the code here, but I do not think they are blockers for this, as they are not protocol-level changes and can be implemented separately to make the protocol more effecient.

in src/blockencodings.h:None in 816956e8da outdated

 147 | +        if (ser_action.ForRead()) {
 148 | +            size_t i = 0;
 149 | +            while (shorttxids.size() < shorttxids_size) {
 150 | +                shorttxids.resize(std::min(1000 + shorttxids.size(), shorttxids_size));
 151 | +                for (; i < shorttxids.size(); i++) {
 152 | +                    uint32_t lsb; uint16_t msb;

paveljanik commented at 5:41 AM on May 18, 2016:

clang warns about lsb and msb used uninitialized.

paveljanik commented at 5:52 AM on May 18, 2016: contributor

test/test_bitcoin failures in travis are strange. Can't reproduce locally. Hmm, we should probably include src/test-suite.log in the travis output in such cases.

... just a second after I wrote this, I see this failure in my logs:

Running 200 test cases...
test/net_tests.cpp:92: error in "caddrdb_read": check addrman1.size() == 3 failed
test/net_tests.cpp:102: error in "caddrdb_read": check addrman2.size() == 3 failed

*** 2 failures detected in test suite "Bitcoin Test Suite"

I will compare many runs in master and this PR:

master: 8 failures
8068: 6 failures

As this is present in master already, it is not caused by this PR. I'll investigate...

The question is, if the travis failure in test_bitcoin is the same I see here...

Looks like the same problem was already reported by me: #7696 (comment)

Separate issue now: #8069

gmaxwell commented at 9:47 AM on May 18, 2016: contributor

Needs rebase to remove the siphash commits from the top. :)

TheBlueMatt force-pushed on May 18, 2016

TheBlueMatt commented at 8:23 PM on May 18, 2016: member

Rebased and fixed @paveljanik's clang compile-warning.

TheBlueMatt commented at 8:23 PM on May 18, 2016: member

Also removed the varint stuff...turns out it wasnt as big a gain as I thought.

dcousens commented at 1:43 AM on May 19, 2016: contributor

concept ACK

TheBlueMatt force-pushed on May 19, 2016

jonasschnelli added the label P2P on May 19, 2016

TheBlueMatt force-pushed on May 20, 2016

TheBlueMatt force-pushed on May 21, 2016

arowser commented at 8:43 AM on May 25, 2016: contributor

Can one of the admins verify this patch?

sipa commented at 1:00 PM on May 26, 2016: member

Thinking more about this (and seeing more pull requests touching the mempool), I think having the mempool store its CTransaction objects using shared_ptr's would make sense.

During erasing from the mempool, we return the deleted entries upwards (for signalling to wallets etc). This requires expensive copying that could be avoided with shared_ptr (alternatively, see #8099)
During transaction relay, BIP35 processing, and tx getdata, we fetch mempool transactions (copying them!) before determining whether they can be relayed. Especially with filters active, this is a pretty expensive operation for omitted cases. As none of the things done with the result (filtering, inving, serializing) require a full copy, shared_ptr would be far more efficient.
mapRelay often contains transactions that are also stored in the mempool. Shared_ptr's would alleviate duplicate storage space.
In this PR, it would avoid the need for manual reference counting and for giving the CTxMempool the weird responsibility for owning transactions that aren't even in the mempool anymore.

TheBlueMatt force-pushed on May 26, 2016

NicolasDorier commented at 12:59 AM on May 29, 2016: contributor

Will test that during next week, I need to use it for one of my project

gmaxwell commented at 4:06 PM on May 30, 2016: contributor

This should update the implemented BIPs list.

sipa commented at 1:35 AM on June 1, 2016: member

Here is a rebase on top of #8126, using shared_ptr's for partial block transactions: https://github.com/sipa/bitcoin/commits/compactblocks

sipa commented at 1:27 PM on June 1, 2016: member

Ok, some comments after looking through the code and working to rebase:

CBlockHeaderAndShortTxIDs::FillShortTxIDSelector should use htole64 before serializing the nonce (endianness correctness)
PartiallyDownloadedBlock::InitData's have_txn can use a vector<bool> (which is bitpacked internally) instead of manual bit logic (nit)
The code in ProcessMessage to add a peer as a direct compact block request peer is duplicated.
A lot of calls to error() that should be LogPrintf's or nothing at all.

gmaxwell commented at 5:16 PM on June 1, 2016: contributor

It would be nice if the getpeerinfo showed the sendcmpct status (maybe hex for the version?).

luke-jr commented at 5:39 PM on June 1, 2016: member

(maybe hex for the version?)

How to display numbers is a client-side thing, and I'm not sure it makes sense to bloat up bitcoin-cli with this kind of logic?

dcousens commented at 2:58 AM on June 2, 2016: contributor

(maybe hex for the version?)

Worth nothing this issue has come up before and was added as versionHex.

in src/blockencodings.cpp:None in e3820046f9 outdated

 161 | +        for (size_t i = 0; i < txhashes.size(); i++) {
 162 | +            if (!txhashes[i].IsNull()) {
 163 | +                if (prefilledit != prefilledtxn.end() && prefilledit->index == i)
 164 | +                    prefilledit++;
 165 | +                else
 166 | +                    pool->ReleaseTxLock(txhashes[i]);

NicolasDorier commented at 6:19 AM on June 4, 2016:

No need for taking lock on pool->cs ?

TheBlueMatt commented at 7:45 AM on June 6, 2016:

Not sure what you're asking? There is no explicit lock on cs here, but ReleaseTxLock does LOCK(cs) itself.

NicolasDorier commented at 4:50 PM on June 6, 2016:

ok, it responds to my question thanks.

in src/blockencodings.h:None in e3820046f9 outdated

  17 | +
  18 | +    ADD_SERIALIZE_METHODS;
  19 | +
  20 | +    template <typename Stream, typename Operation>
  21 | +    inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
  22 | +        READWRITE(tx); //TODO: Compress tx encoding

NicolasDorier commented at 8:08 AM on June 4, 2016:

If you intend to do it later, it's better removing it from the PR. Just for curiosity, if it is later included, the goal will be to use sendcmpct's version to decide the type of serialization of the transactions ?

TheBlueMatt commented at 7:46 AM on June 6, 2016:

Yes, use the version field in cmpctblock is the upgrade mechanism here.

sipa commented at 10:10 PM on June 12, 2016:

I'd rather say "// Future transaction compression standards could be implemented here" rather than TODO, as there is no actionable change you could make right now.

in src/main.cpp:None in e3820046f9 outdated

4841 | +        bool fAnnounceUsingCMPCTBLOCK = false;
4842 | +        uint64_t nCMPCTBLOCKVersion = 1;
4843 | +        vRecv >> fAnnounceUsingCMPCTBLOCK >> nCMPCTBLOCKVersion;
4844 | +        if (nCMPCTBLOCKVersion == 1) {
4845 | +            LOCK(cs_main);
4846 | +            State(pfrom->GetId())->fProvidesHeaderAndIDs = fAnnounceUsingCMPCTBLOCK;

NicolasDorier commented at 8:47 AM on June 4, 2016:

fAnnounceUsingCMPCTBLOCK is the way with which the remote node prefer to receive block notifications.

It gives no information about whether the remote node itself provide or not header and IDs. Imho it should be fixed to:

State(pfrom->GetId())->fProvidesHeaderAndIDs = pfrom->nVersion >= SHORT_IDS_BLOCKS_VERSION && pfrom->nServices & NODE_NETWORK;

Moved when we the node receive the VERSION message.

Because even if fAnnounceUsingCMPCTBLOCK is false (low bandwidth relaying case), the node still provide header and ids.

TheBlueMatt commented at 8:07 AM on June 6, 2016:

Yup, they were just inverted, fixed.

in src/main.cpp:None in e3820046f9 outdated

4911 | +                                    if (nodeid == pfrom->GetId())
4912 | +                                        fAlreadyAnnouncing = true;
4913 | +                                if (!fAlreadyAnnouncing) {
4914 | +                                    bool fAnnounceUsingCMPCTBLOCK = false;
4915 | +                                    uint64_t nCMPCTBLOCKVersion = 1;
4916 | +                                    if (lNodesAnnouncingHeaderAndIDs.size() >= 3) {

NicolasDorier commented at 12:56 PM on June 4, 2016:

nit: constant would be nice, 3 is reused on https://github.com/bitcoin/bitcoin/pull/8068/files#diff-7ec3c68a81efff79b6ca22ac1f1eabbaR5499

Actually I think that this whole code about unsubscribing from CMPCTBLOCK of other node and registering to this node is duplicated below.

in src/main.cpp:None in e3820046f9 outdated

5037 | +
5038 | +        BlockTransactions resp(req);
5039 | +        for (size_t i = 0; i < req.indexes.size(); i++) {
5040 | +            if (req.indexes[i] >= block.vtx.size()) {
5041 | +                Misbehaving(pfrom->GetId(), 100);
5042 | +                return error("Peer %d sent us a getblocktxn with out-of-bounds tx indicies", pfrom->id);

NicolasDorier commented at 2:32 PM on June 4, 2016:

typo: indicies

gmaxwell commented at 5:48 PM on June 4, 2016: contributor

@TheBlueMatt when you continue this you should probably continue from Pieter's rebase.

TheBlueMatt commented at 8:18 AM on June 6, 2016: member

Rebased on latest master (Pieter's is an insignificant change here, I'll just rebase when it gets merged), and addressed all the comments I saw above, though I didnt add cmpctblock status to getpeerinfo since its already there (in the form of message size info) and I dont want to be bikeshedded for getpeerinfo api....

Note for LogPrints in network processing, I tried to use the rule "LogPrint("net" in general, but LogPrintf( if you're gonna set a DoS score, since it always irritates me when I see nodes getting DoS scores and nothing to tell me why in debug.log.

TheBlueMatt force-pushed on Jun 6, 2016

sipa commented at 12:00 PM on June 6, 2016: member

From Travis:

EXCEPTION: St12out_of_range       
CInv::GetCommand(): type=4 unknown type       
bitcoin in ProcessMessages()

TheBlueMatt force-pushed on Jun 6, 2016

TheBlueMatt force-pushed on Jun 7, 2016

in src/main.cpp:None in 53012f994c outdated

 459 | @@ -432,6 +460,31 @@ void UpdateBlockAvailability(NodeId nodeid, const uint256 &hash) {
 460 |      }
 461 |  }
 462 |  
 463 | +void MaybeSetPeerAsAnnouncingHeaderAndIDs(const CNodeState* nodestate, CNode* pfrom) {
 464 | +    if (nodestate->fProvidesHeaderAndIDs) {
 465 | +        bool fAlreadyAnnouncing = false;
 466 | +        BOOST_FOREACH(const NodeId nodeid, lNodesAnnouncingHeaderAndIDs)
 467 | +            if (nodeid == pfrom->GetId())
 468 | +                fAlreadyAnnouncing = true;

NicolasDorier commented at 8:18 AM on June 8, 2016:

nit: You can early return here instead of using a boolean.

in src/main.cpp:None in 53012f994c outdated

5369 | +            // Dirty hack to process as if it were just a headers message
5370 | +            std::vector<CBlock> headers;
5371 | +            headers.push_back(cmpctblock.header);
5372 | +            CDataStream vHeadersMsg(SER_NETWORK, PROTOCOL_VERSION);
5373 | +            vHeadersMsg << headers;
5374 | +            return ProcessMessage(pfrom, NetMsgType::HEADERS, vHeadersMsg, nTimeReceived, chainparams);

NicolasDorier commented at 8:32 AM on June 8, 2016:

Are locks recursive ?

TheBlueMatt commented at 9:52 AM on June 8, 2016:

Yes. Otherwise we'd have ~infinity deadlocks.

in src/main.cpp:None in 53012f994c outdated

5383 | +        vRecv >> resp;
5384 | +
5385 | +        map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator it = mapBlocksInFlight.find(resp.blockhash);
5386 | +        if (it == mapBlocksInFlight.end() || !it->second.second->partialBlock ||
5387 | +                it->second.first != pfrom->GetId()) {
5388 | +            LogPrint("net", "Peer %d sent us block transactions for block we didn't requset", pfrom->id); //...or we timed out

NicolasDorier commented at 8:35 AM on June 8, 2016:

nit: typo rquset, also should add a space after '//'

in src/main.cpp:None in 53012f994c outdated

5406 | +            ProcessNewBlock(state, chainparams, pfrom, &block, false, NULL);
5407 | +            int nDoS;
5408 | +            if (state.IsInvalid(nDoS)) {
5409 | +                assert (state.GetRejectCode() < REJECT_INTERNAL); // Blocks are never rejected with internal reject codes
5410 | +                if (state.CorruptionPossible()) {
5411 | +                    // Its possible there was a collision we didnt detect...request the block

NicolasDorier commented at 9:11 AM on June 8, 2016:

nit: typo "didnt" and "Its"

NicolasDorier commented at 9:14 AM on June 8, 2016: contributor

Code Review ACK (except small nits about typo and one question about recursive lock, as you are calling ProcessMessage recursively)

I'll compile and test it myself. (my tests will be in C# though)

TheBlueMatt force-pushed on Jun 8, 2016

TheBlueMatt force-pushed on Jun 9, 2016

TheBlueMatt commented at 12:07 AM on June 9, 2016: member

Rebased. Had to throw in a fix for CheckBlockHeader requiring context instead of using ContextualCheckBlockHeader so that blockencodings.cpp was insane to fix a bug (though it still is...who's idea was it to have a flag in CBlock about a block being checked by a function in main?)

TheBlueMatt commented at 1:50 AM on June 9, 2016: member

To clarify: the bug was that the merkle root check would result in a DoS ban, but could happen due to conflicting short IDs. The solution was to check merkle root in blockencodings.cpp to keep all the "maybe-short-id-collision" checks in one place. In order to avoid checking the merkle tree twice (which is incredibly expensive), I had to call CheckBlock, which required three #includes (including main.h) to blockencodings.cpp, despite them being really unrelated.

TheBlueMatt force-pushed on Jun 9, 2016

in src/main.cpp:None in b351d55e39 outdated

5169 | @@ -5170,6 +5170,13 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
5170 |              return true;
5171 |          }
5172 |  
5173 | +        if (mapBlockIndex.find(headers[0].hashPrevBlock) == mapBlockIndex.end()) {
5174 | +            // Doesn't connect, instead of DoSing in AcceptBlockHeader, request deeper headers
5175 | +            if (!IsInitialBlockDownload())
5176 | +                pfrom->PushMessage(NetMsgType::GETHEADERS, chainActive.GetLocator(pindexBestHeader), uint256());

sdaftuar commented at 7:47 PM on June 9, 2016:

Won't this put us in an infinite loop if our peer has a broken implementation?

TheBlueMatt commented at 10:48 PM on June 9, 2016:

Yes, but do we care? I'm not sure how to fix this without adding a bunch more per-node state, but I'm sure there are other infinite loops somewhere in the protocol if people are broken in the right way.

sdaftuar commented at 1:31 AM on June 10, 2016:

Well my guess is that this isn't a theoretical problem, but an actual one -- I just started grepping the debug logs on one of my nodes, and I'm seeing roughly 1 message/day of the form "ERROR: AcceptBlockHeader: prev block not found". I didn't check in depth, but I believe that corresponds to the condition that the handling of getheaders messages is broken, which would mean the infinite loop behavior would be triggered.

Not obvious to me what the best solution is. We could add more per-node state, perhaps a single bool fBadHeadersImplementation that is set to false whenever a valid headers message is processed from a peer, and when processing a headers message that doesn't connect, set it to true and request more headers, unless it's already true, in which case we give up? But I haven't tried to implement so not sure how tricky this would be...

btcdrak commented at 6:37 PM on June 10, 2016:

Can't we just apply a small ban score each time?

TheBlueMatt commented at 6:54 PM on June 10, 2016:

Well the point of this was also to ensure that peers can enable us to do headers-sync without them needing to keep lots of state about where our blockchain is. The fact that headers messages /must/ connect seems rather insane to me from a protocol-design perspective (also because its not written that way in the BIP).

Within that context, the only state you could add to fix this is to try to track when a headers message was a response to a getheaders like the above, where we expect that it must connect or the peer is actually violating the spec.

sipa commented at 10:58 PM on June 12, 2016:

Is it necessary that we treat a non-connecting header as an inv? If the peer is not tracking any headers tree and just relaying headers, requesting anything from them won't do us any good anyway, and that seems to be the only use case for this?

TheBlueMatt commented at 11:47 PM on June 12, 2016:

The current code requires that you track the state of each of your peer's headers chain or risk getting DoS banned (which is not mentioned in the spec, and is something which we actually do not fully do currently without races - resulting in these prints appearing occasionally in debug.log). I'd say its a pretty non-trivial bug.

sipa commented at 11:49 PM on June 12, 2016:

Sorry if I'm not clear. I suggest changing it so that we don't DoS in that case, but also don't respond with a getheaders. Or rather, I'm wondering whether that suffices for your use case.

TheBlueMatt commented at 4:33 AM on June 13, 2016:

Differing philosophy, I guess...Indeed, this already isnt an issue for the CMPCTBLOCK handling, but I really don't like the idea that our peer might notify us that they have some blocks available and we will simply ignore them because they aren't keeping track of our chainstate. Can we use hashLastUnknownBlock to track if we hit the infinite-loop condition without adding additional state here?

sipa commented at 2:59 PM on June 13, 2016:

Thinking more about this, I think it is fine. Assuming the peer responds with a headers chain that indeed matches the locator we send, the same condition won't trigger again.

TheBlueMatt commented at 5:46 PM on June 13, 2016:

I believe that was exactly Suhas' concern - that a peer might respond to a headers request with a chain that was disconnected from our locator.

sdaftuar commented at 6:36 PM on June 14, 2016:

Yes, I just looked at the first example of "prev block not found" in the debug log of one my long-running listening nodes, and it's a peer that fails to send connecting headers on initial startup:

2016-05-30 12:50:07 Added connection to [redacted] peer=963241
2016-05-30 12:50:07 received: version (102 bytes) peer=963241
2016-05-30 12:50:07 send version message: version 70012, blocks=414057, us=0.0.0.0:8333, them=[redacted], peer=963241
2016-05-30 12:50:07 sending: version (102 bytes) peer=963241
2016-05-30 12:50:07 sending: verack (0 bytes) peer=963241
2016-05-30 12:50:07 receive version message: /[redacted subver I've never heard of before]/: version 70002, blocks=16863, us=[redacted], peer=963241, peeraddr=[redacted]
2016-05-30 12:50:07 sending: ping (8 bytes) peer=963241
2016-05-30 12:50:07 sending: addr (31 bytes) peer=963241
2016-05-30 12:50:07 initial getheaders (414056) to peer=963241 (startheight:16863)
2016-05-30 12:50:07 sending: getheaders (997 bytes) peer=963241
2016-05-30 12:50:07 sending: inv (37 bytes) peer=963241
2016-05-30 12:50:08 sending: inv (37 bytes) peer=963241
2016-05-30 12:50:08 received: verack (0 bytes) peer=963241
2016-05-30 12:50:08 received: getaddr (0 bytes) peer=963241
2016-05-30 12:50:08 received: ping (8 bytes) peer=963241
2016-05-30 12:50:08 sending: pong (8 bytes) peer=963241
2016-05-30 12:50:08 received: pong (8 bytes) peer=963241
2016-05-30 12:50:08 received: headers (162003 bytes) peer=963241
2016-05-30 12:50:08 ERROR: AcceptBlockHeader: prev block not found
2016-05-30 12:50:08 ProcessMessages(headers, 162003 bytes) FAILED peer=963241

Given that no new information was exchanged in the less than 2 seconds this interaction took, I think this would result in an infinite loop where my peer would send me ~160kb of data every 2 seconds...

JeremyRubin commented at 9:43 PM on June 9, 2016: contributor

Some thoughts on the overall design and implementation. I think points 1, 2, and 7 are the most immediate.

Can I suggest adding code to disable this mode when you have a max block size (and hence number of transactions) that makes the failure rate untenable? Or code that expands the number of bits used in the hash to keep mean-time-to-failure constant.
~~Perhaps having sendcmpct have more than two modes (perhaps a bytes worth) would be a good design choice for future expansion of more compact modes.~~ I missed the version number, should be sufficient.
I would also like to see some analysis of the benefit of siphash compared to truncated sha256 for this use case -- it's just performance, right? It may be good perhaps to have an option to fall back to this case.
I am also slightly skeptical of the need for a per individual salt. It may be sufficient to have a global salt that changes, say, every hour. This would result in less hashing of the mempool without much increase in adversarial ability as well as the ability to precompute the short ids. Although siphash seems to be cheap so perhaps this is overkill, but reducing the latency at time of receipt is a worthwhile goal maybe. Perhaps a good waypoint is to pre-receive a nonce from all peers and upon getting an inv in low bandwidth mode, one begins hashing the mempool.
On BlockTransactionsRequest, (if and only if it is common to be missing a lot of transactions) I would advise a bitfield which indicates more than half missing and then "inverts" the differential encoding. This keeps the cost of sending slightly smaller when many are missing.
Prefilledtxn should, I believe, be delivered as a separate struct to HeaderAndShortIDs. This allows for processing to begin while potentially a lot of data is delivered.
If node B receives from A a block and requests transactions {1,2,3}, then B should relay to node C in prefilledtxn {1,2,3} as well as C is likely to not have those txns.

gmaxwell commented at 11:10 PM on June 9, 2016: contributor

Can I suggest adding code to disable this mode when you have a max block size (and hence number of transactions) that makes the failure rate untenable? Or code that expands the number of bits used in the hash to keep mean-time-to-failure constant.

This is already designed targeting several times the maximum size permitted in the protocol. Also the size of the block does not weigh that strongly in the result (mempool size dominates), and the implementation deals fairly gracefully with small numbers of collisions.

Perhaps having sendcmpct have more than two modes (perhaps a bytes worth) would be a good design choice for future expansion of more compact modes.

The protocol is versioned, any change would need to be a new version, so I don't see what extra states would do there.

I would also like to see some analysis of the benefit of siphash compared to truncated sha256 for this use case

It's 27 times faster in a performance important path. Siphash was an upgrade from using an even simpler function previously.

I am also slightly skeptical of the need for a per individual salt. It may be sufficient to have a global salt that changes, say, every hour. This would result in less hashing of the mempool without much increase in adversarial ability as well as the ability to precompute the short ids. Although siphash seems to be cheap so perhaps this is overkill, but reducing the latency at time of receipt is a worthwhile goal maybe. Perhaps a good waypoint is to pre-receive a nonce from all peers and upon getting an inv in low bandwidth mode, one begins hashing the mempool.

A global salt would provide absolutely no protection against the collision attack. The value must be unpredictable to an attacker and cannot be precomputed. There should be no total reduction in hashing the mempool- it's just once per received block. Avoiding latency is important but time taken for siphash a maxed out mempool on a single 3GHz core is 0.17ms, this is insubstantial compared to the rest of block processing.

On BlockTransactionsRequest, (if and only if it is common to be missing a lot of transactions) I would advise a bitfield which indicates more than half missing and then "inverts" the differential encoding. This keeps the cost of sending slightly smaller when many are missing.

I originally implemented that, in fact. But low hitrates are unobservably rare after the initial start... spending a byte to signal it is a net loss.. plus the code is more complex. It's also the case that low hitrate data is naturally smaller because all the differences will be very small.

Prefilledtxn should, I believe, be delivered as a separate struct to HeaderAndShortIDs. This allows for processing to begin while potentially a lot of data is delivered.

That is an interesting point however, the coinbase txn is always required; so doing exactly that would not improve anything.

Ignoring the coinbase implementation would be rather complex: ... if you complete the decode and the prefilled haven't arrived yet, do you wait? how long? or do you just gettxn potentially redundantly with the transactions in flight? if you wait and time out do you ban the peer when it doesn't respond or? Basically when thinking about implementation complexity you should think about the complexity being exponential with the number of communication states you might have with a peer. :)

If node B receives from A a block and requests transactions {1,2,3}, then B should relay to node C in prefilledtxn {1,2,3} as well as C is likely to not have those txns.

I've tested this and it works great. The recommendations in BIP152 were based precisely on doing this. It's not included in this PR to minimize the scope as it doesn't change the protocol and can be added any point. (there are further refinements you can do, like leaving out txn that a target peer has INVed to you, even if you didn't know them)

in src/blockencodings.h:None in 27d56369d5 outdated

 100 | +
 101 | +    ADD_SERIALIZE_METHODS;
 102 | +
 103 | +    template <typename Stream, typename Operation>
 104 | +    inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
 105 | +        uint64_t idx = index;

instagibbs commented at 2:14 PM on June 10, 2016:

What is the reasoning for uint16 here? Local space savings? ( I know this practically isn't a big deal due to realistic near future blocksizes but still)

TheBlueMatt commented at 6:49 PM on June 10, 2016:

Dunno, easier to be careful about using the "right" types so that any assumptions you might make later about range of a value dont blow up in your face...probably no real reason for this, but...it just is

in src/blockencodings.cpp:None in c270f63c31 outdated

  80 | +    for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
  81 | +        while (txn_available[i + index_offset])
  82 | +            index_offset++;
  83 | +        shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
  84 | +    }
  85 | +    if (shorttxids.size() != cmpctblock.shorttxids.size())

gmaxwell commented at 6:43 PM on June 10, 2016:

Though it doesn't have to be done now, it would be good to simply mark both txn that collide in the compact block as missing instead of immediately falling back. I've been testing in this way, and finding that even with 16-bit short IDs a super-majority of blocks are successfully reconstructed with only a relatively small number of gettxn.

TheBlueMatt commented at 6:55 PM on June 10, 2016:

Added a //TODO note so that someone who goes through and cleans up all the optimizations later can track them.

TheBlueMatt force-pushed on Jun 10, 2016

JeremyRubin commented at 1:48 AM on June 11, 2016: contributor

This is already designed targeting several times the maximum size permitted in the protocol. Also the size of the block does not weigh that strongly in the result (mempool size dominates), and the implementation deals fairly gracefully with small numbers of collisions.

Yes, mempool size should dominate. This seems like a completely-other issue. Mining nodes who keep large mempools will run into large collision frequencies and this will be less useful.

This is furthermore troubling because the size used in the bip (m=100000 txns or m*225 bytes not including overhead) is around 22 megabytes whereas the defaults in policy.h seems to be 300 mb of mempool, unless I'm mistaken. Adding a factor of 10 txns to m puts the bits above 48. 56 bits allows for up to 20 gigabytes or so, which seems more appropriate. Although it may make the most sense to have peers communicate to each other how full their mempools are and set hash length based on that.

The protocol is versioned, any change would need to be a new version, so I don't see what extra states would do there.

👍 yup I struck that one out before you replied :)

It's 27 times faster in a performance important path. Siphash was an upgrade from using an even simpler function previously.

A global salt would provide absolutely no protection against the collision attack. The value must be unpredictable to an attacker and cannot be precomputed. There should be no total reduction in hashing the mempool- it's just once per received block. Avoiding latency is important but time taken for siphash a maxed out mempool on a single 3GHz core is 0.17ms, this is insubstantial compared to the rest of block processing.

I'd like to see more of a threat model on this. What's the attack? An attacker makes a block that they mined slow to propagate? Why would they do that, and not just withhold the block? An attacker broadcasts transactions to be included which would cause a lot of conflicts into the networks mempool on every block? This is expensive to do. Overall, I don't think there is any real security concern with making the nonce be deterministically based on the previous block.

Let's say we pick a more difficult hash to compute, but make it possible to compute before receiving the block this minimizes the hash-grinding concern, right? But this also still makes it possible to precompute the table which removes the 0.17 ms latency in the hot path. If the goal is < 10ms validation of a block, then 0.17 is not nothing if it can be shaved off. (Furthermore, currently the code re-hashes on a per-peer basis rather than implementing the BIP implementation note 6, which would be a bit better)

I originally implemented that, in fact. But low hitrates are unobservably rare after the initial start... spending a byte to signal it is a net loss.. plus the code is more complex. It's also the case that low hitrate data is naturally smaller because all the differences will be very small.

👍

That is an interesting point however, the coinbase txn is always required; so doing exactly that would not improve anything. Ignoring the coinbase implementation would be rather complex: ... if you complete the decode and the prefilled haven't arrived yet, do you wait? how long? or do you just gettxn potentially redundantly with the transactions in flight? if you wait and time out do you ban the peer when it doesn't respond or? Basically when thinking about implementation complexity you should think about the complexity being exponential with the number of communication states you might have with a peer. :)

Well coinbase txn could always be included outside of the prefilled separate block. I actually like that as a design anyways -- perhaps there should be a difference between txns we KNOW to not be in their mempool and ones we EXPECT to not be in the mempool. At the cost of an extra length field, perhaps not worth it, but if it is just the coinbase (not needing length) perhaps it is worth it.

I've tested this and it works great. The recommendations in BIP152 were based precisely on doing this. It's not included in this PR to minimize the scope as it doesn't change the protocol and can be added any point. (there are further refinements you can do, like leaving out txn that a target peer has INVed to you, even if you didn't know them)

👍

I don't see these recommendations specifically in the BIP, but I support adding this later.

gmaxwell commented at 4:52 AM on June 11, 2016: contributor

This seems like a completely-other issue. Mining nodes who keep large mempools will run into large collision frequencies and this will be less useful.

This isn't the case. The numbers here are sized for their targets assuming a mempool roughly 10 times what we see with the current maximum. There is little reason to run with multiple days worth of mempool in any case (transactions will expire after 72 hours).

When reaching that figure the result isn't a "large collision frequency", it is a per-link failure rate of 1/281474. Even if many links fail, the block will still propagate quickly through the network.

It's also the case that one can simply look only at the top N of the mempool (which is overwhelmingly more likely to get mined) to achieve whatever effect one wants.

This is furthermore troubling because the size used in the bip (m=100000 txns or m*225 bytes not including overhead) is around 22 megabytes whereas the defaults in policy.h seems to be 300 mb of mempool, unless I'm mistaken.

You are mistaken.

$ ./bitcoin-cli getmempoolinfo { "size": 13297, "bytes": 160454650, "usage": 295521312, "maxmempool": 300000000, "mempoolminfee": 0.00001420 }

So at the moment a full mempool is ~13499 transactions. (I was actually surprised at how high that was, but I remember now that we just increased the efficiency, in 0.12 it's more like 9800 txn IIRC).

Your 225 is more like the median txn size than the mean, and the limit is based on memory usage not the size of the compactly serialized transaction-- they're bigger in memory due to a multitude of overheads.

Although it may make the most sense to have peers communicate to each other how full their mempools are and set hash length based on that.

If there is a need for more or more flexible IDs in the future, the protocol is extensible for that reason.

Doubly so here, since one can use only as much of the node's feerate (thus probability) sorted mempool as makes sense for them to use.

My experience is that lots of bells and whistles ahead of time end up just being implementation complexity that goes unused 99.9% of the time. Testing complexity also grows exponentially with the amount of options.

I'd like to see more of a threat model on this. What's the attack?

This is described in the BIP: "Collision resistance It should be hard for network participants to create transactions that cause collisions. If an attacker were able to cause such collisions, filling mempools (and, thus, blocks) with them would cause poor network propagation of new (or non-attacker, in the case of a miner) blocks."

If the IDs are not salted you can trivially compute colliding sets of transactions and send them to the network, making compact block transmission always fail. A miner doesn't need to do this, anyone can. (though a miner could perhaps profitability avoid it by intentionally avoiding mining those booby-trap transactions-- but profit is irrelevant for trivial vandalism anyone can do).

But this also still makes it possible to precompute the table which removes the 0.17 ms latency in the hot path. If the goal is < 10ms validation of a block, then 0.17 is not nothing if it can be shaved off.

Most of the time all the solutions are found in the first two megabytes of the mempool, so if it terminates early the 0.17ms wouldn't be there either. Removing the salting would require increasing the IDs to 16 bytes or so to eliminate this kind of shenanigans. Adding many packets and tens of kilobytes of transmission costs a lot more than 0.17ms on most links.

Let's say we pick a more difficult hash to compute, but make it possible to compute before receiving the block this minimizes the hash-grinding concern, right?

There is no guaranteed "minimum time between blocks" during which you can do this computation, and slowing the hash function down gives only a linear slowdown for the attacker. If X is attackable, X*10 is likely attackable too.

currently the code re-hashes on a per-peer basis

This is on the sending side, which means it is only running over the transactions in a block, 0.17ms was for a full mempool (receiver size).

perhaps there should be a difference between txns we KNOW to not be in their mempool

We never "KNOW"-- not physically possible. If we want to be particular about it, they could have the txn already but the light cone from that event may not have reached us by the time we transmit.

At the cost of an extra length field, perhaps not worth it, but if it is just the coinbase

The cost of a length field would be irrelevant (from a size perspective-- it's 16 bytes of Bitcoin protocol overhead plus 40 bytes of TCP/IP overhead are much worse then the length). But the size cost isn't my concern... the cost that I think matters is that a message would be received without actually having enough data to fully act on it but while not being an immediate error condition, requiring another state in the state machine. "I have the first part of a compact block, but not the rest"-- along with the mess of additional corner cases and error handling involving that extra state. Otherwise I'd totally support this.

Especially when you consider that the hope is to revise this over time with improved protocols (this design is a long way from the most efficient we know how to design) there is a good reason to not put in a lot of doodads and options, as they just turn into extra technical debt in older versions which are carried around for compatibility. We don't need to design for forever here. I would have even left out high-bandwidth mode and the ability to have predicted transactions, but those were minimums required to get rid of any need to have a separate fast block relay network protocol.

sipa commented at 1:17 PM on June 11, 2016: member

@JeremyRubin @gmaxwell The number 0.17ms you're citing is not actually relevant in this discussion.

For the receiver, the reconstruction time is likely dominated by iterating over the mempool (the memory accesses needed per mempool entry are way slower than the SipHash calculation), so being able to use a preconstructred mempool index with shortids would likely very significantly reduce it. Unfortunately, indeed, to make collision attacks infeasible in that case, we'd likely need ~16-byte short ids.

If the reconstruction time ever becomes significant enough to optimize, the low hanging fruit is creating a continuous in-memory block with all mempool txids, perhaps subdivided in a few tiers (sorted by feerate).

in src/blockencodings.cpp:None in c63626aeae outdated

  69 | +            // If we are inserting a tx at an index greater than our full list of shorttxids
  70 | +            // plus the number of prefilled txn we've inserted, then we have txn for which we
  71 | +            // have neither a prefilled txn or a shorttxid!
  72 | +            return READ_STATUS_INVALID;
  73 | +        }
  74 | +        txn_available[lastprefilledindex] = std::shared_ptr<const CTransaction>(new CTransaction(cmpctblock.prefilledtxn[i].tx));

sipa commented at 10:04 PM on June 12, 2016:

Using std::make_shared(cmpctblock.prefilledtxn[i].tx) is slightly more efficient, as it allocates the reference counter and the CTransaction in a single malloc, while the normal std::shared_ptr constructor needs two separate ones.

in src/main.cpp:None in 20ec1a307a outdated

4517 | @@ -4512,6 +4518,15 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam
4518 |                          // else
4519 |                              // no response
4520 |                      }
4521 | +                    else if (inv.type == MSG_CMPCT_BLOCK)
4522 | +                    {
4523 | +                        // Note that while we will respond to all MSG_CMPCT_BLOCK requests here,

sipa commented at 11:11 PM on June 12, 2016:

What is the reason for this? I think we should check early and dosban peers who getdata a CMPCT_BLOCK that was not recently inved.

TheBlueMatt commented at 2:53 AM on June 13, 2016:

There is no DoS score involved in a request for which we did not send an inv (ie something which is buried in our chain), only for those which request something with !BLOCK_HAVE_DATA. For those, we definitely wont even send a CMPCTBLOCK, because its covered by the surrounding if statement.

As for not sending the compact block if the block is >= 10 deep, yes, I can add an if statement and simply not respond to the getdata for those.

gmaxwell commented at 11:15 PM on June 12, 2016: contributor

ACK (+/- various in-flight nits). Beyond reviewing the spec and code, I've had a network of hosts running this (and earlier versions) for over a month with good results, public testing looks good, and and four the last week I've had a network running a modified version with 16-bit IDs to test all the collision corner cases. That network has reliably stayed in sync (except for one bug I encountered which is fixed here).

There is room for further improvement, including prediction, using the orphan map in recovery, better interaction with fetching logic (e.g. in initial block download case); but those can and should be in other PRs done at other times. Should some problem show up in this in the future it's versioned and negotiated, so it could simply be turned off.

in src/main.cpp:None in 20ec1a307a outdated

5861 | @@ -5802,7 +5862,9 @@ bool SendMessages(CNode* pto)
5862 |              // add all to the inv queue.
5863 |              LOCK(pto->cs_inventory);
5864 |              vector<CBlock> vHeaders;
5865 | -            bool fRevertToInv = (!state.fPreferHeaders || pto->vBlockHashesToAnnounce.size() > MAX_BLOCKS_TO_ANNOUNCE);
5866 | +            bool fRevertToInv = ((!state.fPreferHeaders &&
5867 | +                                 (!state.fPreferHeaderAndIDs || pto->vBlockHashesToAnnounce.size() > 1)) ||

sipa commented at 11:28 PM on June 12, 2016:

I don't think this test should be here. The block below (that builds vHeaders) can skip things from vBlockHashesToAnnounce.

TheBlueMatt commented at 4:24 AM on June 13, 2016:

I don't immediately see how to resolve this in the way you're suggesting. Because I want to share the code in the first if (!fRevertToInv) block I need to change the definition of fRevertToInv (or the condition for that block) slightly.

sipa commented at 3:22 PM on June 13, 2016:

I mean like here: https://github.com/sipa/bitcoin/commit/526a02c114a5f34fef053d3550438ebb9e741b42

sipa commented at 4:39 PM on June 14, 2016:

Ping? I think the code I linked above is simpler and easier to read.

TheBlueMatt commented at 7:42 PM on June 14, 2016:

This requires fPreferHeaders in order for fPreferHeaderAndIDs to work, which I was deliberately trying to avoid.

in src/main.cpp:None in 20ec1a307a outdated

5915 | @@ -5854,6 +5916,33 @@ bool SendMessages(CNode* pto)
5916 |                      }
5917 |                  }
5918 |              }
5919 | +            if (!fRevertToInv && !vHeaders.empty()) {

sipa commented at 11:29 PM on June 12, 2016:

... continued. This if block could be replaced by the if inside of it, and making it reset vHeaders. No code movement for the normal headers inv is necessary in that case.

TheBlueMatt commented at 4:25 AM on June 13, 2016:

I think this may be possible by bending over backwards to change fRevertToInv in the right way between the !fRevertToInv and fRevertToInv conditionals, but I think that just makes the already hard-to-read code even worse, which is not worth saving a tiny bit of code movement to me.

in src/main.cpp:None in 1340078929 outdated

 197 | @@ -197,8 +198,9 @@ namespace {
 198 |      /** Blocks that are in flight, and that are in the queue to be downloaded. Protected by cs_main. */
 199 |      struct QueuedBlock {
 200 |          uint256 hash;
 201 | -        CBlockIndex* pindex;     //!< Optional.
 202 | -        bool fValidatedHeaders;  //!< Whether this block has validated headers at the time of request.
 203 | +        CBlockIndex* pindex;                                     //!< Optional.
 204 | +        bool fValidatedHeaders;                                  //!< Whether this block has validated headers at the time of request.
 205 | +        std::unique_ptr<PartiallyDownloadedBlock> partialBlock;  //!< Optional, used for COMPRBLOCK downloads

sipa commented at 11:33 PM on June 12, 2016:

s/COMPRBLOCK/CMPCTBLOCK/

in src/main.cpp:None in 1340078929 outdated

 396 | +void MarkBlockAsInFlight(NodeId nodeid, const uint256& hash, const Consensus::Params& consensusParams, CBlockIndex *pindex = NULL, list<QueuedBlock>::iterator **pit = NULL) {
 397 |      CNodeState *state = State(nodeid);
 398 |      assert(state != NULL);
 399 |  
 400 | +    // Short-circuit most stuff in case its from the same node
 401 | +    map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator itInFlight = mapBlocksInFlight.find(hash);

sipa commented at 11:46 PM on June 12, 2016:

An auto type may be worth it here.

TheBlueMatt commented at 11:53 PM on June 12, 2016:

I tend to prefer not auto-typing when I'm gonna actually use some part of the type (ie I'd like to ensure there be a compiler error if I'm accessing a variable and it changes type).

in src/main.cpp:None in 1340078929 outdated

 388 | @@ -387,25 +389,42 @@ bool MarkBlockAsReceived(const uint256& hash) {
 389 |  }
 390 |  
 391 |  // Requires cs_main.
 392 | -void MarkBlockAsInFlight(NodeId nodeid, const uint256& hash, const Consensus::Params& consensusParams, CBlockIndex *pindex = NULL) {
 393 | +// When pit is set it is assumed a PartiallyDownloadedBlock will be used
 394 | +// pit is only set if a new PartiallyDownloadedBlock was created
 395 | +// pit will only be valid as long as the same cs_main lock is being held

sipa commented at 11:52 PM on June 12, 2016:

That's pretty unintuitive behaviour, and I don't think it's necessary to put that much decision logic in this function. I think it could just return a QueuedBlock* always, and then the caller can then insert a new partialBlock if needed.

in src/main.cpp:None in 1340078929 outdated

5355 | +            return true;
5356 | +        }
5357 | +
5358 | +        PartiallyDownloadedBlock& partialBlock = *it->second.second->partialBlock;
5359 | +        CBlock block;
5360 | +        ReadStatus status = partialBlock.FillBlock(block, resp.txn);

sipa commented at 12:24 AM on June 13, 2016:

Perhaps this part can be factored out into a separate function, that can be called from the codepath for CMPCTBLOCKs that don't have any missing txn?

TheBlueMatt commented at 3:11 AM on June 13, 2016:

For now I swapped in the same call-headers-msg code from CMPCTBLOCK handling into the CMPCTBLOCK code call ::BLOCKTXN handling. Its a dirty hack to serialize and then immediately deserialize a message, but its a short message so it doesnt cost much, and I'm assuming the network stack will be (properly) rewritten soonish anyway, so then it can be called like the individual function it should be.

TheBlueMatt force-pushed on Jun 13, 2016

TheBlueMatt commented at 4:41 AM on June 13, 2016: member

I believe I either responded to all code comments or fixed them.

Also added a few commits to optimize PartiallyDownloadedBlock::InitData. Just iterating over the mempool costs quite a bit of CPU time, which would near being a DoS-issue if it werent for the fact that you have to do a disconnect/reconnect cycle to trigger the code again. By limiting its worst-case runtime in the case that someone significantly increases their mempool size and priming the memory access a bit, its mostly fine, though further changes may be required for the UDP code based on this stuff.

in src/blockencodings.cpp:None in 39298a29b6 outdated

  86 | +    // Calculate map of txids -> positions and check mempool to see what we have (or dont)
  87 | +    // TODO: Instead of using a simple XOR for hashing here, we could just
  88 | +    // limit the number of elements per bucket. Because well-formed cmpctblock
  89 | +    // messages will have a (relatively) uniform distribution of short IDs, any
  90 | +    // highly-uneven distribution of elements can be safely treated as a read failure.
  91 | +    std::unordered_map<uint64_t, uint16_t, SixtyFourBitHasher> shorttxids;

sipa commented at 2:55 PM on June 13, 2016:

I don't think the xor helps at all. Groups of short ids that were close together (and thus had a high chance of ending up in the same bucket) remain close together.

TheBlueMatt commented at 5:43 PM on June 13, 2016:

LOL, I must've been really tired when I thought that one through....anyway, I'll do the bucket-count thing.

sipa commented at 9:12 PM on June 13, 2016:

What would work is multiplying by a random odd 64-bit integer, but I agree - bucket counting sounds better. You could do a chi-square test.

in src/blockencodings.cpp:None in 39298a29b6 outdated

  32 | +void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const {
  33 | +    CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
  34 | +    stream << header;
  35 | +    CSHA256 hasher;
  36 | +    hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
  37 | +    uint64_t nonce_e = htole64(nonce); // Serialization makes everything host-endian, but we want LE

sipa commented at 3:00 PM on June 13, 2016:

A better suggestion than what I said before: just replace this whole block with stream << header << nonce.

TheBlueMatt commented at 5:43 PM on June 13, 2016:

Heh, good point.

in src/main.cpp:None in 39298a29b6 outdated

3396 | @@ -3356,6 +3397,10 @@ bool ContextualCheckBlockHeader(const CBlockHeader& block, CValidationState& sta
3397 |      if (block.GetBlockTime() <= pindexPrev->GetMedianTimePast())
3398 |          return state.Invalid(false, REJECT_INVALID, "time-too-old", "block's timestamp is too early");
3399 |  
3400 | +    // Check timestamp

sipa commented at 3:06 PM on June 13, 2016:

Why is this moved?

TheBlueMatt commented at 5:46 PM on June 13, 2016:

To prevent yet more includes and the crazy-looking GetAdjustedTime call from within the GetBlock stuff. See #8068 (comment)

sipa commented at 9:08 PM on June 13, 2016:

Fair enough.

JeremyRubin commented at 3:21 PM on June 13, 2016: contributor

@sipa thanks for the clarification.

instagibbs commented at 5:10 PM on June 13, 2016: member

slightly tested ACK

I've been running versions of this for smoothly about a month and compiling stats/graphing the results.

in src/blockencodings.h:None in 39298a29b6 outdated

  25 | +    }
  26 | +};
  27 | +
  28 | +struct BlockTransactionsRequest {
  29 | +    uint256 blockhash;
  30 | +    std::vector<uint32_t> indexes;

NicolasDorier commented at 9:12 PM on June 13, 2016:

nit of some incoherences:

ushort were used in PrefilledTransaction to represent an index but here it is uint.
PrefilledTransaction->index represent a differential index, but BlockTransactionsRequest->indexes represent absolute indexes (because the translation from diff to absolute is done during seria/deseria)

TheBlueMatt force-pushed on Jun 13, 2016

in src/blockencodings.h:None in 39298a29b6 outdated

  41 | +            while (indexes.size() < indexes_size) {
  42 | +                indexes.resize(std::min((uint64_t)(1000 + indexes.size()), indexes_size));
  43 | +                for (; i < indexes.size(); i++) {
  44 | +                    uint64_t index = 0;
  45 | +                    READWRITE(COMPACTSIZE(index));
  46 | +                    indexes[i] = index;

NicolasDorier commented at 9:29 PM on June 13, 2016:

maybe should check

if(index > std::numeric_limits<uint32_t>::max())
                    throw std::ios_base::failure("indexes overflowed 32-bits");

TheBlueMatt force-pushed on Jun 13, 2016

TheBlueMatt force-pushed on Jun 14, 2016

TheBlueMatt commented at 12:14 AM on June 14, 2016: member

The travis failure seems to be a travis issue, not a real failure

btcdrak commented at 9:19 AM on June 14, 2016: contributor

@TheBlueMatt Travis passed now.

NicolasDorier commented at 3:43 PM on June 14, 2016: contributor

@TheBlueMatt can you consider to cherry pick https://github.com/NicolasDorier/bitcoin/commit/5a156ebc6f402f60c2e5faa880e3cdc2c6bb5b32 ?

PrefilledTransaction.index becomes an absolute index instead of a differential one. Differential index should only be used on wire.

in src/blockencodings.cpp:None in da8ae90dc1 outdated

  86 |          while (txn_available[i + index_offset])
  87 |              index_offset++;
  88 |          shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
  89 | +        // The math for a max bucket size of 10 is rather complicated, but simulation
  90 | +        // shows that, for blocks of up to 10k transactions, any individual bucket having
  91 | +        // more than 10 entries is highly unlikely.

sipa commented at 5:47 PM on June 14, 2016:

How accurate was your simulation? If I approximate the chance as buckets*P[binomial(n,1.0/buckets)], where n<=buckets (due to max_load_factor=1.0 by default for unordered_map), this would randomly fail about once every 9000 transmissions for n=10000 buckets=10000.

According to this approximation, if we want the random failure chance to be less than once in a billion, you need:

> 10 for up to 13 transactions
> 11 for up to 23 transactions
> 12 for up to 56 transactions
> 13 for up to 291 transactions
> 14 for up to 3423 transactions
> 15 for up to 53645 transactions
> 16 for up to 913429 transactions

in src/blockencodings.cpp:None in a4a2c32aa5 outdated

  63 | +            return READ_STATUS_INVALID;
  64 | +
  65 | +        lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1;
  66 | +        if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
  67 | +            return READ_STATUS_INVALID;
  68 | +        if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i + 1) {

sdaftuar commented at 1:11 AM on June 16, 2016:

I think there's an off by one here. If shorttxids.size() == 0, and prefilledtxn.size() == 1, then sending a compact block with prefilledtxn[0].index = 1 would pass this check, but cause an out-of-bounds memory access below.

in src/blockencodings.cpp:None in a4a2c32aa5 outdated

  61 | +    for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
  62 | +        if (cmpctblock.prefilledtxn[i].tx.IsNull())
  63 | +            return READ_STATUS_INVALID;
  64 | +
  65 | +        lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1;
  66 | +        if (lastprefilledindex > std::numeric_limits<uint16_t>::max())

sdaftuar commented at 1:16 AM on June 16, 2016:

comment nit: i was convinced there were all kinds of potential for overflows until I found the sanity check on the prefilledtxn index values that is done in deserialization (which also explained why you have this uint16_t max check, which was inexplicable from looking at the surrounding code). Adding a short comment explaining the logic would be helpful to future code readers.

in src/blockencodings.cpp:None in a4a2c32aa5 outdated

  53 | +    if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_SIZE / MIN_TRANSACTION_SIZE)
  54 | +        return READ_STATUS_INVALID;
  55 | +
  56 | +    assert(header.IsNull() && txn_available.empty());
  57 | +    header = cmpctblock.header;
  58 | +    txn_available.resize(cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size());

sdaftuar commented at 1:16 AM on June 16, 2016:

nit: this could be shortened using cmpctblock.BlockTxCount()

in src/blockencodings.cpp:None in a4a2c32aa5 outdated

  94 | +    // TODO: in the shortid-collision case, we should instead request both transactions
  95 | +    // which collided. Falling back to full-block-request here is overkill.
  96 | +    if (shorttxids.size() != cmpctblock.shorttxids.size())
  97 | +        return READ_STATUS_FAILED; // Short ID collision
  98 | +
  99 | +    char have_txn[txn_available.size() / 8 + 1];

sdaftuar commented at 1:23 AM on June 16, 2016:

Agree with @sipa about making this a vector<bool>!

TheBlueMatt commented at 8:00 PM on June 16, 2016:

I really dont like doing a malloc() for such a small buffer :/

sipa commented at 8:03 PM on June 16, 2016:

You're already doing a malloc for each shortid in the unordered_map above.

TheBlueMatt commented at 8:30 PM on June 16, 2016:

True, but I didnt want to implement my own unordered_map...a vector<bool> is easy :p

in src/main.cpp:None in a4a2c32aa5 outdated

5296 | +            }
5297 | +        }
5298 | +
5299 | +        // If AcceptBlockHeader returned true, it set pindex
5300 | +        assert(pindex);
5301 | +        if (pindex->nStatus & BLOCK_HAVE_DATA)

sdaftuar commented at 2:02 AM on June 16, 2016:

I think HAVE_DATA is the wrong check if we are a pruning node. We should do if (pindex->nTx > 0) instead.

On further thought, pindex->nTx > 0 isn't right either, if there are any scenarios where a pruning node might re-request (via cmpctblock) a previously validated block in order to reorg to the chain that block is on. I think elsewhere in the code, we catch this case by checking to see if the block is requested, and rely on the download logic being smart enough to not request useless blocks.

sipa commented at 4:07 PM on June 17, 2016:

If BLOCK_HAVE_DATA is set, there is no need to process the CMPCTBLOCK, regardless of pruning, no?

in src/main.cpp:None in a4a2c32aa5 outdated

5306 | +        // If we're not close to tip yet, give up and let parallel block fetch work its magic
5307 | +        if (!CanDirectFetch(chainparams.GetConsensus()))
5308 | +            return true;
5309 | +
5310 | +        CNodeState *nodestate = State(pfrom->GetId());
5311 | +        if (pindex->pprev->nStatus & BLOCK_HAVE_DATA) {

sdaftuar commented at 2:12 AM on June 16, 2016:

Again, here we should instead check if pindex->pprev->nTx > 0, so that this will work in the pruning case (it probably doesn't actually matter much in this specific case, but I think it's better to not use HAVE_DATA to minimize future errors).

Also, I think before we try to work on reconstructing the block and potentially requesting it, we should have a check that either we requested this CMPCTBLOCK, or that the header is valid and has more work than our tip. Otherwise I believe we'd be vulnerable to a fill-up-your-disk attack.

sdaftuar commented at 2:27 AM on June 17, 2016:

Further thought: just drop this condition, and always process the CMPCTBLOCK. We don't need the parents of this block to have arrived to correctly reconstruct and process the CMPCTBLOCK (just like we are able to process full blocks out of order). This fixes the sync bug that is popping up in the RPC tests.

Then you can also get rid of the code in the else{} down below, where you invoke the HEADERS processing.

However, we should reuse the direct fetch logic that is implemented in the headers processing, so that if we are receiving a CMPCTBLOCK that is the tip of a reorg, and we're missing some intermediate block (for which we have headers, of course, or else this announcement would be dropped), then we should go back and request those intermediate blocks.

sipa commented at 4:20 PM on June 17, 2016:

Agree, just drop this condition. We can deal with discontinuous blocks just fine (maybe we should check that we're not too far ahead of the main chain, though EDIT: CanDirectFetch already does that).
I agree we also need direct fetching logic in response to CMPCTBLOCK, but it's less needed than for HEADERS, as CMPCTBLOCK are usually just sent as a single tip. Also, I really want that direct fetching logic to be factored out into a separate function first, which can be used for both responding to INV, HEADERS and CMPCTBLOCK.

in src/main.cpp:None in a4a2c32aa5 outdated

5327 | +                PartiallyDownloadedBlock& partialBlock = *(*queuedBlockIt)->partialBlock;
5328 | +                ReadStatus status = partialBlock.InitData(cmpctblock);
5329 | +                if (status == READ_STATUS_INVALID) {
5330 | +                    Misbehaving(pfrom->GetId(), 100);
5331 | +                    LogPrintf("Peer %d sent us invalid compact block", pfrom->id);
5332 | +                    return true;

sdaftuar commented at 2:29 AM on June 16, 2016:

We should clear the block as no longer being in flight. Otherwise we're relying on the Misbehaving() to cause a disconnect, which would eventually clear the state -- but this seems error prone, eg if the node happens to be whitelisted.

laanwj added the label Feature on Jun 16, 2016

NicolasDorier commented at 7:53 PM on June 16, 2016: contributor

Reply getdata MSG_CMPCT_BLOCK to MSG_BLOCK inv : https://github.com/NicolasDorier/bitcoin/commit/83cc735bfa803e1e7eee02e458127e8d94c24534

TheBlueMatt force-pushed on Jun 16, 2016

in src/txmempool.cpp:None in 52783001e3 outdated

 449 | @@ -447,6 +450,15 @@ void CTxMemPool::removeUnchecked(txiter it)
 450 |      BOOST_FOREACH(const CTxIn& txin, it->GetTx().vin)
 451 |          mapNextTx.erase(txin.prevout);
 452 |  
 453 | +    if (vTxHashes.size() > 1) {
 454 | +        vTxHashes[it->vTxHashesIdx] = vTxHashes[vTxHashes.size() - 1];

sipa commented at 11:00 PM on June 16, 2016:

Use vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes[vTxHashes.size() - 1]) or std::swap(vTxHashes[it->vTxHashesIdx], vTxHashes[vTxHashes.size() - 1]) to avoid needing std::shared_ptr copy (which needs an atomic operation to increment the refcount).

in src/txmempool.cpp:None in 52783001e3 outdated

 449 | @@ -447,6 +450,15 @@ void CTxMemPool::removeUnchecked(txiter it)
 450 |      BOOST_FOREACH(const CTxIn& txin, it->GetTx().vin)
 451 |          mapNextTx.erase(txin.prevout);
 452 |  
 453 | +    if (vTxHashes.size() > 1) {
 454 | +        vTxHashes[it->vTxHashesIdx] = vTxHashes[vTxHashes.size() - 1];
 455 | +        txiter newhashit = mapTx.find(vTxHashes[it->vTxHashesIdx].first);

sipa commented at 11:06 PM on June 16, 2016:

If not for this find, we wouldn't need a wtxid index in the mempool... as long we don't build vTxHashes asynchronously, it could be done by storing a CTxMemPool::txiter in vTxHashes instead of a std::shared_ptr<const CTransaction>.

TheBlueMatt commented at 12:57 AM on June 17, 2016:

I avoided doing that since I didnt want to look up iterator invalidation in boost's multi index map, will do that now.

sipa commented at 4:19 AM on June 17, 2016:

They are never invalidated until you delete the item itself. http://www.boost.org/doc/libs/1_60_0/libs/multi_index/doc/tutorial/indices.html#guarantees

TheBlueMatt commented at 5:17 AM on June 17, 2016:

Yes, I found that out after looking it up :)

On June 16, 2016 9:19:08 PM PDT, Pieter Wuille notifications@github.com wrote:

@@ -447,6 +450,15 @@ void CTxMemPool::removeUnchecked(txiter it) BOOST_FOREACH(const CTxIn& txin, it->GetTx().vin) mapNextTx.erase(txin.prevout);
if (vTxHashes.size() > 1) {
   vTxHashes[it->vTxHashesIdx] = vTxHashes[vTxHashes.size() -
1];
   txiter newhashit =
mapTx.find(vTxHashes[it->vTxHashesIdx].first);
They are never invalidated until you delete the item itself. http://www.boost.org/doc/libs/1_60_0/libs/multi_index/doc/tutorial/indices.html#guarantees

You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/bitcoin/bitcoin/pull/8068/files/ba9b1415c5c226eee55f77b10095335240d7af5e..52783001e3cb06759bc823c71ab04e3690b81ad1#r67459055

in src/txmempool.cpp:None in 1f06569449 outdated

 437 | @@ -438,6 +438,9 @@ bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry,
 438 |      totalTxSize += entry.GetTxSize();
 439 |      minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
 440 |  
 441 | +    vTxHashes.emplace_back(hash, newit->GetSharedTx());
 442 | +    const_cast<CTxMemPoolEntry&>(*newit).vTxHashesIdx = vTxHashes.size() - 1;

sipa commented at 5:39 AM on June 17, 2016:

An alternative for the cast is marking vTxHashes as mutable

laanwj added this to the milestone 0.13.0 on Jun 17, 2016

JeremyRubin commented at 2:00 PM on June 17, 2016: contributor

I have a concern with how the block reconstruction mechanism interacts with any mempool policy -- first seen, replace by fee, or opt-in replace by fee. I am worried that mempool policies can be used to greatly increase reconstruction failure rates.

Suppose a new block is found by a miner, containing a bunch of transactions. A malicious node is close to the miner and is able to see the block first. The malicious node has included many high fee transactions such that they have a large portion of the txns included in the block (or really, any portion of the txns). Before the block propagates very far, the malicious node sends replace by fee messages for those transactions. This evicts the old transactions that would go into that block and decreases the block reconstruction success rate.

There are many variants of above attack, including one where a txn is simply frequently RBF'd without trying to condition on when a new block is found.

This kind of attack is also possible with a first seen policy. An attacker generates two transactions of equal fee spending the same coins and propagates them both, such that they reach half the network. This transaction now has a high likelihood of not being reconstructable depending on how that txn propagates (perhaps along a boundary of some sort). Sending multiple such transactions could, each time, partition the network in two, virtually guaranteeing a failure to reconstruct if each partition is fully independent and a reasonable number of transactions (log(nodes)) is used.

I'm not sure that there are many effective mitigations to this, other than attempting to flag transactions that seem to have been used in this manner for the prefill.

gmaxwell commented at 4:17 PM on June 17, 2016: contributor

@JeremyRubin Being able to use more than just the currently active mempool was part of the motivation in switching to use sharedptr rather than the manual rc used earlier. Before making a getblocktxn it could go and check the relaypool, orphanpool, or even a not yet existing pool of rejected transactions. But that would be a further optimization that I don't think is necessary to shove in the very first implementation now. The specific mempool policy shouldn't matter that much because it isn't limited to using the mempool.

in src/main.cpp:None in 1f06569449 outdated

5376 | +    else if (strCommand == NetMsgType::BLOCKTXN && !fImporting && !fReindex) // Ignore blocks received while importing
5377 | +    {
5378 | +        BlockTransactions resp;
5379 | +        vRecv >> resp;
5380 | +
5381 | +        map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator it = mapBlocksInFlight.find(resp.blockhash);

sdaftuar commented at 7:05 PM on June 17, 2016:

Oops, I meant I think we need a cs_main lock here (deleted other comment).

laanwj commented at 2:57 PM on June 18, 2016: member

Summary from last Thursday's meeting: this will get an extra week to be ready for merge* (thus exception from the feature freeze). Next meeting we should decide whether this is along far enough to merge. If so it will still make it into 0.13. If not, it will be merged after 0.13 is branched, and will thus roll forward to 0.14.

* This doesn't mean that there cannot be improvements or small fixes left to do, there can be further development on master after merge, but it should be far enough along that we can be confident that before the rc1/0.13 branch-off, scheduled for 2016-07-06, it will be release-quality

TheBlueMatt commented at 7:38 PM on June 18, 2016: member

@JeremyRubin Indeed, sadly this is inherit in any similar optimizations :(. As @gmaxwell points out we can limit the impact by broadening the scope of what we look at during reconstruction, but we will never be able to fully solve this problem. Still, the goal of this work is to reduce bandwidth during relay on the P2P network, not neccessarily improve relay times, as other solutions are better targeted at that. I hope to write up a "how to set up a UDP-based relay network" post soon to encourage people to set up really effecienct block relay networks that dont (as much) suffer from these issues.

JeremyRubin commented at 2:40 AM on June 19, 2016: contributor

@TheBlueMatt @gmaxwell, thanks for your responses.

I agree that this seems like a fundamental problem with such optimizations. @TheBlueMatt, it might help to clarify the BIP to emphasize that the latency reduction side effect is easily attacked, relying on the decreased latency would be a DOS vector waiting to happen.

I do not think that looking at more caches is a great solution as the probability of failure to reconstruct grows with number of txns looked at and as sipa points out, the memory churn overhead is somewhat large.

TheBlueMatt force-pushed on Jun 19, 2016

Stop trimming when mapTx is empty 96806c39f4

If AcceptBlockHeader returns true, pindex will be set.

Assert this instead of checking (and then dref'ing later anyway)
to make sure no one thinks they can change that postcondition of
AcceptBlockHeader..

7c29ec9449

Move context-required checks from CheckBlockHeader to Contextual... cbda71cf04

Add COMPACTSIZE wrapper similar to VARINT for serialization 5249daca5a

Add partial-block block encodings API 85ad31ede7

Add TestMemPoolEntryHelper::FromTx version for CTransaction f4f8f14adc

Add some blockencodings tests e3b2222144

Add protocol messages for short-ids blocks 00c40784fe

Add sender-side protocol implementation for CMPCTBLOCK stuff 9c837d5468

TheBlueMatt force-pushed on Jun 19, 2016

TheBlueMatt commented at 8:35 AM on June 19, 2016: member

@laanwj thanks for the update.

Updates: Pulled in #8220, which is required. Various small code updates in a few places, nothing that changes behavior, except for sync logic: Pulled out the fix that removes the DoS penalty for non-conencting header messages. Still think thats a really useful change, but it could be replaced with a return or something now since the compact block stuff doesnt rely on it, so should be separate. @sdaftuar and @sipa tried to use some of the AcceptBlock logic in the do-we-process-compact-blocks logic but I'm pretty sure it was wrong, so its now a combination of that code copied into the net-processing code and some slight tweaks (you can see the proposed changes at https://github.com/TheBlueMatt/bitcoin/pull/6/commits/4b212d279eec0c10ed237936cb292a873c526c4f and https://github.com/TheBlueMatt/bitcoin/pull/6/commits/5f1692d1d6aded853f846e33ff0ade2e9f7241f5)

TheBlueMatt force-pushed on Jun 19, 2016

in src/main.cpp:None in 7b71015fd0 outdated

 458 | @@ -435,6 +459,28 @@ void UpdateBlockAvailability(NodeId nodeid, const uint256 &hash) {
 459 |      }
 460 |  }
 461 |  
 462 | +void MaybeSetPeerAsAnnouncingHeaderAndIDs(const CNodeState* nodestate, CNode* pfrom) {
 463 | +    if (nodestate->fProvidesHeaderAndIDs) {
 464 | +        BOOST_FOREACH(const NodeId nodeid, lNodesAnnouncingHeaderAndIDs)
 465 | +            if (nodeid == pfrom->GetId())
 466 | +                return;
 467 | +        bool fAnnounceUsingCMPCTBLOCK = false;

NicolasDorier commented at 8:31 PM on June 19, 2016:

This variable is not very useful anymore.

TheBlueMatt commented at 7:54 PM on June 21, 2016:

Ehh, I prefer to make it clear that its a bool instead of using false and getting some crazy C magic where you never know what type you end up with :p

instagibbs commented at 7:58 PM on June 21, 2016:

I think he means it will always be false at 474, and true at 479?

TheBlueMatt commented at 8:15 PM on June 21, 2016:

Yea, I mean its intended to be a constant, just to force type since I feel better serializing variables and not in-code constants. Maybe (ok, definitely) I'm just crazy :p.

in src/main.cpp:None in 7b71015fd0 outdated

5075 | +            Misbehaving(pfrom->GetId(), 100);
5076 | +            LogPrintf("Peer %d sent us a getblocktxn for a block we don't have", pfrom->id);
5077 | +            return true;
5078 | +        }
5079 | +
5080 | +        if (it->second->nHeight < chainActive.Height() - 10) {

NicolasDorier commented at 8:43 PM on June 19, 2016:

I don't think this is a good idea. But if you insist doing that, I think you should not use ' - 10'.

Imagine the following event:

This peer send a cmpct_blocks at block tip - 10
New block discovered
Remote peer respond with GETBLOCKTXN
This peer will not respond to it causing a timeout for the remote peer

I think you should ideally remove this condition, which is not a DDOS vector, but if you insist, you should put it at a value like - 15 just to be sure we won't timeout the remote peer.

sipa commented at 3:15 PM on June 20, 2016:

I agree, the max depth for responding to getblocktxn should be higher than for responding to a getdata cmpctblock.

TheBlueMatt commented at 11:10 PM on June 21, 2016:

Added a temporary fix here, will add more in #8235.

TheBlueMatt force-pushed on Jun 20, 2016

TheBlueMatt commented at 4:31 AM on June 20, 2016: member

I have no idea why the travis tests failed here, and the error message seems to indicate its a bug in Travis or so?

TheBlueMatt force-pushed on Jun 20, 2016

TheBlueMatt commented at 6:03 AM on June 20, 2016: member

Fixed a few missing \ns in compact block log prints.

Add receiver-side protocol implementation for CMPCTBLOCK stuff d25cd3ec4e

Add ability to fetch CNode by NodeId 927f8eede0

Get our "best three" peers to announce blocks using cmpctblocks 2f34a2e476

Add reconstruction debug logging 56ba516727

Add BIP 152 to implemented BIPs list 678ee9793f

Provide a flat list of txid/terators to txn in CTxMemPool 811902649d

Use vTxHashes to optimize InitData significantly 0d4cb48ef1

Elaborate bucket size math ccd06b94f6

TheBlueMatt force-pushed on Jun 20, 2016

in src/main.cpp:None in ccd06b94f6 outdated

4499 | @@ -4454,7 +4500,7 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam
4500 |              boost::this_thread::interruption_point();
4501 |              it++;
4502 |  
4503 | -            if (inv.type == MSG_BLOCK || inv.type == MSG_FILTERED_BLOCK)
4504 | +            if (inv.type == MSG_BLOCK || inv.type == MSG_FILTERED_BLOCK || inv.type == MSG_CMPCT_BLOCK)

sipa commented at 3:18 PM on June 20, 2016:

Below is a line that stops the getdata processing loop when we have processed sending a block. I think MSG_CMPCT_BLOCK should be included in that line.

(github app does not allow me to comment on the line itself)

TheBlueMatt commented at 11:10 PM on June 21, 2016:

Fixed

in src/main.cpp:None in ccd06b94f6 outdated

 458 | @@ -435,6 +459,28 @@ void UpdateBlockAvailability(NodeId nodeid, const uint256 &hash) {
 459 |      }
 460 |  }
 461 |  
 462 | +void MaybeSetPeerAsAnnouncingHeaderAndIDs(const CNodeState* nodestate, CNode* pfrom) {
 463 | +    if (nodestate->fProvidesHeaderAndIDs) {
 464 | +        BOOST_FOREACH(const NodeId nodeid, lNodesAnnouncingHeaderAndIDs)
 465 | +            if (nodeid == pfrom->GetId())
 466 | +                return;

instagibbs commented at 7:12 PM on June 20, 2016:

Why not just put them in the front of the queue to avoid "eviction"?

TheBlueMatt commented at 8:03 PM on June 21, 2016:

Will fix in PR #2.

TheBlueMatt commented at 8:27 PM on June 21, 2016:

See #8235

sipa commented at 5:29 PM on June 21, 2016: member

Tested ACK ccd06b94f69c3e7758c35ac4bcd36d0e9450e158

The block fetching logic is getting complicated, and is due for refactoring so that more logic can be shared for the decision logic about what to answer in response to inv/headers/cmpctblock, but that can be done later.

Furthermore, it has been running on production systems with very good results for a while.

in src/blockencodings.h:None in ccd06b94f6 outdated

 133 | +
 134 | +    void FillShortTxIDSelector() const;
 135 | +
 136 | +    friend class PartiallyDownloadedBlock;
 137 | +
 138 | +    static const int SHORTTXIDS_LENGTH = 6;

NicolasDorier commented at 9:40 PM on June 21, 2016:

unused

instagibbs commented at 9:54 PM on June 21, 2016:

it's used in 2 static_asserts?

NicolasDorier commented at 10:50 PM on June 21, 2016:

yes, but not in actual code

TheBlueMatt commented at 11:20 PM on June 21, 2016:

Yes, it is intended to exist purely for assertions. If you just look at the code you might assume you can change the encoding and it'll continue to work fine, but this is not true. So instead we add a constant and static_assert.

TheBlueMatt commented at 11:58 PM on June 21, 2016:

where the static_asserts are right beside all of the points in the code you'd have to change, that is.

NicolasDorier commented at 9:55 PM on June 21, 2016: contributor

tested ACK ccd06b9 (https://github.com/MetacoSA/NBitcoin/blob/aeb5f56542765997fb6d22de3f11490c279d67ab/NBitcoin.Tests/cmpctblock_tests.cs) I also played manually with 1 bit shortids, to see how it handled collision and it worked fine.

nits: SHORTTXIDS_LENGTH is unused and my comment on https://github.com/bitcoin/bitcoin/pull/8068/files#diff-7ec3c68a81efff79b6ca22ac1f1eabbaR5080

EDIT: my nits have been responded and on 48efec8. All good for me.

Fix some minor compact block issues that came up in review 48efec82f3

sipa commented at 11:05 AM on June 22, 2016: member

ReACK 48efec82f3a18364c019577495914fcebb425e35

btcdrak commented at 11:09 AM on June 22, 2016: contributor

ACK 48efec8, running node for three weeks using and abusing the connections.

in src/net.h:None in 48efec82f3

  86 |  void AddressCurrentlyConnected(const CService& addr);
  87 |  CNode* FindNode(const CNetAddr& ip);
  88 |  CNode* FindNode(const CSubNet& subNet);
  89 |  CNode* FindNode(const std::string& addrName);
  90 |  CNode* FindNode(const CService& ip);
  91 | +CNode* FindNode(const NodeId id); //TODO: Remove this

fanquake commented at 11:17 AM on June 22, 2016:

Does this need to be removed?

sipa commented at 11:20 AM on June 22, 2016:

Yes, there is a (slightly) longer description in net.cpp.

in src/version.h:None in 48efec82f3

  38 | @@ -39,4 +39,7 @@ static const int SENDHEADERS_VERSION = 70012;
  39 |  //! "feefilter" tells peers to filter invs to you by fee starts with this version
  40 |  static const int FEEFILTER_VERSION = 70013;
  41 |  
  42 | +//! shord-id-based block download starts with this version

fanquake commented at 11:19 AM on June 22, 2016:

nit s/shord/short

laanwj commented at 11:48 AM on June 22, 2016: member

casually-tested ACK https://github.com/bitcoin/bitcoin/commit/48efec82f3a18364c019577495914fcebb425e35

instagibbs commented at 12:04 PM on June 22, 2016: member

nit: cmpctblock debug option not in help text in init.cpp

laanwj merged this on Jun 22, 2016

laanwj closed this on Jun 22, 2016

laanwj referenced this in commit e9d76a161d on Jun 22, 2016

TheBlueMatt deleted the branch on Jul 23, 2016

rebroad commented at 4:47 AM on August 24, 2016: contributor

I hope this is the right place to ask this, but how does this functionality differ from XThin? I notice that various other forks of Bitcoin Core include XThin functionality and these nodes do appear currently to be nodes that are relaying blocks faster than most other nodes. Would it not be worthwhile for Bitcore Core to include the ability to talk XThin also (in addition to compact blocks) thereby allowing it to be more easily determined which performs better?

in src/main.cpp:None in 48efec82f3

3311 |      if (fCheckPOW && !CheckProofOfWork(block.GetHash(), block.nBits, consensusParams))
3312 |          return state.DoS(50, false, REJECT_INVALID, "high-hash", false, "proof of work failed");
3313 |  
3314 | -    // Check timestamp
3315 | -    if (block.GetBlockTime() > nAdjustedTime + 2 * 60 * 60)
3316 | -        return state.Invalid(false, REJECT_INVALID, "time-too-new", "block timestamp too far in the future");

Roasbeef commented at 9:42 PM on August 24, 2016:

It was moved to ContextualCheckBlockHeader.

TheBlueMatt commented at 1:10 AM on August 25, 2016: member

@rebroad This has been answered a few times in other forums, but generally you mmight want to read the various comments at https://www.reddit.com/r/Bitcoin/comments/4hm1nq/bitcoindev_mailing_list_matt_corallo_proposes_new/d2qr24v. As to why not include both, last I checked the Xthin patch touched a ton of code, so would almost certainly conflict (since the various forks that have it forked off of previous versions) and I'm not aware of anyone who wants to do the work to simplify/fix that patch to apply.

rebroad commented at 1:45 PM on August 26, 2016: contributor

@TheBlueMatt I'll give it a go... I'm also writing some patches that can cause my node to crawl around the network favouring the nodes that deliver blocks quicker (disconnecting the least node each time a block is received). Anyway, the XThin code does look pretty messy and it is a headache merging it in with Compact Blocks and SegWit, but I'm slowly working through it - I might give up before I'm finished!

laanwj commented at 3:35 PM on August 26, 2016: member

NACK on merging XTHIN code into Bitcoin Core, this will unnecessarily complicate the handling code. One 'compact blocks' implementation ought to be enough.

in src/main.cpp:None in 48efec82f3

5309 | +                LogPrintf("Peer %d sent us invalid header via cmpctblock\n", pfrom->id);
5310 | +                return true;
5311 | +            }
5312 | +        }
5313 | +
5314 | +        // If AcceptBlockHeader returned true, it set pindex

rebroad commented at 6:55 AM on September 11, 2016:

Are you assuming AcceptBlockHeader returned true at this point in the code? If so, surely the return statement above is in the wrong place.

TheBlueMatt commented at 1:21 PM on September 12, 2016:

AcceptBlockHeader will either set state invalid or return true. At some point it might also set state.IsError, though it doesnt currently, in which case assert(NULL) isnt all that bad an outcome.

in src/main.cpp:None in 48efec82f3

5326 | +            if (fAlreadyInFlight) {
5327 | +                // We requested this block for some reason, but our mempool will probably be useless
5328 | +                // so we just grab the block via normal getdata
5329 | +                std::vector<CInv> vInv(1);
5330 | +                vInv[0] = CInv(MSG_BLOCK, cmpctblock.header.GetHash());
5331 | +                pfrom->PushMessage(NetMsgType::GETDATA, vInv);

rebroad commented at 5:49 PM on September 12, 2016:

I'm confused, why getdata it if it's already in flight?

rebroad commented at 5:24 AM on November 1, 2016:

Still confused by this. I guess this isn't the place to seek clarification....

rebroad commented at 8:15 AM on November 1, 2016:

I'm realising that the variable fAlreadyInFlight isn't meaning whether it's in fight, but perhaps is supposed to refer to whether the block was requested or not...?

in src/main.cpp:None in 48efec82f3

5361 | +                    MarkBlockAsReceived(pindex->GetBlockHash()); // Reset in-flight state in case of whitelist
5362 | +                    Misbehaving(pfrom->GetId(), 100);
5363 | +                    LogPrintf("Peer %d sent us invalid compact block\n", pfrom->id);
5364 | +                    return true;
5365 | +                } else if (status == READ_STATUS_FAILED) {
5366 | +                    // Duplicate txindexes, the block is now in-flight, so just request it

rebroad commented at 5:50 PM on September 12, 2016:

Still confused - "in-flight" means it's already been requested, doesn't it? Perhaps it can be clarified somewhere what the term means?

in src/main.cpp:None in 48efec82f3

5343 | +        // possibilities in compact block processing...
5344 | +        if (pindex->nHeight <= chainActive.Height() + 2) {
5345 | +            if ((!fAlreadyInFlight && nodestate->nBlocksInFlight < MAX_BLOCKS_IN_TRANSIT_PER_PEER) ||
5346 | +                 (fAlreadyInFlight && blockInFlightIt->second.first == pfrom->GetId())) {
5347 | +                list<QueuedBlock>::iterator *queuedBlockIt = NULL;
5348 | +                if (!MarkBlockAsInFlight(pfrom->GetId(), pindex->GetBlockHash(), chainparams.GetConsensus(), pindex, &queuedBlockIt)) {

rebroad commented at 5:15 AM on November 1, 2016:

This practice of using function names that then are not used for what their name implies make me quite uncomfortable about the reliability of the code. I would far prefer to see MarkBlockAsInFlight called only just before or just after the block is in flight, i.e. after the PushMessage of GETDATA. For readability more than anything else.

in src/main.cpp:None in 48efec82f3

5316 | +        UpdateBlockAvailability(pfrom->GetId(), pindex->GetBlockHash());
5317 | +
5318 | +        std::map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator blockInFlightIt = mapBlocksInFlight.find(pindex->GetBlockHash());
5319 | +        bool fAlreadyInFlight = blockInFlightIt != mapBlocksInFlight.end();
5320 | +
5321 | +        if (pindex->nStatus & BLOCK_HAVE_DATA) // Nothing to do here

rebroad commented at 7:26 AM on November 1, 2016:

would if (pindex->nTx > 0) be better since we'd also have nothing to do here if we received a compact block for a block that we've already pruned.

in src/main.cpp:None in 48efec82f3

5314 | +        // If AcceptBlockHeader returned true, it set pindex
5315 | +        assert(pindex);
5316 | +        UpdateBlockAvailability(pfrom->GetId(), pindex->GetBlockHash());
5317 | +
5318 | +        std::map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator blockInFlightIt = mapBlocksInFlight.find(pindex->GetBlockHash());
5319 | +        bool fAlreadyInFlight = blockInFlightIt != mapBlocksInFlight.end();

rebroad commented at 8:04 AM on November 1, 2016:

fAlreadyInFlight is a confusing variable name since it will be true if we requested the block and false if we did not, therefore fRequested would be a more suitable variable name, wouldn't it?

Or is the intention to ask if it's been requested from another peer?

Does it matter if it was requested from this peer, or another peer?

codablock referenced this in commit 7bd6bc8517 on Sep 16, 2017

gladcow referenced this in commit f7b5910f19 on Mar 2, 2018

gladcow referenced this in commit b539bc252f on Mar 13, 2018

gladcow referenced this in commit 740380b4f3 on Mar 14, 2018

gladcow referenced this in commit 36a17b2926 on Mar 15, 2018

gladcow referenced this in commit 4e7c52509e on Mar 15, 2018

gladcow referenced this in commit 485bacbb9c on Mar 24, 2018

gladcow referenced this in commit f4d49bc74b on Apr 4, 2018

UdjinM6 referenced this in commit bc45a2f87a on Apr 11, 2018

zkbot referenced this in commit 3b68ab255f on Apr 17, 2018

zkbot referenced this in commit d408e23ab7 on Apr 18, 2018

zkbot referenced this in commit 0753a0e8a9 on Apr 19, 2018

andvgal referenced this in commit fd5c50bc2b on Jan 6, 2019

furszy referenced this in commit 8cd9c592a9 on May 29, 2020

in src/main.cpp:5374 in 48efec82f3

5369 | +                    pfrom->PushMessage(NetMsgType::GETDATA, vInv);
5370 | +                    return true;
5371 | +                }
5372 | +
5373 | +                BlockTransactionsRequest req;
5374 | +                for (size_t i = 0; i < cmpctblock.BlockTxCount(); i++) {

rebroad commented at 3:56 PM on September 2, 2021:

Why not start at index 1 instead of 0 (since isn't this always the prefilled tx)?

MarcoFalke locked this on Sep 2, 2021