Topic: [ANSWERED] Why is bitcoin proof of work parallelizable ? (Read 4656 times)

I took a few days to research this to a bit more detail and I think I have an answer to my original question and to some of the aspects which have been raised in the discussion. I will explain this in some detail using LaTeX syntax. At the end, I will draw a conclusion.

I use the following conventions: There is a set $N$ consisting of control words (aka nonces), which control the non-deterministic part. There is a set $P$ of PoW specifications. There is a result set $R$.

A proof of work is given by two functions $f: N \times P \to R$ and $v: P \times R \to {0,1}$. The PoW to solve is given by an element $p \in P$. The task of the miner is to find a control word or nonce $n \in N$ such that the result $f(n,p)$ satisfies the correctness condition. The latter is determined by evaluating the solution verification function $v$. If $v(p,f(n,p)) = 1$ then the nonce $n$ is a good solution to the problem $p$.

The time to calculate a $f(n,p)$ is given by a function $\tau: N \times P \to {\Bbb R}^+$.

This description models in a sufficiently general fashion a proof-of-work which I use since it helps me to understand the conceptual issues.

To be a more realistic model, think of the set $N$ not only of the set of 32-bit nonces in the sense of the reference implementation but of the set of all possible changes a client can make for winning a block.

In Bitcoin, $N$ is extremely large and the time to calculate $f(n,p)$ is very small (we have to evaluate a SHA). Thus, the proper strategy is to chose an $n \in N$ randomly and to calculate $f(n,p)$. (Note: The miners do not chose the nonce randomly, but in our model $N$ is meant to model the entire variability to solve the PoW, so $N$ is indeed extremly large and if we assume $n$ is selected randomly instead of sequentially, we make a negligible error). Thus, we are doing a large number of experiments with a small chance of success and thus a Poisson distribution is a good guess.

As a result of this observation, we can parallelize a search for a good $n\in N$ over this larger set $N$.

Now let us look at different PoWs, as we discussed them in this thread.

ONE possibility we will consider only for theoretical purposes is that $N$ contains only one element and $f(n,p)$ takes very long to calculate. This corresponds to the completely sequential PoW. There is no chance for parallelization at all. The miner with the fastest CPU wins the block all the time.

ANOTHER possibility would be to consider a set $N$ with a small number of elements, say some 100 or so, where the time to calculate $f(n,p)$ is much longer. In this case, there would be no good parallelization (the maximal degree of parallelization would be 100). So since there are more CPUs then elements in $N$, we will again have the situation that the guy with the fastest 100 machines wins every block. Not what we want.

The second and only other design decision we could change is the time complexity. So, for some $n \in N$ the time to calculate $f(n,p)$ would be smaller and for others it would be larger.

Let us look at the two possible cases here: A small set $N$ and a large set $N$.

For the case of a small set $N$, I can construct the situation I intuitively had in mind when starting this thread. However, as we will see, there is no real benefit. As an example I consider a case where $N$ and $f$ is such, that there are 5 easy and 100 very complicated PoWs. Very complicated would correspond to non-parallelizable. Now assume, there are 2 attackers and 200 honest nodes. Under this assumption, the 200 honest nodes find a solution quickly, where (on the average) the attackers will have a disadvantage. Chances are high that the attackers will end up with the complicated tasks. So even when there are more attackers, they could not really gain something in parallelization, since the attackers are likely to chose from the 100 very complicated tasks. However, when varying the numbers of the example one immediately sees that this effect breaks done, if the number of easy and complicated tasks is different or if some honest nodes turn into attackers. Of course, this is not robust enough to be a suggestion for Bitcoin. However, I can produce the effect of which I intuitively felt it would be possible.

For the case of a large set $N$, every miner would probe some thousand or more elements of $n$. Here, the differences in easy and very complicated work situations are equivalent to a situation where all tasks have the same average time complexity. So, the effect becomes smaller and is no longer noticeable.

I thus come to the conclusion: Yes, we can (quite artificially) produce situations, where a non-parallelizable proof-of-work is of advantage for Bitcoin. However the assumptions needed for obtaining such an advantage are unrealistic and allow other forms of attacks.

The answer thus is: Yes, there is a very good reason that the PoWs in Bitcoin are constructed the way they are constructed - it just took me a few hours to reach that level of understanding.

Thanx for all the contributions to this thread.

Yes, this is strict identity verification. There are numerous authorities which do so and which are not central. Every identity verification system of a modern state is distributed and depends on trust relations between the various offices and employees. as mentioned, this is not Bitcoin-related work and it is much more vague than the thoughts on PoW.


I agree - although challenging every absolutely I find is part of my daily work as researcher and the way I feed myself 

A non-parallelizable PoW will not help me to distinguish 1 person running 100 computers from 100 persons running 1 computer each and this also is not what I intend to do with non-parallelizable PoWs.

So what do I want to do?

Right now, Bitcoin uses PoW to (1) randomly select a winner (2) ensure a waiting time between two blocks. Both, selection of winner and waiting time, may be described by a probability distribution. The currently employed PoW in Bitcoin produces two very particular probability distributions. Probability of selection is proportional to (pooled) performance and waiting time is Poisson / exponential with a mean which can be nearly arbitrarily lowered by an attacker.

1) I want to prevent an attacker from arbitrarily lowering the mean of the waiting time (this is a direct consequence of parallelizability)

2) I want to understand if the distributions we get from the current implementation really are the distributions we want (non-parallelizable PoWs give rise to completely different distributions)



 

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).


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.


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.


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.

What you are describing requires strict identity verification, and thus also requires a central authority (to do said verifications) and lots of trust.  In other words, it's nothing at all like Bitcoin.  If you're going to require a central authority, don't bother with proofs of work or anything like that; just record balances in a database.

Absent some centralized mechanism, which is contrary to everything Bitcoin stands for, you have to realize that there is absolutely no way to distinguish any sort of difference between one person running one hundred computers or one hundred people running one computer each.  If you cannot tell who is running what there is no way any sort of "non-parallelizable proof of work" could possibly work.

You fail to explain why a completely serial Proof-of-work would be better than the current system. As others have pointed out, a serial proof-of-work has two major problems:

• Fastest node wins every time. If you think FPGAS are scary now, wait till they are optimized for your serial problem. (Actually, an ASIC may be needed to achieve a higher clock speed). If high clock-speed paid, I might just invest in liquid nitrogen cooling for 5+GHz clock-rates.
• 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.

Edit2: That machine I mentioned earlier would still be able to do better than most competing nodes. It would be able to verify 32 Proof-of-work candidates in parallel, while speculatively generating a "proof-of-work" block based on each.

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?

Damn, I know, I know. The core of problem is, like stated in the previous post, that a "trying to win a lottery" is perfectly parallelizable.

.. scratching my head ..

So would non-parallelizable PoW make it so only the fastest machine would always find new blocks ('cause all the others are lagging behind in doing the exact same calculation),  while parallelizable PoW provides a chance, even if small, for even the slowest machines to find blocks? Or are there non-par PoWs that allow for slower machines to still somtimes get to the right conclusion first?

Yes. By your post I suppose that I finally managed to make myself understood. The idea actually also was reshaping due to the good discussion on the board here. Thanx to all, guys.


From what I see right now (have 2 leave train in some minutes and may need some more thoughts) this is identical to one of the non-parallelizable PoWs I found in the literature.

I am not so sure how big the problem of a long verification really is (could we overlap checking the last block with producing the next one ?). We are using PoWs in a bit different manner in Bitcoin than in, for example, spam and dos protection (where it is essential that the server can do a quick verification and the client does a complicated puzzle). In Bitcoin, we are more symmetric and would probably just slow down block production speed by a factor of 2.

Moreover, I just found some nice recent papers on non-par PoWs and I hope one of them contains a suggestion.

If you have 4 computers you can test 4 different Kn at a time -> 4 times the chance of finding a winning nonce.

Sybil is on my mind.

I plan a register of persons to prevent fake multiple identities. Assuming a core number of trusted users, every user would show up in person at a certain number of users in his area (partially to be selected by random choice, to prevent systematic collusion). The user would present some official documents and then get a uid based on a standardized id scheme, eg a hash on "Firstname Middleinitial Lastname-When-Born Birthplace Birthdate". To be able to act anonymously, the user would first logon using this id and then use this to generate secondary anonymous credentials for login. These will be produced in a manner that there will only be one credential for every user per time unit. Thus, the user is anonymous AND the risc of a large number of fake users is small. It is kind-of a decentral implementation of a PKI, similar to the web-of-trust in PGP (but preventing collusion attacks).

Having prevented a Sybil attack by that mechanism, a trust based system is now possible as next level or user management.

The disadvantage, of course, is the requirement to establish identity first, which is rather tedious.

I can handle this disadvantage, since users who did not establish identity may use the system but will not have additional access rights and will not have rights in the trust layer. Of course, this is a not feasible for Bitcoin, because there is essentially just a single functionality (no different access right levels and no trust) and users would be very frustrated, if they had to do all kinds of registration before receiving or making payments.

Very interesting discussion in this thread. I think I understand both the goals which Forp tries to achieve and the reasons for it.

One possibility to include badly parallelizing serialization into the Bitcoin would be to request that each step of PoW depends on the previous one.

Example of the idea (unusable for real usage):

To find a block (PoW):

1. Set initial hash H0 = SHA256([ block header ] )
2. Perform following serial steps:
3. Let Hn+1 = SHA256([Hn | Kn]), where each Kn is randomly chosen
4. When Hn is lower than difficulty, stop, solution is found, store nonce and all Kn ;-)

By [a | b] I mean concatenation of the blocks a and b into single message.

Thus, even if I own 4 computers, they will compete each against other and will not help me to find more blocks in given time frame.

Of course, there is big flaw in the above - verification of block requires the same time as took to find the block, plus one needs to store all Kn chosen. But its an idea that came up. Feel free to improve on it .

Things like this tend to be prone to Sybil attacks. I'm not an expert but what I learned from comments like this is that there are some very good reasons why Bitcoin is based on Proof-of-Work rather than trust. Not sure if this applies to your system.

Ah. That's a concept which might fit nicely into my application. Actually, by reading the other thread, I realize that it is much easier to express what I want, and probably also easy to implement: As part of the proof-of-work and branch selection concept !

I favor a technique of "those who have more documents, key-value pairs stored and have been active in the system for a longer time and are trusted/interconnected to more users have a stronger say on branch selection" over the "those who have more $$$ for GPUs have a stronger say".

I'm mostly referring to ideas I've expressed in the previously linked thread, to augment proof of work with proof-of-stake and circulation (possibly quantified as bitcoin days destroyed) in branch selection.

And in different applications it depends on the motivation of the attacker. In a monetary application (Bitcoin) the attackers may be botnets which want to make some $$$ (or, rather, BBB); unless you are the FED or Visa, of course. If you look at directory applications, an attacker is not interested in double spending but might be interested in preventing a certain result or document from being stored in the system or to disrupt the operation of the system. Here, the motivation of an attacker is different, as well as the means he can use for an attack.


@Meni Care to give a hint about what you are thinking of? Working on a new application type, a "fundamental change" in how branches are selected is a real option. Therefore I would be very interested in learning about this, even if it is "just" a "raw" idea and not a source code patch.

Let me see if I understood correctly, where I lost you.


Your ability to parallelize depends on the number of computers you have and on the type of problem you want to solve.

If the problem you want to solve is finding the correct nonce for a bitcoin block to meet its target, you can parallelize very nicely. Generally speaking, every problem which consists of brute-force attacks is nicely parallelizable. Also, multi-dimensional problems can be parallelized very nicely, for example matrix mulitplication. Let us assume we multiply a 10x10 matrix with another 10x10 matrix. When I have 10 computers instead of 1 I will be (nearly) 10 times as fast. Even having 100 computers may help (one for every element of the result matrix). What about 200 computers? Still good, since I now could split the calculation of each sum into two halfs. What about 1 billion computers? Well, probably there is a limit to the degree to which matrix multiplication is parallelizable.

This observation may motivate a search for problems, which cannot be parallelized very well.

For example, assume you have a number x and want to calculate sha(x). Fine, we have an algorithm for that. But now let us calculate sha(sha(x)). How would we parallelize this? Actually we FIRST have to calculate sha(x) and THEN we have to evaluate the hash function again. It does not help me to have an additional computer. We know of no shortcut for parallelization. (There are functions, where we know shortcuts, like in addition: Many invocations of an addition can be expressed as multiplication, but with, for example sha, there is an issue).

So the idea was to replace the proof-of-work problem in Bitcoin (which currently is highly parallelizable) by a problem which is not parallelizable at all. (As outlined, this is only part of the concept, because a completely serialized proof-of-work would not lead to the probabilistic behaviour we want).

Hope I got the point where I lost you.
 

This depends on who runs the botnet.

How do you block an attack? Reject blocks that have the "evil" bit set? (Actually there are ways, but they require a fundamental change in how branches are selected)

The botnets seemed to have come to the conclusion that it is better to join the bitcoin network rather than sabotage it. What would be the point of an attack even if it could be briefly successful before being discovered and blocked?

You lost me here: as others have said, you can parallelize by buying more computers. If you want to use a lot of memory and branching to remove the advantage of GPUs, I can still parallelize if I have more money than anybody else.

Oracle quotes me just over $44,000 USD for a fully loaded SPARC T4-1 Server (PDF) with 256GB of RAM, supporting 64 simultaneous compute threads. It can consolidate 64 virtual machines (with 4GB of RAM each) in 2U, while drawing under 800 Watts. Granted, the 4MB L3 cache becomes 64kB afer being split 64 ways (128KB L2 becomes 16kB split 8 ways (8 cores)),  but each "machine" is only costing you about $687.50 USD.

If you had money to burn you could probably put 20 in a rack for 1280 virtual machines in a rack. How is anybody doing this not taking advantage of parallelism? Edit: assuming your "racks" of 4 GPUs are 4U each, your example for the "parallel" case has only 8 times the density (256 threads per U vs 32).

I think I now understand what you're talking about. This is basically making the computation more granular, significantly increasing the time it takes to test one value (from a microsecond to 10 minutes).

I think you'll find that still, an entity with enough resources wins, and more easily than with the current system.

You're welcome, glad to help.