elective-stereophonic
elective-stereophonic
NXT stake-grinding attack?
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Stable Nxt Client: Nxt 1.12.2

Pages: 1 2 [All]

Author Topic: NXT stake-grinding attack?  (Read 9145 times)

coretechs

  • Sr. Member
  • ****
  • Karma: +161/-1
  • Offline Offline
  • Posts: 436
    • View Profile
NXT stake-grinding attack?
« on: February 26, 2015, 02:33:09 am »

https://download.wpsoftware.net/bitcoin/alts.pdf

Quote
In its initial incarnation, NXT was susceptible to a trivial stake-grinding attack (to be described below) and could not achieve any consensus. Since becoming closed-source while spamming technically-illiterate claims at popular conferences, it has fallen out of scope of this document

Does anyone know more about the stake-grinding attack referenced here?  Does the "initial incarnation" refer to something that happened right after NXT was launched?
Logged
https://ardorportal.org - Ardor blockchain explorer | https://nxtportal.org - Nxt blockchain explorer | http://bitcoindoc.com - The Rise and Rise of Bitcoin
ARDOR-T43P-R2K9-8W79-9W2AL | NXT-WY9K-ZMTT-QQTT-3NBL7

jones

  • Hero Member
  • *****
  • Karma: +310/-8
  • Offline Offline
  • Posts: 1043
  • write code not war
    • View Profile
    • jNxt
Re: NXT stake-grinding attack?
« Reply #1 on: February 26, 2015, 02:47:17 am »

https://download.wpsoftware.net/bitcoin/alts.pdf

Quote
In its initial incarnation, NXT was susceptible to a trivial stake-grinding attack (to be described below) and could not achieve any consensus. Since becoming closed-source while spamming technically-illiterate claims at popular conferences, it has fallen out of scope of this document

Does anyone know more about the stake-grinding attack referenced here?  Does the "initial incarnation" refer to something that happened right after NXT was launched?

Edit:
"Because NXT is a new and scary technology that I don't feel like learning more about to make this document I'm going to say it has the same vulnerability that other earlier PoS systems had to get rid of it"

Stake grinding was a technique based around PoS currencies which used coin age, which nxt never was. BCnext originally was going to use coin age, but was dissuaded to do so by cunicula if I remember my history correctly.

Bitcoiners are scared :)
Logged
-- Jones NXT-RJU8-JSNR-H9J4-2KWKY

Tosch110

  • Hero Member
  • *****
  • Karma: +211/-18
  • Offline Offline
  • Posts: 2365
    • View Profile
Re: NXT stake-grinding attack?
« Reply #2 on: February 26, 2015, 02:57:49 am »

Stake grinding was a technique based around PoS currencies which used coin age, which nxt never was. BCnext originally was going to use coin age, but was dissuaded to do so by cunicula if I remember my history correctly.

I have something familiar in mind.

Bitcoiners are scared :)

Quote from: Douglas Crockford
Weaving the Threads
- The people who should be first to recognize the value of innovation are often the last
- Obsolete technologies fade away slowly

coretechs

  • Sr. Member
  • ****
  • Karma: +161/-1
  • Offline Offline
  • Posts: 436
    • View Profile
Re: NXT stake-grinding attack?
« Reply #3 on: February 26, 2015, 03:19:13 am »

I'm surprised that he confused PPcoin with NXT, especially considering how recently the paper is dated.
Logged
https://ardorportal.org - Ardor blockchain explorer | https://nxtportal.org - Nxt blockchain explorer | http://bitcoindoc.com - The Rise and Rise of Bitcoin
ARDOR-T43P-R2K9-8W79-9W2AL | NXT-WY9K-ZMTT-QQTT-3NBL7

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: NXT stake-grinding attack?
« Reply #4 on: February 26, 2015, 03:31:14 am »

I'm surprised that he confused PPcoin with NXT, especially considering how recently the paper is dated.
both have three letters "PPC" and "NXT" and it is easy to get them mixed up
Logged
There are over 1000 people in SuperNET slack! http://slackinvite.supernet.org/ automatically sends you an invite

I am just a simple C programmer

achim

  • Hero Member
  • *****
  • Karma: +50/-6
  • Offline Offline
  • Posts: 648
    • View Profile
