Re: [bitcoin-dev] Some real-world results about the current Segwit Discount

[Sergio Demian Lerner via bitcoin-dev]

I'm not advocating. I'm mediating.


This is out of

On Wed, May 10, 2017 at 1:39 PM, Matt Corallo 
wrote:

> I highly disagree about the "not shit" part.  You're advocating for
> throwing away one of the key features of Segwit, something that is very
> important for Bitcoin's long-term reliability! If you think doing so is
> going to somehow help get support in a divided community, I don't
> understand how - more likely you're only going to make things significantly
> worse.
>
> On May 10, 2017 11:25:27 AM EDT, Sergio Demian Lerner <
> sergio.d.ler...@gmail.com> wrote:
> >Jaja. But no shit. Not perfect maybe, but Bitcoin was never perfect. It
> >has
> >always been good enough. And at the beginning it was quite simple.
> >Simple
> >enough it allowed gradual improvements that anyone with some technical
> >background could understand. Now we need a full website to explain an
> >improvement.
> >But this is becoming more and more out of topic.
> >
> >
> >On Wed, May 10, 2017 at 11:05 AM, Matt Corallo
> >
> >wrote:
> >
> >> I'm highly unconvinced of this point. Sure, you can change fewer
> >lines
> >> of code, but if the result is, lets be honest, shit, how do you
> >believe
> >> its going to have a higher chance of getting acceptance from the
> >broader
> >> community? I think you're over-optimizing in the wrong direction.
> >>
> >> Matt
> >>
> >> On 05/09/17 20:58, Sergio Demian Lerner wrote:
> >> > I agree with you Matt.
> >> > I'm artificially limiting myself to changing the parameters of
> >Segwit as
> >> > it is..
> >> >
> >> > This is motivated by the idea that a consensual HF in the current
> >state
> >> > would have greater chance of acceptance if it changes the minimum
> >number
> >> > of lines of code.
> >> >
> >> >
> >> >
> >> > On Tue, May 9, 2017 at 5:13 PM, Gregory Maxwell  >> > > wrote:
> >> >
> >> > On Tue, May 9, 2017 at 7:42 PM, Matt Corallo
> >> > >
> >wrote:
> >> > > at beast.
> >> >
> >> > Rawr.
> >> >
> >> >
> >>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Some real-world results about the current Segwit Discount

[Matt Corallo via bitcoin-dev]

I highly disagree about the "not shit" part.  You're advocating for throwing 
away one of the key features of Segwit, something that is very important for 
Bitcoin's long-term reliability! If you think doing so is going to somehow help 
get support in a divided community, I don't understand how - more likely you're 
only going to make things significantly worse.

On May 10, 2017 11:25:27 AM EDT, Sergio Demian Lerner 
 wrote:
>Jaja. But no shit. Not perfect maybe, but Bitcoin was never perfect. It
>has
>always been good enough. And at the beginning it was quite simple.
>Simple
>enough it allowed gradual improvements that anyone with some technical
>background could understand. Now we need a full website to explain an
>improvement.
>But this is becoming more and more out of topic.
>
>
>On Wed, May 10, 2017 at 11:05 AM, Matt Corallo
>
>wrote:
>
>> I'm highly unconvinced of this point. Sure, you can change fewer
>lines
>> of code, but if the result is, lets be honest, shit, how do you
>believe
>> its going to have a higher chance of getting acceptance from the
>broader
>> community? I think you're over-optimizing in the wrong direction.
>>
>> Matt
>>
>> On 05/09/17 20:58, Sergio Demian Lerner wrote:
>> > I agree with you Matt.
>> > I'm artificially limiting myself to changing the parameters of
>Segwit as
>> > it is..
>> >
>> > This is motivated by the idea that a consensual HF in the current
>state
>> > would have greater chance of acceptance if it changes the minimum
>number
>> > of lines of code.
>> >
>> >
>> >
>> > On Tue, May 9, 2017 at 5:13 PM, Gregory Maxwell > > > wrote:
>> >
>> > On Tue, May 9, 2017 at 7:42 PM, Matt Corallo
>> > >
>wrote:
>> > > at beast.
>> >
>> > Rawr.
>> >
>> >
>>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Some real-world results about the current Segwit Discount

[Sergio Demian Lerner via bitcoin-dev]

Jaja. But no shit. Not perfect maybe, but Bitcoin was never perfect. It has
always been good enough. And at the beginning it was quite simple. Simple
enough it allowed gradual improvements that anyone with some technical
background could understand. Now we need a full website to explain an
improvement.
But this is becoming more and more out of topic.


On Wed, May 10, 2017 at 11:05 AM, Matt Corallo 
wrote:

> I'm highly unconvinced of this point. Sure, you can change fewer lines
> of code, but if the result is, lets be honest, shit, how do you believe
> its going to have a higher chance of getting acceptance from the broader
> community? I think you're over-optimizing in the wrong direction.
>
> Matt
>
> On 05/09/17 20:58, Sergio Demian Lerner wrote:
> > I agree with you Matt.
> > I'm artificially limiting myself to changing the parameters of Segwit as
> > it is..
> >
> > This is motivated by the idea that a consensual HF in the current state
> > would have greater chance of acceptance if it changes the minimum number
> > of lines of code.
> >
> >
> >
> > On Tue, May 9, 2017 at 5:13 PM, Gregory Maxwell  > > wrote:
> >
> > On Tue, May 9, 2017 at 7:42 PM, Matt Corallo
> > > wrote:
> > > at beast.
> >
> > Rawr.
> >
> >
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Per-block non-interactive Schnorr signature aggregation

