Topic: Interactive Proof-of-Stake (Read 9478 times)

kushti · « **on:** January 05, 2016, 07:54:46 am »

Hi guys! And Happy New Year!

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.

mthcl · « **Reply #1 on:** January 05, 2016, 02:03:22 pm »

Thanks for sharing! Will read...

kushti · « **Reply #2 on:** January 05, 2016, 03:41:37 pm »

Quote from: mthcl on January 05, 2016, 02:03:22 pm

Thanks for sharing! Will read...

Thanks! I would be happy to get a feedback, in form of heavy but constructive criticism preferably

jabo38 · « **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.

kushti · « **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.

mthcl · « **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...

kushti · « **Reply #6 on:** January 09, 2016, 06:22:52 pm »

Quote from: mthcl 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...

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.

mthcl · « **Reply #7 on:** January 09, 2016, 07:14:50 pm »

Quote from: kushti on January 09, 2016, 06:22:52 pm

Quote from: mthcl 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...

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?

kushti · « **Reply #8 on:** January 09, 2016, 08:06:12 pm »

Quote from: mthcl on January 09, 2016, 07:14:50 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.

mthcl · « **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.

mthcl · « **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?

kushti · « **Reply #11 on:** January 11, 2016, 08:28:15 pm »

Quote from: mthcl 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.

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

mthcl · « **Reply #12 on:** January 11, 2016, 09:27:06 pm »

Quote from: kushti on January 11, 2016, 08:28:15 pm

Quote from: mthcl 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.

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

kushti · « **Reply #13 on:** January 12, 2016, 08:27:52 pm »

Quote from: mthcl on January 11, 2016, 09:27:06 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.

mthcl · « **Reply #14 on:** January 12, 2016, 10:33:56 pm »

Quote from: kushti on January 12, 2016, 08:27:52 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...

kushti · « **Reply #15 on:** January 13, 2016, 08:12:01 pm »

Quote from: mthcl on January 12, 2016, 10:33:56 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%.

mthcl · « **Reply #16 on:** January 13, 2016, 09:10:00 pm »

Quote from: kushti on January 13, 2016, 08:12:01 pm

Quote from: mthcl on January 12, 2016, 10:33:56 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?

kushti · « **Reply #17 on:** January 14, 2016, 07:38:40 pm »

Quote from: mthcl on January 13, 2016, 09:10:00 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.

Quote from: mthcl on January 13, 2016, 09:10:00 pm

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!

mthcl · « **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.

petko · « **Reply #19 on:** January 16, 2016, 10:39:36 pm »

Quote from: mthcl 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.

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.

News:

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