[Bitcoin-development] BIP draft - Auxiliary Header Format

[Bitcoin-development] BIP draft - Auxiliary Header Format

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 603 bytes --]

I created a draft BIP detailing a way to add auxiliary headers to Bitcoin
in a bandwidth efficient way.  The overhead per auxiliary header is only
around 104 bytes per header.  This is much smaller than would be required
by embedding the hash of the header in the coinbase of the block.

It is a soft fork and it uses the last transaction in the block to store
the hash of the auxiliary header.

It makes use of the fact that the last transaction in the block has a much
less complex Merkle branch than the other transactions.

https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki

[-- Attachment #2: Type: text/html, Size: 797 bytes --]

Re: [Bitcoin-development] BIP draft - Auxiliary Header Format

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 2329 bytes --]

I made some changes to the draft.  The merkleblock now has the auxiliary
header information too.

There is a tradeoff between overhead and delayed transactions.  Is 12.5%
transactions being delayed to the next block unacceptable?  Would adding
padding transactions be an improvement?

Creating the "seed" transactions is an implementation headache.

Each node needs to have control over an UTXO to create the final
transaction in the block that has the digest of the auxiliary header.  This
means that it is not possible to simply start a node and have it mine.  It
has to somehow be given the private key.  If two nodes were given the same
key by accident, then one could end up blocking the other.

On one end of the scale is adding a transaction with a few thousand outputs
into the block chain.  The signatures for locktime restricted transactions
that spend those outputs could be hard-coded into the software.  This is
the easiest to implement, but would mean a large table of signatures.  The
person who generates the signature list would have to be trusted not to
spend the outputs early.

The other end of the scale means that mining nodes need to include a
wallets to manage their UTXO entry.  Miners can split a zero value output
into lots of outputs, if they wish.

A middle ground would be for nodes to be able to detect the special
transactions and use them.  A server could send out timelocked transactions
that pay to a particular address but the transaction would be timelocked.
The private key for the output would be known.  However, miners who mine
version 2 blocks wouldn't be able to spend them early.


On Sat, Nov 8, 2014 at 11:45 PM, Tier Nolan <tier.nolan@gmail.com> wrote:

> I created a draft BIP detailing a way to add auxiliary headers to Bitcoin
> in a bandwidth efficient way.  The overhead per auxiliary header is only
> around 104 bytes per header.  This is much smaller than would be required
> by embedding the hash of the header in the coinbase of the block.
>
> It is a soft fork and it uses the last transaction in the block to store
> the hash of the auxiliary header.
>
> It makes use of the fact that the last transaction in the block has a much
> less complex Merkle branch than the other transactions.
>
> https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki
>
>

[-- Attachment #2: Type: text/html, Size: 2968 bytes --]

Re: [Bitcoin-development] BIP draft - Auxiliary Header Format

[Gregory Maxwell]

Some initial comments...

Tying in the protocol changes is really confusing and the fact that
they seem to be required out the gates would seemingly make this much
harder to deploy.   Is there a need to do that? Why can't the p2p part
be entirely separate from the comitted data?

On Mon, Nov 10, 2014 at 12:39 AM, Tier Nolan <tier.nolan@gmail.com> wrote:
> I made some changes to the draft.  The merkleblock now has the auxiliary
> header information too.
>
> There is a tradeoff between overhead and delayed transactions.  Is 12.5%
> transactions being delayed to the next block unacceptable?  Would adding
> padding transactions be an improvement?
>
> Creating the "seed" transactions is an implementation headache.
>
> Each node needs to have control over an UTXO to create the final transaction
> in the block that has the digest of the auxiliary header.  This means that
> it is not possible to simply start a node and have it mine.  It has to
> somehow be given the private key.  If two nodes were given the same key by
> accident, then one could end up blocking the other.
>
> On one end of the scale is adding a transaction with a few thousand outputs
> into the block chain.  The signatures for locktime restricted transactions
> that spend those outputs could be hard-coded into the software.  This is the
> easiest to implement, but would mean a large table of signatures.  The
> person who generates the signature list would have to be trusted not to
> spend the outputs early.
>
> The other end of the scale means that mining nodes need to include a wallets
> to manage their UTXO entry.  Miners can split a zero value output into lots
> of outputs, if they wish.
>
> A middle ground would be for nodes to be able to detect the special
> transactions and use them.  A server could send out timelocked transactions
> that pay to a particular address but the transaction would be timelocked.
> The private key for the output would be known.  However, miners who mine
> version 2 blocks wouldn't be able to spend them early.
>
>
> On Sat, Nov 8, 2014 at 11:45 PM, Tier Nolan <tier.nolan@gmail.com> wrote:
>>
>> I created a draft BIP detailing a way to add auxiliary headers to Bitcoin
>> in a bandwidth efficient way.  The overhead per auxiliary header is only
>> around 104 bytes per header.  This is much smaller than would be required by
>> embedding the hash of the header in the coinbase of the block.
>>
>> It is a soft fork and it uses the last transaction in the block to store
>> the hash of the auxiliary header.
>>
>> It makes use of the fact that the last transaction in the block has a much
>> less complex Merkle branch than the other transactions.
>>
>> https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki
>>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

Re: [Bitcoin-development] BIP draft - Auxiliary Header Format

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 4084 bytes --]

The aheaders message is required to make use of the data by SPV clients.
This could be in a separate BIP though.  I wanted to show that the merkle
path to the aux-header transaction could be efficiently encoded, but a
reference to the other BIP would be sufficient.

For the other messages, the problem is that the hash of the aux header is
part of the block, but the aux header itself is not.  That means that the
aux header has to be sent for validation of the block.

I will change it so that the entire aux-header is encoded in the block.  I
think encoding the hash in the final transaction and the full aux-header in
the 2nd last one is the best way to do it.  This has the added advantage of
reducing the changes to block data storage, since the aux-header doesn't
have to be stored separately.

On Mon, Nov 10, 2014 at 12:52 AM, Gregory Maxwell <gmaxwell@gmail.com>
wrote:

> Some initial comments...
>
> Tying in the protocol changes is really confusing and the fact that
> they seem to be required out the gates would seemingly make this much
> harder to deploy.   Is there a need to do that? Why can't the p2p part
> be entirely separate from the comitted data?
>
> On Mon, Nov 10, 2014 at 12:39 AM, Tier Nolan <tier.nolan@gmail.com> wrote:
> > I made some changes to the draft.  The merkleblock now has the auxiliary
> > header information too.
> >
> > There is a tradeoff between overhead and delayed transactions.  Is 12.5%
> > transactions being delayed to the next block unacceptable?  Would adding
> > padding transactions be an improvement?
> >
> > Creating the "seed" transactions is an implementation headache.
> >
> > Each node needs to have control over an UTXO to create the final
> transaction
> > in the block that has the digest of the auxiliary header.  This means
> that
> > it is not possible to simply start a node and have it mine.  It has to
> > somehow be given the private key.  If two nodes were given the same key
> by
> > accident, then one could end up blocking the other.
> >
> > On one end of the scale is adding a transaction with a few thousand
> outputs
> > into the block chain.  The signatures for locktime restricted
> transactions
> > that spend those outputs could be hard-coded into the software.  This is
> the
> > easiest to implement, but would mean a large table of signatures.  The
> > person who generates the signature list would have to be trusted not to
> > spend the outputs early.
> >
> > The other end of the scale means that mining nodes need to include a
> wallets
> > to manage their UTXO entry.  Miners can split a zero value output into
> lots
> > of outputs, if they wish.
> >
> > A middle ground would be for nodes to be able to detect the special
> > transactions and use them.  A server could send out timelocked
> transactions
> > that pay to a particular address but the transaction would be timelocked.
> > The private key for the output would be known.  However, miners who mine
> > version 2 blocks wouldn't be able to spend them early.
> >
> >
> > On Sat, Nov 8, 2014 at 11:45 PM, Tier Nolan <tier.nolan@gmail.com>
> wrote:
> >>
> >> I created a draft BIP detailing a way to add auxiliary headers to
> Bitcoin
> >> in a bandwidth efficient way.  The overhead per auxiliary header is only
> >> around 104 bytes per header.  This is much smaller than would be
> required by
> >> embedding the hash of the header in the coinbase of the block.
> >>
> >> It is a soft fork and it uses the last transaction in the block to store
> >> the hash of the auxiliary header.
> >>
> >> It makes use of the fact that the last transaction in the block has a
> much
> >> less complex Merkle branch than the other transactions.
> >>
> >>
> https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki
> >>
> >
> >
> >
> ------------------------------------------------------------------------------
> >
> > _______________________________________________
> > Bitcoin-development mailing list
> > Bitcoin-development@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> >
>

[-- Attachment #2: Type: text/html, Size: 5332 bytes --]

Re: [Bitcoin-development] BIP draft - Auxiliary Header Format

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 4424 bytes --]

I updated the BIP to cover only the specification of the transactions that
need to be added.  I will create a network BIP tomorrow.

On Mon, Nov 10, 2014 at 11:42 AM, Tier Nolan <tier.nolan@gmail.com> wrote:

> The aheaders message is required to make use of the data by SPV clients.
> This could be in a separate BIP though.  I wanted to show that the merkle
> path to the aux-header transaction could be efficiently encoded, but a
> reference to the other BIP would be sufficient.
>
> For the other messages, the problem is that the hash of the aux header is
> part of the block, but the aux header itself is not.  That means that the
> aux header has to be sent for validation of the block.
>
> I will change it so that the entire aux-header is encoded in the block.  I
> think encoding the hash in the final transaction and the full aux-header in
> the 2nd last one is the best way to do it.  This has the added advantage of
> reducing the changes to block data storage, since the aux-header doesn't
> have to be stored separately.
>
>
> On Mon, Nov 10, 2014 at 12:52 AM, Gregory Maxwell <gmaxwell@gmail.com>
> wrote:
>
>> Some initial comments...
>>
>> Tying in the protocol changes is really confusing and the fact that
>> they seem to be required out the gates would seemingly make this much
>> harder to deploy.   Is there a need to do that? Why can't the p2p part
>> be entirely separate from the comitted data?
>>
>> On Mon, Nov 10, 2014 at 12:39 AM, Tier Nolan <tier.nolan@gmail.com>
>> wrote:
>> > I made some changes to the draft.  The merkleblock now has the auxiliary
>> > header information too.
>> >
>> > There is a tradeoff between overhead and delayed transactions.  Is 12.5%
>> > transactions being delayed to the next block unacceptable?  Would adding
>> > padding transactions be an improvement?
>> >
>> > Creating the "seed" transactions is an implementation headache.
>> >
>> > Each node needs to have control over an UTXO to create the final
>> transaction
>> > in the block that has the digest of the auxiliary header.  This means
>> that
>> > it is not possible to simply start a node and have it mine.  It has to
>> > somehow be given the private key.  If two nodes were given the same key
>> by
>> > accident, then one could end up blocking the other.
>> >
>> > On one end of the scale is adding a transaction with a few thousand
>> outputs
>> > into the block chain.  The signatures for locktime restricted
>> transactions
>> > that spend those outputs could be hard-coded into the software.  This
>> is the
>> > easiest to implement, but would mean a large table of signatures.  The
>> > person who generates the signature list would have to be trusted not to
>> > spend the outputs early.
>> >
>> > The other end of the scale means that mining nodes need to include a
>> wallets
>> > to manage their UTXO entry.  Miners can split a zero value output into
>> lots
>> > of outputs, if they wish.
>> >
>> > A middle ground would be for nodes to be able to detect the special
>> > transactions and use them.  A server could send out timelocked
>> transactions
>> > that pay to a particular address but the transaction would be
>> timelocked.
>> > The private key for the output would be known.  However, miners who mine
>> > version 2 blocks wouldn't be able to spend them early.
>> >
>> >
>> > On Sat, Nov 8, 2014 at 11:45 PM, Tier Nolan <tier.nolan@gmail.com>
>> wrote:
>> >>
>> >> I created a draft BIP detailing a way to add auxiliary headers to
>> Bitcoin
>> >> in a bandwidth efficient way.  The overhead per auxiliary header is
>> only
>> >> around 104 bytes per header.  This is much smaller than would be
>> required by
>> >> embedding the hash of the header in the coinbase of the block.
>> >>
>> >> It is a soft fork and it uses the last transaction in the block to
>> store
>> >> the hash of the auxiliary header.
>> >>
>> >> It makes use of the fact that the last transaction in the block has a
>> much
>> >> less complex Merkle branch than the other transactions.
>> >>
>> >>
>> https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki
>> >>
>> >
>> >
>> >
>> ------------------------------------------------------------------------------
>> >
>> > _______________________________________________
>> > Bitcoin-development mailing list
>> > Bitcoin-development@lists.sourceforge.net
>> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>> >
>>
>
>

[-- Attachment #2: Type: text/html, Size: 5874 bytes --]

Re: [Bitcoin-development] BIP draft - Auxiliary Header Format

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 4938 bytes --]

I have added the network BIP too.  It only has the aheaders message and the
extra field for getheaders.

https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header-network.mediawiki

The transaction definitions are still at:

https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki

On Mon, Nov 10, 2014 at 9:21 PM, Tier Nolan <tier.nolan@gmail.com> wrote:

> I updated the BIP to cover only the specification of the transactions that
> need to be added.  I will create a network BIP tomorrow.
>
> On Mon, Nov 10, 2014 at 11:42 AM, Tier Nolan <tier.nolan@gmail.com> wrote:
>
>> The aheaders message is required to make use of the data by SPV clients.
>> This could be in a separate BIP though.  I wanted to show that the merkle
>> path to the aux-header transaction could be efficiently encoded, but a
>> reference to the other BIP would be sufficient.
>>
>> For the other messages, the problem is that the hash of the aux header is
>> part of the block, but the aux header itself is not.  That means that the
>> aux header has to be sent for validation of the block.
>>
>> I will change it so that the entire aux-header is encoded in the block.
>> I think encoding the hash in the final transaction and the full aux-header
>> in the 2nd last one is the best way to do it.  This has the added advantage
>> of reducing the changes to block data storage, since the aux-header doesn't
>> have to be stored separately.
>>
>>
>> On Mon, Nov 10, 2014 at 12:52 AM, Gregory Maxwell <gmaxwell@gmail.com>
>> wrote:
>>
>>> Some initial comments...
>>>
>>> Tying in the protocol changes is really confusing and the fact that
>>> they seem to be required out the gates would seemingly make this much
>>> harder to deploy.   Is there a need to do that? Why can't the p2p part
>>> be entirely separate from the comitted data?
>>>
>>> On Mon, Nov 10, 2014 at 12:39 AM, Tier Nolan <tier.nolan@gmail.com>
>>> wrote:
>>> > I made some changes to the draft.  The merkleblock now has the
>>> auxiliary
>>> > header information too.
>>> >
>>> > There is a tradeoff between overhead and delayed transactions.  Is
>>> 12.5%
>>> > transactions being delayed to the next block unacceptable?  Would
>>> adding
>>> > padding transactions be an improvement?
>>> >
>>> > Creating the "seed" transactions is an implementation headache.
>>> >
>>> > Each node needs to have control over an UTXO to create the final
>>> transaction
>>> > in the block that has the digest of the auxiliary header.  This means
>>> that
>>> > it is not possible to simply start a node and have it mine.  It has to
>>> > somehow be given the private key.  If two nodes were given the same
>>> key by
>>> > accident, then one could end up blocking the other.
>>> >
>>> > On one end of the scale is adding a transaction with a few thousand
>>> outputs
>>> > into the block chain.  The signatures for locktime restricted
>>> transactions
>>> > that spend those outputs could be hard-coded into the software.  This
>>> is the
>>> > easiest to implement, but would mean a large table of signatures.  The
>>> > person who generates the signature list would have to be trusted not to
>>> > spend the outputs early.
>>> >
>>> > The other end of the scale means that mining nodes need to include a
>>> wallets
>>> > to manage their UTXO entry.  Miners can split a zero value output into
>>> lots
>>> > of outputs, if they wish.
>>> >
>>> > A middle ground would be for nodes to be able to detect the special
>>> > transactions and use them.  A server could send out timelocked
>>> transactions
>>> > that pay to a particular address but the transaction would be
>>> timelocked.
>>> > The private key for the output would be known.  However, miners who
>>> mine
>>> > version 2 blocks wouldn't be able to spend them early.
>>> >
>>> >
>>> > On Sat, Nov 8, 2014 at 11:45 PM, Tier Nolan <tier.nolan@gmail.com>
>>> wrote:
>>> >>
>>> >> I created a draft BIP detailing a way to add auxiliary headers to
>>> Bitcoin
>>> >> in a bandwidth efficient way.  The overhead per auxiliary header is
>>> only
>>> >> around 104 bytes per header.  This is much smaller than would be
>>> required by
>>> >> embedding the hash of the header in the coinbase of the block.
>>> >>
>>> >> It is a soft fork and it uses the last transaction in the block to
>>> store
>>> >> the hash of the auxiliary header.
>>> >>
>>> >> It makes use of the fact that the last transaction in the block has a
>>> much
>>> >> less complex Merkle branch than the other transactions.
>>> >>
>>> >>
>>> https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki
>>> >>
>>> >
>>> >
>>> >
>>> ------------------------------------------------------------------------------
>>> >
>>> > _______________________________________________
>>> > Bitcoin-development mailing list
>>> > Bitcoin-development@lists.sourceforge.net
>>> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>>> >
>>>
>>
>>
>

[-- Attachment #2: Type: text/html, Size: 6798 bytes --]

Re: [Bitcoin-development] BIP draft - Auxiliary Header Format

[Tier Nolan]

[-- Attachment #1: Type: text/plain, Size: 5713 bytes --]

I was going to look into creating reference code for this.

The first BIP could be reasonably easy, since it just needs to check for
the presence of the 2 special transactions.

That would mean that it doesn't actually create version 3 blocks at all.

Ideally, I would make it easy for miners to mine version 3 blocks.  I could
add a new field to the getblocktemplate that has the 2 transactions ready
to go.

What do pools actually use for generating blocks.  I assume it's custom
code but that they use (near) standard software for the memory pool?


On Mon, Nov 10, 2014 at 11:39 PM, Tier Nolan <tier.nolan@gmail.com> wrote:

> I have added the network BIP too.  It only has the aheaders message and
> the extra field for getheaders.
>
>
> https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header-network.mediawiki
>
> The transaction definitions are still at:
>
> https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki
>
> On Mon, Nov 10, 2014 at 9:21 PM, Tier Nolan <tier.nolan@gmail.com> wrote:
>
>> I updated the BIP to cover only the specification of the transactions
>> that need to be added.  I will create a network BIP tomorrow.
>>
>> On Mon, Nov 10, 2014 at 11:42 AM, Tier Nolan <tier.nolan@gmail.com>
>> wrote:
>>
>>> The aheaders message is required to make use of the data by SPV
>>> clients.  This could be in a separate BIP though.  I wanted to show that
>>> the merkle path to the aux-header transaction could be efficiently encoded,
>>> but a reference to the other BIP would be sufficient.
>>>
>>> For the other messages, the problem is that the hash of the aux header
>>> is part of the block, but the aux header itself is not.  That means that
>>> the aux header has to be sent for validation of the block.
>>>
>>> I will change it so that the entire aux-header is encoded in the block.
>>> I think encoding the hash in the final transaction and the full aux-header
>>> in the 2nd last one is the best way to do it.  This has the added advantage
>>> of reducing the changes to block data storage, since the aux-header doesn't
>>> have to be stored separately.
>>>
>>>
>>> On Mon, Nov 10, 2014 at 12:52 AM, Gregory Maxwell <gmaxwell@gmail.com>
>>> wrote:
>>>
>>>> Some initial comments...
>>>>
>>>> Tying in the protocol changes is really confusing and the fact that
>>>> they seem to be required out the gates would seemingly make this much
>>>> harder to deploy.   Is there a need to do that? Why can't the p2p part
>>>> be entirely separate from the comitted data?
>>>>
>>>> On Mon, Nov 10, 2014 at 12:39 AM, Tier Nolan <tier.nolan@gmail.com>
>>>> wrote:
>>>> > I made some changes to the draft.  The merkleblock now has the
>>>> auxiliary
>>>> > header information too.
>>>> >
>>>> > There is a tradeoff between overhead and delayed transactions.  Is
>>>> 12.5%
>>>> > transactions being delayed to the next block unacceptable?  Would
>>>> adding
>>>> > padding transactions be an improvement?
>>>> >
>>>> > Creating the "seed" transactions is an implementation headache.
>>>> >
>>>> > Each node needs to have control over an UTXO to create the final
>>>> transaction
>>>> > in the block that has the digest of the auxiliary header.  This means
>>>> that
>>>> > it is not possible to simply start a node and have it mine.  It has to
>>>> > somehow be given the private key.  If two nodes were given the same
>>>> key by
>>>> > accident, then one could end up blocking the other.
>>>> >
>>>> > On one end of the scale is adding a transaction with a few thousand
>>>> outputs
>>>> > into the block chain.  The signatures for locktime restricted
>>>> transactions
>>>> > that spend those outputs could be hard-coded into the software.  This
>>>> is the
>>>> > easiest to implement, but would mean a large table of signatures.  The
>>>> > person who generates the signature list would have to be trusted not
>>>> to
>>>> > spend the outputs early.
>>>> >
>>>> > The other end of the scale means that mining nodes need to include a
>>>> wallets
>>>> > to manage their UTXO entry.  Miners can split a zero value output
>>>> into lots
>>>> > of outputs, if they wish.
>>>> >
>>>> > A middle ground would be for nodes to be able to detect the special
>>>> > transactions and use them.  A server could send out timelocked
>>>> transactions
>>>> > that pay to a particular address but the transaction would be
>>>> timelocked.
>>>> > The private key for the output would be known.  However, miners who
>>>> mine
>>>> > version 2 blocks wouldn't be able to spend them early.
>>>> >
>>>> >
>>>> > On Sat, Nov 8, 2014 at 11:45 PM, Tier Nolan <tier.nolan@gmail.com>
>>>> wrote:
>>>> >>
>>>> >> I created a draft BIP detailing a way to add auxiliary headers to
>>>> Bitcoin
>>>> >> in a bandwidth efficient way.  The overhead per auxiliary header is
>>>> only
>>>> >> around 104 bytes per header.  This is much smaller than would be
>>>> required by
>>>> >> embedding the hash of the header in the coinbase of the block.
>>>> >>
>>>> >> It is a soft fork and it uses the last transaction in the block to
>>>> store
>>>> >> the hash of the auxiliary header.
>>>> >>
>>>> >> It makes use of the fact that the last transaction in the block has
>>>> a much
>>>> >> less complex Merkle branch than the other transactions.
>>>> >>
>>>> >>
>>>> https://github.com/TierNolan/bips/blob/aux_header/bip-aux-header.mediawiki
>>>> >>
>>>> >
>>>> >
>>>> >
>>>> ------------------------------------------------------------------------------
>>>> >
>>>> > _______________________________________________
>>>> > Bitcoin-development mailing list
>>>> > Bitcoin-development@lists.sourceforge.net
>>>> > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>>>> >
>>>>
>>>
>>>
>>
>

[-- Attachment #2: Type: text/html, Size: 7883 bytes --]