[adiabat via bitcoin-dev]

I messed up and only replied to Russel O'Connor; my response is copied below.
And then there's a bit more.

-
Aha, Wagner's generalized birthday attack, the bane of all clever tricks!
I didn't realize it applied in this case but looks like it in fact does.
 applies to this case.  It would have to be a miner performing the
attack as the s-value would only be aggregated in the coinbase tx, but
that's hardly an impediment.

In fact, sketching it out, it doesn't look like the need to know m1,
m2... m_n is a big problem.  Even if the m's are fixed after being
chosen based on the P1... Pn's, (in bitcoin, m always commits to P so
not sure why it's needed in the hash) there is still freedom to
collide the hashes.  The R values can be anything, so getting h(m1,
R1, P1) + h(m2, R2, P2)... to equal -h(m0, R0, P0) is doable with
Wagner's attack by varying R1, R2... to get different hashes.

I *think* there is a viable defense against this attack, but it does
make the whole aggregation setup less attractive.  The miner who
calculates s-aggregate could also aggregate all the public keys from
all the aggregated signatures in the block (P0, P1...), sort them and
hash the concatenated list of pubkeys.  They could then multiply s by
this combo-pubkey hash (call it h(c)).  Then when nodes verify the
aggregate signature, they need to go through all the pubkeys in the
block, create the same combo-pubkey hash, and multiply s by the
multiplicative inverse of the h(c) they calculate, then verify s.  I
believe this breaks the Wagner generalized birthday attack because
every h(m_i, R_i, P_i)*h(c) included or omitted affects the c part of
h(m0, R0, P0)*h(c).

I'm not sure how badly this impacts the verification speed.  It might
not be too bad for verification as it's amortized over the whole
block.  For the miner doing the aggregation it's a bit slower as they
need to re-sort and hash all the pubkeys every time a new signature is
added.  Might not be too slow.

I'm not super confident that this actually prevents the generalized
birthday attack though.  I missed that attack in the previous post so
I'm 0 for 1 against Wagner so far :)

-

Andrew: Right, commiting to all the R values would also work; is there
an advantage to using the R's instead of the P's?  At first glance it
seems about the same.

Another possible optimization: instead of sorting, concatenate all the
R's or P's in the order they appear in the block.  Then have the miner
commit to s*h(c)^1, the multiplicative inverse of the hash of all
those values.  Then when nodes are verifying in IBD, they can just
multiply by h(c) and they don't have to compute the inverse.  A bit
more work for the miner and a bit less for the nodes.

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

Re: [bitcoin-dev] Some real-world results about the current Segwit Discount

[Matt Corallo via bitcoin-dev]

I'm highly unconvinced of this point. Sure, you can change fewer lines
of code, but if the result is, lets be honest, shit, how do you believe
its going to have a higher chance of getting acceptance from the broader
community? I think you're over-optimizing in the wrong direction.

Matt

On 05/09/17 20:58, Sergio Demian Lerner wrote:
> I agree with you Matt. 
> I'm artificially limiting myself to changing the parameters of Segwit as
> it is.. 
> 
> This is motivated by the idea that a consensual HF in the current state
> would have greater chance of acceptance if it changes the minimum number
> of lines of code.
> 
> 
> 
> On Tue, May 9, 2017 at 5:13 PM, Gregory Maxwell  > wrote:
> 
> On Tue, May 9, 2017 at 7:42 PM, Matt Corallo
> > wrote:
> > at beast.
> 
> Rawr.
> 
> 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Per-block non-interactive Schnorr signature aggregation

[Andrew Poelstra via bitcoin-dev]

On Tue, May 09, 2017 at 09:59:06PM -0400, Russell O'Connor via bitcoin-dev 
wrote:
> I'm a bit amateur at this sort of thing, but let me try to argue that this
> proposal is in fact horribly broken ;)
> 
> Suppose Alice has some UTXO with some money Bob wants to steal.  Grant me
> that the public key P0 protecting Alice's UTXO is public (say because the
> public key has been reused elsewhere).
> 
> Bob going to spend Alice's UTXO by generating random values s0, k0 and R0
> := k0*G and thus creating a random signature for it, [R0, s0].  Now clearly
> this signature isn't going to be valid by itself because it is just random.
> Bob's goal will be to make a transaction with other inputs such that, while
> the individual signatures are not valid, the aggregated signature will be
> valid.
>

If you seed the randomization with every R value (which would come for free
if you used, say, the witness root) then Wagner's attack no longer applies.

The idea is that no aggregation occurs until a miner produces a block. You
have a bunch of independent Schnorr sigs (s_i, R_i). Then the _miner_ multiples
each s_i by H(witness root || index) or whatever, sums up the s_i's, and commits
the sum somewhere where it doesn't affect the root.

Verifiers then multiply each R_i by the same multiplying factors and are able
to do a batch verification of them.


Verifiers who have seen a signature before and cached it as valid can save
themselves a bit of time by subtracting H(witness root || index)*s_i from
the summed s-value and then skipping R_i in the above step. These are scalar
operations and are extremely cheap.

They can recognize the signature given only the transaction it signs and R_i,
which uniquely determine a valid signature.


I believe this is what Tadge was referring to when he mentioned a talk of mine.
It's roughly what I've had in mind whenever I talk about non-interactive Schnorr
aggregation.



Cheers
Andrew


-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



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