Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1TCDYW-0003PD-PE for bitcoin-development@lists.sourceforge.net; Thu, 13 Sep 2012 17:50:24 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of eigbox.net designates 66.96.188.16 as permitted sender) client-ip=66.96.188.16; envelope-from=SRS0=nh6BJu=HM=godofgod.co.uk=matthewmitchell@eigbox.net; helo=bosmailout16.eigbox.net; Received: from bosmailout16.eigbox.net ([66.96.188.16]) by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1TCDYV-0005vp-Po for bitcoin-development@lists.sourceforge.net; Thu, 13 Sep 2012 17:50:24 +0000 Received: from bosmailscan08.eigbox.net ([10.20.15.8]) by bosmailout16.eigbox.net with esmtp (Exim) id 1TCDYQ-0003lu-Hb for bitcoin-development@lists.sourceforge.net; Thu, 13 Sep 2012 13:50:18 -0400 Received: from bosimpout02.eigbox.net ([10.20.55.2]) by bosmailscan08.eigbox.net with esmtp (Exim) id 1TCDYQ-00030U-13; Thu, 13 Sep 2012 13:50:18 -0400 Received: from bosauthsmtp11.eigbox.net ([10.20.18.11]) by bosimpout02.eigbox.net with NO UCE id yhpv1j00J0EKspE01hpvqi; Thu, 13 Sep 2012 13:49:55 -0400 X-Authority-Analysis: v=2.0 cv=V8rKJ5bi c=1 sm=1 a=Vnyysazsc9gF4v5jbSvB8A==:17 a=Goz4v7xpImgA:10 a=JhU9KSwl1l8A:10 a=RmqW3wxksLsA:10 a=eGitJVp2AAAA:8 a=-aUnnjAAwhoA:10 a=pGLkceISAAAA:8 a=wqI5gXztqGSwXhhk5iEA:9 a=CjuIK1q_8ugA:10 a=MSl-tDqOz04A:10 a=HraHw9EmjoyJ3M4Frn0A:9 a=_W_S_7VecoQA:10 a=anyYG9rjTBM1sAjEBQ8Cew==:117 X-EN-OrigOutIP: 10.20.18.11 X-EN-IMPSID: yhpv1j00J0EKspE01hpvqi Received: from [109.175.173.27] by bosauthsmtp11.eigbox.net with esmtpsa (TLSv1:AES128-SHA:128) (Exim) id 1TCDY2-0003n4-PP; Thu, 13 Sep 2012 13:49:55 -0400 From: Matthew Mitchell Content-Type: multipart/alternative; boundary="Apple-Mail=_1431EAE0-F143-4154-BECE-76E80F9BB9D4" Message-Id: Mime-Version: 1.0 (Mac OS X Mail 6.0 \(1486\)) Date: Thu, 13 Sep 2012 18:49:49 +0100 References: <2104FC7F-0AE0-4C55-9987-B20EFCE19FC3@godofgod.co.uk> <19ED4257-0BCA-41C5-A533-B0AB9B500181@godofgod.co.uk> <2B95CF41-4304-4D2A-9ABF-198D97B7449B@godofgod.co.uk> To: Gregory Maxwell , "bitcoin-development@lists.sourceforge.net" In-Reply-To: X-Mailer: Apple Mail (2.1486) X-EN-UserInfo: c68a83c59c94ef03b40bb4bc312c51e4:dffc0a9b4c8a0435ad832ff5852cab82 X-EN-AuthUser: godofgod@godofgod.co.uk Sender: Matthew Mitchell X-EN-OrigIP: 109.175.173.27 X-EN-OrigHost: unknown X-Spam-Score: -0.7 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 SPF_PASS SPF: sender matches SPF record -0.5 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain 1.0 HTML_MESSAGE BODY: HTML included in message 0.3 AWL AWL: From: address is in the auto white-list X-Headers-End: 1TCDYV-0005vp-Po Subject: Re: [Bitcoin-development] Segmented Block Relaying BIP draft. X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 13 Sep 2012 17:50:24 -0000 --Apple-Mail=_1431EAE0-F143-4154-BECE-76E80F9BB9D4 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii On 13 Sep 2012, at 16:51, Gregory Maxwell wrote: > I thoroughly understand the value of tree hashes. That wasn't what I > was asking about. >=20 > If you're validating a block you need all the transactions, once you > have them or their hashes you can build the tree without transferring > more, e.g. what a fully validating node needs. If you're checking a > single transaction to need the path from the transaction to the root > (what a SPV nodes need, for example). >=20 > Can you spell out the 'end user'ish application for fetching a tree = level? A merkle tree root is found by hashing the two children together and = those children are found the same way until you get to the greatest = level down the tree. This means you can validate children as being = correct as long as they hash together to form the root. This means you = do not need all the transaction hashes to validate segments of the = block, you only need the root hashes for all the segments you want. = Let's say there are 8 transactions and you want to verify 4 segments (2 = transactions each), The merkle tree looks like this (Might not work = depending on the font): Level 0: * / \ / \ / \ / \ / \ / \ / \ Level 1: * * / \ / \ / \ / \ / \ / \ Level 2: * * * * / \ / \ / \ / \ Level 3: * * * * * * * * When you look at any non-leaf node you can see a separate merkle tree = where the root can be found exactly the same as any other merkle tree. = In this example you want four segments, so you ask for level 2. Now = imagine a tree without level 3, you can validate the root with level 2. = In fact you can validate that the root exists for any level. So you = first check that the level 2 hashes do indeed calculate to the root. = Once this is done you can now use these hashes to validate the segments. = When you receive a segment, you check that segment against the segment's = root. So you've validated the segment transactions for the segment root = and the segment root was validated for the entire tree's root. You = validate the segments for each segment root and this way you know all = the transactions are valid for the four segments and thus are valid for = the entire tree. This way you have downloaded 4 hashes instead of 8.=20 Downloading the transactions hashes are therefore not necessary only the = level for the segment roots. You might for instance want to divide the = block into two segments in which case you ask for level 1 and download 2 = hashes. I hope that made sense. And yes the merkle tree is particularly useful for validating a single = transaction exists in a block as that saves a large proportion of the = data required. The redundant data removed in the proposal here is = smaller as a proportion of the total data (Because most of the data is = the actual transactions themselves), so you might argue it's not worth = it but it's simple to implement.= --Apple-Mail=_1431EAE0-F143-4154-BECE-76E80F9BB9D4 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=us-ascii
On = 13 Sep 2012, at 16:51, Gregory Maxwell <gmaxwell@gmail.com> = wrote:

