From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1VdPYr-000163-85 for bitcoin-development@lists.sourceforge.net; Mon, 04 Nov 2013 19:11:41 +0000 Received: from mail-pb0-f43.google.com ([209.85.160.43]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1VdPYq-0001pz-0I for bitcoin-development@lists.sourceforge.net; Mon, 04 Nov 2013 19:11:41 +0000 Received: by mail-pb0-f43.google.com with SMTP id md4so7478517pbc.16 for ; Mon, 04 Nov 2013 11:11:34 -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=ugiiTDSGSqUzwMfbD6cIFxG2xDWSQNINWEowJPEkNI0=; b=bBoNmIWJ8o7m/Q7BeuU6Mll0sdanSGuuLwY8aBtrrpoAamE2kCvB5Wmbq7kJw1obGk aSUf25PqFJ5PkxlPG9Z2vAEX8cTM0E1Qm1szgtdtMzuD1M+FQC7M9ASMhcYFzuYeL+j7 sfS8GY8vkg09hYe+0mi34AnIV2hUWXwQqxIf5gwKXLITj96XEkbRv95IswNDxTGS9e4l 2PYDP0z+FtFjc5vMcgmX0F8hQfkPGn3sJkZsGPlptTaD/8IAdDGH05JWR/ReV16Mf/Zj a94CJf03XF6BQX32tbTbDaGwl9oVGVrxX2cxNzIT9Qa2pDY8G07YbR6LJqWKcCwJ+ZHH LMqA== X-Gm-Message-State: ALoCoQkVlQgSopyeDP7cdc4Rv5aVJPOx6lqfWFvJsPDpF0oRFpqpTXZrT8pTVtrfPLQMmbNa04Kk X-Received: by 10.66.141.144 with SMTP id ro16mr2586330pab.173.1383592294008; Mon, 04 Nov 2013 11:11:34 -0800 (PST) Received: from phobos.local (50-0-36-80.dsl.dynamic.sonic.net. [50.0.36.80]) by mx.google.com with ESMTPSA id gh3sm9124906pbb.2.2013.11.04.11.11.32 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 04 Nov 2013 11:11:33 -0800 (PST) Message-ID: <5277F166.9090606@monetize.io> Date: Mon, 04 Nov 2013 11:11:34 -0800 From: Mark Friedenbach Organization: Monetize.io Inc. User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:24.0) Gecko/20100101 Thunderbird/24.1.0 MIME-Version: 1.0 To: bitcoin-development@lists.sourceforge.net References: <20131104115314.GA1013@savin> <20131104181649.GA3847@petertodd.org> In-Reply-To: <20131104181649.GA3847@petertodd.org> 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: 1VdPYq-0001pz-0I Subject: Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard 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: Mon, 04 Nov 2013 19:11:41 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 11/4/13 10:16 AM, Peter Todd wrote: > Again, the right way to do this is define the standard to use the > last txout so that midstate compression can be applied in the > future. We can re-use this for merge-mining and other commitments > easily by defining a simple standard based on defined path > directions. Essentially for each thing you might want to commit, > perhaps a merge-mined coin, a p2pool share, a UTXO commitment, > whatever, generate a random 128-bit UUID. > > Now interpret the bits of that UUID as an allowed path: 0 = left, 1 > = right, from the top of the tree. When you build the tree, make > sure everything that is going to be committed to uses it's allowed > path; the tree will look a bit jagged. If everyone picks their > per-purpose UUIDs randomly the paths won't collide for very many > levels on average, and path lengths will remain short. Validating > that some given data was committed properly is simple and easy: > just check the path, and check that the directions from the top of > the tree followed the spec. You mean... an authenticated prefix tree? Composable/commutative properties are not needed as far as I can see, so you could make the path validation, traversal, and proof size smaller by using level compression. I had previously proposed to this list a hash256-to-UUID mechanism explicitly for this purpose. Recap: use 122 of the low 128 bits of the aux-chain's genesis block to form a version=4 (random) or version=6 (previously unused) UUID. However since making that proposal I am now leaning towards simply using the hash of the genesis block directly to identify aux chains since level compression will allow longer keys with the same path length. I'm in the middle of writing BIPs to this end, among my many other tasks. But basically it's the same as you describe ("OP_RETURN <32-byte auth tree root>" for the last output), except keys don't necessarily have to be UUIDs. If there is general interest, I can make finishing this a higher priority. Mark -----BEGIN PGP SIGNATURE----- Version: GnuPG/MacGPG2 v2.0.19 (Darwin) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJSd/FmAAoJEAdzVfsmodw4pA0QALtgKLKsMNFocUanKGNp5T1F 918IjFt/HASRMs4GXiPpIeTB+o5Id6aCsg1ikKRuL9xD+WKoSyo83JP5UmcxGjFA WTPi/0/ArYRh8L7ECvWoBSanNrun3z72p3KMI1Aa8qcJCgWbPx88AYeJv0Ki4JOo 1Pxc883772bOJnazrh4f/C4gcrqrlgs29PwI1rc3yCD9dmJhVmkz+O0/yfq+U8Gg FXrpqR14mUM36wGX2HjqEual7Ry/7TEz5Ne4o8uncaVHtGgaYVw45a5Hk6rdo1rH F3EV9nIpsLhGyqbKPqSxSju2h3eYQxQXKUP14mJS+ja/mKFXVc3PXDV+IHtXAplk 4gW8vtTWtVIDJAGTTh5RkJu5yAr57vq9lUMTNGGk6v1C3xOPP2C097sHRLaD4kD+ olsw5M9NW/Qpn1X3SCN3K85f7dvV3+fucmWL8mPM9KMLfc38fgs7I5SQgurMngsS 2D5jSwcZVjI/4n6ocgK3Y66yKC5xuzOOi2ZV+pPM38TjUeCF8fbjRnoIWyaBPDWy mKA0bJiw5NMzi+IsNK5YDS5Gqb3qxS6tYLCp1+hesW3pBj35Zv/LdSh5DyecRETW J0ye56lw/DfRAfNf+YERvrznqC2WVDZcQaElACq8R/nPJ2HD53p+SfxMSbljVO+I SDsDOSvAzfQjQBLGdkx7 =5fPS -----END PGP SIGNATURE-----