Bounded block backlog

This is a description of the change to bound the number of unconfirmed blocks in the ledger. Adding a bandwidth cap has effectively bounded the rate at which the network confirms blocks but there still can be a large number of unconfirmed blocks in the ledger.

A new table called ‘backlog’ will be in the database to track unconfirmed block hashes.
In memory, a sorted container mapping difficulty to block hash is kept and used to look up unchecked blocks by difficulty.

When a block is inserted, its hash is put into the backlog table and the memory mapping is updated. If the memory mapping exceeds a node-configurable number, it will find the block hash with the lowest difficulty and remove it from the ledger.

Eventually it is possible the block will have low enough difficulty that it will get removed from all ledgers in the network because there is a cap on the number of blocks the node will keep in the backlog. This will require the block creator to increase the difficulty on the block and publish it again. The functionality to increase this difficulty and republish already exists.

This strategy ensures the number of blocks accepted into the ledger that are not confirmed stays reasonable. It also offers a direct way to find unconfirmed blocks instead of scanning account frontiers as is currently done in the confirmation height processor.

30 Likes

Can I ask in a noncoding way so myself and others can understand?

Lower Bandwidth helps increase the network difficulty without hitting other two factors (CPU, DISK limits for node), however, here if unconfirmed blocks are high, all those that were published with lower difficulty are asked to come back with a higher difficulty (network raises difficulty due to increase in unconfirmed blocks and other dyPOW factors) to prove they are not spam, for users, it is hitting try again if the network difficulty changed that instant when they hit send but for the spammer, its a pain in the ass, also none of his transactions would be added to the ledger coz his blocks won't be confirmed unless he re-broadcasts with a higher POW. So it also addresses ledger bloat.

Did i understand it right?

8 Likes

This is the ELI5/10 I posted on reddit. Maybe it helps others understand the proposal better.

Here's my ELI5, because one was requested. Maybe it's more an ELI10.
A TL;DR is at the end, which might qualify as ELI5 (crypto edition).

Please give me feedback about misconceptions, so that I can update it accordingly.

Right now you can have a lot of unconfirmed blocks in the ledger, all of them are put into the ledger, which causes disk I/O and seems to be one reason weaker nodes have been overwhelmed by the spam.
I'm not sure whether there's any limit regarding the unconfirmed blocks coded into the node. I suppose there isn't one.

The proposal regarding the backlog suggest a table, in which the hashes (the identifier) of unconfirmed blocks get added, sorted by difficulty.
This table runs in RAM and is much faster than the ledger on SSD.
This table has a configurable size. Once the size has been reached, the blocks with the lowest difficulty get pushed out.
Blocks that are confirmed, leave the backlog and get stored on SSD.

This pretty much mimics the scheme behind the mempool and tx fees in Bitcoin.

Bitcoin:
Tx fees allow to compete for a place in a Bitcoin block. The higher the fee (per size of the tx), the more likely the tx gets included.
Until a tx is confirmed, it needs to wait in the mempool.

NANO:
The difficulty if the work allows a block to compete for a place in the ledger on SSD. The higher the diff, the more likely the block stays in the backlog until it gets confirmed.
Until a block is confirmed, it needs to wait in the backlog.

TL;DR
The backlog at NANO is the equivalent of the mempool at Bitcoin.
As long as a block (NANO) or tx (Bitcoin) is in the backlog (NANO) or mempool (Bitcoin), it has a chance of getting put into the ledger.
Once it's out of the backlog/mempool (both have size limits), it can only be put into the local ledger by syncing it from other nodes.
If the block/tx drops out of all backlogs/mempools, it needs to be sent again.

8 Likes

block hash with the lowest difficulty and remove it from the ledger

Is this something that shouldn't happen if the block is published with the current node-reported difficulty level? Or would wallets have to check if the average/median unconfirmed count is nearing the default limit and increase the difficulty?

