Xpress Validation - request for input

[Peter Tschipper]

Hi All,

Something I've been playing with for a while and was thinking would require a BUIP but @theZerg thinks maybe it doesn't rise to the level of requiring one. It's only about 15 lines of code and doesn't change much but is another performance enhancement and really the second part to Xtreme Thinblocks. I've attached what was going to be the BUIP details below and your comments are appreciated as well as whether you think this type of change needs a formal vote. (Thanks to @YarkoL for the branding and for being a sounding board)

Summary

The problem of quickly relaying blocks of any size to all nodes worldwide within just a few seconds has remained elusive. Without the ability to do so means there is no way to effectively increase block size without potentially causing problems for nodes which would no longer be able to keep up with the blockchain and not be able to consistently relay transactions in a timely manner. Often forgotten in the debate is that during the time a block is downloaded and validated, no transactions can be relayed by that node. If today it takes a node 10 to 60 seconds to download and validate a block then as we increase block size further we will only create ever larger queues of un-propagated transactions with subsequent sudden transaction spikes as the queues become unblocked.

Xtreme Thinblocks fixed the first part of p2p block relay; the downloading of a block of almost any size is now in the sub second region. However, the second part of relay, the validation of the block is equally important and can be more time consuming. Enter Xpress Validation or XV. XV builds on Xtreme Thinblock technology and now makes it possible to validate a block of virtually any size in a consistently short period of time. By using the XV reference client, testing shows that full blocks are typically downloaded and then fully verified, with the tip connected, in approximately 0.75 to 1.5 seconds for the full round trip (* NOTE: these numbers are all from the v11.2 client on a very slow laptop, I'll update these as I get to v12). Therefore XV in addition to Xtreme Thinblocks will make it possible to relay newly mined blocks of almost any size to the entire global network of nodes within 5 to 10 seconds, thus freeing up local CPU and bandwidth while also allowing for a more consistent and reliable flow of transactions throughout the p2p network than is currently possible.


Design

There are several steps within the process of validating a block. Most of them are relatively quick and in terms of milliseconds or tenths of a second to execute. Where block validation gets slow is during the process of checking inputs. So how can we get around that and still fully validate the block before relaying it to another node?

As it turns out it’s not that difficult with the reason being that currently every transaction in a block is actually checked twice; once, during the process of accepting a transaction into the memory pool and once again when the block is verified; this double checking works in our favour as follows. With Xtreme Thinblocks we re-construct the block from transactions that already exist in the memory pool and have been previously verified, their inputs have already checked; we don’t have to check those again! The only transactions we have to check are the ones we know nothing about, the ones arriving in the XThinblock and which are only a handful in number. So out of a typically 1500 to 2500 transaction block we only need to verify a few of them before connecting the tip. In this way, verifying a full block typically takes about 0.75 seconds rather than 10 to 30 seconds and sometimes longer. Furthermore, it has shown to be twice as fast as when relying on the signature cache.


Testing

In order to easily test XV you must also download XThinblocks. Use the following setting to connect to a thinblock provider.

connect-thinblock=<ip>

When this setting is used the node will connect to the IP address(es) specified and only download blocks or thinblocks from those IP addresses. However, transactions will still be downloaded from all connected peers regardless of this setting in order to keep the memory pools in relative sync.


Test Results

The following results show an example of the requesting of an almost 1MB block (over the internet to a node 1200 miles away) to the receiving of the block and the final updating of the tip with the associated response times, and performed on an antiquated dual core laptop with an Intel B820 processor.

2016-02-02 15:28:01 Starting creation of bloom filter
2016-02-02 15:28:01 Sending bloom filter: 9312 bytes peer=3610
2016-02-02 15:28:01 Requesting Thinblock 000000000000000006659c241d9f078952c3ed821433cc79e00e41ff02f8c822 (396326) peer=3610
2016-02-02 15:28:01 Received Thinblock 000000000000000006659c241d9f078952c3ed821433cc79e00e41ff02f8c822 peer=3610 (9408 bytes)
2016-02-02 15:28:01 Reassembled Thinblock for 000000000000000006659c241d9f078952c3ed821433cc79e00e41ff02f8c822 (949216 bytes)
2016-02-02 15:28:01 Received block 000000000000000006659c241d9f078952c3ed821433cc79e00e41ff02f8c822 in 0.47 seconds
2016-02-02 15:28:02 UpdateTip: new best=000000000000000006659c241d9f078952c3ed821433cc79e00e41ff02f8c822 height=396326 log2_work=84.026511 tx=107482487 date=2016-02-02 15:26:59 progress=0.999999 cache=57.3MiB(23696tx)
2016-02-02 15:28:02 Processed block 000000000000000006659c241d9f078952c3ed821433cc79e00e41ff02f8c822 in 0.56 seconds


Backward Compatibility

Although XV is potentially compatible with any client, it is currently only invoked when receiving an XThinblock and when “use-thinblocks” is enabled on the client. In other words, we can download blocks from any client, but XV is only used when downloading a block from a node that supports thinblocks.


Fall Back

Turning off XV is the same as turning off XThinblocks and is a straightforward “bitcoin.conf” entry. By setting “use-thinblocks” to zero the downloading of thinblocks and XV will be turned off.

use-thinblocks=0


Deployment

This enhancement does not require a hard or soft fork.


Future Strategies

Lightning Block Relay (for Miners): Now that the groundwork is done for the p2p node network it would be possible to build a truly decentralized relay for miners.

Enhanced Memory Pool Synchronization: Although XThinblocks and XV will improve mempool synchronization by relieving stress on the single threaded network layer there is much more to be done in order to scale into the 100’s or 1000’s of transactions per second and higher. Several initiatives could improve the fast relay of transactions throughout the network such as transaction bundling combined with datastream compression and a multithreaded network.

 

[theZerg]

Just for clarity, I don't think this needs a BUIP because it is an internal optimization -- instead of validating the same transaction twice (which has not benefit whatsoever) the fix reportedly validates a txn once.

The BUIP process is not meant to open every development detail to everyone (which would be very tedious, esp. for non-coders), its meant to set overall direction and highlight major user visible behaviorial features/changes.

EDIT: Also I want to get this into the forthcoming release

 

[sickpig]

@Peter Tschipper

fantastic idea!

So in bitcoin core not only txs are sent twice also validated twice. I wonder if the same applies to btcd /cc @davecgh.

I was wondering if there's a way to test this feature on historical data, just to make sure that there's no arcane corner case when validating a block produce a different result than validate the txs belonging to it separately (time wise). I don't 't even know if this makes sense, though.

That said you're officially my new hero.

edit: IMHO no need for a new BUIP

 

[cypherdoc]

sounds impressive.

 

[solex]

@Peter Tschipper
Thanks for the detailed explanation of Xpress Validation. I agree that this is a logical component of XThinblocks and is necessary to get full benefit of the enhancement. It is not a distinct functional change from a user perspective, and shouldn't need a separate BUIP.

The ideas you are putting into code will make the next release of BU simply phenomenal.

 

[cypherdoc]

assuming this all works as intended, one has to wonder why these things never get added into Core?

 

[Peter Tschipper]

@sickpig

@Peter Tschipper
I was wondering if there's a way to test this feature on historical data, just to make sure that there's no arcane corner case when validating a block produce a different result than validate the txs belonging to it separately (time wise). I don't 't even know if this makes sense, though.
edit: IMHO no need for a new BUIP

I don't think we need to do that, all we're checking is the transaction hash, nothing inside the tx is getting checked so historical tx's wont be relevant here. But more testing is always good.
[doublepost=1455842064][/doublepost]Sound all good, I'll submit a PR tonight.

 

[solex]

assuming this all works as intended, one has to wonder why these things never get added into Core?

The answer to that has 3 parts:

a) No need for all nodes to have efficient block propagation if the block limit is always going to stay at 1MB
b) Definitely bad to have fast block propagation for all nodes as it demolishes the argument to keep the block limit unchanged.
c) A hard-fork for changing the block limit puts the high status of the reference client at risk. Goto (a)

 

[freetrader]

Sounds like it would be another feather in the cap for xthin blocks.
My questions relate to the following:

With Xtreme Thinblocks we re-construct the block from transactions that already exist in the memory pool and have been previously verified, their inputs have already checked; we don’t have to check those again!

Is there anything preventing XV from being applied also to blocks received by other means?
The concept of not re-validating txns already in the mempool sounds fairly generic to me.

Turning off XV is the same as turning off XThinblocks

If XV could have a justification independent of Xthinblocks, then it would perhaps be sensible to have a separate switch to enable/disable it (across all paths of block verification).

 

[YarkoL]

assuming this all works as intended, one has to wonder why these things never get added into Core?

I've been discussing this with @Peter Tschipper , as it is the first question that springs to mind. The most likely explanation for the double validation is an attack scenario where a block contains an already-seen transaction id but actually holds something else. So even with XV enabled, we still do the extra check if we get a regular block instead of xthin (in which case we just pull txs from our own mempool).

This new improvement needs thorough review and testing before incorporating it to BU. IMO we could even save it to a later release together with the ""dynamic partial hashes" version of XThinblocks.

 

[Peter Tschipper]

Sounds like it would be another feather in the cap for xthin blocks.
Is there anything preventing XV from being applied also to blocks received by other means?
The concept of not re-validating txns already in the mempool sounds fairly generic to me.

You can but it requires us to reconstruct the incoming block with tx's from our own mempool. It's more work and if we're going to be using xthins in the future then I"m not sure it's worth the effort.

 

[solex]

I've been discussing this with @Peter Tschipper , as it is the first question that springs to mind. The most likely explanation for the double validation is an attack scenario where a block contains an already-seen transaction id but actually holds something else. So even with XV enabled, we still do the extra check if we get a regular block instead of xthin (in which case we just pull txs from our own mempool).

This new improvement needs thorough review and testing before incorporating it to BU. IMO we could even save it to a later release together with the ""dynamic partial hashes" version of XThinblocks.

Would this attack scenario require two different txns with the same hash, and even then after building the block the merkle-root would be different from the header? Which then means the block gets rejected and the node has to fall back to obtaining a standard block. Seems like a pretty weak attack.

 

[YarkoL]

@solex Yes well, the bottomline is that the heavy lifting in the validation is in the signature verification, and that is cached. So the validation that occurs during the block checking is quick looking at things like nLocktime and other tx attributes.. definitely there are many ways to do funny business with them, but as said, we do it also with regular blocks.

 

[Peter Tschipper]

@solex there's not much they can do other than cause us to re-request a block. But even so I don't see how they could get a txn that wasn't valid into the mempool.

 

[Chronos]

Can a block contain a transaction that spends an input that's also created in that block? If so, could the validity of that transaction depend on whether the input is in fact created in that block? If so, how could the validation of that transaction be completed before the contents of that block are known?

 

[Peter Tschipper]

if we havn't seen the transaction yet in our mempool then we can't validate it until we actually accept the block. So those transactions that we haven't seen yet will either be in the orphan cache or appended to the xthinblock. Either way, the tx will get validated at some point. It's just that we want to do as many as possible beforehand. Generally we only have to validate a handful of tx's but sometimes there are many orphans that get included in a block where we haven't seen the parent yet, or the parent is announce only in the block. (Seems that BTCC does that somewhat frequently)

One thing we're going to add in the next release is to pre-validate the orphan signatures. We can't validate their inputs but we can at least look at the sigs, which is the most time consuming verification. Once done the sigs go into the sig cache and won't have to be validated again when the block is accepted. So we'll save time there if there are many orphans included in the block. But as far as what's in the xthin, we have to validate those at the end when the block is accepted.

 

[Chronos]

Interesting. Is an "orphan signature" a transaction that spends from a zero-conf utxo that hasn't been seen by the node yet?

I'm not sure if you answered my question. I'm asking about a transaction that's only valid if another transaction is also in the block, where both transactions are already in the mempool. So the block must be analyzed before validity can be confirmed.

 

[Peter Tschipper]

an orphan signature is just a signature of the transaction, it's not any different from any other tx, it's just that orphans don't get their signatures checked unless they get pulled into the mempool.

So, if both tx's are in the mempool then they have already been analyzed. if one is a parent of the other it doesn't matter, they are both in the mempool. If the parent were not in the mempool yet then the child would still be in the orphan cache and not analyzed yet. When the parent shows up in the mempool the orhpan is pulled into the mempool and verified at that point. Not sure I answered your question?

 

[Chronos]

So, this scenario:

1) receive an orphan (transaction 1)
2) parent shows up (transaction 2). Both transactions are validated.
3) xthinblock arrives with transaction 1 in it, but transaction 2 is missing. This makes transaction 1 an invalid transaction because its parent is not in the blockchain.

Is this scenario caught by Xpress Validation?

 

[Peter Tschipper]

if that scenario were to happen the block would be invalid and not accepted. The parent has to be there in the block or in the blockchain. A miner wouldn't mine such a block, maybe someone who was trying to DOS would but as I said the block would be rejected and the peer banned.