Proof-of-work difficulty increasing

[dmp1ce]

I don't know what you're talking about accepting easier difficulties.

We were essentially discussing Sabunir's question about what prevents someone from messing with the program's source code to adjust block-generating difficulty to be very easy, then make a network on his own and create a, say, 50,000-block proof-of-work within seconds then finally propagate it across the real network to steal "votes" towards his new fake blocks as technically, his proof would be "the longest". So is there a way to verify how much work was actually put into a given PoW (for eg. how many zero's are at the beginning of each hash or something)?

I am also wondering about Suggester's question.  It seems like modifying the code to give a node an advantage in generating coins might be possible.

I am confused as to why each node on the network is actually doing when set to generate coins.  What problem are they solving that takes 100% CPU?

[theymos]

Your CPU is creating SHA-256 hashes. It's not possible to cheat: if the hashes you create are invalid, no one else in the network will accept them. If you inject a 50,000-block chain of "easy blocks" into the network, everyone will immediately see that the hash for the first block in the chain is above the current target and ignore it and every block derived from it.

[fergalish]

Interestingly, using laszlo's mac os version of bitcoin, one can see how many hashes per second the computer is performing.  I'm currently getting about 1 million hashes per second.  Given the current difficulty 0000000013ec53, I'll have to perform about 2^35~3x10^10 hashes before I have a decent chance of getting one below the target, and at 10^6/s, that should take about 30000 sec, or about two per day.  The actual interval varies a lot - it's a random process, but that seems to be more-or-less the correct amount.

Satoshi, could you update the first post in this thread, with the complete history of difficulty-of-work increases please?  I'd try, but for some reason, I've lost my logfiles.  Fortunately the wallet is safe.

[laszlo]

Maybe someone with a little background in this statistics/math stuff can shed some light on this..

The way this thing works is it takes a (basically random) block of data and alters a 32 bit field inside it by starting at 1 and incrementing.  The block of data also contains a timestamp and that's incremented occasionally just to keep mixing it up (but the incrementing field isn't restarted when the timestamp is update).  If you get a new block from the network you sort of end up having to start over with the incrementing field at 1 again.. however all the other data changed too so it's not the same thing you're hashing anyway.

The way I understand it, since the data that's being hashed is pretty much random and because the hashing algorithm exhibits the 'avalanche effect' it probably doesn't matter if you keep starting with 1 and incrementing it or if you use pseudo random values instead, but I was wondering if anyone could support this or disprove it.

Can you increase your likelihood of finding a low numerical value hash by doing something other than just sequentially incrementing that piece of data in the input?  Or is this equivalent to trying to increase your chances of rolling a 6 (with dice) by using your other hand?

[D҉ataWraith]

The way I understand it, since the data that's being hashed is pretty much random and because the hashing algorithm exhibits the 'avalanche effect' it probably doesn't matter if you keep starting with 1 and incrementing it or if you use pseudo random values instead, but I was wondering if anyone could support this or disprove it.

Yep, your understanding here is correct. It does not matter what exactly gets hashed, and no, you can't cheat without first breaking SHA-256, which is considered difficult.

The salient property of cryptographic hash functions is that they are as random as is possible while still being deterministic. That's what their strength depends on -- after all if they weren't random, if there were obvious patterns, they could be broken that way. So the ideal hash function behaves just like a random number generator. It does not matter what you feed in, timestamp or not, whatever's put in there, the hash should still behave randomly (i.e. every possible outcome has the same a-priori probability of occuring). Incrementing by one works just as well as completely changing everything every step (this follows from the avalanche property). However, the initial value, before you start incrementing, must be (pseudo-)randomly chosen, or every computer will start at the same point, and the fastest one always wins, which is not what is wanted here.

[teppy]

A nice addition to the GUI would be an estimate of how many hashes/sec it's computing. Either present this as a raw number or a "you can expect to generate X packs of bitcoins per week."

This might partially solve the frustration of new users not getting any Bitcoins right away.

[satoshi]

That's a good idea.  I'm not sure where exactly to fit that in, but it could certainly calculate the expected average time between blocks generated, and then people would know what to expect.

Every node and each processor has a different public key in its block, so they're guaranteed to be scanning different territory.

Whenever the 32-bit nonce starts over at 1, bnExtraNonce gets incremented, which is an arbitrary precision integer.

[laszlo]

I created a little performance counter for myself to use locally, you guys are welcome to try it.

Satoshi, maybe you could integrate this or something similar and put an option in there to turn it on/off?  It spams up your debug.log and shows the performance of each thread.. it also shows on the UI in the status bar where it used to say 'Generating'.

Patch: http://heliacal.net/~solar/bitcoin/bitcoin-svn-79-perfcounter-2010-06-02.patch

Screenshot:

[lachesis]

Can someone share the math required to compute the estimated amount of time to generate a pack of bitcoins?

Basically, a formula that integrates the difficulty (either as a hex number (currently 000000000f675c00000000000000000000000000000000000000000000000000) or as the difficulty factor (currently 16.62)) and number of hashes checked per second (currently like 1M for me) which would return the average time between blocks found?

[theymos]

chancePerHash=target/max
numberOfHashesToWin=0.5/chancePerHash
numberOfSecondsToWin=numberOfHashesToWin/hahesPerSecond

