Bitcoin Forum

I am trying to understand why Bitcoin has a parallelizable proof of work.

The task of the proof of work in Bitcoin is to make it increasingly difficult for an attacker to "change" the "past" and to ensure some kind of convergence in the concept of the "longest chain" in the block structure. Also, the block bonus provides some incentive to the miner, which keeps the system running.

The currently employed proof of work schemes are parallelizable.

As a result of this, pooled mining is faster than GPU mining (250 cores) is faster than iCore 7 mining (8 cores) is faster than Celeron mining (1 core). In my opinion, this is a disadvantage, for a number of reasons:

* Larger pools have a significant share of the total hash capacity. This increases their chances for a 50% attack.
* The speed with which the block chain "converges" (or in the case of a fork "heals") is faster, when many competitors with small computing power are in competition, as compared to the situation, when there are less competitors or competitors with higher (aggregated) computing power.
* Bitcoin was meant to be peer 2 peer; pooling is in contradiction to this. The pools are the banks of tomorrow.

A non-parallelizable proof of work would still serve the same goals as a parallelizable proof of work but would solve these problems.

Of course, at the current difficulty, chances to "win" a block for a single miner would be small. This issue however can be solved easily:

* By increasing block speed and apropriately reducing the bounty, the economics could be kept the same in the long run, but the granularity of the block bounty would be adapted.
* If we want to keep block speed and bounty, we could still have miners operate several computers or GPU work on blocks, but every core would work on its own block variant. This would still increase the return on investment for the miner linearly, but it would not show the problems outlined above.

Therefore my question: Why are we having a parallelizable proof of work ??

Is there a good reason which I do not see or is it merely a historical accident (possibly waiting to be cured?) ?

Provide any example of

Very few things can't be parallelized.  A mining pool is one example of that.  Provide an example of a problem that an individual can solve but a group of individuals can't solve more quickly.

Remember multiple GPU (or multiple people in a pool) aren't working together they are working independently and simply sharing the reward.  You could design a work unit so that it requires so much resources that one computer can only work on one solution at a time.  You simply shift the bottleneck from computation power to memory or disk access. Still even if you did so you wouldn't eliminate pools.

If one computer can work on a problem then two computers can work independently and share the reward.  That is all pools are doing.  They aren't working together.  Shares are worthless and don't help the pool, they are merely a metric to avoid cheating.  The only hash that is worth anything is the solution and it is worth 50BTC (plus fees).  So every share produced is worthless except the one which is the solution and it is worth everything.    A pool is simply an agreement that everyone works and then you split the 50 BTC.  Shares and RPC and long polling are simply mechanisms to enforce that sharing.

How exactly would you outlaw sharing?

The aim is to distribute coins via lottery -- every nonce you test is a lottery ticket you bought.

If you used a non-parallelizable test, the same person would win every time: the person with the fastest single serial processor.  That would be an even dumber distribution than the existing one.

How is this whine about pools related to parallelization? 1 cpu or 1 gpu, nothing would change, we would still have pools with cpu, cause otherwise to find a block in solo it will take us years.

And the "50% attack from pool" thing can be easily solved, there can still be pool but in a way that they CANNOT control the work

A  parallelizable problem also makes it easy to tune the difficulty. If you were able to claim a block reward by finding large primes, the block interval would be a lot less predictable.

Also, the chosen method (cryptographic hashing with a result below a target value) is a problem that is difficult to solve, but easy to verify. The hash serves a dual prupose: poof-of-work and integrity verification. Combining the two makes pre-computing the work ahead of time nearly impossible (exception: block-chain fork).

IMHO, the short answer is that Bitcoin is a distributed network. If you want lots of people around the world to work on the same problem, you need to parallelize it one way or another.

This question has already been asked in many ways. If you can limit mining to a single network node (CPU), dedicated miners will just set up multiple nodes for themselves. If you want to limit mining power per person, you've just thrown away the whole idea of an anonymous distributed network. Also, do you want to ban people from working together towards a common goal?

