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=63469471iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Committing to extra block data/a better merge-mine standard
On Mon, Nov 04, 2013 at 01:00:16PM +0100, Mike Hearn wrote: Given that IP address data is inherently transient, perhaps a better solution is to define a short hash in the coinbase that commits to extra data that is relayed along with block data (e.g. appended to the block message). It can then be stored temporarily in the block db and erased after some time, like a few months. It would therefore not really be a part of the chain, but could be extended as we see fit with any other semi-transient data required. A new getextra message would let nodes query for it. The hash can be short because it doesn't have to survive brute forcing attacks longer than the expected validity period of the transient data anyway. 80 bits would probably be overkill. 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; another 22 bytes is insignificant compared to the size of the path. 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. For timestamping, just pick any empty spot in the tree. 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 optional PUSHDATA just prior to the commitment pushdata, allowing overly long paths to be eliminated entirely by simply incrmenting the nonce. Unlike the original, broken, merge-mining standard alt-coins have used this actually works, extends indefinitely, and is simple and easy to validate given a single merkle-path for each purpose. Generating the trees of commitments is a bit convoluted, but at least that code only needs to be written once. -- 'peter'[:-1]@petertodd.org 0002c43b3c05c0ed0842317747f0d1e3982489d0a51e7c8a05a3 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=65839951iu=/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=65839951iu=/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=65839951iu=/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 p...@petertodd.org 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=65839951iu=/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=65839951iu=/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 m...@monetize.io 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=65839951iu=/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=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
