elective-stereophonic
elective-stereophonic
Transparent Forging algorithm  
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Stable Nxt Client: Nxt 1.12.2

Author Topic: Transparent Forging algorithm  (Read 5098 times)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Transparent Forging algorithm
« on: April 23, 2014, 01:30:06 pm »

The following is our joint proposal with ChuckOne and mczarnek about the Transparent Forging.

Below, "the article" means this one: http://www.docdroid.net/bfwb/forging0-4-2.pdf.html

We are considering the future one-block-per-minute regime. The main changes to the current algorithm that we propose are:

(1) there should be an upper limit, i.e., an account with more than X NXT forges as if it had exactly X NXT (e.g., X=5M). Reason: see "conclusions" (the last one) in the end of Section 4 of the article.


(2) there should also be a lower limit, i.e., an account with less than Y NXT does not forge at all. This will make costly those games with non-forging discussed in Section 5 of the article. Also, this would encourage leasing the forging power (so that more people would become happy because they'll receive at least something).

Now, as for the value of Y, it need not be constant, it can actually change! In normal situation (there are not many non-forging events) it can be relatively low, say, 1000NXT. However, if someone is starting playing games (and so there are many non-forging events), then Y increases in order to protect the network.


(3) It would be indeed a good idea to introduce randomness to the TF. The reasons for this were discussed here: https://nxtforum.org/transparent-forging/jftr-randomness-without-cheating/msg11143/#msg11143. The algorithm we propose is in the end of Section 6 of the article, let me reproduce it here:

(a) each forging account must maintain a hashchain of some (large) length (actually, the nodes must maintain them for their accounts), and publish the last hash;
(b) at blocks Nm, m=1,2,3,..., the list of K richest accounts with respect to the effective balance is formed, and this list becomes valid  for blocks Nm+L,...,N(m+1)+L-1;
(c) special ``randomizing'' blocks are forged just in between of every two normal blocks (this can be adjusted, maybe does not need to be so frequent);
(d) randomizing blocks are forged by the accounts from the valid list, e.g., in the cyclic order; they contain the hash from the hashchain preceding to the one already published (so the forger cannot cheat);
(e) to determine the forger of the next block (number n), the random number we use is
sha256(what was there before, sum of hashes in L' last randomizing blocks published before the block n-L).

One may take e.g. N=1440,K=100,L=10, L'=50, but, of course, these constants may be adjusted. In particular, the value of K must be neither too small, nor too large. If it is small, the danger is that the bad guy controls all K top accounts. On the other hand, if it is too large, then some accounts among the top K would be (relatively) small (for a rich guy), so he can start thinking about playing non-forging games.

With this approach, by the way, we can predict the next L forgers (but not more!), which was also a desirable feature of TF, as far as the authors remember.

The point of having the richest accounts do the randomization job is the following: it is probably impossible for the attacker to control e.g. top 100 accounts, that is just too expensive.
And another point: since the accounts must be big, cheating by not publishing the random number now becomes very expensive as well (an account that does not forge the randomizing block when it must to, is banned and so unable to forge normal blocks for some period).


OK. Let the discussion begin.
« Last Edit: April 23, 2014, 03:47:49 pm by mthcl »
Logged

bitcoinpaul

  • Hero Member
  • *****
  • Karma: +590/-590
  • Offline Offline
  • Posts: 3097
  • Karmageddon
    • View Profile
Re: Transparent Forging algorithm
« Reply #1 on: April 23, 2014, 01:48:21 pm »

Thanks for your brainjuice, guys!

I wonder how this correlates to CfB's thoughts about transparent forging.
Logged
Like my Avatar? Reply now! NXT-M5JR-2L5Z-CFBP-8X7P3

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Transparent Forging algorithm
« Reply #2 on: April 23, 2014, 02:39:50 pm »

And another point: since the accounts must be big, cheating by not publishing the random number now becomes very expensive as well (an account that does not forge the randomizing block when it must to, is banned and so unable to forge normal blocks for some period).

How is solved the problem of an irrational forger?
Logged

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Transparent Forging algorithm
« Reply #3 on: April 23, 2014, 02:42:15 pm »

What is "the problem of an irrational forger"?
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Transparent Forging algorithm
« Reply #4 on: April 23, 2014, 02:45:33 pm »

What is "the problem of an irrational forger"?

It's a kamikaze forger who doesn't care about money loss (i.e. USA govt).
Logged

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Transparent Forging algorithm
« Reply #5 on: April 23, 2014, 02:48:19 pm »

Then he'll quickly find himself in a situation when most of his money is unable to forge (we can even increase the penalty for non-forging, just in case).
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Transparent Forging algorithm
« Reply #6 on: April 23, 2014, 02:57:31 pm »

Then he'll quickly find himself in a situation when most of his money is unable to forge (we can even increase the penalty for non-forging, just in case).

Good. How high the penalty should be? 5 blocks, 1440 blocks, 16807 blocks?
Logged

ChuckOne

  • Hero Member
  • *****
  • Karma: +293/-17
  • Offline Offline
  • Posts: 3450
  • ☕ NXT-4BTE-8Y4K-CDS2-6TB82
    • View Profile
Re: Transparent Forging algorithm
« Reply #7 on: April 23, 2014, 03:09:56 pm »

1440 blocks. Because otherwise, the guy just creates another account.

EDIT: if we want a bigger penalty, we need to increase the coin maturity as well.
Logged

mczarnek

  • Hero Member
  • *****
  • Karma: +68/-4
  • Offline Offline
  • Posts: 898
    • View Profile
    • Nxt Place - Craigslist for Nxt
Re: Transparent Forging algorithm
« Reply #8 on: April 23, 2014, 11:24:19 pm »

1440 blocks. Because otherwise, the guy just creates another account.

EDIT: if we want a bigger penalty, we need to increase the coin maturity as well.

Wouldn't necessarily have to increase the coin maturity, if we lock it up, then they lose access to that money, they can't just move it to another account, right?  Though certainly just resetting their coin maturity is the easiest way to do it.
Logged
NXT Organization: Tech
Donations greatly appreciated: NXT-DWVJ-G89C-RHNL-6QW6Q

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Transparent Forging algorithm
« Reply #9 on: April 24, 2014, 06:18:40 am »

1440 is a magic number. It may not work.
Logged

ChuckOne

  • Hero Member
  • *****
  • Karma: +293/-17
  • Offline Offline
  • Posts: 3450
  • ☕ NXT-4BTE-8Y4K-CDS2-6TB82
    • View Profile
Re: Transparent Forging algorithm
« Reply #10 on: April 24, 2014, 06:22:39 am »

Wouldn't necessarily have to increase the coin maturity, if we lock it up, then they lose access to that money, they can't just move it to another account, right?  Though certainly just resetting their coin maturity is the easiest way to do it.

Err, I would not like to have my NXTs locked up just because there was a power outage. I would live with forging-penalty but I want access to my NXT everywhere and everywhen.
Logged

ChuckOne

  • Hero Member
  • *****
  • Karma: +293/-17
  • Offline Offline
  • Posts: 3450
  • ☕ NXT-4BTE-8Y4K-CDS2-6TB82
    • View Profile
Re: Transparent Forging algorithm
« Reply #11 on: April 24, 2014, 06:31:13 am »

1440 is a magic number. It may not work.

Suggestions then? 1440 blocks seems reasonably large to me.
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: Transparent Forging algorithm
« Reply #12 on: April 24, 2014, 12:04:32 pm »

Suggestions then? 1440 blocks seems reasonably large to me.

I prefer 1337 blocks. But only math can give the correct answer. Let's wait for mthcl.
Logged

bitcoinpaul

  • Hero Member
  • *****
  • Karma: +590/-590
  • Offline Offline
  • Posts: 3097
  • Karmageddon
    • View Profile
Re: Transparent Forging algorithm
« Reply #14 on: April 24, 2014, 03:05:19 pm »

Thanks, mthcl. JL, implement it  ;D
Logged
Like my Avatar? Reply now! NXT-M5JR-2L5Z-CFBP-8X7P3

ChuckOne

  • Hero Member
  • *****
  • Karma: +293/-17
  • Offline Offline
  • Posts: 3450
  • ☕ NXT-4BTE-8Y4K-CDS2-6TB82
    • View Profile
Re: Transparent Forging algorithm
« Reply #15 on: April 24, 2014, 07:49:48 pm »

1442 is too large. Because an attacker can create an new forging account in 1441 blocks. ;) So, he wins 1 block. Could be important. :D
Logged

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Transparent Forging algorithm
« Reply #16 on: April 24, 2014, 11:08:21 pm »

Another point, why too much predictability may be bad.  Imagine the bad guy can calculate who will be the potential forgers for the next (say) 1440 blocks. Then, he may use this knowledge to plan a DDOS attack: imagine that, by analyzing the forger list and the locations of their nodes,  one can deduce that it would be necessary to DDOS here, here, and there at a certain time, to make the forging stop for, say, one hour.

So, IMHO it's good that under the above algorithm only L (e.g., =10) next forgers are predictable.
Logged

mczarnek

  • Hero Member
  • *****
  • Karma: +68/-4
  • Offline Offline
  • Posts: 898
    • View Profile
    • Nxt Place - Craigslist for Nxt
Re: Transparent Forging algorithm
« Reply #17 on: April 25, 2014, 02:01:05 am »

Err, I would not like to have my NXTs locked up just because there was a power outage. I would live with forging-penalty but I want access to my NXT everywhere and everywhen.

I see where you are coming from.. 1440 should be enough, if he can attack the network once per day (plus however long it takes to win your first forging block), I suspect that's sufficient.
Logged
NXT Organization: Tech
Donations greatly appreciated: NXT-DWVJ-G89C-RHNL-6QW6Q

doctorevil

  • Jr. Member
  • **
  • Karma: +27/-0
  • Offline Offline
  • Posts: 42
    • View Profile
Re: Transparent Forging algorithm
« Reply #18 on: April 27, 2014, 10:48:53 pm »

@mathcl, since you asked for my opinion on this: At first glance nothing jumps out at me as horribly misguided in your proposal.  That being said, this is not an endorsement.  I suck at reasonsing about multiparty protocols and this is the sort of thing where I don't think I'd intimately understand the protocol until I actually tried to implement it. 

Also, skimming “Protocols for multiparty coin toss with dishonest majority”, makes me realize a lot of people have been thinking about this problem for a while and that it would require a lot deeper dive into the literature to understand the underlying problem well enough to qualify me to make a substantive comment on the matter.
Logged
You know, I have one simple request. And that is to have sharks with frickin' laser beams attached to their heads! Now evidently, my cycloptic colleague informs me that that can't be done. Can you remind me what I pay you people for? Honestly, throw me a bone here.

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Transparent Forging algorithm
« Reply #19 on: April 27, 2014, 11:11:16 pm »

@mathcl, since you asked for my opinion on this: At first glance nothing jumps out at me as horribly misguided in your proposal.  That being said, this is not an endorsement.  I suck at reasonsing about multiparty protocols and this is the sort of thing where I don't think I'd intimately understand the protocol until I actually tried to implement it. 

Also, skimming “Protocols for multiparty coin toss with dishonest majority”, makes me realize a lot of people have been thinking about this problem for a while and that it would require a lot deeper dive into the literature to understand the underlying problem well enough to qualify me to make a substantive comment on the matter.
Many thanks!  I looked at the reference; the main difference from their situation, IMO, is that we can ban the guys that skip their turn. That's why we proposed that only rich guys provide the randomness: if someone skips his turn, he cannot do normal forging for many rounds, and so the small bias from skipping would not compensate the inability to gain fees.
Logged
 

elective-stereophonic
elective-stereophonic
assembly
assembly