Quote from: phillipsjk on October 07, 2011, 05:09:11 PM

You fail to explain

Yes. I currently fail to explain.

The thread started out trying to understand why the current PoWs are completely parallelizable. Throughout the discussion I realized that different PoWs might be better. I do not yet have a completely convincing argument for or against a specific form of PoWs (although my guts are telling me, there could be some advantages for non-parallelizable PoWs). Since I did not see an argument why the PoWs must be the way they currently are, I spent some 20 hours researching other possibilities. I do not have a final answer yet but I am developing some systematic approach to settle this question. Currently I am convinced this can be done, but this still will need a bit of time (and I am not working fulltime on this issue as well).

Quote from: phillipsjk on October 07, 2011, 05:09:11 PM

why a completely serial Proof-of-work would be better than the current system.

A completely serial PoW clearly is not better but just does not work, as you point out in your posting.

I suppose that a non-parallelizable PoW may be better. Our current PoWs are parallelizable to an extreme degree. Maybe the optimal situation is something in between.

Quote from: phillipsjk on October 07, 2011, 05:09:11 PM

Verification requires the proof-of-work to be repeated by every node. If there are two competing POWs sumbitted, the network must stall until at least 1 is verified. Some nodes may elect to blindly start the next proof-of-work without verification, but that only compounds the problem.

According to my current understanding: No and no.

Verification could use some kind of trapdoor mechanism and thus be faster. In the literature there are some non-parallelizable PoWs with faster trapdoor verification, however they have the issue that the trapdoor secret must be kept secret. One of the natural approaches to this is to share or split this secret (which could lead to a significantly more complex protocol). While I do not buy into Verification requires the proof-of-work to be repeated (there are counter examples) I do not have a working example either (at least by now...)

Also, I am not yet convinced that a verification, which takes a bit of time, really is a problem.

Quote from: phillipsjk on October 07, 2011, 05:09:11 PM

Edit: You brought up trust. It appears you want to eliminate "wasted" computations by having a distributed central authority choose the winner ahead of time. If that is the case, why use proof-of-work at all?

In Bitcoin, I think, the PoW serves additional purposes next to choosing a winner and making a majority consensus be a winner. For example, it also provides some kind of clocking in the block chain which slows down the transaction rate (which ensures that the probabilistic gossip does not go out of control). It may contain some kind of inbuilt DDoS protection as well.

Actually, Bitcoin realizes some kind of distributed central trusted store.

The ideas I mentioned on trust are far down the road and still need more time of thinking. My interest here is along the "proof-of-stake" idea mentioned by an earlier poster.

With regard to distributed central authorities: Most algorithms for distributed central authority of which I know have some other nasty problem. Either they scale badly (usually in number of communications). Or they make unrealistic assumptions (like having a common trusted random noise generator, or having a pre-shared common secret etc). Or they pose problems in ad-hoc networks with an unknown number of nodes joining and leaving the network. Or their description looks so awkward that I did not muster up time or courage to understand them. Bitcoin therefore fascinates me, since it seems to be a good mix here. However, Bitcoin does not seem to very well understood from a formalized approach and many design choices (to me) are not as obvious. Also it lacks strict complexity analysis. That's why I love to poke Bitcoin once in a while and understand what happens when a core part gets modified.