Pages:
Author

Topic: Nxt source code flaw reports - page 45. (Read 113369 times)

newbie
Activity: 56
Merit: 0
January 05, 2014, 10:09:14 AM
I still don't see the problem. Once a transaction is included into a block its timestamp doesn't matter. Block timestamp overwrites transaction timestamp. U can send transactions even with negative timestamps, it doesn't matter.

The problem is that you can take away transactions (and fees) from the generator of the next block by putting off sending out yours by a little. Sending your block a bit later is no problem, since it will a) take more time for someone else to generate a block b) you'll have a better cumulative difficulty than the other person, even if the other person was there earlier.
full member
Activity: 168
Merit: 100
IDEX - LIVE Real-time DEX
January 05, 2014, 09:59:19 AM
smaragda, ricot, vamdor, ImmortAlex, rlh: Please PM your NXT tip account. Thanks for pouring through the code.

FrictionlessCoin send yours too cuz you need a NXT hug.
legendary
Activity: 2142
Merit: 1010
Newbie
January 05, 2014, 09:58:42 AM
Hm? Was that sarcastic? Or do you ask me to game the system? ^^

I don't see problem here. Let me to re-read ur post...

Edit: I still don't see the problem. Once a transaction is included into a block its timestamp doesn't matter. Block timestamp overwrites transaction timestamp. U can send transactions even with negative timestamps, it doesn't matter.
newbie
Activity: 56
Merit: 0
January 05, 2014, 09:54:15 AM
How to avoid that:
change (transaction.timestamp > curTime + 15) to (transaction.timestamp > blockTimestamp)
And also make sure that the generation logic for blocks doesn't have the same flaw.

Extra cash is good, imho.

Hm? Was that sarcastic? Or do you ask me to game the system? ^^
legendary
Activity: 2142
Merit: 1010
Newbie
January 05, 2014, 09:51:39 AM
How to avoid that:
change (transaction.timestamp > curTime + 15) to (transaction.timestamp > blockTimestamp)
And also make sure that the generation logic for blocks doesn't have the same flaw.

Extra cash is good, imho.
newbie
Activity: 56
Merit: 0
January 05, 2014, 09:46:34 AM
And another bug...
The topic this time: Transaction timestamps Smiley

Let's have Bob do some malicious things again  Cool
It's Bob's turn to forge a block. He decides to hold back that block a little, not too much, so that there aren't 2 blocks generated by other people in the meantime and his block still has the highest cumulated difficulty.
Let's say this gives him an extra minute of time. (In reality, at the moment this would be even higher)
He now goes on to include incoming transactions in the block, even those with a creation timestamp after his block's timestamp.
After he's done, he sends that block to the peers.
The peers should see the better cumulated difficulty and then hopefully check, whether it only contains transactions up to it's creation time.

So let's take a look in the code, if they actually do that...
We are somewhere in pushBlock and have just extracted the transactions contained in the block. Now for every transaction, we check the following:
Code:
if (transaction.timestamp > curTime + 15
    || transaction.deadline < 1
    || (transaction.timestamp + transaction.deadline * 60 < blockTimestamp && getLastBlock().height > 303)
    || transaction.feeNxt <= 0
    || !transaction.validateAttachment()
    || Nxt.transactions.get(block.transactions[i]) != null
    || (transaction.referencedTransaction != 0
        && Nxt.transactions.get(transaction.referencedTransaction) == null && blockTransactions
        .get(transaction.referencedTransaction) == null)
    || (Nxt.unconfirmedTransactions.get(block.transactions[i]) == null && !transaction.verify())) {
  break;
}
The transaction timestamp is checked in 2 occasions:
First:
(transaction.timestamp > curTime + 15) causes the block to be invalid. So what's curTime? curTime = getEpochTime(System.currentTimeMillis()), so current system time, basically.
That one is fine, the transaction was issued in the very recent past.
Second:
(transaction.timestamp + transaction.deadline * 60 < blockTimestamp)
Our block also doesn't contains transactions whose deadline has already passed, so we're fine, too in that regard.

... There are no other checks for transaction timestamps ...
So Bob's block goes thru with some extra transactions in it for some extra cash... *yay*

How to avoid that:
change (transaction.timestamp > curTime + 15) to (transaction.timestamp > blockTimestamp)
And also make sure that the generation logic for blocks doesn't have the same flaw.

[edit]
The generation logic has the same flaw, the timestamp is not checked at all. And I also don't see a check whether the unconfirmed transaction is still within deadline in generateBlock() or am I blind?
legendary
Activity: 2142
Merit: 1010
Newbie
newbie
Activity: 50
Merit: 0
January 05, 2014, 09:34:19 AM
The chance that you get the next block when you can chose which of the 2 possible blocks you want to forge, just doubles. This exactly cancels out, just calculate it.
Ok, I misunderstood what you wrote the first time,  I am a bit tired now, I think I will continue thinking when I am more rested Smiley

Quote
The thing with the more transactions is actually a point, but that should become mute with transparent forging, i.e. weighting you down if you don't chose to forge with the account that's eligible first.

