Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

[Jim Posen via bitcoin-dev]

To address the at-least-one-honest peer security assumption for light
clients, I think this is a rather good security model for light clients.
First it significantly reduces the chances that an attacker can eclipse a
client just by chance, and clients can implement measures like ensuring
connectivity to peers from different subnets. But even if, as you suggest,
a network attacker controls the target's local network, peers still can
have good security guarantees by requiring authenticated connections to
semi-trusted peers. A client can select a set of N servers that it believes
will not collude to attack it, and only sync filters if connected to a
threshold of them. So even if the network is malicious, the attacker cannot
forge the authenticated responses. The level of trust in these designated
parties again is quite low because only one has to be honest. This would
require something like BIP 150.

Even if clients are uncomfortable with whitelisting required peers, it
could have a policy of requiring a certain number of connections to peers
that have honestly served it filters in the past. This is sort of like
trust-on-first-use. This type of scheme, however, would require nodes to
advertise a pubkey per address, which BIP 150/151 does not support at
present.

All in all, I think this is an acceptable security model for light clients.
Without the ability to verify filter validity, a client would have to stop
syncing altogether in the presence of just one malicious peer, which is
unacceptable.

The other concern you raise, Greg, is using a filter for P2P communications
that we expect may be replaced in the future. You also raise the point that
full node wallets can use the smaller filters for rescans because the
filter validity is not in question. I'd perfectly fine with the idea of
defining two filter types in the BIP, one that is output script + outpoint
and the other output script + prev script. But I imagine some people would
object to the idea of full nodes storing two different filters that overlap
in contents. If we had to pick just one though, I'm strongly in support of
output script + outpoint so that BIP 157 can be deployed ASAP without a
consensus change. It's entirely possible we will learn even more about
optimal filter design through deployment and adoption.

On Fri, Jun 1, 2018 at 5:22 PM Gregory Maxwell  wrote:

> On Sat, Jun 2, 2018 at 12:01 AM, Olaoluwa Osuntokun 
> wrote:
> >> A typical network attacker (e.g.  someone on your lan or wifi segmet, or
> >> someone who has compromised or operates an upstream router) can be all
> of
> >> your peers.
> >
> > This is true, but it cannot make us accept any invalid filters unless the
> > attacker is also creating invalid blocks w/ valid PoW.
>
> I wish that were the true, but absent commitments that wouldn't be the
> case unless you were always downloading all the blocks-- since you
> wouldn't have any sign that there was something wrong with the
> filter-- and downloading all the blocks would moot using the filters
> in the first place. :)
>
> Or have I misunderstood you massively here?
>
> For segwit originally I had proposed adding additional commitments
> that would make it possible to efficiently prove invalidity of a
> block; but that got stripped because many people were of the view that
> the "assume you have at least one honest peer who saw that block and
> rejected it to tell you that the block was invalid" security
> assumption was of dubious value. Maybe it's more justifiable to make
> use of a dubious assumption for a P2P feature than for a consensus
> feature?  Perhaps,  I'd rather have both filter types from day one so
> that things not implementing the comparison techniques don't get the
> efficiency loss or the extra work to change filter types for a
> consensus one.
>
> [I think now that we're much closer to a design that would be worth
> making a consensus committed version of than we were a few months ago
> now, since we are effectively already on a second generation of the
> design with the various improvements lately]
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

[Gregory Maxwell via bitcoin-dev]

On Sat, Jun 2, 2018 at 12:01 AM, Olaoluwa Osuntokun  wrote:
>> A typical network attacker (e.g.  someone on your lan or wifi segmet, or
>> someone who has compromised or operates an upstream router) can be all of
>> your peers.
>
> This is true, but it cannot make us accept any invalid filters unless the
> attacker is also creating invalid blocks w/ valid PoW.

I wish that were the true, but absent commitments that wouldn't be the
case unless you were always downloading all the blocks-- since you
wouldn't have any sign that there was something wrong with the
filter-- and downloading all the blocks would moot using the filters
in the first place. :)

Or have I misunderstood you massively here?

For segwit originally I had proposed adding additional commitments
that would make it possible to efficiently prove invalidity of a
block; but that got stripped because many people were of the view that
the "assume you have at least one honest peer who saw that block and
rejected it to tell you that the block was invalid" security
assumption was of dubious value. Maybe it's more justifiable to make
use of a dubious assumption for a P2P feature than for a consensus
feature?  Perhaps,  I'd rather have both filter types from day one so
that things not implementing the comparison techniques don't get the
efficiency loss or the extra work to change filter types for a
consensus one.

[I think now that we're much closer to a design that would be worth
making a consensus committed version of than we were a few months ago
now, since we are effectively already on a second generation of the
design with the various improvements lately]
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

[Olaoluwa Osuntokun via bitcoin-dev]

> A typical network attacker (e.g.  someone on your lan or wifi segmet, or
> someone who has compromised or operates an upstream router) can be all of
> your peers.

This is true, but it cannot make us accept any invalid filters unless the
attacker is also creating invalid blocks w/ valid PoW.

> The original propsal for using these kinds of maps was that their digests
> could eventually be commited and then checked against the commitment,
> matching the same general security model used otherwise in SPV.

Indeed, but no such proposal for committing the filters has emerged yet.
Slinging filters with new p2p messages requires much less coordination that
adding a new committed structure to Bitcoin. One could imagine that if
consensus exists to add new committed structures, then there may also be
initiatives to start to commit sig-ops, block weight, utxo's etc. As a
result one could imagine a much longer deployment cycle compared to a pure
p2p roll out in the near term, and many applications are looking for a
viable alternative to BIP 37.

> Unfortunately, using the scripts instead of the outpoints takes us further
> away from a design that is optimized for committing (or, for that matter,
> use purely locally by a wallet)...

I agree that using the prev input scripts would indeed be optimal from a
size perspective when the filters are to be committed. The current proposal
makes way for future filter types and it's likely the case that only the
most optimal filters should be committed (while other more niche filters
perhaps, remain only on the p2p level).

-- Laolu


On Thu, May 31, 2018 at 9:14 PM Gregory Maxwell  wrote:

> On Fri, Jun 1, 2018 at 2:52 AM, Olaoluwa Osuntokun via bitcoin-dev
>  wrote:
> > One notable thing that I left off is the proposed change to use the
> previous
> > output script rather than the outpoint. Modifying the filters in this
> > fashion would be a downgrade in the security model for light clients, as
> it
>
> Only if you make a very strong assumption about the integrity of the
> nodes the client is talkign to. A typical network attacker (e.g.
> someone on your lan or wifi segmet, or someone who has compromised or
> operates an upstream router) can be all of your peers.
>
> The original propsal for using these kinds of maps was that their
> digests could eventually be commited and then checked against the
> commitment, matching the same general security model used otherwise in
> SPV.
>
> Unfortunately, using the scripts instead of the outpoints takes us
> further away from a design that is optimized for committing (or, for
> that matter, use purely locally by a wallet)...
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SIGHASH2 for version 1 witness programme

[Johnson Lau via bitcoin-dev]

> On 2 Jun 2018, at 2:15 AM, Russell O'Connor  wrote:
> 
> 
> I prefer a different opcode for CHECKSIGFROMSTACK because I dislike opcodes 
> that pop a non-static number of elements off the stack.  Popping a dynamic 
> number of stack elements makes it more difficult to validate that a Script 
> pubkey doesn't allow any funny business.


Agreed. This is one of the reasons I think we should remove CHECKMULTISIG in 
the new script system___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SIGHASH2 for version 1 witness programme

[Russell O'Connor via bitcoin-dev]

On Fri, Jun 1, 2018 at 1:03 PM, Johnson Lau  wrote:

> On 1 Jun 2018, at 11:03 PM, Russell O'Connor 
> wrote:
> On Thu, May 31, 2018 at 2:35 PM, Johnson Lau via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>>
>>   Double SHA256 of the serialization of:
>>
>
> Should we replace the Double SHA256 with a Single SHA256?  There is no
> possible length extension attack here.  Or are we speculating that there is
> a robustness of Double SHA256 in the presence of SHA256 breaking?
>
> I suggest putting `sigversion` at the beginning instead of the end of the
> format.  Because its value is constant, the beginning of the SHA-256
> computation could be pre-computed in advance.  Furthermore, if we make the
> `sigversion` exactly 64-bytes long then the entire first block of the
> SHA-256 compression function could be pre-computed.
>
> Can we add CHECKSIGFROMSTACK or do you think that would go into a separate
> BIP?
>
>
> I think it’s just a tradition to use double SHA256. One reason we might
> want to keep dSHA256 is a blind signature might be done by giving only the
> single SHA256 hash to the signer. At the same time, a non-Bitcoin signature
> scheme might use SHA512-SHA256. So a blind signer could distinguish the
> message type without learning the message.
>
> sigversion is a response to Peter Todd’s comments on BIP143:
> https://petertodd.org/2016/segwit-consensus-critical-code-review#bip143-
> transaction-signature-verification
>
> I make it a 0x0100 at the end of the message because the last 4 bytes
> has been the nHashType in the legacy/BIP143 protocol. Since the maximum
> legacy nHashType is 0xff, no collision could ever occur.
>
> Putting a 64-byte constant at the beginning should also work, since a
> collision means SHA256 is no longer preimage resistance. I don’t know much
> about SHA256 optimisation. How good it is as we put a 64-byte constant at
> the beginning, while we also make the message 64-byte longer?
>

In theory, having a fixed 64 byte constant at the beginning results in zero
overhead for those 64 bytes.  An implementation would just start the usual
SHA-256 algorithm with a different pre-computed and fixed initial value
than SHA-256's standard initial value.  The SHA-256 padding counter would
also need to start at 64*8 bits rather than starting at 0 bits.  In
practice, assuming a OpenSSL-like implementation of SHA-256, it should be
easy to implement this optimization. One would replace SHA256_Init call
with a variant that initializes the SHA256_CTX to this pre-computed value
and sets SHA256_CTX's num counter to the appropriate value.  Non-optimized
implementations can still just add the 64 byte prefix and use any SHA-256
implementation.

For CHECKSIGFROMSTACK (CSFS), I think the question is whether we want to
> make it as a separate opcode, or combine that with CHECKSIG. If it is a
> separate opcode, I think it should be a separate BIP. If it is combined
> with CHECKSIG, we could do something like this: If the bit 10 of SIGHASH2
> is set, CHECKSIG will pop one more item from stack, and serialize its
> content with the transaction digest. Any thought?
>

I prefer a different opcode for CHECKSIGFROMSTACK because I dislike opcodes
that pop a non-static number of elements off the stack.  Popping a dynamic
number of stack elements makes it more difficult to validate that a Script
pubkey doesn't allow any funny business.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] SIGHASH2 for version 1 witness programme

[Johnson Lau via bitcoin-dev]

> On 1 Jun 2018, at 11:03 PM, Russell O'Connor  wrote:
> 
> 
> 
> On Thu, May 31, 2018 at 2:35 PM, Johnson Lau via bitcoin-dev 
>  > wrote:
> 
>   Double SHA256 of the serialization of:
> 
> Should we replace the Double SHA256 with a Single SHA256?  There is no 
> possible length extension attack here.  Or are we speculating that there is a 
> robustness of Double SHA256 in the presence of SHA256 breaking?
> 
> I suggest putting `sigversion` at the beginning instead of the end of the 
> format.  Because its value is constant, the beginning of the SHA-256 
> computation could be pre-computed in advance.  Furthermore, if we make the 
> `sigversion` exactly 64-bytes long then the entire first block of the SHA-256 
> compression function could be pre-computed.
> 
> Can we add CHECKSIGFROMSTACK or do you think that would go into a separate 
> BIP?

I think it’s just a tradition to use double SHA256. One reason we might want to 
keep dSHA256 is a blind signature might be done by giving only the single 
SHA256 hash to the signer. At the same time, a non-Bitcoin signature scheme 
might use SHA512-SHA256. So a blind signer could distinguish the message type 
without learning the message.

sigversion is a response to Peter Todd’s comments on BIP143: 
https://petertodd.org/2016/segwit-consensus-critical-code-review#bip143-transaction-signature-verification
 


I make it a 0x0100 at the end of the message because the last 4 bytes has 
been the nHashType in the legacy/BIP143 protocol. Since the maximum legacy 
nHashType is 0xff, no collision could ever occur.

Putting a 64-byte constant at the beginning should also work, since a collision 
means SHA256 is no longer preimage resistance. I don’t know much about SHA256 
optimisation. How good it is as we put a 64-byte constant at the beginning, 
while we also make the message 64-byte longer?

For CHECKSIGFROMSTACK (CSFS), I think the question is whether we want to make 
it as a separate opcode, or combine that with CHECKSIG. If it is a separate 
opcode, I think it should be a separate BIP. If it is combined with CHECKSIG, 
we could do something like this: If the bit 10 of SIGHASH2 is set, CHECKSIG 
will pop one more item from stack, and serialize its content with the 
transaction digest. Any thought?


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

Re: [bitcoin-dev] SIGHASH2 for version 1 witness programme

[Russell O'Connor via bitcoin-dev]

On Thu, May 31, 2018 at 2:35 PM, Johnson Lau via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
>   Double SHA256 of the serialization of:
>

Should we replace the Double SHA256 with a Single SHA256?  There is no
possible length extension attack here.  Or are we speculating that there is
a robustness of Double SHA256 in the presence of SHA256 breaking?

I suggest putting `sigversion` at the beginning instead of the end of the
format.  Because its value is constant, the beginning of the SHA-256
computation could be pre-computed in advance.  Furthermore, if we make the
`sigversion` exactly 64-bytes long then the entire first block of the
SHA-256 compression function could be pre-computed.

Can we add CHECKSIGFROMSTACK or do you think that would go into a separate
BIP?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev