Bitcoin Forum
December 09, 2016, 06:17:33 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 [2]  All
  Print  
Author Topic: P2P block download - use bit torrent like method  (Read 4317 times)
JoelKatz
Legendary
*
Offline Offline

Activity: 1386


Democracy is vulnerable to a 51% attack.


View Profile WWW
July 14, 2011, 10:16:35 PM
 #21

Bittorrent can get me data as fast as my connection, why should it take half a day to get 200MB on Bitcoin?
Because you are performing multiple cryptographic operations to validate every single byte of those 200MB. For each block received, you must at least:

1) Check that the hash of the block meets the target.
2) Check that the block correctly links to the preceding block.
3) Calculate the Merkle tree for all the transactions and verify it against the block header.
4) Retrieve every transaction whose outputs are claimed by transactions in this block.
5) Check the difficulty against the block count and timestamps.
6) For every input of most transactions, you must check that the public key has the correct hash and that the signature is correct.

I picked a random block (136,301) and did the math, it's about 500 signatures and 800 hashes for that one block. A typical mid-range modern CPU can verify 800 signatures a second and compute 300,000 hashes per second. (Including the overhead to set up each operation. You can do them faster in a tight brainless loop where the code stays in caches, that's unrealistic.) So processing this one block would take about half a second. (In fairness, this was an unusually large block.)

Now you're trying to do this 136,000 times. That's 18 hours at 2 blocks per second.

I am an employee of Ripple.
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
1481264253
Hero Member
*
Offline Offline

Posts: 1481264253

View Profile Personal Message (Offline)

Ignore
1481264253
Reply with quote  #2

1481264253
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
TierNolan
Legendary
*
Offline Offline

Activity: 1050


View Profile
July 14, 2011, 10:58:20 PM
 #22

Now you're trying to do this 136,000 times. That's 18 hours at 2 blocks per second.

You could just trust any block that is more than 1000 blocks behind the head of the chain.

All other blocks could be verified by just checking that the hashes match.

If security is really required, then you could do the verification slowly once the entire chain has been downloaded.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
JoelKatz
Legendary
*
Offline Offline

Activity: 1386


Democracy is vulnerable to a 51% attack.


View Profile WWW
July 15, 2011, 12:21:33 AM
 #23

Now you're trying to do this 136,000 times. That's 18 hours at 2 blocks per second.

You could just trust any block that is more than 1000 blocks behind the head of the chain.
That creates a chicken and egg problem. You can't know the correct block X until you know the correct block X-1. So saying "if it's 1,000 blocks behind a valid block, it's valid" won't help.

Suppose there are 136,000 blocks in the chain. You receive, from an untrusted peer, a block that purports to be block 53,000. How can you tell it's more than 1,000 blocks behind the block 136,000 that you don't even know exists yet because you have no way to verify it?

Quote
If security is really required, then you could do the verification slowly once the entire chain has been downloaded.
So then why bother to download the blocks really quickly? There's nothing you can do with an unverified block -- you don't know it's valid.

I am an employee of Ripple.
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
TierNolan
Legendary
*
Offline Offline

Activity: 1050


View Profile
July 15, 2011, 12:31:57 AM
 #24

That creates a chicken and egg problem. You can't know the correct block X until you know the correct block X-1. So saying "if it's 1,000 blocks behind a valid block, it's valid" won't help.

The block chain can be verified first without verifying the transactions contained in it.  Only the 80 byte block header is required to verify that each header is part of a chain.

Quote
Suppose there are 136,000 blocks in the chain. You receive, from an untrusted peer, a block that purports to be block 53,000. How can you tell it's more than 1,000 blocks behind the block 136,000 that you don't even know exists yet because you have no way to verify it?

If you receive 100 different chains from 100 different peers, you can still check which one is the longest chain.  That gets you all the block headers for the strongest chain.

You can use that to verify where each block slots into the sequence of blocks.

If someone sends you money you can verify that it hasn't been double spent by seeing if it is included in the block chain, with 6 confirms, it isn't likely to be a double spend.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
deepceleron
Legendary
*
Offline Offline

Activity: 1470



View Profile WWW
July 15, 2011, 12:58:16 AM
 #25

Now you're trying to do this 136,000 times. That's 18 hours at 2 blocks per second.

You could just trust any block that is more than 1000 blocks behind the head of the chain.
That creates a chicken and egg problem. You can't know the correct block X until you know the correct block X-1. So saying "if it's 1,000 blocks behind a valid block, it's valid" won't help.

Suppose there are 136,000 blocks in the chain. You receive, from an untrusted peer, a block that purports to be block 53,000. How can you tell it's more than 1,000 blocks behind the block 136,000 that you don't even know exists yet because you have no way to verify it?

Quote
If security is really required, then you could do the verification slowly once the entire chain has been downloaded.
So then why bother to download the blocks really quickly? There's nothing you can do with an unverified block -- you don't know it's valid.


I'm suggesting having a deep queue of the next blocks ready for verification so the only bottleneck is processing them. If after verifying block #100 I have to hit the p2p network again, request block #101, and wait for the client I request a block from to respond (or not) and send it to me, that's adding that much more latency per block. Block #101 from the network is as likely to be valid if I get it on-demand, or if I've already downloaded blocks 102-500 too. If I've filled my queue and still have network speed to burn, I could have even requested block #101 three times and MD5'd them or have a pool of potential blocks in case I need to sort out which is the longest block chain (although this is silly, the chance of picking up in-the-wild invalid early blocks seems so low that we can almost assume everything we get is good and ignore optimizing the queue around this possibility).

A basic proof to see if there is utility would be to bootstrap a fresh client on a local-only network with several nodes and see how close you can peg CPU to 100% (this still has the client idle requesting the next block). How long does it take to get all the blocks? Then do the same on the P2P network. If it takes longer, there is room for improvement.


TierNolan
Legendary
*
Offline Offline

Activity: 1050


View Profile
July 15, 2011, 08:43:05 AM
 #26

I'm suggesting having a deep queue of the next blocks ready for verification so the only bottleneck is processing them. If after verifying block #100 I have to hit the p2p network again, request block #101, and wait for the client I request a block from to respond (or not) and send it to me, that's adding that much more latency per block. Block #101 from the network is as likely to be valid if I get it on-demand, or if I've already downloaded blocks 102-500 too.

The current system requests blocks in groups of up to 500 blocks at a time.  It possibly does download -> verify -> download -> verify.

The key point is that once you have the block headers, you can download the full blocks in any order.  You can verify any  block by checking that the header matches and that the merkle root is correct.  This proves that it is a valid part of the chain.  This can be done without checking any of the signatures.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
JoelKatz
Legendary
*
Offline Offline

Activity: 1386


Democracy is vulnerable to a 51% attack.


View Profile WWW
July 15, 2011, 02:00:39 PM
 #27

That creates a chicken and egg problem. You can't know the correct block X until you know the correct block X-1. So saying "if it's 1,000 blocks behind a valid block, it's valid" won't help.

The block chain can be verified first without verifying the transactions contained in it.  Only the 80 byte block header is required to verify that each header is part of a chain.
Right, but so what? Just because the header is valid you cannot conclude the block is valid.

Quote
Quote
Suppose there are 136,000 blocks in the chain. You receive, from an untrusted peer, a block that purports to be block 53,000. How can you tell it's more than 1,000 blocks behind the block 136,000 that you don't even know exists yet because you have no way to verify it?

If you receive 100 different chains from 100 different peers, you can still check which one is the longest chain.  That gets you all the block headers for the strongest chain.
The "longest chain" test only applies among valid chains. A longer chain that is not valid is not strongest.

Quote
If someone sends you money you can verify that it hasn't been double spent by seeing if it is included in the block chain, with 6 confirms, it isn't likely to be a double spend.
Again, chicken and egg problem. You can't tell if it's included in the block chain with 6 confirms until you know which chain is the valid one, and that requires checking the transactions.

I am an employee of Ripple.
1Joe1Katzci1rFcsr9HH7SLuHVnDy2aihZ BM-NBM3FRExVJSJJamV9ccgyWvQfratUHgN
TierNolan
Legendary
*
Offline Offline

Activity: 1050


View Profile
July 15, 2011, 03:23:30 PM
 #28

Right, but so what? Just because the header is valid you cannot conclude the block is valid.

The further from the end of the chain that a block occurs, the more likely it is to be valid.  If you accept a transactions after 6 confirms, then you should accept a block that is 6+ back along the block chain.

To fake it, you need > 50% of the hashing power of the network since the point where you fork it.

Quote
The "longest chain" test only applies among valid chains. A longer chain that is not valid is not strongest.

The chain "timestamp"/certification process is secured by the hashing power of the network not by the digital signatures on the transactions.

If you were able to generate an alternative chain that was longer than the main chain, then you could just generate a chain which is 100% coinbase transactions all payable to you.

As long as a chain starts from the genesis block, has valid timestamps (increasing properly and not more than 2 hours in the future), correctly calculated difficulty updates and all hashes meet the difficulty target, then it can be assumed to be a valid chain.  This can be confirmed entirely by looking at the headers.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Pages: « 1 [2]  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!