I've seen this "transparent forging" mentioned in this thread multiple times. Is there a description somewhere on what it is?
newbie
Activity: 56
Merit: 0
January 05, 2014, 09:20:13 AM
Hmm... so it seems to be right that this Proof-of-Stake scheme penalises the small accounts. (not just those that are handled by a single entity, but everyone else the same way)
No, it only penalizes entities that have multiple accounts.

Quote
In the case of Bob's 2 accounts, the chance that we can choose with which account to forge is 0.00000025. So in that case, your forging weight doubles (i.e. 2 accounts)... However, that doubling just brings us back to where we would have been if we had only one account.

I don't think so. You have two accounts, but can only use one of them, so it doesn't double your reward. There is a chance that the second one helps you to get one more though. (though that's much smaller) Also there is what I said about the time spent gathering fees: if you choose the later one, you get more fees as you can wait for more transactions.

The chance that you get the next block when you can chose which of the 2 possible blocks you want to forge, just doubles. This exactly cancels out, just calculate it.
The thing with the more transactions is actually a point, but that should become mute with transparent forging, i.e. weighting you down if you don't chose to forge with the account that's eligible first.
legendary
Activity: 2142
Merit: 1010
Newbie
January 05, 2014, 09:17:49 AM
So there are a bunch of factors in play here. But it seems sure that this PoS doesn't make the distribution "truly fair". Maybe quite close though.

Modeling shows that it's not truly fair. Though the difference is ~ dispersion.
newbie
Activity: 50
Merit: 0
January 05, 2014, 09:09:57 AM
If you know that both accounts are elligible before anybody else (no matter of at the same time or at different times), you still just get one block's worth of transaction fees. The only other thing you can do is influence your chances with the next block by chosing which block to use to forge at that point. But the former disadvantage exactly cancels out the latter advantage.

Hmm... so it seems to be right that this Proof-of-Stake scheme penalises the small accounts. (not just those that are handled by a single entity, but everyone else the same way)

But I don't think that it exactly balances out the block-choosing algorithm.

Quote
In the case of Bob's 2 accounts, the chance that we can choose with which account to forge is 0.00000025. So in that case, your forging weight doubles (i.e. 2 accounts)... However, that doubling just brings us back to where we would have been if we had only one account.

I don't think so. You have two accounts, but can only use one of them, so it doesn't double your reward. There is a chance that the second one helps you to get one more though. (though that's much smaller) Also there is what I said about the time spent gathering fees: if you choose the later one, you get more fees as you can wait for more transactions.

So there are a bunch of factors in play here. But it seems sure that this PoS doesn't make the distribution "truly fair". Maybe quite close though.
newbie
Activity: 56
Merit: 0
January 05, 2014, 08:44:20 AM
Ah, damn those probabilities, you're right...

Here the elementary school version for people as dumb as me ^^
Chance that only your first account is eligible: 1/2000*1999/2000 = 0.00049975
Chance that only your secnod account is eligible: 1999/2000*1/2000 = 0.00049975
Chance that both accounts are eligible: 1/2000*1/2000 = 0.00000025

And since you get the same reward in these 3 situations: 0.00049975 + 0.00049975 + 0.00000025 = 0.00099975

But let's continue with the proper calculation:
In the case of Bob's 2 accounts, the chance that we can choose with which account to forge is 0.00000025.

Why? They don't have to be eligible at the same timestamp. As you "see the future", you know whether you have two eligible accounts at different timestamps too.

I am also still not convinced that the collisions reduce the chances of the fragmented accounts, but it's difficult to prove or disprove it without seeing some formal specs of the protocol.

It may also be possible to have different accounts that are never eligible at the same time. (I think eligibility is calculated as difference from a hash, so you just need to ensure that your accounts are not covering the same hash intervals)

If you know that both accounts are elligible before anybody else (no matter of at the same time or at different times), you still just get one block's worth of transaction fees. The only other thing you can do is influence your chances with the next block by chosing which block to use to forge at that point. But the former disadvantage exactly cancels out the latter advantage.
newbie
Activity: 50
Merit: 0
January 05, 2014, 08:41:15 AM
Ah, damn those probabilities, you're right...

Here the elementary school version for people as dumb as me ^^
Chance that only your first account is eligible: 1/2000*1999/2000 = 0.00049975
Chance that only your secnod account is eligible: 1999/2000*1/2000 = 0.00049975
Chance that both accounts are eligible: 1/2000*1/2000 = 0.00000025

And since you get the same reward in these 3 situations: 0.00049975 + 0.00049975 + 0.00000025 = 0.00099975

But let's continue with the proper calculation:
In the case of Bob's 2 accounts, the chance that we can choose with which account to forge is 0.00000025.

Why? They don't have to be eligible at the same timestamp. As you "see the future", you know whether you have two eligible accounts at different timestamps too.

I am also still not convinced that the collisions reduce the chances of the fragmented accounts, but it's difficult to prove or disprove it without seeing some formal specs of the protocol.

It may also be possible to have different accounts that are never eligible at the same time. (I think eligibility is calculated as difference from a hash, so you just need to ensure that your accounts are not covering the same hash intervals) (ok, this isn't true, all relevant hashed changes with every timestamp)
newbie
Activity: 56
Merit: 0
January 05, 2014, 08:23:40 AM
No, it doesn't. If you generate 100,000 accounts, it decreases your forging chance by 1.44%. Your influence on the forging probabilities of the next block should be higher than that... Who wants to calculate? Wink

Someone should do this, coz it's not obvious and may be incorrect.
Btw: Your calculation where Bob had less forging chance because he had 2 accounts is wrong. It has to be (1-1998/2000) = 1/1000. Your calculation was something with 2 draws but there is only one draw.

This is incorrect. Chances for each account don't depend each on other and may overlap.
Ah, damn those probabilities, you're right...

Here the elementary school version for people as dumb as me ^^
Chance that only your first account is eligible: 1/2000*1999/2000 = 0.00049975
Chance that only your secnod account is eligible: 1999/2000*1/2000 = 0.00049975
Chance that both accounts are eligible: 1/2000*1/2000 = 0.00000025

And since you get the same reward in these 3 situations: 0.00049975 + 0.00049975 + 0.00000025 = 0.00099975

But let's continue with the proper calculation:
In the case of Bob's 2 accounts, the chance that we can choose with which account to forge is 0.00000025. So in that case, your forging weight doubles (i.e. 2 accounts)... However, that doubling just brings us back to where we would have been if we had only one account.
I'm quite sure that this is generalizable to n accounts, and given the additional penalty of weighing down accounts that don't take part in forging and it's circumvention, I don't think it's possible to gain anything by this method.
legendary
Activity: 2142
Merit: 1010
Newbie
January 05, 2014, 08:08:33 AM
Wouldn't the above code always result in a break after the Genesis Block has been generated due to its block.payloadLength?

No.
legendary
Activity: 2142
Merit: 1010
Newbie
January 05, 2014, 07:56:23 AM
If I were to expose the flaw without having calculated the actual outputs (like the one in my question) will it be considered?

Yes.
legendary
Activity: 2142
Merit: 1010
Newbie
January 05, 2014, 07:55:42 AM
No, it doesn't. If you generate 100,000 accounts, it decreases your forging chance by 1.44%. Your influence on the forging probabilities of the next block should be higher than that... Who wants to calculate? Wink

Someone should do this, coz it's not obvious and may be incorrect.


Btw: Your calculation where Bob had less forging chance because he had 2 accounts is wrong. It has to be (1-1998/2000) = 1/1000. Your calculation was something with 2 draws but there is only one draw.

This is incorrect. Chances for each account don't depend each on other and may overlap.
newbie
Activity: 56
Merit: 0
January 05, 2014, 07:51:17 AM
One might think that the angle of attack is fought off by the new transparent forging algorithm because the account that chooses not to forge gets a lower forging weight. However, that's not the case if you move the balance off of that account and into a brand new one as soon as you forge the block. (To avoid fees) This brand new account will be inactive for 1440 blocks, but that just means that a maximum of 1440 of your accounts will be inactive. So that's only a very small percentage of your total number of accounts in that case and you can influence the chances at which you can generate the next block.

Right. Isn't this lower ur chance to forge blocks and ruins all the advantage of this strategy?

No, it doesn't. If you generate 100,000 accounts, it decreases your forging chance by 1.44%. Your influence on the forging probabilities of the next block should be higher than that... Who wants to calculate? Wink

Btw: Your calculation where Bob had less forging chance because he had 2 accounts is wrong. It has to be (1-1998/2000) = 1/1000. Your calculation was something with 2 draws but there is only one draw.
legendary
Activity: 2142
Merit: 1010
Newbie
January 05, 2014, 07:48:57 AM
Code:
logMessage("Scanning blockchain...");
HashMap tmpBlocks = blocks;
blocks = new HashMap<>();
lastBlock = GENESIS_BLOCK_ID;
long curBlockId = GENESIS_BLOCK_ID;
do {

Block curBlock = tmpBlocks.get(curBlockId);
long nextBlockId = curBlock.nextBlock;
curBlock.analyze();
curBlockId = nextBlockId;

} while (curBlockId != 0);
logMessage("...Done");


Why is lastBlock = GENESIS_BLOCK_ID; & curBlockId = GENESIS_BLOCK_ID; every time we scan the blockchain?

Also, can someone PLEASE provide the output of block.payloadLength for the Genesis Block...   thnx   Smiley

I don't answer questions that may reveal the flaw, sorry.
legendary
Activity: 2142
Merit: 1010
Newbie
January 05, 2014, 07:38:36 AM
One might think that the angle of attack is fought off by the new transparent forging algorithm because the account that chooses not to forge gets a lower forging weight. However, that's not the case if you move the balance off of that account and into a brand new one as soon as you forge the block. (To avoid fees) This brand new account will be inactive for 1440 blocks, but that just means that a maximum of 1440 of your accounts will be inactive. So that's only a very small percentage of your total number of accounts in that case and you can influence the chances at which you can generate the next block.

Right. Isn't this lower ur chance to forge blocks and ruins all the advantage of this strategy?
Pages:
Jump to: