Transparent mining, or What makes Nxt a 2nd generation currency - page 5.

jettico

member

Activity: 80

Merit: 10

Quote from: Come-from-Beyond on January 31, 2014, 04:23:04 AM

Quote from: jettico on January 31, 2014, 04: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)² (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

Quote

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

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: jettico on January 31, 2014, 04:25:05 AM

Quote

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

Activity: 80

Merit: 10

Quote from: Come-from-Beyond on January 30, 2014, 05:10:09 PM

Quote from: jettico on January 30, 2014, 04:25:33 PM

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.

Quote

Well, it is related to TF. Ur model is not.

Proof?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: jettico on January 31, 2014, 04: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)² (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

Quote

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

Activity: 80

Merit: 10

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)² (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

Quote

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

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: jettico on January 31, 2014, 03:55:39 AM

Quote from: Come-from-Beyond on January 31, 2014, 02:59:32 AM

Quote from: jettico on January 31, 2014, 02:37:50 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

Activity: 80

Merit: 10

Quote from: Come-from-Beyond on January 31, 2014, 02:59:32 AM

Quote from: jettico on January 31, 2014, 02:37:50 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.

jettico

member

Activity: 80

Merit: 10

Quote from: Cryddit on January 31, 2014, 12: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; <...>

[/pre]

This code is good. Although it still has a small imperfection:

From those steps of the algorithm

Quote

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

Quote

return 1000 * roll / balance;

instead of

Quote

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

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: jettico on January 31, 2014, 02:37:50 AM

Your game of dice has no connection to this algorithm.

What about the answers on my questions?

jettico

member

Activity: 80

Merit: 10

This code in python

Quote from: jettico on January 30, 2014, 03:48:58 PM

Quote

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

Quote

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_Forging

Your game of dice has no connection to this algorithm.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

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?

Cryddit

legendary

Activity: 924

Merit: 1132

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 
#include 

// 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$

Cryddit

legendary

Activity: 924

Merit: 1132

Quote from: opticalcarrier on January 30, 2014, 11:31:26 PM

Quote from: Cryddit on January 30, 2014, 10:59:13 PM

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.

opticalcarrier

full member

Activity: 238

Merit: 100

Quote from: Cryddit on January 30, 2014, 10:59:13 PM

Quote from: Come-from-Beyond on January 30, 2014, 05:10:09 PM

Quote from: jettico on January 30, 2014, 04:25:33 PM

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

Activity: 924

Merit: 1132

Quote from: Come-from-Beyond on January 30, 2014, 05:10:09 PM

Quote from: jettico on January 30, 2014, 04:25:33 PM

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.

Cryddit

legendary

Activity: 924

Merit: 1132

Quote from: Come-from-Beyond on January 30, 2014, 04:10:41 PM

Quote from: jettico on January 30, 2014, 04:04:42 PM

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?

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: jettico on January 30, 2014, 04:25:33 PM

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.

sepehr

sr. member

Activity: 399

Merit: 250

Cryptocurrency Evangelist

I receive this every time it wants to initiate a block creation:

Quote

[2014-01-31 00:24:53.195] DEBUG: Error in block generation thread
java.lang.NullPointerException
at Nxt$Block.getLastBlocks(Nxt.java:1353)
at Nxt$Account.getGuaranteedBalance(Nxt.java:579)
at Nxt$Account.getEffectiveBalance(Nxt.java:516)
at Nxt$8.run(Nxt.java:6574)
at java.util.concurrent.Executors$RunnableAdapter.call(Unknown Source)
at java.util.concurrent.FutureTask.runAndReset(Unknown Source)
at java.util.concurrent.ScheduledThreadPoolExecutor$ScheduledFutureTask.
access$301(Unknown Source)
at java.util.concurrent.ScheduledThreadPoolExecutor$ScheduledFutureTask.
run(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
at java.lang.Thread.run(Unknown Source)

Any Idea why this happen?

jettico

member

Activity: 80

Merit: 10

Reason? In the previous post I provided a python scrypt that does EXACTLY what is stated in this wiki page. http://wiki.nxtcrypto.org/wiki/Transparent_Forging

The analogy with throwing dice is for illustrative purposes only.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: jettico on January 30, 2014, 04:04:42 PM

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.

Topic: Transparent mining, or What makes Nxt a 2nd generation currency - page 5. (Read 35830 times)