Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1Vu63j-0000k5-Gf for bitcoin-development@lists.sourceforge.net; Fri, 20 Dec 2013 19:48:31 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.220.42 as permitted sender) client-ip=209.85.220.42; envelope-from=gmaxwell@gmail.com; helo=mail-pa0-f42.google.com; Received: from mail-pa0-f42.google.com ([209.85.220.42]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1Vu63h-0003Dg-IO for bitcoin-development@lists.sourceforge.net; Fri, 20 Dec 2013 19:48:31 +0000 Received: by mail-pa0-f42.google.com with SMTP id lj1so3060302pab.15 for ; Fri, 20 Dec 2013 11:48:23 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.68.110.132 with SMTP id ia4mr10423878pbb.99.1387568903679; Fri, 20 Dec 2013 11:48:23 -0800 (PST) Received: by 10.70.81.170 with HTTP; Fri, 20 Dec 2013 11:48:23 -0800 (PST) In-Reply-To: <52B3A1C8.5000005@monetize.io> References: <52B3A1C8.5000005@monetize.io> Date: Fri, 20 Dec 2013 11:48:23 -0800 Message-ID: From: Gregory Maxwell To: Mark Friedenbach Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -1.6 (-) 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 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (gmaxwell[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked. See http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block for more information. [URIs: monetize.io] -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1Vu63h-0003Dg-IO Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees 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: Fri, 20 Dec 2013 19:48:31 -0000 On Thu, Dec 19, 2013 at 5:47 PM, Mark Friedenbach wrote: > Hello fellow bitcoin developers. Included below is the first draft of > a BIP for a new Merkle-compressed data structure. The need for this > data structure arose out of the misnamed "Ultimate blockchain > compression" project, but it has since been recognized to have many > other applications. A couple very early comments=E2=80=94 I shared some of these with you on IR= C but I thought I'd post them to make them more likely to not get lost. Whats a VARCHAR() A zero terminated string? A length prefixed string? How is the length encoded? Hopefully not in a way that has redundancy, since things that don't survive a serialization round trip is a major trap. Is the 'middle' the best place for the extradata? Have you contemplated the possibility that some applications might use midstate compression? On that general subject, since the structure here pretty much always guarantees two compression function invocations. SHA512/256 might actually be faster in this application. Re: using sha256 instead of sha256^2, we need to think carefully about the implications of Merkle-Damgard generic length extension attacks. It would be unfortunately to introduce them here, even though they're currently mostly theoretical for sha256. WRT hash function performance, hash functions are so ludicrously fast (and will be more so as processors get SHA2 instructions) that the performance of the raw compression function would hardly ever be a performance consideration unless you're using a slow interpreted language (... and that sounds like a personal problem to me). So I don't think CPU performance should be a major consideration in this BIP. What I do think should be a consideration is the cost of validating the structure under a zero-knowledge proof. An example application is a blind proof for a SIN or a proof of how much coin you control... or even a proof that a block was a correctly validated one, and in these cases additional compression function calls are indeed pretty expensive. But they're not the only cost, any conditional logic in the hash tree evaluation is expensive, and particular, I think that any place where data from children will be combined with a variable offset (especially if its not word aligned) would potentially be rather expensive. I'm unconvinced about the prefix tree compressed applications, since they break compact update proofs. If we used them in the Bitcoin network they could only be used for data where all verifying nodes had all their data under the tree. I think they add a lot of complexity to the BIP (esp from people reading the wrong section), so perhaps they should be split into another document? In any case, I want to thank you for talking the time to write this up. You've been working on this stuff for a while and I think it will be lead to useful results, even if we don't end up using how it was originally envisioned.