Moreover, limiting generation per person throws away all incentives for developing the network. In its current form, the network is stronger against attacks, because people are rewarded for spending computational power on it. In other words, who is going to do any work, if you just give everyone a big chunk of money?

The problem to solve must, of course, be inherently serial. Searching (guessing) a nonce for a single hash condition is not. Thus we should think more along the lines of hash chains.

There is some literature on this although it is not so widely known.

Colin Boyd presented a talk at the CANS 2007 conference on "Toward Non-parallelizable Client Puzzles"

The classical reference if from Rivest, Shamir, wagner: Timelock puzzles and timed release crypto.

Green, Juen, Fatemieh, Shankesi et al discuss the GPU issue in "Reconstructing Hash reversal based Proof of Work Schemas".

All in all, there are some 20 papers on this and the math is straight forward.

No. This is not specific for non-parallelizable.

The current Bitcoin proof of work leads to a stochastic situation since the solution algorithm is stochastic in nature and every miner (rather: pools) works on a different task.

Both aspects of course must be built into the non-parallelizable proof of work. This can be done, for example by extending the algorithm in the Rivest shamir Wagner paper (see above) by nonce aspects. I have not yet worked out the details or implemented this, but assume it is straight forward.
 

The incentive aspect can be solved by adapting difficulty as written in my original post.

Why would parallelizability and tunability relate to each other? In the Rivest Shamir paper I cited above there is a nice non-parallelizable puzzle which explicitly contains the "number fo computational seconds" as tuning parameter.


Finding large primes would be a very bad non-parallelizable proof-of-work because most prime-finding algorithms are very nicely parallelizable - especiall the probabilistic algorithms. Thus: Non-parallelizable proof-of-works usually are not based on finding large primes.


Which is true for all proof-of-work concepts by definition and also for the non-parallelitable ones we find in the literature.

You are aware that they are not working on the same problem? Every miner is working on a different problem (with a different bounty transaction, different time stamp etc.). This cannot be the reason.


Exactly. This improves the probabilistic convergence speed of the algorithm. That's just my claim. Hopefully I can come around to produce a more formal proof for this the next days.


The point is: The current proof of work scheme makes it possible to parallelize and have pools. A pool could thus become a very strong adversary which is not what we want - right? A non-parallelizable proof of work scheme has the consequence that nobody can become stronger than a, say, 4.5 GHz overclocked single core pentium. This is what we want.

If I can get X power by doing Y. How am I not going to be able to get 2X power by doing Y twice? How could you possibly tell the difference between two people doing Y and one person doing Y twice? Not to mention (again) that the pool is actually just a bunch of people separately doing Y and sharing results.

It is possible to design a proof-of-work scheme where being part of a pool doesn't provide any (or negligible) advantage, aside from the benefit of having a more predictable revenue stream.  Perhaps that's what the OP is wondering about.

That is all that a pool currently does.

How would you prevent the fastest miner from winning every block?

And bitcoin gets taken over by a single botnet.

THAT IS THE ONLY ADVANTAGE POOLS HAVE NOW.

Each miner in the pool is working Independently. A pool with 1000 miners has absolutely no advantage over a pool with 10 or a solo miner (1). At its most basic level a pool is simply an agreement to "share" the reward.  No work gets shared, only the reward.    If a pool of 10,000 miners mines 5 million shares and then one miner finds the solution.  Essentially the other 9,999 miners did ABSOLUTELY nothing.  One miner solved the entire problem ALL BY HIMSELF.

However there is huge volatility in mining yourself (due to the high reward and low chance of "winning").   A pool normalizes the results (smaller reward, higher chance of winning) but the expected value is the same.


The protocols of the pool (i.e. checking low difficulty shares, rpc, etc) merely exist to keep people honest.  The simplest pool requires no protocols just trust.

Me and 4 friends (all with exactly the same hardware) all hash independently.  If one of us "wins" we split the prize 5 ways.  Expected value is exactly the same but volatility has decreased.   Now as pool gets larger the risk of cheating gets higher so pools implement protocols and procedures to ensure "fairness".

