Re: [bitcoin-dev] Compact Block Relay BIP

[Gregory Maxwell via bitcoin-dev]

On Tue, May 10, 2016 at 5:28 AM, Rusty Russell via bitcoin-dev
 wrote:
> I used variable-length bit encodings, and used the shortest encoding
> which is unique to you (including mempool).  It's a little more work,
> but for an average node transmitting a block with 1300 txs and another
> ~3000 in the mempool, you expect about 12 bits per transaction.  IOW,
> about 1/5 of your current size.  Critically, we might be able to fit in
> two or three TCP packets.

Hm. 12 bits sounds very small even giving those figures. Why failure
rate were you targeting?

I've mostly been thing in terms of 3000 txn, and 20k mempools, and
blocks which are 90% consistent with the remote mempool, targeting
1/10 failure rates (which is roughly where it should be to put it
well below link failure levels).

If going down the path of more complexity, set reconciliation is
enormously more efficient (e.g. 90% reduction), which no amount of
packing/twiddling can achieve.

But the savings of going from 20kb to 3kb is not interesting enough to
justify it*.  My expectation is that later we'll deploy set
reconciliation to fix relay efficiency, where the savings is _much_
larger,  and then with the infrastructure in place we could define
another compactblock mode that used it.

(*Not interesting because it mostly reduces exposure to loss and the
gods of TCP, but since those are the long poles in the latency tent,
it's best to escape them entirely, see Matt's udp_wip branch.)

> I would also avoid the nonce to save recalculating for each node, and
> instead define an id as:

Doing this would greatly increase the cost of a collision though, as
it would happen in many places in the network at once over the on the
network at once, rather than just happening on a single link, thus
hardly impacting overall propagation.

(The downside of the nonce is that you get an exponential increase in
the rate that a collision happens "somewhere", but links fail
"somewhere" all the time-- propagation overall doesn't care about
that.)

Using the same nonce means you also would not get a recovery gain from
jointly decoding using compact blocks sent from multiple peers (which
you'll have anyways in high bandwidth mode).

With a nonce a sender does have the option of reusing what they got--
but the actual encoding cost is negligible, for a 2500 transaction
block its 27 microseconds (once per block, shared across all peers)
using Pieter's suggestion of siphash 1-3 instead of the cheaper
construct in the current draft.

Of course, if you're going to check your whole mempool to reroll the
nonce, thats another matter-- but that seems wasteful compared to just
using a table driven size with a known negligible failure rate.

64-bits as a maximum length is high enough that the collision rate
would be negligible even under fairly unrealistic assumptions-- so
long as it's salted. :)

> As Peter R points out, we could later enhance receiver to brute force
> collisions (you could speed that by sending a XOR of all the txids, but
> really if there are more than a few collisions, give up).

The band between "no collisions" and "infeasible many" is fairly
narrow.  You can add a small amount more space to the ids and
immediately be in the no collision zone.

Some earlier work we had would send small amount of erasure coding
data of the next couple bytes of the IDs.  E.g. the receiver in all
the IDs you know, mark totally unknown IDs as erased and the let the
error correction fix the rest. This let you algebraically resolve
collisions _far_ beyond what could be feasibly bruteforced. Pieter
went and implemented... but the added cost of encoding and software
complexity seem not worth it.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] Making AsicBoost irrelevant

[Peter Todd via bitcoin-dev]

As part of the hard-fork proposed in the HK agreement(1) we'd like to make the
patented AsicBoost optimisation useless, and hopefully make further similar
optimizations useless as well.

What's the best way to do this? Ideally this would be SPV compatible, but if it
requires changes from SPV clients that's ok too. Also the fix this should be
compatible with existing mining hardware.


1) 
https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff

2) http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making AsicBoost irrelevant

[Tier Nolan via bitcoin-dev]

The various chunks in the double SHA256 are

Chunk 1: 64 bytes
version
previous_block_digest
merkle_root[31:4]

Chunk 2: 64 bytes
merkle_root[3:0]
nonce
timestamp
target

Chunk 3: 64 bytes
digest from first sha pass

Their improvement requires that all data in Chunk 2 is identical except for
the nonce.  With 4 bytes, the birthday paradox means collisions can be
found reasonable easily.

If hard forks are allowed, then moving more of the merkle root into the 2nd
chunk would make things harder.  The timestamp and target could be moved
into chunk 1.  This increases the merkle root to 12 bytes in the 2nd
chunk.  Finding collisions would be made much more difficult.

