elective-stereophonic
elective-stereophonic
Dominant forging exploit possible? singapore
Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Nxt Client: Nxt 1.11.15

Author Topic: Dominant forging exploit possible?  (Read 1902 times)

monsterer

  • Full Member
  • ***
  • Karma: +18/-2
  • Offline Offline
  • Posts: 175
    • View Profile
Dominant forging exploit possible?
« on: September 10, 2015, 01:47:57 pm »

Why isn't this possible when forging:

*) wait until you produce a block
*) pre calculate N permutations of the block you are about to generate in order to produce one with a hash which allows you to satisfy the condition for producing the next block

This should lead to a dominant forging strategy in which you continue to win the contest to forge a block...or at the least drastically increase your chances?
Logged
https://metaexchange.info/
NXT<->BTC instant exchange - low spread, no registration

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Dominant forging exploit possible?
« Reply #1 on: September 10, 2015, 01:51:51 pm »

Why isn't this possible when forging:

*) wait until you produce a block
*) pre calculate N permutations of the block you are about to generate in order to produce one with a hash which allows you to satisfy the condition for producing the next block

This should lead to a dominant forging strategy in which you continue to win the contest to forge a block...or at the least drastically increase your chances?
because the forging hash chain isnt dependent on the contents of a block. If it was, what you describe would work.

Sorry, no N@S here.

the pubkey of the forging acct is used in the hash chain, so you can only use accounts that you have and only accounts with non-zero balances are eligible. And you cant just transfer funds into an account that would forge, as there is 1440 blocks after transfer before the balance counts toward forging.

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

monsterer

  • Full Member
  • ***
  • Karma: +18/-2
  • Offline Offline
  • Posts: 175
    • View Profile
Re: Dominant forging exploit possible?
« Reply #2 on: September 10, 2015, 02:05:54 pm »

because the forging hash chain isnt dependent on the contents of a block. If it was, what you describe would work.

I thought the algorithm used the hash of the last block as part of its calculation?
Logged
https://metaexchange.info/
NXT<->BTC instant exchange - low spread, no registration

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Dominant forging exploit possible?
« Reply #3 on: September 10, 2015, 02:18:39 pm »

because the forging hash chain isnt dependent on the contents of a block. If it was, what you describe would work.

I thought the algorithm used the hash of the last block as part of its calculation?
my understanding is that there are two hash chains, one for the txid and another for the forging and they are independent
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

jones

  • Hero Member
  • *****
  • Karma: +310/-8
  • Offline Offline
  • Posts: 1043
  • write code not war
    • View Profile
    • jNxt
Re: Dominant forging exploit possible?
« Reply #4 on: September 10, 2015, 04:32:12 pm »

because the forging hash chain isnt dependent on the contents of a block. If it was, what you describe would work.

I thought the algorithm used the hash of the last block as part of its calculation?
my understanding is that there are two hash chains, one for the txid and another for the forging and they are independent

This is correct, payload signature is of the block and generation signature is of the forgers public key hashed wit the last blocks Gen signature
Logged
-- Jones NXT-RJU8-JSNR-H9J4-2KWKY

monsterer

  • Full Member
  • ***
  • Karma: +18/-2
  • Offline Offline
  • Posts: 175
    • View Profile
Re: Dominant forging exploit possible?
« Reply #5 on: September 10, 2015, 04:58:55 pm »

This is correct, payload signature is of the block and generation signature is of the forgers public key hashed wit the last blocks Gen signature

Ok, so the last block is involved? Given you can control the last block completely (should you get a chance to forge), can't you just generate a favourable block signature so that you get elected to produce the next block, and so on?
Logged
https://metaexchange.info/
NXT<->BTC instant exchange - low spread, no registration

bcdev

  • Hero Member
  • *****
  • Karma: +162/-22
  • Offline Offline
  • Posts: 666
    • View Profile
Re: Dominant forging exploit possible?
« Reply #6 on: September 10, 2015, 05:29:01 pm »

You cannot. The only way is to skip your right to generate a block, allowing someone else to generate a block.
In other words who generates a next block [and next next block [and ...]] is deterministic. Contents of a block don't matter. Only the account  ID knowsmatters.

You could predict who will generate a block an hour from now assuming you know which accounts are forging, and which are not. [and no forger skips their right to generate a block within that hour]
That is called Trasparent Forging.

The whitepaper isn't clear on that, you'll need to dive into the source code to find that out.

Btw. One year ago I thought of exactly the same attack and that was the response:
Account's hit mining attack

Description:
1) Attacker gets to generate a block.
2) Attacker makes a block with one "Message" transaction. I'll call it nonce tx.
   Attacker mines a block using the nonce tx and creates a generation signature.
   Generation signature is specially crafted to make an attacker's account's hit very low.
3) Because attackers account's hit is very low, he gets to generate a new block.

Steps 2-3 can be repeated, effectively allowing an Attacker to generate as long chain as he desires.

Is this attack valid?
If not, what prevents account's hit to be mined?

There are following "problems" with your attack vector:

1) Attacker can't "craft" generation signature. It is deterministic value not depends on his will.

Generation signature is calculated as sha256 of previous block signature and generator(attacker) public key:

generationSignature :: Block -> Account -> ByteString
generationSignature prevBlock acct =  sha256 ( append (generationSignature prevBlock) (publicKey acct) )

2) Why message transaction? Who will be the sender? If attacker itself, he not earns anything from it, in other case transaction will be not valid, so blocks generated will be declined by other nodes.
 
P.S. I'm going to write some articles about the forging algo.
P.P.S. Thank You for attempts to crack the forging algo  :)

Best regards, kushti
« Last Edit: September 10, 2015, 05:56:59 pm by bcdev »
Logged

monsterer

  • Full Member
  • ***
  • Karma: +18/-2
  • Offline Offline
  • Posts: 175
    • View Profile
Re: Dominant forging exploit possible?
« Reply #7 on: September 10, 2015, 05:37:04 pm »

You cannot. The only way is to skip your right to generate a block, allowing someone else to generate a block.
In other words who generates a next block [and next next block [and ...]] is deterministic. Contents of a block don't matter. Only the account knows.

If the contents of the block don't matter, then why is the signature of the block used in the calculations? I think the response you got when you suggested the same attack is wrong.

Ok, looking at the code I can see that the generation signature is a hash of the combination of your public key and the previous forgers public key, rather than the being a hash of the block contents.

Code: [Select]
static BigInteger getHit(byte[] publicKey, Block block) {
        if (allowsFakeForging(publicKey)) {
            return BigInteger.ZERO;
        }
        if (block.getHeight() < Constants.TRANSPARENT_FORGING_BLOCK) {
            throw new IllegalArgumentException("Not supported below Transparent Forging Block");
        }
        MessageDigest digest = Crypto.sha256();
        digest.update(block.getGenerationSignature());
        byte[] generationSignatureHash = digest.digest(publicKey);
        return new BigInteger(1, new byte[] {generationSignatureHash[7], generationSignatureHash[6], generationSignatureHash[5], generationSignatureHash[4], generationSignatureHash[3], generationSignatureHash[2], generationSignatureHash[1], generationSignatureHash[0]});
    }
« Last Edit: September 10, 2015, 05:46:29 pm by monsterer »
Logged
https://metaexchange.info/
NXT<->BTC instant exchange - low spread, no registration

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Dominant forging exploit possible?
« Reply #8 on: September 10, 2015, 05:54:43 pm »

You cannot. The only way is to skip your right to generate a block, allowing someone else to generate a block.
In other words who generates a next block [and next next block [and ...]] is deterministic. Contents of a block don't matter. Only the account knows.

If the contents of the block don't matter, then why is the signature of the block used in the calculations? I think the response you got when you suggested the same attack is wrong.

Ok, looking at the code I can see that the generation signature is a hash of the combination of your public key and the previous forgers public key, rather than the being a hash of the block contents.

Code: [Select]
static BigInteger getHit(byte[] publicKey, Block block) {
        if (allowsFakeForging(publicKey)) {
            return BigInteger.ZERO;
        }
        if (block.getHeight() < Constants.TRANSPARENT_FORGING_BLOCK) {
            throw new IllegalArgumentException("Not supported below Transparent Forging Block");
        }
        MessageDigest digest = Crypto.sha256();
        digest.update(block.getGenerationSignature());
        byte[] generationSignatureHash = digest.digest(publicKey);
        return new BigInteger(1, new byte[] {generationSignatureHash[7], generationSignatureHash[6], generationSignatureHash[5], generationSignatureHash[4], generationSignatureHash[3], generationSignatureHash[2], generationSignatureHash[1], generationSignatureHash[0]});
    }
So are you still convinced that N@S attack is possible?

You might call what NXT is doing "bandaids", but to me it seems to be a design that avoids the N@S attack and other problems with earlier PoS implementations.

Not saying it is perfect, but if N@S is not possible (or cost prohibitive rendering it a nonviable attack), then even though it isnt PoW, it creates a blockchain that can be validated against fake blockchains as there is also a concept of chain weight.

It is true though that in the early days NXT was vulnerable in ways bitcoin wasnt, but like a seed that grows into a tree, the fact that it was once vulnerable is not relevant anymore
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

monsterer

  • Full Member
  • ***
  • Karma: +18/-2
  • Offline Offline
  • Posts: 175
    • View Profile
Re: Dominant forging exploit possible?
« Reply #9 on: September 10, 2015, 09:25:03 pm »

So are you still convinced that N@S attack is possible?

This particular exploit isn't possible as far as I know.
Logged
https://metaexchange.info/
NXT<->BTC instant exchange - low spread, no registration

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Dominant forging exploit possible?
« Reply #10 on: September 10, 2015, 10:42:24 pm »

So are you still convinced that N@S attack is possible?

This particular exploit isn't possible as far as I know.
Interesting. So if N@S is not possible, then even though there isnt any large cost to create a block, it is not making a problem.

Of course, if even somebody obtains 50%+, then they can do any sort of horrible thing, but considering the widespread distribution, it seems quite improbable for any such stake to be possible
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

monsterer

  • Full Member
  • ***
  • Karma: +18/-2
  • Offline Offline
  • Posts: 175
    • View Profile
Re: Dominant forging exploit possible?
« Reply #11 on: September 10, 2015, 11:10:27 pm »

Interesting. So if N@S is not possible, then even though there isnt any large cost to create a block, it is not making a problem.

Of course, if even somebody obtains 50%+, then they can do any sort of horrible thing, but considering the widespread distribution, it seems quite improbable for any such stake to be possible

I mean, this particular exploit of using sybil attack on block generation isn't possible as per the OP. I haven't explored whether the other factors which affect the randomness of forger selection can be gamed.
Logged
https://metaexchange.info/
NXT<->BTC instant exchange - low spread, no registration

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Dominant forging exploit possible?
« Reply #12 on: September 10, 2015, 11:33:53 pm »

Interesting. So if N@S is not possible, then even though there isnt any large cost to create a block, it is not making a problem.

Of course, if even somebody obtains 50%+, then they can do any sort of horrible thing, but considering the widespread distribution, it seems quite improbable for any such stake to be possible

I mean, this particular exploit of using sybil attack on block generation isn't possible as per the OP. I haven't explored whether the other factors which affect the randomness of forger selection can be gamed.
Each block creates what is essentially a sorted list of addresses that can generate the next block. As time passes, more and more nodes are able to submit the winning block, but in most all cases if a node is online and it is at the top of the list, it will get the block. The search space is pretty large and the SHA256 does a good job of randomizing the next winner.

So in order to game this, you would need to somehow get a set of addresses that are eligible to forge the next block (1440 block wait for funds to mature) and predict the SHA256 results.  since the chances to forge a block is very close to linear, with the same amount of funds you will have roughly the same chance by having 1 big account or thousands of small ones.

It might be possible to predict the next 10 blocks ahead of time and to precompute the address network with the best chances, but there is no time to fund them. There is too much uncertainity to predict 1440 blocks ahead

The model used is where each NXT represents a fixed hashrate so the more NXT you have the more likely you will generate the next block, but being a statistical process, there are no guarantees

Since the process is so simple, the chances for an undiscovered edge case after all this time is pretty low, but maybe fresh eyes will discover some flaw

James
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

bcdev

  • Hero Member
  • *****
  • Karma: +162/-22
  • Offline Offline
  • Posts: 666
    • View Profile
Re: Dominant forging exploit possible?
« Reply #13 on: September 11, 2015, 12:20:00 am »

I'm able to imagine an exploit that would provide slightly bigger advantage to a big forger [>= 10% of the network].

10% forger splits his stake into two 5%.
While:
if both stakes are the winners [which will happen in *0.25% blocks], choose one with greater probability of getting both stake win in the future.
if only one stake is the winner [which will happen in 10% blocks], calculate if "maybe" there is a probability to get a higher reward in the future by skipping a block.

I think it might give a slight edge for the forger [nothing protocol-breaking]. I've heard some rumors that core devs plan to punish forgers that skip blocks, so that method won't be viable.

* guess - i suck at statistics
« Last Edit: September 11, 2015, 12:22:48 am by bcdev »
Logged

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Dominant forging exploit possible?
« Reply #14 on: September 11, 2015, 06:19:40 am »

I'm able to imagine an exploit that would provide slightly bigger advantage to a big forger [>= 10% of the network].

10% forger splits his stake into two 5%.
While:
if both stakes are the winners [which will happen in *0.25% blocks], choose one with greater probability of getting both stake win in the future.
if only one stake is the winner [which will happen in 10% blocks], calculate if "maybe" there is a probability to get a higher reward in the future by skipping a block.

I think it might give a slight edge for the forger [nothing protocol-breaking]. I've heard some rumors that core devs plan to punish forgers that skip blocks, so that method won't be viable.

* guess - i suck at statistics
So a few times per day, you will be able have both the #1 and #2 position. But at that point you need to project forward blocks and hopefully find one of the accounts in the <10 blocks that are predictable.

So about half the time you will predict a better outcome path, but the error rate on 10 blocks ahead is quite large, so I think about 10% gain is likely, or about 0.25 extra blocks per day. This is not bad, but the odds of a larger account are a bit more than smaller ones, so there will be a bit of loss from that.

I think though, your method will net about 1NXT extra per week for the 10 million NXT account. And at that level, we need to adjust for the lost revenues during the 1440 blocks you cant forge, lets say 50 NXT would be lost. So, after about a year you will recoup the lost forging and then its pure profits!

James
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

bcdev

  • Hero Member
  • *****
  • Karma: +162/-22
  • Offline Offline
  • Posts: 666
    • View Profile
Re: Dominant forging exploit possible?
« Reply #15 on: September 11, 2015, 06:34:59 am »

That's why I said might and slight. ;)
I'm sure that 1NXT per week wouldn't cover extra electricity for this algorithm.

Quote
odds of a larger account are a bit more than smaller ones, so there will be a bit of loss from that.
So you're saying that 2*1milNXT will generate less blocks that 2milNXT? I thought they should be statistically exactly the same.
Logged

jl777

  • Hero Member
  • *****
  • Karma: +718/-123
  • Offline Offline
  • Posts: 6170
    • View Profile
Re: Dominant forging exploit possible?
« Reply #16 on: September 11, 2015, 06:38:35 am »

That's why I said might and slight. ;)
I'm sure that 1NXT per week wouldn't cover extra electricity for this algorithm.

Quote
odds of a larger account are a bit more than smaller ones, so there will be a bit of loss from that.
So you're saying that 2*1milNXT will generate less blocks that 2milNXT? I thought they should be statistically exactly the same.
Not sure of the exact bias, but the 2mil acct will do a bit better than 2 1 mil accts. Not anything drastic, but just enough to make creating a zillion accounts silly

electric costs for the algo will be free, nothing measurable
ah, but the development costs... that is a different story.
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
 

elective-stereophonic
elective-stereophonic
assembly
assembly