From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1Vty9M-0000sJ-9U for bitcoin-development@lists.sourceforge.net; Fri, 20 Dec 2013 11:21:48 +0000 Received: from mail-pb0-f49.google.com ([209.85.160.49]) by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1Vty9K-0003fM-Vw for bitcoin-development@lists.sourceforge.net; Fri, 20 Dec 2013 11:21:48 +0000 Received: by mail-pb0-f49.google.com with SMTP id jt11so2471090pbb.22 for ; Fri, 20 Dec 2013 03:21:41 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:organization:user-agent :mime-version:to:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=K5HCs4cp1ZuvhJPwmeqWxY0xd4TvL82b2e6ctUuHTF4=; b=HZV/YuK66QU5PpsufaKUmfMA7WeWy01gom/z35nUDv6dniyslV7ZK3wJiEN9aUiVnm FVHpFchlGEb3qAtUHQrpoE0QJjy8UIwCg8gjsjcC7PJtQroyiP56JDSxR9iEz6l9/1uj FdyKRlennnlE3bWts4Fua4aQ7Yvz2/em0gBlnI7zwIDd6WlSS3c1nCaVw3CaU/iv8jG1 4JZXpBHXXnN3Km1H2bZ+fkokVv8SaFPPFzG6ru1ChTLzHTwZ5fcL9SX5rccvdldPiGcn GgfzgWk2Gbm65EKN0yFGm7zpvZd38G/+fgUFqOLIcdKOHOOleYOnvpnGRdim9yQZJUME ORUw== X-Gm-Message-State: ALoCoQlnvcG9xlL68frD/b+MSVUSvqqctUkozJmmw0c6kUbNZI2xK0PK1Pg5ThldggVnZxDNL21s X-Received: by 10.66.220.198 with SMTP id py6mr7809984pac.21.1387538500999; Fri, 20 Dec 2013 03:21:40 -0800 (PST) Received: from [192.168.127.180] (50-0-36-217.dsl.dynamic.sonic.net. [50.0.36.217]) by mx.google.com with ESMTPSA id ae5sm17788281pac.18.2013.12.20.03.21.39 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 20 Dec 2013 03:21:40 -0800 (PST) Message-ID: <52B42842.6000306@monetize.io> Date: Fri, 20 Dec 2013 03:21:38 -0800 From: Mark Friedenbach Organization: Monetize.io Inc. User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0 MIME-Version: 1.0 To: bitcoin-development@lists.sourceforge.net References: <52B3A1C8.5000005@monetize.io> In-Reply-To: X-Enigmail-Version: 1.6 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. 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: enigmail.net] X-Headers-End: 1Vty9K-0003fM-Vw 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 11:21:48 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Jeremy, Let's give a preview of the application-oriented BIPs I mentioned: Stateless validation and mining involves prefixing transaction and block messages with proofs of their UTxO state changes. These are the "operational proofs" I describe in the draft, and they work on prefix trees whose root hashes committed to the coinbase in a soft-fork upgrade of the validation rules. "Ultimate blockchain compression" involves consensus over an address index, which can be queried over the p2p network by lightweight nodes. The structure of the index is an authenticated prefix tree, and the results of such a query is an an inclusion proof. Document time-stamping and this new method of merged mining use the same structure: a prefix tree whose root hash value is committed to a pruneable output of the coinbase transaction. Document timestamp proofs and merged mining proof-of-works are inclusion proofs over this tree. I hope that shows how the BIP directly affects interoperability of the bitcoin protocol and clients which use these applications. I released this BIP first to get some feedback on the structure itself, which will be used by all of the application-specific BIPs which follow. Stepping back and speaking generically, the purpose of a BIP as I see it is to standardize details which affect interoperability between clients. In fact, at a cursory glance only about half of the BIPs deal with protocol issues directly - the rest deal with local / user-interface issues like key derivation or JSON-RPC APIs. Even if none of the applications involved protocol changes, I still think BIPs like this would be of value in that they serve to standardize things which are or will seek to become commonly used and widely implemented. Cheers, Mark On 12/19/2013 10:48 PM, Jeremy Spilman wrote: > Wow there's a lot here to think about. I'm pretty sure I haven't > grasped the full implications yet. > > I see it proposes to also introduce additional BIPs describing the > use of the data stucture for stateless validation & mining, the UBC > address index for "SPV+" operating modes, document timestamping and > merged mining. > > Can the BIP stand alone as a BIP without some specific changes to > the protocol or end-user accessible features defined within it? It > seems like an extremely useful data stucture, but as I understand > it the purpose of BIPS is defining interoperability points, not > implementation details? > > Unless the tree itself is becoming part of the protocol, seems like > its spec, test vectors, and reference implementation can live > elsewhere, but I would love to read about BIPS which use this tree > to accomplish some amazing scalability or security benefits. > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (GNU/Linux) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJStChCAAoJEAdzVfsmodw42DcQAIlgkukh5K/XYloIiT5pgaHS xCZXtOvxpNUep8x35rvEO1ePjvPvUkbUE2jRw2se1rSMkhzw3PpHHtXV/gIOGqUe WVKeeIM5pZX56sEcEdUQ1pTwB2rmtSNeyCuHl8fLatk8eLhcAHcpv/7esLuAjWCr EE840s8+q3ltuzKi3nqxK84bwIohgSMKhncfonNp5lMAtug8Itqopq3DPDoxwiK/ qUwSz5UCEMH6oNHnywzhKGUhBErqo4q8IgAKcZYBZZ9n4BRjf4ngoCw9n5wCef8v tyTvwrg0nSQTQa67cg7RCsY7SisrI9gaMvCYTSvEMKdw9X0aqAX1p0yZpTbV+dIr Q2ZT6gJmg2sD22zKY1/58oq+PiNO+nRS81OG2znZofsIfhOVW0bIZAQ8+zZtFW40 vXxMuHCNieCK8e7f9A6LLv/Zz7rmNxdQ6cHBEL1nIs1Y4d1FpHJVI2LHi54QmVXf C5PKF/e7K2eD3LZMNxS818rZaiJJ7qmpjS3rkG2owHyJHEhBJIlkYXfI1YCraT+b R5AzAh2Oz0Nyb5ChP2VSaecJNjGvRMo7Z6HCytmgAGOEcDDZkxSv0kkprbvchqXx XziFgA4iSajBKYWPiPLGMADfMPT6zd4fhDjyaN8+LPO3d3ZK1VwmQDLRQ3DxfeIP RgchHR/pS77XI7hCFwtN =ao17 -----END PGP SIGNATURE-----