I thoroughly understand the = value of tree hashes. That wasn't what I
was asking about.

If = you're validating a block you need all the transactions, once = you
have them or their hashes you can build the tree without = transferring
more, e.g. what a fully validating node needs. If you're = checking a
single transaction to need the path from the transaction = to the root
(what a SPV nodes need, for example).

Can you = spell out the 'end user'ish application for fetching a tree = level?

A merkle tree root is = found by hashing the two children together and those children are found = the same way until you get to the greatest level down the tree. This = means you can validate children as being correct as long as they hash = together to form the root. This means you do not need all the = transaction hashes to validate segments of the block, you only need the = root hashes for all the segments you want. Let's say there are 8 = transactions and you want to verify 4 segments (2 transactions each), = The merkle tree looks like this (Might not work depending on the = font):

Level 0:   =             *
              =         / \
                  =    /   \
                  =   /     \
                  =  /       \
                  / =         \
                 / =           \
              =   /             = \
Level 1:     =   *               = *
      =         / \           =   / \
    =          /   \         =   /   \
  =           /     \     =     /     \
Level 2:   *       *       * =       *
          / \     / \   =   / \ =     / = \
Level 3: *   * =   *   = *   *   * =   *   = *

When you look at = any non-leaf node you can see a separate merkle tree where the = root can be found exactly the same as any other merkle tree. = In this example you want four segments, so you ask for level 2. Now = imagine a tree without level 3, you can validate the root with level 2. = In fact you can validate that the root exists for any level. = So you first check that the level 2 hashes do = indeed calculate to the root. Once this is done you can now = use these hashes to validate the segments. When you receive a segment, = you check that segment against the segment's root. So you've validated = the segment transactions for the segment root and = the segment root was validated for the entire tree's root. = You validate the segments for each segment root and this way = you know all the transactions are valid for the four segments and thus = are valid for the entire tree. This way you have downloaded 4 = hashes instead of 8. 

Downloading the = transactions hashes are therefore not necessary only the level for the = segment roots. You might for instance want to divide the block into two = segments in which case you ask for level 1 and download 2 = hashes.

I hope that made = sense.

And yes the merkle = tree is particularly useful for validating a single transaction exists = in a block as that saves a large proportion of the data required. The = redundant data removed in the proposal here is smaller as a proportion = of the total data (Because most of the data is the actual transactions = themselves), so you might argue it's not worth it but it's simple to = implement.
= --Apple-Mail=_1431EAE0-F143-4154-BECE-76E80F9BB9D4--