From mboxrd@z Thu Jan 1 00:00:00 1970 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 1WSQT1-000738-JM for bitcoin-development@lists.sourceforge.net; Tue, 25 Mar 2014 12:28:31 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.81 as permitted sender) client-ip=62.13.149.81; envelope-from=pete@petertodd.org; helo=outmail149081.authsmtp.net; Received: from outmail149081.authsmtp.net ([62.13.149.81]) by sog-mx-2.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1WSQSz-0005Mm-It for bitcoin-development@lists.sourceforge.net; Tue, 25 Mar 2014 12:28:31 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt18.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s2PCSNAb028676; Tue, 25 Mar 2014 12:28:23 GMT Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s2PCSFAs033960 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Tue, 25 Mar 2014 12:28:17 GMT Date: Tue, 25 Mar 2014 08:28:51 -0400 From: Peter Todd To: Mark Friedenbach Message-ID: <20140325122851.GA9818@savin> References: <20140322084702.GA13436@savin> <20140322150836.GG3180@nl.grid.coop> <20140322190825.GB6047@savin> <532DE7E6.4050304@monetize.io> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="Q68bSM7Ycu6FN28Q" Content-Disposition: inline In-Reply-To: <532DE7E6.4050304@monetize.io> User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: f21c3da0-b418-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdAcUFVQGAgsB AmIbWlZeUlV7WGs7 bAxPbAVDY01GQQRq WVdMSlVNFUsrA3xy ZWhvERlxdAxAeDB2 bUNmWT4NXkUpdhIs QlMGEWwOeGZhPWMC AkhYdR5UcAFPdx8U a1UrBXRDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA43BDMx AhsCFDQpBgUdXSg3 LhknLFcGDQ4KL0A3 OEEwMf9/ X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) 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 X-Headers-End: 1WSQSz-0005Mm-It Cc: bitcoin-development@lists.sourceforge.net Subject: Re: [Bitcoin-development] Tree-chains preliminary summary 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: Tue, 25 Mar 2014 12:28:31 -0000 --Q68bSM7Ycu6FN28Q Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Mar 22, 2014 at 12:43:34PM -0700, Mark Friedenbach wrote: > Btw, any chance we could get a summary description of tree-chains > posted to bitcoin-development? Sure: Introduction =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Bitcoin doesn't scale. There's a lot of issues at hand here, but the most fundemental of them is that to create a block you need to update the state of the UTXO set, and the way Bitcoin is designed means that updating that state requires bandwidth equal to all the transaction volume to keep up with the changes to what set. Long story short, we get O(n^2) scaling, which is just plain infeasible. So let's split up the transaction volume so every individual miner only needs to keep up with some portion. In a rough sense that's what alt-coins do - all the tipping microtransactions on Doge never have to hit the Bitcoin blockchain for instance, reducing pressure on the latter. But moving value between chains is inconvenient; right now moving value requires trusted third parties. Two-way atomic chain transfers does help here, but as recent discussions on the topic showed there's all sorts of edge cases with reorganizations that are tricky to handle; at worst they could lead to inflation. So what's the underlying issue there? The chains are too independent. Even with merge-mining there's no real link between one chain and another with regard to the order of transactions. Secondly merge-mining suffers from 51% attacks if the chain being merge-mined doesn't have a majority of total hashing power... which kinda defeats the point if we're worried about miner scalability. Blocks and the TXO set as a binary radix tree =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D So how can we do better? Start with the "big picture" idea and take the linear blockchain and turn it into a tree: =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=B4=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=90 =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94=B4=E2=94=80=E2=94=80=E2= =94=80=E2=94=90 =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94=B4=E2=94= =80=E2=94=80=E2=94=80=E2=94=90 =E2=94=8C=E2=94=80=E2=94=B4=E2=94=80=E2=94=90 =E2=94=8C=E2=94=80=E2= =94=B4=E2=94=80=E2=94=90 =E2=94=8C=E2=94=80=E2=94=B4=E2=94=80=E2=94=90 = =E2=94=8C=E2=94=80=E2=94=B4=E2=94=80=E2=94=90 =E2=94=8C=E2=94=B4=E2=94=90 =E2=94=8C=E2=94=B4=E2=94=90 =E2=94=8C=E2=94= =B4=E2=94=90 =E2=94=8C=E2=94=B4=E2=94=90 =E2=94=8C=E2=94=B4=E2=94=90 =E2=94= =8C=E2=94=B4=E2=94=90 =E2=94=8C=E2=94=B4=E2=94=90 =E2=94=8C=E2=94=B4=E2=94= =90 Obviously if we could somehow split up the UTXO set such that individual miners/full nodes only had to deal with subsets of this tree we could significantly reduce the bandwidth that any one miner would need to process. Every transaction output would get a unique identifier, say txoutid=3DH(txout) and we put those outputs in blocks appropriately. We can't just wave a magic wand and say that every block has the above structure and all miners co-ordinate to generate all blocks in one go. Instead we'll do something akin to merge mining. Start with a linear blockchain with ten blocks. Arrows indicate hashing: a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD a4 =E2=87=BD a5 =E2= =87=BD a6 =E2=87=BD a7 =E2=87=BD a8 =E2=87=BD a9 The following data structure could be the block header in this scheme. We'll simplify things a bit and make up our own; obviously with some more effort the standard Satoshi structures can be used too: struct BlockHeader: uint256 prevBlockHash uint256 blockContentsHash uint256 target uint256 nonce uint time For now we'll say this is a pure-proof-of-publication chain, so our block contents are very simple: struct BlockContents: uint256 merkleRoot As usual the PoW is valid if H(blockHeader) < blockHeader.target. Every block creates new txouts, and the union of all such txouts is the txout set. As shown previously(1) this basic proof-of-publication functionality is sufficient to build a crypto-currency even without actually validating the contents of the so-called transaction outputs. The scalability of this sucks, so let's add two more chains below the root to start forming a tree. For fairness we'll only allow miners to either mine a, a+b, or a+c; attempting to mine a block with both the b and c chains simultaneously is not allowed. struct BlockContents: uint256 childBlockHash # may be null bool childSide # left or right uint256 merkleRoot Furthermore we shard the TXO space by defining txoid =3D H(txout) and allowing any txout in chain a, and only txouts with LSB=3D0 in b, LSB=3D1 in c; the beginning of a binary radix tree. With some variance thrown in we get the following: b0 =E2=87=BD=E2=87=BD b1 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87= =BD b2 =E2=87=BD b3 =E2=87=BD b4 =E2=87=BD b5 =E2=87=BD b6 =E2=87=BD b7 =E2= =87=BD b8 =E2=86=99 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD=E2=87=BD=E2=87=BD= =E2=87=BD=E2=87=BD=E2=87=BD a4 =E2=87=BD a5 =E2=87=BD a6 =E2=87=BD a7 =E2= =87=BD a8 =E2=86=96 =E2=86=96 =E2=86=96 =E2=86=96 = =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 =E2=87=BD c3 =E2=87=BD=E2=87=BD=E2=87= =BD=E2=87=BD=E2=87=BD=E2=87=BD c4 =E2=87=BD c5 =E2=87=BD c6 =E2=87=BD=E2=87= =BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD c7 We now have three different versions of the TXO set: =E2=88=91a, =E2=88=91a= + =E2=88=91b, and =E2=88=91a+=E2=88=91c. Each of these versions is consistent in that for a g= iven txoutid prefix we can achieve consensus over the contents of the TXO set. Of course, this definition is recursive: a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD=E2=87=BD=E2=87=BD= =E2=87=BD=E2=87=BD=E2=87=BD a4 =E2=87=BD a5 =E2=87=BD a6 =E2=87=BD a7 =E2= =87=BD a8 =E2=86=96 =E2=86=96 =E2=86=96 =E2=86=96 = =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 =E2=87=BD c3 =E2=87=BD=E2=87=BD=E2=87= =BD=E2=87=BD=E2=87=BD=E2=87=BD c4 =E2=87=BD c5 =E2=87=BD c6 =E2=87=BD=E2=87= =BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD c7 =E2=86=96 =E2=86=96 =E2=86=96 =E2=86=96 = =E2=86=96 d0 =E2=87=BD d1 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2= =87=BD d2 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD d3 =E2=87= =BD d4 =E2=87=BD=E2=87=BD=E2=87=BD d5 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD = d6 Unicode unfortunately lacks 3D box drawing at present, so I've only shown left-sided child chains. Herding the child-chains =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D If all we were doing was publishing data, this would suffice. But what if we want to syncronize our actions? For instance, we may want a new txout to only be published in one chain if the corresponding txout in another is marked spent. What we want is a reasonable rule for child-chains to be invalidated when their parents are invalidated so as to co-ordinate actions across distant child chains by relying on the existance of their parents. We start by removing the per-chain difficulties, leaving only a single master proof-of-work target. Solutions less than target itself are considered valid in the root chain, less than the target << 1 in the root's children, << 2 in the children's children etc. In children that means the header no longer contains a time, nonce, or target; the values in the root block header are used instead: struct ChildBlockHeader: uint256 prevChildBlockHash uint256 blockContentsHash For a given chain we always choose the one with the most total work. But to get our ordering primitive we'll add a second, somewhat brutal, rule: Parent always wins. We achieve this moving the child block header into the parent block itself: struct BlockContents: ChildBlockHeader childHeader # may be null (zeroed out) bool childSide # left or right bytes txout Let's look at how this works. We start with a parent and a child chain: a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=86=96 =E2=86=96 b0 =E2=87=BD b1 =E2=87=BD b2 =E2=87=BD b3 =E2=87=BD b4 =E2=87=BD b5 First there is the obvious scenario where the parent chain is reorganized. Here our node learns of a2 =E2=87=BD a3' =E2=87=BD a4': =E2=87=BD a3' =E2=87=BD a4' a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD X =E2=86=96 =E2=86=96 b0 =E2=87=BD b1 =E2=87=BD b2 =E2=87=BD b3 =E2=87=BD X Block a3 is killed, resulting in the orphaning of b3, b4, and b5: a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3' =E2=87=BD a4' =E2=86=96 b0 =E2=87=BD b1 =E2=87=BD b2 The second case is when a parent has a conflicting idea about what the child chian is. Here our node receives block a5, which has a conflicting idea of what child b2 is: a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3' =E2=87=BD a4' =E2=87=BD a5 =E2=86=96 =E2=86=96 b0 =E2=87=BD b1 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87= =BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD= =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD b2' =E2=87=BD b2 =E2=87=BD X As the parent always wins, even multiple blocks can get killed off this way: a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD a4 =E2=86=96 b0 =E2=87=BD b1 =E2=87=BD b2 =E2=87=BD b3 =E2=87=BD b4 =E2=87=BD b5 = =E2=87=BD b6 =E2=87=BD b7 to: a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD a4 =E2=87=BD a5 =E2=86=96 =E2=86=96 b0 =E2=87=BD b1 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87= =BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD= =E2=87=BD=E2=87=BD b2' =E2=87=BD b2 =E2=87=BD b3 =E2=87=BD b4 =E2=87=BD b5 =E2=87= =BD X This behavior is easier to understand if you say instead that the node learned about block b2', which had more total work than b2 as the sum total of work done in the parent chain in blocks specifying the that particular child chain is considered before comparing the total work done in only the child chain. It's important to remember that the parent blockchain has and validates both childrens' block headers; it is not possible to mine a block with an invalid secret of child headers. For instance with the following: a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD a4 =E2=86=96 =E2=86=96 =E2=86=96 b0 =E2=87=BD b1 =E2=87=BD b2 =E2=87=BD b3 =E2=87=BD b4 =E2=87=BD b5 = =E2=87=BD b6 =E2=87=BD b7 I can't mine block a5 that says following b2 is b2' in an attempt to kill off b2 through b7. Token transfer with tree-chains =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D How can we make use of this? Lets start with a simple discrete token transfer system. Transactions are simply: struct Transaction: uint256 prevTxHash script prevPubKey script scriptSig uint256 scriptPubKeyHash We'll say transactions go in the tree-chain according to their prevTxHash, with the depth in the tree equal to the depth of the previous output. This means that you can prove an output was created by the existance of that transaction in the block with prefix matching H(tx.prevTxHash), and you can prove the transaction output is unspent by the non-existance of a transaction in the block with prefix matching H(tx). With our above re-organization rule everything is consistent too: if block b_i contains tx1, then the corresponding block c_j can contain a valid tx2 spending tx1 provided that c_j depends on a_p and there is a path from a_p to b_(i+k). Here's an example, starting with tx1 in c2: b0 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD b1 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD a2 =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 Block b2 below can't yet contain tx2 because there is no path: b0 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD b1 =E2=87= =BD b2 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD a2 =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 However now c3 is found, whose PoW solution was also valid for a3: b0 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD b1 =E2=87= =BD b2 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=86=96 =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 =E2=87=BD c3 Now b3 can contain tx2, as b3 will also attempt to create a4, which depends on a3: b0 =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD b1 =E2=87= =BD b2 =E2=87=BD b3 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=86=96 =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 =E2=87=BD c3 Now that a3 exists, block c2 can only be killed if a3 is, which would also kill b3 and thus destroy tx2. Proving transaction output validity in a token transfer system =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D How cheap is it to prove the entire history of a token is valid from genesis? Perhaps surprisingly, without any cryptographic moon-math the cost is only linear! Remember that a transaction in a given chain has committed to the chain that it can be spent in. If Alice is to prove to Bob that the output she gave him is valid, she simply needs to prove that for every transaction in the histroy of the token the token was created, remained unspent, then finally was spent. Proving a token remained unspent between blocks b_n and b_m is trivially possible in linear size. Once the token is spent nothing about blocks beyond b_m is required. Even if miners do not validate transactions at all the proof size remains linear provided blocks themselves have a maximum size - at worst the proof contains some invalid transactions that can be shown to be false spends. While certainly inconvenient, it is interesting how such a simple system appears to in theory scale to unlimited numbers of transactions and with an appropriate exchange rate move unlimited amounts of value. A possible model would be for the the tokens themselves to have power of two values, and be split and combined as required. The lost data problem =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D There is however a catch: What happens when blocks get lost? Parent blocks only contain their childrens' headers, not the block contents. At some point the difficulty of producing a block will drop sufficiently for malicious or accidental data loss to be possible. With the "parent chain wins" rule it must be possible to recover from that event for mining on the child to continue. Concretely, suppose you have tx1 in block c2, which can be spent on chain b. The contents of chain a is known to you, but the full contents of chain b are unavailable: b0 =E2=87=BD b1 (b) (b) =E2=86=99 =E2=86=99 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD a4 =E2=87=BD a5 =E2=86=96 =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 =E2=87=BD c3 =E2=87=BD c4 =E2=87=BD c5 Blocks a3 and a4 are known to have children on b, but the contents of those children are unavailable. We can define some ratio of unknown to known blocks that must be proven for the proof to be valid. Here we show a 1:1 ratio: =E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2= =87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87=BD=E2=87= =BD b0 =E2=87=BD b1 (b) (b) b2 =E2=87=BD b3 =E2=87=BD b4 =E2=87= =BD b5 =E2=87=BD b6 =E2=87=BD b7 =E2=86=99 =E2=86=99 =E2=86=99 =E2=86=99 = =E2=86=99 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD a2 =E2=87=BD a3 =E2=87=BD a4 =E2=87=BD a5 =E2= =87=BD a6 =E2=87=BD a7 =E2=87=BD a8 =E2=87=BD a9 =E2=86=96 =E2=86=96 =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 =E2=87=BD c3 =E2=87=BD c4 =E2=87=BD c5 = =E2=87=BD c6 =E2=87=BD c7 =E2=87=BD c8 =E2=87=BD c9 The proof of now shows that while a3 and a4 has b-side blocks, by the time you reach b6 those two lost blocks were in the minority. Of course a real system needs to be careful that mining blocks and then discarding them isn't a profitably way to create coins out of thin air - ratios well in excess of 1:1 are likely to be required. Challenge-response resolution =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D Another idea is to say if the parent blockchain's contents are known we can insert a challenge into it specifying that a particular child block be published verbatim in the parent. Once the challenge is published further parent blocks may not reference that children on that side until either the desired block is re-republished or some timeout is reached. If the timeout is reached, mining backtracks to some previously known child specified in the challenge. In the typical case the block is known to a majority of miners, and is published, essentially allowing new miners to force the existing ones to "cough up" blocks they aren't publishing and allow the new ones to continue mining. (obviously some care needs to be taken with regard to incentives here) While an attractive idea, this is our first foray into moon math. Suppose such a challenge was issued in block a2, asking for the contents of b1 to be published. Meanwhile tx1 is created in block c3, and can only be spent on a b-side chain: b0 =E2=87=BD b1 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD (a2) =E2=87=BD a3 =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 =E2=87=BD c3 The miners of the b-chain can violate the protocol by mining a4/b1', where b1' appears to contain valid transaction tx2: b0 =E2=87=BD b1 b1' =E2=86=99 =E2=86=99 a0 =E2=87=BD a1 =E2=87=BD (a2) =E2=87=BD a3 =E2=87=BD a4 =E2=86=96 c0 =E2=87=BD c1 =E2=87=BD c2 =E2=87=BD c3 A proof of tx2 as valid payment would entirely miss fact that the challenge was published and thus not know that b1' was invalid. While I'm sure the reader can come up with all kinds of complex and fragile way of proving fraud to cause chain a to be somehow re-organized, what we really want is some sub-linear proof of honest computation. Without getting into details, this is probably possible via some flavor of sub-linear moon-math proof-of-execution. But this paper is too long already to start getting snarky. Beyond token transfer systems =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D We can extend our simple one txin, one txout token transfer transactions with merkle (sum) trees. Here's a rough sketch of the concept: input #1=E2=94=80=E2=94=90 =E2=94=8C=E2=94=80output #1 =E2=94=9C=E2=94=90 =E2=94=8C=E2=94=A4 input #2=E2=94=80=E2=94=98=E2=94=82 =E2=94=82=E2=94=94=E2=94=80output #2 =E2=94=9C=E2=94=80=E2=94=A4 input #3=E2=94=80=E2=94=90=E2=94=82 =E2=94=82=E2=94=8C=E2=94=80output #3 =E2=94=9C=E2=94=98 =E2=94=94=E2=94=A4 input #4=E2=94=80=E2=94=98 =E2=94=94=E2=94=80output #4 Where previously a transaction committed to a specific transaction output, we can make our transactions commit to a merkle-sum-tree of transaction outputs. To then redeem a transaction output you prove that enough prior outputs were spend to add up to the new output's value. The entire process can happen incrementally without any specific co-operation between miners on different parts of the chain, and inputs and outputs can come from any depth in the tree provided that care is taken to ensure that reorganization is not profitable. Like the token transfer system proving a given output is valid has cost linear with history. However we can improve on that using non-interactive proof techniques. For instance in the linear token transfer example the history only needs to be proven to a point where the transaction fees are higher than the value of the output. (easiest where the work required to spend a txout of a given value is well defined) A similar approach can be easily taken with the directed-acyclic-graph of mutliple-input-output transactions. Secondly non-interactive proof techniques can also be used, again out of the scope of this already long preliminary paper. 1) "Disentangling Crypto-Coin Mining: Timestamping, Proof-of-Publication, and Validation", http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/= msg03307.html --=20 'peter'[:-1]@petertodd.org 00000000000000002fd949770524eea54446adb70603a90a4c493d345f890e04 --Q68bSM7Ycu6FN28Q Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (GNU/Linux) iQGrBAEBCACVBQJTMXZ8XhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDA2ZWEyNzQxYzlhYjFlOWZmZjA3ZWEwNjk1OTA1N2Y5M2Vl NDc2Njg1Yjc0YTE5YTEvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfsZvgf+LCbcOmir87U2hAiHaBj1F4NF GQ7VdOeSd6ss9kJqxKaAoAG4LrUVlOqa/eXdouGYisZiTXXE9RH+97Umb7lPobI+ TCv8n8iRwOfHZ2hNs9A69RPGD4ijHMUoLdjBULFH/03atFF2X9tlEi7FmR3JWU48 YaPliWx5z/QKQgu9KDmojLwRrb4bxl3Jj97+n7i0LCDoAl/M2brCJgNdXtH3j5Zc gHf6oIhSsznhFubzGU/FQxFKyR+QaMa4Zx74sbtakEH+PNIrG5KSZfxLwoKQlxAv if7RAoNvUHFJYJRYvAmSlMhdI3YNBomTYyMyyulULq0ya6scGVUa9cR6XvroEg== =TSgu -----END PGP SIGNATURE----- --Q68bSM7Ycu6FN28Q--