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 98EF8959 for ; Wed, 8 Mar 2017 01:55:20 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f44.google.com (mail-it0-f44.google.com [209.85.214.44]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 07E9F139 for ; Wed, 8 Mar 2017 01:55:19 +0000 (UTC) Received: by mail-it0-f44.google.com with SMTP id m27so17727363iti.1 for ; Tue, 07 Mar 2017 17:55:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bittorrent-com.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=x2zsrJoRwmQc+BpFaZR6Ke48oN/EO621E1Gh5LJqSfA=; b=Qv8g01q2R2V7gr/DD7T5mR+QOk0dWNXMpqo5pQUOyikPnuU0X+T2PzXfnbzfBayn5t jz3p7kCiIqo3UJ1etNjfEx1Jl++Bm3I7OIJgIrHIPknqTdBgfeE3FfvcRkFEOYWg6v9m BnwtiMZBuRhhvneivjW53g/5ZPq2lhSZ2dpXZf5bMT6lsVHFV0T11/Mr+k1RRFwIHZ6I +Xqa8m/RMZcOei7+Pr4P4uBS3irK3ZJMIlVVVxV6Xn9CHFC5MlSV0z71LO31/VQBCcEA oW7cXVb7S7ntoc4QKty0bfGZeyyrwLn2GIbJYT+DAA9K0/sFiueGsn8dm5FnazKYsO2K j2pA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=x2zsrJoRwmQc+BpFaZR6Ke48oN/EO621E1Gh5LJqSfA=; b=jLVm73uavZiJ4qGJzqhV6tepMeAXzsAB8rgL010sMb7U82UFzz6ai6RO5WHjIIIEzc 5Ot1W26WCyGWgMIGN1NXLftxJT2kmhTMkR8RQzzALR0JCaRSaIBnjp/8m+n9TKmgPSPl X1a7mx37UBEj05p441GVnVWDJPqzXlDRGsu+DxcsBltKa8ThdcsWBAhz/ZryxpVc0swQ gc9ddU9CI/zdrhkFEEwrlQ6bIeTjOBareaky+LxOh75Eg9m3TrzcNdX3hSW9KGnefuza 3vHsWv/dYRDfD4dTg+zSN+bUpUCFtkAZNILZfX5gzelysGvvpDMUnQSpjYndzcDwZ8FS ayiw== X-Gm-Message-State: AMke39nhC8BOu8mE71fK75X9SLp6/zk+sIkOkeJGEHgVIs76fXT7l+oB/vsdMfes4hVl4wuBNgcpKV7FcNVHCjak X-Received: by 10.36.196.8 with SMTP id v8mr23422130itf.115.1488938119362; Tue, 07 Mar 2017 17:55:19 -0800 (PST) MIME-Version: 1.0 Received: by 10.36.254.132 with HTTP; Tue, 7 Mar 2017 17:55:18 -0800 (PST) In-Reply-To: <_Z0S6yfN2uS1b0SYoZzU9LMo3QQ967dyn0e12ep_aXJ8cNw8wTovQWED6mKg3PH0hb2yKEG-5Cv0xH3IC2cG5rczP5qo-xLtrjJMXW1uCss=@protonmail.com> References: <_Z0S6yfN2uS1b0SYoZzU9LMo3QQ967dyn0e12ep_aXJ8cNw8wTovQWED6mKg3PH0hb2yKEG-5Cv0xH3IC2cG5rczP5qo-xLtrjJMXW1uCss=@protonmail.com> From: Bram Cohen Date: Tue, 7 Mar 2017 17:55:18 -0800 Message-ID: To: praxeology_guy , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=94eb2c05d0d4b2abc9054a2e6b75 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_LOW, RCVD_IN_SORBS_SPAM autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] A Commitment-suitable UTXO set "Balances" file data structure 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: Wed, 08 Mar 2017 01:55:20 -0000 --94eb2c05d0d4b2abc9054a2e6b75 Content-Type: text/plain; charset=UTF-8 On Tue, Mar 7, 2017 at 1:28 PM, praxeology_guy via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > > merkle tree hashes: > - array of "piece count" leaf hashes, hashing the balance pieces > - array of "(child layer count + 1)/2" node hashes, hashing pairs of child > hashes, or copying up if only one child > - repeat ^ until the root hash is written > ... except reverse the layer order. In other words, it should be breadth > first. > A big yuck on that format. It should be something based on a patricia trie to support incremental updates. Also if the things being stored are output transaction + output number then those two can be hashed together to make a consistent size identifier and be put into the merkle set format I proposed, which is exactly the intended usage: https://github.com/bramcohen/MerkleSet - We could make BCP 4383 blocks, which would be 12 times per year, given > block period was exactly 10 minutes. But since block period is not exactly > 10 minutes, and file names generated with period 4283 are much less > comprehensible than file names generated with period 5000... I propose > 5000. > If it's of that order it should be synched up with the work difficulty reset interval of 2016. If the format supports incremental updates it would of course be possible to require them more frequently later. > - Having a shorter BCP period would result in more frequent checks on UTXO > set integrity, and permit new pruning nodes to start synching closer to the > tip. But it may require nodes to keep more copies of the balances file to > satisfy the same backup period, and require more background work of > creating more balances files. > With a patricia based format it would be possible to make much more common utxo commitments, possibly as often as every block only trailing by a few, and the cost of updating wouldn't be onerous and reorgs could be handled by simply undoing the last few transactions in the set and and then rolling forward. --94eb2c05d0d4b2abc9054a2e6b75 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On T= ue, Mar 7, 2017 at 1:28 PM, praxeology_guy via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

merkle tree= hashes:
- array of "piece count" leaf hashes, hash= ing the balance pieces
- array of "(child layer count + = 1)/2" node hashes, hashing pairs of child hashes, or copying up if onl= y one child
- repeat ^ until the root hash is written
... except reverse the layer order. In other words, it should be bre= adth first.

A big yuck on that fo= rmat. It should be something based on a patricia trie to support incrementa= l updates. Also if the things being stored are output transaction + output = number then those two can be hashed together to make a consistent size iden= tifier and be put into the merkle set format I proposed, which is exactly t= he intended usage: https= ://github.com/bramcohen/MerkleSet

- We could make BCP 4383 blocks, whic= h would be 12 times per year, given block period was exactly 10 minutes.=C2= =A0 But since block period is not exactly 10 minutes, and file names genera= ted with period 4283 are much less comprehensible than file names generated= with period 5000...=C2=A0 I propose 5000.

<= /div>
If it's of that order it should be synched up with the work d= ifficulty reset interval of 2016. If the format supports incremental update= s it would of course be possible to require them more frequently later.
=C2=A0
<= /div>
- Having a shorter BCP period would result in more frequent check= s on UTXO set integrity, and permit new pruning nodes to start synching clo= ser to the tip.=C2=A0 But it may require nodes to keep more copies of the b= alances file to satisfy the same backup period, and require more background= work of creating more balances files.

With a patricia based format it would be possible to make much m= ore common utxo commitments, possibly as often as every block only trailing= by a few, and the cost of updating wouldn't be onerous and reorgs coul= d be handled by simply undoing the last few transactions in the set and and= then rolling forward.

--94eb2c05d0d4b2abc9054a2e6b75--