From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id DF124B7E for ; Fri, 31 Mar 2017 22:05:09 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f47.google.com (mail-it0-f47.google.com [209.85.214.47]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D9018172 for ; Fri, 31 Mar 2017 22:05:08 +0000 (UTC) Received: by mail-it0-f47.google.com with SMTP id 68so7802878itx.0 for ; Fri, 31 Mar 2017 15:05:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bittorrent-com.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=zoaCtHs3Y1Xaum+4bAjR4RBg6G6hCwPXH5MUlGgAxPc=; b=RlIX0k3pA6X+5wPAFSLHspzhsYIASdll6MWwYA9BUG8o4XYp4DccDCGowTSDzDFpKK 1Bu74gZeZtMlZLeBt+cx7jUlzikGk8kmZxN6DKVKBJTETv1/d1BiRowpzB8KvgDAMl/I uTcnHfHuX31jgtp+btnHBJBRoUPVvaUu5ZjI2z6FDpxz8RcxvE0nA1Nf6jWGYoe2uVfg UIDq57R+KZTo3AJ41q2uWb7NLQT/W053XCpDm9XnCT5gTYklwyKnwch/xps4XYRCX9HL okERy4+csTh2AUdzwIF62JlJiKRj9hwFHLejL1x8dhMZV5vQ4iPCK52q6fMpdR1svjcy KCHg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=zoaCtHs3Y1Xaum+4bAjR4RBg6G6hCwPXH5MUlGgAxPc=; b=qvrZyy/dML3ZaNJBcxCx1mvvnYIYzHuyqdsfTbEykW9uL3kOWXMhQLl00ivY/LnlY0 OHnjfx09VvlDkjO98JRzhfKiUlITyV7czsSkjakJVWnLnNtrCI/xwT1NUBxzxtWvMd58 O4fAs9UxTIY13+CKE64K4VhZmEnrr7kgvbKeJE+U1Vyv7ld+V2jX8Ej1eMTMBZH7YTab m80KFR4p/+aNBGLQkSPDNws/pCgvoLseG2ERPG8yV7ytzhlLSeflWgCJ8exJrYv+5nEY w/3LwZNnr+yBfW0eBDmrDL8yTP4pZ/E+KlZH2HSzHBHZQD+2hFFDeR095km3oSK4Er2j zxFQ== X-Gm-Message-State: AFeK/H0Qfg9k3Qb6Dco92auNDs4YZxcm4x0qV04RkCuZpbb+RdYQLDKAKWUaF2k+aTxj05k3ThV/aNzcDqX3G34X X-Received: by 10.36.188.129 with SMTP id n123mr6062091ite.65.1490997908012; Fri, 31 Mar 2017 15:05:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.36.184.70 with HTTP; Fri, 31 Mar 2017 15:05:07 -0700 (PDT) From: Bram Cohen Date: Fri, 31 Mar 2017 15:05:07 -0700 Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=94eb2c114564ab1933054c0e00f9 X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [bitcoin-dev] The TXO bitfield X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 31 Mar 2017 22:05:10 -0000 --94eb2c114564ab1933054c0e00f9 Content-Type: text/plain; charset=UTF-8 Looking forward in node scaling we can envision a future in which blocks are required to come with proofs of their validity and nodes can be run entirely in memory and never have to hit disk. Ideally we'd like for proofs to be able to be stored in client wallets which plan to spend their utxos later, or at least be able to have a full node make a single not terribly expensive disk access to form the proof which can then be passed along to other peers. Such proofs will probably be significantly larger than the blocks they prove (this is merkle root stuff, not zero knowledge stuff), but if we accept that as a given then this should be doable, although the details of how to do it aren't obvious. This vision can be implemented simply and efficiently by playing some games with the semantics of the term 'proof'. A proof is a thing which convinces someone of something. What we've discussed in the past for such proofs mostly has to do with maintaining a hash root of everything and having proofs lead to that. This is an extrema of complexity of the proof and simplicity of the checker, at the expense of forcing the root to be maintained at all times and the proof to be reasonably fresh. Some tricks can be applied to keep that problem under control, but there's an alternative approach where the amount of data necessary to do validation is much larger but still entirely reasonable to keep in memory, and the sizes of proofs and their required freshness is much smaller. In the previous discussion on Merkle sets I commented that insertion ordering's main practical utility may be that it allows for compression. It turns out that a constant factor of 256 makes a big difference. Since there's only really one bit stored for each txo (stored or not) once you have an insertion ordering you can simply store a bitfield of all txos so far, which is entirely reasonable to hold in memory, and can be made even more reasonable by compactifying down the older, mostly spent portions of it (how best to compress a bitfield while maintaining random access is an interesting problem but entirely doable). This approach meets all the design goals, even allowing wallets to remember their own 'proofs', which are just proofs of insertion ordering. Those don't even change once the risk of reorgs has passed, so they can be stored for years without being maintained. Proofs of insertion ordering can be made by having a canonical way of calculating a root of position commitments for each block, and nodes calculate those roots when evaluating the block history and store them all in memory. A proof of position is a path to one of those roots. I've intentionally skipped over most of the details here, because it's probably best to have a high level discussion of this as a general approach before getting lost in the weeds. --94eb2c114564ab1933054c0e00f9 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Looking forward in node scaling we can envision a future i= n which blocks are required to come with proofs of their validity and nodes= can be run entirely in memory and never have to hit disk. Ideally we'd= like for proofs to be able to be stored in client wallets which plan to sp= end their utxos later, or at least be able to have a full node make a singl= e not terribly expensive disk access to form the proof which can then be pa= ssed along to other peers.

Such proofs will probably be = significantly larger than the blocks they prove (this is merkle root stuff,= not zero knowledge stuff), but if we accept that as a given then this shou= ld be doable, although the details of how to do it aren't obvious.

This vision can be implemented simply and efficiently = by playing some games with the semantics of the term 'proof'. A pro= of is a thing which convinces someone of something. What we've discusse= d in the past for such proofs mostly has to do with maintaining a hash root= of everything and having proofs lead to that. This is an extrema of comple= xity of the proof and simplicity of the checker, at the expense of forcing = the root to be maintained at all times and the proof to be reasonably fresh= . Some tricks can be applied to keep that problem under control, but there&= #39;s an alternative approach where the amount of data necessary to do vali= dation is much larger but still entirely reasonable to keep in memory, and = the sizes of proofs and their required freshness is much smaller.

In the previous discussion on Merkle sets I commented that = insertion ordering's main practical utility may be that it allows for c= ompression. It turns out that a constant factor of 256 makes a big differen= ce. Since there's only really one bit stored for each txo (stored or no= t) once you have an insertion ordering you can simply store a bitfield of a= ll txos so far, which is entirely reasonable to hold in memory, and can be = made even more reasonable by compactifying down the older, mostly spent por= tions of it (how best to compress a bitfield while maintaining random acces= s is an interesting problem but entirely doable).

= This approach meets all the design goals, even allowing wallets to remember= their own 'proofs', which are just proofs of insertion ordering. T= hose don't even change once the risk of reorgs has passed, so they can = be stored for years without being maintained.

Proo= fs of insertion ordering can be made by having a canonical way of calculati= ng a root of position commitments for each block, and nodes calculate those= roots when evaluating the block history and store them all in memory. A pr= oof of position is a path to one of those roots.

I= 've intentionally skipped over most of the details here, because it'= ;s probably best to have a high level discussion of this as a general appro= ach before getting lost in the weeds.
--94eb2c114564ab1933054c0e00f9--