From: Peter Todd <pete@petertodd•org>
To: Mike Hearn <mike@plan99•net>
Cc: Bitcoin Dev <bitcoin-development@lists•sourceforge.net>
Subject: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
Date: Mon, 4 Nov 2013 13:16:49 -0500 [thread overview]
Message-ID: <20131104181649.GA3847@petertodd.org> (raw)
In-Reply-To: <CANEZrP1uqee1UO=zb+50t9BNtv2voTHoCKQCTQExNyoL=Y0=PA@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 2906 bytes --]
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
0000000000000002c43b3c05c0ed0842317747f0d1e3982489d0a51e7c8a05a3
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]
next prev parent reply other threads:[~2013-11-04 18:17 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-11-04 11:26 [Bitcoin-development] Auto-generated miner backbone Mike Hearn
2013-11-04 11:53 ` Peter Todd
2013-11-04 12:00 ` Mike Hearn
2013-11-04 18:16 ` Peter Todd [this message]
2013-11-04 18:32 ` [Bitcoin-development] Committing to extra block data/a better merge-mine standard Peter Todd
2013-11-04 19:11 ` Mark Friedenbach
2013-11-15 22:06 ` Peter Todd
2013-11-04 19:38 ` Mike Hearn
2013-11-04 19:53 ` Mark Friedenbach
2013-11-04 20:10 ` Mike Hearn
2013-11-04 11:58 ` [Bitcoin-development] Auto-generated miner backbone Michael Gronager
2013-11-04 12:03 ` Mike Hearn
2013-11-04 12:20 ` Peter Todd
2013-11-04 12:40 ` Michael Gronager
2013-11-04 15:58 ` Gregory Maxwell
2013-11-04 14:26 ` Peter Todd
2013-11-04 14:34 ` Pieter Wuille
2013-11-04 14:46 ` Peter Todd
[not found] ` <CABT1wWm1NzKSS9H=Qh3Z6pFmNHbOFKC12WaE=b3kE0mNsRgfmw@mail.gmail.com>
2013-11-04 15:04 ` Peter Todd
[not found] ` <CABT1wWmONUeOWRg-=FKr88bgBQf0un4bvjYW2h8d-10ys-VKtA@mail.gmail.com>
2013-11-04 15:46 ` Peter Todd
[not found] ` <CABT1wWmM466jWWdWAo5GmzP58xJFT70Vcr74ta+2QF2fWT+1SA@mail.gmail.com>
2013-11-04 16:07 ` Peter Todd
[not found] ` <CABT1wWm5BDZf7U40pOqZvTqdOKeTWUTekjUNckq5McMV=LDu_g@mail.gmail.com>
2013-11-04 16:51 ` Peter Todd
[not found] ` <CABT1wWmwb17b4ACHMmDKqd94tUSKsvwAPx344mZ0VS+47myeWg@mail.gmail.com>
2013-11-04 21:04 ` Peter Todd
2013-11-04 21:45 ` Alan Reiner
2013-11-04 22:03 ` Peter Todd
2013-11-04 15:27 ` Mike Hearn
2013-11-04 17:36 ` Peter Todd
2013-11-04 15:51 ` Gregory Maxwell
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20131104181649.GA3847@petertodd.org \
--to=pete@petertodd$(echo .)org \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
--cc=mike@plan99$(echo .)net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox