Ok, if you really don't understand: all wallets will use some strong cryptographic hash to determine the index of an entry of that table. They will hash the item along with some big random salt (unique for each wallet).
I really do understand this. It doesn't make a difference, because the user chooses their salt, their address, and which hashes to generate levels from or not... so they control their *own* hash selection. It has nothing to do with other miners, other wallets, other anything except for the hashes the users mine into this list/tree/hashtable/whatever state history.
They will NOT use first bits of plain item data as an entry index.
Miner will NOT be able to select specific levels for degeneracy attack cause he will in fact not know what hash function each node use for that table.
They do know the state of the table at any given moment, and for any given hash can determine if adding that hash would make that state more or less degenerate, if it would drive complexity up or not.
If they can affect this distribution of the hashes along a sort order, then they can affect the complexity of future searches by selectively completing hashes that `fall into the sort` in a way that leads to a degenerate complexity. (In other words bail out of the work function after "just" the sha hashing to generate the level if the level does not hash to something within some selected deviation of some desired statistical distribution.)
In other words, they can choose to make their mining work over time "push" away from the average case by working toward building particular
non-uniform distributions into their hashes, and "build out" structure that tends toward worst case. As such, we *do* have to consider both average case and worst case in such an index. It is the only way that we can answer "how bad *can* it get under attack?" to know if it would likely kill the network in a day of attack, a year of attack, decades of attack, or more.
Can we at least agree that there is a zero point at which the size of the set would overwhelm average block time, even if we could only show that time as being eons from now? Can you understand why I would ask you to establish what that timeframe would be before enacting the change?
Of course at the end of the day it is somewhat of a moot point. You have >51% of the network and can effectively do whatever you want with your chain.... so make a patch, put it out there for the world, and start mining on it. We'll see what happens?
The only problem is that those hash tables will not be interchangable between different wallets. Is that a problem?
Generating the table per-address probably makes the problem slightly worse, because then the miner doesn't have to worry about anyone else affecting the state of his hashtable's distribution as he works on extending it out to be increasingly degenerate.
Anyway, limited time (24 hours) solution will be simpler and enough and I'm absolutely not insisting on using that hash table.
Yes, I think this much we can agree on! Putting known finite bound(s) on things often obviates questions of complexity in this way. (Shameless plug for tauchainzennetcointhingy, heh...) So let us just go ahead and put the "check for duplicates" based approach behind us, and leave the complexity concern of level duplication checks as an academic exercise for the reader?