Ledger bloat problem and possible solution

I posted a suggestion on r/nanocurrency an they told me that this forum would be more appropriate for post like this.

In the case that the Ledger pruning become reality this idea may mitigate the Ledger bloat problem, in particular it aims to solve the Penny Spend Attack.

In practice, each wallet must be coupled by a value (nonce) that satisfies:
hash(address + nonce) = [N BIT TO 0] [REMAINING HASH]
where hash is a ASIC resistant, GPU proof hasing function; N is the difficulty.

The difficulty could be set to a value that about 1h is needed to find a valid nonce: to create a wallet you need to dedicate a CPU for one hour to this task. Once the nonce has been found the wallet is ready to send and receive Nano. (1h is totally arbitrary I don't know if it can be a reasonable time)

To send Nano from wallet A to wallet B the sender must also provide the nonce of A and B or the transaction will be rejected. When a receving address is shared (for example through the QR code) the nonce must be included or the sender will need to find a valid nonce for the wallet (computationally expensive).
An attacker who wants to make the ledger bloat would have to create hundreds of thousands of wallets, with an absurd computational cost.

Another suggestion derived from the comment below says that could be more convenient to increase the already present PoW difficulty only for sending Nano to not opened accounts.

10 Likes

Hmm, I like it.

I think the addresses would just become the concatenation of the public key and the nonce. Higher levels would treat addresses the same, they'd simply be longer.

This contrasts with the high-difficulty open-block strategy which only slows keypair from beginning transactions; this prevents addresses from even existing which cuts the penny spend problem down at the source instead of the destination.

In the long term, this could help with signing schemes that have larger public keys by ensuring references have an associated account.

In the block, this would require widening the address and link fields.

4 Likes

I'm struggling to see a big downside to this. Though how much additional work/delay does this put on a node to verify the nonce? Or does it just get grouped with an existing verification process?

It's hard to think of a valid use case for sending low value transactions to thousands of random (likely unopened) accounts. But this seems to be one of the most difficult attacks to deal with without losing full functionality. (Assuming pruning is active)

Some quick math (If I'm doing it right), for a 5 minute hash, it'd only cost $0.002 (elec) per acct opening but it'd require 17,000+ hours of hashing for a spammer to drum up enough valid sends to add just 1 GB to the ledger (not including the required send PoW). Seems clear to me that spam deterrents will end up being time not $$$.

As you both said, for good actors this just looks like a longer send address (base address generated from seed + a valid nonce) and it doesn't make it impossible, just much slower, to do a valid send to an address with unknown nonce.

2 Likes

This is an interesting approach. It would put additional pressure on wallets who bring on new users and exchanges or other services which best function with 1 address/user setups. Would definitely have to wait until a solution for payment IDs is in place so individual addresses isn't the primary method of capturing unique payments, to avoid disruptions to services, etc. They would have to migrate to get all user account existing nonces as well, which would drive some initial cost for their existing user base. But long term appears to be an approach to consider.

5 Likes

Aside from that, the other use case would be tip bots that create a ton of custodian wallets for non-users.

1 Like

I like the concept, but I see some potential issues.

  1. Creating a wallet may need some time. I guess people would like to create they wallet and use the wallet immediatly.
  2. This is more computing on small devices.

So, here an idea how to maybe get around that.
How about having a similar concept as the representatives? Like one address which satisfies this value is able to "verify" x other addresses.
The idea being here, you can create an address, but before you can do transactions you have to satisfy either the value or some other address has to "vertify" your address.
So when people create a wallet and transfer the funds from the exchange to their wallet, the exchange also "verifies" the address and the user is able to use the address immediatly.
For use-cases for smaller devices, I am able to satisfy this value on address and can "verify" a bunch of other addresses for my devices. Without calculating it on the device directly.

A prolonged computation for new address creation seems like a reasonable trade off. Significantly better than a minimum account balance.

6 Likes

This would depend on if you could vary the computational power required for the nonce would it not? If it can be varied then a stepped rollout may work. The first update would role things out with an extremely low nonce calculation requirement and then a second update a few weeks later once existing services have acquired a nonce for existing addresses to up the calculation requirements for addresses created beyond that point.

Or perhaps a rollout of a predefined nonce attached to all existing addresses in the first wave.

1 Like

Given the asynchronous nature of the network it can be difficult to do multi-phased rollouts for things that affect transactions validity, consensus, etc. A good summary of these methods can be found here: Network Upgrades - Nano Documentation

With those limitations in place, it might need to involve some canary blocks or maybe timings could be used, but that is much less flexible since they have to be hard coded into a node release.

Based on your response, it sounds doable with some careful planning then.

In this case could not the nonce work as a sort of checksum in an on itself?
Also why can't you keep the nonce outside the signed block (so that you don't need to increase account/link fields on the block)? I imagine the node would keep a list of frontiers + nonces so that every time you need to send to an already used account you could add the nonce, instead of keeping the nonce on every block.

If someone uses a different valid nonce for the same account, the nodes validates the same way it would anyway (hash) but just don't add to the local DB of valid nonces since it already has one.

Also while I like this idea, I can't seem to find a good way of balancing user experience with prevention. A long enough time to actually deter a bloat attacker seems to be too much for a user, a low enough time to not impact significantly a user seems to not have the desired effect vs an attacker.

1 Like

I have read a few topics around the forum and if I'm not mistaken this approach could also mitigate the misuse of the "Representative" field to save data as it would not be possible to enter an arbitrary address.

That's a really good point, it probably would.

I was thinking a bit on how to associate the nonce with the address, the previous idea was to concatenate them and lengthen the address.

It seems an alternative is to 1) require that the account already be opened by the recipient, if it doesn't, the block would be rejected and 2) Allowing accounts to be opened with 0 balance, without a source block, provided the open block has the high difficulty nonce.

This alternative appears to be a cleaner approach. It would also avoid repeating the value of the nonce in every send and change transaction.

However, for each send and change transaction it is necessary to check that the recipient account has been opened, while in the other case (address widening) the "proof of open account" would already be included in the transaction.

1 Like

Yea agreed, it does take an extra lookup but the savings both in the smaller transaction size and UX of a longer address seems like it is a good tradeoff.

The transaction processing step already does a few disk lookups so I don't think it will affect performance greatly.

How about adding that the sender is also able to open the account, if it isn't opened yet? So it's like delegating proof of work.

Just going to caution that if it's required that a recepient's account already be opened most people lose the ability for a "cold" or "air gapped" wallet.

Good point. That also shouldn't be an issue, if you have some kind of mechanism to delegate this opening account. For example by giving a sender the ability to open it as well. Or you can have an additional list of accounts which are considered to be opened, even though they don't have the "proof of open account".
You can add it that transactions are accepted, even though don't have it, but when available in the client, the client also just creates this proof. You can remove the accounts from the list which got opened on every node updat. So that eventually you can remove the whole list.

Would the proposed alternative not have any issues with the asynchronous nature of Nano? The validity of a send block would essentially rely on the state of another (the recipient's) account chain, which could cause a race condition where one node sees the account as open, but another doesn't. Would this simply result in the block being dropped and not reaching quorum, or are there other potential issues to consider with this?

but open would need a send block into the address. if you reject send blocks to unopened accounts you get a chicken/egg problem.