It also offers a direct way to find unconfirmed blocks instead of scanning account frontiers

Would this change speed up the time required for a restarted node to get back up to speed with the network? If so, a very welcomed change.

1 Like

I love it! Thank you Colin and the team!

This simple change should address spam and ledger bloat at the same time by effectively throttling the network and prioritizing transactions by attached proof of work difficulty rather than fees.

@numsu yes it should let weaker nodes catch up since only a certain number of blocks are processed at a time rather than as many as permitted by bandwidth.

Maybe I'm confused but I've asked multiple times prior on discord about this issue. I was told there was a "container" that maxed out at 50,000 blocks. Is this just now being implemented?

I'm also confused about how this works compared to the DPoW description of "dropping" blocks after certain time periods.

In the end I'm a fan of a system that drops low PoW blocks sooner rather than later.

There is a memory version that holds all the elections, in a similar ordered container, but if they get removed due to size, the block still remains on disk.

This limits the number of unconfirmed blocks that can be on disk.

3 Likes

The wallet already samples the active network difficulty and targets that when generating PoW difficulty. It will also increase the difficulty when it sees the block isn't getting confirmed.

It should yes, since the ledger will directly track unconfirmed blocks it doesn't need to scan the account list in search of them.

2 Likes

Thanks for clarifying. Is there a suggested number for the unconfirmed block limit?

In thinking about it quickly, keeping this number small could increase the speed at which a sender of a low PoW difficulty transaction realizes their getting "pushed out" by other transactions. Thus, they generate a higher difficulty PoW and resend more quickly. Thus, network PoW levels rise. Thus, things get tougher on a spammer.

1 Like

PS I know you're not looking for a pat on the back but your level of engagement during this spam deal has been fantastic. I think I speak for a lot of the community when I say it's greatly appreciated.

13 Likes

So each node will control how many unconfirmed blocks it holds in memory, allowing it to throttle to its own hardware specs?

How would a sender know how much PoW is needed to ensure their block doesn't get dropped? In the current attack wouldn't the sender assume it's OK to send at the baseline difficulty but I believe that would put them on even footing with the spam.

It doesn't need to be that big, a few seconds worth at network cps would be enough.

Special consideration will need to be taken to deal with bootstrapping as a large number of unconfirmed blocks can exist.

1 Like

Will some sort of initial triage/validation be conducted on an unconfirmed block before it is added to the 'backlog'? My concern would be that an invalid block (work value appears to compute high but is in fact invalid for that particular block) could spam the backlog and cause legitimate blocks to fall off.

1 Like

I find this solution brilliant:

  1. This is a proven solution, similar to Bitcoin's mempool.
  2. Doesn't require a concept of "time" in the protocol.
  3. Looks to be reasonably simple to implement.
  4. Operators can configure the mempool size, so in case of attack they can lower it to trigger a difficulty change quicker.

You're a genius, Colin.

PS: only possible drawback to this solution, is that an attacker with resources could pre-calculate a pretty high POW thus forcing the rest of the network to have a higher (and slower) POW. But at least this would cost the attacker a lot more money, specially after a move to equihash.

9 Likes

This is amazing, love this solution, can't wait for it to be implemented

1 Like

Yea this is what would happen. Precaching a PoW solution means the latency won't be noticeable for most users. If an attacker needs to generate 4x difficulty for the next transaction and so does a user, a user may not need to use that solution for hours or days making it unnoticable.

Adding to the backlog only happens after a block is inserted in to the ledger. Inserting in to the ledger is where all the transaction checks are done so yes, it will be a functionally valid block before being added to the backlog.

3 Likes

Any chance of this being implemented for V22 or is too late?

Not sure, but I can think of V21.3 :wink:

1 Like

So, a gazillion low priority blocks by a spammer that are dropped from the backlog would still be in the ledger? What's the effect of a block dropped from the backlog then? As I understand it, then this would increase POW but not solve the ledger size increase, right?