There are no public implementations resistant to 51% attacks.

Ok, now to your question.

My current understanding: through blockchain you can't resolve it. You need to have been online during one of the 1 to K blocks and have seen for yourself that the signatures were indeed broadcasted. Then you can be sure that (K+1)th SH is the liar.
The honest nodes will then take action to suppress the (K+1)th from the network and enforce their opinion. For example, all the communication related to the false chain is not relayed by them. So it's a kind of vote of the whole network.
Now if the attacker has a significant portion of the network as well, he can form an appreciable fork. There it becomes harder, and the users will have to interfere. Those who missed the fork buildup (and therefore don't know the truth) will have to decide which chain they're going to be on. Etlase2 proposed some trust-based solutions. All the real people who are not the attacker will either know the good chain, or be undecided. So you could run a vote among the people whom you believe to be real.

I hope Etlase2 can comment as well.

Sorry AnonyMint, but I think you either don't know what you are talking about or bring confusion on purpose. "preimage the entropy"? "can't be a preimage because every peer is racing to compute it"? What is that supposed to mean?

"I can choose a seed a priori"? I've just proven that this is impossible.

I don't think this will be a productive discussion until you educate yourself enough to understand the arguments. Visit the "preimage attack" wikipedia page that I've linked, play the little md5 seed game. It will help.

That cost is going to be very high. Bitcoin is built around the hardness of this task, only they try to find a partial preimage, while we're talking about finding a full preimage. So if you can choose the seed here, you'll have no trouble killing bitcoin as well. For some hashes this has not been accomplished even once: https://en.wikipedia.org/wiki/Preimage_attack
So you don't get to choose your seed.

This is silly, it's like saying "I got this encrypted message, so I can decrypt it by enumerating the key. So the encryption is useless." Yes you can, go on.
If you still find it difficult to understand, play a little game: imagine the seed is MD5 hash (that's a "weak" one), and the transactions are written in ascii text. The first transaction says "Transfer 5 decrits from account 1 to 2." You choose the next transaction(s), concatenate them with that string and compute the MD5. Now try to have the result of all zeroes. If you succeed, post your transaction here.

First, the IDs are chosen, and then you know the seed. Not the other way around.

Yes. Still it may be very difficult, but it's safer to use the "random" input.

On wikipedia there's a passage about some patent application: http://en.wikipedia.org/wiki/Bitcoin#Satoshi_Nakamoto
I think these guys are him

The seed could be the hash of all transaction in the previous CB. You can't control the value of a hash, that's a major point of hashes: you can't find the content of a transaction which, when concatenated with the other transactions, will result in the given hash value. So you can't control the seed even if you control a part of the transactions.

Furthermore, you have very limited control of IDs of your SHs. They're assigned by the order of their appearance. And they're decided before the seed for the next CB is decided.

Since there is no control of the random generator, you'll have to resort to bruteforcing it. In order to prevent that, I proposed fixing all the seeds completely and not using any "entropy" by your terms. While this complicates the attack significantly, it's still not bulletproof. Maybe it's easier to deal with the possibility of bruteforce search of a favorable seed. If the proportion of shares that you own is p, to have n consecutive TBs you'll have to enumerate (1/p)^n seeds. For n=360, an hour of disruption, and p=0.9, a 90% attack, you will need to enumerate 29695907506101728.772544490140544 seeds on average. We can live with that.

Bitcoin's 51% works like that: you create your own blocks in secrecy, however many you want, while you have the 51% advantage, and then release your chain. It will be longer than the honest one, so all peers will abandon the honest one and take yours, with whatever you put there. Not only you have continuous control of TBs proportional to your hashing power advantage period duration (which is the cost of the attack), but you can reverse the already accepted transactions, which you can't do in your weak attack on decrits.

But we are not in the future, we're now and you said you want to place the next TB under your control. The only way to do this is to spend money or wait. You can't wait because then you'll lose the next TB. So you need to spend money continuously. That little program can simulate that.
If you wait a really long time until the current ID count is favorable, your percentage of the overall SHs will be lower, because all the IDs which you've skipped are not yours.

Ok then. Now we need the computation of how much you will gain exactly. If you come up with precise number, like I can gain this much (percent) for every day of continuous control, we could see how much you'll need to spend to achieve that. Then we will see if there's a situation where the attack is profitable.

Yes, for a limited period of time growing with the cost of the attack.

Not really. You may be able to gain some resources, but how much they are, compared to the considerable cost of an attack, is an open question.

Agreed. But let's assume that the locking time is much greater than the time of possible continuous control. You can't recycle your funds which are being unlocked to prolong the attack.

Say you have money to buy 2000 shares and there are 1000 honest ones, so it's a 66% attack. You buy one, the probability of you to not be the next is 1000/1001. If you've lost, you buy another, now the probability is 1000/1002. And so on. How long do you think you're going to hold the TBs on your side?
The answer is 2000 TBs on average: https://ideone.com/qnSuyP
You can play with different values yourself there on that website. After these 2000 TBs, for 10s TBs that's 5.6 hours, you fund is locked, and you can't control the things anymore. What did you gain? If that's the decrits-killing attack, I'm not impressed.

No, because you'll quickly deplete your funds, they'll all be locked in shares that you deposited while gaming the order of TBs before. When you'll have no more money, you'll have no further control over the order of TBs, but the honest SHs keep arriving.

Only assuming the infinite ability to create SHs, which you can't - there's simply not enough money in the system for that, it's a finite amount at given time.
Increasing the share amount and deposit locking time will make the power even more limited.

Yes, my argument is exactly the same. Make arbitrary placement of ID cost a lot of money or time.

I just try to understand his point. After all, the issue is very simple. Much simpler than the other outstanding problems, like disconnected nodes.

Which ID do you want? How long do you wish to wait?
No, the rate of honest SHs is fixed and does not depend on how many SHs you possess currently.

Sure it's known, and what? Suppose you know that you'll sign TB#35677 in the next day and TB#22789 in the day after that. What power does that give you compared to the case when you didn't know that? How to exploit that power?

I'm not even using the word "entropy".

Until you present a working attack on a very simple, fully specified by now algorithm which per your claim breaks the consensus completely. I want to see it, that's all. I've even offered to code your attack, just describe the algorithm in words. Now you're in position where Etlase2 was some time ago, remember? He managed to give the algorithm after some time.

No, we're not done yet, one more circle of nonsense is necessary, I'm afraid. Your SH application will not be accepted if its timestamp falls out of the current TB (how long was that? Make it a minute). And the timestamp doesn't decide your ID, it's the order of the timestamps. So that the earliest timestamp has ID=1, the one after ID=2 etc. If you want to have an ID of 1000000, you'll have to wait a until a million other SHs register, that's quite long.

If you want to game the system you have to give me the algorithm. You may be forgetting that I chose a very strong cryptographic random number generator which is difficult to "game". And also you'll have to explain what your attack should actually achieve.

Timestamp ordering of the initial SH deposit transaction. In case of two peers applying to be an SH in the same nanosecond, lexicographical ordering of a hash of their deposit transactions decides. I believe this could not be an issue because only the same guy could realistically synchronize the timestamps with that precision, so he can only decide the distribution of a continuous sequence of IDs to his own SHs. But if you can exploit that in your attack, you're welcome.

To set the numbers straight, suppose that the honest SH count is a Poisson process such that there is one SH registration expected per hour.

Okay, okay, that's an assumption. This assumption is stronger than those made by bitcoin. It's a start. Before, I thought that it's impossible to know the truth at all by passive observation, now it turns out that you need to disrupt the communication severely to prevent that. If broadcast is not working at all, the network is split and the situation is hopeless. If it works, but slower than usual, then we need to evaluate how much slower it can be made, how this could be prevented, etc.

At least there is a grade of how long were you offline. The nodes connecting for the first time ever are the extreme case. A node who missed one message is probably easier to handle.

Well, now there's an algorithm, we can get down to business. Like, calculate what a particular ID allocation strategy could give you, in what time and for how much money
One thing I didn't specify is the random generator to use. Lets settle for HMAC_DRBG from http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf initialized with the first post of this thread as it is now in UTF-8

No, that's not so unreasonable. It's not true, of course, it's an assumption, but in a highly connected network the broadcasts are quite reliable. You can try to amuse yourself by computing the probability of a message being not received by a peer when everyone is connected to N other peers, as a function of reliability of a connection and size of the network. Imagine that everyone passes the message to all neighbors once upon receiving it.

Now with not-always-online nodes there may be problems, but again these could be addressed to minimize damage to them.

So the whole issue is based on the ability of SH to choose their IDs? Let their ID be their number in the SH sequence. So the very first SH has ID=1, the one who registers after him ID=2 and so on. Their order for signing TBs is determined by a chosen good pseudorandom number generator in [1..number of SHs at the moment], initialized with seed value of 0 at the very first TB.
Not good? Please provide an algorithm to gain significant control over your position in TB signing queue with that (good luck). We can test it right away, I'll write the program SHs have very limited control over their ID now, they can just wait until the number grows to their desired position, or fill the IDs by creating a lot of SHs, which is supposed to be costly, and your resources are limited.

I skipped the rest because it was all based on this.

That node itself cannot be fooled. For example, assuming that everyone is always online, the system is perfect already (under the other assumptions, of course). It's a starting point which shows that the truth can be established at least under some assumptions. Now the next question is how to relax those assumptions, to make the system more fault-tolerant, such that loss of some messages could be compensated, for instance. Etlase2 did some steps in that direction in the detailed descriptions above.

This one please. What exactly do you mean by "randomized", and what kind of attack you imagine if this property is not present?
In cryptography "random" usually means "unpredictable", which cannot be the case here, as you say in point 1. Why can't we just let SHs sign TBs in alphabetical order of their IDs? If this is bad for some reason, there's an infinite number of other ways to do it.

Depends on what definition you will give to randomness in this case, but in general "the only way" is always a very strong statement about an algorithm, which can practically never be true. You can only say "the only way I'm aware of currently". The "entropy of signatures" and its use to find the order has to be explained, after you explain the need for it in point 2. above.

Every peer will decide for himself. Remember the assumption of bounded time guaranteed broadcast.

Even if that solution didn't work out, there is no proof of this statement.

Now you came up with another argument, one which is completely unrelated with what was discussed yesterday I must add, and pretend that you've closed the question. You argument includes no details, just a keyword. That doesn't work that way, you didn't convince me of anything - I didn't follow the entropy talk of the last month. As I said, either an attack is spelled out, in whatever form, or it doesn't exits.

It's ok for me if you don't want to continue the discussion, you don't have to. The final answer should come out of an implementation anyway, not from the arguments.