Cryddit
Legendary
Offline
Activity: 924
Merit: 1132
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 02:37:01 AM |
|
Now imagine that you throw a dice with numbers from 1 to 6 and your opponent throws a semi-dice with three possible values from 1 to 3. Who gets the lower number wins the round. In half of the cases you will throw 4-6 and win. In the other half you will have 50:50 chances to win. Thus your chances are 1/2 + 1/4 = 0.75 and his chances are 1/4 = 0.25. Which is 3 times lower.
This doesn't model forging process correctly. I think all are agreed that the presented model is not the right way to do it. But does it accurately state the forging process that the current code implements?
|
|
|
|
Cryddit
Legendary
Offline
Activity: 924
Merit: 1132
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 02:59:13 AM |
|
The analogy with throwing dice is for illustrative purposes only.
This is the problem. 100K account does have advantage over 100x 1K accounts. But this advantage is small. In ur example it's noticeable coz u use conventional dice. If u used dice with 2^64 faces u would get other results. Um, okay. Let's look at it with continuous probabilities on the range 0..1 then. Wallet A has a 100K account and wallet B has a 50K account. Wallet A throws am infinite-sided die mapped to 0..1 and gets N1, wallet B throws the same infinite-sided die and gets N2. Wallet A then takes a default generation time of (say) 10M seconds and divides by 100K x N1, while Wallet B takes the same default generation time and divides by 50K x N2. If B gets the shorter/first time, B forges the new block while if A gets the shorter/first time, A forges the new block. So, for A: 10M seconds /(100K x N1) = 100 seconds / N1 while, for B: 10M seconds/(50K x N2) = 200 seconds / N2 And that means that if N1 < N2 (ie half the time) A always forges the block. Otherwise, if N1 < N2/2, (ie, half the remaining time) A always forges the block. Otherwise, N1 > N2/2, and B forges the block. I ignore the case where N1 == N2/2; we were throwing infnite-sided dice so the probability is infinitesimal.
|
|
|
|
opticalcarrier
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 03:31:26 AM |
|
The analogy with throwing dice is for illustrative purposes only.
This is the problem. 100K account does have advantage over 100x 1K accounts. But this advantage is small. In ur example it's noticeable coz u use conventional dice. If u used dice with 2^64 faces u would get other results. Um, okay. Let's look at it with continuous probabilities on the range 0..1 then. Wallet A has a 100K account and wallet B has a 50K account. Wallet A throws am infinite-sided die mapped to 0..1 and gets N1, wallet B throws the same infinite-sided die and gets N2. Wallet A then takes a default generation time of (say) 10M seconds and divides by 100K x N1, while Wallet B takes the same default generation time and divides by 50K x N2. If B gets the shorter/first time, B forges the new block while if A gets the shorter/first time, A forges the new block. So, for A: 10M seconds /(100K x N1) = 100 seconds / N1 while, for B: 10M seconds/(50K x N2) = 200 seconds / N2 And that means that if N1 < N2 (ie half the time) A always forges the block. Otherwise, if N1 < N2/2, (ie, half the remaining time) A always forges the block. Otherwise, N1 > N2/2, and B forges the block. I ignore the case where N1 == N2/2; we were throwing infnite-sided dice so the probability is infinitesimal. but doesnt that correspond with what we expect as normal, where 1 out of every 3 blocks is forged by B, and 2 out of every 3 blocks is forged by A; since A has 2x as much NXT as B, then it will forge 2x as many blocks?
|
|
|
|
Cryddit
Legendary
Offline
Activity: 924
Merit: 1132
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 03:37:22 AM |
|
So, for A: 10M seconds /(100K x N1) = 100 seconds / N1 while, for B: 10M seconds/(50K x N2) = 200 seconds / N2
And that means that if N1 < N2 (ie half the time) A always forges the block.
Otherwise, if N1 < N2/2, (ie, half the remaining time) A always forges the block.
Otherwise, N1 > N2/2, and B forges the block.
but doesnt that correspond with what we expect as normal, where 1 out of every 3 blocks is forged by B, and 2 out of every 3 blocks is forged by A; since A has 2x as much NXT as B, then it will forge 2x as many blocks? I think it corresponds with the case where A forges 3/4 of the blocks and B forges 1/4 of the blocks, which gives A more advantage than we expect or desire; with 2x as much balance, A ought to be forging 2/3 not 3/4. I'm going to write a toy simulation and check this; it's possible that in my gedanken experiment I messed up some statistics and that in a simulation I won't.
|
|
|
|
Cryddit
Legendary
Offline
Activity: 924
Merit: 1132
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 04:17:22 AM |
|
confirmed. A doubled balance appears to give triple the forging power rather than double. Doesn't matter how many "sides" the dice have. In my example I tried 100K trials and got splits of about 75K and 25K (plus-minus statistical noise). Here is the very simple C code; #include <stdlib.h> #include <stdio.h>
// takes a balance; returns an interval to block forging time. double rollem(double balance){ double roll = 0.0; while (roll == 0.0) roll = ((double) rand())/RAND_MAX; // no divisions by zero return 1000 / (balance * roll); }
// tries a hundred thousand trials and reports the advantage of an // account with supposedly 2x as much forging power. main(){ double A = 10000000; double B = 5000000;
double Atime; double Btime;
int count; int Acount = 0; int Bcount = 0;
for (count = 0; count < 100000; count++){ do{ Atime = rollem (A); Btime = rollem (B); }while (Atime == Btime); // no ties count. if (Atime < Btime) Acount++; else Bcount++; } printf("\nA forged %d blocks, B forged %d blocks\n", Acount, Bcount); printf("With A balance = 2x B balance, A forged %f times as many blocks.\n\n", ((double)Acount) / Bcount); }
And here's the compile/run: ~/src/Cred/testprogs$ gcc -o nxtforging nxtforging.c ~/src/Cred/testprogs$ ./nxtforging
A forged 75141 blocks, B forged 24859 blocks With A balance = 2x B balance, A forged 3.022688 times as many blocks.
~/src/Cred/testprogs$
|
|
|
|
Come-from-Beyond (OP)
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 05:59:48 AM |
|
Alice rolls 1000-face die. Bob rolls 1000-face die. Alice wins if she gets 1 or 2 (her balance is 100k), Bob wins if he gets 1 (his balance is 50k).
How many times Alice will win if she rolls the die 1000 times? How many times Bob will win if he rolls the die 1000 times?
Could anyone answer the questions above?
|
|
|
|
jettico
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 06:37:50 AM |
|
This code in python import random
NBLOCKS = 1000000 W1 = 1000 W2 = 100000
na = nb = 0.
for x in xrange(NBLOCKS): a = random.uniform(0, 1./W1) b = random.uniform(0, 1./W2)
if a<b: na += 1 elif a>b: nb += 1
print nb/na
200.369311317 (instead of 100 as expected) is the DIRECT and VERBATIM implementation of this algorithm: Do http://localhost:7874/nxt?requestType=getState to get value of "lastBlock" 1) Do http://localhost:7874/nxt?requestType=getBlock&block=10621696942372068326 (assuming 10621696942372068326 is the value of "lastBlock") 2) Convert "generationSignature" into binary, and append the public key bytes returned by getAccountPublicKey 3) Calculate SHA256 (generationSignature, publicKey) 4) The first 8 bytes of this value, as an unsigned long in little-endian notation, is the "HIT" value 5) The value of "baseTarget", multiplied by the effective balance of the account, is STATIC_TARGET 6) Repeat steps 3-6 for each active account, and find the one with lowest HIT/STATIC_TARGET ratio. This account will forge the next block taken from here: http://wiki.nxtcrypto.org/wiki/Transparent_ForgingYour game of dice has no connection to this algorithm.
|
|
|
|
Come-from-Beyond (OP)
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 06:59:32 AM |
|
Your game of dice has no connection to this algorithm.
What about the answers on my questions?
|
|
|
|
jettico
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 07:54:03 AM |
|
confirmed. A doubled balance appears to give triple the forging power rather than double. Doesn't matter how many "sides" the dice have.
In my example I tried 100K trials and got splits of about 75K and 25K (plus-minus statistical noise).
Here is the very simple C code; <...>
[/pre]
This code is good. Although it still has a small imperfection: From those steps of the algorithm 3) Calculate SHA256 (generationSignature, publicKey) 4) The first 8 bytes of this value, as an unsigned long in little-endian notation, is the "HIT" value 6) Repeat steps 3-6 for each active account, and find the one with lowest HIT/STATIC_TARGET ratio it is clear that it should be return 1000 * roll / balance; instead of return 1000 / (balance * roll); But it doesn't affect the result because the distribution is uniform. So yes, I confirm that: 1) this program produces the provided result (I reproduced it by compiling and running on my computer) 2) with the above-mentioned fix it correctly models the algorithm described in the wiki (and produces the same result as without the correction).
|
|
|
|
jettico
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 07:55:39 AM |
|
Your game of dice has no connection to this algorithm.
What about the answers on my questions? Those questions are unrelated to the Transparent Forging. Start a new forum thread, let's discuss this new problem there, or explain how it relates to Transparent Forging.
|
|
|
|
Come-from-Beyond (OP)
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 08:05:10 AM |
|
Your game of dice has no connection to this algorithm.
What about the answers on my questions? Those questions are unrelated to the Transparent Forging. Start a new forum thread, let's discuss this new problem there, or explain how it relates to Transparent Forging. Well, it is related to TF. Ur model is not. U can answer my questions and we continue the discussion.
|
|
|
|
jettico
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 08:19:59 AM |
|
I can instead create a FAQ about my code. Q: Why do you use random() instead of first 8 bytes of SHA256 of the transaction hash as described in the algorithm? A: Because SHA256 is designed to generate values that are uniformly distributed. Q: What happens if a==b? Why don't you process this situation? A: The original algorithm described in wiki doesn't give the answer either. But the possibility of this event is proportional to (2 -64) 2 (because 8 first bytes of sha256 have 64 bits) which is about 10 -38 so it is safe in this code to simple skip such cases for clarity. If you are feeling pedantic you can add the line print NBLOCKS-(na+nb) in the end of the code and it will always (well, ok, with an estimated probability of 1-NBLOCKS*(10 -38) = 1-10 -32) give you zero.
|
|
|
|
Come-from-Beyond (OP)
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 08:23:04 AM |
|
I can instead create a FAQ about my code. Q: Why do you use random() instead of first 8 bytes of SHA256 of the transaction hash as described in the algorithm? A: Because SHA256 is designed to generate values that are uniformly distributed. Q: What happens if a==b? Why don't you process this situation? A: The original algorithm described in wiki doesn't give the answer either. But the possibility of this event is proportional to (2 -64) 2 (because 8 first bytes of sha256 have 64 bits) which is about 10 -38 so it is safe in this code to simple skip such cases for clarity. If you are feeling pedantic you can add the line print NBLOCKS-(na+nb) in the end of the code and it will always (well, ok, with an estimated probability of 1-NBLOCKS*(10 -38) = 1-10 -32) give you zero. Hehe, why r u affraid of answering my questions?
|
|
|
|
jettico
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 08:25:05 AM |
|
The analogy with throwing dice is for illustrative purposes only.
This is the problem. 100K account does have advantage over 100x 1K accounts. But this advantage is small. In ur example it's noticeable coz u use conventional dice. If u used dice with 2^64 faces u would get other results. 100K account is 10000 times more likely to forge a block than any single account of 1K, and 100 times more than all of them combined. I tell you once again. I mention dice to illustrate WHY the algorithm is wrong, run my code Cryddit's code or if you want to make sure IF the algorithm is wrong. Well, it is related to TF. Ur model is not. Proof?
|
|
|
|
Come-from-Beyond (OP)
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 08:28:31 AM |
|
Well, it is related to TF. Ur model is not. Proof? We'll come to it step by step. The 1st step requires u to answer the questions.
|
|
|
|
jettico
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 08:30:09 AM Last edit: January 31, 2014, 08:41:59 AM by jettico |
|
I can instead create a FAQ about my code. Q: Why do you use random() instead of first 8 bytes of SHA256 of the transaction hash as described in the algorithm? A: Because SHA256 is designed to generate values that are uniformly distributed. Q: What happens if a==b? Why don't you process this situation? A: The original algorithm described in wiki doesn't give the answer either. But the possibility of this event is proportional to (2 -64) 2 (because 8 first bytes of sha256 have 64 bits) which is about 10 -38 so it is safe in this code to simple skip such cases for clarity. If you are feeling pedantic you can add the line print NBLOCKS-(na+nb) in the end of the code and it will always (well, ok, with an estimated probability of 1-NBLOCKS*(10 -38) = 1-10 -32) give you zero. Hehe, why r u affraid of answering my questions? No, I'm ignoring your attempt to substitute notions (we both remember that you've done it before, and last time you failed to explain how the substituted notion related to my original post). Start a new thread and I shall answer it there. I'm not willing to continue this senseless flood any longer. It doesn't help anyone. If you don't believe me or Cryddit ask someone whom you believe. Ask BCNext, ask Jean-Luc.
|
|
|
|
Come-from-Beyond (OP)
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 08:31:44 AM |
|
No, I'm ignoring your attempt to substitute notions (we both remember that you've done it before).
Start a new thread and I shall answer it there.
Ok. Keep ignoring. Discussion is over, we'll continue it after I get the answers.
|
|
|
|
jettico
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 80
Merit: 10
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 09:34:53 AM |
|
We'll come to it step by step. The 1st step requires u to answer the questions. btw, this is childish. I'm ready to answer any of your questions related to my original post. This question is not until you explain how.
|
|
|
|
starik69
Legendary
Offline
Activity: 1367
Merit: 1000
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 09:36:00 AM |
|
Jettico, you are wrong. ![Tongue](https://bitcointalk.org/Smileys/default/tongue.gif)
|
|
|
|
Come-from-Beyond (OP)
Legendary
Offline
Activity: 2142
Merit: 1010
Newbie
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2014, 10:00:51 AM |
|
We'll come to it step by step. The 1st step requires u to answer the questions. btw, this is childish. I'm ready to answer any of your questions related to my original post. This question is not until you explain how. I don't blame u, coz there is no a good explanation how forging works, but I'm quite tired to explain why people r wrong with their models. In ur case u r wrong coz u analyze an impossible situation when there r only 2 forging accounts in the system. Models doesn't work in extremum conditions.
|
|
|
|
|