So back to the OP point.  Please provide an example where the reward can't be shared by a pool.   You can't.  Even if the work is completely non-parallizable the reward certainly can be via INDEPENDENT actors sharing the reward via mutual agreement.

So what exactly would a non-parallelizable solution solve?  Of course the fastest miner would always win the non-parallelizable solution.

Another tiny problem, all nonparallelizable puzzle schemes proposed so far require the puzzle creator to keep a secret from the puzzle solver. How exactly do you do that in a decentralized system?

The original paper from 1996, Rivest, Shamir, Wagner (see above) provides some nice real-world examples here.

1 woman needs 9 months to give birth to a baby. So 2 women will have twice the power and will need 4.5 months to produce a baby.

A bus full of passengers stands in the desert. They ran out of gasoline. The driver discovers that the next gas station is 50 miles away. This is no problem, since there are 50 passengers on the bus. They will just split the task and every passenger will walk his share of 1 mile.

The examples show that there are tasks where you do not get 2X power by doing Y twice. In my above posting there are references to mathematical examples in the literature.

From the discussion I realize that I did not properly describe my core goal. It is not about mining or increasing revenue or making them more predictable. It is rather about undstanding the implications of the current choice improving the stability and speed of statistical convergence of the longest chain.  The discussion here thus far was very helpful and enables me to rephrase my thoughts, hopefully in a better way.

In a non-parallelizable PoW, we will have, say, 1.000.000 processing units all competing individually for a block. Some are faster, some are slower, but they do not differ so widely in performance. Every processing unit corresponds to a single processor (no parallelization advantage for a GPU or a multi core; however a single person might own several competing processing units, which might sit on a single die or a single GPU or several racks).

In a parallelizable PoW we will have a much smaller number of processing units competing for a block. Many of the former units will cooperate by the mere fact that they are sitting inside of a GPU and are parallelizing their work. Other units are even stronger, since they form pools. Moreover, we see a big variance in performance (ranging from the Celeron miner to the 100 racks x 4 high end GPU x 256 GPU processing cores miner).

Now, how do these two worlds compare?

1) In the parallelizable world it is POSSIBLE to form a processing unit which has more than 50% of the hashing power. You simply buy as many GPUs as necessary and that's it. In the non-parallelizable world this is not possible. The best you can do is to overclock your single core or to build specific SHA processor.

2) As a result of (1), the distribution of processing power in the two cases are very much different and thus the two algorithms will definitely behave differently.

