Quote from: Serith on February 24, 2013, 01:46:41 AM

Quote from: MoonShadow on February 23, 2013, 03:14:40 PM

Quote from: Serith on February 23, 2013, 02:55:21 PM

Quote from: MoonShadow on February 23, 2013, 07:08:15 AM

The verification delays grow exponentially with the number of transactions simply because each node must perform it's own series of checks before forwarding said block.

Wrong, because the number of nodes getting involved in verification of specific block grows exponentially as well, so the relationship between number of transactions and propagation time is linear.

As an analogy think about how a bacteria multiplies, at every step a size of the colony increased by factor of 2 until it's reached lets say 1024, if suddenly it requires twice more time to multiple then it takes only twice longer to reach the size of 1024 because the number of multiplication steps is still the same.

If block verification were a distributable process, you'd be correct, but it isn't. At least it's not now, and I don't know how it could be done. One thing that could be altered to speed up propagation is for some nodes to have trusted peers, wherein if they receive a block from that peer, they re-broadcast that block first then do their checks. But if this was the default behavior, the network could be DDOS'ed with false blocks.

Lets say you have 1025 full nodes on the network, to keep the example simple we will have those nodes connected in a form of binary tree where a block starts propagating from it's root. Lets say it takes 1 minutes for a node to verify a block and relay it to its children, then it will take 10 minutes for 1024 nodes ( I exclude the root from verification time) to verify the block, in another words it takes 10 minutes for a block to get propagated and verified by the network.

Now lets have a bigger block that takes twice more time to verify, then it will take 20 minutes for 1024 nodes to verify the block, in another words it will take twice more minutes for a block to get propagated and verified by the network. Therefore the relationship between verification time of block and propagation delay it's causing is linear, e.g. if it takes thrice more time to verify a block then, in the simplified example, it will take thrice more time to propagate it through the network.

Your example does not relate to the network. It's not a binary tree, and doubling the size of the block does not simply double the verification times. While it might actually be close enough to ignore in practice, the increase in the actual number of transactions in the myrkle tree makes the tree itself more complex, with more binary branches thus more layers to the myrkle tree. This would imply a greater complexity to the verification process on it's own. For example, a simple block with only four transactions will have the TxID hashes for those four transactions, plus two hashes for their paired myrkel tree branches, and a final hash that pairs those two together, and that is the myrkle root, which is then included into the block header. Moving beyond four transactions, however, creates another layer in the binary tree; and then another after 8 transactions, and another after 16 transactions. Once your into a block with several thousand transactions, your myrkel tree is going to have several layers, and only the bottom of the tree are actual transaction ID's; all the rest are artifacts of the myrkel tree, which every verification of a block must replicate. The binary myrkel tree within a block is a very efficient way to verifiablely store the data in a way that it can be trimmed later, but it's most certainly not a linear progression. More complex transaction types, such as contracts or send-to-many, has a similar effect; as the process for verifying transactions is not as simple as a single hash. Portions of the entire transaction must be excluded from the signing hash that each input address must add to the end of each transaction, and then be re-included as the verification process marches down the list of inputs. And that is just an example of what I, personally, know about the process. Logically, the increase in clock cycles for larger, and more complex, blocks and transactions must increase the propagation times at least linearly; and it's very likely to be greater than linear. Which is, by defintion, exponential. It may or may not matter in practice, as that exponetial growth may be so small as to not really effect the outcomes, but it is very likely present; and if so, the larger and more complex that blocks are permitted to grow the more likely said growth will metasize to a noticable level.