elective-stereophonic
elective-stereophonic
Interactive Proof-of-Stake singapore
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Nxt Client: Nxt 1.11.15

Pages: 1 2 [All]

Author Topic: Interactive Proof-of-Stake  (Read 6204 times)

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Interactive Proof-of-Stake
« on: January 05, 2016, 07:54:46 am »

Hi guys! And Happy New Year!   ;D

A new proposal for a new pure Proof-of-Stake protocol by me(solely this time):

http://arxiv.org/abs/1601.00275

Comments:

1. Nxt has similar %% against private fork attack with better distribution (with 28.57% online stake an attacker has ~10% chance to generate a better chain of 10 confirmation, ~.1% to generate a better chain of 60 confs).

2. Dunno anything about implementation. Probably will be implemented in Scorex, mb in form of hybrid though.
« Last Edit: January 06, 2016, 09:17:22 pm by kushti »
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #1 on: January 05, 2016, 02:03:22 pm »

Thanks for sharing! Will read...
Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #2 on: January 05, 2016, 03:41:37 pm »

Thanks for sharing! Will read...

Thanks! I would be happy to get a feedback, in form of heavy but constructive criticism preferably :)
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

jabo38

  • Sr. Member
  • ****
  • Karma: +40/-38
  • Offline Offline
  • Posts: 381
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #3 on: January 06, 2016, 05:51:06 pm »

I'm really looking forward into seeing it in Scorex in some form.  :-)

It is nice to see somebody doing work on trying to make a stronger and better PoS. 
Logged
Never Enough Money

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #4 on: January 07, 2016, 05:00:27 pm »

I'm going further. There are some very new approaches hopefully could resolve concerns around PoS entirely and make it provably more safe than PoW even. I mean the paper from 2015 about decentralized public randomness generation http://eprint.iacr.org/2015/366.pdf (it uses non-standard cryptography assumptions though) and Cothorities(http://dedis.cs.yale.edu/dissent/pres/151009-stanford-cothorities.pdf), also very new approach providing public randomness as well and chain enforcement probably. Another way is a hybrid consensus protocol, and instead of PoW I have an idea of an alternative principle based on Proof-of-Retrievability(http://cs.umd.edu/~amiller/permacoin.pdf). Paper on that will be available in February, hopefully.



 

Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #5 on: January 09, 2016, 05:46:28 pm »

I'm through the paper; but let me first ask the following to remove any doubt: do you really mean that the score of a ticket is b^m (b to power m), and not simply bm? I thought it was a misprint, but it happens two times, on pp. 4 and 5...
Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #6 on: January 09, 2016, 06:22:52 pm »

I'm through the paper; but let me first ask the following to remove any doubt: do you really mean that the score of a ticket is b^m (b to power m), and not simply bm? I thought it was a misprint, but it happens two times, on pp. 4 and 5...

Alright, b^m (b to power m). I also tried b*(m^k), with k=8 seems more or less ok. With k=1, big stakeholders have too much advantage.
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #7 on: January 09, 2016, 07:14:50 pm »

I'm through the paper; but let me first ask the following to remove any doubt: do you really mean that the score of a ticket is b^m (b to power m), and not simply bm? I thought it was a misprint, but it happens two times, on pp. 4 and 5...

Alright, b^m (b to power m). I also tried b*(m^k), with k=8 seems more or less ok. With k=1, big stakeholders have too much advantage.
And what value of R you're thinking of? 16, as in the paper?
Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #8 on: January 09, 2016, 08:06:12 pm »

And what value of R you're thinking of? 16, as in the paper?

With R=16, 1/16 of all accounts in average are participating in a round. Appropriate choice for few hundreds online non-empty accounts. For a bigger network, R=8(or even less) is safer. Adaptive R calculation is needed for a public network(see "Further Work"), as number of generators will go up and down. R=16 was used for simulations.
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #9 on: January 09, 2016, 08:47:58 pm »

Well, even with R=8 there is a big problem with the "hidden chain" attack performed by the guy with max balance. Assume, for example, that the richest guy has 5% of the stake, and others less than 1%. Then, even if he forges alone, he'll get sometimes very heavy weights (5⁸=390625), one his block will easily overweight a very long blockchain created by all others.
Logged

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #10 on: January 10, 2016, 11:32:29 am »

As a side note, I don't understand why you write "However, it is possible to iterate over delta" when discussing the Nxt algorithm on p.3.  Delta is in the right-hand side of (2), which is monotone, and it is not hashed. What advantage could it bring to the attacker then?
Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #11 on: January 11, 2016, 08:28:15 pm »

Well, even with R=8 there is a big problem with the "hidden chain" attack performed by the guy with max balance. Assume, for example, that the richest guy has 5% of the stake, and others less than 1%. Then, even if he forges alone, he'll get sometimes very heavy weights (5⁸=390625), one his block will easily overweight a very long blockchain created by all others.

Oh, that's true. I've fixed ticket's score formula with m * log2 b. Happily, simulations show the updated formula works better against attacks, so adversarial power IPoS is claimed to be safe against is raised to 1/3(33.33%). I've added you to Acknowledgement section  :)  Uploading fixed paper to the Arxiv...
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #12 on: January 11, 2016, 09:27:06 pm »

Well, even with R=8 there is a big problem with the "hidden chain" attack performed by the guy with max balance. Assume, for example, that the richest guy has 5% of the stake, and others less than 1%. Then, even if he forges alone, he'll get sometimes very heavy weights (5⁸=390625), one his block will easily overweight a very long blockchain created by all others.

Oh, that's true. I've fixed ticket's score formula with m * log2 b. Happily, simulations show the updated formula works better against attacks, so adversarial power IPoS is claimed to be safe against is raised to 1/3(33.33%). I've added you to Acknowledgement section  :)  Uploading fixed paper to the Arxiv...

It's m times binary logarithm of b, correct?  Then there should be kind of "best splitting strategy" to maximize the forging chances (with logarithms, it's clear that getting the highest possible value of m is the best strategy). It would be interesting to do the calculations...  But it is important to observe that if everybody uses some kind of splitting strategy, then this l parameter (the number of blocks you must skip before forging the next one) is essentially unimportant (if you have a lot of small accounts, you won't "feel" this restriction).

Also, do I understand correctly that with this algorithm "small" accounts will never forge?  I mean, assume that a rich guy has balance B, and splits it into (say) 10R*l equal accounts. Then, any account that has less than B/(10R*l) has almost no chance to forge?..

Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #13 on: January 12, 2016, 08:27:52 pm »


It's m times binary logarithm of b, correct?  Then there should be kind of "best splitting strategy" to maximize the forging chances (with logarithms, it's clear that getting the highest possible value of m is the best strategy). It would be interesting to do the calculations...  But it is important to observe that if everybody uses some kind of splitting strategy, then this l parameter (the number of blocks you must skip before forging the next one) is essentially unimportant (if you have a lot of small accounts, you won't "feel" this restriction).

Also, do I understand correctly that with this algorithm "small" accounts will never forge?  I mean, assume that a rich guy has balance B, and splits it into (say) 10R*l equal accounts. Then, any account that has less than B/(10R*l) has almost no chance to forge?..

First of all, updated version of the paper is on Arxiv (http://arxiv.org/abs/1601.00275).

Yes, small-stake accounts as well as big stakeholder generate a disproportionally low number of tickets. So for a big stakeholder, aside of attacks, there's the economic incentive to split stake into middle-class accounts.

For attack with stake-splitting, now best number of accounts for 33% stakeholder is about 180(R=16, l=10)(old number with b^m was about 96). Bigger swarm reduces chances to generate a better chain than network's.

Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #14 on: January 12, 2016, 10:33:56 pm »


Yes, small-stake accounts as well as big stakeholder generate a disproportionally low number of tickets. So for a big stakeholder, aside of attacks, there's the economic incentive to split stake into middle-class accounts.

For attack with stake-splitting, now best number of accounts for 33% stakeholder is about 180(R=16, l=10)(old number with b^m was about 96). Bigger swarm reduces chances to generate a better chain than network's.
OK, assume R=16, l=10, for definiteness. Imagine that there there is someone who controls, say, 10% of the stake (or, maybe, several big holders collude so that they do control 10%). Assume also that other accounts are not so big, say, each controls less than 0.1%.  Then, the 10% holder would be able to forge really a lot of blocks in a row, by dividing his stake into 100 equal parts (with overwhelming probability at least one of his accounts gets the maximal m=R).

What do you think of this attack?  In general, the situation that many small holders cannot forge anything together is worrying, I think...
Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #15 on: January 13, 2016, 08:12:01 pm »

OK, assume R=16, l=10, for definiteness. Imagine that there there is someone who controls, say, 10% of the stake (or, maybe, several big holders collude so that they do control 10%). Assume also that other accounts are not so big, say, each controls less than 0.1%.  Then, the 10% holder would be able to forge really a lot of blocks in a row, by dividing his stake into 100 equal parts (with overwhelming probability at least one of his accounts gets the maximal m=R).

What do you think of this attack?  In general, the situation that many small holders cannot forge anything together is worrying, I think...

I'll check both IPoS / Nxt against that, but intuitively, in this case a system is probably vulnerable. I don't worry much about such a scenario though. Economy is about Pareto distribution of wealth. Paper ( http://arxiv.org/abs/1308.3892 ) shows the Bitcoin is about stretched exponential distribution. I can't imagine a system with a single 10+% account and others hold < 0.1%.
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #16 on: January 13, 2016, 09:10:00 pm »

OK, assume R=16, l=10, for definiteness. Imagine that there there is someone who controls, say, 10% of the stake (or, maybe, several big holders collude so that they do control 10%). Assume also that other accounts are not so big, say, each controls less than 0.1%.  Then, the 10% holder would be able to forge really a lot of blocks in a row, by dividing his stake into 100 equal parts (with overwhelming probability at least one of his accounts gets the maximal m=R).

What do you think of this attack?  In general, the situation that many small holders cannot forge anything together is worrying, I think...

I'll check both IPoS / Nxt against that, but intuitively, in this case a system is probably vulnerable. I don't worry much about such a scenario though. Economy is about Pareto distribution of wealth. Paper ( http://arxiv.org/abs/1308.3892 ) shows the Bitcoin is about stretched exponential distribution. I can't imagine a system with a single 10+% account and others hold < 0.1%.
Not necessarily single account, but maybe a collusion  of several big holders. Anyhow, that's all speculations, for now.

Could you clarify also this:
Quote from: mthcl
As a side note, I don't understand why you write "However, it is possible to iterate over delta" when discussing the Nxt algorithm on p.3.  Delta is in the right-hand side of (2), which is monotone, and it is not hashed. What advantage could it bring to the attacker then?

Logged

kushti

  • Board Moderator
  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #17 on: January 14, 2016, 07:38:40 pm »


Not necessarily single account, but maybe a collusion  of several big holders. Anyhow, that's all speculations, for now.

Please note, in Nxt the best strategy for 33% attacker (against exponentially distributed network), is also splitting, into ~= 24 accounts though(via simulations). By splitting stake chance to avoid unlucky hit generation increases.


Could you clarify also this:
Quote from: mthcl
As a side note, I don't understand why you write "However, it is possible to iterate over delta" when discussing the Nxt algorithm on p.3.  Delta is in the right-hand side of (2), which is monotone, and it is not hashed. What advantage could it bring to the attacker then?

Well, for a single block, Delta could be calculated as target function is monotonic. However, in case of hidden chain generation time could be shifted to increase cumulative difficulty. Quick example, say intended delay is 60 seconds(Nxt case), block B could be generated 25 seconds after block A, block C 65 seconds after block B. In this case attacker could "delay"(i.e. insert different timestamp into block header) block B by 5 seconds, (A->B 30 seconds, so base-target penalty disappears). Maybe wording in the paper is misleading, I will re-check. Thanks mthcl!
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #18 on: January 15, 2016, 12:14:50 pm »

Anyhow, in a week or so the BT adjustment algorithm will change, and it will become virtually impossible to play games with it.
Logged

petko

  • Jr. Member
  • **
  • Karma: +24/-0
  • Offline Offline
  • Posts: 98
    • View Profile
    • My blog
Re: Interactive Proof-of-Stake
« Reply #19 on: January 16, 2016, 10:39:36 pm »

Anyhow, in a week or so the BT adjustment algorithm will change, and it will become virtually impossible to play games with it.

Hi, could you please clarify why the new adjustment algorithm makes grinding impossible? The only improvement I see is that BT is not adjusted every block. It is adjusted every 2 blocks, so indeed an improvement, but not really impossible I think. Most probably I don't understand something. Thanks.
Logged

mthcl

  • Hero Member
  • *****
  • Karma: +96/-8
  • Offline Offline
  • Posts: 562
    • View Profile
Re: Interactive Proof-of-Stake
« Reply #20 on: January 16, 2016, 11:44:25 pm »

Anyhow, in a week or so the BT adjustment algorithm will change, and it will become virtually impossible to play games with it.

Hi, could you please clarify why the new adjustment algorithm makes grinding impossible? The only improvement I see is that BT is not adjusted every block. It is adjusted every 2 blocks, so indeed an improvement, but not really impossible I think. Most probably I don't understand something. Thanks.
As kushti observed just above, in the current situation the forger may delay a block a little to influence the BT adjustment. Since currently the BT can change a lot (two times!) in just one step, every possibility to play with it can be considered a danger. With the new algorithm delaying one block makes a very small effect on the BT, because of the averaging.
Logged
Pages: 1 2 [All]
 

elective-stereophonic
elective-stereophonic
assembly
assembly