Current state: I am trying to understand this difference. My (yet unproven) mathematical guts feeling is, that the convergence in the non-parallelizable setting is better (I am referring to the thoughts very informally described on pages 7 and 8 of Satoshi's white paper) and the system is more robust against some forms of attacks. I do not have a completely thought through concept yet.

The discussion here is very helpful for this. Thank you!

This is a very important question and trying to answer this I am understanding the mechanism I want to design much better. Thank you for asking it!

The PoW system currently used in Bitcoin has the same problem. It solves this problem by offering an extremly large search space and a situation (hashing) where nothing can be said efficiently or systematically on how to find a good solution. Thus, the solution method is random parallelization of a brute force search. This solution method introduces a random element into the situation (which was not there from the beginning: the PoW task is not random).

So, parallelization introduces a random element here. If we now prevent parallelization completely and produce a PoW system which makes the solver work through a sequential number of deterministic steps, the fastest single core processing unit will win every block.

Thus, we must reintroduce a random element in the PoW. Possibly, there are two construction elements for building a PoW: Two tasks could be chained one-after-the-other (leading to non-parallelizable work) or combined (leading to parallelizable work). Currently Bitcoin uses only ONE of these construction elements. Using ONLY the other one is a clear fail (as FreeTrade just pointed out). Using BOTH mechanisms could lead to a new, different PoW.

The question is: Would there be advantages when using a different PoW?

In addition to the ones outlined in my above posts, I see one more: Currently the time for solving a PoW is distributed according to a Poisson distribution (Satoshi describes the consequences of this in his paper). We have a parameter (difficulty) where we can tune the mean of this distribution, but we cannot independently tune the variance of the distribution (with Poisson it will always be equal to the mean). With a different PoW system we will be able to obtain different distribution shapes (possibly with a smaller variance than Poisson). This could make the entire system more stable. Certainly it will impact the Bitcoin convergence behaviour. For the end user the impact might be a higher trust in a block with smaller waiting times.

To my current understanding this is just the other way round.

In Bitcoin, a single botnet can obtain so much hashing power as to take over the system, since it can parallelize the PoW.

In a completely non-parallelizable PoW (as FreeTrade pointed out recently and I just commented on), the fastest single processor takes over the system - but we have a perfect protection against a botnet take-over (because parallelization does not help).

In the concept I am thinking of right now, we should be able to combine the advantages of both worlds, depending on how we build the PoW (described in a bit more detail in my recent reply to FreeTrade).

I think you're confused about how the so-called "Bitcoin lottery" works. You seem to think that if I have some system and you have a parallel system with x100 the power, then you will find all the blocks and I will find none, because you'll always beat me to the punch. But no, these are independent Poisson processes (tied only via occasional difficulty adjustments) with different rates, meaning that you will simply find 100 times the blocks I will. So over a period where 1010 blocks were found between us, about 1000 will be yours and 10 will be mine.

In other words, it scales linearly - the amount you get out is exactly proportional to what you put in.

If that's all you're after, mission is already accomplished.

But if you think your "non-parallelizable PoW" system should behave differently, let's say that in this system a person with a computer finds one block per month. Then four people with a computer each should find a total of 4 blocks per month, right?. So a person with 4 computers also finds 4 blocks per month, because the system can't know who the computers belong to (and if it can then it's not at all about a different computational problem, but about using non-computational cues in distributing blocks). So a person with a special 4-CPU system also finds 4 blocks, as does a person with a quad-core CPU.


And, once more - pools are not a security threat if implemented correctly. There's no reason the pooling mediator also has to generate the work. And, there are already peer-to-peer pools such as p2pool.


Edit: Parallelism means that an at-home miner can plug in his computer and contribute to security/receive rewards exactly in proportion to what he put in. Non-parallelism means his effect will depend in complicated ways on what others are doing and usually leave the poor person at a significant disadvantage (since others are using faster computers), which is the opposite of what you want.

Block finding follows a Poisson process, which means that the time to find a block follows the exponential distribution (where the variance is the square of the mean). The variance is high, but that's an inevitable consequence of the fair linearly scaling process.

If it pleases you, the variance of block finding times will probably be less in the transaction fees era.

There are standard techniques to solve the problem you pose in a decentralized system. The buzzwords here are secret splitting (the puzzle is not created by a single person but by many persons, none of which knows the entire secret), you might want to Google "coin flipping over the phone" or "how to play any mental game".

I do not know yet if these standard techniques are practically feasible in the Bitcoin setting. They might. They might be not. That's the thrill of research. :-)

I am not sure whether there are non-parallelizable puzzle schemes where this requirement can be relaxed. Thus, there may be another way out.

Thanx for your interestign reply.


No. I do not think that.


I completely agree.

Now suppose it is you and me and some 40 other guys with the same hash performance as you have in your example. Suppose I want to claim 100 BTC bounty for every block instead of the standard 50 BTC. Chances are next to 100% that I will manage. Since, on the avaerage, I am faster than you (and all the other guys combined), I will dominate the longest chain in the long run.


No. It is not my mission.


Why?

The perspective I am looking at is not the single block but the development of the block chain.

As soon as one of the four people found a block, this person broadcasts this block and the puzzles the other three had been working on becomes obsolete (at least that's my understanding on what the reference implementation does). Only a cheater would be interested in continuing to work on "his" version of the block; however, having lost the block in question, chances are getting higher that he will not manage to push "his" version of the next block.

Four people with a computer would rather find a total of 4 blocks in FOUR months - and these blocks would be the four blocks chained next to each other, ie a block chain of length 4.


How do you prevent a pool from pooling more than 50% of the hashability and then imposing its own understanding of Bitcoin upon the remaining nodes?


I agree to the interpretation of the parallel PoW situation. I disagree with the interpretation of the non-parallelism situation - there is not yet a final proposal for a non-parallelizable PoW, so we do not know yet if this is a necessary consequence. However, I am grateful that you are pointing out this argument, since it is a possible problem. I will take this in consideration in my future work on this - it is a helpful objection.


Again you are raising an important aspect. The task thus is to see that two goals can be balanced: Linear scaling and small variance.

I agree that the Poisson process is a very natural solution here and prominently unique due to a number of it's characteristic features, such as independence, being memory and state less etc. A non-parallelizable PoW will certainly lose the state-less property. If we drop this part, how will the linear scaling (effort to expected gain) and the variance change? We will not have all properties of Poisson, but we might keep most of the others. The question sounds quite interesting to me.

Come on man you are ignoring the entire concept of a reward.

A pool doesn't "get more" it isn't trying to get 2x.  It still gets x.  It simply gets x more consistently.

A better example would be a lottery (real world) pool.  In a lottery (lets ignore the lesser prizes) you either win nothing or you win a HUGE prize.  However the odds of you winning in each draw is so low that even if you played every day for the rest of your life you may never win.  Rather similar to the bitcoin lottery right?

So you and 19 friends get a great idea.  Instead of playing individually you pool your 20 tickets and if any ticket wins you SPLIT THE REWARD 20 ways. 

Has the lottery pool gained 2x?  No.  Do bitcoin pools gain 2x?  No.  In the long run (say 100 years of solid 24/7 mining) a solo miner and a pool miner (assuming same hardware, downtime, and fees) will earn the same amount.  They both earn X.  The only advantage of a bitcoin pool is reduced volatility. You reach the "long run" (where expected value and actual value converge) much quicker.

Any problem no matter how non-parallelizable can be pooled.  Each "miner" would work completely independent and if/when he "wins" he shares the reward with the rest of the pool.  That is unavoidable.  If you think the biggest risk to bitcoin is pools then your proposal does nothing about that (and creates a large number of new problems).

Ok, you're definitely confused about the capabilities of someone with >50% of the hashing power. He cannot do things like put a 100BTC generation transaction per block. Such blocks are invalid and will be rejected by the network (particularly the nodes that actually accept bitcoins for goods and services). In other words, these will not be Bitcoin blocks - the rest of the network will happily continue to build the Bitcoin chain, while he enjoys his own isolated make-believe chain.

Does your system maintain the notion that each given block is found by some specific individual? If so, if 4 people find 4 blocks in 4 months, it means each person finds 1 block in 4 months, contrary to the premise that each person finds 1 block per month...

If it wasn't clear, in this example the intention was that the 4 people aren't all there is, there are 4000 more similar people each finding 1 block per month, for a total of 4000 blocks per month. So again, if 4 people find 1 block per month each, then between them they find 4 blocks per month.

Because the pool shouldn't be the one deciding what goes in a block. As was explained, a pool is essentially just an agreement to share rewards. Even in centralized pools (and like I said there are decentralized ones), all the operator needs is to verify that miners intend to share rewards, by checking that they find shares which credit the pool in the generation transaction. But everything else can be chosen by the miner.

This is a future fix, however - currently centralized pools do tell miners what to include in the block. But miners can still verify that they're building on the latest block, so they can detect pools attempting a double-spend attack (which is the main thing you can do with >50%).

Variance in block finding times is unwanted, but I think most will agree it pales in comparison to the other issues involved. Especially since there are basically two relevant timescales - "instant" (0 confirmations) and "not instant". The time for 10 confirmations follows Erlang(10) distribution which has less variance.

By all means you should pursue whatever research question interests you, but I expect you'll be disappointed both in finding a solution satisfying your requirements, and in its potential usefulness.

My example is wrong, since an incorrect bounty is something a node can check on its own. If you replace the setting by a double spend, it should work.


Why?

It is characteristic of non-parallelizable PoWs that they do not scale in the way you describe. I believe we have a misunderstanding here.


Ok. Forget the pool as part of the argument here but think of parallel computing. The pool is a parallel computer.

The line of reasoning is about parallel computation and scalability of the PoWs.

With parallelizable PoWs, Bill Gates can buy as much computing power as he wants. He then changes a transaction in block 5 to his favour. Thanx to his computing power he easily can redo the entire block chain history since then. If the PoWs are, as I suggest, non-parallelizable, he simply cannot do better buy buying more computers. The only thing he can do is increase the clocking. By this, he can speed up his computation mabe by a factor of 5 or 10 - as opposed to buying more computers, where only money is his limit. So, non-parallelizable PoWs are an effective solution against this kind of attack.

(Yes, I know that the hashes of some 6 or so intermediate blocks are hardcoded in the bitcoin program and hence the attack will not work out exactly the way I described it - but this does not damage the line of reasoning in principle.)


I do not think that the "variance in block finding times" is the essential advantage, it is rather convergence speed to "longest chain" (I have no hard results on this but am currently simulating this a bit) and better resistence against attacks which involve pools parallel computers.


Trying to understand the argument. Do you think there is no PoW matching all the requirements? Care to give a hint why?

As to a potential usefulness: The concept is by now means "finished" but until now the discussion on the board proved very fruitful and helps to improve the system I am working on. This is for a different kind of block-chain application, so I am not expecting an impact for Bitcoin. Bitcoin is widely disseminated so I do not expect significant protocol changes to occur any time soon, especially by suggestions from outside the core team. 

Let´s make it a bit easier: assume, as in Menis example, that 4000 blocks are found per month by individual participants, under the assumption that your non-parallelizable PoW is in operation. Assume further that all of these people just meet up and decide to share the revenue equally to smoothe out their income stream. According to what you have been arguing, the total number of blocks they find would go down to 1 purely due to the fact, that they are colluding in terms of revenue-sharing.
By definition 4000 blocks, will reduce to 1 by your formular magically devining social contracts?
Good luck with that line of argumentation...

This isn't about parallelizable vs. non-parallelizable computations. Performance in serial computations doesn't scale linearly with more computing cores, but this is irrelevant. This is about the process of block finding, which is why I asked if your system diverges fundamentally in the notion that blocks are something found once in a while by people on the network. If not then it's really "if Billy and Sally each have an apple, then that's two apples" math - if in a given scenario (not in distinct scenarios) two people find 1 block each, then both of them together finds 2 blocks. If a network of 4000 people find 4000 blocks per month, each finds on average 1 block per month. This isn't enough data to know the distribution (it's possible one person finds all 4000) but the best scenario is when each finds close to 1.

It also means that if in a given situation 4000 people find 4000 blocks, each finding about 1, then if I join in it would only be fair if I also find about 1 (or, more precisely, that each will now find 4000/4001).

Yes, with parallelizable PoW you can overwhelm the network given enough time and money. My contention is that non-parallelizable makes the problem worse, not better. With fully serial only the fastest one will do anything, so noone else will be incentivized to contribute his resources. So this one person can do the attack, and even if he's honest, it's only his resources that stand against a potential attacker (rather than the resources of many interested parties).

And there's no indication that some hybrid middle ground gives better results - to me it seems like more like a linear utility function where fully parallel is best and it gets worse the closer you make it to fully serial.

Also, I hold the position that security can be significantly improved using some form of proof-of-stake (https://bitcointalk.org/index.php?topic=37194.0) (basically a more methodical version of the hardcoded hashes).

See above. I think you're going the wrong way.

I'm still not completely sure what the requirements are, this whole discussion has been confusing to me. But yes, to me it seems that from a "back to basics" viewpoint a serial computation only makes it easier for one entity to dominate the blockchain, making the "better security" requirement impossible. Again, if multiple computers don't give more power over the network, it means the attacker doesn't have to compete against multiple computers, only against one.

You mean an alternative Bitcoin-like currency, or something that doesn't look anything like it? If the former I doubt this will be applicable, if the latter I can only speculate unless you give more details about the application.

The Bitcoin code progresses slowly, probably mostly because of the sophistication of the code, but I trust that all sufficiently good ideas will make it in eventually.

Thanx, Gandalf, for your help. I still do not get it and plead guilty of having caused the misunderstanding.

But I still do not get it and would like to work it out.


Fine. Still with you. Assuming this.


No. Why should the number of blocks go down? I do not claim that they go down.

Maybe the misunderstanding is earlier. A non-parallelizable PoW means that the participants CANNOT collude on the PoW. Of course, they still can share their revenues, that is a completely different issue.

In current parallelizable PoW, all 4000 participants work by looking for a nonce with a specific property. For this goal, they test large numbers of candidate nonces. Every test has a certain success probability (determined by difficulty). Individual tests are, of course, independent of each other. Hence the PoW can be brute forced. This can be done in parallel. A block is found sooner or later, according to the Poisson process in place. So, the time to find a block follows and exponential distribution.

Now let us consider a strictly sequential, deterministic PoW (not as a suggestion for Bitcoin, but to see the difference). Here, a specific computational result must be obtained. To obtain this result, a large number of arithmetic operations must be performed in strict sequence. The number is adapted to the average speed of a single core CPU. The participant who reaches the result first wins the block. This cannot be done in parallel. However, it is always the participant with the fastest single core CPU, who wins the block. This is boring and not what we need. This is time lock cryptography and not exactly useful for Bitcoin.

Now let us consider a non-parallelizable PoW. Here, every participant must make a large number of sequential steps to reach a goal. However, contrary to the sequential, deterministic PoW, there are still random aspects, branching points in the computation. So it still depends on random choices of the participants, who will win the block (which is what we need). Of course, participants can still pool. Two participants will still get twice as many blocks in the long run. The block rate does not go down magically.

However now comes the crucial difference. Assume I have 2^256 participants, numbered 0, 1, 2, 3, ... How long will they need for the first block? In the current (parallelizable) PoW used in Bitcoin they need a few microseconds. Every participant uses his own number as nonce in the first round...and most likely one of them will produce a hash which is smaller than the current target value. In the non-parallelizable PoW I am thinking of, they will still need more or less 10 minutes as they should, since this corresponds more or less to the number of operations they have to do before they get a realistic chance for reaching the goal. However, since there is some variability, also a slower CPU with better random choices gets a chance.

To begin, the discussion and the reference to the proof-of-stakes thread, is very helpful to me. Thank you.


Agreed. I really guess we somehow got stuck in a misunderstanding, I might have caused.


Agreed. A sequential deterministic PoW does not do the job for the obvious reasons you are giving. We need both (randomization of block winners AND non-parallelizability) and I am curious how this can be done.

The issue I take is: A very high number of CPUs has a different effect for parallelizable PoWs than for non-parallelizable PoWs. (The "Bill Gates" attack).


We are reaching common ground. In my model, multiple computers do give more power to the network - but not due to the effect that a single PoW is solved faster in time. When we add computers to the network, the PoWs I am thinking of, must be adapted, as in normal Bitcoin. However, the effect is that the probabilities for finding a solution are rearranged not the overall time for solving a block.


I am thinking not of a currency-like application but on a replicated directory service kind of application. Since this is written from scratch, there is the chance to try different PoW systems without having to break the old algorithm (or mind sets of developers).

Thanx again for challenging my thoughts in the discussion. This is very fruitful.

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.

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) (http://www.oracle.com/us/products/servers-storage/servers/sparc-enterprise/t-series/sparc-t4-1-ds-487858.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).

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?

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)

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.
 

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.

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.

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

Things like this tend to be prone to Sybil attacks (http://en.wikipedia.org/wiki/Sybil_attack). I'm not an expert but what I learned from comments like this (https://bitcointalk.org/index.php?topic=41059.msg513979#msg513979) 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.

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

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.

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

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.

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?

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

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?

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.

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.

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)



 

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.