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.

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.

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

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

Academic guys *need* a stable program of talks online at the site before they have a chance to secure funding to attend such an event.

So...looking forward to a more complete program.

Also, some info on how to submit contributions would be *really* helpful.

Just some nice pictures of confirmed speakers are not enough...

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

+1 for the first part.
-1 for the second part.

I got interested in undstanding Bitcoin by Satoshi's paper, i.e. I did not at all understand the true concept in Satoshi's paper but it served as a good cliff hanger and appetizer.

5 weeks later, having read Bitcoin source code and having hacked my way to my own block explorer tool, I had a better understanding of the way Bitcoin works. Thus, I do not understand why u suggest a translation of the paper; a reenginered, improved paper with more precision giving the complete picture would be much more important.

 

Ich schreibe derzeit an einem längeren Text über Bitcoin. Die Extremkurzversion erscheint hoffentlich bei einer wiss. Zeitschrift und für die Langversion suche ich gerade einen Verlag. Zudem ist es ein Thema im Seminar bei uns an der Uni. Da könnte man sich ja mal zusammensetzen und plaudern. Bei Interesse bitte Message über das Forum senden. Danke.

Google for "How to share a secret", a paper by Shamir. Might answer your question.

From my point of view it is a correct reading of the source but an incorrectly drawn conclusion.

Example: Assume a transaction hat the outputs X and Y. Then usually ONE is the recipient of the payment and the OTHER is the original owner of the coins. Now assume that X is a well known bitcoin address (for example a donation address mentioned here in the forum). In this case you can safely conclude that Y belongs to the original owner of the coins.

As someone who is teaching advanced level computer science for a living (and is fairly fluent in C++) my thoughts on this are:

The Satoshi client contains a particularly advanced style of C++ programming which occasionally is hard to read but is very refined, highly thought through and very efficient.

Currently I am working on source code documentation, reading line by line, adding some assertions and test and peek and debug code and writing down what each line really does. I did so for some 60-70% of the code. In parallel I am working on a documentation which describes the code in plain language; there are some 80 pages now, in draft version. This is a description, not an RFC-like spec.

Originally I also felt the strong desire of reimplementing this, also in a different language. Right now, after some 400 hours spent in reading BTC C++ code, I have reversed my opinion: Reimplementing BTC is probably a bad idea, since the client has a very large number of tricky details which one is likely not to see upon first or second reading (and which are not documented, neither in the code nor in the wiki nor in the rules). Moreover, these aspects are hard to describe in a specification of RFC-like style (which is the reason that I recently introduced a "advanced p2p concepts" chapter in my book on BTC).

However, some reworking of C++ would help the client. The problems I see are:

* Too many classes in one file, bad source code to file mapping
* Too much global state, bad encapsulation and isolation
* Many preprocessor constructions which make the code hard to read
* The class structure is smart and efficient but not quite well adapted to the conceptual elements of BTC. Obviously, the code was growing throughout the project and there was no clear object oriented analysis at the beginning. This probably is the biggest problem since this would require some far reaching code refactoring completely accross the current object structure.

Moreover, I think that C++ is the exactly right language for this (although it leads to a much larger code base than in a Python implementation). Python is the "wrong way of thinking" for this type of code - and there is the efficiency argument as well.

I am happy to share thoughts and drafts of my book at a bit later stage but advice that currently the text is in German. There will be an english version later, but currently it is in German since I need it in German :-)
 

How do I do that correctly?

What I did was set DISPLAY to :0, turn off xfire and then set DEVICE=0 (1, 2, 3, 4, 5).

Is that the way to do it?

Because...it sounds like a quite plausible explanation that I was only using ONE card. And if I addressed them with atitweak incorrectly as well...I also might be getting the funny performance figures.


Yes. But that's fine for me. I am still grilling my steak on the stove and not on the GPU :-)

I am mildly underclocking the cards, a bit intentional. Moreover, it is summer here and when I did some modest overlocking the cards locked up on me. 

I can confirm this.

I am running Windows 7 enterprise with 3x 6990 cards, which is 6x GPUs, using the 11.8 preview driver. The rig does some 1600 MHash/s which I currently split between solo and pool.

That's plural. TWO power supplies adding up to 1650 watts. So it should be fine.

However, I got the rig running now under Windows 7. Looks like the 11.8 preview driver is indeed able to accommodate 6 GPUs (the one I used before did not - windows complained about the driver of the third 6990 having insufficient ressources). And I get 1600 MH/s and am quite happy :-)

Also it looks like 11.8 preview leads to a thermal improvement. I am running at 5 - 8 deg celsius less with the same hash rate per GPU, if compared to earlier drivers.

The sad side, of course, is, that something I did not achieve under Linux now is working fine under Micro$oft. To me, this is rather irritating 

So what?

Bitcoin is not about printing your own money but about collectively building up a peer-2-peer value transfer system.

@Kiv, just as information: Now it is Norton Internet Security, which also reports your 2011-07-11 version of GUIMiner, downloaded from Github.

+1

guiminer-2011-07-11.exe from github user Kiv reports as virus on Norton Internet Security; no further useful details.

Die Location war ok. Ich konnte dafür Unterstützung gewinnen - aber nur für dieses Mal. Für das nächste Mal sollten wir da eine bessere Lösung finden.

Hat da jemand ne Idee?

Das Meeting fand also statt 

Wir waren zu viert: LetBit, harm, Jeff und Forp - und haben dreieinhalb Stunden spannend gefachsimpelt.

Die Themen, die wir hatten, waren dabei:

• Mining
• Bitcoin Tausch
• Meetings in Deutschland
• Funktionsweise des Transaktions-Netzes, Wechselgeld-Verfahren im Client
• Sicherheit beim Bitcoin Tausch und bei Kauf und Verkauf mit Bitcoins
• Weitere Meetings

Die Frage ist nun: Wie geht es weiter.

Wer würde denn zu einem nächsten Meeting kommen.

Dabei stand die Idee im Raum, zu einem Thema einen Referenten zu suchen, für ein Impulsreferat - und dann in die Diskussion einzusteigen.