Proposal to prevent Precomputed PoW Attack

[manjalyc]

A past closed discussion looked at mitigating a precomputed PoW attack by appending a random prefix string (#493):

A valid block must have a nonce such that the nonce concatenated with the previous block's hash maps to a value below a certain threshold under hashing. Proof of work involves trying several different nonces before we find one that meets our requirement. We can roughly think of a number being below a certain threshold as having a certain number of zeros as its prefix. The number of zeros we require sets the difficulty of PoW. Suppose instead we require a random string of bits of a fixed length to be the prefix (instead of simply zeros) and the network agrees upon a different random prefix string every few minutes. However we keep the length fixed. Thus we make the PoW requirement dynamic, at the same time not making it any more difficult for honest users.

The biggest issue seemed to be getting the network to agree on a prefix string without any form of centralisation/significant overhead.

Start with an n-bit prefix string, for example a bit-pit prefix string of 00110110. Every x hours representatives randomly choose between a 0 and a 1 and broadcasts it to the network, at the end of this (lets say x=3) hour period whichever number has the most stake (not in terms of representatives, but how much nanocoin each representative holds) the 8-bit prefix string changes as such:

(assuming '1' is the consensus)

1. take the original 8-bit prefix string and append the digit with the most stake: "00110110" + '1' --> "001101101'

2. now remove the leftmost bit to get the new 8-bit prefix string prefix string: '01101101'

By repeating this process within 24 (8*x) hours a prefix string won't contain a single 'same' bit it had 24 hours ago. Of course the number of bits and time period between prefix string updates can be changed. It would only fail in the case all decentralized networks struggle - an attacker has >50% of active voting stake. This method would prevent a precomputed PoW attack while not relying on any other networks and remaining decentralised.

[Ethunxxx]

Maybe I'm misunderstanding, but wouldn't this mean that the PoW couldn't be precomputed in general (even by legitimate users)? If implemented, every PoW would have to be computed right before the transaction, right? If that's the case, I believe this would be detrimental for a lot of users/use cases.

[manjalyc]

Leniency could be built in to allow for prefix strings within the past 6 or so hours (accept the kth string, and k-1th string). If you want to predict the next prefix string for the next 3 hours there are only 2 possibilities no matter how many bits the prefix string is. For 6 hours there are only 4 possibilities, but it becomes exponentially harder to guess the prefix string the further into the future you wish to precompute. This allows precomputation within an acceptable range of time while making a precomputed PoW attack infeasible.

[Fiono11]

"Every x hours..." The network is asynchronous and nodes don't have a notion of time. One way that, perhaps, could be used to provide "synchronicity" to the network is trough the validation of a block whose hash fulfills a certain probabilistic condition. For example, a block hash with x number of zeros will appear on the network from time to time with a certain probability. When that happens, the representative of that block could initiate the process of updating the prefix string, announcing his bit. The other representatives will announce their bit when they see the block and add it to their ledger. When a bit has more than y % of votes, the prefix string is updated. The condition that the block hash must fulfill should be defined according to some metric related to the tps of the network in order to target a certain time for the updates, like every hour. The idea is to make this time the most consistent possible and minimize its manipulation.

[manjalyc]

Actually, there is a simpler (but somewhat similar) solution to deal with time/synchronicity, I'm going to give an example using a special transaction whose goal is not to transfer money but determine each bit. The actual implementation would vary significantly. Note I am using the terminology accounts/transactions as an example but in reality this is not a typical nano account/transaction but is special/restricted which I will explain after this example.

Lets say there is a user Carl who controls three accounts A, B & C. At any point in time two of the accounts have a balance of 0 with the remaining account have a balance of lets say 1 nano. Lets say the balance in account A right now is 1 nano (and B & C have 0 nano).

Every 3 hours Carl broadcasts two transactions, one transfers 1 nano from account A to B, another transfers 1 nano from account A to C. Only 1 transaction can be approved and every node randomly chooses which one to approve. At the end of that 3 hours, either account B will have 1 nano or account C will, and from this state you determine the next bit in the prefix string. Carl repeats this process every 3 hours, and in doing so, instead of monitoring and synchronizing the time, every node simply monitors the balance of accounts A, B, and C to determine the prefix bit, and just like that we have a new prefix string!

In this example, however, there is one problem - Carl. If one person can control when the prefix string is updated, there is a major problem in terms of centralization. To get around this is why these accounts/transactions are "special". Accounts A, B, and C will have their private and public keys published/known to the world. In addition these accounts are restricted in two ways. First of, they can only transfer nano to each other and not to other accounts. Secondly, these three acounts are rate limited by the network such that they can only conduct 1 validated transaction every 3 hours. Now within every 3 hour range instead of Carl sending the transaction, every node tries to send and validate a transaction either from A-->B or A-->C, when the confirmed balance of either B or C becomes non-zero the new bit has been determined. This avoids time synchronization, is "relatively" simple to implement (rate limiting mechanisms is really the only significant new feature - but they already exist on other blockchains so the ability is present), and maintains decentralization while using existing infastructure.

[Fiono11]

Secondly, these three acounts are rate limited by the network such that they can only conduct 1 validated transaction every 3 hours.

We reach the same problem. How do you measure these 3 hours?

[manjalyc]

How do you measure these 3 hours?

That's the beauty of rate limiting (or at least this proposed way to do so) - you don't. In a simpler sense every node only sends/validates a transaction between these accounts every 3 hours from the last time they did so. Once a majority of stake is in one transaction the transaction is confirmed. This means if every node limits their sending/validation of this transaction to doing so once every 3 hours, the account balance will only be updated every 3 hours.

Here's an example where we have 5 nodes (p, q, r, s, t) each with a 20% voting stake. Note when I say votes I mean the act of sending/validating a transaction between the account, also for the sake of using small integers lets say they vote every 5 minutes on sending money between accounts A, B, and C instead of 3 hours:

Lets say the following: p and q vote on minute 1, 6, 11, 16, 21... r and s vote on minute 2, 7, 12, 17... t votes on minute 4, 9, 14...

• Minute 0: Account A has 1 nano, B & C have 0
• Minute 1: p votes for B, q votes for B
• Minute 2: r votes for C, s votes for B
• B is now confirmed to have the 1 nano by majority active stake. (note that t has not yet voted but his vote does not matter and he is aware the balances have changed)
• Minute 3: Nothing
• Minute 4: t votes for A
• Minute 5: Nothing
• Minute 6: p votes for A, q votes for C
• Minute 7: r votes for C, s votes for A
• A is now confirmed to have the 1 nano by majority active stake.

If you continue this method, where nodes don't vote the moment a balance is changed but 5 minutes from the last time they voted there is no need for time synchronization as the balances will update a maximum of 5 minutes later. It is easy to see in this example how it may happen in 4 minutes if at minute 6 q votes for A instead. However, since in the real world there is way more than 5 nodes, the Law of Large Numbers in conjuction with some properties of 1-D Brownian motion in its applications to the approximate normal (high degree binomial) curves is enough to sufficiently show that on average approximately every 5 minutes the balances will change regardless of how evenly spread the voting is over the time range as long as each node votes 5 minutes after its last vote.

Edit: To summarize, when I say the network could rate limit these accounts, I mean each node only validates a transaction between these 3 accounts 3 hours from the last time they did so. In doing so it doesn't matter if Bob does so at hours 1,4,7 and Alice does so at hours 2,5,8 the balances will still update approximately every 3 hours. This avoids the need for time synchronization between Bob and Alice.

[npy0]

@Fiono11 to solve the issue of the network being asynchronous, perhaps, this network-nonce can be thought of as a chain. Let nodes vote and broadcast their pick at every x hours on their local machine time. Once you get >50% vote on a new network-nonce, nodes can assume that the network has moved forward x hours. Now, the local counter for broadcasting the next network-nonce can also be restarted. Change of network-nonce can be used to synchronise the network within a certain tolerance.

Think about it like this. Representatives send out their picks every x hours (local time). That is like a fork. Once the network resolves that fork, and confirms a new network-nonce, that becomes the frontier on which others can generate pow. The idea about "leniency" can also be kept to ensure that blocks don't get dropped because the network-nonce changed while they were propagating.

[rotemdan]

Edit: I've proposed the same idea in a more informal way on the Nano forum. I recommend reading that post before this one to understand the general idea and intention of this approach: https://forum.nano.org/t/precomputed-pow-dos/687/15?u=rotemdan

Edit: I did not initially understand how a nonce is used in the PoW algorithm but I now I believe I mostly fixed it.

---

How about something like this:

The computation starts with an initial nonce.

The initial nonce is hashed with the previous block: nonce = HASH(nonce, previousBlock)

Now the client is required to find the hash of a transaction satisfying the following requirements:

1. The transaction's hash is sufficiently close to the nonce (its prefix matches to some number of bits).
2. The transaction has been approved during the past x minutes.
3. The transaction originated from a sufficiently high-stake account (stake is measured by both value and age).
4. The originating account was responsible for a reasonable amount of transactions during the past x minutes (i.e. not a spammer).

Now set nonce = HASH(nonce, selected transaction hash) and repeat the same process all over again, several times, yielding a chain of transaction hashes (the originating accounts of the chosen transactions must all be distinct).

This sequence of transaction hashes will be sent along with the normal proof of work (which would be computed over the resulting "augmented" nonce) as an additional proof of recency. It is up to the nodes to decide if the proof given is sufficiently convincing based on their own internal clocks and view of the network.

I believe that this approach might be difficult to attack, if tuned correctly, as well as possibly allow for a recency time frame of several minutes instead of several hours. I'm not currently very familiar with all the details of how nano works but I thought this might be useful to post.

(The chaining is inspired by the Fiat-Shamir heuristic for non-interactive proofs)