(0.5/(target/max))/hashesPerSecond

Code:

(0.5/(0x000000000f675c00000000000000000000000000000000000000000000000000/0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff))/1000000 

=

35689 seconds

About one block per 9.9 hours. Does this match your observations? I'm not totally sure about the math.

[lachesis]

Sounds completely reasonable. I just started generating today, so I'll let you know once I get more blocks. Thanks!

[lachesis]

Laszio, I've remade your patch to spam the debug log less (1/10th as often). I also the extended JSON-RPC library to add "gethps" (which returns the same string displayed in the UI). It also adds listgenerated, which returns a list of the strings from the UI representing generated blocks. In the third and final patch, I modified net.h to compile with -O2 on my machine (which it wouldn't before).

Here are the patches:
http://www.alloscomp.com/bitcoin/bitcoin-svn-80-perfcounter-less-debug-spam-2010-06-05.patch <- Apply Laszio's patch first, then this one.
Sorry, that patch ^^ is completely broken. The changes are trivial (the same line in 3 places), but I failed at diffing. I'll upload a better patch when I have time.
http://www.alloscomp.com/bitcoin/bitcoin-svn-80-rpcextended-2010-06-05.patch
http://www.alloscomp.com/bitcoin/bitcoin-svn-80-netpatch-2010-06-05.patch

Thanks to Laszio for the original performance patch.

[laszlo]

Cool, I was just playing around with trying to make it adjust the rate without taking much of a performance hit.. that's why it tries to adjust that variable, to keep it to a few per second or so.. maybe you can figure out a better formula, I just kind of did that by experimenting around with it.

[lachesis]

About one block per 9.9 hours. Does this match your observations? I'm not totally sure about the math.

My system has jumped up to about 1200 khps. Also, I got Bitcoin running on a VPS which is giving about 2350 khps. The formula which you posted (and I arrived at myself later) predicts a block every 8.2 hours for my laptop and one every 4.2 hours for the VPS. Since I started yesterday afternoon, I've only generated the one block.

Sound strange? Or am I just having bad luck?

[theymos]

The main part of the formula that I'm uneasy about is the "target probability" of 0.5. 0.5 is used for calculations involving brute-forcing passwords, but maybe this is different. If your blocks consistently take double the amount of time that the formula predicts, use 1 instead.

[lachesis]

The main part of the formula that I'm uneasy about is the "target probability" of 0.5. 0.5 is used for calculations involving brute-forcing passwords, but maybe this is different. If your blocks consistently take double the amount of time that the formula predicts, use 1 instead.

I thought about that. I don't know if 0.5 is valid or not. I'll continue to take observations. I wonder if it writes to the debug log when it has success.

Actually, that formula assumes that you're working on one block until you figure it out. In Bitcoin, aren't multiple nodes working on the same block? When one finishes, the others abandon work on it and choose another block? That was the impression that I had, but it might be wrong.

[theymos]

I wonder if it writes to the debug log when it has success.

BitCoin does say when it has solved a block. Search for "proof-of-work found".

In Bitcoin, aren't multiple nodes working on the same block?

No. Each node's block is unique because it contains their unique public key. Functionally, every hash gives you a totally random number between 0 and the maximum value of a 256-bit number. If the random number is equal to or below the target, you win. So the probability of winning with one hash is target in max.

Starting on another block because somebody else won requires almost no work.

See the BitCoin Wiki "block" article and the BitCoin paper for more info.

[fergalish]

I thought about that. I don't know if 0.5 is valid or not. I'll continue to take observations. I wonder if it writes to the debug log when it has success.

Use a value of 1, not 0.5.  Suppose max=100 and target=10, then 10 out of every 100 hashes will be at or below the target, so your success rate will be 10% NOT 5%.

At the moment target/max ~= 1.5x10^-11 (target~=0x000000000f, which is 36 zeros, so you basically need to throw a dice with 2^36=69 billion sides, and wait until you get a 1), and you're doing 1 million x 86400 = 86.4 billion hashes per day, so you can expect slightly more than one success per day.

It's VERY important to realise that this is the AVERAGE bitcoin creation time, and will only be valid over periods longer than about a week or so.  Because a success event is completely random (I hope, otherwise the hash function is probably not secure and someone will eventually crack it, and therefore bitcoin!), the interval between one success and the next will follow a Poisson distribution with n=0, i.e. an exponential (see wikipedia).  Therefore, with an average rate of, say, 1 success per day, you can expect that roughly 10% of the time, you'll have to wait 2¼ days or more, 1% of the time 4½ days, 0.1% 7 days and so on.

[theymos]

Thanks for clearing that up, fergalish!

[satoshi]

I integrated the hashmeter idea into the SVN version.  It displays khash/s in the left section of the status bar.

Two new log messages:
21/06/2010 01:23 hashmeter   2 CPUs    799 khash/s
21/06/2010 01:23 generated 50.00

grep your debug.log for "generated" to see what you've generated, and grep for "hashmeter" to see the performance.  On windows, use:
 findstr "hashmeter generated" "%appdata%\bitcoin\debug.log"

I have the hashmeter messages once an hour.  How often do you think it should be?