Time-as-a-Currency & PoS4QoS - PoS-based Anti-spam via Timestamping

To continue on the discussion from the reddit thread here, factoring in some of the discussions that I've had with Colin, the PoS-based anti-spam system would work as follows.

Summary

Add QoS tiers to the Nano protocol where nodes may deterministically identify a "safe" order to resolve transactions in the event of an ongoing spam attack.

This may be done by adding a timestamp field to the protocol to be used as a loose idea of when a request was made. The receiving nodes will verify that this timestamp field falls within a range (GRACE_PERIOD) of their (the nodes') current time and obeys other rules of the network that are carefully crafted to prevent spam attacks.

If this verification fails, the user's requests fall into the lowest QoS tier (known as the normal queue). If this verification succeeds, the user's transaction enters the priority queue, where its actual QoS is determined by the stake of the wallet issuing the transaction.

Tiebreakers in stake would be determined via the current method of the nonce complexity.

Threat Model

Attacker is assumed to be able to precompute effectively "infinite" PoW. This can feasibly be done via an ASIC that would outperform a mobile user by an order of 1012. Since mobile users need to be catered to with a relatively realistic PoW (<100 seconds), this means that the attacker would be able to generate at least 1010 more PoW than an acceptable user, or effectively infinite, with a price tag of around $105 USD.

Terms

Priority Queue - The new "normal" for the network; the location for all requests that conform to new timestamping rules. Within this queue, transactions are further divided into sub-queues based on the PoS of the transacting account.
Normal Queue - The old "normal" for the network; the location for all requests that do not conform to new timestamping rules. This is effectively the lowest QoS level in the network, and is processed after all PoS-based QoS that occurs in the Priority Queue.

Timestamping

Rules

To qualify for the Priority Queue, a transaction must meet all of the following criteria:

  1. The transaction must be timestamped, and the previous transaction within the user's blockchain (if not the OPEN operation) must also be timestamped. In the event of an OPEN operation with an included RECEIVE, the corresponding SEND operation must be timestamped.
  2. When a node receives the transaction, the timestamp must be within GRACE_PERIOD from the current time. This may be in either direction (past or future).
  3. The transaction's timestamp must be at least MINIMUM_GAP time after the timestamp of the previous transaction.
  4. For OPEN-RECEIVE and RECEIVE operations, the timestamp must be at least MINIMUM_GAP time after the corresponding SEND operation.

Rule Justifications

Rule (1) is the primary driver of the entire system. Without a timestamp on the current node and a timestamp on the previous node, there are no timestamps with which to compare anything.

Rule (2) combined with Rule (3) create a system whereby an attacker cannot simultaneously send more requests at once than GRACE_WINDOW / MINIMUM_GAP without either (A) being forcibly throttled to 1 / MINIMUM_GAP TPS or (B) falling out of the Priority Queue for 1 transaction (effectively forcing the spam to be cleared fully before they are allowed to resume).

Rule (4) prevents attacks that involve an attacker with a large amount of Nano (106+) from sending Nano to new addresses repeatedly, by enforcing that the receiving accounts are also incrementing their timer by MINIMUM_GAP based on the sender's timestamp.

Variables

  • GRACE_PERIOD - The amount of permitted time-drift from the node's timestamp that a node will allow a transaction to have to still qualify for the Priority Queue. For example, if a node's time is 5:00, and they receive a request that has a GRACE_PERIOD of 30 seconds, then they are willing to accept the request into the Priority Queue as long as it's dated for anywhere from 4:59:30 through 5:00:30.
  • GRACE_WINDOW - Defined as 2 * GRACE_PERIOD, because the period is both into the past & future, so the window is the full amount of time of this period in both directions. In the above example, the GRACE_WINDOW is 1 minute (30s in both directions; 05:00:30 - 04:59:30 = 00:01:00).
  • MINIMUM_GAP - The amount of increase one timestamp must have from the last timestamp in a chain. For example, if the timestamp of an account's previous request is 05:02:25 and the MINIMUM_GAP is 15 seconds, the next request must be dated for 05:02:40 or later.
  • SUSTAINED_TPS - This is, by definition, the multiplicative inverse of MINIMUM_GAP (that is, 1 / MINIMUM_GAP).
  • MAX_BURST - Defined as GRACE_WINDOW / MINIMUM_GAP. This is the maximum amount of transactions that may be precomputed and sent simultaneously. It requires the attacker to use the full extent of their GRACE_WINDOW, from TIME - GRACE_PERIOD through TIME + GRACE_PERIOD, incrementing every MINIMUM_GAP in between.

These variables (particularly GRACE_PERIOD and MINIMUM_GAP) may be determined dynamically based on the PoS of the wallet in question. Ideally, this is done via empirical determination of valuable metrics.

For example, if it is determined that an exchange typically handles 1 TPS, with occasional bursts to 1,000 TPS during very busy times, this could be resolved into MINIMUM_GAP = 1 AND GRACE_PERIOD = 500 for wallets with more than 106 stake.

Lower users may have more restricted TPS (both in consistent TPS (MINIMUM_GAP) as well as burst TPS (indirectly determined via GRACE_PERIOD).

PoS4QoS

If a request falls within the Priority Queue, it is then resolved based on the stake of the wallet. A wallet with 107 Nano would have its transaction resolved before the actions of a wallet containing 103 Nano, and so on down the chain.

In the Reddit thread (and initial thoughts), the QoS tiers were separated into discrete chunks. However, there is no apparent reason why the QoS tiers could not be effectively a continuous scale whereby higher PoS always yields a higher QoS.

Sample Attack Considerations

Attack 1: Invested Attacker Single Account Spam

Problem: Attacker with high amount of Nano (106 - ~$35m investment) wants to spam attack the network by sending trivial amounts to another wallet.

Solution: Due to the limitations of Rule (2) + Rule (3), the attacker would be limited to MAX_BURST requests before being throttled down to SUSTAINED_TPS unless they're willing to exit the Priority Queue. If they exit the Priority Queue, they must wait for the spam attack (which exists within the Priority Queue) to resolve itself, as well as all other Priority Queue traffic, before their new Normal Queue request is resolved. This means that they are effectively DoS'ing their own ability to continue the spam attack until the ongoing spam attack subsides.

Attack 2: Mass Account Spam

Problem: Attacker uses 1,000,000 wallets, each sending 0.0000001 Nano per second through the network, bypassing the protections offered by the Priority Queue within the Time-as-a-Currency system.

Solution: PoS4QoS ensures that these extremely low value wallets would be at such an exceptionally low QoS (due to having such little PoS) that they are effectively DoS'ing such a microscopic part of the ecosystem (extremely small requests & outdated nodes/mistakes that cause legitimate users to enter the Normal Queue) so as to make the attack unfeasible/unprofitable.

Attack 3: Invested Attacker Chaining New Account Spam

Problem: Attacker owns a large amount (106+) of Nano and wants to DoS the network by sending its entire balance to a new account, which will then immediately pass the entire balance to another new account, and so on.

Solution: Rule (4) of the timestamp rules ensures that the RECEIVE block is upped a MINIMUM_GAP from its corresponding SEND block; this attack becomes identical to the above Attack 1.

Additional Notes

Concepts

  • Herd Immunity - It is fairly easy to envision a scenario where, in Attack#2, microscopic amounts of the legitimate traffic on the network are still vulnerable to a spam attack. However, by protecting the high-value members, launching this attack becomes unprofitable and ultimately pointless. By neutering the goal of the attack, the weakest transactions on the network (i.e., those worth < 0.0000001 Nano, or those in the Normal Queue due to error/mistake) gain protection implicitly.

  • Timestamp Trust? - Timestamps are not trusted to be correct. It is in the clients' best interest to provide an accurate timestamp, so as to ensure that they are in the Priority Queue. The purpose of the timestamp and related variables (GRACE_PERIOD | MINIMUM_GAP) is for decentralized throttling, not a trustworthy reporting of time. However, in a pinch, these timestamps are better than nothing to identify the time at which a request was sent, which adds a small bonus for some forensics.

  • Time-as-a-Currency - I've thrown this term around a few times now; what does this really mean? The fundamental idea is that you are given a set block of time as a "currency" that you may spend (equal to GRACE_WINDOW). However, you must spend it in minimum chunks (MINIMUM_GAP). In addition, you regenerate this currency at a rate of 1 second (currency) per second (time), all in a decentralized manner. The result of MAX_BURST is due to stockpiling your "currency" (time) up to its maximum reserve (GRACE_WINDOW) and spending it all on as many requests as possible (GRACE_WINDOW / MINIMUM_GAP).

  • Normal Queue Meaning - The Normal Queue is a bit of a misnomer. Perhaps better names would be the "Protected Queue" and the "Vulnerable Queue." The "Protected Queue" (here called Priority Queue) is protected from spam attacks due to the Time-as-a-Currency rate limiting principle and further protected due to PoS4QoS. Meanwhile, the "Vulnerable Queue" (AKA Normal Queue) offers no such protection. However, that does not mean that the Normal Queue would be a spammed, worthless hole of requests. In fact, the Normal Queue is what is now the entire Nano network. In short, the worst attack that an attacker could launch against this (one that forces all nodes to the Normal Queue) would simply revert the network back to the status quo.

Conclusion

Wrote this over here to move the discussion from Reddit and have a place to keep the discussion centralized in an area that won't "get away" from us. The real TL;DR is up top under "Summary" if interested.

15 Likes

Would this TLDR be correct - We move away from simple POW weight prioritisation, to a more complex mechanism that still primarily uses POW, but favours accounts that have larger balances, and/or have made sporadic nano transactions in the past.

I think this is a really interesting idea. I had one idea pop up into my head, is it in theory possible to even not add those blocks that end up in the normal queue to the ledger at all? To avoid ledger bloat? Perhaps this would only happen during saturation, but I'm thinking if you have these separate queues this opens for this possibility as well?

2 Likes

I hate to sound overly negative here but time stamps has absolutely no place in a protocol of an asynchronous network. Couple of reasons:

  • Do you want to synchronize all the nodes?
  • There is only one time and that is relative: the time of the individual node.
  • Time stamps can be easily forged.
3 Likes

I don't understand how you're so strongly against time stamps in the light of

Timestamp Trust? - Timestamps are not trusted to be correct . It is in the clients' best interest to provide an accurate timestamp, so as to ensure that they are in the Priority Queue . The purpose of the timestamp and related variables ( GRACE_PERIOD | MINIMUM_GAP ) is for decentralized throttling, not a trustworthy reporting of time. However, in a pinch, these timestamps are better than nothing to identify the time at which a request was sent, which adds a small bonus for some forensics.

Can you please explain that further?

5 Likes

What would happen in this case:

GRACE_PERIOD: 00:01:00

Node 1 local time: 05:00:00
Node 2 local time: 05:00:10

a client broadcasts a send with a timestamp of 04:59:01.

For Node 1 it is a valid transaction, for Node 2 it is not. Would a vote be required in this case?

1 Like

It is correct for both nodes, but second node will not put it into priority queue.

2 Likes

There is also a rule - trivial, but needs to be implemented that Receive has the later timestamp than corresponding Send, otherwise Attack 3 can be successful.

I am not sure if there is some antics possible with faking timestamp, like, suppose I'm going to do double-spends (because double-spends need more communication rounds between nodes), and I'm going to first spend in the priority queue, and the second to the normal queue, wouldn't it slow the stuff down?

So sounds like it would be in the best interest of the send to have a timestamp as close as possible to the clocks of high weight PRs to ensure they reach 50% of votes as quickly as possible. And also hope that high weight PRs keep their clock from drifting from the rest of the network.

As for Attack 2: Mass Account Spam
How would this system work if the theoretical attacker is sending non-trivial amounts to new wallets? Say in this example of 1,000,000 Nano, the attacker sends 10 Nano to 100,000 new wallets. This is certainly a higher value than some legitimate uses of the network.

For the most part. The PoW becomes optional, I think, since the network is modeled under the threat where a bad actor has infinite PoW anyway, though I've yet to see any convincing reason to remove it.

However, how "sporadic" previous transactions are doesn't really matter. The grace period is intended to be a relatively short metric (measured in hours at most), not something that takes into account full node histories. Else a user could just build up an enormous grace period over a very long period of time and use it like a capacitor on the network.

It creates a new attack surface altogether, which is denial of service via timestamp desyncing. Right now, Normal Queue submissions are still valid -- they just get de-prioritized -- and the Herd Immunity effect that this adds to the network would still protect them from spam. However, if you prevent these transactions altogether, then this means that de-syncing someone's local time would cause them to fail the network altogether.

Additionally, I don't think that this offers any protection against ledger bloating attacks. A malicious actor could still spam the network successfully with a ledger-bloating attack by just infinitely chain-sending 0.00001 Nano in an endless path to a newly created account. Every account would just have two transactions in its chain: OPEN + RECV -> SEND. They'd all be in the Priority Queue as well, so filtering out Normal Queue entries would do nothing to prevent ledger bloat.

Correct. To prevent deadlock, nodes would need to recognize when the majority of the nodes are actively reaching quorum on some other transaction. If it sees that it's apparently desynced (i.e., what it thought was the voting transaction is actually within the Normal Queue according to most nodes), it would need to recognize that after some time and continue on in step with the rest of the network.

Yes! I listed this as "Rule (4)" in the rule list above.

I've considered this, but I suspect that this implementation actually fixes the issue of double-spending in this manner, right? The global network would reach a consensus on the first (timestamped/Priority Queue) request, and then they would all see what is little more than a "late to the party" request.

This is actually a two-stage attack.

Stage 1: Invested attacker sends 10 Nano to 100,000 accounts.

This gets solved exactly like Attack 1, because the sender is a single account and thus rate-limited to their BURST (i.e., GRACE_WINDOW / MINIMUM_GAP).

Stage 2: Individual wallets all call RECEIVE on their new 10 Nano.

This is basically an Attack 2 whereby the target threshold (and, thus, DoS limit) is everyone who has under 10 Nano.

You're right that there are some legitimate users of the network below 10 Nano. The question becomes one of "how long can this be sustained?"

A better example might look like this: a malicious actor with 1,000,000 Nano divides it among 100,000 accounts. They all have 10 Nano now, and so they all start sending 0.000001 Nano to random addresses at their maximum rate.

Tweaking of the MINIMUM_GAP would be needed to ensure that this attack wouldn't be able to be sustained. For example, a MINIMUM_GAP of 100 would mean that all 100 accounts could only produce a cumulative total of 1,000 requests per second. If the maximum TPS of the network is higher than this, then it's acceptable.

The trade-off is that the MINIMUM_GAP determines the rate limit applied to legitimate users during a spam attack as well. This means that if <= 10 Nano had a MINIMUM_GAP of 100 seconds, then they could only sustain sending 1 transaction per 2 minutes... during a spam attack. Of course, when a spam attack is not going on, they could exceed this threshold by dipping into the Normal Queue.

1 Like

Actually, we need to somehow come up with MIN_GAP(STAKE) function.

I suggest having MIN_GAP = CONST/STAKE, that way if attacker subdivides their weight into two wallets these two wallets will be able to spam with similar speed as the big one (provided grace period is the same).

The main thing that concerns me is how big should the GRACE_PERIOD be? Can network be spammed into the state where response times are > grace_period, effectively removing priority queue? And if grace period is too big, there are more possiblities to spam priority queue? Can nodes update it dynamically from some heuristic?

I've thought of a potential new attack on this network, which I'll call a waterfall attack.

Say the attacker has 1,000 Nano, and wants to cause as many priority queue transactions as possible. Instead of sending a tiny amount of Nano to many addresses the naïve way, they can send 500 Nano to two accounts, each of which sends 250 to two new accounts (with the appropriately incremented timestamp) and so on. This attacker can split their 1000 Nano into 10^34 1 raw transactions in just 109 dividing steps, at each step doubling the number of transactions and halving the transaction value. So even if the time interval they have to wait at each step is fairly large - even hours - the exponential nature means they only need to cover a small number of steps to split their funds up into an extremely large number of accounts that can spend those funds.

OK, suppose we have an attacker with 10^6 Nano. What is TPS that we are OK to have from them? I think right now we can not process more than 200, suppose after some growth we can do 10^4.

Then it will make people with Nano to have 10^-2 TPS, i.e. 1 transaction in 100 seconds. Which is reasonable in case of spam (while disrupts some applications like tip bots and stuff, but can be fixed by adding a bit of funds on these intermediate accounts).

With 10^7 attacker coming to screw Nano network in the current state (200 TPS max), the network will become barely usable even for people with 10 Nano - they are allowed 2 * 10^{-4} transactions per second, i.e. slightly more than 1 in two hours.

I am not sure if there can be some permanent deterrent against spam except either fees or PoW. I'm, personally, for PoW.

It doesn't do anything good if these moondust accounts have low MIN_GAP. If MIN_GAP is inversely proportional to stake then any splitting of funds does exactly nothing, I think.

This is a good point, halving the balance should at least halve the priority otherwise balance splitting is advantageous.

Is there any reason for GRACE_PERIOD to be dynamic? If not, then MIN_GAP = const/STAKE sounds natural.

Also, I have the following suggestion: DPoS4QoS. Allow people to vouch for wallets (1 wallet can vouch for only one wallet, redelegation is a transaction). Vouching for wallet adds to its stake (non-transitionally, of course). That way, people will be able to vouch for useful services like bots and make them have high priority.

I think making MIN_GAP merely directly proportional to balance still has an issue. Those splitting transactions themselves are network activity that only pays half the expected time-fee. The receives may be deprioritized but the sends won't be. I can't express it clearly so am probably mistaken, but it feels like the attacker still gets half a free lunch here.

One thing I've been mulling over is that this prioritization should be made in terms of the current actual TPS. If there are 10,000 transactions queued and the network can process all of them at once, the priority doesn't really matter whereas if the network can only do 10tps, it's entirely different.

Keep in mind that each RECEIVE would need to be be timestamped based on the sending timestamp plus MINIMUM_GAP due to Rule (4). As a result, this would not work beyond 2^MAX_BURST depth -- even less, because MAX_BURST would decrease as you go to lower Nano levels.

If your priority is equal to your stake, then halving the balance does exactly that.

We would be protected in two* ways:

  1. The MAX_BURST mention I made above due to Rule (4).
  2. As you get down to progressively lower tiers, their stakes are exponentially lower.

Let's consider that MAX_BURST issue. If 1,000 Nano means you have a MINIMUM_GAP of 100 and a GRACE_PERIOD of 300 (GRACE_WINDOW of 600) then your MAX_BURST is 6.

With that, _and not including the fact that MAX_BURST would go down due to lower PoS's, this is the resulting amount of transactions that you could make at each PoS tier:

1 @ 1000 (T = -250) [giving 50s for drift]
2 @ 500 (T = -100)
4 @ 250 (T = -50)
8 @ 125 (T = 50)
16 @ ~64 (T = 150)
32 @ 32 (T = 250)

32 + 16 + 8 + 4 + 2 + 1 = 65. AKA, with a MAX_BURST of 6, you can achieve at most 2^6 - 1 requests, with the biggest bulk (half) of these requests occuring at STAKE / 2^5.

Using other numbers: say you have 10^5 Nano and a MAX_BURST of 10. Again, omitting the fact that this value will decrease as you lose PoS due to the increasing MINIMUM_GAP, you would get the following:

2^10 - 1 (1023) burst requests
Half of the requests would happen with a stake equal to STAKE / 2^9 (10^5 / 512 = ~200 Nano)

The biggest thing to take from this here is that MAX_BURST should scale down quickly as you move from 10^6 (where exchanges might have a legitimate reason to have a MAX_BURST of 1000) to sub-10^4 (where retail users will basically never need to burst more than 5ish transactions because, let's be real, when do you ever personally swipe your credit card more than 5 times in a short period?)

It's a variable to tweak to ensure that MAX_BURST does not get too large (or too small) for various stakes.

Consider: an exchange might need to sustain 10 TPS and burst 1k TPS. Their GRACE_WINDOW would need to be 1k/10 = 100.

A user might need to sustain 0.01 TPS and burst 5 TPS. Their GRACE_WINDOW would need to be 5/0.01 = 500.

One thing to beware of here is that if you start being restrictive with the Priority Queue under a heavy load, you are actually playing into an attacker's hand: you are forcing more legitimate requests out into the Normal Queue where they actually have no protection from the spam attack itself.

The system can already self-solve for the instance where the network can process all outstanding transactions: the Normal Queue. If a user wants to burst 1000 requests but has a MAX_BURST of 5, they can say "screw you" and just issue all 1000 requests into the Normal Queue. If the network can handle it, it will. Even if they're prioritized at the "end" of the network, they still get processed.

I.e., there is no gain to the network to acknowledge when it can process everything. If it can process everything, it just will.

1 Like

(double post)

I've been thinking of a way to more mathematically structure this system.

Let's estimate the outstanding number of Nano (TOTAL_NANO) at 100,000,000 (108), for easy-to-work-with numbers.

Let's estimate the maximum transactions per second (MTPS) of the network at 10,000 (104). I think that's more than recent tests show, but realistically it must be at least this high in order to be competitive long-term IMO.

If you were allowed to send data into the network at a maximum rate directly proportional with how much of the network you own, that would mean that your MINIMUM_GAP is defined as follows:

MINIMUM_GAP = 1 / (%OWNERSHIP * MTPS)
MINIMUM_GAP = 1 / ((STAKE / TOTAL_NANO) * MTPS)
MINIMUM_GAP = TOTAL_NANO / (STAKE * MTPS)

For an account with 10,000 (104) Nano, your MINIMUM_GAP would be defined as 10^8 / (10^4 * 10^4) = 1.

By using MINIMUM_GAP in this sense, it becomes effectively a mathematical SLA that says you are guaranteed, in the worst sustained case scenario to get your request out once every second.

What constitutes a "worst sustained case scenario?" A worst case scenario is assuming that every other Nano on the entire network is owned by a single entity and that other entity is sending all of their Nano at a sustained rate as fast as possible.

With this solution, you can mathematically prove that every single user in the network would be guaranteed in the worst sustained case scenario to get their request filled within a mathematically-defined SLA. It would not be possible to spam the network in such a way that any user, even 0.000001 users, would be permanently DoS'ed. (although these users many have SLA's that measure in the order of thousands of years, heh).

The primary thing I dislike about this is that it results in exchanges getting more TPS than they need (10^8 / (10^6 * 10^4) = 100 TPS) and the poorest users getting less TPS than they need (10^8 / (10^4 * 10^1) = 0.001 TPS).

However, it may be possible to smoothen out the curve in a very beneficial way by increasing the amount of TPS that richer users gain in a logarithmic manner. Speaking intuitively (haven't solved the math), this would likely resolve in more beneficial numbers BUT a permanent spam attack of undetermined value would become possible if the attacker owned something like 33% of the network.
Just food for thought, if anyone is interested in taking this thought process the step further into calculated, mathematical proof territory for MIN_GAP and such.

2 Likes