Which transactions go into which blocks?

[Hepatizon]

I read the paper and did a brief forum search, so I apologize if this has already been asked/answered.

How do nodes determine when to include a particular transaction into a block?

There scenario I'm wondering about is this:
Alice tries to double-spend her coins.  As luck would have it, two different nodes simultaneously hash the next block, 1001, each containing one transaction of Alice's double spending attempt.  Call them 1001a and 1001b.  Then, a node working on 1001a hashes the next block, 1002, and every node sees that the chain containing 1000 -> 1001a -> 1002 is the longest (and most likely to be honest) and halts work on 1001b.  One of Alice's two forks in her double-spending attempts is ignored, and her attempt therefore fails.  The guy who was running the node that made 1001b sees that he almost made 50 bc and gets annoyed, but I guess that's acceptable.

But what happens to the other transactions that were in block 1001b but not in 1001a?  Do they get lost as well?  Suppose Bob also bought something at about the same time as Alice, and his transaction ended up being hashed in 1001b (but not 1001a) as well.  I assume that what happens next is that after chain 1002 gets accepted as legitimate, a node working on 1003 overhears Alice's and Bob's transactions, and then checks to see if the two are already in the chain.  It will find that Alice's transaction is fake, and ignore it, and that Bob's transaction isn't in the chain yet, and add that to the block-in-progress.  But then that means that every transaction has to keep echoing around for at least a few blocks to make sure that it ends up in the accepted chain - and every node that overhears a transaction has to check to make sure it isn't already in the list.

The other question - and I know this must have been answered somewhere and I just couldn't find it - what determines transaction uniqueness?  Say Alice buys a widget from Bob for 31.42 bc.  Alice then decides she wants another widget, and places a new order - with the same keys for both buyer and seller - for another 31.42 bc.  What makes these two transactions distinct?  If a node sees one transaction for 31.42 from A to B, then sees a transaction for 31.42 from A to B, what tips it off that these are two distinct transactions rather than the same transaction detected twice?

[Quantumplation]

When a transaction occurs, it's broadcast and distributed across the entire network, and everyone is supposed to add it to their block.  If the client who made the transaction sees that it isn't in the next solved block, it rebroadcasts the transaction to everyone, so it makes it into the next block.  From what I've heard, it's pretty relentless about this:  It'll keep trying, forever, until it makes it into the block chain.  Until it does, it shows up as 0/unconfirmed under status.

[Gavin Andresen]

The other question - and I know this must have been answered somewhere and I just couldn't find it - what determines transaction uniqueness?  Say Alice buys a widget from Bob for 31.42 bc.  Alice then decides she wants another widget, and places a new order - with the same keys for both buyer and seller - for another 31.42 bc.  What makes these two transactions distinct?  If a node sees one transaction for 31.42 from A to B, then sees a transaction for 31.42 from A to B, what tips it off that these are two distinct transactions rather than the same transaction detected twice?

A few things make those 31.42BTC transactions unique:

+ The timestamps in them will be different.
+ The input transactions will be different (you can think of those as being different 'coins' going in to make the payment).
+ And if the input transactions don't add up to exactly 31.42 (and they probably won't), they'll have different output transactions for returning any change to Alice.

By the way: all that stuff is hashed together to give each transaction a unique 256-bit transaction ID (which you never see, but is used internally so Bitcoin can quickly figure out if it has already seen this transaction before).

[Hepatizon]

The other question - and I know this must have been answered somewhere and I just couldn't find it - what determines transaction uniqueness?  Say Alice buys a widget from Bob for 31.42 bc.  Alice then decides she wants another widget, and places a new order - with the same keys for both buyer and seller - for another 31.42 bc.  What makes these two transactions distinct?  If a node sees one transaction for 31.42 from A to B, then sees a transaction for 31.42 from A to B, what tips it off that these are two distinct transactions rather than the same transaction detected twice?

A few things make those 31.42BTC transactions unique:

+ The timestamps in them will be different.
+ The input transactions will be different (you can think of those as being different 'coins' going in to make the payment).
+ And if the input transactions don't add up to exactly 31.42 (and they probably won't), they'll have different output transactions for returning any change to Alice.

By the way: all that stuff is hashed together to give each transaction a unique 256-bit transaction ID (which you never see, but is used internally so Bitcoin can quickly figure out if it has already seen this transaction before).

Ah, that works.

[mizerydearia]

+ The timestamps in them will be different.

This is not true.  I have determined that some blocks have been generated and use the same timestamp as a previously generated block

http://bitcointalk.org/index.php?topic=464.0

[Hepatizon]

Is the timestamp on the transaction, or just the block?

[mizerydearia]

+ The timestamps in them will be different.

This is not true.  I have determined that some blocks have been generated and use the same timestamp as a previously generated block

http://bitcointalk.org/index.php?topic=464.0

In fact, it is far from true.

http://bitcointalk.org/index.php?topic=441.msg4586#msg4586

Apparently timestamps for newly generated blocks can even have timestamps prior to the last block generated.

Snippets of data extracted from blk0001.dat

Code:

69273 1279655546 779734388429
69274 1279655947 779734388429
69275 1279655761 779734388429
69276 1279656675 779734388429

Code:

69246 1279640200 779734388429
69247 1279640882 779734388429
69248 1279640415 779734388429
69249 1279642645 779734388429

Code:

69239 1279638523 779734388429
69240 1279639005 779734388429
69241 1279638976 779734388429
69242 1279639437 779734388429

Code:

69037 1279540630 779734388429
69038 1279541270 779734388429
69039 1279541269 779734388429
69040 1279541367 779734388429

And here's a more interesting example.
Block 68,462 has timestamp before 68,461 but not before 68,460
Block 68,463 has timestamp before 68,462 AND 68,461
However, block 68,464 corrects things by having a timestamp after all previous blocks.

Code:

68458 1279287594 194933597107
68459 1279287774 194933597107
68460 1279287998 194933597107
68461 1279288077 194933597107
68462 1279288037 194933597107
68463 1279287679 194933597107
68464 1279288393 194933597107

Perhaps in theory it could be possible that a timestamp is assigned to a block that predates all other blocks, even the first one?

[bdonlan]

Perhaps in theory it could be possible that a timestamp is assigned to a block that predates all other blocks, even the first one?

It's probably possible; it would just mean that someone's computer clock is VERY far off base.

[mizerydearia]

Perhaps in theory it could be possible that a timestamp is assigned to a block that predates all other blocks, even the first one?

It's probably possible; it would just mean that someone's computer clock is VERY far off base.

Which would be intentional most likely.  Does this have any effect on anything other than reliability of statistics?  Is there a way to overcome this affect on timestamp data for statistics?

sorry to hijack the thread, back to original topic.