If ASIC limitations mean that the nonce must stay where it is, this would
mean that the merkle root would be split into two pieces.

On Tue, May 10, 2016 at 7:57 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As part of the hard-fork proposed in the HK agreement(1) we'd like to make
> the
> patented AsicBoost optimisation useless, and hopefully make further similar
> optimizations useless as well.
>
> What's the best way to do this? Ideally this would be SPV compatible, but
> if it
> requires changes from SPV clients that's ok too. Also the fix this should
> be
> compatible with existing mining hardware.
>
>
> 1)
> https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff
>
> 2)
> http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making AsicBoost irrelevant

[Matt Corallo via bitcoin-dev]

Yea, I think in any hardfork that we should be talking about, a part of
it should include 1) fix the version field so its a static constant, 2)
the merkle root becomes hash of the real block header 3) swap first 2
bytes of the merkle root with the timestamp's two high-order bits, 4)
swap the next 4 bytes of the merkle root with the difficulty field.

I believe this should be compatible with all existing ASICs, with the
exception, possibly, of some 21 Inc hardware. I believe this fixes
AsicBoost (without thinking about it tooo much, so please critique).

While this is somewhat nasty, the risks of AsicBoost and the precedent
that should be set necessitates a response, and it should be included in
any hardfork.

Matt

On 05/10/16 20:27, Tier Nolan via bitcoin-dev wrote:
> The various chunks in the double SHA256 are
> 
> Chunk 1: 64 bytes
> version
> previous_block_digest
> merkle_root[31:4]
> 
> Chunk 2: 64 bytes
> merkle_root[3:0]
> nonce
> timestamp
> target
> 
> Chunk 3: 64 bytes
> digest from first sha pass
> 
> Their improvement requires that all data in Chunk 2 is identical except
> for the nonce.  With 4 bytes, the birthday paradox means collisions can
> be found reasonable easily.
> 
> If hard forks are allowed, then moving more of the merkle root into the
> 2nd chunk would make things harder.  The timestamp and target could be
> moved into chunk 1.  This increases the merkle root to 12 bytes in the
> 2nd chunk.  Finding collisions would be made much more difficult.
> 
> If ASIC limitations mean that the nonce must stay where it is, this
> would mean that the merkle root would be split into two pieces.
> 
> On Tue, May 10, 2016 at 7:57 PM, Peter Todd via bitcoin-dev
>  > wrote:
> 
> As part of the hard-fork proposed in the HK agreement(1) we'd like
> to make the
> patented AsicBoost optimisation useless, and hopefully make further
> similar
> optimizations useless as well.
> 
> What's the best way to do this? Ideally this would be SPV
> compatible, but if it
> requires changes from SPV clients that's ok too. Also the fix this
> should be
> compatible with existing mining hardware.
> 
> 
> 1)
> 
> https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff
> 
> 2)
> 
> http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html
> 
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> 
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 
> 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making AsicBoost irrelevant

[Sergio Demian Lerner via bitcoin-dev]

Your idea of moving the Merkle root to the second chunk does not work.

The AsicBoost can change the version bits and it does not need to find a
collision.
(However *Spondoolies patent *only mentions Merkle collisions:
https://patentscope.wipo.int/search/docservicepdf_pct/id0032873338/PAMPH/WO2016046820.pdf
)

Back in 2014 I designed a ASIC-compatible block header that prevents
AsicBoost in all its forms.

You can find it here:
https://bitslog.wordpress.com/2014/03/18/the-re-design-of-the-bitcoin-block-header/

Basically, the idea is to put in the first 64 bytes a 4 byte hash of the
second 64-byte chunk. That design also allows increased nonce space in the
first 64 bytes.

But it you want to do a simpler change, you can more easily use the first
32 bits of the Parent Block Hash (now currently zero) to store the first 4
bytes of the SHA256 of the last 16 bytes of the header. That way to "tie"
the two header chunks. It's a minimal change (but a hard-fork)

But some ASIC companies already have cores that are better (on power, cost,
rate, temperature, etc.) than competing companies ASICs. Why do you think a
10% improvement from AsicBoost is different from many of other improvements
they already have (secretly) added? Maybe we (?) should only allow ASICs
that have a 100% open source designs?

If we change the protocol then the message to the ecosystem is that ASIC
optimizations should be kept secret. It is fair to change the protocol
because we don't like that certain ASIC manufacturer has better chips, if
the chips are sold in the market and anyone can buy them? And what about
using approximate adders (30% improvement), or dual rail asynchronous
adders (also more than 10% improvement) ? How do we repair those?

Disclaimer: I have stake in AsicBoost, but I'm not sure about this.


On Tue, May 10, 2016 at 5:27 PM, Tier Nolan via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> The various chunks in the double SHA256 are
>
> Chunk 1: 64 bytes
> version
> previous_block_digest
> merkle_root[31:4]
>
> Chunk 2: 64 bytes
> merkle_root[3:0]
> nonce
> timestamp
> target
>
> Chunk 3: 64 bytes
> digest from first sha pass
>
> Their improvement requires that all data in Chunk 2 is identical except
> for the nonce.  With 4 bytes, the birthday paradox means collisions can be
> found reasonable easily.
>
> If hard forks are allowed, then moving more of the merkle root into the
> 2nd chunk would make things harder.  The timestamp and target could be
> moved into chunk 1.  This increases the merkle root to 12 bytes in the 2nd
> chunk.  Finding collisions would be made much more difficult.
>
> If ASIC limitations mean that the nonce must stay where it is, this would
> mean that the merkle root would be split into two pieces.
>
> On Tue, May 10, 2016 at 7:57 PM, Peter Todd via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> As part of the hard-fork proposed in the HK agreement(1) we'd like to
>> make the
>> patented AsicBoost optimisation useless, and hopefully make further
>> similar
>> optimizations useless as well.
>>
>> What's the best way to do this? Ideally this would be SPV compatible, but
>> if it
>> requires changes from SPV clients that's ok too. Also the fix this should
>> be
>> compatible with existing mining hardware.
>>
>>
>> 1)
>> https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff
>>
>> 2)
>> http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html
>>
>> --
>> https://petertodd.org 'peter'[:-1]@petertodd.org
>>
>> ___
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making AsicBoost irrelevant

[Marco Pontello via bitcoin-dev]

On Tue, May 10, 2016 at 8:57 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As part of the hard-fork proposed in the HK agreement(1) we'd like to make
> the
> patented AsicBoost optimisation useless, and hopefully make further similar
> optimizations useless as well.
>

Just in the interest of clarity, I think you should clarify who you are
including in the "we".

Bye!
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making AsicBoost irrelevant

[Sergio Demian Lerner via bitcoin-dev]

On Tue, May 10, 2016 at 3:57 PM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As part of the hard-fork proposed in the HK agreement(1) we'd like to make
> the
> patented AsicBoost optimisation useless, and hopefully make further similar
> optimizations useless as well.
>
>
> You say that you want to make patented optimization useless, but you point
to a link that doesn't say anything about ASIC improvements or patents,
which means that you have been planning to change the protocol rules with
some miners (but not all the community).

All changes to the protocol should be discussed in public here. If you want
to make "further similar optimizations useless as well" then maybe you
should propose a switch to EquiHash.



>
> 1)
> https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff
>
> 2)
> http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making AsicBoost irrelevant

[Chris Riley via bitcoin-dev]

The second like "2)" has a link to the paper:
http://www.math.rwth-aachen.de/~Timo.Hanke/AsicBoostWhitepaperrev5.pdf

which does discuss the fact that it is "patent-pending".   Likewise it
discusses ASIC improvements.  Avoiding patents that impact bitcoin and are
not freely licensed, is something that is worthwhile for discussion.


On Tue, May 10, 2016 at 6:17 PM, Sergio Demian Lerner via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
>
> On Tue, May 10, 2016 at 3:57 PM, Peter Todd via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> As part of the hard-fork proposed in the HK agreement(1) we'd like to
>> make the
>> patented AsicBoost optimisation useless, and hopefully make further
>> similar
>> optimizations useless as well.
>>
>>
>> You say that you want to make patented optimization useless, but you
> point to a link that doesn't say anything about ASIC improvements or
> patents, which means that you have been planning to change the protocol
> rules with some miners (but not all the community).
>

> All changes to the protocol should be discussed in public here. If you
> want to make "further similar optimizations useless as well" then maybe you
> should propose a switch to EquiHash.
>
>
>
>>
>> 1)
>> https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff
>>
>> 2)
>> http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html
>>
>> --
>> https://petertodd.org 'peter'[:-1]@petertodd.org
>>
>> ___
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Making AsicBoost irrelevant

[Matt Corallo via bitcoin-dev]

Replies inline.

On 05/10/16 21:43, Sergio Demian Lerner via bitcoin-dev wrote:
-snip-

> But some ASIC companies already have cores that are better (on power,
> cost, rate, temperature, etc.) than competing companies ASICs. Why do
> you think a 10% improvement from AsicBoost is different from many of
> other improvements they already have (secretly) added? Maybe we (?)
> should only allow ASICs that have a 100% open source designs?

One is patented and requires paying a license fee to a group, or more
likely, ends up with it being impossible to import hardware from other
jurisdictions into the US/western world. The other requires more
investment in R&D, and over the long run, there is no guaranteed
advantage to such groups.

> If we change the protocol then the message to the ecosystem is that ASIC
> optimizations should be kept secret.

To some extent, this is the case, but there is a strong difference
between a guaranteed advantage enforced by the legal system and one that
is true due to intellectual superiority. In the long run, I am confident
the second will not remain the case. For example, AsicBoost was
independently discovered by at least two companies/individuals within a
year or two.

> It is fair to change the protocol
> because we don't like that certain ASIC manufacturer has better chips,
> if the chips are sold in the market and anyone can buy them? And what
> about using approximate adders (30% improvement), or dual rail
> asynchronous adders (also more than 10% improvement) ? How do we repair
> those?

As far as I'm aware neither of these are patented. Is this not the case?

> Disclaimer: I have stake in AsicBoost, but I'm not sure about this.
>  
> 
> On Tue, May 10, 2016 at 5:27 PM, Tier Nolan via bitcoin-dev
>  > wrote:
> 
> The various chunks in the double SHA256 are
> 
> Chunk 1: 64 bytes
> version
> previous_block_digest
> merkle_root[31:4]
> 
> Chunk 2: 64 bytes
> merkle_root[3:0]
> nonce
> timestamp
> target
> 
> Chunk 3: 64 bytes
> digest from first sha pass
> 
> Their improvement requires that all data in Chunk 2 is identical
> except for the nonce.  With 4 bytes, the birthday paradox means
> collisions can be found reasonable easily.
> 
> If hard forks are allowed, then moving more of the merkle root into
> the 2nd chunk would make things harder.  The timestamp and target
> could be moved into chunk 1.  This increases the merkle root to 12
> bytes in the 2nd chunk.  Finding collisions would be made much more
> difficult.
> 
> If ASIC limitations mean that the nonce must stay where it is, this
> would mean that the merkle root would be split into two pieces.
> 
> On Tue, May 10, 2016 at 7:57 PM, Peter Todd via bitcoin-dev
>  > wrote:
> 
> As part of the hard-fork proposed in the HK agreement(1) we'd
> like to make the
> patented AsicBoost optimisation useless, and hopefully make
> further similar
> optimizations useless as well.
> 
> What's the best way to do this? Ideally this would be SPV
> compatible, but if it
> requires changes from SPV clients that's ok too. Also the fix
> this should be
> compatible with existing mining hardware.
> 
> 
> 1)
> 
> https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff
> 
> 2)
> 
> http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html
> 
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
> 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> 
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> 
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 
> 
> 
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Compact Block Relay BIP

[Rusty Russell via bitcoin-dev]

Gregory Maxwell  writes:
> On Tue, May 10, 2016 at 5:28 AM, Rusty Russell via bitcoin-dev
>  wrote:
>> I used variable-length bit encodings, and used the shortest encoding
>> which is unique to you (including mempool).  It's a little more work,
>> but for an average node transmitting a block with 1300 txs and another
>> ~3000 in the mempool, you expect about 12 bits per transaction.  IOW,
>> about 1/5 of your current size.  Critically, we might be able to fit in
>> two or three TCP packets.
>
> Hm. 12 bits sounds very small even giving those figures. Why failure
> rate were you targeting?

That's a good question; I was assuming a best-case in which we have
mempool set reconciliation (handwave) thus know they are close.  But
there's also an alterior motive: any later more sophisticated approach
will want variable-length IDs, and I'd like Matt to do the work :)

In particular, you can significantly narrow the possibilities for a
block by sending the min-fee-per-kb and a list of "txs in my mempool
which didn't get in" and "txs which did despite not making the
fee-per-kb".  Those turn out to be tiny, and often make set
reconciliation trivial.  That's best done with variable-length IDs.

> (*Not interesting because it mostly reduces exposure to loss and the
> gods of TCP, but since those are the long poles in the latency tent,
> it's best to escape them entirely, see Matt's udp_wip branch.)

I'm not convinced on UDP; it always looks impressive, but then ends up
reimplementing TCP in practice.  We should be well within a TCP window
for these, so it's hard to see where we'd win.

>> I would also avoid the nonce to save recalculating for each node, and
>> instead define an id as:
>
> Doing this would greatly increase the cost of a collision though, as
> it would happen in many places in the network at once over the on the
> network at once, rather than just happening on a single link, thus
> hardly impacting overall propagation.

"Greatly increase"?  I don't see that.

Let's assume an attacker grinds out 10,000 txs with 128 bits of the same
TXID, and gets them all in a block.  They then win the lottery and get a
collision.  Now we have to transmit ~48 bytes more than expected.

> Using the same nonce means you also would not get a recovery gain from
> jointly decoding using compact blocks sent from multiple peers (which
> you'll have anyways in high bandwidth mode).

Not quite true, since if their mempools differ they'll use different
encoding lengths, but yes, you'll get less of this.

> With a nonce a sender does have the option of reusing what they got--
> but the actual encoding cost is negligible, for a 2500 transaction
> block its 27 microseconds (once per block, shared across all peers)
> using Pieter's suggestion of siphash 1-3 instead of the cheaper
> construct in the current draft.
>
> Of course, if you're going to check your whole mempool to reroll the
> nonce, thats another matter-- but that seems wasteful compared to just
> using a table driven size with a known negligible failure rate.

I'm not worried about the sender: The recipient needs to encode all the
mempool.

>> As Peter R points out, we could later enhance receiver to brute force
>> collisions (you could speed that by sending a XOR of all the txids, but
>> really if there are more than a few collisions, give up).
>
> The band between "no collisions" and "infeasible many" is fairly
> narrow.  You can add a small amount more space to the ids and
> immediately be in the no collision zone.

Indeed, I would be adding extra bits in the sender and not implementing
brute force in the receiver.  But I welcome someone else to do so.

Cheers,
Rusty.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Compact Block Relay BIP

[Matt Corallo via bitcoin-dev]

Replies inline.

On May 10, 2016 5:23:55 PM EDT, Rusty Russell via bitcoin-dev 
 wrote:
>Gregory Maxwell  writes:
>> On Tue, May 10, 2016 at 5:28 AM, Rusty Russell via bitcoin-dev
>>  wrote:
>>> I used variable-length bit encodings, and used the shortest encoding
>>> which is unique to you (including mempool).  It's a little more
>work,
>>> but for an average node transmitting a block with 1300 txs and
>another
>>> ~3000 in the mempool, you expect about 12 bits per transaction. 
>IOW,
>>> about 1/5 of your current size.  Critically, we might be able to fit
>in
>>> two or three TCP packets.
>>
>> Hm. 12 bits sounds very small even giving those figures. Why failure
>> rate were you targeting?
>
>That's a good question; I was assuming a best-case in which we have
>mempool set reconciliation (handwave) thus know they are close.  But
>there's also an alterior motive: any later more sophisticated approach
>will want variable-length IDs, and I'd like Matt to do the work :)

Yea, there's already an ongoing discussion of that, and the UDP stuff will 
definitely want something different than the current proposals.

>In particular, you can significantly narrow the possibilities for a
>block by sending the min-fee-per-kb and a list of "txs in my mempool
>which didn't get in" and "txs which did despite not making the
>fee-per-kb".  Those turn out to be tiny, and often make set
>reconciliation trivial.  That's best done with variable-length IDs.
>
>> (*Not interesting because it mostly reduces exposure to loss and the
>> gods of TCP, but since those are the long poles in the latency tent,
>> it's best to escape them entirely, see Matt's udp_wip branch.)
>
>I'm not convinced on UDP; it always looks impressive, but then ends up
>reimplementing TCP in practice.  We should be well within a TCP window
>for these, so it's hard to see where we'd win.

Not at all. The goal with the UDP stuff I've been working on is not to provide 
reliable transport. Like the relay network, it is assumed some percent of 
blocks will fail to transit properly, and you will use some other transport to 
figure out how to get the block. Indeed, a big part of my desire for diversity 
in network protocols is to enable them to make tradeoffs in 
reliability/privacy/etc.

>>> I would also avoid the nonce to save recalculating for each node,
>and
>>> instead define an id as:
>>
>> Doing this would greatly increase the cost of a collision though, as
>> it would happen in many places in the network at once over the on the
>> network at once, rather than just happening on a single link, thus
>> hardly impacting overall propagation.
>
>"Greatly increase"?  I don't see that.
>
>Let's assume an attacker grinds out 10,000 txs with 128 bits of the
>same
>TXID, and gets them all in a block.  They then win the lottery and get
>a
>collision.  Now we have to transmit ~48 bytes more than expected.

I assume what Greg was referring to the idea that if there is a conflict, a 
given block will require an extra round trip when being broadcast between 
roughly each peer, compounding the effect across each hop.

>> Using the same nonce means you also would not get a recovery gain
>from
>> jointly decoding using compact blocks sent from multiple peers (which
>> you'll have anyways in high bandwidth mode).
>
>Not quite true, since if their mempools differ they'll use different
>encoding lengths, but yes, you'll get less of this.

... Assuming different encoding lengths aren't just truncated, but ok :).

>> With a nonce a sender does have the option of reusing what they got--
>> but the actual encoding cost is negligible, for a 2500 transaction
>> block its 27 microseconds (once per block, shared across all peers)
>> using Pieter's suggestion of siphash 1-3 instead of the cheaper
>> construct in the current draft.
>>
>> Of course, if you're going to check your whole mempool to reroll the
>> nonce, thats another matter-- but that seems wasteful compared to
>just
>> using a table driven size with a known negligible failure rate.
>
>I'm not worried about the sender: The recipient needs to encode all the
>mempool.
>
>>> As Peter R points out, we could later enhance receiver to brute
>force
>>> collisions (you could speed that by sending a XOR of all the txids,
>but
>>> really if there are more than a few collisions, give up).
>>
>> The band between "no collisions" and "infeasible many" is fairly
>> narrow.  You can add a small amount more space to the ids and
>> immediately be in the no collision zone.
>
>Indeed, I would be adding extra bits in the sender and not implementing
>brute force in the receiver.  But I welcome someone else to do so.
>
>Cheers,
>Rusty.
>___
>bitcoin-dev mailing list
>bitcoin-dev@lists.linuxfoundation.org
>https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/

Re: [bitcoin-dev] Making AsicBoost irrelevant

[Timo Hanke via bitcoin-dev]

There is no way to tell from a block if it was mined with AsicBoost or not.
So you don’t know what percentage of the hashrate uses AsicBoost at any
point in time. How can you risk forking that percentage out? Note that this
would be a GUARANTEED chain fork. Meaning that after you change the block
mining algorithm some percentage of hardware will no longer be able to
produce valid blocks. That hardware cannot “switch over” to the majority
chain even if it wanted to. Hence you are guaranteed to have two
co-existing bitcoin blockchains afterwards.

Again: this is unlike the hypothetical persistence of two chains after a
hardfork that is only contentious but doesn’t change the mining algorithm,
the kind of hardfork you are proposing would guarantee the persistence of
two chains.

Note that “AsicBoost” above is replaceable with “optimization X”. It’s
simply a logical argument: If you want to make optimization X impossible
and someone is already using optimization X you end up with two chains. So
unless you know exactly which optimizations are in use (and therefore also
know which ones are not in use) you can’t make these kind of changes.
AsicBoost is known at least since middle of 2013.

To be more precise, if you change the block validation ruleset R to block
validation ruleset S you have to make sure that every hardware that was
capable of mining R-valid blocks is also capable of mining S-valid blocks.

The problem is that chip manufacturers will not tell you which
optimizations they use. You would have to threaten to irreversibly fork
their hardware out by a rule change, only then would they start shouting
and reveal their optimization. It seems extremely dangerous to set the
precedence of a hardfork that irreversibly forks out a certain type of
mining hardware.

The part "Also the fix should be compatible with existing mining hardware."
is impossible to achieve because it's unclear what "existing mining
hardware" is. There has never been a specification of what mining hardware
should do. There are only acceptance rules.

The only way out is to go the exact opposite way and to embrace as many
optimizations as possible to the point where there are no more
optimizations left to do, or hopefully getting very close to that point.

Timo



On Tue, May 10, 2016 at 11:57 AM, Peter Todd via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As part of the hard-fork proposed in the HK agreement(1) we'd like to make
> the
> patented AsicBoost optimisation useless, and hopefully make further similar
> optimizations useless as well.
>
> What's the best way to do this? Ideally this would be SPV compatible, but
> if it
> requires changes from SPV clients that's ok too. Also the fix this should
> be
> compatible with existing mining hardware.
>
>
> 1)
> https://medium.com/@bitcoinroundtable/bitcoin-roundtable-consensus-266d475a61ff
>
> 2)
> http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-April/012596.html
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev