Topic: Choosing Transactions (Read 705 times)

I got it.  I just haven't responded yet.

@DannyHamilton,
I sent you a PM. Did you get it? I'm still rated as newbie so maybe my PMs are restricted. Not sure. Can you confirm if you got it?

Thanks

I've given serious consideration to offering a class.  Something where businesses that are considering blockchain technology or bitcoin itself could hire me to come in and explain the technical details to their staff.

However, I'm much better in a Q&A format than I am at organizing multiple concepts into a cohesive book.  I'll give it some consideration though.

In the meantime, if you have additional technical questions about bitcoin, you should post them here at bitcointalk.  There are other members here that do a great job of answering (such as Achow101 and HCP).  Feel free to send me a PM to point out the post with your question so I don't overlook it.

I have to agree with boogersguy - THank you DannyHamilton for your concise input.

While there are plenty of technical components to block chain, grasping the relevant factors does not require programming or cryptography. I'm new to block chains, but I've worked in IT most of my life and I find much of what is available is either extremely oversimplified (for the general public) or over the top with unnecessary technical details that still don't answer my questions about the basic components and operations.   I can dig into the details as I need them.

Danny, you hit the nail squarely on the head. You might consider writing a book

This makes sense.  I guess since they're hashing the data, they could just change one piece (like the timestamp), and then they can reset the nonce to zero and start incrementing again.
thank you for your input.

The nonce in the block header is a 4 byte integer.  Therefore there are only 4294967296 possible nonce values for any given header. After that, you need to modify the header in some other way to gain another 4294967296 nonce attempts.  Common ways to modify the header are to adjust the 4 byte timestamp or to change the transaction list so as to get a new merkle root.


There are no protocol rules on what software or function you must use to calculate the merkle root.  I haven't looked closely enough at any of the existing miner software to know how they manage it.  Each software developer is allowed to implement that in whatever way they see fit as long as the result is a properly generated merkle root.

You the man, Danny Ham!
Seriously though, your responses have been really to the point and helpful for noobs like me.

BTW, how can you run out of nonce values? Can't you just continue incrementing the number, or are you talking about the fact that a integer (or whatever the data type is) has a numeric limit?

You also said
I'm curious if they mix up the routine to build this tree, as I would have just assumed it's a built-in function call in the software: like "BuildMerkleTree(transactions)" (where transactions is the list of selected transactions). I guess I'm curious as to how this tree is built. Wondering if there are any performance advantages (ie speed) to building it in a certain way versus using a canned function. 

A partial preimage attack on (double) SHA-256, done by brute force.


It is not a matter of solving the nonce value.  The nonce is meaningless, in and of itself; that is why it’s called a nonce.  Or perhaps it may be said, the nonce is meaningfully meaningless.  The only means of bruteforcing a hash (partial) preimage is to repeatedly change the input until you get the desired output.  The nonce is the part which gets changed; it is really a sort of a throwaway value, only there to provide arbitrarily changeable input bits.

SHA-256 is assumed (or pretended, depending on whom you ask) to have the properties of a random oracle.  Simply for the sake of understanding, pretend that for each increment of the nonce, you are generating a random number.  If target difficulty requires an unbroken string of x zeroes in the highest digit positions, then imagine how many times you’d need to generate a 256-bit random number before you have the luck to draw one which starts with x zeroes.  Alternatively, think of it as a 256-bit string of coin flips with H=0 T=1.  How long will it take you by random chance to get a string starting with x heads in a row?

(Question for anybody:  Would the probability equal that of simply flipping x heads in a row, or would you need to repeatedly flip whole 256-bit strings of flips until you get one which starts with x heads in a row?  I seem to have temporarily confused myself here.  Checked in in alpha state.  May be patched.)

Another interesting way to look at it:  If SHA-256 has good avalanche (as we suppose), then for a single-bit flip in its input, each bit of output has a 50% probability of flipping.  Implications for bruteforcing a partial preimage are left as an exercise to the reader.

(I used several basic/intermediate level cryptography terms of art here.  I tried to pinpoint those in boldface so you can look them up if you’re unfamiliar with them.)

Yes.

The miner keeps trying new nonce values until they find one such that hashing the 80 byte block header results in a value that is less than the current difficulty target value.  The fact that the block header (which includes the nonce) hashes to a value that is lower than the target is proof that they have completed the necessary work.

Here's a dummy question ...
What is the proof of work?

When a miner solves the nonce value, is that the proof of work or is there some other process that has to be done in addition to solving the nonce to complete the block?

@DannyHamilton

Thank you

Apropos:  Bitcoin mining is NP-hard (or rather, transaction selection is).  The upshot is that it doesn’t get solved optimally, at least from a theoretical perspective.  In practice, “good enough” is good enough:  Fill your knapsack mostly full of mostly the best stuff, and start hashing.  The race is on, and time is critical!

There are all sorts of prickly points around the subtle art of selecting transactions for inclusion in a block.  When making changes to Bitcoin, careful engineering work can be required to at least not make it harder.


Unless they want to attack Bitcoin by deliberately mining empty blocks.  (Here, “empty” means with only the coinbase transaction.)  There is suspicion that this has happened.  Empty blocks are also sometimes produced for other reasons as DannyHamilton explained.

No.

With a merkle tree each transaction is individually hashed...

Then pairs of hashes are hashed to get to the next level of the tree...

Then pairs of those hashes are hashed to get to the next level of the tree...

Then pairs of those hashes are hashed to get to the next level of the tree...

This process continues until there in only 1 pair of hashes.  That pair is hashed together to get the root.


Yes, but hashing is VERY fast.  It is true that additional transactions will increase the amount of hashing that must be done, but compared to the proof-of-work it is rather a very small amount of time.


Correct.


That depends on how many transactions you have waiting around in your mempool.

Additionally, you need to spend time verifying the block that you just received from the network and removing all those transactions from your mempool so that you don't accidentally include a confirmed (or invalid) transaction in your block.  As such, it can be efficient to build an immediate block with no transactions, and get your ASIC started on that.  Then while your ASIC is busy you can do all the verifying and transaction manipulation to prepare another block header for hashing.


If you are just talking about choosing from an already validated transaction set and building the block header, then yes the time to build the block header is generally many orders of magnitude faster than the proof-of-work (however, it is possible to get lucky and complete your proof-of-work on your very first hash. You don't know whether or not that will be the case while you are building the header).


We do see single transaction blocks.  As I said, some miners/pools will get started on a single transaction block first, then while the ASIC is busy they will build a block header with transactions. If that first block gets lucky and is solved before the bigger block, then it gets broadcast.

Hmmm ... that's not clear to me.
If you feed 1 byte, 50 bytes, or 5,000 bytes of data to a hash function, does it take more clock cycles to calculate the hash?
The merkel tree is a single hash value of all transactions in a block - Correct?
Does the time to calculate the merkel tree increase with larger argument data (more transactions)?

It might take time to gather more transactions together to feed as arguments into the hash function, but that process has to run regardless, so how much difference can it make to gather 5 transactions versus 20 transaction? I'm not sure but I think we're talking some where between a number of clock cycles or milliseconds where determining the nonce (hence solving the block) is a question of minutes.

If the number of transaction was a significant delay (causing miners to lose the race for the block) I think we would predominately see single transaction blocks. if it's not significant, I would expect to see the maximum that will fit.

Am I missing something here?

Correct.

The miner (or mining pool) builds a block of transactions from the unconfirmed transactions that they are aware of.

Then they build a merkle tree from the chosen transactions and calculate the merkle root.

They use the merkle root (along with the hash of the previous block, the timestamp, the current difficulty, and a block version number) to build an 80 byte block header for that set of transactions.

Then they begin the proof-of-work on that block header.

If they hear about a valid completed block before they complete their proof-of-work, then they start over.
If they try all possible nonce values without completing their proof-of-work, then they start over.
If they complete their proof-of-work, then they broadcast their block and start over.

There are two types of miners who mine transactions based on their preference. Individual miners and pool miners. Pool miners are those who from a group of miners to build more mining power and mine transactions together.
They choose as many transactions as possible because at the end of the day they want to earn more and for that they have to mine more.
This depends on their preference as some miners prefer transactions with fees while other prefers more number of transactions. Both need the same amount of energy and can be equally profitable.
More number of transactions take more time. Quite logical.
Yes the miner can configure/choose which transaction he wants to mine and can set the software according to the given criteria. You must be knowledgeable with computers in order to perform these tasks.

When you say "(the transaction that pays the block reward)", does the miner create this transaction himself?

So, based on your answers, it sounds like miners around the globe are independently adding transactions to blocks first, THEN, they start working on the proof of work,  correct? This is probably the only sane case because doesn't the POW depend on the transactions in the block itself? 

choose minimum amount to transect to control it

The solo-miner (or mining pool) typically runs software that makes the decisions.  They can often configure that software in any way that they like.

In the case of Bitcoin, they are required to include AT LEAST one transaction (the transaction that pays the block reward).  Beyond that they can include as many or few valid transactions as they like as long as they don't exceed any size limits on the block.

Since the miner gets to keep the transaction fees of all the transactions that he includes in his block, there is a financial incentive for him to include as many transactions as possible and to choose the transactions that pay the highest fee per byte.


The solo-miner (or mining pool) typically runs software that makes the decisions.  They can often configure that software in any way that they like.

Since the miner gets to keep the transaction fees of all the transactions that he includes in his block, there is a financial incentive for him to include as many transactions as possible and to choose the transactions that pay the highest fee per byte.


It takes some time to choose transactions and generate the merkle tree, and the more transactions the longer it takes.  In general this amount of time is VERY small in comparison to the time it takes to complete the proof-of-work, but a miner may choose to include less transactions if he wants to get started on the proof-of-work sooner.

It is also possible that a miner may not have access to a complete list of pending transactions, and therefore will simply build a block with the transactions that they have available to them at the time.


If you are solo-mining, yes.


If you are mining in a pool, yes.

I'm new to blockchain and trying to figure out what determines/controls the transactions that are included in a new block. 

If I understand correctly, miners pull from pending new transactions in the mem pool. But;

1. What determines if they choose 1 or 10 or 50?

2. What determines which transactions are chosen? Most recent? Highest fees?

3. Is there some reason for not choosing as many as possible to get more fees?

4. Is this something you configure according to some criteria in your mining software or some thing determined by your pool?

Thx