Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
On Mon, Nov 04, 2013 at 11:11:34AM -0800, Mark Friedenbach wrote: > > 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. You don't need level compression if you adopt my per-block randomization idea. I think we'd be better off keeping the proofs as simple as possible, just dumb merkle paths. > 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 mentioned UUID more in spirit than in terms of the official UUID standard; any large randomly picked integer is fine. > If there is general interest, I can make finishing this a higher priority. Wouldn't hurt to run the idea past forrestv, given p2pool will be affected as it'd need to adopt the standard. He's run into some oddness with mining hardware and nonces that would be good to understand. (note how p2pool blocks don't commit to a fully random hash - there's some extra bytes in there due to stratum or something IIRC) -- 'peter'[:-1]@petertodd.org 000601a5b2f2b4a597851fdf00f6fc3572bbc03f26857c170032 signature.asc Description: Digital signature -- DreamFactory - Open Source REST & JSON Services for HTML5 & Native Apps OAuth, Users, Roles, SQL, NoSQL, BLOB Storage and External API Access Free app hosting. Or install the open source package on any LAMP server. Sign up and see examples for AngularJS, jQuery, Sencha Touch and Native! http://pubads.g.doubleclick.net/gampad/clk?id=63469471&iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
Yes, sure. I was talking about the case of transiently relayed data, like IP addresses. On Mon, Nov 4, 2013 at 8:53 PM, Mark Friedenbach wrote: > -BEGIN PGP SIGNED MESSAGE- > Hash: SHA1 > > On 11/4/13 11:38 AM, Mike Hearn wrote: > > The Merkle branch doesn't get stored indefinitely though, whereas > > the coinbase hash does. The data stored in the coinbase [output] > > can always just be the 256-bit root hash truncated to less. > > > > I doubt the additional bytes make much difference really, so the > > additional complexity may not be worth it. But it wouldn't be an > > issue to do. > > The bits make a difference if you are merged mining. You can use the > birthday attack to construct two data trees whose hash match the > (truncated) value, each containing separate aux block headers. This > allows you to double-count the bitcoin PoW for more than one aux block > on the same chain, potentially facilitating aux chain attacks. > > If you want 128 bits of security for merged mined aux chains, you need > 256 bits of hash in the coinbase. > -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/shAAoJEAdzVfsmodw48a0P/RaCOctBDvhU0THnsUw6nRBm > A8oH3Kpio4ZltU4oIT0tznZbUOG2j2xVrmATqXDYOZQ6FuGihjmkKJ9jHgl57pb5 > 0qDdCBiEuWtLIh2+Awrb3Y0s8czyCQP9/1CJyzdEFmI8rSwCaqJMa6B2Ny6Xz6+8 > eiK45YdXCPgdTAb56FKOi9WzOe0g1aOO5KiUOci22xRkXvh4qPYrt2F0LIgjZTdC > koyXU6dcKON9H8Cecu+ag7jJ5A9ZDj7oIq5rflEyolh2V4ie0tGQ50rFGg/ii6iQ > Tz9AWwigsHEkuinBTuN5041Xb8nAgHLvA60RQ41lWUHJxfAvDE+wN6NqgHmMVaRo > NHqlZcCuEl1jn7HW81XQTpgarrXHk1G7b2vK10pB/lUxUNIstZvCSjcp8QdtmC9v > tIhC2czSnsQaE6kIBuHxDNZxOlZ8DxBYCAgXSkycwznwzGhFPP0xB1lV9HfaP5+i > aikmx5SQmqBXQQKsxmIacoykrfu5x+O2TB/bq8JhJ1ak2jG9LVFyQqjorABVAgA7 > pLEN6EomWht5qstaLVfHYpNsLMf6WA7UzRG08HKItUeDPtG7bDx8vBx5TvIUjT44 > A0i09bOt8ZIgp+lJ8lFLWiPLChViAoy7fqKy2vrdsZerOF3l4LUQeQO/xnfZc+dG > AEG+7iCBOMxJSVoJ5bP6 > =nydG > -END PGP SIGNATURE- > > > -- > Android is increasing in popularity, but the open development platform that > developers love is also attractive to malware creators. Download this white > paper to learn more about secure code signing practices that can help keep > Android apps secure. > http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk > ___ > Bitcoin-development mailing list > Bitcoin-development@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 11/4/13 11:38 AM, Mike Hearn wrote: > The Merkle branch doesn't get stored indefinitely though, whereas > the coinbase hash does. The data stored in the coinbase [output] > can always just be the 256-bit root hash truncated to less. > > I doubt the additional bytes make much difference really, so the > additional complexity may not be worth it. But it wouldn't be an > issue to do. The bits make a difference if you are merged mining. You can use the birthday attack to construct two data trees whose hash match the (truncated) value, each containing separate aux block headers. This allows you to double-count the bitcoin PoW for more than one aux block on the same chain, potentially facilitating aux chain attacks. If you want 128 bits of security for merged mined aux chains, you need 256 bits of hash in the coinbase. -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/shAAoJEAdzVfsmodw48a0P/RaCOctBDvhU0THnsUw6nRBm A8oH3Kpio4ZltU4oIT0tznZbUOG2j2xVrmATqXDYOZQ6FuGihjmkKJ9jHgl57pb5 0qDdCBiEuWtLIh2+Awrb3Y0s8czyCQP9/1CJyzdEFmI8rSwCaqJMa6B2Ny6Xz6+8 eiK45YdXCPgdTAb56FKOi9WzOe0g1aOO5KiUOci22xRkXvh4qPYrt2F0LIgjZTdC koyXU6dcKON9H8Cecu+ag7jJ5A9ZDj7oIq5rflEyolh2V4ie0tGQ50rFGg/ii6iQ Tz9AWwigsHEkuinBTuN5041Xb8nAgHLvA60RQ41lWUHJxfAvDE+wN6NqgHmMVaRo NHqlZcCuEl1jn7HW81XQTpgarrXHk1G7b2vK10pB/lUxUNIstZvCSjcp8QdtmC9v tIhC2czSnsQaE6kIBuHxDNZxOlZ8DxBYCAgXSkycwznwzGhFPP0xB1lV9HfaP5+i aikmx5SQmqBXQQKsxmIacoykrfu5x+O2TB/bq8JhJ1ak2jG9LVFyQqjorABVAgA7 pLEN6EomWht5qstaLVfHYpNsLMf6WA7UzRG08HKItUeDPtG7bDx8vBx5TvIUjT44 A0i09bOt8ZIgp+lJ8lFLWiPLChViAoy7fqKy2vrdsZerOF3l4LUQeQO/xnfZc+dG AEG+7iCBOMxJSVoJ5bP6 =nydG -END PGP SIGNATURE- -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
I like the UUID-as-path idea. That resolves the problem of how to share the alt-chain merkle tree quite nicely. On Mon, Nov 4, 2013 at 7:16 PM, Peter Todd wrote: > No sense in compromising - you need a whole merkle path to prove the > extra data is valid so you might as well make this a full 256 bits; > The Merkle branch doesn't get stored indefinitely though, whereas the coinbase hash does. The data stored in the coinbase [output] can always just be the 256-bit root hash truncated to less. I doubt the additional bytes make much difference really, so the additional complexity may not be worth it. But it wouldn't be an issue to do. -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
-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-
--
Android is increasing in popularity, but the open development platform that
developers love is also attractive to malware creators. Download this white
paper to learn more about secure code signing practices that can help keep
Android apps secure.
http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
On Mon, Nov 04, 2013 at 01:16:49PM -0500, Peter Todd wrote: > You'll want to put some "reasonable" limit on actual path lengths, just > pick something like 32 levels; if applications pick their UUIDs honestly > a collision will be very unlikely. You can also make the allowed paths > block specific by defining them as H(uuid | nonce), with nonce as an This could be H(uuid | nLockTime) Coinbase transactions still have a nLockTime, and while it's generally left at zero it can be any value valid for a transaction in the block. -- 'peter'[:-1]@petertodd.org 00086d6d5b17d979d44a24a68bcf92eb9aea18351e4f6bc485b6 signature.asc Description: Digital signature -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