Re: NXT stake-grinding attack?
« Reply #5 on: February 26, 2015, 08:26:25 am »

Quote
could not achieve any consensus.

This is the part I love the most  :)

In the old days we used to post block height and ids daily to check if we were on a fork.
The network may have been fragmented a little bit during the zombie node attacks and such, but consensus was always reached sooner or later.

coud not achieve any consensus... lol
« Last Edit: February 26, 2015, 11:01:13 am by achim »
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #6 on: February 26, 2015, 10:58:29 am »

https://download.wpsoftware.net/bitcoin/alts.pdf

Quote
In its initial incarnation, NXT was susceptible to a trivial stake-grinding attack (to be described below) and could not achieve any consensus. Since becoming closed-source while spamming technically-illiterate claims at popular conferences, it has fallen out of scope of this document

Does anyone know more about the stake-grinding attack referenced here?  Does the "initial incarnation" refer to something that happened right after NXT was launched?

The author of that "whitepaper" is a bitcoiner. It explains all.
Logged

youyou

  • Sr. Member
  • ****
  • Karma: +44/-46
  • Offline Offline
  • Posts: 472
    • View Profile
Re: NXT stake-grinding attack?
« Reply #7 on: February 26, 2015, 11:11:33 am »

Quote
Since becoming closed-source while spamming technically-
illiterate claims at popular conferences, it has fallen out of scope of this document.

 ???
Logged

valarmg

  • Hero Member
  • *****
  • Karma: +178/-57
  • Offline Offline
  • Posts: 1766
    • View Profile
Re: NXT stake-grinding attack?
« Reply #8 on: February 26, 2015, 11:32:45 am »

I'm surprised that he confused PPcoin with NXT, especially considering how recently the paper is dated.

Seems that quote is copy-pasted from his pos.pdf from back in April/May.

Anyway, having that quote in the document indicates that much of the "treatise" is likely to be unresearched and wrong. Saves having to waste time reading it.
Logged
NXT-CSED-4PK5-AR4V-6UB5V

msin

  • Hero Member
  • *****
  • Karma: +138/-18
  • Offline Offline
  • Posts: 1288
    • View Profile
Re: NXT stake-grinding attack?
« Reply #9 on: February 26, 2015, 01:46:31 pm »

If I were to write a paper on Bitcoiner authors, I would describe this guy as an "incredible dumbass"
Logged

Tosch110

  • Hero Member
  • *****
  • Karma: +211/-18
  • Offline Offline
  • Posts: 2365
    • View Profile
Re: NXT stake-grinding attack?
« Reply #10 on: February 26, 2015, 01:52:53 pm »

If I were to write a paper on Bitcoiner authors, I would describe this guy as an "incredible dumbass"

but he knows scientific paper format... has to be legit.

coretechs

  • Sr. Member
  • ****
  • Karma: +161/-1
  • Offline Offline
  • Posts: 436
    • View Profile
Re: NXT stake-grinding attack?
« Reply #11 on: February 26, 2015, 03:32:32 pm »

Seems that quote is copy-pasted from his pos.pdf from back in April/May.

Anyway, having that quote in the document indicates that much of the "treatise" is likely to be unresearched and wrong. Saves having to waste time reading it.

Actually the first half of the paper isn't bad, it does a pretty good job explaining bitcoin / pow consensus.  It would have been nice to read a criticism of NXT if the author had the same level of understanding about it.
Logged
https://ardorportal.org - Ardor blockchain explorer | https://nxtportal.org - Nxt blockchain explorer | http://bitcoindoc.com - The Rise and Rise of Bitcoin
ARDOR-T43P-R2K9-8W79-9W2AL | NXT-WY9K-ZMTT-QQTT-3NBL7

Daedelus

  • Hero Member
  • *****
  • Karma: +230/-12
  • Offline Offline
  • Posts: 3280
    • View Profile
Re: NXT stake-grinding attack?
« Reply #12 on: March 01, 2015, 02:09:07 pm »

If I were to write a paper on Bitcoiner authors, I would describe this guy as an "incredible dumbass"

but he knows scientific paper format... has to be legit.

Yup, and it's a PDF. So I can't see how it can't be anything other than 100% watertight.
Logged
NXT: NXT-4CS7-S4N5-PTH5-A8R2Q

kushti

  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: NXT stake-grinding attack?
« Reply #13 on: March 19, 2015, 09:51:46 am »

The quality of the treatise is just horrible. And it seems Andrew hasn't an idea about a "consensus"(can't get totally which kind of consensus he has assumed) & why proof-of-work was proposed for anonymous Byzantine Agreement (see intro https://eprint.iacr.org/2014/765.pdf for details)
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

kushti

  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: NXT stake-grinding attack?
« Reply #14 on: March 21, 2015, 02:43:15 am »

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

Daedelus

  • Hero Member
  • *****
  • Karma: +230/-12
  • Offline Offline
  • Posts: 3280
    • View Profile
Re: NXT stake-grinding attack?
« Reply #15 on: March 21, 2015, 09:27:55 am »

I saw. Feels to me you are calling his bluff, far too many excuses for not doing a full analysis were given in those few paragraphs..  :D I don't know how you can make these kind of claims without academic rigor.
Logged
NXT: NXT-4CS7-S4N5-PTH5-A8R2Q

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #16 on: March 21, 2015, 10:09:00 am »

I don't know how you can make these kind of claims without academic rigor.

Easily. Science of decentralized consensus doesn't have established paradigms yet.
Logged

kushti

  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: NXT stake-grinding attack?
« Reply #17 on: March 21, 2015, 06:58:25 pm »

I don't know how you can make these kind of claims without academic rigor.

Easily. Science of decentralized consensus doesn't have established paradigms yet.


Disagree, it's around for ~50 years or maybe even more. Internet of today wouldn't be possible without a bunch of fault- and byzantine-tolerant algos. The innovation around blockchain is sybil-resistent solution to anonymous Byzantine agreement for building decentralized append log(a.k.a. versioned database a.k.a. blockchain).
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #18 on: March 21, 2015, 07:44:24 pm »

Disagree, it's around for ~50 years or maybe even more. Internet of today wouldn't be possible without a bunch of fault- and byzantine-tolerant algos.

Haha, it's cool that you mentioned byzantine-tolerant algos. I claim that Satoshi has not solved byzantine generals problem. Do you agree or not? If not, I'd like to hear your reasoning.
Logged

kushti

  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: NXT stake-grinding attack?
« Reply #19 on: March 22, 2015, 03:25:18 am »

Haha, it's cool that you mentioned byzantine-tolerant algos. I claim that Satoshi has not solved byzantine generals problem. Do you agree or not? If not, I'd like to hear your reasoning.

Again, here's the outstanding paper on that https://eprint.iacr.org/2014/765.pdf
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #20 on: March 22, 2015, 07:32:27 am »

Again, here's the outstanding paper on that https://eprint.iacr.org/2014/765.pdf

Aye, it's quite good, but it proves my claim about Satoshi.

Regarding 50 years, a link to a whitepaper dated that old would prove your words, do you have one?
Logged

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: NXT stake-grinding attack?
« Reply #21 on: March 22, 2015, 07:48:49 am »

Again, here's the outstanding paper on that https://eprint.iacr.org/2014/765.pdf

Aye, it's quite good, but it proves my claim about Satoshi.

Regarding 50 years, a link to a whitepaper dated that old would prove your words, do you have one?
so this means satoshi didnt prove it, but he did solve it and now this paper is proving it?
Logged
There are over 1000 people in SuperNET slack! http://slackinvite.supernet.org/ automatically sends you an invite

I am just a simple C programmer

kushti

  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: NXT stake-grinding attack?
« Reply #22 on: March 22, 2015, 07:54:41 am »

I don't quite follow both of you guys  :)
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #23 on: March 22, 2015, 08:48:12 am »

so this means satoshi didnt prove it, but he did solve it and now this paper is proving it?

Satoshi solved another problem. If anyone solved Byzantine Generals problem then they would get that 1/3 of rogue entities is enough to conduct a successful attack. 1/3, not 1/2.
Logged

kushti

  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: NXT stake-grinding attack?
« Reply #24 on: March 22, 2015, 09:01:40 am »

Satoshi solved another problem. If anyone solved Byzantine Generals problem then they would get that 1/3 of rogue entities is enough to conduct a successful attack. 1/3, not 1/2.

There are different Byzantine Agreement solutions around with own tolerance to adversary/honest ratio(I saw 1/3, 1/2, 1/1). And it seems you haven't read Backbone's paper yet, Byzantine Agreement model proposed there allows 1/1 ratio if f -> 0 (so to say very roughly 50+% mining power if block propagation within seconds and block generation every 10 minutes)
« Last Edit: March 22, 2015, 09:06:41 am by kushti »
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #25 on: March 22, 2015, 09:24:50 am »

There are different Byzantine Agreement solutions around with own tolerance to adversary/honest ratio(I saw 1/4, 1/3, 1/2)...

Now my turn to say "I disagree".

There is only one BGP and it has only 2 scenarios:
- 1/3 of rogue participants is enough to break the system if we don't have a way to verify who signed a message
- Even zillions of rogue participants is not enough to break the system if we do have a way to verify who signed a message
A formal proof of this can be found here - http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf

Solutions that you call "different Byzantine Agreement ... 1/4, 1/3, 1/2" is a combined problem of Byzantine Generals + Sybil attack. PoW and PoS are used as a sybil attack mitigation mechanism based on resource testing. We could imagine Bitcoin that uses proof-of-X, where X allows 50% of miners to trick the system by increasing their "weight" 4-fold (e.g. by splitting identities). In this case we would get Bitcoin vulnerable to 1/5 attack. Have you noticed the trick? I changed only the way how sybil attack is mitigated and reduced 51% attack to 21% one. I didn't change BGP component at all.
« Last Edit: March 22, 2015, 09:27:02 am by Come-from-Beyond »
Logged

kushti

  • Sr. Member
  • ****
  • Karma: +184/-5
  • Offline Offline
  • Posts: 384
  • Nxt Core & Apps Dev
    • View Profile
Re: NXT stake-grinding attack?
« Reply #26 on: March 22, 2015, 09:44:26 am »

Now my turn to say "I disagree".

There is only one BGP and it has only 2 scenarios:
- 1/3 of rogue participants is enough to break the system if we don't have a way to verify who signed a message
- Even zillions of rogue participants is not enough to break the system if we do have a way to verify who signed a message
A formal proof of this can be found here - http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf

Solutions that you call "different Byzantine Agreement ... 1/4, 1/3, 1/2" is a combined problem of Byzantine Generals + Sybil attack. PoW and PoS are used as a sybil attack mitigation mechanism based on resource testing. We could imagine Bitcoin that uses proof-of-X, where X allows 50% of miners to trick the system by increasing their "weight" 4-fold (e.g. by splitting identities). In this case we would get Bitcoin vulnerable to 1/5 attack. Have you noticed the trick? I changed only the way how sybil attack is mitigated and reduced 51% attack to 21% one. I didn't change BGP component at all.

1. See e.g. http://18.7.29.232/bitstream/handle/1721.1/14368/20051076.pdf?sequence=1 for different options
2. Why don't you want just to read the paper instead of writing something strange? If you disagree with paper, write detailed feedback paper please and share with paper authors. I'm going to leave the forum crapgrinding
Logged
for donations / messages: NXT-PKXM-WH25-UXXG-CJAVD (alias: kushti)

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #27 on: March 22, 2015, 10:15:30 am »

1. See e.g. http://18.7.29.232/bitstream/handle/1721.1/14368/20051076.pdf?sequence=1 for different options

Funny joke - linking to a 60-page document that doesn't have search option.  ;D What page are you referring to?


2. Why don't you want just to read the paper instead of writing something strange? If you disagree with paper, write detailed feedback paper please and share with paper authors. I'm going to leave the forum crapgrinding

I did read it. But I expected that if you mention it that often then you share their point of view and can defend their position.
Logged

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #28 on: April 06, 2015, 06:48:39 pm »

I have found out that another person shares my opinion that 50+ year history of distributed consensus research is quite useless when we talk about cryptos - http://www.reddit.com/r/ethereum/comments/31mj2i/my_blockchain_scalability_paper_entering_public/cq32vfr:

Quote
[–]vbuterin Founder 3 очка 2 hours ago
Yeah, I would agree with both those points and my next round of revision will probably focus on ease of reading. As for placing squarely in the 20+ year history of distributed systems research, I tend to be quite skeptical that traditional distributed systems research can be easily applied to blockchains. I'm sure there are insights, but the issue is that the hardest problems are not technical; they are economic, and that is something that previous computer scientists simply have not had to face. I've personally found that the field of law and economics (as described by Posner, Becker, Friedman, etc) actually has greater applicability to blockchain theory than anything else. But would love pointers to anything in either field that I may have missed.

Nice to see some progress done in the right direction.
« Last Edit: April 06, 2015, 06:52:43 pm by Come-from-Beyond »
Logged

gs02xzz

  • Hero Member
  • *****
  • Karma: +56/-12
  • Offline Offline
  • Posts: 1101
    • View Profile
Re: NXT stake-grinding attack?
« Reply #29 on: April 06, 2015, 08:23:43 pm »

Nice to see some progress done in the right direction.

In the paper - https://raw.githubusercontent.com/vbuterin/scalability_paper/master/scalability.pdf, the authors used Nxt algo as an example. It seems a confirmation of Nxt security (But I am not a expert)

Quote
Example 3.0.2. The cryptoeconomically secure entropy source used in NXT[16] is de ned recursively as follows:
 E(G) = 0
 E( + ) = sha256(E()+V ( )) where V ( ) is the block proposer of
.
Assumption 3.1. For any time internal I, there exists some xed probabil-ity po(I) such that a node randomly selected according to the weight functionused to measure a cryptoeconomic state machine's Byzantine fault tolerancecan be expected to be oine for at least the next I seconds starting from anyparticular point in time with at least probability po.Note. We can derive the above assumption from an altruism assumption bysimply stating in the protocol that nodes \should" randomly drop oinewith low probability; however, in practice it is simpler and cleaner to relyonly on natural faults.Note. Combining the two uninuenceability criteria into one (\it is impos-
sible to increase the probability of P from p to p  (1+k) without expendingat least b L k resources") is likely very dicult; it is hard to avoid having
ways to cheaply multiply the probability of low-probability predicates byonly acting when you are sure that your action will have an inuence on theresult.
......

Lemma 3.0.3. The NXT algorithm described above satis es the conditionsfor being a cryptoeconomically secure entropy source.Proof. To prove unpredictability, we note that the NXT blockchain pro-duces a block every minute, and so the update v   sha256(v; V ( )) takesplace once a minute. During each round of updating, there is a probabil-ity 1 ...........
« Last Edit: April 06, 2015, 08:26:16 pm by gs02xzz »
Logged
Nxt Mission is to commercialize the crypto technology and build new commerce and society.

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #30 on: April 06, 2015, 08:55:11 pm »

In the paper - https://raw.githubusercontent.com/vbuterin/scalability_paper/master/scalability.pdf, the authors used Nxt algo as an example. It seems a confirmation of Nxt security (But I am not a expert)

Quote
Example 3.0.2. The cryptoeconomically secure entropy source used in NXT[16] is de ned recursively as follows:
 E(G) = 0
 E( + ) = sha256(E()+V ( )) where V ( ) is the block proposer of
.
Assumption 3.1. For any time internal I, there exists some xed probabil-ity po(I) such that a node randomly selected according to the weight functionused to measure a cryptoeconomic state machine's Byzantine fault tolerancecan be expected to be oine for at least the next I seconds starting from anyparticular point in time with at least probability po.Note. We can derive the above assumption from an altruism assumption bysimply stating in the protocol that nodes \should" randomly drop oinewith low probability; however, in practice it is simpler and cleaner to relyonly on natural faults.Note. Combining the two uninuenceability criteria into one (\it is impos-
sible to increase the probability of P from p to p  (1+k) without expendingat least b L k resources") is likely very dicult; it is hard to avoid having
ways to cheaply multiply the probability of low-probability predicates byonly acting when you are sure that your action will have an inuence on theresult.
......

Lemma 3.0.3. The NXT algorithm described above satis es the conditionsfor being a cryptoeconomically secure entropy source.Proof. To prove unpredictability, we note that the NXT blockchain pro-duces a block every minute, and so the update v   sha256(v; V ( )) takesplace once a minute. During each round of updating, there is a probabil-ity 1 ...........

BCNext's idea not to provide the whitepaper to force an independent analysis has finally worked. Good, now this page can be turned.
Logged

Daedelus

  • Hero Member
  • *****
  • Karma: +230/-12
  • Offline Offline
  • Posts: 3280
    • View Profile
Re: NXT stake-grinding attack?
« Reply #31 on: April 06, 2015, 09:16:18 pm »

Yeay. Does that mean, after months of agony, you can give us the full version of Nxts whitepaper? BCNext would have wanted it..
Logged
NXT: NXT-4CS7-S4N5-PTH5-A8R2Q

Come-from-Beyond

  • Hero Member
  • *****
  • Karma: +794/-671
  • Offline Offline
  • Posts: 4013
    • View Profile
Re: NXT stake-grinding attack?
« Reply #32 on: April 06, 2015, 09:17:02 pm »

Yeay. Does that mean, after months of agony, you can give us the full version of Nxts whitepaper? BCNext would have wanted it..

I quitted Nxt, you are left on your own.
Logged

Daedelus

  • Hero Member
  • *****
  • Karma: +230/-12
  • Offline Offline
  • Posts: 3280
    • View Profile
Re: NXT stake-grinding attack?
« Reply #33 on: April 06, 2015, 09:30:50 pm »

Lol, I keep asking. It amuses when you post that for some reason  :D
Logged
NXT: NXT-4CS7-S4N5-PTH5-A8R2Q

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: NXT stake-grinding attack?
« Reply #34 on: April 06, 2015, 10:29:54 pm »

Lemma 3.0.3. The NXT algorithm described above satisfies the conditions
for being a cryptoeconomically secure entropy source.

Proof. To prove unpredictability, we note that the NXT blockchain produces
a block every minute, and so the update v ← sha256(v, V (β)) takes
place once a minute. During each round of updating, there is a probability
1 − po(60) that the primary signer will be online, and po(60) that the
signer will be offline and thus a secondary signer will need to produce the
block. Hence, after 1
−log(po(60)) blocks, there is a probability p ≈
1
2
that the
resulting value will be the “default value” obtained from updating v with
the primary signers’ public keys at each block, and a p ≈
1
2
probability that
the resulting value will be different. We model 512 iterations of this process
as a tree, with all leaves being probability distributions over sequences
of 512 public keys of signers, where all probability distributions are disjoint
(ie. no sequence appears with probability greater than zero in multiple
leaves). By random-oracle assumption of sha256, we thus know that we have
a set of 2512 independently randomly sampled probability distributions from
{0, 1}
256, and so each value will be selected an expected {0, 1}
256 times, with
standard deviation 2128. Hence, the probability distribution is statistically
indistinguishable from a random distribution.
To show that the first uninfluenceability criterion holds true, note that
the only way to manipulate the result is for the block proposer to disappear,
leading to another proposer taking over. However, this action is costly for
the proposer as the proposer loses a block reward. The optimal strategy
is to disappear with probability 0 < q <= 1 only when the predicate will
be unsatisfied with the proposer participating but will be satisfied with
the next proposer partipating; if a predicate has probability p this entails
disappearing p ∗ (1 − p) ∗ q of the time, meaning that the predicate will be
satisfied p + p ∗ (1 − p) ∗ q of the time instead of p of the time, a probability
increment of p∗(1−p)∗q will have a cost of p∗(1−p)∗q∗R if R is the signing
reward (whose real value is proportional to the quantity of transaction fees, a
reasonable metric of economic activity). Hence, the desired condition holds
true with b = 1.
To show that the second uninfluenceability criterion holds true, note that
when one is not the signer, one has no influence on the entropy, and when
one is the signer one has the ability to not sign and instead defer to the
next signer. Hence, an attacker controlling 1
k
of all signing slots will be able
to defer to the second signer 1
k
of the time, to the third signer 1
k
2 of the
time (by being in the first two slots simultaneously), etc, so in total such an
attacker will on average be able to choose between 1 + 1
k−1
values and thus
multiply the probability of a desired predicate by a factor of 1 + 1
k−1
. If the
attacker controls 1
3
of all signing slots, the result will thus be increasing the
probablity by a factor of 3
2
.

***********
it seems vitalik made a proof about NXT algo
Logged
There are over 1000 people in SuperNET slack! http://slackinvite.supernet.org/ automatically sends you an invite

I am just a simple C programmer
Pages: 1 2 [All]
 

elective-stereophonic
elective-stereophonic
assembly
assembly