Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard

2013-11-15 Thread Peter Todd
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


Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard

2013-11-04 Thread Peter Todd
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

2013-11-04 Thread Mark Friedenbach
-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

2013-11-04 Thread Mike Hearn
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

2013-11-04 Thread Mark Friedenbach
-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

2013-11-04 Thread Mike Hearn
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