Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-07 Thread Russell O'Connor via bitcoin-dev
On Wed, Jul 7, 2021 at 9:12 AM Russell O'Connor 
wrote:

>
> On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj  wrote:
>
>> Good morning Russell,
>>
>> > Hi ZmnSCPxj,
>> >
>> > I don't believe we need to ban Turing completeness for the sake of
>> banning Turing completeness.
>>
>> Well I believe we should ban partial Turing-completeness, but allow total
>> Turing-completeness.
>>
>
> Unfortunately, when it comes to cross-transaction computations, it is
> infeasible to ban non-terminating computation.
>
> The nature of recursive covenants is that the program "writes" the *source
> code* next step of the computation to the scriptPubKey to one of the
> outputs of its transaction. Technically speaking it verifies that the
> scriptPubKey is a commitment to the source code of the next step of the
> program, but morally that is the same as writing the source code.  Then the
> next step of the computation is invoked by someone "evaluating* that next
> step's source code by creating a valid transaction that spends the
> generated output.
>
> The point is this ability to create new source code and then evaluate it
> leads to the ability to write universal (i.e non-terminating)
> computations.  The only way to prevent it is to ban source code
> manipulation, but since Bitcoin Script source code is just a string of
> bytes, it would mean banning the manipulation of strings of bytes.  But the
> entire Bitcoin Script language works by manipulating strings of bytes
> within a stack machine.  Indeed the most trivial of non-terminating
> programs can be implemented by extracting the current input's scriptPubKey
> from the sighash and "writing" the identical scriptPubKey to one of its
> outputs.  That example hardly takes any manipulation at all to implement.
>

A follow up:  Because recursive covenants need to be sent to a new
transaction in order to recurse, you might choose to view this stepping
mechanism as productive by modeling each transaction step as the continue
constructor in your RecResult codata type.  Indeed after (drinking coffee
and) rereading your mailing list item, it seems that this is the point you
were making.

So sorry for my hasty response.  I believe we are largely in agreement here.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-07 Thread Russell O'Connor via bitcoin-dev
On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj  wrote:

> Good morning Russell,
>
> > Hi ZmnSCPxj,
> >
> > I don't believe we need to ban Turing completeness for the sake of
> banning Turing completeness.
>
> Well I believe we should ban partial Turing-completeness, but allow total
> Turing-completeness.
>

Unfortunately, when it comes to cross-transaction computations, it is
infeasible to ban non-terminating computation.

The nature of recursive covenants is that the program "writes" the *source
code* next step of the computation to the scriptPubKey to one of the
outputs of its transaction. Technically speaking it verifies that the
scriptPubKey is a commitment to the source code of the next step of the
program, but morally that is the same as writing the source code.  Then the
next step of the computation is invoked by someone "evaluating* that next
step's source code by creating a valid transaction that spends the
generated output.

The point is this ability to create new source code and then evaluate it
leads to the ability to write universal (i.e non-terminating)
computations.  The only way to prevent it is to ban source code
manipulation, but since Bitcoin Script source code is just a string of
bytes, it would mean banning the manipulation of strings of bytes.  But the
entire Bitcoin Script language works by manipulating strings of bytes
within a stack machine.  Indeed the most trivial of non-terminating
programs can be implemented by extracting the current input's scriptPubKey
from the sighash and "writing" the identical scriptPubKey to one of its
outputs.  That example hardly takes any manipulation at all to implement.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-06 Thread Russell O'Connor via bitcoin-dev
If the main outstanding issue is whether to split R or S, I think as far as
Elements goes, I am inclined to go with the CAT option regardless of
whether Bitcoin chooses to split R/S or not (not that I'm necessarily a
decision maker here).

The issue here is that (a) Elements already has CAT, and (b) updating
CHECKSIGFROMSTACK is effectively a blocking issue for deploying Taproot on
Elements.  I don't think we will be holding up CHECKSIGFROMSTACK for this
issue even if it risks being incompatible with an eventual Bitcoin
CHECKSIGFROMSTACK.

To be clear, I don't mean to prejudice this discussion by this statement.
This just happens to be what makes sense for the Elements project at this
time, and what makes sense for Elements may not necessarily make sense for
Bitcoin.

Of course, I think we should just go for CAT compatibility.  Otherwise we
are just going to have a proliferation of trusted CAT oracles paid for with
lightning by people wanting to perform CAT operations.

On Tue, Jul 6, 2021 at 1:55 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Re-threading Sanket's comment on split R value:
>
> I also am in general support of the `OP_CHECKSIGFROMSTACK` opcode. We
>> would need to update the suggestion to BIP340, and add it to sigops budget.
>> I have no strong preference for splitting R and s values or variable-length
>> messages.
>>
>
> Back to my comment:
>
>
> I see a few options:
>
> 1) Making a new 64 byte PK standard which is (R, PK)
> 2) Splitting (R,S)
> 3) Different opcodes
> 4) CAT
>
> The drawback of option 1 is that it's designed to support only very
> specific use cases. The main drawback of splitting via option 2 is that you
> entail an extra push byte for every use. Option 3 wastes opcodes. CAT has
> the general drawbacks of CAT, but worth noting that CAT will likely
> eventually land making the splitting feature redundant.
>
>
> Before getting too in the weeds, it might be worth listing out interesting
> script fragments that people are aware of with split R/S so we can see how
> useful it might be?
>
> Use a specific R Value
> -   ||  SWAP  CSFS
>
> Reuse arbitrary R for a specific M (pay to leak key)
> -  ||  DUP2 EQUAL NOT VERIFY 2 PICK SWAP  DUP TOALTSTACK
> CSFSV FROMALTSTACK CSFS
>
> Verify 2 different messages reuse the same R.
> -  ||  2 PICK EQUAL NOT VERIFY 3 PICK  DUP
> TOALTSTACK CSFSV FROMALTSTACK CSFS
>
> Use a R Value signed by an oracle:
> -  || DUP TOALTSTACK  CSFSV
> FROMALTSTACK SWAP  CSFS
>
> ___
> 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] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-06 Thread Russell O'Connor via bitcoin-dev
On Tue, Jul 6, 2021 at 2:26 AM Billy Tetrud  wrote:

> >  when people are talking about enabling covenants, we are talking about
> whether OP_CAT should be allowed or not
>
> Are they? Are you implying that anything that enables covenants is
> equivalent to enabling OP_CAT? Generally when I think about enabling
> covenants, I'm thinking more about OP_CTV (or some similarly specific
> opcode
> 
> ).
>
> > OP_TWEAK
>
> I wasn't able to find anything about what that is. Would you mind
> clarifying what that concept is?
>

In tapscript one can generally recover the current input's scriptPubkey
through sighash introspection via the usual covenant tricks.  This allows
you to make a recursive covenant by spending funds back to the same
identical scriptPubkey.  However, in order for a recursive covenant to be
actually interesting, there needs to be some sort of state update in each
transition.  If there is no state update then sending funds back to itself
is of very limited value.  It will reset the timer on relative locks, but
that is about all.

The "normal" way of writing useful recursive covenants is to modify the
scriptPubkey by changing a fragment of it that contains some sort of
state.  However in order to update a tapscript pubkey one needs to apply
not only hashing, to create a Merkel root, but also to create a tweaked
taproot pubkey that commits to this root.  While script currently comes
with a SHA-256 hashing opcode, there is no opcode that will let you perform
the necessary tweaking to create a taproot scriptPubkey.

But as I mentioned afterwards, there are other places in the UTXO that you
could put data in order to perform a state update.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-05 Thread Russell O'Connor via bitcoin-dev
Hi ZmnSCPxj,

I don't believe we need to ban Turing completeness for the sake of banning
Turing completeness.  My concerns have always been around ensuring that
transaction and block validation is not unduly burdensome for nodes.  So
for Bitcoin Script, we want to bound the amount of resources needed to
execute it, preferably as a linear function of weight[1], and preferably
have it clear what the evaluation costs are going to be prior to
evaluation[2].  We also want to keep Script execution as a pure function of
the transaction data so that nodes do not need to reevaluate their mempool
on every new block.  For consensus purposes we prefer to have simple
primitive operations that have clear and precise semantics that are as
likely as possible to be reimplemented correctly if they are reimplemented
(or at least let us not make this problem worse than it already is).  In
particular, Script needs to be easy to parse to avoid weird parsing
machines that lead to security vulnerabilities within node software.

While the above design constraints imply a prohibition on Turing complete
computation within a single Script, they do not imply a prohibition on
arbitrary, covenant-enabled computations that spans across multiple
transactions.  Neither would these constraints prohibit some kind of STARK
or SNARK tapleaf version that was somehow capable of succinctly
representing arbitrary computations, so long as validation costs remain
bounded.

And while it is true that covenant-enabled computations could allow users
to put their funds at risk through weird machines that manipulate their
money on the blockchain, as longs as that weirdness stays at that level of
the abstract Bitcoin Script machine, then I suppose it is *caveat emptor*;
don't send your funds to random unverified Bitcoin Scripts, advice that is
already the case today.  We can keep that potential weirdness at bay by
keeping Script simple, and maintaining our understanding that the Script
programs (like the rest of the blockchain data) are untrusted inputs and
they need to be validated and scrutinized before interpretation.

[1] In tapscript I believe all operations are linear time with the
exception of OP_ROLL.  However OP_ROLL is still constrained by global
limits on stack size, etc.
[2] In Bitcoin Script, without loops of any kind, every opcode is evaluated
at most once, so counting opcodes is an easy way to put an upper bound on
your costs before evaluation.

On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Dave,
>
> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> >
> > > However, I think the broader community is unconvinced by the cost
> benefit
> > > of arbitrary covenants. See
> > >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > > as a recent example. Therefore as a critical part of building
> consensus on
> > > various techniques I've worked to emphasize that specific additions do
> not
> > > entail risk of accidentally introducing more than was bargained for to
> > > respect the concerns of others.
> >
> > Respecting the concerns of others doesn't require lobotomizing useful
> > tools. Being respectful can also be accomplished by politely showing
> > that their concerns are unfounded (or at least less severe than they
> > thought). This is almost always the better course IMO---it takes much
> > more effort to satisfy additional engineering constraints (and prove to
> > reviewers that you've done so!) than it does to simply discuss those
> > concerns with reasonable stakeholders. As a demonstration, let's look
> > at the concerns from Shinobi's post linked above:
> >
> > They seem to be worried that some Bitcoin users will choose to accept
> > coins that can't subsequently be fungibily mixed with other bitcoins.
> > But that's already been the case for a decade: users can accept altcoins
> > that are non-fungible with bitcoins.
> >
> > They talk about covenants where spending is controlled by governments,
> > but that seems to me exactly like China's CBDC trial.
> >
> > They talk about exchanges depositing users' BTC into a covenant, but
> > that's just a variation on the classic not-your-keys-not-your-bitcoins
> > problem. For all you know, your local exchange is keeping most of its
> > BTC balance commitments in ETH or USDT.
> >
> > To me, it seems like the worst-case problems Shinobi describes with
> > covenants are some of the same problems that already exist with
> > altcoins. I don't see how recursive covenants could make any of those
> > problems worse, and so I don't see any point in limiting Bitcoin's
> > flexibility to avoid those problems when there are so many interesting
> > and useful things that unlimited covenants could do.
>
> The "altcoins are even worse" argument does seem quite convincing, and if
> Bitcoin can survive altcoins, surely it can survive covenants too?
>
> In before "turns out 

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-04 Thread Russell O'Connor via bitcoin-dev
On Sun, Jul 4, 2021 at 9:02 PM Russell O'Connor 
wrote:

> Bear in mind that when people are talking about enabling covenants, we are
> talking about whether OP_CAT should be allowed or not.
>
> That said, recursive covenants, the type that are most worrying, seems to
> require some kind of OP_TWEAK operation, and I haven't yet seen any
> evidence that this can be simulated with CHECKSIG(FROMSTACK).  So maybe we
> should leave such worries for the OP_TWEAK operation.
>

Upon further thought, you can probably make recursive covenants even with a
fixed scritpubkey by sneaking the state into a few bits of the UTXO's
amount.  Or if you try really hard, you may be able to stash your state
into a sibling output that is accessed via the txid embedded in the
prevoutpoint.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-04 Thread Russell O'Connor via bitcoin-dev
Bear in mind that when people are talking about enabling covenants, we are
talking about whether OP_CAT should be allowed or not.

That said, recursive covenants, the type that are most worrying, seems to
require some kind of OP_TWEAK operation, and I haven't yet seen any
evidence that this can be simulated with CHECKSIG(FROMSTACK).  So maybe we
should leave such worries for the OP_TWEAK operation.

On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Dave,
>
> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> >
> > > However, I think the broader community is unconvinced by the cost
> benefit
> > > of arbitrary covenants. See
> > >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > > as a recent example. Therefore as a critical part of building
> consensus on
> > > various techniques I've worked to emphasize that specific additions do
> not
> > > entail risk of accidentally introducing more than was bargained for to
> > > respect the concerns of others.
> >
> > Respecting the concerns of others doesn't require lobotomizing useful
> > tools. Being respectful can also be accomplished by politely showing
> > that their concerns are unfounded (or at least less severe than they
> > thought). This is almost always the better course IMO---it takes much
> > more effort to satisfy additional engineering constraints (and prove to
> > reviewers that you've done so!) than it does to simply discuss those
> > concerns with reasonable stakeholders. As a demonstration, let's look
> > at the concerns from Shinobi's post linked above:
> >
> > They seem to be worried that some Bitcoin users will choose to accept
> > coins that can't subsequently be fungibily mixed with other bitcoins.
> > But that's already been the case for a decade: users can accept altcoins
> > that are non-fungible with bitcoins.
> >
> > They talk about covenants where spending is controlled by governments,
> > but that seems to me exactly like China's CBDC trial.
> >
> > They talk about exchanges depositing users' BTC into a covenant, but
> > that's just a variation on the classic not-your-keys-not-your-bitcoins
> > problem. For all you know, your local exchange is keeping most of its
> > BTC balance commitments in ETH or USDT.
> >
> > To me, it seems like the worst-case problems Shinobi describes with
> > covenants are some of the same problems that already exist with
> > altcoins. I don't see how recursive covenants could make any of those
> > problems worse, and so I don't see any point in limiting Bitcoin's
> > flexibility to avoid those problems when there are so many interesting
> > and useful things that unlimited covenants could do.
>
> The "altcoins are even worse" argument does seem quite convincing, and if
> Bitcoin can survive altcoins, surely it can survive covenants too?
>
> In before "turns out covenants are the next ICO".
> i.e. ICOs are just colored coins, which are useful for keeping track of
> various stuff, but have then been used as a vehicle to scam people.
> But I suppose that is a problem that humans will always have: limited
> cognition, so that *good* popular things that are outside your specific
> field of study are indistinguishable from *bad* popular things.
> So perhaps it should not be a concern on a technical level.
> Maybe we should instead make articles about covenants so boring nobody
> will hype about it (^^;)v.
>
> Increased functionality implies increased processing, and hopefully
> computation devices are getting cheap enough that the increased processing
> implied by new features should not be too onerous.
>
>
>
> To my mind, an "inescapable" covenant (i.e. one that requires the output
> to be paid to the same covenant) is basically a Turing machine, and
> equivalent to a `while (true);` loop.
> In a `while (true);` loop, the state of the machine reverts back to the
> same state, and it repeats again.
> In an inescpable covenant, the control of some amount of funds reverts
> back to the same controlling SCRIPT, and it repeats again.
> Yes, you can certainly add more functionality on top of that loop, just
> think of program main loops for games or daemons, which are, in essence,
> "just" `while (true) ...`.
> But basically, such unbounded infinite loops are possible only under
> Turing machines, thus I consider covenants to be Turing-complete.
> Principle of Least Power should make us wonder if we need full Turing
> machines for the functionality.
>
> On the other hand --- codata processing *does* allow for unbounded loops,
> without requiring full Turing-completeness; they just require total
> functionality, not partial (and Turing-completeness is partial, not total).
> Basically, data structures are unbounded storage, while codata structures
> are unbounded processing.
> Perhaps covenants can encode an upper bound on the number of recursions,
> which prevents full Turing-completeness 

Re: [bitcoin-dev] CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-04 Thread Russell O'Connor via bitcoin-dev
On Sun, Jul 4, 2021 at 1:30 PM Jeremy  wrote:

> I don't really see the point of CHECKSIGFROMSTACKADD since it's not bound
> to the txdata? When might you use this?
>

I don't feel strongly about *ADD.  I just figured it might be useful to do
a 2-of-3 between Alice, Bob and an Oracle signed value.  But I don't have
any particular use case in mind.  Either way the *ADD functionality can be
replicated by various SWAPs and ADDs etc, so we could just leave it out
until it is wanted.


> And yes -- "Add OP_CHECKSIGFROMSTACK and OP_CHECKSIGFROMSTACKVERIFY to
> follow the semantics from bip340-342 when witness program is v1." is a bit
> light on detail for what the BIP would end up looking like. If you're able
> to open up the design process a bit more on that it would be good as I
> think there are some topics worth discussing at large before things proceed
> with Elements (assuming feature compatibility remains a goal).
>

I'm certainly open to a wider design process.  We can open a specific issue
on the Elements repo.  That said, I don't see a particularly wide design
space on this front.


> The non-prehashed argument seems OK (at the cost of an extra byte...) but
> are there specific applications for !=32 arguments? I can't think of a
> particular one beyond perhaps efficiency. Can we safely use 0-520 byte
> arguments?
>

One of the reasons given in the issue (yes, the thread there is very long)
was that hashing the message requires the hash to be collision resistant
while if you give the message directly it only requires the hash to be
"random-prefix" collision / preimage resistant.  For example SHA-1 is
clearly not collision resistant but it appears to still be random-prefix
collision resistant AFAIU.  Another reason is that it allows for extremely
fast signing oracles because and R value and the midstate of the hash can
be precomputed all the way upto the application prefix, and if the message
being signed is less than 55 bytes or so, the signing cost can be as low as
one compression function and a little bit of non-EC modular arithmetic to
compute S.  If the message were required to be prehashed, then it would
take a minimum of 2 compression function calls to sign, nearly doubling the
signing time needed for the fast oracle.

Even if BIP-0340 kept its requirements that the message be exactly 32
bytes, I would still be inclined to design CHECKSIGFROMSTACK for tapscript
to take the 32-byte message from the stack instead of hashing a message
itself (BIP-0340 does it's own hashing, so prehashing the message isn't a
security concern in the same way it is for ECDSA.)  This would keep the
message off the blockchain, saving space and adding some amount of privacy
and making the operation compatible with rolling SHA256 opcodes.  But given
that BIP-0340 is going to be extended to support non-32 byte messages, then
there is no reason to impose a message length restriction on
CHECKSIGFROMSTACK.  Yes the operation will still be subject to stack item
length restrictions.  This is something script writers will have to be
aware of, but I see little reason to support messages split across multiple
stack items when we expect, by far, most messages to be 32-bytes, and I
expect those rare non-32 byte messages are expected to be reasonably short.


> Also do you have thoughts on the other questions i posed above? E.g.
> splitting R/S could be helpful w/o CAT.
>

Regarding  internal pubkeys and invalid pubkeys, I see no reason to deviate
from whatever tapscript CHECKSIG* do.

Regarding splitting R/S, This is harder because Elements does have CAT and
I think we should add CAT to Bitcoin too.  This game of trying to prevent
covenants by restricting script to the point where we are not even allowed
to have a CAT operation is a losing game.  It's just a matter of time
before we accidently introduce some way to enable covenants anyways, and it
is not worth cutting off vast amounts of functionality in pursuit of this
questionable goal.  And I say this as someone who was originally of the
opinion that we should be very very cautious before enabling new
expressivity such as covenants.  All the scary scenarios of covenants that
I am aware of can be more easily, cheaply, and flexibility implemented by
just having a counterparty in a multi-party signature that enforces their
own policy that they only sign transactions that pay to outputs that they
remain a party to.  And even if scary covenants were scarier than what can
already be done by multisig and policy, I still don't think they are scary
enough to warrant keeping CAT disabled.

So I don't think we should get fancy with CHECKSIGFROMSTACK.  Just take a
normal 64-byte signature value as a stack item.  But I don't feel strongly
about this, and I wouldn't oppose splitting R and S in Bitcoin if that is
where consensus lies.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org

Re: [bitcoin-dev] CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-03 Thread Russell O'Connor via bitcoin-dev
There is one line written at
https://github.com/ElementsProject/elements/pull/949/files#r660130155. I
suppose we need to decide on which variants of *VERIFY and *ADD we want to
include (presumably all of them) and choose which opcodes they will be
assigned to.  And I guess for CHECKSIGFROMSTACKADD will want to place the n
value between the signature and the message on the stack.  ... So I suppose
we will need more than one sentence.

The semantics would be basically to call secp256k1_schnorrsig_verify <
https://github.com/bitcoin-core/secp256k1/blob/0440945fb5ce69d335fed32827b5166e84b02e05/include/secp256k1_schnorrsig.h#L158>,
treating pubkeys and signatures the same way the other CHECKSIG operations
do, and in passing the (variable length) message from the stack.
CHECKSIGFROMSTACK would also be subject to the same sigops budget that
CHECKSIG has in tapscript.

On Sat, Jul 3, 2021 at 2:30 PM Jeremy  wrote:

> Awesome to hear that!
>
> Actually I don't think I did know (or I forgot/didn't catch it) that there
> was an updated spec for elements, I searched around for what I could find
> and came up empty handed. Do you have any links for that? That sounds
> perfect to me.
>
>
> On Sat, Jul 3, 2021, 10:50 AM Russell O'Connor 
> wrote:
>
>> Hi Jermy,
>>
>> As you are aware, we, and by we I mean mostly Sanket, are developing an
>> updated OP_CHECKSIGFROMSTACK implementation for tapscript on elements.  The
>> plan here would be to effectively support the an interface to the
>> variable-length extension of BIP-0340 schnorr signatures.
>>
>> BIP-0340 would dispense with DER encoding (good riddance).
>> BIP-0340 signatures are batch verifiable along with other BIP-0340
>> transaction signatures and taproot tweak verification.
>> Support for variable length messages in BIP-0340 has been discussed in <
>> https://github.com/sipa/bips/issues/207> and an implementation has
>> recently been merged in <
>> https://github.com/bitcoin-core/secp256k1/pull/844>.  The BIP has not
>> yet been updated but the difference is that the message m does not have to
>> be 32-bytes (it is recommended that the message be a 32-bit tagged hash or
>> a message with a 64-bit application specific prefix). The CHECKSIGFROMSTACK
>> operation (in tapscript) would use a stack item for this m value to
>> BIP-0340 signature verification and would not necessarily have to be 32
>> bytes.
>>
>> I think this design we are aiming for would be perfectly suited for
>> Bitcoin as well.
>>
>> On Sat, Jul 3, 2021 at 12:32 PM Jeremy via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> Reproduced below is the BIP text from Bitcoin Cash's (MIT-Licensed)
>>> specification for "CheckDataSig", more or less the same thing as
>>> CHECKSIGFROMSTACK
>>> https://github.com/bitcoincashorg/bitcoincash.org/blob/master/spec/op_checkdatasig.md.
>>> In contrast to Element's implementation, it does not have Element's bugs
>>> around verify semantics and uses the nullfail rule, and there is a
>>> specification document so it seemed like the easiest starting point for
>>> discussion v.s. drafting something from scratch.
>>>
>>> Does anyone have any issue with adapting this exact text and
>>> implementation to a BIP for Bitcoin using 2 OP_SUCCESSX opcodes?
>>>
>>> Note that with *just* CheckSigFromStack, while you can do some very
>>> valuable use cases, but without OP_CAT it does not enable sophisticated
>>> covenants (and as per
>>> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html
>>> just CAT alone enables such uses).
>>>
>>> Design questions worth considering as modifications:
>>>
>>> 1. Should CSFS require some sort of tagged hash? Very likely answer is
>>> no – tags interfere with certain use cases
>>> 2. Should CSFS split the signature’s R & S value stack items for some
>>> applications that otherwise may require OP_CAT? E.g. using a pinned R value
>>> allows you to extract a private key if ever double signed, using 2 R values
>>> allows pay-to-reveal-key contracts. Most likely answer is no, if that is
>>> desired then OP_CAT can be introduced
>>> 3. Should CSFS support a cheap way to reference the taproot internal or
>>> external key? Perhaps, can be handled with undefined upgradeable keytypes.
>>> One might want to use the internal key, if the signed data should be valid
>>> independent of the tapscript tree. One might want to use the external key,
>>> if the data should only be valid for a single tapscript key + tree.
>>> 4. Should invalid public keys types be a NOP to support future extended
>>> pubkey types?
>>>
>>>
>>>
>>> Best,
>>>
>>>
>>> Jeremy
>>>
>>>
>>> ---
>>> layout: specification
>>> title: OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY Specification
>>> category: spec
>>> date: 2018-08-20
>>> activation: 154230
>>> version: 0.6
>>> ---
>>>
>>> OP_CHECKDATASIG
>>> ===
>>>
>>> OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY check whether a signature is 
>>> valid with respect to a message and a public key.
>>>

Re: [bitcoin-dev] CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

2021-07-03 Thread Russell O'Connor via bitcoin-dev
Hi Jermy,

As you are aware, we, and by we I mean mostly Sanket, are developing an
updated OP_CHECKSIGFROMSTACK implementation for tapscript on elements.  The
plan here would be to effectively support the an interface to the
variable-length extension of BIP-0340 schnorr signatures.

BIP-0340 would dispense with DER encoding (good riddance).
BIP-0340 signatures are batch verifiable along with other BIP-0340
transaction signatures and taproot tweak verification.
Support for variable length messages in BIP-0340 has been discussed in <
https://github.com/sipa/bips/issues/207> and an implementation has recently
been merged in .  The
BIP has not yet been updated but the difference is that the message m does
not have to be 32-bytes (it is recommended that the message be a 32-bit
tagged hash or a message with a 64-bit application specific prefix). The
CHECKSIGFROMSTACK operation (in tapscript) would use a stack item for this
m value to BIP-0340 signature verification and would not necessarily have
to be 32 bytes.

I think this design we are aiming for would be perfectly suited for Bitcoin
as well.

On Sat, Jul 3, 2021 at 12:32 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Reproduced below is the BIP text from Bitcoin Cash's (MIT-Licensed)
> specification for "CheckDataSig", more or less the same thing as
> CHECKSIGFROMSTACK
> https://github.com/bitcoincashorg/bitcoincash.org/blob/master/spec/op_checkdatasig.md.
> In contrast to Element's implementation, it does not have Element's bugs
> around verify semantics and uses the nullfail rule, and there is a
> specification document so it seemed like the easiest starting point for
> discussion v.s. drafting something from scratch.
>
> Does anyone have any issue with adapting this exact text and
> implementation to a BIP for Bitcoin using 2 OP_SUCCESSX opcodes?
>
> Note that with *just* CheckSigFromStack, while you can do some very
> valuable use cases, but without OP_CAT it does not enable sophisticated
> covenants (and as per
> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html just
> CAT alone enables such uses).
>
> Design questions worth considering as modifications:
>
> 1. Should CSFS require some sort of tagged hash? Very likely answer is no
> – tags interfere with certain use cases
> 2. Should CSFS split the signature’s R & S value stack items for some
> applications that otherwise may require OP_CAT? E.g. using a pinned R value
> allows you to extract a private key if ever double signed, using 2 R values
> allows pay-to-reveal-key contracts. Most likely answer is no, if that is
> desired then OP_CAT can be introduced
> 3. Should CSFS support a cheap way to reference the taproot internal or
> external key? Perhaps, can be handled with undefined upgradeable keytypes.
> One might want to use the internal key, if the signed data should be valid
> independent of the tapscript tree. One might want to use the external key,
> if the data should only be valid for a single tapscript key + tree.
> 4. Should invalid public keys types be a NOP to support future extended
> pubkey types?
>
>
>
> Best,
>
>
> Jeremy
>
>
> ---
> layout: specification
> title: OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY Specification
> category: spec
> date: 2018-08-20
> activation: 154230
> version: 0.6
> ---
>
> OP_CHECKDATASIG
> ===
>
> OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY check whether a signature is valid 
> with respect to a message and a public key.
>
> OP_CHECKDATASIG permits data to be imported into a script, and have its 
> validity checked against some signing authority such as an "Oracle".
>
> OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY are designed to be implemented 
> similarly to OP_CHECKSIG [1]. Conceptually, one could imagine OP_CHECKSIG 
> functionality being replaced by OP_CHECKDATASIG, along with a separate Op 
> Code to create a hash from the transaction based on the SigHash algorithm.
>
> OP_CHECKDATASIG Specification
> -
>
> ### Semantics
>
> OP_CHECKDATASIG fails immediately if the stack is not well formed. To be well 
> formed, the stack must contain at least three elements [``, ``, 
> ``] in this order where `` is the top element and
>   * `` must be a validly encoded public key
>   * `` can be any string
>   * `` must follow the strict DER encoding as described in [2] and the 
> S-value of `` must be at most the curve order divided by 2 as described 
> in [3]
>
> If the stack is well formed, then OP_CHECKDATASIG pops the top three elements 
> [``, ``, ``] from the stack and pushes true onto the stack 
> if `` is valid with respect to the raw single-SHA256 hash of `` and 
> `` using the secp256k1 elliptic curve. Otherwise, it pops three 
> elements and pushes false onto the stack in the case that `` is the 
> empty string and fails in all other cases.
>
> Nullfail is enforced the same as for OP_CHECKSIG [3]. If the signature 

Re: [bitcoin-dev] OP_BEFOREBLOCKVERIFY - discussing and opcode that invalidates a spend path after a certain block

2021-06-12 Thread Russell O'Connor via bitcoin-dev
On Sat, Jun 12, 2021 at 3:59 AM Billy Tetrud  wrote:

> >  taproot annex
>
> From what I can tell, the annex is basically additional inputs to a script
> that might have additional constraints put on it. Is that right? I don't
> quite follow how moving the max height to the annex helps script caching
> here. I wasn't able to find much information on how the annex is envisioned
> to be used. Would you mind elaborating on how this would work?
>
> Also, I think the proposal as it stands already addresses script caching
> (in the Transaction Evaluation section
> ).
> The result of the script can be cached as long as the cache item also
> contains information requiring just the OP_BBV to be re-evaluated (for the
> relevant block).
>

The normal approach for this problem would be a design that adds an "annex
field" (where the details on how to delimit annex fields is not yet
standardized) for a maxheight value, and add a consensus rule that
transaction with one (or more?) maxheight fields are invalid in blocks
whose height exceeds this (or any) maxheight value.  Then you could/would
add an OP code to push a copy of the (smallest) maxheight value from the
annex onto the stack or maybe an opcode to compare a stack item with this
(every) maxheight value from the annex.  This indirection is how OP_CLTV
and OP_CSV work and this indirection makes script validity cacheable
because script remains a function of the transaction data only.  Since
transaction data doesn't change, neither does the outcome of script
evaluation. The rule that invalidates late transactions looks only at the
annex and is independent of any script evaluation considerations.


> > this auto-double-spend wallet would send every payment with an annex value
> that limits the payment to being valid only up to the next block
>
> One possible solution to that would be to require that the input to OP_BBV
> to be in the script itself and not originate from the witness.
>
> Regardless, I think the ideal solution is to not have any of these such
> rules if we can simply change the definition for what counts as
> finalization to account for the fact that BBV transactions mined close to
> their expiration. Is there a reason this finalization-redefinition is not
> an adequate solution?
>

Generally speaking, you cannot solve security problems through optional and
completely voluntary transaction relay policy.  I'll just send my
about-to-expire transactions directly to miners and they will probably mine
them because they are, in fact, valid, and pay fees.  Why wouldn't they
mine it?

(Yes, I know this logic also applies to RBF flagged transactions.  Indeed,
you cannot rely on an RBF flag to prevent double spending,  Yes I think the
RBF flag ought to be removed from consideration and every transaction
should be considered RBFable.  Maybe that even happens to be my own node's
relay policy.)

I apologize, but I don't think I have further time to engage in an idea
that I don't consider likely to achieve broad community support.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_BEFOREBLOCKVERIFY - discussing and opcode that invalidates a spend path after a certain block

2021-06-11 Thread Russell O'Connor via bitcoin-dev
On Fri, Jun 11, 2021 at 7:12 AM James MacWhyte  wrote:

> @Billy I like the idea. It is very obvious how useful an opcode like this
> would be! (My background is in wallet implementation)
>
> @Russell I do understand your concerns of monotonism, however I'm having a
> hard time really coming up with an attack vector. You said "one can design
> a wallet to passively take advantage of reorgs by always spending through
> an OP_BBV that is on the verge of becoming invalid." Unless I'm mistaken,
> this means you would need to send yourself a fresh transaction using OP_BBV
> set to, say, 2 blocks in the future, then immediately spend that output in
> a new payment to someone else and hope a reorg happens. Does this mean the
> theoretical double-spend wallet you are proposing would have to send two
> transactions every time you make a single payment, doubling the transaction
> fees and adding more uncertainty around when the second transaction would
> get confirmed?
>

Assuming the proposal is rewritten to place the maxheight into the taproot
annex in order to address the issue with caching of script validity, then
this auto-double-spend wallet would send every payment with an annex value
that limits the payment to being valid only up to the next block.  If the
payment doesn't make it into the next block, then resign it with the annex
incremented to the next block, and repeat.


> In a normal double spend scenario, there is no cost to a failed attempt,
> but much to gain from a success. With your design, there is a real cost to
> every single attempt (transaction fees) and no evidence that the rate of
> success would be higher (you still have to bet on the reorg not including
> your transaction in the first few blocks). It sounds like this new system
> would actually be less attractive to double spenders than the current model!
>
> I also agree with Billy's idea for relay rules. We already have abusable
> chain rules (e.g. a tx can be included in a block with 0 transaction fee
> [spam?]) but we add protection with relay rules (e.g. minimum fee to
> relay). I don't see how this would be any different, if the chain rules
> only enforced the block height for confirmation and the relay rules forced
> a minimum OP_BBV value in order to protect against reorg double spends.
>

The inclusion of a tx with 0 transaction fee in a block is not in of itself
an abuse.  There is nothing wrong with blocks containing such
transactions.  The *relay* of 0 transaction fee transactions is what is an
abuse because it allows one to usurp Bitcoin's gossip network for their own
arbitrary communications platform without cost.  Most Bitcoin users aren't
signing up for being a usenet provider.  So, by policy, nodes require a
cost to relay transactions so that broadcasting isn't free. Even when that
price is paid to someone else, it still is an effective limitation on abuse.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_BEFOREBLOCKVERIFY - discussing and opcode that invalidates a spend path after a certain block

2021-06-10 Thread Russell O'Connor via bitcoin-dev
As it stands today, in order to double spend a transaction during a reorg,
one must take an active role of recognizing that a reorg has happened, hope
that the new branch has completely omitted your spending transaction, and
then quickly broadcast a replacement transaction with a higher fee to
outbid your previous transaction.

However with, pretty much any change to Bitcoin that leads to non-monotonic
validity rules, that is any rule where transactions that are valid at one
tip, can become invalid at a latter tip through some other means than their
inputs being spent, such as OP_BBV, one can design a wallet to passively
take advantage of reorgs by always spending through an OP_BBV that is on
the verge of becoming invalid.  Then you just have to sit back and wait for
a suitable reorg to take back your UTXO for you without any work.  I would
probably attempt to build such a wallet for myself should any OP_BBV-like
proposal be implemented.  Think of it as an auto-double spend wallet.

Some people hold the opinion that there is no meaningful distinction
between the active and passive roles in these two scenarios.  I'm not
convinced.  I see a material difference between needing to actively
broadcast a replacement transaction and passively waiting for your
transaction to fall out of validity.  I also see a material difference
between needing the transaction to be completely omitted from the reorging
chain versus just having the transaction fail a height qualification in the
reorging chain.

(There are a few other lesser problems with an OP_BBV proposal, including
the fact that Bitcoin software tends to cache script validity so you'd want
to use the taproot annex instead of pure script; and a possible issue that
the proposal defeats limits on transaction replacement because now instead
of meeting minimum thresholds for fee bumping you can just let the previous
transaction expire and bump the fee by a fraction (though you are
effectively rate limited so maybe that is considered sufficiently
mitigated?).  But there is little point in addressing these lesser concerns
if the main concern is outstanding.)

On Thu, Jun 10, 2021 at 6:20 PM Billy Tetrud  wrote:

> @Russell In that thread, you quoted Satoshi there, but neither he nor you
> really deeply explained the concern. Would you mind elaborating on a
> situation that calls for concern here? Some deeper explanation of the
> "reorg safety" property would also be helpful. I'd very much like to know
> what your thoughts are on the specific points I brought up in the BIP as
> well.
>
> On Thu, Jun 10, 2021 at 11:35 AM Russell O'Connor <
> rocon...@blockstream.com> wrote:
>
>> This is a continuation of the thread at
>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-April/018760.html
>> on this topic.
>>
>> I still remain unconvinced that we ought to give up on the "reorg safety"
>> property that is explicitly part of Bitcoin's design.
>>
>> On Thu, Jun 10, 2021 at 1:56 PM Billy Tetrud via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> Hi Everyone,
>>>
>>> I'd like to open a discussion of an opcode I call OP_BEFOREBLOCKVERIFY
>>> (OP_BBV) which is similar to ones that have been discussed before (eg
>>> OP_BLOCKNUMBER). The opcode is very simple: the it takes as a parameter
>>> a number representing a block height, and marks the transaction invalid if
>>> the current block the transaction is being evaluated for is greater than or
>>> equal to that block height, the transaction is invalid. I wrote up a bip
>>> for OP_BBV here
>>> 
>>> .
>>>
>>> The motivation for this opcode is primarily to do switch-off kinds of
>>> transactions. Eg, an output that contains both a spend path that uses
>>> OP_BBV and a spend path that uses OP_CHECKSEQUENCEVERIFY so that before a
>>> particular block one person can spend, and after that block a different
>>> person can spend. This can allow doing things like expiring payments or
>>> reversible payments in a cheaper way. Currently, things like that require a
>>> sequence of multiple transactions, however OP_BBV can do it in a single
>>> transaction, making these applications a lot more economically feasible.
>>>
>>> The particular application I'm most interested in is more efficient
>>> wallet vaults. However, wallet vaults requires other new opcodes, and I've
>>> been given the (good, I think) advice to start off this discussion with
>>> something a bit more bite sized and manageable. So I want to keep this
>>> discussion to OP_BBV and steer away from the specifics of the wallet vaults
>>> I'm thinking of (which are more involved, requiring other new opcodes that
>>> I think makes more sense to discuss in a different thread).
>>>
>>> The main thing I'd like to discuss is the historical avoidance of and
>>> stigma toward opcodes that can cause a valid transaction to become invalid.
>>>
>>> It seems there 

Re: [bitcoin-dev] OP_BEFOREBLOCKVERIFY - discussing and opcode that invalidates a spend path after a certain block

2021-06-10 Thread Russell O'Connor via bitcoin-dev
This is a continuation of the thread at
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-April/018760.html
on this topic.

I still remain unconvinced that we ought to give up on the "reorg safety"
property that is explicitly part of Bitcoin's design.

On Thu, Jun 10, 2021 at 1:56 PM Billy Tetrud via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Everyone,
>
> I'd like to open a discussion of an opcode I call OP_BEFOREBLOCKVERIFY
> (OP_BBV) which is similar to ones that have been discussed before (eg
> OP_BLOCKNUMBER). The opcode is very simple: the it takes as a parameter a
> number representing a block height, and marks the transaction invalid if
> the current block the transaction is being evaluated for is greater than or
> equal to that block height, the transaction is invalid. I wrote up a bip
> for OP_BBV here
> 
> .
>
> The motivation for this opcode is primarily to do switch-off kinds of
> transactions. Eg, an output that contains both a spend path that uses
> OP_BBV and a spend path that uses OP_CHECKSEQUENCEVERIFY so that before a
> particular block one person can spend, and after that block a different
> person can spend. This can allow doing things like expiring payments or
> reversible payments in a cheaper way. Currently, things like that require a
> sequence of multiple transactions, however OP_BBV can do it in a single
> transaction, making these applications a lot more economically feasible.
>
> The particular application I'm most interested in is more efficient wallet
> vaults. However, wallet vaults requires other new opcodes, and I've been
> given the (good, I think) advice to start off this discussion with
> something a bit more bite sized and manageable. So I want to keep this
> discussion to OP_BBV and steer away from the specifics of the wallet vaults
> I'm thinking of (which are more involved, requiring other new opcodes that
> I think makes more sense to discuss in a different thread).
>
> The main thing I'd like to discuss is the historical avoidance of and
> stigma toward opcodes that can cause a valid transaction to become invalid.
>
> It seems there are two concerns:
>
> 1. that an opcode like might create a DOS vector where a malicious actor
> might be able to spam the mempool with transactions containing this opcode.
> 2. that an opcode like this could cause "bad" reorg behavior, where in a
> reorg, transactions that were spent become not spend and not spendable
> because they were mined too near their expiry point.
>
> While I don't want to claim anything about opcodes that can cause spend
> paths to expire in general, I do want to claim that *some* opcodes like
> that are safe - in particular OP_BBV. In the context of OP_BBV
> specifically, it seems to me like item 1 (mempool handling) is a solvable
> problem and that point 2 (reorg issues) is not really a problem since
> people should generally be waiting for 6 confirmations and software can
> warn the user to wait for 6 confirmations in relevant scenarios where a
> 6-block reorg might reverse the transaction. I discuss this in detail in
> the Design Tradeoffs and Risks
> 
>  section
> of the document I wrote for OP_BBV. I'd love to hear thoughts from others
> on here about these things and especially the discussion of these issues in
> the document I linked to.
>
> Thanks,
> BT
>
> ___
> 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] BIP - limiting OP_RETURN / HF

2021-04-16 Thread Russell O'Connor via bitcoin-dev
Firstly, a minor point is that your proposal is a soft-fork, not a
hard-fork.

But more importantly, adding limitations on OP_RETURN transactions is not
helpful.  Users who want to embed arbitrary data in their transactions can
always do so by encoding their data inside the values of legacy
multi-signature scriptpubkeys (pubkeys can be generated without knowing the
private key in order to encode non-key related data).  Not only can users
do this, users have done this in the past.  However, this behaviour is
problematic because such multi-signature "data" scriptpubkeys are
indistinguishable from "real" multisignature scriptpubkeys, and thus must
be kept in the UTXO set.  This differs from outputs using OP_RETURN which
are provably unspendable, and therefore can be safely omitted from the UTXO
set.

Thus, given that it is otherwise impossible to stop people from putting
arbitrary data values into their transactions, then we rather encourage
people who are going to encode their arbitrary data in transaction to use
the OP_RETURN outputs in order to avoid UTXO bloat.

Also, as it stands, fees already nudge various participants to consolidate
their data in the way that you suggest they do.

On Fri, Apr 16, 2021 at 9:32 AM Christopher Gilliard via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I have created a BIP which can be found here:
> https://github.com/cgilliard/bips/blob/notarization/bip-.mediawiki
>
> I'm sending this email to start the discussion regarding this proposal. If
> there are any comments/suggestions, please let me know.
>
> Regards,
> Chris
> ___
> 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] maximum block height on transaction

2021-04-09 Thread Russell O'Connor via bitcoin-dev
>From https://bitcointalk.org/index.php?topic=1786.msg22119#msg22119:

We can't safely do OP_BLOCKNUMBER.  In the event of a block chain reorg
> after a segmentation, transactions need to be able to get into the chain in
> a later block.  The OP_BLOCKNUMBER transaction and all its dependants would
> become invalid.  This wouldn't be fair to later owners of the coins who
> weren't involved in the time limited transaction.
>
> nTimeLock does the reverse.  It's an open transaction that can be replaced
> with new versions until the deadline.  It can't be recorded until it
> locks.  The highest version when the deadline hits gets recorded.  It could
> be used, for example, to write an escrow transaction that will
> automatically permanently lock and go through unless it is revoked before
> the deadline.  The feature isn't enabled or used yet, but the support is
> there so it could be implemented later.
>

Unfortunately, limiting the maximum block height for a specific transaction
would have exactly the same problem as cited above for OP_BLOCKNUMBER.

On Fri, Apr 9, 2021 at 7:21 AM Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> is there any way to specify a maximum block height on a transaction?
>
> ie: this tx is only valid if included in a block with a certain height or
> less
>
> i feel like this would be useful
> ___
> 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] Taproot Activation Meeting Reminder: April 6th 19:00 UTC bitcoin/bitcoin-dev

2021-04-06 Thread Russell O'Connor via bitcoin-dev
On Tue, Apr 6, 2021 at 12:27 PM Russell O'Connor 
wrote:

> On Tue, Apr 6, 2021 at 12:23 PM David A. Harding  wrote:
>
>>
>>   You need to upgrade by $( date -d "$MIN_LOCKIN_TIME + 11 days" )
>>
>> Ten minute estimators can say:
>>
>>   You need to upgrade by $( date -d "$MIN_LOCKIN_TIME + $((10 * 2016))
>> minutes" )
>>
>> And nine minute estimators can say:
>>
>>   You need to upgrade by $( date -d "$MIN_LOCKIN_TIME + $((9 * 2016))
>> minutes" )
>>
>
> It isn't  "$MIN_LOCKIN_TIME + $((10 * 2016)) minutes". It's
> "$MIN_LOCKIN_TIME + time until next retargeting period + $((10 * 2016))
> minutes".
>

Not only that, but the "time_until_next_retargeting_period" is a variable
whose distribution could straddle between 0 days and 14 days should the
MIN_LOCKIN_TIME end up close to a retargeting boundary.  MTP risks having a
persistent two week error in estimating the activation time (which is the
time that nodes need to strive to be upgraded) which may not be resolved
until only two weeks prior to activation!  If MIN_LOCKIN_TIME ends up close
to a retargeting boundary, then the MTP estimate becomes bimodal and
provides much worse estimates than provided by height based activation,
just as we are approaching the important 4 weeks (or is it 2 weeks?) prior
to activation!

Compare this with height based activation which simply becomes more and
more accurate in its estimation consistently (until, at less than two weeks
prior to activation, the height based estimate and the corresponding MTP
estimate have identical distributions because they both become height based
at that point in time.) This works out nicely because of the overall
simpler and easier to reason about design of height based activation.

The short of it is that MTP LOCKIN only really guarantees a minimum 2 week
notice prior to activation, which is largely the purpose of that LOCKIN
period.  Whereas height based activation gives an estimate whose
distribution smoothly and continuously becomes more and more accurate as
activation approaches, with no abrupt changes in estimates.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Taproot Activation Meeting Reminder: April 6th 19:00 UTC bitcoin/bitcoin-dev

2021-04-06 Thread Russell O'Connor via bitcoin-dev
On Tue, Apr 6, 2021 at 12:23 PM David A. Harding  wrote:

>
>   You need to upgrade by $( date -d "$MIN_LOCKIN_TIME + 11 days" )
>
> Ten minute estimators can say:
>
>   You need to upgrade by $( date -d "$MIN_LOCKIN_TIME + $((10 * 2016))
> minutes" )
>
> And nine minute estimators can say:
>
>   You need to upgrade by $( date -d "$MIN_LOCKIN_TIME + $((9 * 2016))
> minutes" )
>

It isn't  "$MIN_LOCKIN_TIME + $((10 * 2016)) minutes". It's
"$MIN_LOCKIN_TIME + time until next retargeting period + $((10 * 2016))
minutes".
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Taproot Activation Meeting Reminder: April 6th 19:00 UTC bitcoin/bitcoin-dev

2021-04-06 Thread Russell O'Connor via bitcoin-dev
I'm pretty sure that the question of "is signalling still possible by the
time enough miners have upgraded and are ready to start signalling?"
Strongly benefits from a guaranteed number of signaling periods that height
based activation offers.  Especially for the short activation period of
Speedy Trial.

The other relevant value of giving enough time for users to upgrade is not
very sensitive.  It's not like 180 days is magic number that going over is
safe and going below is unsafe.

That said, as Jeremy has pointed out before (maybe it was on IRC), we can
almost ensure a minimum of 7 retargeting periods by carefully selecting
signaling start and end dates to line up in the middle of expected
retargeting periods that we would otherwise chose with height based
activation. Why we would rather use MTP to fake a height based activation,
I will never understand. But if this is what it takes to activate taproot,
that is fine by me.

The differences between height and MTP activation are too small to matter
that much for what is ultimately transient code.  As long as MTP activation
can pass code review it is okay with me.


On Mon., Apr. 5, 2021, 06:35 Anthony Towns via bitcoin-dev, <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Sat, Apr 03, 2021 at 09:39:11PM -0700, Jeremy via bitcoin-dev wrote:
> > As such, the main conversation in this agenda item is
> > around the pros/cons of height or MTP and determining if we can reach
> consensus
> > on either approach.
>
> Here's some numbers.
>
> Given a desired signalling period of xxx days, where signaling begins
> on the first retarget boundary after the starttime and ends on the last
> retarget boundary before the endtime, this is how many retarget periods
> you get (based on blocks since 2015-01-01):
>
>  90 days: mainnet  5-7 full 2016-block retarget periods
> 180 days: mainnet 11-14
> 365 days: mainnet 25-27
> 730 days: mainnet 51-55
>
> (This applies to non-signalling periods like the activation/lock in delay
> too of course. If you change it so that it ends at the first retarget
> period after endtime, all the values just get incremented -- ie, 6-8,
> 12-15 etc)
>
> If I've got the maths right, then requiring 1814 of 2016 blocks to signal,
> means that having 7 periods instead of 5 lets you get a 50% chance of
> successful activation by maintaining 89.04% of hashpower over the entire
> period instead of 89.17%, while 55 periods instead of 51 gives you a 50%
> chance of success with 88.38% hashpower instead of 88.40% hashpower.
> So the "repeated trials" part doesn't look like it has any significant
> effect on mainnet.
>
> If you target yy periods instead of xxx days, starting and ending on a
> retarget boundary, you get the following stats from the last few years
> of mainnet (again starting at 2015-01-01):
>
>  1 period:  mainnet 11-17 days (range 5.2 days)
>  7 periods: mainnet 87-103 days (range 15.4 days)
> 13 periods: mainnet 166-185 days (range 17.9 days)
> 27 periods: mainnet 352-377 days (range 24.4 days)
> 54 periods: mainnet 711-747 days (range 35.0 days)
>
> As far as I can see the questions that matter are:
>
>  * is signalling still possible by the time enough miners have upgraded
>and are ready to start signalling?
>
>  * have nodes upgraded to enforce the new rules by the time activation
>occurs, if it occurs?
>
> But both those benefit from less real time variance, rather than less
> variance in the numbers of signalling periods, at least in every way
> that I can think of.
>
> Corresponding numbers for testnet:
>
>  90 days: testnet   5-85
> 180 days: testnet  23-131
> 365 days: testnet  70-224
> 730 days: testnet 176-390
>
> (A 50% chance of activating within 5 periods requires sustaining 89.18%
> hashpower; within 85 periods, 88.26% hashpower; far smaller differences
> with all the other ranges -- of course, presumably the only way the
> higher block rates ever actually happen is by someone pointing an ASIC at
> testnet, and thus controlling 100% of blocks for multiple periods anyway)
>
>   1 period:  testnet 5.6minutes-26 days (range 26.5 days)
>  13 periods: testnet 1-135 days (range 133.5 days)
>  27 periods: testnet 13-192 days (range 178.3 days)
>  54 periods: testnet 39-283 days (range 243.1 days)
> 100 periods: testnet 114-476 days (range 360.9 days)
>  (this is the value used in [0] in order to ensure 3 months'
>   worth of signalling is available)
> 132 periods: testnet 184-583 days (range 398.1 days)
> 225 periods: testnet 365-877 days (range 510.7 days)
> 390 periods: testnet 725-1403 days (range 677.1 days)
>
> [0] https://github.com/bitcoin/bips/pull/1081#pullrequestreview-621934640
>
> Cheers,
> aj
>
> ___
> 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

Re: [bitcoin-dev] Taproot activation proposal "Speedy Trial"

2021-03-06 Thread Russell O'Connor via bitcoin-dev
Hi Andrew,

This is a slight misunderstanding of the proposal.  Rather than an extended
lockin period (a term I've erroneously used in the past) it is really a
minimum activation height.

Thus using your figures it would instead be:

* start height = 681408 /* about May 1st */
* timeout height = 695520 /* about Aug 7th */
* min activation height = 709632 /* about Nov 13th */
* lockinontimeout = False
* signaling bit = 2
* threshold = 1815/2016 blocks (90%)

This guarantees 7 retargeting periods between start height and timeout
height.

Being able to make a guarantee about how many retargeting periods we get is
perhaps something worth pursuing given that the signaling period is so
short for this trial.

On Sat, Mar 6, 2021 at 1:04 AM Andrew Chow via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I like this idea.
>
> In terms of actual parameters, I propose that we base this Speedy Trial
> off of BIP 8 with the following parameters:
> * start height = 681408
> * timeout height = 695520
> * lockinontimeout = False
> * signaling bit = 2
> * threshold = 1815/2016 blocks (90%)
>
> For the extended lockin period, I propose 14112 blocks, which is 7
> retarget periods. Thus the earliest activation height will be 697536 and
> the latest activation height will be 709632.
>
> This will give us an approximate start time of May 1st 2021 and an
> approximate timeout time of August 7th 2021, for a total activation
> period of just over 3 months. The extended lockin period is the same
> number of blocks as the activation period so that will also be just over
> 3 months, giving us the latest activation time of November 13th, 2021.
> If miners activated as soon as possible, the earliest activation time
> would be August 21st 2021.
>
> Additionally, this timeline assumes a mid-April release of Bitcoin Core
> 0.21.1 containing these parameters. They could be changed to move up if
> the expected release date were sooner.
>
>
> Andrew Chow
>
> On 3/5/21 10:43 PM, David A. Harding via bitcoin-dev wrote:
> > On the ##taproot-activation IRC channel, Russell O'Connor recently
> > proposed a modification of the "Let's see what happens" activation
> > proposal.[1] The idea received significant discussion and seemed
> > acceptable to several people who could not previously agree on a
> > proposal (although this doesn't necessarily make it their first
> > choice).  The following is my attempt at a description.
> >
> > 1. Start soon: shortly after the release of software containing this
> > proposed activation logic, nodes will begin counting blocks towards
> > the 90% threshold required to lock in taproot.[2]
> >
> > 2. Stop soon: if the lockin threshold isn't reached within approximately
> > three months, the activation attempt fails.  There is no mandatory
> > activation and everyone is encouraged to try again using different
> > activation parameters.
> >
> > 2. Delayed activation: in the happy occasion where the lockin threshold
> > is reached, taproot is guaranteed to eventually activate---but not
> > until approximately six months after signal tracking started.
> >
> > ## Example timeline
> >
> > (All dates approximate; see the section below about BIP9 vs BIP8.)
> >
> > - T+0: release of one or more full nodes with activation code
> > - T+14: signal tracking begins
> > - T+28: earliest possible lock in
> > - T+104: locked in by this date or need to try a different activation
> process
> > - T+194: activation (if lockin occurred)
> >
> > ## Analysis
> >
> > The goal of Speedy Trial is to allow a taproot activation attempt to
> > either quickly succeed or quickly fail---without compromising safety in
> > either case.  Details below:
> >
> > ### Mitigating the problems of early success
> >
> > New rules added in a soft fork need to be enforced by a large part of
> > the economy or there's a risk that a long chain of blocks breaking the
> > rules will be accepted by some users and rejected by others, causing a
> > chain split that can result in large direct losses to transaction
> > receivers and potentially even larger indirect losses to holders due to
> > reduced confidence in the safety of the Bitcoin system.
> >
> > One step developers have taken in the past to ensure widespread adoption
> > of new consensus rules is programming in a delay between the time
> software
> > with those rules is expected to be released and when the software starts
> > tracking which blocks signal for activation.  For example:
> >
> >  Soft fork| Release| Start  | Delta
> >  -+++--
> >  BIP68 (v0.12.1)  | 2016-04-15 | 2016-05-11 | 26 days
> >  BIP141 (v0.13.1) | 2016-10-27 | 2016-11-18 | 24 days
> >
> >  Sources: BitcoinCore.org,
> https://gist.github.com/ajtowns/1c5e3b8bdead01124c04c45f01c817bc
> >
> > Speedy Trial replaces most of that upfront delay with a backend delay.
> > No matter how fast taproot's activation threshold 

Re: [bitcoin-dev] Making the case for flag day activation of taproot

2021-03-04 Thread Russell O'Connor via bitcoin-dev
Appologies as I've rearranged your comments in my reply.

On Wed, Mar 3, 2021 at 5:14 PM Matt Corallo 
wrote:

>
> On 3/3/21 14:08, Russell O'Connor via bitcoin-dev wrote:
>
> After a normal and successful Core update with LOT=false, we will have
> more data showing broad community support for the
> > taproot upgrade in hand.
>
> I think this is one of the strongest arguments against a flag day
> activation, but, as I described in more detail in the
> thread "Straight Flag Day (Height) Taproot Activation", I'm not sure we
> aren't there enough already.
>

I agree with you.  I also think we have plenty of evidence to proceed with
taproot and could proceed with a PR for such a flag day activation.  If
there is support for it to be merged, that would be fantastic.  I think we
should proceed along these lines forthwith.

However, the existence and/or release of a flag day activation code does
not in of itself preclude concurrently developing and/or releasing a BIP8
LOT=false deployment.  Activating taproot is "idempotent" after all. We
could even do a Core release with a flag day activation while we continue
to discuss BIP8 LOT=false if that gets the ball rolling.  Certainly having
a flag day activation code merged would take a lot of pressure off further
BIP8 LOT=false work.

As Aaron noted on IRC, if the sticking point here is the MUST_SIGNAL state,
then running BIP8 LOT=false alongside a flag day activation at timeout may
be the way to go.  Once a flag day deployment is released, the LOT=true
people would have their guaranteed activation and would be less interested
in an alternative client. And without a MUST_SIGNAL state, I believe the
LOT=false deployment won't lead any hashpower that is following
standardness rules to create invalid blocks.


> > In the next release, 6 months later or so, Core could then confidently
> deploy a BIP8 LOT=true
>
> Could you clarify what an acceptable timeline is, then? Six months from
> release of new consensus rules to activation (in
> the case of a one-year original window) seems incredibly agressive for a
> flag-day activation, let alone one with
> forced-signaling, which would require significantly higher level of
> adoption to avoid network split risk. In such a
> world, we'd probably get Taproot faster with a flag day from day one.
>

Whatever timeline people are in favour of.  I think having a year or more
between the LOT=true or flag day more and the anticipated second release
date is fair myself.
That would suggest a 2-year timeout from the start to give plenty of room.

Of course, if we start with a flag day from the start then we can just do 1
year and we don't need a second deployment.

We could also do a "Let’s see what happens" with a short 3 or 4-month
deployment and still do a follow up activation if that is more agreeable.
That would give a net of about 1.5 years or so because we don't need to
anticipate the second relase date.

I'm good with whatever, and I'm happy to make more concrete suggestions if
that is necessary.  I think there exist acceptable timelines here.


> > client, should it prove to be necessary.  A second Core deployment of
> LOT=true would mitigate some of the concerns with
> > LOT=false, but still provide a period beforehand to objective actions
> taken by the community in support of taproot.  We
> > don't even have to have agreement today on a second deployment of
> LOT=true after 6 months to start the process of a
> > LOT=false deployment. The later deployment will almost certainly be
> moot, and we will have 6 months to spend debating
> > the LOT=true deployment versus doing a flag day activation or something
> else.
>


> That was precisely the original goal with the LOT=false movement - do
> something easy and avoid having to hash out all
> the technical details of a second deployment. Sadly, that's no longer
> tennable as a number of people are publicly
> committed to deploying LOT=true software on the network ASAP.
>



First things last:

> Even today, I still think that starting with BIP8 LOT=false is, generally
> speaking, considered a reasonably safe
> > activation method in the sense that I think it will be widely considered
> as a "not wholly unacceptable" approach to
> > activation.
>
> How do you propose avoiding divergent consensus rules on the network,
> something which a number of commentors on this
> list have publicly committed to?
>

Firstly, it is an open network.  Anyone can join and run whatever consensus
rules they want.  People have run divergent consensus rules on the network
in the past and it will continue to do so in the future.
It is troublesome when it happens in mass, but it isn't fatal.  We can't
prevent it, and we should continue working to keep the protocol robust in
the face of it.
And

Re: [bitcoin-dev] Making the case for flag day activation of taproot

2021-03-03 Thread Russell O'Connor via bitcoin-dev
While I support essentially any proposed taproot activation method,
including a flag day activation, I think it is premature to call BIP8 dead.

Even today, I still think that starting with BIP8 LOT=false is, generally
speaking, considered a reasonably safe activation method in the sense that
I think it will be widely considered as a "not wholly unacceptable"
approach to activation.

After a normal and successful Core update with LOT=false, we will have more
data showing broad community support for the taproot upgrade in hand.  In
the next release, 6 months later or so, Core could then confidently deploy
a BIP8 LOT=true client, should it prove to be necessary.  A second Core
deployment of LOT=true would mitigate some of the concerns with LOT=false,
but still provide a period beforehand to objective actions taken by the
community in support of taproot.  We don't even have to have agreement
today on a second deployment of LOT=true after 6 months to start the
process of a LOT=false deployment. The later deployment will almost
certainly be moot, and we will have 6 months to spend debating the LOT=true
deployment versus doing a flag day activation or something else.

I don't think we need to start self-sabotaging our efforts to get taproot
activated this year just yet.  Let's cherry-pick the commits of PR #19573
to split it up into non-MUST_SIGNAL and MUST_SIGNAL components, and get
some reviews on that first.  Then afterwards we can decide if BIP8 is dead
or not.

On Wed, Mar 3, 2021 at 9:39 AM Chris Belcher via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> The bitcoin world is close to total gridlock on the question of how to
> activate taproot. There's no agreement on activation[1][2], and if an
> agreement isn't reached then nothing happens. That would be really
> terrible because we'd miss out on the benefits of taproot and
> potentially other future soft forks.
>
> A major problem with BIP8 is that it would result to a situation where
> different parts of the bitcoin ecosystem run different consensus rules.
> Some people will run LOT=true and others LOT=false. Worst of all, it
> becomes vulnerable to a twitter/reddit/social media blitz which could
> attempt to move the date of miner activation around.
>
> Twitter and reddit drama provide a perfect cover for social attacks on
> bitcoin.
>
> Forced signalling leads to brinksmanship. Where two or more sides
> (backed up by social media drama) enter into a game of chicken with
> deployed nodes. If one of them doesn't concede then we get a damaging
> chain split. And the $1 trillion in value that the bitcoin network
> protects is put at risk. From the point of view of a miner or big
> exchange stuck in the middle, if they look at the ecosystem of twitter
> and reddit (especially if you think about all the problems with bots and
> sockpuppets) they have no idea which consensus rules they should
> actually follow and exactly what date they take effect. Miners,
> exchanges, merchants and the rest of the ecosystem exist to serve their
> customers and users, and trouble happens when they don't know what their
> customers really want. Social media attacks are not just a theoretical
> concern; back during the block size drama, the bitcoin reddits were
> targetted by bots, sockpuppets and brigading[3].
>
> Enter flag day activation. With a flag day there can be no
> brinksmanship. A social media blitz cant do anything except have its own
> followers fork away. Crucially, miner signalling cant be used to change
> the activation date for nodes that didn't choose to and just passively
> follow signalling. Changing the activation date requires all those users
> to actually run different node software.
>
> Flag day activation works simply: we choose a block height and after
> that block height the new taproot rules become enforced.
>
>
> Supporters of the permissionless, "users rule" approach of LOT=true
> should be happy because it completely takes miners out of activation.
>
> Supporters of the safe, conservative approach of LOT=false can be made
> happy with a few ways of derisking:
>
> * Getting mining pools, businesses and users to look at the code and ask
> if they (a) think its either neutral or good for their business or use
> case and (b) they believe others view it similarly and that the
> consensus changes proposed have a good social consensus around them.
>
> * Setting the flag day far in the future (18 months or 2 years in the
> original proposal[3]).
>
>
> == What if flag day activation is used maliciously? ==
>
> What if one day the Core developer team is co-opted and uses the flag
> day method to do something bad? For example, a soft fork where sending
> to certain blacklisted addresses is not allowed. The bitcoin user
> community who wants to resist this can create their own
> counter-soft-fork full node, where the first block after the flag day
> MUST pay to one of those addresses on the blacklist. This forces a chain
> split between the 

Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)

2020-10-08 Thread Russell O'Connor via bitcoin-dev
On Thu, Oct 8, 2020 at 11:00 AM David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Rather than go through that again, I'd prefer we use the
> backwards compatible proposal from BIPs PR#945 and, if we want to
> maximize safety, consensus restrict v1 witness program size, e.g. reject
> transactions with scriptPubKeys paying v1 witness programs that aren't
> exactly 32 bytes.
>

Adding some kind of relay policy rule would be easier than a consensus
rule, and maybe effective enough.  (This comment is not intended to endorse
any one proposal over another.)


> Hopefully by the time we want to use segwit v2, most software will have
> implemented length limits and so we won't need any additional consensus
> restrictions from then on forward.
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] On the compatibility of Bech32 and Shamir's Secret Sharing

2020-08-03 Thread Russell O'Connor via bitcoin-dev
With the help of Pieter I've recently made some interesting mathematical
observations about Bech32 codewords and Shamir's secret sharing:

(1) Affine combinations of two Bech32 codewords is again a valid Bech32
codeword.
(2) Lagrange polynomials form a partition of unity.

The consequences of these facts is that when you perform Shamir's secret
sharing where all your shares have valid Bech32 checksums, then the
resulting secret will also have a valid Bech32 checksum.  Conversely, if
your secret has a valid Bech32 checksum, and your random shares have valid
Bech32 checksums, then all your derived shares will have valid Bech32
checksums.  This can form a basis on which we can build a simple secret
sharing scheme for dividing up a BIP-32 master seed.

In order to illustrate this, I'll describe an example scheme for *k*-of-*n*
Shamir's secret sharing scheme where *2 <= k* <= *n* <= 31.

Suppose we have a 128-bit master seed 0xb6721d937d82f238672de4db91b87d0c.
We encode this secret as the following Bech32 codeword: "
donotusesss321s2name00keepmymasterseedunderwraps2n89wr".  Let's deconstruct
this codeword.

"donotusesss32": A Bech32 hrp for this example scheme.
"1": The Bech32 separator.
"s": The first data character is the index of this share. Each index is a
Bech32 character.  In this scheme the secret share is always at index "s",
which stands for "secret".
"2": The second data character is the threshold.  In this example we are
using a 2-of-n threshold.  We use the digits 2-9 for thresholds upto 9.  We
use Bech32 characters a-y for thresholds from 10 to 31.
"name00": The next 6 characters are an id for this set of shares.  This id
isn't part of the secret data. It is used to ensure that the shares you are
reconstructing were generated for the same secret.  This id just needs to
be unique for all the secrets that you are dividing up with this scheme.
The id can be chosen randomly, sequentially, or even set to the constant
such as "qq" if you do not want to use it for identification.
"keepmymasterseedunderwraps": This is the 128-bit secret master seed
0xb6721d937d82f238672de4db91b87d0c encoded in Bech32.  The master seed can
be a 128-bit, 256-bit or 512-bit value.
"2n89wr" is the Bech32 checksum.

We will generate shares for a 2-of-3 threshold.  We generate the first
share at index "a".  In this example we generate "
donotusesss321a2name00q0h5aajczn04g9sh0wtsl2f0y0g3vlkr".

"donotusesss32": The Bech32 hrp for this example scheme.
"1": The Bech32 separator.
"a": The first data character is the index of this share which we have
chosen to be "a".
"2": The second data character is the threshold, which is 2.
"name00": The next 6 characters is the id we chose above for this set of
shares.
"q0h5aajczn04g9sh0wtsl2f0y0": This is 26 randomly selected bech32 characters
"g3vlkr" is the Bech32 checksum.

We generated the next two shares at index "c" and and index "d".  These
shares are generated using characterwise Lagrange interpolation of the
secret share and the above randomly generated share.
The resulting shares are "
donotusesss321c2name00chzu58ep57hd9xmaw6zmuyjeau0kq4mr" and "
donotusesss321d2name00ung8rmkf2snftj57zu45g7z84hzmzk4r"

Notice that the resulting strings have
(1) valid checksums;
(2) have correct indices;
(3) have the correct threshold values;
(4) have the correct ids.

This scheme still enjoys the perfect information hiding property of
Shamir's secret sharing.  Even when you know *k*-1 shares, every possible
master seed value has exactly one set of shares that includes those
particular *k*-1 shares, so knowing *k*-1 shares tells you nothing about
the secret data value.

One nice property of Lagrange interpolation is that it is simple enough to
compute by hand with the help of a few lookup tables.  Bech32 checksums can
also be computed and checked by hand with the help of lookup tables.  While
the majority of users wouldn't do hand computations, those motivated users
who have a healthy distrust of digital devices can generate and manipulate
the secret shares by hand.  The Bech32 checksum property means that after
generating the shares by hand, you can then validate the checksums by hand.
With extremely high probability, you will catch any computation error you
make.  My SSS32 repository at https://github.com/roconnor-blockstream/SSS32
has a postscript file that generates the lookup tables needed for hand
computation, although the document is a bit disorganized at the moment.

The main deficiency of the scheme presented here is that we want a longer
checksum than used in BIP-173 that is more suitable for error correction,
rather than simply error detection.

This example scheme was inspired in part by SLIP-32
 with the
intent to be a hand computable version of the same idea.

P.S. It is possible that this all could be made obsolete by a threshold
musig signature scheme.
___
bitcoin-dev mailing 

Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses

2020-07-15 Thread Russell O'Connor via bitcoin-dev
The bold values are the witness program lengths and address lengths of the
segwit v0 programs (BIP-141), which clearly need to be covered in my
proposed amendment.  32 bytes is also the proposed witness program length
for segwit v1 that would correspond to a taproot (BIP-341) program.

On Wed, Jul 15, 2020 at 5:05 PM Greg Sanders  wrote:

> Can you make it clear what the bold vs not-bold numbers mean?
>
> On Wed, Jul 15, 2020 at 4:56 PM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> On Wed, Nov 13, 2019 at 1:31 AM Pieter Wuille via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>>
>>> That brings me to Matt's point: there is no need to do this right now.
>>> We can simply amend BIP173 to only permit length 20 and length 32 (and only
>>> length 20 for v0, if you like; but they're so far apart that permitting
>>> both shouldn't hurt), for now. Introducing the "new" address format (the
>>> one using an improved checksum algorithm) only needs to be there in time
>>> for when a non-32-byte-witness-program would come in sight.
>>>
>>
>> As a prerequisite to taproot activation, I was looking into amending
>> BIP173 as stated above.  However after reviewing
>> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb#detection-of-insertion-errors
>> it seems that insertions of 5 characters or more is "safe" in the sense
>> that there is low probability of creating a valid checksum by doing so
>> randomly.
>>
>> This means we could safely allow witness programs of lengths *20*, 23,
>> 26, 29, *32*, 36, and 40 (or 39).  These correspond to Bech32 addresses
>> of length *42*, 47, 52, 57, *62*, 68, and 74 (or 73).  We could also
>> support a set of shorter addresses, but given the lack of entropy in such
>> short addresses, it is hard to believe that such witness programs could be
>> used to secure anything.  I'm not sure what the motivation for allowing
>> such short witness programs was, but I'm somewhat inclined to exclude them
>> from the segwit address format.
>>
>> Given that we would only be able to support one of 39 or 40 byte witness
>> programs, it is sensible to choose to allow 40 byte witness programs to be
>> addressable.  This is the maximum witness program size allowed by BIP 141.
>>
>> So my proposal would be to amend BIP173 in such a way to restrict "bc"
>> and "tb" segwit address formats to require witness programs be of size
>> *20*, 23, 26, 29, *32*, 36, or 40.  Witness programs of other sizes
>> (between 2 and 40) would, of course, still be legal in accordance with BIP
>> 141; however they would be unaddressable by using this "bc" and "tb"
>> prefix.  Another address format would be needed to support other witness
>> sizes, should the need ever arise.
>>
>> --
>> Russell O'Connor
>> ___
>> 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] Bech32 weakness and impact on bip-taproot addresses

2020-07-15 Thread Russell O'Connor via bitcoin-dev
On Wed, Nov 13, 2019 at 1:31 AM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> That brings me to Matt's point: there is no need to do this right now. We
> can simply amend BIP173 to only permit length 20 and length 32 (and only
> length 20 for v0, if you like; but they're so far apart that permitting
> both shouldn't hurt), for now. Introducing the "new" address format (the
> one using an improved checksum algorithm) only needs to be there in time
> for when a non-32-byte-witness-program would come in sight.
>

As a prerequisite to taproot activation, I was looking into amending BIP173
as stated above.  However after reviewing
https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb#detection-of-insertion-errors
it seems that insertions of 5 characters or more is "safe" in the sense
that there is low probability of creating a valid checksum by doing so
randomly.

This means we could safely allow witness programs of lengths *20*, 23, 26,
29, *32*, 36, and 40 (or 39).  These correspond to Bech32 addresses of
length *42*, 47, 52, 57, *62*, 68, and 74 (or 73).  We could also support a
set of shorter addresses, but given the lack of entropy in such short
addresses, it is hard to believe that such witness programs could be used
to secure anything.  I'm not sure what the motivation for allowing such
short witness programs was, but I'm somewhat inclined to exclude them from
the segwit address format.

Given that we would only be able to support one of 39 or 40 byte witness
programs, it is sensible to choose to allow 40 byte witness programs to be
addressable.  This is the maximum witness program size allowed by BIP 141.

So my proposal would be to amend BIP173 in such a way to restrict "bc" and
"tb" segwit address formats to require witness programs be of size *20*,
23, 26, 29, *32*, 36, or 40.  Witness programs of other sizes (between 2
and 40) would, of course, still be legal in accordance with BIP 141;
however they would be unaddressable by using this "bc" and "tb" prefix.
Another address format would be needed to support other witness sizes,
should the need ever arise.

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


Re: [bitcoin-dev] MIN_STANDARD_TX_NONWITNESS_SIZE and OP_RETURN

2020-05-27 Thread Russell O'Connor via bitcoin-dev
I don't believe that 60 bytes is a problem here.  SHA256 padding includes a
length value of the original message data. Thus a padded non-64 byte
transaction can never be the same as any padded 64-byte value, and
therefore after applying the SHA256 compression function the resulting
hashes cannot be identical (unless SHA256 itself is broken).

P.S. SHA256 also includes 10* padding, which also suffices to ensure
messages of different lengths have different padding.

On Sat, May 23, 2020 at 8:52 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Thomas,
>
> > So I think the question to ask would be "why can't we just make sure
> it's not 64?"
>
> If we accept a 60-byte tx, then SHA-256 will pad it to 64 bytes, and it
> may still be possible to mount CVE-2017-12842 attack with 32-bits of work.
> Of course some other details will be changed from the standard SHA-256 in
> mounting this attack, but from my poor understanding it seems safer to just
> avoid the area around length 64.
>
> It *might* be safe to accept 65-byte or larger (but do not believe me, I
> only play a cryptographer on the Internet), but that does not help your
> specific application, which uses 60 byte tx.
>
> Regards,
> ZmnSCPxj
>
> >
> > On Sat, May 23, 2020 at 11:24 AM Greg Sanders 
> wrote:
> >
> > > AFAIU the number was picked to protect against CVE-2017-12842
> covertly. See: https://github.com/bitcoin/bitcoin/pull/16885 which
> updated the text to explicitly mention this fact.
> > >
> > > On Sat, May 23, 2020 at 11:20 AM Thomas Voegtlin via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> > >
> > > > Hello list,
> > > >
> > > > I have been trying to CPFP a transaction using OP_RETURN, because the
> > > > remaining output value would have been lower than the dust threshold.
> > > >
> > > > The scriptPubkey of the output was OP_RETURN + OP_0, and there was a
> > > > single p2wsh input.
> > > >
> > > > The result is a 60 bytes transaction (without witness), that gets
> > > > rejected because it is lower than MIN_STANDARD_TX_NONWITNESS_SIZE,
> which
> > > > is equal to 82 bytes.
> > > >
> > > > Why is that value so high? Would it make sense to lower it to 60?
> > > >
> > > > Thomas
> > > > ___
> > > > 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] BIP-341: Committing to all scriptPubKeys in the signature message

2020-05-02 Thread Russell O'Connor via bitcoin-dev
On Sat, May 2, 2020 at 10:26 AM Anthony Towns  wrote:

>
> except that we'd arguably still be missing:
>
> is this a coinbase output? (Coin.fCoinBase)
> what was the height of the coin? (Coin.nHeight)
>
> Maybe committing to the coinbase flag would have some use, but committing
> to the height would make it hard to chain unconfirmed spends, so at
> least that part doesn't seem worth adding.
>

To add to this point, the height of the coin is something that is *not*
currently covered by any signature mode and including it would constitute a
change of an entirely different  caliber; a change that I would strongly
caution against for your above reason and more.

The coinbase output flag is currently covered by the signature as the
outpoint hash has the required information (its prevout index of 0x
is only legal in a coinbase transaction).  While I'm not particularly
enthusiastic about making it easier to distinguish coinbase outputs from
other outputs, and I worry a little about alternative designs for
implementing the Bitcoin protocol where this information is not so readily
available, I suppose I won't really oppose adding it.  However, I don't
think anyone is seriously proposing it.
-
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIP-341: Committing to all scriptPubKeys in the signature message

2020-05-02 Thread Russell O'Connor via bitcoin-dev
> If you didn't verify the output scriptPubKeys, you would *only* be able
> to care about fees since you couldn't verify where any of the funds went?
> And you'd only be able to say fees are "at least x", since they could be
> more if one of the scriptPubKeys turned out to be OP_TRUE eg. That might
> almost make sense for a transaction accelerator that's trying to increase
> the fees; but only if you were doing it for someone else's transaction
> (since otherwise you'd care about the output addresses) and only if you
> were happy to not receive any change? Seems like a pretty weird use case?
>

You are right of course.  I was thinking of cases where you only care about
where some of the outputs go but not all.  But of course, even in that case
you will need to wade through all of the output ScriptPubKeys anyways.
The current design shares the hashOuputs value with the one computed with
BIP-143, and that is a somewhat valuable property to keep.

Thanks for setting me straight.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIP-341: Committing to all scriptPubKeys in the signature message

2020-05-01 Thread Russell O'Connor via bitcoin-dev
While I'm not entirely convinced yet that accertaining non-ownership of an
input is a robust method of solving the problem here, I also see little
reason not to amend BIP-341 as proposed. The ScriptPubKeys in question is
already indirectly covered through the outpoints, so it is just a matter of
optimization.  Furthermore in the consensus code, the ScriptPubKeys are
part of the UTXO data set, and it is already being retrieved as part of the
transaction checking process, so it is readily available.

I'm not sure how much my opinion on the topic matters, but I did include
this kind of functionality in my design for Simplicity on Elements, and I
have been leaning towards adding this kind of functionality in my Bitcoin
demo application of Simplicity.

Regarding specifics, I personally think it would be better to keep the
hashes of the ScriptPubKeys separate from the hashes of the input values.
This way anyone only interested in input values does not need to wade
through what are, in principle, arbitrarily long ScriptPubKeys in order to
check the input values (which each fixed size).  To that end, I would also
(and independently) propose separating the hashing of the output values
from the output ScriptPubKeys in `sha_outputs` so again, applications
interested only in summing the values of the outputs (for instance to
compute fees) do not have to wade through those arbitrarily long
ScriptPubKeys in the outputs.

On Thu, Apr 30, 2020 at 4:22 AM Andrew Kozlik via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi everyone,
>
> In the current draft of BIP-0341 [1] the signature message commits to the
> scriptPubKey of the output being spent by the input. I propose that the
> signature message should commit to the scriptPubKeys of *all* transaction
> inputs.
>
> In certain applications like CoinJoin, a wallet has to deal with
> transactions containing external inputs. To calculate the actual amount
> that the user is spending, the wallet needs to reliably determine for each
> input whether it belongs to the wallet or not. Without such a mechanism an
> adversary can fool the wallet into displaying incorrect information about
> the amount being spent, which can result in theft of user funds [2].
>
> In order to ascertain non-ownership of an input which is claimed to be
> external, the wallet needs the scriptPubKey of the previous output spent by
> this input. It must acquire the full transaction being spent and verify its
> hash against that which is given in the outpoint. This is an obstacle in
> the implementation of lightweight air-gapped wallets and hardware wallets
> in general. If the signature message would commit to the scriptPubKeys of
> all transaction inputs, then the wallet would only need to acquire the
> scriptPubKey of the output being spent without having to acquire and verify
> the hash of the entire previous transaction. If an attacker would provide
> an incorrect scriptPubKey, then that would cause the wallet to generate an
> invalid signature message.
>
> Note that committing only to the scriptPubKey of the output being spent is
> insufficient for this application, because the scriptPubKeys which are
> needed to ascertain non-ownership of external inputs are precisely the ones
> that would not be included in any of the signature messages produced by the
> wallet.
>
> The obvious way to implement this is to add another hash to the signature
> message:
> sha_scriptPubKeys (32): the SHA256 of the serialization of all
> scriptPubKeys of the previous outputs spent by this transaction.
>
> Cheers,
> Andrew Kozlik
>
> [1]
> https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#common-signature-message
> [2]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014843.html
> ___
> 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] Overview of anti-covert-channel signing techniques

2020-03-22 Thread Russell O'Connor via bitcoin-dev
On Sun, Mar 22, 2020 at 5:43 AM Tim Ruffing  wrote:

> On Sat, 2020-03-21 at 12:59 -0400, Russell O'Connor wrote:
> > Public keys are deterministic and can be spot checked.  In fact,
> > AFAIU if hardened HD key derivations are not used, then spot checking
> > is very easy.
> >
> > While spot checking isn't ideal, my original concern with the
> > synthetic none standard proposal was that it is inherently non-
> > deterministic and cannot ever be spot checked.  This is why anti-
> > covert signing protocols are so important if we are going to use
> > synthetic nonces.
>
> If spot checking means checking a few instances, then I think this is a
> pretty weak defense. What if the device starts to behave differently
> after a year?
>

I agree, which is why there perhaps is merit in using a non-hardered
derivation path so that the software side of a hardware wallet can check
the pubkey. Though I understand there are some disadvantages to the
non-hardened paths.

However, spot checking can even be done retroactively (and thoroughly).
Again, I agree that this is less than ideal, but does let you take some
action once you notice a deviation.

Your claim is that if we don't fix the pubkey issue there is no point in
fixing the signature issue.  I disagree.  While I think both issues need to
be fully addressed, the issues around the original proposed
non-deterministic signature scheme are far more severe. The proposal would
move us from a deterministic scheme, where spot checks are possible, with
all the caveats that entails, to a non-deterministic scheme where spot
checks are impossible.  My hope is that we can standardise a scheme that
has the advantages of non-determinism without the threat of covert channels.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Overview of anti-covert-channel signing techniques

2020-03-21 Thread Russell O'Connor via bitcoin-dev
On Sat, Mar 21, 2020 at 12:46 PM Tim Ruffing via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Pieter,
>
> Let's take a step back first. If we believe that malicious hardware
> wallets are big enough of a concern, then signing is only part of the
> problem. The other issue is key generation. The PRG from which the seed
> is derived can be malicious, e.g., just H(k_OO,counter) for a key k_OO
> chosen by the hardware manufacturer. I haven't seen an argument why
> attacks during the signing model should more realistic than attacks
> during key generation, so I'd be very hesitant to deploy anti-covert
> channel singing protocols without deploying protocols for key
> generation that are secure in the same attacker model.
>

Public keys are deterministic and can be spot checked.  In fact, AFAIU if
hardened HD key derivations are not used, then spot checking is very easy.

While spot checking isn't ideal, my original concern with the synthetic
none standard proposal was that it is inherently non-deterministic and
cannot ever be spot checked.  This is why anti-covert signing protocols are
so important if we are going to use synthetic nonces.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Removing Single Point of Failure with Seed Phrase Storage

2020-03-06 Thread Russell O'Connor via bitcoin-dev
On Wed, Feb 26, 2020 at 2:56 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> As a replacement for paper, something like this makes sense v.s. what you
> do with a ledger presently.
>
> However, shamir's shares notoriously have the issue that the key does
> exist plaintext on a device at some point.
>
> Non-interactive multisig has the benefit of being able to sign
> transactions without having keys in the same room/place/device ever.
> --
> @JeremyRubin 
> 
>

The way I see it, the main benefit of Shamir's Secret Sharing is for those
people who are already willing or wanting to be able to sign transactions
on a single device, in a single room, etc., but would prefer not to keep
their secret backup in a single room/place/device.  It is one thing to go
and gather your shares whenever you need to recover from a broken/wiped
hardware wallet versus having to go gather your shares whenever you want to
make a transaction.  (I do agree that SSS is not a suitabl for creating a
multisig from multiple participants.)

This thread inspired me tidy up and post my concept for creating secret
shares using paper computers (slide charts) and can be found at
https://github.com/roconnor-blockstream/SSS32/blob/master/SSS32.ps. It is a
design for splitting a secret encoded in the Bech32 alphabet into 2-of-n
shares (where n <= 31) using pencil, paper and lookup tables.  There are
numerous issues  and
more that need to be addressed before one could even think about using it
for actual valuable data.  Right now I'm mostly interested to find out if
paper sharing is really feasible.

A secret of 26 random Bech32 characters provides 130 bits of entropy, and a
secret of 51 random Bech32 characters provides 255 bits of entropy.
However, to enable robust recovery, the secret data ought to contain an
error correcting code.  Because each character of the secret is
independently split into shares, any single character error in one of the
shares translates into a single character error in the recovered secret
which can be corrected by the error correcting code.  See the exercise at
the end of "Verifying Bech32 Checksums with Pen and Paper" <
http://r6.ca/blog/20180106T164028Z.html> on how to attach the Bech32 error
correcting code to a raw secret string by hand.  However, protecting the
secret data is so important that one would want to design a checksum BCH
code longer than 6 characters to get strong error correcting capabilities.

I still don't know if this proposed method all a good idea or not.  I've
only experimented with encoding and recovering a 10 character "secret"
data.  Generating 2-of-n shares is quite easy as all the shares are a
function of the secret share and the first random share.  It only takes
lookup up a pair of coordinates in a table to generate one character for
each of the n shares together.  Recovering the secret data is more work;
however, if your plan is to recover a hardware wallet anyways, it is
reasonable for the hardware wallet to do the recovery from the shares
itself for you.  Generating the error correcting code by hand is a bit more
worrying, because it doesn't do you much good if your generate an incorrect
checksum.  However, by doing 1 or 2 manual passes to verify the checksum is
maybe adequate.  Also passing the secret data into the hardware wallet you
wish to use, along with its checksum, would let the hardware wallet tell
you if there was an error in the checksum.  I think creating more general
3-of-n schemes can be implemented too, but require work similar to recovery
to generate rather than the simple lookup table process.  Generating 4-of-n
and higher schemes may also be possible, but would require even more hand
computation (i.e. computing lagrange polynomials.)

Maybe this scheme is workable for the subset of people that this would
appeal to.  In anycase, my document is open source and available for those
who want to tinker with it.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Fwd: BIP 340 updates: even pubkeys, more secure nonce generation

2020-02-25 Thread Russell O'Connor via bitcoin-dev
On Sun, Feb 23, 2020 at 11:26 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> 2. Nonce generation
>
> All other semantical changes are around more secure nonce generation
> in BIP 340, dealing with various failure cases:
>
> * To protect against fault injection attacks it is recommended to
> include actual signing-time randomness into the nonce generation
> process. This was mentioned already, but the update elaborates much
> more about this, and integrates this randomness into the standard
> signing process.
>

I do worry that standardizing on a non-deterministic nonce generation
scheme makes the problem of private key exfiltration a much bigger concern
in the application of hardware signing devices.
While sorely imperfect, with a deterministic nonce scheme, we at least have
the option of spot checking hardware devices to see if they are producing
signatures in accordance with their specified nonce scheme.  But short of
providing some kind of certificate, we won't be able to do such checks
against hardware devices that use the proposed synthetic nonce. (Question:
can a hardware device safely output the random value 'a' it used its
"certificate"?  AFAIU 'a' is not considered secret data; it just needs to
be not under attacker control.  Should hardware wallets be encouraged to
return this value?)

The best way to mitigate this is to use the Nonce exfiltration protection
mentioned; however there are no references on how to do this.  Ideally we'd
standardize this Nonce exfiltration protection scheme within this synthetic
nonce scheme.  However, I don't think it is worth holding this BIP up on
that; it seems reasonable to introduce a new section to this BIP addressing
that problem in the future.  Maybe instead we can get references to more
information about this Nonce exfiltration protection that is mentioned?

Really I just want to do whatever we reasonably can do to avoid a world
where we end up providing hardware signing devices with a hard to detect
underhanded communications channel.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript

2019-12-05 Thread Russell O'Connor via bitcoin-dev
After chatting with andytoshi and others, and some more thinking I've been
convinced that my specific concern about other users masquerading other
people pubkeys as their own in complex scripts is actually a non-issue.

No matter what you write in Script (today), you are limited to expressing
some policy that is logically equivalent to a set of conditions and
signatures on pubkeys that can be expressed in disjunctive normal form.  We
can write such a policy as

(C[1] && PK[1,1] && ... && PK[1,m[1]]) || ... || (C[n] && PK[n,1] && ... &&
PK[n,m[n]])

where C[i] is some conjunction of conditions such as timelock constraints,
or hash-lock constraints or any other kind of proof of publication, and
where PK[i,j] is a requirement of a signature against a specific public key.

>From Alice's point of view, she can divide set of clauses under the
disjunction into those that contain a pubkey that she considers (partially)
under her control and those clauses that she does not control (even though
as we shall see those other keys might actually be under Alice's control,
unbeknownst to her). To that end, let us consider a specific representative
policy.

(C[1] && APK[1]) || (C[2] && APK[2] && BPK[2]) || (C[3] && BPK[3])

where Alice considers herself in control of APK[1] and APK[2], and where
she considers Bob in control of BPK[2] and BPK[3] and where C[1], C[2], and
C[3] are different conditions, let's say three different hash-locks.  We
will also say that Alice has ensured that her pubkeys in different clauses
are different (i.e. APK[1] != APK[2]), but she doesn't make any such
assumption for Bob's keys and neither will we.

When Alice funded this Script, or otherwise accepted it for consideration,
she agreed that she wouldn't control the redemption of the UTXO as long as
the preimage for C[3] is published.  In particular, Alice doesn't even need
to fully decode the Script semantics for that clause beyond determining
that it enforces the C[3] requirement that she cares about. Even if Bob was
masquerading Alice's pubkey as his own (as in BPK[3] = APK[1] or BPK[3] =
APK[2]), and he ends up copying her signature into that clause, Alice ends
up with C[3] published as she originally accepted as a possibility.  Bob
masquerading Alice's pubkey as his own only serves to hamper his own
ability to sign for his clauses (I mean, Bob might be trying to convince
some third party that Alice signed for something she didn't actually sign
for, but such misrepresentations of the meaning of digital signatures is
outside our scope and this just serves as a reminder not to be deceived by
Bob's tricks here).

And the same argument holds for BPK[2].  Even if BPK[2] = APK[1] and Bob
tries to copy Alice's signature into the C[2] condition, he still needs a
countersignature with her APK[2], so Alice remains in control of that
clause.  And if BPK[2] = APK[2] then Bob can only copy Alice's signature on
the C[2] condition, but in that case she has already authorised that
condition.  Again, Bob masquerading Alice's pubkey as his own only serves
to hamper his own ability to sign for his clauses.

So what makes our potential issue here safe, versus the dangers that would
happen in  where Bob
masqurades Alice's UTXO as his own?  The key problem in the UTXO case isn't
so much Bob masquerading Alice's pubkey as his own, as it is an issue with
Alice reusing her pubkeys and Bob taking advantage of that.  We do, in
fact, have exactly the same issue in Script.  If Alice were to reuse
pubkeys such that APK[1] = APK[2], then Bob could take her signature for
C[1] and transplant it to redeem under condition C[2].  We see that it is
imperative that Alice ensures that she doesn't reuse pubkeys that she
considers under her control for different conditions when she wants her
signature to distinguish between them.

For various reasons, some historical, it is much harder to avoid pubkey
reuse for different UTXOs than it is to avoid pubkey reuse within a single
script.  We often use Bitcoin addresses in non-interactive ways, such as
putting them on flyers or painting them on walls and such.  Without a
standard for tweaking such pubkeys in a per-transaction way, we end up with
a lot of pubkey reuse between various UTXOs.  However, within a Script,
avoiding pubkey reuse ought to be easier.  Alice must communicate different
pubkeys intended for different clauses, or if Bob is constructing a whole
complex script on Alice's behalf, he may need to add CODESEPARATORs if
tweaking Alice's pubkey isn't an option.

The conversion of a policy to disjunctive normal form can involve an
exponential blowup (see <
https://en.wikipedia.org/wiki/Disjunctive_normal_form#Conversion_to_DNF>).
For instance, if Alice's policy (not in disjunctive normal form) is of the
form

(C[1] || D[1]) && ... && (C[n] || D[n]) && APK

where C[i] and D[i] are all distinct hashlocks, we require O(2^n) clauses
to put it in disjunctive normal form.  If 

Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript

2019-12-01 Thread Russell O'Connor via bitcoin-dev
On Thu, Nov 28, 2019 at 3:07 AM Anthony Towns  wrote:

> FWIW, there's discussion of this at
> http://www.erisian.com.au/taproot-bip-review/log-2019-11-28.html#l-65
>

I think variants like signing the position of the enclosing
OP_IF/OP_NOTIF/OP_ELSE of the OP_IF/OP_NOTIF/OP_ELSE block that the
checksig is within, or signing the byte offset instead of the opcode number
offset are all fine.  In particular, signing the enclosing OP_IF... would
allow sharing of the hashed signed data in a normal multisig sequence of
operations.  Below I'll continue to refer to my proposal as signing the
CHECKSIG position, but please take it to mean any of these proposed,
semantically equivalent, realizations of this idea.

I also think that it is quite reasonable to have a sighash flag control
whether or not the signature covers the CHECKSIG position or not, with
SIGHASH_ALL including the CHECKSIG position.


> First, it seems like a bad idea for Alice to have put funds behind a
> script she doesn't understand in the first place. There's plenty of
> scripts that are analysable, so just not using ones that are too hard to
> analyse sure seems like an option.
>

I don't think this is true in general.  When constructing a script it seems
quite reasonable for one party to come to the table with their own custom
script that they want to use because they have some sort of 7-of-11 scheme
but in one of those cases is really a 2-of-3 and another is 5-of-6.  The
point is that you shouldn't need to decode their exact policy in order to
collaborate with them.  This notion is captured quite clearly in the MAST
aspect of taproot.  In many circumstances, it is sufficient for you to know
that there exists a branch that contains a particular script without need
to know what every branch contains.  Because we include the tapleaf in the
signature, we already prevent this signature copying attack against
attempts to transplant one's signature from one tapleaf to another.  My
proposal is to simply extend this same protection to branches within a
single tapscript.

Second, if there are many branches in the script, it's probably more
> efficient to do them via different branches in the merkle tree, which
> at least for this purpose would make them easier to analyse as well
> (since you can analyse them independently).
>

Of course this should be done when practical.  This point isn't under
dispute.


> Third, if you are doing something crazy complex where a particular key
> could appear in different CHECKSIG operators and they should have
> independent signatures, that seems like you're at the level of
> complexity where learning about CODESEPARATOR is a reasonable thing to
> do.
>

So while I agree that learning about CODESEPARATOR is a reasonable thing to
do, given that I haven't heard the CODESEPARATOR being proposed as
protection against this sort of signature-copying attack before and given
the subtle nature of the issue, I'm not sure people will know to use it to
protect themselves.  We should aim for a Script design that makes the
cheaper default Script programming choices the safer one.

On the other hand, in a previous thread a while ago I was also arguing that
sophisticated people are plausibly using CODESEPARATOR today, hidden away
in unredeemed P2SH UTXOs.  So perhaps I'm right about at least one of these
two points. :)

I think CODESEPARATOR is a better solution to this problem anyway. In
> particular, consider a "leaf path root OP_MERKLEPATHVERIFY" opcode,
> and a script that says "anyone in group A can spend if the preimage for
> X is revelaed, anyone in group B can spend unconditionally":
>
>  IF HASH160 x EQUALVERIFY groupa ELSE groupb ENDIF
>  MERKLEPATHVERIFY CHECKSIG
>
> spendable by
>
>  siga keya path preimagex 1
>
> or
>
>  sigb keyb path 0
>
> With your proposed semantics, if my pubkey is in both groups, my signature
> will sign for position 10, and still be valid on either path, even if
> the signature commits to the CHECKSIG position.
>
> I could fix my script either by having two CHECKSIG opcodes (one for
> each branch) and also duplicating the MERKLEPATHVERIFY; or I could
> add a CODESEPARATOR in either IF branch.
>

> (Or I could just not reuse the exact same pubkey across groups; or I could
> have two separate scripts: "HASH160 x EQUALVERIFY groupa MERKLEPATHVERIFY
> CHECKSIG" and "groupb MERKLEPATHVERIFY CHECKSIG")
>

I admit my proposal doesn't automatically prevent this signature-copying
attack against every Script template.  To be fully effective you need to be
aware of this signature-copying attack vector to ensure your scripts are
designed so that your CHECKSIG operations are protected by being within the
IF block that does the verification of the hash-preimage.  My thinking is
that my proposal is effective enough to save most people most of the time,
even if it doesn't save everyone all the time, all while having no
significant burden otherwise.  Therefore, I don't think your point that
there still exists a 

Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

2019-11-27 Thread Russell O'Connor via bitcoin-dev
Thanks for this work Jeremy.

I know we've discussed this before, but I'll restate my concerns with
adding a new "global" state variable to the Script interpreter for tracking
whether the previous opcode was a push-data operation or not.  While it
isn't so hard to implement this in Bitcoin Core's Script interpreter,
adding a new global state variable adds that much more complexity to anyone
trying to formally model Script semantics.  Perhaps one can argue that
there is already (non-stack) state in Script, e.g. to deal with
CODESEPARATOR, so why not add more?  But I'd argue that we should avoid
making bad problems worse.

If we instead make the CHECKTEMPLATEVERIFY operation fail if it isn't
preceded by (or alternatively followed by) an appropriate sized
(canonical?) PUSHDATA constant, even in an unexecuted IF branch, then we
can model the Script semantics by considering the
PUSHDATA-CHECKTEMPLATEVERIFY pair as a single operation.  This allows
implementations to consider improper use of CHECKTEMPLATEVERIFY as a
parsing error (just as today unbalanced IF-ENDIF pairs can be modeled as a
parsing error, even though that isn't how it is implemented in Bitcoin
Core).

I admit we would lose your soft-fork upgrade path to reading values off the
stack; however, in my opinion, this is a reasonable tradeoff.  When we are
ready to add programmable covenants to Script, we'll do so by adding CAT
and operations to push transaction data right onto the stack, rather than
posting a preimage to this template hash.

Pleased to announce refinements to the BIP draft for OP_CHECKTEMPLATEVERIFY
> (replaces previous OP_SECURETHEBAG BIP). Primarily:
>
> 1) Changed the name to something more fitting and acceptable to the
> community
> 2) Changed the opcode specification to use the argument off of the stack
> with a primitive constexpr/literal tracker rather than script lookahead
> 3) Permits future soft-fork updates to loosen or remove "constexpr"
> restrictions
> 4) More detailed comparison to alternatives in the BIP, and why
> OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may
> make it semi-redundant.
>
> Please see:
> BIP: https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki
> Reference Implementation:
> https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify
>
> I believe this addresses all outstanding feedback on the design of this
> opcode, unless there are any new concerns with these changes.
>
> I'm also planning to host a review workshop in Q1 2020, most likely in San
> Francisco. Please fill out the form here
> https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in participating
> (even if you can't physically attend).
>
> And as a "but wait, there's more":
>
> 1) RPC functions are under preliminary development, to aid in testing and
> evaluation of OP_CHECKTEMPLATEVERIFY. The new command `sendmanycompacted`
> shows one way to use OP_CHECKTEMPLATEVERIFY. See:
> https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs.
> `sendmanycompacted` is still under early design. Standard practices for
> using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a
> separate BIP. This work generalizes even if an alternative strategy is used
> to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY.
> 2) Also under development are improvements to the mempool which will, in
> conjunction with improvements like package relay, help make it safe to lift
> some of the mempool's restrictions on longchains specifically for
> OP_CHECKTEMPLATEVERIFY output trees. See: 
> https://github.com/bitcoin/bitcoin/pull/17268
> This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's
> fate.
>
>
> Neither of these are blockers for proceeding with the BIP, as they are
> ergonomics and usability improvements needed once/if the BIP is activated.
>
> See prior mailing list discussions here:
>
> *
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.html
> *
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.html
>
> Thanks to the many developers who have provided feedback on iterations of
> this design.
>
> Best,
>
> Jeremy
>
> --
> @JeremyRubin 
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Signing CHECKSIG position in Tapscript

2019-11-27 Thread Russell O'Connor via bitcoin-dev
Hi all,

I'd like to revisit an old topic from last year about the data signed in
tapscript signatures <
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-November/016508.html
>.

The current tapscript proposal requires a signature on the last executed
CODESEPRATOR position.  I'd like to propose an amendment whereby instead of
signing the last executed CODESEPRATOR position, we simply always sign the
position of the CHECKSIG (or other signing opcode) being executed. Then we
can deprecate CODESEPARTOR (either by making it OP_SUCCESS, or a nop, or
always fail when executed, or whatever).

The main motivation for this proposal is to increase robustness against
various signature-copying attacks in Scripts that have multiple spending
conditions.  Bitcoin is already robust against attacks where the attacker
attempts to peddle a victim's UTXO as their own and try to copy the
victim's signature from one transaction input to another input.  Because
Bitcoin signatures specify which input within a transaction is being signed
for, such attacks fail (see https://bitcoin.stackexchange.com/a/85665/49364
).

However, unless CODESEPARATOR is explicitly used, there is no protection
against these sorts of attacks when there are multiple participants that
have signing conditions within a single UTXO (or rather within a single
tapleaf in the tapscript case).  As it stands, Bitcoin's signed data only
covers which input is being signed, and not the specific conditions are
being signed for.  So for example, if Alice and Bob are engaged in some
kind of multi-party protocol, and Alice wants to pre-sign a transaction
redeeming a UTXO but subject to the condition that a certain hash-preimage
is revealed, she might verify the Script template shows that the code path
to her public key enforces that the hash pre-image is revealed (using a
toolkit like miniscript can aid in this), and she might make her signature
feeling secure that it, if her signature is used, the required preimage
must be revealed on the blockchain.  But perhaps Bob has masquated Alice's
pubkey as his own, and maybe he has inserted a copy of Alice's pubkey into
a different path of the Script template.  Now Alice's signature can be
copied and used in this alternate path, allowing the UTXO to be redeemed
under circumstances that Alice didn't believe she was authorizing.  In
general, to protect herself, Alice needs to inspect the Script to see if
her pubkey occurs in any other branch.  Given that her pubkey, in
principle, could be derived from a computation rather that pushed directly
into the stack, it is arguably infeasible for Alice to perform the required
check in general.

I believe that it would be safer, and less surprising to users, to always
sign the CHECKSIG position by default.  This will automatically enforce
conditions with the signature in most cases, rather than requiring users to
proactively try to reason if CODESEPARATOR is required for protection
within their protocol or not, and risk having them leave it out for cost
savings when it ends up being required for security after all.

I do not believe signing the CHECKSIG position is an undue burden on those
signers who have no conditions they require enforcement for.  As it stands,
the tapscript proposal already requires the tapleaf_hash value under the
signature; this CHECKSIG position value is simply more of the same kind of
data.  In simple Script templates (e.g. those with only one CHECKSIG
operation) the signed position will be a fixed known value.  Complex Script
templates are precisely the situations where you want to be careful about
enforcement of conditions with your signature.

As a side benefit, we get to eliminate CODESEPARATOR, removing a fairly
awkward opcode from this script version.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Bech32 weakness and impact on bip-taproot addresses

2019-11-08 Thread Russell O'Connor via bitcoin-dev
I do like the idea of length prefixing the witness program.  I will note
that the 1 byte witness version is really more like a 1 character witness
version.  There are 17 different segwit versions and there are 32
characters in the bech32 alphabet.  That leaves 15 unused characters that
we can use for assigning new meanings too.

That said, it is probably most sensible to define a new
human-readable-prefix for length prefixed bitcoin witness programs.  "btc1"
anyone?

On Fri, Nov 8, 2019 at 12:12 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Pieter, and all,
>
> Can we modify Bech32 SegWit address format for version 1 and above as
> below?
>
>   * The data-part values:
>   ** 1 byte: the witness version
> + ** If the witness version is non-zero, 1 byte: the length of the
> witness program.
>   ** A conversion of the 2-to-40-byte witness program (as defined by [
> https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141])
> to base32:
>   *** Start with the bits of the witness program, most significant bit
> per byte first.
>   *** Re-arrange those bits into groups of 5, and pad with zeroes at
> the end if needed.
>   *** Translate those bits to characters using the table above.
>
> This retains the ability of a bech32 address to specify any valid witness
> length and allows future version 1 addresses with lengths other than 32,
> while closing this malleation.
>
> Older software being given the modified v1 address format would mis-send
> it to the wrong witness program, however.
>
> Alternately we could just keep using version 0 in the address format
> forever.
> The requirement would be to ensure that SegWit vN (N >= 1) output witness
> programs would have a data-part value encoded as below:
>
> * The data-part values:
> ** 1 byte: legacy witness version, which must always be 0.
> ** 1 byte: actual witness version, which must be non-zero.
> ** 1 byte: padding length: 0 or 1.
> ** If padding length is 1, 1 byte: padding, which must be 0.
> ** 1 byte: witness program length.
> ** variable: witness program.
>
> A writer for a v1 or later address would initially set an empty padding,
> then compute:
>
>   1 // actual witness version
> + 1 // padding length
> + 1 // witness length
> + witness_length
>
> If the above sum is 20 or 32, then the writer selects a non-zero padding
> and inserts the padding byte so that the above sum is now 21 or 33.
>
> To a reader that understands only bech32 v0, such an encoding would look
> like a SegWit v0 invalid-program-length, and be rejected.
> A reader which understands the above protocol would, instead of rejecting
> a SegWit v0 invalid-program-length, instead attempt to parse it as above
> first, and consider it as SegWit v1 or higher if it was parsed correctly as
> above.
>
> The above proposal is of course ridiculous and I am now currently running
> diagnostics on my processing units to see if further glitches occur in test
> reasoning skills.
>
> Regards,
> ZmnSCPxj
> ___
> 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] Taproot proposal

2019-06-28 Thread Russell O'Connor via bitcoin-dev
Hmm? If I'm following what you mean, that's not the P2P rules, it's the
> Unserialize code, in particular:
>
>   compat/assumptions.h:52:static_assert(sizeof(int) == 4, "32-bit int
> assumed");
>
>   serialize.h:289:uint64_t ReadCompactSize(Stream& is)
>
>   serialize.h-679-template typename V>
>   serialize.h-680-void Unserialize_impl(Stream& is, prevector& v,
> const V&)
>   serialize.h-681-{
>   serialize.h-682-v.clear();
>   serialize.h:683:unsigned int nSize = ReadCompactSize(is);
>
>   (and other Unserialize_impl implementations)
>
> However, ReadCompactSize throws "size too large" if the return value is
> greater than MAX_SIZE == 0x0200 =~ 33.5M, which prior to the implicit
> cast to 32 bits in Unserialize_impl. And it looks like that check's been
> there since Satoshi...
>
> So as far as I can see, that encoding's just unsupported/invalid, rather
> than equivalent/non-canonical?
>

Thanks for this correction!  I totally missed that MAX_SIZE == 0x0200.
I think I mistook it for SIZE_MAX when reviewing this, or just didn't
notice it at all.

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


Re: [bitcoin-dev] Taproot proposal

2019-06-26 Thread Russell O'Connor via bitcoin-dev
I have a comment about the 'input_index' of the transaction digest for
taproot signatures.  It is currently listed as 2 bytes.  I think it would
be better to expand that to 4 bytes.
The two byte limit is derived from the block size / weight limit, which
limits the maximum size of a transaction, which in turn, due to a minimum
size of an inputs, places a limit on the maximum number of inputs.

However, I think it is a mistake to mix limits from the block layer into
the transaction layer of the consensus rules.  For example, I believe that,
as it stands currently, if we wanted to hardfork an increase in the block
weight limit, doing so wouldn't have any impact on the transaction layer
and we could transparently manage larger transactions with the current
transaction format [2].  However if we start incorporating the block limits
into the transaction layer, then we run the risk of such a hard fork
needing to also make consensus changes in the transaction
format/interpretation if we wanted to handle larger transaction sizes,
which, while doable, wouldn't be so great.

The current transaction format limits the number of inputs (and the number
of outputs) to 2^32-1 or less [1].  So using 4 bytes for the 'input_index'
will suffice.

Given that adding 2 bytes to the signed transaction digest isn't a big
deal, it's probably better just to keep block limits and transaction limits
separate.

[1]The var-integer field for the number of inputs (and the number of
outputs) in a transaction looks like it should allow upto 2^64-1 inputs;
however this is an illusion.  The P2P rules dictate that these values are
immediately taken modulo 2^32 after decoding.  For example, if the number
of inputs is a var-integer encoding of 0x010001, it is actually just a
non-canonical way of encoding that there is 1 input.  Try this at home!

[2]If we were to hardfork an increase in the block weight limit, we would
probably want to still keep the limit on the size of transactions that
consume legacy UTXOs in order to avoid the quadratic computation problems
that plagues the legacy transaction digest.

On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here are two BIP drafts that specify a proposal for a Taproot
> softfork. A number of ideas are included:
>
> * Taproot to make all outputs and cooperative spends indistinguishable
> from eachother.
> * Merkle branches to hide the unexecuted branches in scripts.
> * Schnorr signatures enable wallet software to use key
> aggregation/thresholds within one input.
> * Improvements to the signature hashing algorithm (including signing
> all input amounts).
> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
> batch validation.
> * Tagged hashing for domain separation (avoiding issues like
> CVE-2012-2459 in Merkle trees).
> * Extensibility through leaf versions, OP_SUCCESS opcodes, and
> upgradable pubkey types.
>
> The BIP drafts can be found here:
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
> specifies the transaction input spending rules.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
> specifies the changes to Script inside such spends.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> is the Schnorr signature proposal that was discussed earlier on this
> list (See
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html
> )
>
> An initial reference implementation of the consensus changes, plus
> preliminary construction/signing tests in the Python framework can be
> found on https://github.com/sipa/bitcoin/commits/taproot. All
> together, excluding the Schnorr signature module in libsecp256k1, the
> consensus changes are around 520 LoC.
>
> While many other ideas exist, not everything is incorporated. This
> includes several ideas that can be implemented separately without loss
> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
> which we're working on as an independent proposal.
>
> The document explains basic wallet operations, such as constructing
> outputs and signing. However, a wide variety of more complex
> constructions exist. Standardizing these is useful, but out of scope
> for now. It is likely also desirable to define extensions to PSBT
> (BIP174) for interacting with Taproot. That too is not included here.
>
> Cheers,
>
> --
> Pieter
> ___
> 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] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

2019-06-25 Thread Russell O'Connor via bitcoin-dev
Bitcoin Core is somewhat outside my core competence, but the various
OP_PUSHDATA are already multi-byte opcodes and GetOp already has a data
return parameter that is suitable for returning the payload of an immediate
32-byte data variant of OP_SECURETHEBAG.  All that I expect is needed is to
ensure that nowhere else is using a non-empty data-field as a proxy for a
non-empty push operation and fixing any such occurrences if they exist.
(AFAIKT there are only a handful of calls to GetOp).

It is probably worth updating the tapscript implementation to better
prepare it for new uses of OP_SUCCESSx.  Parsing should halt when an
OP_SUCCESSx is encountered, by having GetScriptOp advance the pc to end
after encountering such a code (decoding Script is no longer meaningful
after an OP_SUCCESS is encountered).  However, that means that GetScriptOp
needs to know what version of script it is expected to be parsing.  This
could be done by sending down some versioning flags, possibly by adding a
versioning field to CScript that can be initialized @
https://github.com/sipa/bitcoin/blob/7ddc7027b2cbdd11416809400c588e585a8b44ed/src/script/interpreter.cpp#L1679
or some other mechanism (and at the same time perhaps having GetSigOpCount
return 0 for tapscript, since counting sigops is not really meaningful in
tapscript). There are probably other reasonable approaches too (e.g your
option 2 below).  I could write some code to illustrate what I'm thinking
if you feel that would be helpful and I do think such changes around
OP_SUCCESS should be implemented regardless of whether we move forward with
OP_SECURETHEBAG or not.

It is probably worth doing this properly the first time around if we are
going to do it at all.

P.S. OP_RESERVED1 has been renamed to OP_SUCCESS137 in bip-tapscript.


>
> On Mon, Jun 24, 2019 at 6:47 PM Jeremy  wrote:

> I agree in principal, but I think that's just a bit of 'how things are'
> versus how they should be.
>
> I disagree that we get composability semantics because of OP_IF. E.g., the
> script "OP_IF  " and "OP_END" are two scripts that separately are
> invalid as parsed, but together are valid. OP_IF already imposes some
> lookahead functionality... but as I understand it, it may be feasible to
> get rid of OP_IF for tapscripts anyways. Also in this bucket are P2SH and
> segwit, which I think breaks this because the concat of two p2sh scripts or
> segwit scripts is not the same as them severally.
>
> I also think that the OP_SECURETHEBAG use of pushdata is a backwards
> compatible hack: we can always later redefine the parser to parse
> OP_SECURETHEBAG as the 34 byte opcode, recapturing the purity of the
> semantics. We can also fix it to not use an extra byte in a future tapleaf
> version.
>

> In any case, I don't disagree with figuring out what patching the parser
> to handle multibyte opcodes would look like. If that sort of upgrade-path
> were readily available when I wrote this, it's how I would have done it.
> There are two approaches I looked at mostly:
>
> 1) Adding flags to GetOp to change how it parses
>   a) Most of the same code paths used for new and old script
>   b) Higher risk of breaking something in old script style/downstream
>   c) Cleans up only one issue (multibyte opcodes) leaves other warts in
> place
>   d) less bikesheddable design (mostly same as old script)
>   e) code not increased in size
> 2) Adding a completely new interpreter for Tapscript
>   a) Fork the existing interpreter code
>   b) For all places where scripts are run, switch based on if it is
> tapscript or not
>   c) Can clean up various semantics, can even do fancier things like
> huffman encode opcodes to less than a byte
>   d) Can clearly separate parsing the script from executing it
>   e) Can improve versioning techniques
>   f) Low risk of breaking something in old script style/downstream
>   g) Increases amount of code substantially
>   h) Bikesheddable design (everything is on the table).
>   i) probably a better general mechanism for future changes to script
> parsing, less consensus risk
>   j) More compatible with templated script as well.
>
> If not clear, I think that 2 is probably a better approach, but I'm
> worried that 2.h means this would take a much longer time to implement.
>
> 2 can be segmented into two components:
>
> 1) the architecture of script parser versioning
> 2) the actual new script version
>
> I think that component 1 can be relatively non controversial, thankfully,
> using tapleaf versions (the architecture question is more around code
> structure). A proof of concept of this would be to have a fork that uses
> two independent, but identical, script parsers.
>
> Part two of this plan would be to modify one of the versions
> substantially. I'm not sure what exists on the laundry list, but I think it
> would be possible to pick a few worthwhile cleanups. E.g.:
>
> 1) Multibyte opcodes
> 2) Templated scripts
> 3) Huffman Encoding opcodes
> 4) OP_IF handling (maybe 

Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

2019-06-25 Thread Russell O'Connor via bitcoin-dev
I suspect that your conjecture is true.  And given that it is plausible
that we would want to add an opcode to tweak public keys, it seems like a
reason design to avoid accidental covenants.
(That said, I strongly prefer that the SECURETHEBAG data be the 32-bytes
immediately following the opcode rather than a OP_PUSHDATA, and I'd be
willing to help code this up (see below)).

On Mon, Jun 24, 2019 at 2:07 PM Jeremy  wrote:

> Do you think the following hypothesis is more or less true:
>
> H: There is no set of pure extensions* to script E such that enabling E
> and OP_SECURETHEBAG as proposed enables recursive covenants, but E alone
> does not enable recursive covenants?
>
> * Of course there are things that specifically are specifically designed
> to switch on if OP_SECURETHEBAG, so pure means normal things like OP_CAT
> that are a function of the arguments on the stack or hashed txn data.
>
> This is the main draw of the design I proposed, it should be highly
> improbable or impossible to accidentally introduce more behavior than
> intended with a new opcode.
>
> I think that given that H is not true for the stack reading version of the
> opcode, we should avoid doing it unless strongly motivated, so as to permit
> more flexibility for which opcodes we can add in the future without
> introducing recursion unless it is explicitly intended.
>

On Sat, Jun 1, 2019 at 12:47 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> A particularly useful topic of discussion is how best to eliminate the
> PUSHDATA and treat OP_SECURETHEBAG like a pushdata directly. I thought
> about how the interpreter works and is implemented and couldn't come up
> with something noninvasive.
>

We shouldn't be using the complexity of the changes to the Bitcoin Core a
measure of the complexity of a proposal.  That is looking the issue from
the wrong side.  If we measure the complexity of Script proposals by how
hard it is to change Bitcoin Core, what will happen is more and more of the
incidental details of Bitcoin Core's implementation will be pulled into the
semantics of Script (e.g. the fact that surrounding opcode values are
readily available in Bitcoin Core's particular implementation of its Script
interpreter).  Instead we should use the complexity of how hard it is to
reason about the new Script semantics.

The peeking semantics of OP_SECURETHEBAG is particularly awful because it
more-or-less breaks the fact that Bitcoin Script can be decomposed into
individual units of "opcodes" whose semantics and be individually
described, and it harms the composability of Bitcoin Script where you can
divide the script between any opcodes and the semantics of the
concatenation of those two scripts is simply the composition of the
semantics of the two halves.  (For those interested in formal semantics,
what we have here is a monoid homomorphism from list of opcodes (syntax) to
stack transformation functions (with side-effects) under (Kleisli)
composition (semantics).) Being able to decompose a Bitcoin Script this way
and reasoning about components is how one would reason about Bitcoin Script
in practice.  (Technically the structure is more involved than a list of
opcodes due to OP_IF, and instead you get a railroad diagram
).

Putting the 32 bytes of data required by OP_SECURETHEBAG immediately after
the opcode, like how OP_PUSHDATA* works, is a superior design choice.  It
lets us treat the opcodes and its immediate data as an atomic unit when
reasoning about Script and removes the need to define what happens when
OP_SECURETHEBAG is not followed by an OP_PUSDATA.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

2019-06-25 Thread Russell O'Connor via bitcoin-dev
OP_SECURETHEBAG doesn't include the script being executed (i.e the
scriptPubKey specified in the output that is redeemed by this input) in its
hash like ordinary signatures do
<https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1271>.
Of course, this ScriptPubKey is indirectly committed to through the input's
prevoutpoint.  However Script isn't able to reconstruct this script being
executed from the prevoutpoint in tapscript without an implementation of
public key tweeking in Bitcoin Script.

On Sun, Jun 23, 2019 at 2:41 AM Jeremy Rubin 
wrote:

> Can you clarify this comment?
>
> We do in fact commit to the script and scriptsig itself (not the witness
> stack) in OP_SECURETHEBAG (unless I'm missing what you meant)?
>
> On Thu, Jun 20, 2019, 10:59 AM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Just to be clear, while OP_CHECKTXDIGESTVERIFY would enable this style
>> of covenants if it pulled data from the stack, the OP_SECURETHEBAG
>> probably cannot create covenants even if it were to pull the data from the
>> stack unless some OP_TWEEKPUBKEY operation is added to Script because the
>> "commitment of the script itself" isn't part of the OP_SECURETHEBAG.
>>
>> So with regards to OP_SECURETHEBAG, I am also "not really seeing any
>> reason to complicate the spec to ensure the digest is precommitted as part
>> of the opcode."
>>
>> On Thu, Jun 6, 2019 at 3:33 AM ZmnSCPxj via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> Good morning aj,
>>>
>>>
>>> Sent with ProtonMail Secure Email.
>>>
>>> ‐‐‐ Original Message ‐‐‐
>>> On Wednesday, June 5, 2019 5:30 PM, Anthony Towns via bitcoin-dev <
>>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>>
>>> > On Fri, May 31, 2019 at 10:35:45PM -0700, Jeremy via bitcoin-dev wrote:
>>> >
>>> > > OP_CHECKOUTPUTSHASHVERIFY is retracted in favor of OP_SECURETHEBAG*.
>>> >
>>> > I think you could generalise that slightly and make it fit in
>>> > with the existing opcode naming by calling it something like
>>> > "OP_CHECKTXDIGESTVERIFY" and pull a 33-byte value from the stack,
>>> > consisting of a sha256 hash and a sighash-byte, and adding a new
>>> sighash
>>> > value corresponding to the set of info you want to include in the hash,
>>> > which I think sounds a bit like "SIGHASH_EXACTLY_ONE_INPUT |
>>> SIGHASH_ALL"
>>> >
>>> > FWIW, I'm not really seeing any reason to complicate the spec to ensure
>>> > the digest is precommitted as part of the opcode.
>>> >
>>>
>>> I believe in combination with `OP_LEFT` and `OP_CAT` this allows
>>> Turing-complete smart contracts, in much the same way as
>>> `OP_CHECKSIGFROMSTACK`?
>>>
>>> Pass in the spent transaction (serialised for txid) and the spending
>>> transaction (serialised for sighash) as part of the witness of the spending
>>> transaction.
>>>
>>> Script verifies that the spending transaction witness value is indeed
>>> the spending transaction by `OP_SHA256  OP_SWAP OP_CAT
>>> OP_CHECKTXDIGESTVERIFY`.
>>> Script verifies the spent transaction witness value is indeed the spent
>>> transaction by hashing it, then splitting up the hash with `OP_LEFT` into
>>> bytes, and comparing the bytes to the bytes in the input of the spending
>>> transaction witness value (txid being the bytes in reversed order).
>>>
>>> Then the Script can extract a commitment of itself by extracting the
>>> output of the spent transaction.
>>> This lets the Script check that the spending transaction also pays to
>>> the same script.
>>>
>>> The Script can then access a state value, for example from an
>>> `OP_RETURN` output of the spent transaction, and enforce that a correct
>>> next-state is used in the spending transaction.
>>> If the state is too large to fit in a standard `OP_RETURN`, then the
>>> current state can be passed in as a witness and validated against a hash
>>> commitment in an `OP_RETURN` output.
>>>
>>> I believe this is the primary reason against not pulling data from the
>>> stack.
>>>
>>> Regards,
>>> ZmnSCPxj
>>> ___
>>> 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] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

2019-06-20 Thread Russell O'Connor via bitcoin-dev
Just to be clear, while OP_CHECKTXDIGESTVERIFY would enable this style of
covenants if it pulled data from the stack, the OP_SECURETHEBAG probably
cannot create covenants even if it were to pull the data from the stack
unless some OP_TWEEKPUBKEY operation is added to Script because the
"commitment of the script itself" isn't part of the OP_SECURETHEBAG.

So with regards to OP_SECURETHEBAG, I am also "not really seeing any reason
to complicate the spec to ensure the digest is precommitted as part of the
opcode."

On Thu, Jun 6, 2019 at 3:33 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning aj,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On Wednesday, June 5, 2019 5:30 PM, Anthony Towns via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> > On Fri, May 31, 2019 at 10:35:45PM -0700, Jeremy via bitcoin-dev wrote:
> >
> > > OP_CHECKOUTPUTSHASHVERIFY is retracted in favor of OP_SECURETHEBAG*.
> >
> > I think you could generalise that slightly and make it fit in
> > with the existing opcode naming by calling it something like
> > "OP_CHECKTXDIGESTVERIFY" and pull a 33-byte value from the stack,
> > consisting of a sha256 hash and a sighash-byte, and adding a new sighash
> > value corresponding to the set of info you want to include in the hash,
> > which I think sounds a bit like "SIGHASH_EXACTLY_ONE_INPUT | SIGHASH_ALL"
> >
> > FWIW, I'm not really seeing any reason to complicate the spec to ensure
> > the digest is precommitted as part of the opcode.
> >
>
> I believe in combination with `OP_LEFT` and `OP_CAT` this allows
> Turing-complete smart contracts, in much the same way as
> `OP_CHECKSIGFROMSTACK`?
>
> Pass in the spent transaction (serialised for txid) and the spending
> transaction (serialised for sighash) as part of the witness of the spending
> transaction.
>
> Script verifies that the spending transaction witness value is indeed the
> spending transaction by `OP_SHA256  OP_SWAP OP_CAT
> OP_CHECKTXDIGESTVERIFY`.
> Script verifies the spent transaction witness value is indeed the spent
> transaction by hashing it, then splitting up the hash with `OP_LEFT` into
> bytes, and comparing the bytes to the bytes in the input of the spending
> transaction witness value (txid being the bytes in reversed order).
>
> Then the Script can extract a commitment of itself by extracting the
> output of the spent transaction.
> This lets the Script check that the spending transaction also pays to the
> same script.
>
> The Script can then access a state value, for example from an `OP_RETURN`
> output of the spent transaction, and enforce that a correct next-state is
> used in the spending transaction.
> If the state is too large to fit in a standard `OP_RETURN`, then the
> current state can be passed in as a witness and validated against a hash
> commitment in an `OP_RETURN` output.
>
> I believe this is the primary reason against not pulling data from the
> stack.
>
> Regards,
> ZmnSCPxj
> ___
> 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] [PROPOSAL] Emergency RBF (BIP 125)

2019-06-09 Thread Russell O'Connor via bitcoin-dev
On Sat, Jun 8, 2019 at 11:59 PM Rusty Russell  wrote:

> "Russell O'Connor"  writes:
> > Hi Rusty,
> >
> > On Sun, Jun 2, 2019 at 9:21 AM Rusty Russell via bitcoin-dev <
> > bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> >> The new "emergency RBF" rule:
> >>
> >>  6. If the original transaction was not in the first 4,000,000 weight
> >> units of the fee-ordered mempool and the replacement transaction is,
> >> rules 3, 4 and 5 do not apply.
> >>
> >> This means:
> >>
> >> 3. This proposal does not open any significant new ability to RBF spam,
> >>since it can (usually) only be used once.  IIUC bitcoind won't
> >>accept more that 100 descendents of an unconfirmed tx anyway.
> >>
> >
> > Is it not possible for Alice to grief Bob's node by alternating RBFing
> two
> > transactions, each one placing itself at the bottom of Bob's top
> 4,000,000
> > weight mempool which pushes the other one below the top 4,000,000 weight,
> > and then repeating with the other transaction?  It might be possible to
> > amend this proposal to partially mitigate this.
>
> Good point.  This will cost Alice approximately one tx every block, but
> that may still be annoying.  My intuition says it's hard to play these
> games across swathes of non-direct peers, since mempools are in constant
> flux and propagation is a bit random.
>
> What mitigations were you thinking?
>

For example,  "If the original transaction was not in the first 4,000,000
weight units of the fee-ordered mempool and the replacement transaction is
in the first 2,000,000 weight units" might adequately address the issue.
There are probably other ways as well.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] [PROPOSAL] Emergency RBF (BIP 125)

2019-06-03 Thread Russell O'Connor via bitcoin-dev
Hi Rusty,

On Sun, Jun 2, 2019 at 9:21 AM Rusty Russell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> The new "emergency RBF" rule:
>
>  6. If the original transaction was not in the first 4,000,000 weight
> units of the fee-ordered mempool and the replacement transaction is,
> rules 3, 4 and 5 do not apply.
>
> This means:
>
> 3. This proposal does not open any significant new ability to RBF spam,
>since it can (usually) only be used once.  IIUC bitcoind won't
>accept more that 100 descendents of an unconfirmed tx anyway.
>

Is it not possible for Alice to grief Bob's node by alternating RBFing two
transactions, each one placing itself at the bottom of Bob's top 4,000,000
weight mempool which pushes the other one below the top 4,000,000 weight,
and then repeating with the other transaction?  It might be possible to
amend this proposal to partially mitigate this.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_SECURETHEBAG (supersedes OP_CHECKOUTPUTSVERIFY)

2019-06-03 Thread Russell O'Connor via bitcoin-dev
On Sat, Jun 1, 2019 at 12:47 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi All,
>
> OP_CHECKOUTPUTSHASHVERIFY is retracted in favor of OP_SECURETHEBAG*.
> OP_SECURETHEBAG does more or less the same thing, but fixes malleability
> issues and lifts the single output restriction to a known number of inputs
> restriction.
>
> OP_CHECKOUTPUTSVERIFY had some issues with malleability of version and
> locktime. OP_SECURETHEBAG commits to both of these values.
>

Can you elaborate a bit more on what the issues were?


> OP_SECURETHEBAG also lifts the restriction that OP_CHECKOUTPUTSVERIFY had
> to be spent as only a single input, and instead just commits to the number
> of inputs. This allows for more flexibility, but keeps it easy to get the
> same single output restriction.
>
> BIP:
> https://github.com/JeremyRubin/bips/blob/op-secure-the-bag/bip-secure-the-bag.mediawiki
> Implementation: https://github.com/JeremyRubin/bitcoin/tree/secure_the_bag
>
> A particularly useful topic of discussion is how best to eliminate the
> PUSHDATA and treat OP_SECURETHEBAG like a pushdata directly. I thought
> about how the interpreter works and is implemented and couldn't come up
> with something noninvasive.
>

I'm not a Core developer but from what I understand, I'd be inclined to to
treat OP_SECURETHEBAG as with an immediate 32-byte parameter by modifying
GetScriptOp to return the 32-byte parameter through pvchRet.

bool GetScriptOp(CScriptBase::const_iterator& pc,
CScriptBase::const_iterator end, opcodetype& opcodeRet,
std::vector* pvchRet)
{
opcodeRet = OP_INVALIDOPCODE;
if (pvchRet)
pvchRet->clear();
if (pc >= end)
return false;

// Read instruction
if (end - pc < 1)
return false;
unsigned int opcode = *pc++;

// Immediate operand
if (opcode <= OP_PUSHDATA4)
{
// ...
}

if (opcode == OP_SECURETHEBAG) {
if (end - pc < 0 || (unsigned int)(end - pc) < 32)
return false;
if (pvchRet)
pvchRet->assign(pc, pc + 32);
pc += 32;
}

opcodeRet = static_cast(opcode);
return true;
}

and go from there.

Thank you for your review and discussion,
>
> Jeremy
>
> * Plus the name is better
>
> ___
> 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] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

2019-05-30 Thread Russell O'Connor via bitcoin-dev
On Mon, May 27, 2019 at 3:21 AM Anthony Towns  wrote:

> On Wed, May 22, 2019 at 05:01:21PM -0400, Russell O'Connor via bitcoin-dev
> wrote:
> > Bitcoin Script appears designed to be a flexible programmable system that
> > provides generic features to be composed to achieve various purposes.
>
> Counterpoint: haven't the flexibly designed parts of script mostly been
> a failure -- requiring opcodes to be disabled due to DoS vectors or
> consensus bugs, and mostly not being useful in practice where they're
> still enabled in BTC or on other chains where they have been re-enabled
> (eg, Liquid and BCH)?
>

You may have a point.  However, I'm still inclined to think that problem is
that you want some subset of concatenation, arithmetic, CHECKDATASIG,
transaction reflection and/or covenants in order to create particularly
useful programs.

A while ago, I was designing a moderately sophisticated Script for Elements
Alpha to see if I could implement a toy game, but ultimately I was thwarted
due to the fact that Elements Alpha didn't support multiplication.
I did briefly consider using repeated additions and nested if statements to
implement multiplication since I was expecting my numbers to be 11 or less,
but ultimately I decided to just continue my work on an alternative to
Script rather than trying to work around the missing multiplication.


> > Instead, I propose that, for the time being, we simply implement OP_CAT
> and
> > OP_CHECKSIGFROMSTACKVERIFY.
>
> FWIW, I'd like to see CAT enabled, though I'm less convinced about a
> CHECKSIG that takes the message from the stack. I think CAT's plausibly
> useful in practice, but a sig against data from the stack seems more
> useful in theory than in practice. Has it actually seen use on BCH or
> Liquid, eg?  (Also, I think BCH's name for that opcode makes more sense
> than Elements' -- all the CHECKSIG opcodes pull a sig from the stack,
> after all)
>
> > * Transaction introspection including:
> > + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply
> by the
> > nature of the construction.
>
> I think simulating an ANYPREVOUT sig with a data signature means checking:
>
> S1 P CHECKSIG -- to check S1 is a signature for the tx
>
> S1 H_TapSighash(XAB) P CHECKDATASIG
>  -- to pull out the tx data "X", "A", "B")
>
> S2 H_TapSighash(XCB) Q CHECKDATASIG
>  -- for the ANYPREVOUT sig, with A changed to C to
> avoid committing to prevout info
>
> X SIZE 42 EQUALVERIFY
> B SIZE 47 EQUALVERIFY
>  -- to make sure only C is replaced from "XCB"
>
> So to get all those conditions checked, I think you could do:
>
>P 2DUP TOALT TOALT CHECKSIGVERIFY
>SIZE 42 EQUALVERIFY
>"TapSighash" SHA256 DUP CAT SWAP CAT TOALT
>SIZE 47 EQUALVERIFY TUCK
>CAT FROMALT TUCK SWAP CAT SHA256 FROMALT SWAP FROMALT
>CHECKDATASIGVERIFY
>SWAP TOALT SWAP CAT FROMALT CAT SHA256 Q CHECKDATASIG
>
> Where the stack elements are, from top to bottom:
>
>S1: (65B) signature by P of tx
>X:  (42B) start of TapSighash spec
>B:  (47B) end of TapSighash spec (amount, nSequence, tapleaf_hash,
>  key_version, codesep_pos)
>A:  (73B) middle of TapSighash spec dropped for ANYPREVOUT (spend_type,
>  scriptPubKey and outpoint)
>C:   (1B) alternate middle (different spend_type)
>S2: (64B) signature of "XCB" by key Q
>
> So 298B for the witness data, and 119B or so for the script (if I've not
> made mistakes), versus "P CHECKSIGVERIFY Q CHECKSIG" and S2 and S1 on
> the stack, for 132B of witness data and 70B of script, or half that if
> the chaperone requirement is removed.
>

I haven't checked your details but the above looks about correct to me.

So what I was thinking is that we could add CHECKDATASIG first, and then
people could get started on actually using ANYPREVOUT in practice and we
can take our time to debate the merits of the chaperone vs non-chaperone,
and possibly learn something about actual use before making a decision.
There is no doubt that using ANYPREVOUT directly uses less weight, but they
seem close enough to that it the simulation is usable, though perhaps far
enough apart that we would want to eventually add ANYPREVOUT.  However, do
keep in mind that our goal is not to minimize the weight of specific
redemption policies.  The weight of implementing any particular redemption
policy in Script is somewhat arbitrary to begin with anyways, being
dependent on the choices made for the Script language operations and its
encoding.  Again, if our goal were to minimize weight for specific
redemption policies we should abandon SCRIPT and directly use a language
similar to Mi

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

2019-05-26 Thread Russell O'Connor via bitcoin-dev
Allowing multiple inputs is certainly better than the 1 restriction COSHV.

However, I agree on your preference for a RISC+CISC approach.  Which is why
instead of COSHV or CHECK_TXID_TEMPLACE_DATA we should do the more RISC-y
thing and begin adding transaction reflection primitives, starting with
OP_NUMINPUTS and OP_PUSHOUTPUTSHASH.  Nothing bad will happen by pushing
the OUTPUTSHASH onto the stack, and we won't even get recursive covenants
with just these transaction reflection primitives in tapscript.

On Fri, May 24, 2019 at 9:08 PM Jeremy  wrote:

> What do you think about having it be OP_CHECK_TXID_TEMPLATE_DATA where the
> hash checked is the TXID of the transaction with the inputs set to ...
> (maybe appended to the fee paid)?
>
> This allows for a variable number of inputs to be allowed (e.g., one, two,
> etc). This also fixes potential bugs around TXID malleability for lightning
> like setups (Greg and I discussed in wizards about version malleability).
>
> Allowing multiple inputs is great for structuring more complex contracts
> with multiple nodes paying into the same covenantted transaction.
>
> Also I personally prefer a RISC+CISC approach -- we should enable the
> common paths easily as they are known (didn't you come up with jets?) and
> improve security for API users, but also piecemeal enable features in
> script to allow for experimentation or custom contracts.
> --
> @JeremyRubin 
> 
>
>
> On Fri, May 24, 2019 at 4:15 PM Russell O'Connor 
> wrote:
>
>> In order of escalating scope of amendments to OP_COSHV, I suggest
>>
>> 1) Peeking at surrounding data surrounding data should definitely be
>> replaced by a pushdata-like op-code that uses the subsequent 32-bytes
>> directly.  The OP_SUCCESSx upgrade path specifically allows for this, and
>> avoids complicating the semantics Bitcoin Script.
>> 2) Furthermore, the number-of-input-verification and the
>> outputhash-verification operations ought to be split into different opcodes
>> as they are logically unrelated.
>> 3) Better still, we should instead implement the transaction reflection
>> operations of OP_PUSHOUTPUTHASH and OP_NUMINPUTS that puts the outputhash
>> and number of inputs respectively onto the stack.  Recursive covenants
>> appear to be effectively impossible without either an OP_TWEEKPUBKEY or an
>> OP_PUSHSCRIPTPUBKEY so the effort your proposal goes through to guard
>> against placing an arbitrary outputhash onto the stack appears to be wasted
>> effort to me.
>> 4) If we anticipate adding OP_CHECKSIGFROMSTACKVERIFY, then we should
>> most definitely prefer (3) instead of OP_COSHV, if we still feel the need
>> to do anything at all.  It is probably best to have both
>> OP_CHECKSIGFROMSTACKVERIFY and transaction reflection operations of
>> OP_PUSHOUTPUTHASH and OP_NUMINPUTS but I think I would be fine with just
>> OP_CHECKSIGFROMSTACKVERIFY as well.
>>
>> On the other hand, if we are serious about preferring less per-block
>> bandwidth over reusable primitive opcodes for programming, then we should
>> instead abandon the RISC-style Bitcoin Script and instead add an
>> alternative CISC-style taproot leaf type that directly provides (a
>> conjunction of) the various popular common policies: channel opening,
>> channel factories, coinjoins, hashlocks, timelocks, congestion control
>> etc.  Segwit v0 already implements this CISC-style for the single most
>> popular policy: single signature verification.
>>
>> On Fri, May 24, 2019 at 4:51 PM Jeremy  wrote:
>>
>>> Hi Russell,
>>>
>>> Thanks for this detailed comparison. The COSHV BIP does include a brief
>>> comparison to OP_CHECKSIGFROMSTACKVERIFY and ANYPREVOUT, but this is more
>>> detailed.
>>>
>>>
>>> I think that the power from CHECKSIGFROMSTACKVERIFY is awesome. It's
>>> clearly one of the more flexible options available and would enable a
>>> multitude of new use cases.
>>>
>>> When I originally presented my work on congestion control at Jan 2017
>>> BPASE, I also discussed it as an option for covenants. Unfortunately I
>>> think it may be on the edge of too powerful -- there are a lot of use cases
>>> and implications from having a potentially recursive covenant. If you see
>>> my response to Matt in the OP_COSHV BIP thread I classify it as enabling a
>>> non-computationally enumerable set of restrictions.
>>>
>>> I think also from a developer point of view working with OP_COSHV is
>>> much much simpler (maybe this can be abstracted) which will lead to
>>> increased adoption. OP_COSHV also uses less per-block bandwidth which also
>>> makes it preferable for a measure intended to decongest blocks. Do you know
>>> the exact byte cost for OP_CHECKSIGFROMSTACK? OP_COSHV scripts, with
>>> templating changes to taproot, can be a single byte. OP_COSHV also has less
>>> potential to have a negative interaction with future opcodes we may want
>>> like OP_PUBKEYTWEAK. While we're getting to an exact spec for 

Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

2019-05-25 Thread Russell O'Connor via bitcoin-dev
In order of escalating scope of amendments to OP_COSHV, I suggest

1) Peeking at surrounding data surrounding data should definitely be
replaced by a pushdata-like op-code that uses the subsequent 32-bytes
directly.  The OP_SUCCESSx upgrade path specifically allows for this, and
avoids complicating the semantics Bitcoin Script.
2) Furthermore, the number-of-input-verification and the
outputhash-verification operations ought to be split into different opcodes
as they are logically unrelated.
3) Better still, we should instead implement the transaction reflection
operations of OP_PUSHOUTPUTHASH and OP_NUMINPUTS that puts the outputhash
and number of inputs respectively onto the stack.  Recursive covenants
appear to be effectively impossible without either an OP_TWEEKPUBKEY or an
OP_PUSHSCRIPTPUBKEY so the effort your proposal goes through to guard
against placing an arbitrary outputhash onto the stack appears to be wasted
effort to me.
4) If we anticipate adding OP_CHECKSIGFROMSTACKVERIFY, then we should most
definitely prefer (3) instead of OP_COSHV, if we still feel the need to do
anything at all.  It is probably best to have both
OP_CHECKSIGFROMSTACKVERIFY and transaction reflection operations of
OP_PUSHOUTPUTHASH and OP_NUMINPUTS but I think I would be fine with just
OP_CHECKSIGFROMSTACKVERIFY as well.

On the other hand, if we are serious about preferring less per-block
bandwidth over reusable primitive opcodes for programming, then we should
instead abandon the RISC-style Bitcoin Script and instead add an
alternative CISC-style taproot leaf type that directly provides (a
conjunction of) the various popular common policies: channel opening,
channel factories, coinjoins, hashlocks, timelocks, congestion control
etc.  Segwit v0 already implements this CISC-style for the single most
popular policy: single signature verification.

On Fri, May 24, 2019 at 4:51 PM Jeremy  wrote:

> Hi Russell,
>
> Thanks for this detailed comparison. The COSHV BIP does include a brief
> comparison to OP_CHECKSIGFROMSTACKVERIFY and ANYPREVOUT, but this is more
> detailed.
>
>
> I think that the power from CHECKSIGFROMSTACKVERIFY is awesome. It's
> clearly one of the more flexible options available and would enable a
> multitude of new use cases.
>
> When I originally presented my work on congestion control at Jan 2017
> BPASE, I also discussed it as an option for covenants. Unfortunately I
> think it may be on the edge of too powerful -- there are a lot of use cases
> and implications from having a potentially recursive covenant. If you see
> my response to Matt in the OP_COSHV BIP thread I classify it as enabling a
> non-computationally enumerable set of restrictions.
>
> I think also from a developer point of view working with OP_COSHV is much
> much simpler (maybe this can be abstracted) which will lead to increased
> adoption. OP_COSHV also uses less per-block bandwidth which also makes it
> preferable for a measure intended to decongest blocks. Do you know the
> exact byte cost for OP_CHECKSIGFROMSTACK? OP_COSHV scripts, with templating
> changes to taproot, can be a single byte. OP_COSHV also has less potential
> to have a negative interaction with future opcodes we may want like
> OP_PUBKEYTWEAK. While we're getting to an exact spec for the features we
> want in Bitcoin scripting, it's hard to sign on to OP_CHECKSIGFROMSTACK
> unless there's an exact specification which makes us confident we're
> hitting all the points.
>
> If the main complaint about OP_COSHV is that it peeks at surrounding data,
> it's also possible to implement it more closely to a multi-byte pushdata
> opcode or do the template optimization.
>
> Lastly, as I have previously noted, OP_LEFT is probably safer to implement
> than OP_CAT and should be more efficient for OP_CHECKSIGFROMSTACK scripts.
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

2019-05-24 Thread Russell O'Connor via bitcoin-dev
On Wed, May 22, 2019 at 5:01 PM Russell O'Connor 
wrote:

> In concert, these two operations enable:
>
> * Oracle signature verification, including discrete log contracts.
>

Jonas informs me that I've misunderstood how discreet log contracts work.
The DLC signatures are not directly checked by Script and do not rely on
CHECKSIGFROMSTACK.  I apologize for my hasty literature review.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

2019-05-24 Thread Russell O'Connor via bitcoin-dev
Hello ZmnSCPxj,

I agree that adding OP_CHECKSIGFROMSTACK doesn't preclude adding shortcuts
such as `SIGHASH_ANYPREVOUT` and `OP_CHECKOUTPUTSHASHVERIFY`, and I agree
we ought to support such operations directly, especially if we see
widespread use of these constructions in practice.

I think it is desirable to add OP_CHECKSIGFROMSTACK for its direct purposes
of enabling oracle verification and discreet log contracts.  Moreover, it
would be better decide if we do or do not want to do this first, because
whether or not we chose to implement a general OP_CHECKSIGFROMSTACK will
influence the design of these other proposals.

For example, if we choose to deploy OP_CHECKSIGFROMSTACK, then the design
of OP_CHECKOUTPUTSHASHVERIFY ought to be simplified to OP_PUSHOUTPUTHASH
and OP_PUSHNUMINPUTS (etc.) because the proposal would no longer be
extending the expressiveness of Bitcoin Script.  And while
OP_CHECKSIGFROMSTACK doesn't directly address whether SIGHASH_ANYPREVOUT
should be with or without a chaperone (as the simulated version with
OP_CHECKSIGFROMSTACK is necessarily chaperoned), we might get an
opportunity to learn if users are willing to take advantage of the
chaperone, or whether they rather bypass it by using a short well-known
pubkey: (e.g.
0x02003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63)
and/or similar short signatures if we deploy OP_CHECKSIGFROMSTACK first.

Since most of the "scary" recursive convents are not available with
OP_CHECKSIGFROMSTACK within taproot (without further extensions), the
OP_CHECKSIGFROMSTACK proposal now has quite different consequences than
before.

On Thu, May 23, 2019 at 12:59 PM ZmnSCPxj  wrote:

> Good morning Russell,
>
> While I am sympathetic to this argument from first principles, as I
> understand it, it requires that provided witness inputs will become larger,
> compared to "shortcuts" like `SIGHASH_ANYPREVOUT` and
> `OP_CHECKOUTPUTSHASHVERIFY`.
>
> For instance, to simulate `SIGHASH_ANYPREVOUT` with `OP_CAT` and
> `OP_CHECKSIGFROMSTACK`, I would effectively split the unsigned transaction
> into its "inputs" and "outputs" part, concat them and use
> `OP_CHECKSIGFROMSTACK` on the chaperone signature, and also use a normal
> `OP_CHECKSIGVERIFY` on that same chaperone signature, then dup the
> "outputs" part and use `OP_CHECKSIGFROMSTACK` on the "any
> prevout"/"noinput" signature.
> I would effectively give the transaction to itself as part of the witness,
> and further, I would also have to very carefully write the script
> (admittedly the writing of the template could be done once, but it would
> require far more review than simple usages of the "limited" operations like
> `SIGHASH_ANYPREVOUT`).
> So my witness stack would contain two signatures, and a duplicate of the
> transaction itself, plus a very much complicated script, whereas use of
> `SIGHASH_ANYPREVOUT` just requires two signatures and a script not much
> longer than pre-Schnorr multisig scripts.
>
>
> It seems to me desirable, to try to reduce bandwidth consumption on the
> Bitcoin blockchain, including witness data.
> Indeed, I had thought the whole exercise of putting `OP_CHECKSIGFROMSTACK`
> in a federated sidechain (Elements/Liquid) was to try to identify common
> patterns of usage for that opcode, and *then* to propose those common
> patterns as specific "optimized" opcodes as a sort of "jet" for Bitcoin
> itself (but not `OP_CHECKSIGFROMSTACK` itself).
>
> Regards,
> ZmnSCPxj
>
>
> Sent with ProtonMail Secure Email.
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

2019-05-24 Thread Russell O'Connor via bitcoin-dev
Hi Jimmy,

The message could really be anything.  For example, in discreet log
contracts, AFAIU, you might have a specific public key from a trusted third
party (the Oracle) that is signs the closing price of corn in BTC on
2019-05-23 with a particular nonce dedicated to that product-date pair, in
which case the message would be the price expressed in binary.  In the case
of amortized secure multiparty computations, the message is protocol
specific binary data that consists of a counter (or counters), concatenated
with shares of secret data that is used to construct the result of the
multiparty computation.  In the case of transaction reflection, the message
would be a duplicate copy of the tapscript signed transaction data (about
244 bytes of data plus a 64 byte prefix).

As you note, the message is likely to constructed from a value computed
from a mix of witness and committed data, though the message might be pure
witness data, as in the discreet log contract example.  In that the
discreet log contract example, you'd probably duplicate the integer value
and do further processing (e.g. compare it to some other committed value).

On Thu, May 23, 2019 at 1:36 PM Jimmy Song  wrote:

> Hi Russell,
>
> This is probably a dumb question, but I'd like to get some clarity on your
> proposal.
>
> OP_CHECKSIGFROMSTACKVERIFY would pop off a signature, message and pubkey.
> Presumably, the message would then have to get constructed as part of the
> Script execution. What would such a message look like? What, in other
> words, would you be signing and would that be similar to what signatures
> sign now? Would it be a single blob that incorporates all the input/output
> information in some hashed manner (like BIP143)? Or would you need separate
> signatures for different parts of the transaction? Or is it something more
> complicated like aggregating multiple signatures over different parts of
> the transaction?
>
> Best,
>
> Jimmy
>
> On Thu, May 23, 2019 at 8:35 AM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Recently there have been some tapscript proposals, SIGHASH_ANYPREVOUT and
>> OP_CHECKOUTPUTHASHVERIFY, that aim to enable particular new features for
>> Bitcoin via new Script operations.  However, I think that these proposals
>> miss the mark when it comes to how they approach Bitcoin Script and
>> language features.
>>
>> Bitcoin Script appears designed to be a flexible programmable system that
>> provides generic features to be composed to achieve various purposes.
>> Thus, when we design new language features for Script, we should be
>> striving, as much as possible, to similarly build general purpose tools
>> which can in turn be used for a variety of purposes.
>>
>> I feel the SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY proposals fail
>> to achieve these design goals.  They are both are designed with very narrow
>> applications in mind, while also going out of their way to extend the
>> semantic domain of the interpretation of Bitcoin operations in new ways
>> that complicate their specification.  In the case of SIGHASH_ANYPREVOUT,
>> the semantic domain is extended by adding new counters to track the use of
>> various v0 and v2 signature types.  In the case of
>> OP_CHECKOUTPUTHASHVERIFY, it employs a new context-sensitive operation that
>> peeks at the value of surrounding opcodes.
>>
>> Instead, I propose that, for the time being, we simply implement OP_CAT
>> and OP_CHECKSIGFROMSTACKVERIFY.  OP_CAT pops two byte arrays off the stack
>> and pushes their concatenation back onto the stack.
>> OP_CHECKSIGFROMSTACKVERIFY pops a signature, message, and pubkey off the
>> stack and performs a bip-schnorr verification on the SHA256 hash of the
>> message.
>>
>> In concert, these two operations enable:
>>
>> * Oracle signature verification, including discrete log contracts.
>> * Amortized secure multiparty computations (see "Amortizing Secure
>> Computation with Penalties" by Kumaresan and Bentov).
>> * Transaction introspection including:
>> + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply
>> by the nature of the construction.
>> + Decide if a transaction has exactly one input or not. (etc.)
>> + Weak covenants, which can verify output scripts to see if they are
>> among a set of predefined values or verify the output hash.
>>
>> and presumably more applications as well.
>>
>> For better or for worse, without an OP_PUBKEYTWEEK operation available,
>> the more interesting recursive-covenants remain largely out of reach, with
>> the exception of a recursive covenant that is only able to sen

Re: [bitcoin-dev] Taproot proposal

2019-05-23 Thread Russell O'Connor via bitcoin-dev
On Wed, May 22, 2019 at 10:06 PM Pieter Wuille 
wrote:

> On Tue, 21 May 2019 at 10:20, Russell O'Connor 
> wrote:
> >
> > Regarding Tapscript, the specification calls for the final value of the
> stack being a single non-false value:
> >
> >> The tapscript is executed according to the rules in the following
> section, with the initial stack as input
> >> II. If the execution results in anything but exactly one element on
> the stack which evaluates to true with CastToBool(), fail.
> >
> > Perhaps it is worth taking this opportunity here to remove a minor wart
> of the Script language and instead require the stack to be exactly empty
> upon completion.
> >
> > In addition to removing a potential malleability vector, I expect it
> would simplify development of Bitcoin Script.  A rule requiring an empty
> stack means that the conjunction (logical and) of two policies can be
> implemented by the simple concatenation of Bitcoin Scripts.  This combined
> with the taproot ability to form the disjunction (logical or) of policies
> by having multiple Merkle branches, means that the translation of a policy
> written in disjunctive normal form (the logical ors of logical ands of
> primitive policies) can be straightforwardly translated to a taproot of
> tapscript.
> >
> > That said, I think the developers of miniscript <
> http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better
> position to comment on whether my above intuition is correct given that
> they've had to implement a host of various calling conventions.  I
> understand that at least some of this complexity is due to Bitcoin Script's
> one element stack rule.
>
> IIRC I looked into this a few months ago, and found that the spending
> cost (script size + expected witness size) of the optimal script for
> every Miniscript policy at most changes by 1 WU (in either direction)
> by requiring an empty stack rather than a true value, though in a
> (admittedly very arbitrarily biased) distribution, more policies were
> improved by it than degraded. This is not taking Taproot into account
> (as many of those policies in a Taproot-supporting world should
> optimally make use of the internal key and Merkle tree, rather than
> turning everything into a monolithic script). I expect that this may
> make the impact somewhat larger, but still never more than a 1 WU
> gain.
>
> I don't think the spending cost changes justify this change, so the
> remaining criteria are complexity ones. In my view, the main benefit
> would be to authors of hand-written scripts where the consistency
> benefits matter, but this needs to be weighed against the mental cost
> of learning the new semantics. For Miniscript itself, this doesn't
> make much difference - the top level calling convention would become
> 'V' instead of 'T', but 'T' would still exist as a calling convention
> that may be used internally; it's a few lines change.
>
> So overall this feels like something with marginal costs, but also at
> most marginal benefits. Perhaps other people have stronger opinions.
>

Thanks for the info.  I'm surprised to learn that 'T' would still exist
internally.  That does make my proposed ammendment a somewhat more marginal
than I expected.  I still think it would be an improvement, but I guess it
is acceptable the way it is if that is what other people prefer.


> > Even if we choose not to implement the empty stack rule, we should at
> least require that the last element be 0x01 to remove a potential
> malleability vector and bring it in line with MINIMAL_IF semantics.
>
> This feels like the right thing to do; as we're making MINIMALIF part
> of consensus for Tapscript it would make sense to apply the same rule
> to the "return" value of the script. There is a downside though,
> namely that in some places where you'd use "
> OP_CHECKSEQUENCEVERIFY" or " OP_CHECKLOCKTIMEVERIFY" you now need
> to add an additional OP_0NOTEQUAL to convert the left-over element n
> into an exact 0x01. I also can't come up with any practical benefits
> that this would have; if the top stack element in a particular code
> path comes directly from the input, it's insecure regardless; if there
> isn't, it'll generally be a a boolean (or an intentional non-boolean
> true value) computed by the script.
>

That is a very good argument.  If we were to go with an empty stack we'd
probably also want modify to have CSV and CLTV pop their inputs off the
stack.  But at that point perhaps we'd want to change their opcode values
to avoid confusion with old style script.  I guess I'm getting more
convinced to not touch this stuff just and just bear with the somewhat
unfortunate legacy behaviour.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK

2019-05-23 Thread Russell O'Connor via bitcoin-dev
Recently there have been some tapscript proposals, SIGHASH_ANYPREVOUT and
OP_CHECKOUTPUTHASHVERIFY, that aim to enable particular new features for
Bitcoin via new Script operations.  However, I think that these proposals
miss the mark when it comes to how they approach Bitcoin Script and
language features.

Bitcoin Script appears designed to be a flexible programmable system that
provides generic features to be composed to achieve various purposes.
Thus, when we design new language features for Script, we should be
striving, as much as possible, to similarly build general purpose tools
which can in turn be used for a variety of purposes.

I feel the SIGHASH_ANYPREVOUT and OP_CHECKOUTPUTHASHVERIFY proposals fail
to achieve these design goals.  They are both are designed with very narrow
applications in mind, while also going out of their way to extend the
semantic domain of the interpretation of Bitcoin operations in new ways
that complicate their specification.  In the case of SIGHASH_ANYPREVOUT,
the semantic domain is extended by adding new counters to track the use of
various v0 and v2 signature types.  In the case of
OP_CHECKOUTPUTHASHVERIFY, it employs a new context-sensitive operation that
peeks at the value of surrounding opcodes.

Instead, I propose that, for the time being, we simply implement OP_CAT and
OP_CHECKSIGFROMSTACKVERIFY.  OP_CAT pops two byte arrays off the stack and
pushes their concatenation back onto the stack.  OP_CHECKSIGFROMSTACKVERIFY
pops a signature, message, and pubkey off the stack and performs a
bip-schnorr verification on the SHA256 hash of the message.

In concert, these two operations enable:

* Oracle signature verification, including discrete log contracts.
* Amortized secure multiparty computations (see "Amortizing Secure
Computation with Penalties" by Kumaresan and Bentov).
* Transaction introspection including:
+ Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply by
the nature of the construction.
+ Decide if a transaction has exactly one input or not. (etc.)
+ Weak covenants, which can verify output scripts to see if they are among
a set of predefined values or verify the output hash.

and presumably more applications as well.

For better or for worse, without an OP_PUBKEYTWEEK operation available, the
more interesting recursive-covenants remain largely out of reach, with the
exception of a recursive covenant that is only able to send back to its own
address, possibly abusing its own TXO value as a state variable.

All this is accomplished by two straightforward opcodes whose semantics are
pure computational operations on stack values.  The only semantic
side-effect is that OP_CHECKSIGFROMSTACKVERIFY would count towards the
existing 'sigops_passed' count.  Moreover, I feel that adding these
operations does not preclude adding more specialized opcodes in the future
as an optimization for whatever popular constructions come up, once we know
what those are.

I feel that this style of generic building blocks truly embodies what is
meant by "programmable money".
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Taproot proposal

2019-05-21 Thread Russell O'Connor via bitcoin-dev
Regarding Tapscript, the specification calls for the final value of the
stack being a single non-false value:

The tapscript is executed according to the rules in the following section,
> with the initial stack as input
> II. If the execution results in anything but exactly one element on
> the stack which evaluates to true with CastToBool(), fail.
>

Perhaps it is worth taking this opportunity here to remove a minor wart of
the Script language and instead require the stack to be exactly empty upon
completion.

In addition to removing a potential malleability vector, I expect it would
simplify development of Bitcoin Script.  A rule requiring an empty stack
means that the conjunction (logical and) of two policies can be implemented
by the simple concatenation of Bitcoin Scripts.  This combined with the
taproot ability to form the disjunction (logical or) of policies by having
multiple Merkle branches, means that the translation of a policy written in
disjunctive normal form (the logical ors of logical ands of primitive
policies) can be straightforwardly translated to a taproot of tapscript.

That said, I think the developers of miniscript <
http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better
position to comment on whether my above intuition is correct given that
they've had to implement a host of various calling conventions.  I
understand that at least some of this complexity is due to Bitcoin Script's
one element stack rule.

Scripts under the old one element rule can be translated to the new rule by
adding an OP_VERIFY operation to the end of the script; however it is
likely that this OP_VERIFY can be folded into the previous operation
yielding an OP_EQUALVERIFY or OP_CHECKSIGVERIFY in many cases.

Even if we choose not to implement the empty stack rule, we should at least
require that the last element be 0x01 to remove a potential malleability
vector and bring it in line with MINIMAL_IF semantics.

Thanks.

On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here are two BIP drafts that specify a proposal for a Taproot
> softfork. A number of ideas are included:
>
> * Taproot to make all outputs and cooperative spends indistinguishable
> from eachother.
> * Merkle branches to hide the unexecuted branches in scripts.
> * Schnorr signatures enable wallet software to use key
> aggregation/thresholds within one input.
> * Improvements to the signature hashing algorithm (including signing
> all input amounts).
> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
> batch validation.
> * Tagged hashing for domain separation (avoiding issues like
> CVE-2012-2459 in Merkle trees).
> * Extensibility through leaf versions, OP_SUCCESS opcodes, and
> upgradable pubkey types.
>
> The BIP drafts can be found here:
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
> specifies the transaction input spending rules.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
> specifies the changes to Script inside such spends.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> is the Schnorr signature proposal that was discussed earlier on this
> list (See
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html
> )
>
> An initial reference implementation of the consensus changes, plus
> preliminary construction/signing tests in the Python framework can be
> found on https://github.com/sipa/bitcoin/commits/taproot. All
> together, excluding the Schnorr signature module in libsecp256k1, the
> consensus changes are around 520 LoC.
>
> While many other ideas exist, not everything is incorporated. This
> includes several ideas that can be implemented separately without loss
> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
> which we're working on as an independent proposal.
>
> The document explains basic wallet operations, such as constructing
> outputs and signing. However, a wide variety of more complex
> constructions exist. Standardizing these is useful, but out of scope
> for now. It is likely also desirable to define extensions to PSBT
> (BIP174) for interacting with Taproot. That too is not included here.
>
> Cheers,
>
> --
> Pieter
> ___
> 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] OP_CODESEPARATOR Re: BIP Proposal: The Great Consensus Cleanup

2019-03-13 Thread Russell O'Connor via bitcoin-dev
Hi Matt,

On Mon, Mar 11, 2019 at 10:23 PM Matt Corallo 
wrote:

> I think you may have misunderstood part of the motivation. Yes, part of
> the motivation *is* to remove OP_CODESEPARATOR wholesale, greatly
> simplifying the theoretical operation of checksig operations (thus somewhat
> simplifying the implementation but also simplifying analysis of future
> changes, such as sighash-caching code).
>

I see.  I was under the mistaken impression the concerns about of
OP_CODESEPARATOR was simply due to the vulnerability it induces.

I'll say it now then: Simplifying the theoretical operation of Bitcoin is
not a sufficient reason to make changes to the consensus rules, and it is
most certainly not a sufficient reason to remove usable op codes.

Had I understood that this was your motivation I would have presented my
opinion earlier. I understand that the OP_CODESEPARATOR vulnerability is
quite serious and making it non-standard while we address the problem is a
good idea (hence the reason why I never objected before now).

What I don't understand is why you feel that avoiding flushing the sigcache
is so critical that you are willing to go through a risky consensus change
just to achieve it?  The sigcache is effectively flushed for each input of
a transaction anyways, so what's the big deal about flushing it during
Script execution as well?


> I think a key part of the analysis here is that no one I've spoken to (and
> we've been discussing removing it for *years*, including many attempts at
> coming up with reasons to keep it) is aware of any real proposals to use
> OP_CODESEPARATOR, let alone anyone using it in the wild. Hiding data in
> invalid pubic keys is a long-discussed-and-implemented idea (despite it's
> discouragement, not to mention it appears on the chain in many places).
>

Well you've spoken to me now, and I believe I have given you good reasons
to keep it.  We all used to think that OP_CODESEPARATOR was a useless
operation that no one in their right mind would ever use, but it turns out
that we were wrong.  Lesson learned.  We should be more humble about
considering these sorts of changes in the future because it seems we might
not understand Bitcoin as well as we think we do.  At the very least I was
caught by surprise by the utility of OP_CODESEPARATOR.

You misunderstand my point regarding invalid public keys.  My point is that
if no one has spoken up about the invalid public key issue on this mailing
list, something that we know really does affects people, why do you expect
that people would have spoken up about OP_CODESEPARATATOR affecting them?


> It would end up being a huge shame to have all the OP_CORESEPARATOR mess
> left around after all the effort that has gone into removing it for the
> past few years, especially given the stark difference in visibility of a
> fork when compared to a standardness change.
>
> As for your specific proposal of increasing the weight of anything that
> has an OP_CODESEPARATOR in it by the cost of an additional (simple) input,
> this doesn't really solve the issue. After all, if we're assuming some user
> exists who has been using sending money, unspent, to scripts with
> OP_CODESEPARATOR to force signatures to commit to whether some other
> signature was present and who won't see a (invariably media-covered)
> pending soft-fork in time to claim their funds, we should also assume such
> a user has pre-signed transactions which are time-locked and claim a number
> of inputs and have several paths in the script which contain
> OP_CODESEPARATOR, rendering their transcription invalid.
>

Agreed, that's why we will want to not simply count the OP_CODESEPARATORS,
but rather count the maximum number of OP_CODESEPARATORS that can be
executed through the any of the various possible OP_IF branches.  Adding
this sort of control-flow analysis is a pretty simple. It just requires a
small stack of pairs of numbers and linear traversal through the Script.
This sort of OP_IF control flow analysis ought to have been done for
counting CHECKSIG operations, but unfortunately it is too late for that
now.  I could prototype the sort of analysis I have in mind if you think
that would be helpful.

In fact, it is really alternating uses of OP_CODESEPARATOR and CheckSig
operations that is problematic, so it is probably worth attempting to count
these pairs rather than just OP_CODESEPARATORS.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_CODESEPARATOR Re: BIP Proposal: The Great Consensus Cleanup

2019-03-13 Thread Russell O'Connor via bitcoin-dev
On Tue, Mar 12, 2019 at 6:39 PM Jacob Eliosoff 
wrote:

> Also, if future disabling isn't the point of making a tx type like
> OP_CODESEPARATOR non-standard - what is?  If we're committed to indefinite
> support of these oddball features, what do we gain by making them hard to
> use/mine?
>

The purpose of making OP_CODESEPARATOR non-standard was to partly mitigate
the risk of the vulnerability that OP_CODESEPARATOR induces while we
consider how to patch it.

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


Re: [bitcoin-dev] Sighash Type Byte; Re: BIP Proposal: The Great Consensus Cleanup

2019-03-13 Thread Russell O'Connor via bitcoin-dev
Hi Matt,

(I moved your comment to this thread, where I think it is more relevant).

This is a fair point.  I concede that as far as Sighash Type Byte is
concerned, the type of change is fairly similar to BIP 68 (though I don't
think the argument applies to OP_CODESEPARATOR).
I might rephrase what you say as "invalidating otherwise-unusable bits of
the protocol".  I don't quite know the right phrasing that captures both
the insecure and redundant aspects of the protocol.  I'm willing to accept
that nSequence numbers (as they originally were), NOP1-NOP10 and these
extra sighash types can all be classified as redundant aspects of the
Bitcoin protocol.

I still think the alternative proposal of caching the sha256 midstate is
the better choice.  We should strive to avoid changing the consensus rules
when we have reasonable alternatives to achieve our goals. However, I now
see that this proposal isn't entirely unprecedented.

On Tue, Mar 12, 2019 at 5:08 PM Matt Corallo 
wrote:

> Note that even your carve-outs for OP_NOP is not sufficient here - if you
> were using nSequence to tag different pre-signed transactions into
> categories (roughly as you suggest people may want to do with extra sighash
> bits) then their transactions could very easily have become
> un-realistically-spendable. The whole point of soft forks is that we
> invalidate otherwise-unused bits of the protocol. This does not seem
> inconsistent with the proposal here.
>
> > On Mar 9, 2019, at 13:29, Russell O'Connor 
> wrote:
> > Bitcoin has *never* made a soft-fork, since the time of Satoishi, that
> invalidated transactions that send secured inputs to secured outputs
> (excluding uses of OP_NOP1-OP_NOP10).
>

On Fri, Mar 8, 2019 at 10:57 AM Russell O'Connor 
wrote:

> On Thu, Mar 7, 2019 at 2:57 PM Matt Corallo 
> wrote:
>
>> I can't say I'm particularly married to this idea (hence the alternate
>> proposal in the original email), but at the same time the lack of
>> existing transactions using these bits (and the redundancy thereof -
>> they don't *do* anything special) seems to be pretty strong indication
>> that they are not in use. One could argue a similarity between these
>> bits and OP_NOPs - no one is going to create transactions that require
>> OP_NOP execution to be valid as they are precisely the kind of thing
>> that may get soft-forked to have a new meaning. While the sighash bits
>> are somewhat less candidates for soft-forking,
>
>
> I don't think "somewhat less candidates for soft-forking" is a fair
> description.  These bits essentially unsuitable for soft-forking within
> legacy Script.
>
> I don't think "someone
>> may have shoved random bits into parts of their
>> locked-for-more-than-a-year transactions" is sufficient reason to not
>> soft-fork something out.
>
>
> I disagree. It is sufficient.
>
> When was the last time Bitcoin soft-forked out working transactions that
> sent funds from securely held UTXOs to securely held UTXOs (aside from
> those secured by Scripts using the reserved OP_NOP1-OP_NOP10)?  AFAIK it
> has never occurred since the time of Satoshi, even for the most
> hypothetical of transactions.  It is my understanding is that Bitcoin Core
> would never do such a thing unless the security of Bitcoin protocol itself
> was under existential threat (see OP_CODESEPARATOR) and even then Bitcoin
> Core would only soft-fork out the minimal amount necessary to safely
> diffuse such a threat.
>
> Since the above soft-fork isn't addressing addressing any such threat
> (that I'm aware of), and could hypothetically destroy other people money,
> it crosses a line I thought we were never supposed to cross.
>
>>
>> Obviously, actually *seeing* it used in
>> practice or trying to fork them out in a fast manner would be
>> unacceptable, but neither is being proposed here.
>>
>
> Perhaps you don't see them in used in the blockchain because the users
> trying to use them are caught up by the fact they they are not being
> relayed by default (violating SCRIPT_VERIFY_STRICTENC) and are having
> difficulty redeeming them.
> You cannot first make transactions non-standard and then use the fact that
> you don't see them being used to justify a soft-fork.
>
> I know of users who have their funds tied up due to other changes in
> Bitcoin Core's default relay policy.  I believe they waiting for their
> funds to become valuable enough to go through the trouble of having them
> directly mined.  Shall we now permanently destroy their funds too, before
> they have a chance to get their transactions mined?
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_CODESEPARATOR Re: BIP Proposal: The Great Consensus Cleanup

2019-03-11 Thread Russell O'Connor via bitcoin-dev
Increasing the OP_CODESEPARATOR weight by 520 (p2sh redeemScript size
limit) + 40 (stripped txinput size) + 8 (stripped txoutput size) + a few
more (overhead for varints) = 572ish bytes should be enough to completely
eliminate any vulnerability caused by OP_CODESEPARATOR within P2SH
transactions without the need to remove it ever.  I think it is worth
attempting to be a bit more clever than such a blunt rule, but it would be
much better than eliminating OP_CODESEPARATOR within P2SH entirely.

Remember that the goal isn't to eliminate OP_CODESEPARATOR per se; the goal
is to eliminate the vulnerability associated with it.

On Mon, Mar 11, 2019 at 12:47 PM Dustin Dettmer via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> What about putting it in a deprecated state for some time. Adjust the
> transaction weight so using the op code is more expensive (10x, 20x?) and
> get the word out that it will be removed in the future.
>
> You could even have nodes send a reject code with the message
> “OP_CODESEPARATOR is depcrecated.”
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_CODESEPARATOR Re: BIP Proposal: The Great Consensus Cleanup

2019-03-11 Thread Russell O'Connor via bitcoin-dev
Hi Jacob,


> Huh?! The whole point of non-standardness in this context is to (a) make
>>> soft-forking something out safer by derisking miners not upgrading right
>>> away and (b) signal something that may be a candidate for soft-forking
>>> out so that we get feedback. Who is getting things disabled who isn't
>>> bothering to *tell* people that their use-case is being hurt?!
>>>
>>
>> People have told me that they are hurt by some other non-standardness
>> changes and I understand that they have been sitting on those funds for
>> years.  Maybe they don't realize their is some place to complain or maybe
>> they think there must be a good reason why they are not allowed to do what
>> they were previously allowed to do.  Perhaps others don't want to risk
>> blowing their pseudonymity.  Perhaps they think that attempting to undo
>> some of these non-standardness changes is futile.  I can bring up the
>> specific cases I've encountered in a new thread if you think it is
>> worthwhile.
>>
>
> Like Matt, I understand non-standardness to be specifically for making a
> transaction type more difficult to set the stage for a future disabling.
>
> If anyone is actually harmed by this change, let them at least speak up
> pseudonymously as others have before.  Backwards compatibility shouldn't
> mean letting imaginary implausible cases veto net-beneficial changes.
>

It is so easy to say stuff like this when one's own money isn't what is at
risk.

While I encourage users who would be harmed to chime in if they can,
unfortunately, I think it is mostly wishful thinking on our part that they
necessarily would.  In fact, there is evidence that in practice people
don't.

To illustrate this, consider the example of the people affected by PR #5247
, which makes unparsable
public keys non-standard.  As far as I am aware none have commented on this
mailing list about it yet even though I happen to know such people do exist
because I've talked with them on Slack.  I believe the person I spoke with
to took over a year (and probably more than two years) to even notice that
the transactions they want to redeem with are no longer standard.  To be
fair, their money that is stuck due to PR #5247 isn't lost yet, but I'm
skeptical they would think or know to speak up here even if their money was
on the chopping block.  The fact that they haven't been able to move their
money in the last *4 years* doesn't mean they wouldn't like it back one day.

While non-standardness is a helpful in dissuading users from committing new
funds to OP_CODESEPARATOR scripts, it doesn't do anything to help users
that may have been caught unaware by the non-standardness change.
Furthermore, because these transactions are non-standard, anyone caught off
guard by the change is going to have a very hard time redeeming their
funds, as we have already seen with PR #5247, a non-standardness change
that is far older than the OP_CODESERPATOR change in PR #11423
.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_CODESEPARATOR Re: BIP Proposal: The Great Consensus Cleanup

2019-03-11 Thread Russell O'Connor via bitcoin-dev
I fear that we cannot simply wait 10 years to address the vulnerability
that OP_CODESEPARATOR has in its current form.

On Fri, Mar 8, 2019 at 7:32 PM LORD HIS EXCELLENCY JAMES HRMH <
willt...@live.com.au> wrote:

> Opinion: Lock in a blockheight to get rid of it 10 years in the future.
> Use it as press that Bitcoin is going to lose $1,000,000 if some mystery
> person does not put their transaction through by then, try for global
> presses. Use the opportunity to get rid of it while you are able. Once
> gazetted anything is public knowledge.
>
> Regards,
> LORD HIS EXCELLENCY JAMES HRMH
> --
> *From:* bitcoin-dev-boun...@lists.linuxfoundation.org <
> bitcoin-dev-boun...@lists.linuxfoundation.org> on behalf of Sjors
> Provoost via bitcoin-dev 
> *Sent:* Saturday, 9 March 2019 6:12 AM
> *To:* Matt Corallo; Russell O'Connor; Bitcoin Protocol Discussion
> *Subject:* Re: [bitcoin-dev] OP_CODESEPARATOR Re: BIP Proposal: The Great
> Consensus Cleanup
>
>
> > (1) It has been well documented again and again that there is desire to
> remove OP_CODESEPARATOR, (2) it is well-documented OP_CODESEPARATOR in
> non-segwit scripts represents a rather significant vulnerability in Bitcoin
> today, and (3) lots of effort has gone into attempting to find practical
> use-cases for OP_CODESEPARATOR's specific construction, with no successes
> as of yet. I strongly, strongly disagree that the highly-unlikely remote
> possibility that someone created something before which could be rendered
> unspendable is sufficient reason to not fix a vulnerability in Bitcoin
> today.
> >
> >> I suggest an alternative whereby the execution of OP_CODESEPARATOR
> increases the transactions weight suitably as to temper the vulnerability
> caused by it.  Alternatively there could be some sort of limit (maybe 1) on
> the maximum number of OP_CODESEPARATORs allowed to be executed per script,
> but that would require an argument as to why exceeding that limit isn't
> reasonable.
> >
> > You could equally argue, however, that any such limit could render some
> moderately-large transaction unspendable, so I'm somewhat skeptical of this
> argument. Note that OP_CODESEPARATOR is non-standard, so getting them mined
> is rather difficult in any case.
>
> Although I'm not a fan of extra complicity, just to explore these two
> ideas a bit further.
>
> What if such a transaction:
>
> 1. must have one input; and
> 2. must be smaller than 400 vbytes; and
> 3. must spend from a UTXO older than fork activation
>
> Adding such a contextual check seems rather painful, perhaps comparable to
> nLockTime. Anything more specific than the above, e.g. counting the number
> of OP_CODESEPARATOR calls, seems like guess work.
>
> Transaction weight currently doesn't consider OP codes, it only considers
> if bytes are part of the witness. Changing that to something more akin to
> Ethereums gas pricing sounds too complicated to even consider.
>
>
> I would also like to believe that whoever went through the trouble of
> using OP_CODESEPARATOR reads this list.
>
> Sjors
>
> ___
> 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] OP_CODESEPARATOR Re: BIP Proposal: The Great Consensus Cleanup

2019-03-09 Thread Russell O'Connor via bitcoin-dev
Hi Matt,

On Fri, Mar 8, 2019 at 1:35 PM Matt Corallo 
wrote:

> Replies inline.
>
> On 3/8/19 3:57 PM, Russell O'Connor wrote:
> > On Thu, Mar 7, 2019 at 2:50 PM Matt Corallo  > > wrote:
> > It's very easy to construct a practical script using OP_CODESEPARATOR.
> >
> > IF <2>   <2> CHECKMULTISIGVERIFY ELSE
> > CODESEPARATOR  CHECKSIGVERFY ENDIF
> >
> > Now when someone hands Alice, the CFO of XYZ corp., some transaction,
> > she has the option of either signing it unilaterally herself, or
> > creating a partial signature such that the transaction additionally
> > needs Bob, the CEOs signature as well, and Alice's choice is committed
> > to the blockchain for auditing purposes later.
> >
> > Now, there are many things you might object about this scheme, but my
> > point is that (A) regardless of what you think about this scheme, it, or
> > similar schemes, may have been devised by users, and (B) users may have
> > already committed funds to such schemes, and due to P2SH you cannot know
> > that this is not the case.
>
> The common way to set that up is to have a separate key, but, ok, fair
> enough. That said, the argument that "it may be hidden by P2SH!" isn't
> sufficient here. It has to *both* be hidden by P2SH and have never been
> spent from (either on mainnet or testnet) or be lock-timed a year in the
> future. I'm seriously skeptical that someone is using a highly esoteric
> scheme and has just been pouring money into it without ever having
> tested it or having withdrawn any money from it whatsoever. This is just
> a weird argument.
>

No one is required to test their Scripts on a public testnet; they can use
regtest. Because these transactions are non-standard on mainnet, it could
take years to arrange for these funds to be recovered by having their
transactions mined directly, or take years to become valuable enough to be
worth bothering having them directly mined.  As I have noted elsewhere, you
cannot first make transactions non-standard and then use the fact that you
don't see them being used on mainnet to justify a soft-fork.

My argument isn't weird; it is principled.  You are skeptical that any uses
of OP_CODESEPARATOR have P2SH commitments.  I am also skeptical, and so is
everyone reading this mailing list.  But none of us know this with
certainty, and it is /wrong/ for any of us to gamble with other people's
money that our assumptions are true.

Instead, it is this soft-fork proposal that is unprecedented. Let me
reiterate what I posted in another thread:

Bitcoin has *never* made a soft-fork, since the time of Satoishi, that
invalidated transactions that send secured inputs to secured outputs
(excluding uses of OP_NOP1-OP_NOP10).

The fact that Bitcoin has stuck to this principle gives me and everyone
else confidence in the protocol; that anyone can secure their funds by
whatever scheme they dream up, and deploy it without needing permission or
anyone else to vet their Scripts. So long as they are not impairing the
Bitcoin protocol itself, the most that Bitcoin Core will do is stop
relaying their transactions by default.

Undermining this principle means undermining what provides Bitcoin's value
in the first place.

The problem in this particular case is that there exist valid secure
transactions that make use OP_CODESEPARATOR such that these transactions
themselves impair the Bitcoin protocol (through excessive validation costs)
in a way that, AFAIU, is fundamental to the nature of such transactions (in
particular, it isn't just due to an implementation detail of Bitcoin
Core).  Thus to fix this vulnerability we must necessarily violate the
principle of not invalidating, secure transactions.  However, this fact
isn't license to freely invalidate any transactions we want.  We ought to
strive to minimize the scope of violation of this principle.  Alice and Bob
from XYZ. corp should be able to keep their benign transaction illustrated
above, and we only eliminate those transactions that actually impair the
Bitcoin protocol.

This is the perfect opportunity to show the world that Bitcoin Core simply
doesn't take chances when it comes to other people money.

> Please don't strawman my position.  I am not suggesting we don't fix a
> > vulnerability in Bitcoin.  I am suggesting we find another way.  One
> > that limits the of risk destroying other people's money.
> >
> > Here is a more concrete proposal:  No matter how bad OP_CODESEPARATOR
> > is, it cannot be worse than instead including another input that spends
> > another identically sized UTXO.  So how about we soft-fork in a rule
> > that says that an input's weight is increased by an amount equal to the
> > number of OP_CODESEPARATORs executed times the sum of weight of the UTXO
> > being spent and 40 bytes, the weight of a stripped input. The risk of
> > destroying other people's money is limited and AFAIU it would completely
> > address the vulnerabilities caused by OP_CODESEPARATOR.
>
> You're 

Re: [bitcoin-dev] OP_CODESEPARATOR Re: BIP Proposal: The Great Consensus Cleanup

2019-03-09 Thread Russell O'Connor via bitcoin-dev
Hi Sjors,

On Fri, Mar 8, 2019 at 2:12 PM Sjors Provoost  wrote:

> Transaction weight currently doesn't consider OP codes, it only considers
> if bytes are part of the witness. Changing that to something more akin to
> Ethereums gas pricing sounds too complicated to even consider.
>

I did say per executed OP_CODESEPARATOR, but upon reflection, I agree that
we'd like to know the weight without execution.  I think counting the
number of occurrences of OP_CODESEPARATOR (perhaps at the same time we
count OP_CHECKSIG operations?) is a reasonable compromise, and increasing
the weight according to my proposed formula based on that count (ideally
we'd take OP_IF branches into account).


> I would also like to believe that whoever went through the trouble of
> using OP_CODESEPARATOR reads this list.
>

I wish this were the case too, but I don't think it is reasonable to assume
that (even maaku isn't subscribed
),
and I don't even think it is fair to assume such a someone necessarily even
speaks English.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] OP_CODESEPARATOR Re: BIP Proposal: The Great Consensus Cleanup

2019-03-08 Thread Russell O'Connor via bitcoin-dev
On Thu, Mar 7, 2019 at 2:50 PM Matt Corallo 
wrote:

> Replies inline.
>
> Matt
>
> On 3/7/19 3:03 PM, Russell O'Connor wrote:
> >
> > * OP_CODESEPARATOR in non-BIP 143 scripts fails the script
> validation.
> > This includes OP_CODESEPARATORs in unexecuted branches of if
> > statements,
> > similar to other disabled opcodes, but unlike OP_RETURN.
> >
> >
> > OP_CODESEPARATOR is the only mechanism available that allows users to
> > sign which particular branch they are authorizing for within scripts
> > that have multiple possible conditions that reuse the same public key.
>
> This is true, and yet it does not appear to actually be practically
> usable. Thus far, despite a ton of effort, I have not yet seen a
> practical use-case for OP_CODESEPARATOR (except for one example of it
> being used to make SegWit scripts ever-so-slightly more effecient in
> TumbleBit, hence why this BIP does not propose disabling it for SegWit).
>

It's very easy to construct a practical script using OP_CODESEPARATOR.

IF <2>   <2> CHECKMULTISIGVERIFY ELSE CODESEPARATOR
 CHECKSIGVERFY ENDIF

Now when someone hands Alice, the CFO of XYZ corp., some transaction, she
has the option of either signing it unilaterally herself, or creating a
partial signature such that the transaction additionally needs Bob, the
CEOs signature as well, and Alice's choice is committed to the blockchain
for auditing purposes later.

Now, there are many things you might object about this scheme, but my point
is that (A) regardless of what you think about this scheme, it, or similar
schemes, may have been devised by users, and (B) users may have already
committed funds to such schemes, and due to P2SH you cannot know that this
is not the case.


> > Because of P2SH you cannot know that no one is currently using this
> > feature.  Activating a soft-fork as describe above means these sorts of
> > funds would be permanently lost.  It is not acceptable to risk people's
> > money like this.
>
> (1) It has been well documented again and again that there is desire to
> remove OP_CODESEPARATOR, (2) it is well-documented OP_CODESEPARATOR in
> non-segwit scripts represents a rather significant vulnerability in
> Bitcoin today, and (3) lots of effort has gone into attempting to find
> practical use-cases for OP_CODESEPARATOR's specific construction, with
> no successes as of yet. I strongly, strongly disagree that the
> highly-unlikely remote possibility that someone created something before
> which could be rendered unspendable is sufficient reason to not fix a
> vulnerability in Bitcoin today.
>

Please don't strawman my position.  I am not suggesting we don't fix a
vulnerability in Bitcoin.  I am suggesting we find another way.  One that
limits the of risk destroying other people's money.

Here is a more concrete proposal:  No matter how bad OP_CODESEPARATOR is,
it cannot be worse than instead including another input that spends another
identically sized UTXO.  So how about we soft-fork in a rule that says that
an input's weight is increased by an amount equal to the number of
OP_CODESEPARATORs executed times the sum of weight of the UTXO being spent
and 40 bytes, the weight of a stripped input. The risk of destroying other
people's money is limited and AFAIU it would completely address the
vulnerabilities caused by OP_CODESEPARATOR.

Even soft forking a rule like, "it is illegal to execute an
OP_CODESEPARATOR after any CHECKSIG/CHECKMULTISIG operation", would be
vastly better than the current proposal, even though I would still object
to it.


> > I suggest an alternative whereby the execution of OP_CODESEPARATOR
> > increases the transactions weight suitably as to temper the
> > vulnerability caused by it.  Alternatively there could be some sort of
> > limit (maybe 1) on the maximum number of OP_CODESEPARATORs allowed to be
> > executed per script, but that would require an argument as to why
> > exceeding that limit isn't reasonable.
>
> You could equally argue, however, that any such limit could render some
> moderately-large transaction unspendable, so I'm somewhat skeptical of
> this argument. Note that OP_CODESEPARATOR is non-standard, so getting
> them mined is rather difficult in any case.
>

I already know of people who's funds are tied up due to in other changes to
Bitcoin Core's default relay policy.  Non-standardness is not an excuse to
take other people's tied up funds and destroy them permanently.

There is some sort of crisis in the Bitcoin protocol stemming from the
possible excessive usage of OP_CODESEPARTOR otherwise we wouldn't even be
considering this soft fork.  Fine.  But presumably it is impossible for a
transaction to both be produced in good faith for legitimate use and at the
same time are expensive enough to be used as an attack vector, and
hopefully there is a wide gap between these two cases.  So let's draw a
line between the two cases to rule out attacks while allowing legitimate
uses by simply suitably pricing the 

Re: [bitcoin-dev] Sighash Type Byte; Re: BIP Proposal: The Great Consensus Cleanup

2019-03-08 Thread Russell O'Connor via bitcoin-dev
On Thu, Mar 7, 2019 at 2:57 PM Matt Corallo 
wrote:

> I can't say I'm particularly married to this idea (hence the alternate
> proposal in the original email), but at the same time the lack of
> existing transactions using these bits (and the redundancy thereof -
> they don't *do* anything special) seems to be pretty strong indication
> that they are not in use. One could argue a similarity between these
> bits and OP_NOPs - no one is going to create transactions that require
> OP_NOP execution to be valid as they are precisely the kind of thing
> that may get soft-forked to have a new meaning. While the sighash bits
> are somewhat less candidates for soft-forking,


I don't think "somewhat less candidates for soft-forking" is a fair
description.  These bits essentially unsuitable for soft-forking within
legacy Script.

I don't think "someone
> may have shoved random bits into parts of their
> locked-for-more-than-a-year transactions" is sufficient reason to not
> soft-fork something out.


I disagree. It is sufficient.

When was the last time Bitcoin soft-forked out working transactions that
sent funds from securely held UTXOs to securely held UTXOs (aside from
those secured by Scripts using the reserved OP_NOP1-OP_NOP10)?  AFAIK it
has never occurred since the time of Satoshi, even for the most
hypothetical of transactions.  It is my understanding is that Bitcoin Core
would never do such a thing unless the security of Bitcoin protocol itself
was under existential threat (see OP_CODESEPARATOR) and even then Bitcoin
Core would only soft-fork out the minimal amount necessary to safely
diffuse such a threat.

Since the above soft-fork isn't addressing addressing any such threat (that
I'm aware of), and could hypothetically destroy other people money, it
crosses a line I thought we were never supposed to cross.

>
> Obviously, actually *seeing* it used in
> practice or trying to fork them out in a fast manner would be
> unacceptable, but neither is being proposed here.
>

Perhaps you don't see them in used in the blockchain because the users
trying to use them are caught up by the fact they they are not being
relayed by default (violating SCRIPT_VERIFY_STRICTENC) and are having
difficulty redeeming them.
You cannot first make transactions non-standard and then use the fact that
you don't see them being used to justify a soft-fork.

I know of users who have their funds tied up due to other changes in
Bitcoin Core's default relay policy.  I believe they waiting for their
funds to become valuable enough to go through the trouble of having them
directly mined.  Shall we now permanently destroy their funds too, before
they have a chance to get their transactions mined?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Sighash Type Byte; Re: BIP Proposal: The Great Consensus Cleanup

2019-03-07 Thread Russell O'Connor via bitcoin-dev
> * If the sighash type byte (ie last byte in a signature being evaluated
> during the execution of OP_CHECKSIG[VERIFY] or OP_CHECKMULTISIG[VERIFY])
> is anything other than 1, 2, 3, 0x81, 0x82, or 0x83, the script
> execution fails. This does not apply to 0-length signature stack elements.
>

The sighash type byte is a "great" place to store a few bits of ancillary
data when making signatures.  Okay it isn't great, but it is good enough
that some misguided users may have been using it and have unbroadcast
transactions in cold storage (think sweeps) for UTXOs whose private keys
may have been lost.  I don't think that one's hunch that there isn't much
risk in disabling these sighashes is good enough to put people funds at
risk, especially given the alternative proposal of caching the
just-before-the-last-byte sighash midstate that is available.

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


Re: [bitcoin-dev] Schnorr and taproot (etc) upgrade

2018-12-19 Thread Russell O'Connor via bitcoin-dev
On Mon, Dec 17, 2018 at 3:16 PM Johnson Lau  wrote:

>
> I proposed the same in BIP114. I wish Satoshi had designed that way.
>

Thanks.  I probably read that and internalized it and forgot you wrote it.


> But I’m not sure if that would do more harm than good. For example, people
> might lose money by copying an existing script template. But they might
> also lose money in the same way as CHECKMULTISIG is disabled. So I’m not
> sure.
>
> Another related thing I’d like to bikeshed is to pop the stack after
> OP_CLTV and OP_CSV. The same pros and cons apply.
>

This one is almost a no-brainer I think.  Nearly every instance of OP_CSV
is followed by an OP_DROP and we'd save 1 WU per OP_CSV if we pop the stack
afterwards.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr and taproot (etc) upgrade

2018-12-19 Thread Russell O'Connor via bitcoin-dev
On Fri, Dec 14, 2018 at 8:39 AM Anthony Towns via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>   5. if there's exactly one, non-zero item on the stack; succeed
>

Unless it is too much bikeshedding, I'd like to propose that to succeed the
stack must be exactly empty.  Script is more composable that way, removing
the need for special logic to handle top-level CHECKSIG, vs mid-level
CHECKSIGVERIFY.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

2018-12-17 Thread Russell O'Connor via bitcoin-dev
On Wed, Dec 12, 2018 at 2:53 PM Johnson Lau  wrote:

>
> I think the root cause of witness weight malleability is some opcodes
> accept variable size input (without affecting the output), and that input
> is provided by the puzzle solver. Going through the opcode list, I think
> such opcodes include IF, NOTIF, VERIFY, DROP, 2DROP, NIP, DEPTH, and all
> arithmetic opcode that accepts CScriptNum (including CHECKMULTISIG)
>
> VERIFY, DROP, 2DROP, NIP are not real problem, since they should not be
> the first opcode to interact with data directly provided by the puzzle
> solver.
>
> CHECKMULTISIG is fixed by BIP147. For the key number and sig number, they
> should be part of the script, so not malleable.
>
> DEPTH is a problem only if its inputs are not later examined by other
> opcodes. Again, this is pointless.
>
> The liberally example should be protected by the MINIMAL_IF policy, which
> requires the input of OP_IF be minimal. As you note, OP_IF could be
> replaced by taproot in many cases
>
> Non-minimal CScriptNum is also banned as BIP62 policy.
>
> For the purpose of preventing malicious third party witness bloating, all
> we need is the miners to enforce the policy. There is no reason for miners
> to accept size malleated txs, as that will reduce the usable block space.
> If they hate a tx, they would simply drop it, instead of wasting the block
> space.
>

I don't know if it such a clear cut case for miner's policy.  A miner is
passed a malleated tx.  They know that there is probably a non-malleated
variant floating around out there somewhere, and they would rather have
it.  But right now they don't, and they probably not going to try to
unmalleate it themselves.  So, why not stick it into their mempool?  If it
eventually makes it into one of their blocks, then it will because it has
the best fee rate available, and to reject it outright is harmful to their
bottom line.  If they find the non-malleated variant later, great, they can
replace it and gain a higher-fee rate tx.  Of course, such a policy opens
them up to a Denial of Service attack.

So what do they do?  Do they accept malleated tx's and implement an RBF
policy that requires sufficient fee rate increases?  Do they reject
malleated txs outright to avoid falling in this trap in the first place as
you suggest?  I don't know, but I don't think things are as clear cut as
you present.


That aside, your list of weight malleable opcodes is shorter than I
imagined and I'm grateful you've compiled it.  Perhaps the best solution is
to make MINIMAL_IF and minimal CScriptNum consensus enforced in the next
version of Script and all but eliminate weight malleability in practice?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

2018-12-17 Thread Russell O'Connor via bitcoin-dev
On Wed, Dec 12, 2018 at 12:26 PM Gregory Maxwell  wrote:

> On Wed, Dec 12, 2018 at 5:15 PM Russell O'Connor via bitcoin-dev
>  wrote:
> > I tend to think in opposite terms. Is there a proof that any script can
> be transformed into an equivalent one that avoids witness weight
> malleability?   But I admit there is a trade off:  If we don't allow for
> signature covers weight, and we do need it, it will be too late to add.  On
> the other hand if we add signature covers weight, but it turns out that no
> Script ever needs to use it, then we've added that software complexity for
> no gain.  However, I think the software complexity is relatively low,
> making it worthwhile.
> >
> > Moreover, even if witness weight malleability is entirely avoidable, it
> always seems to come at a cost.  Taking as an example libwally's proposed
> "csv_2of3_then_2"
>
> I'm largely in agreement with you-- but my difficulty in arguing for
> signing the weight is that it seemed to me that it was only easy to
> sign an upper bound because some witnesses are variable size... and
> signing an upper bound means more signalling overhead... offsetting
> the space gains for demalleating.
>

In multi-party protocols, the last person to sign knows what the total
weight is going to be (now that we have fixed sized signatures) and at
least they have the ability to sign it.  They are probably motivated to
sign the weight as long as they are interested in the success of the
transaction.  I suppose there could be asynchronous protocols where there
isn't a last person to sign, but that seems a bit weird.  Greg, you are
probably more familiar with examples of multi-party protocols than I am.

OTOH maybe the last person to sign isn't interested in the success of the
transaction and wants to cause grief by bloating the transaction and
signing the bloated weight.  I guess in such protocols, you'll have to keep
the anti-malleablity Script Code.

I totally get the idea that signing weight has a lot of issues in many
scenarios.  But I still feel than on the whole it is better to make the
option available than to be forced to rely on anti-malleability Script Code
or non-consensus relay policy.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

2018-12-17 Thread Russell O'Connor via bitcoin-dev
On Wed, Dec 12, 2018 at 7:06 PM Anthony Towns  wrote:

> On Tue, Dec 11, 2018 at 05:50:24PM -0500, Russell O'Connor via bitcoin-dev
> wrote:
> > On Sun, Dec 9, 2018 at 2:13 PM Johnson Lau  wrote:
> > The current proposal is that a 64-byte signature will be used for the
> > default “signing all” sighash, and 65-byte for other sighash types.
> The
> > space saved will allow a few more txs in a block, so I think it
> worths
> > doing. However, this also makes witness weight estimation more
> difficult in
> > multisig cases.
>
> This seems strange to me -- why wouldn't you just assume every signature
> is 65 witness bytes, and just be grateful for the prioritisation benefit
> if someone chooses a shorter signature? Your error margin is just 0.25
> vbytes per signature.
>

The issue is that the proposal is to sign the actual weight, rather than
sign an upper bound on the weight.
The problem with signing an upper bound, is that you need to specify that
upper bound someplace in the transaction, and we are out of sneaky places
to stash that data.
Signing the actual weight is easy because the total weight is implicit, but
now you need to know the total weight before signing.


> > I tend to think in opposite terms. Is there a proof that any script can
> be
> > transformed into an equivalent one that avoids witness weight
> malleability?
>
> An alternative generalisation: is there a proof that all valid witnesses
> will have a weight within some small range?
>
> > Moreover, even if witness weight malleability is entirely avoidable, it
> always
> > seems to come at a cost.  Taking as an example libwally's proposed "
> > csv_2of3_then_2" Script, it begins with "OP_DEPTH OP_1SUB OP_1SUB"
>
> (DEPTH 2 NUMNOTEQUAL seems like it would have been more obvious...)
>
> I think the 1SUB idea was derived from the csv_2of2_then_1 Script where
DEPTH 1SUB is shorter than DEPTH 1 NUMNOTEQUAL.


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


Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

2018-12-11 Thread Russell O'Connor via bitcoin-dev
I don't believe that the default RBF policy works that way.  My
understanding is that current policy requires an absolute fee increase (by
an amount related to incrementalrelayfee).  There have been proposals to
change default RBF policy, however even my proposal <
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015717.html>
still requires a minimal amount of absolute fee increase as a DoS defense.

(I'm reading your comment as attempting to rebroadcast the original
transaction with the same fee amount, with its relatively higher fee-rate).

On Mon, Dec 10, 2018 at 10:00 AM David A. Harding  wrote:

> On Thu, Dec 06, 2018 at 11:57:09AM -0500, Russell O'Connor via bitcoin-dev
> wrote:
> > One more item to consider is "signature covers witness weight".
> >
> > While signing the witness weight doesn't completely eliminate witness
> > malleability (of the kind that can cause grief for compact blocks), it
> does
> > eliminate the worst kind of witness malleability from the user's
> > perspective, the kind where malicious relay nodes increase the amount of
> > witness data and therefore reduce the overall fee-rate of the
> transaction.
>
> To what degree is this an actual problem?  If the mutated transaction
> pays a feerate at least incremental-relay-fee[1] below the original
> transaction, then the original transaction can be rebroadcast as an RBF
> replacement of the mutated transaction (unless the mutated version has
> been pinned[2]).
>
> -Dave
>
> [1] $ bitcoind -help-debug | grep -A2 incremental
>   -incrementalrelayfee=
>Fee rate (in BTC/kB) used to define cost of relay, used for mempool
>limiting and BIP 125 replacement. (default: 0.1)
>
> [2]
> https://bitcoin.stackexchange.com/questions/80803/what-is-meant-by-transaction-pinning
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

2018-12-09 Thread Russell O'Connor via bitcoin-dev
One more item to consider is "signature covers witness weight".

While signing the witness weight doesn't completely eliminate witness
malleability (of the kind that can cause grief for compact blocks), it does
eliminate the worst kind of witness malleability from the user's
perspective, the kind where malicious relay nodes increase the amount of
witness data and therefore reduce the overall fee-rate of the transaction.
Generally users should strive to construct their Bitcoin Scripts in such a
way that witness malleability isn't possible, but as you are probably
aware, this can be quite difficult to achieve as Scripts become more
complex and maybe isn't even possible for some complex Scripts.

Given the new fixed-sized signature of the Schnorr BIP, it becomes much
easier to compute the final witness weight prior to signing.  In complex
multi-party signing protocol, the final witness weight might not be known
at signing time for everyone involved, so the "signature covers witness
weight" ought to be optional.


On Tue, Nov 27, 2018 at 11:59 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Mon, 19 Nov 2018 at 14:37, Pieter Wuille 
> wrote:
> > Here is a combined proposal:
> > * Three new sighash flags are added: SIGHASH_NOINPUT, SIGHASH_NOFEE, and
> SIGHASH_SCRIPTMASK.
> > * A new opcode OP_MASK is added, which acts as a NOP during execution.
> > * The sighash is computed like in BIP143, but:
> >   * If SIGHASH_SCRIPTMASK is present, for every OP_MASK in scriptCode
> the subsequent opcode/push is removed.
> >   * The scriptPubKey being spent is added to the sighash, unless
> SIGHASH_SCRIPTMASK is set.
> >   * The transaction fee is added to the sighash, unless SIGHASH_NOFEE is
> set.
> >   * hashPrevouts, hashSequence, and outpoint are set to null when
> SIGHASH_NOINPUT is set (like BIP118, but not for scriptCode).
>
> Thanks for all the input so far. Going over the suggestions and other
> ideas:
>
> * OP_MASK should be required to be followed by a push, as suggested by
> Anthony Towns. The alternative would permit substituting arbitrary
> opcodes for masked pushes, which is at least very hard to reason
> about. This would effectively turn it into a multi-byte OP_MASKEDPUSH
> opcode.
>
> * It's probably better to sign the amounts of all inputs, as suggested
> by Johnson Lau. As that would cause default sighashes to sign all
> input and output amounts, is there still a need to sign the tx fee
> explicitly? Or in other words, are there situations where changing the
> set of inputs or outputs after signing is desired, but the net
> difference between them cannot change? If not, that would remove the
> need for NOFEE.
>
> * Do we need to keep the rule that sequence values of other inputs are
> only signed with default sighash? It feels cleaner to always sign the
> sequence values of all inputs that are included in the sighash anyway
> (so all of them, unless ANYONECANPAY or NOINPUT, which would make it
> sign only the current input's sequence value). If NOINPUT also blanks
> the sequence values (as currently specified by BIP118), and all input
> amounts are signed, that would make amounts/sequence values always be
> treated identically.
>
> * If MASK implies NOINPUT, and NOINPUT implies ANYONECANPAY, the 3 of
> them can be encoded in just 2 bits using the
> PARTIALSCRIPT/KNOWNSCRIPT/KNOWNTX/ALL_INPUTS encoding Anthony Towns
> suggested.
>
> * Regarding the discussion about preventing signatures from being
> rebound to a different script(path)/checksig:
>   * With MAST there is indeed less need for this, but at least
> single-tree MAST constructions cannot replace all script branches (a
> script with 40 IF/THEN/ELSE constructions may have 2^40 different
> execution paths, for which computing a Merkle tree is intractable).
>   * Just signing the opcode position of the CHECKSIG operator isn't
> enough for all cases either. For example, you could have a complex
> nested set of branches that puts a number of pubkeys on the stack, and
> then a CHECKMULTISIG after the last ENDIF to verify all of them. In
> such a situation, if the same key can occur in multiple combinations,
> you still may want to prevent a signature generated for one
> combination from being rebindable to the same key in another
> combination. I believe that signing the opcode position plus the
> true/false condition of all previous(?) IF statements is probably
> sufficient to achieve that, but it would also introduce unnecessary
> complexity for signers in most cases (see next point).
>   * Thinking about signing code, adding these sort of execution trace
> commitments to the sighash means they need to know which checksig
> operator etc. they are signing for. I believe that in practice for
> example HW devices will just whatever position the wallet indicated,
> rather than verifying it corresponds with a particular intended code
> path. Preventing rebinding isn't very useful if an attacker can make
> you bind 

Re: [bitcoin-dev] CPFP Carve-Out for Fee-Prediction Issues in Contracting Applications (eg Lightning)

2018-11-30 Thread Russell O'Connor via bitcoin-dev
On Fri, Nov 30, 2018 at 9:50 AM Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> To partially-address the CPFP security model considerations, a next step
> might involve tweaking Lightning's commitment transaction to have two
> small-value outputs which are immediately spendable, one by each channel
> participant, allowing them to chain children off without allowng
> unrelated third-parties to chain children. Obviously this does not
> address the specific attack so we need a small tweak to the anti-DoS
> CPFP rules in Bitcoin Core/BIP 125:
>

It seems to me that this two-output scheme does address the specific attack
without tweaking the RBF rules of BIP 125, since you are not doing an RBF
at all.

Suppose we have a 1k-vbyte unconfirmed transaction, TX0, with outputs Z, A,
and B, where A and B are small outputs controlled by the participants Alice
and Bob respectively, with a 1ksat fee, yielding a fee rate of 1sat/vbyte.
Someone, maybe Alice, attempts to pin the transaction, maliciously or not,
by attaching a 10k-vbyte transaction, TX1, to either output Z or output A,
with a fee of 21ksats.  This brings the fee rate for the TX0-TX1 package to
2sat/vbyte, being 11k-vbyte total size with 22ksats in total fees.

Now Bob wants to CPFP to increase the effective fee rate of TX0 to
3sats/vbyte using output B.  He attaches a 1k-vbyte transaction, TX2, to
output B with a fee of 5ksats.  This ought to create a new TX0-TX2 package
with a 3sat/vbyte fee rate, being 2k-vbyte total size with 6ksats in total
fees.  TX1 has now been excluded from the package containing TX0. But TX1
hasn't been replaced, so the RBF rules from BIP125 don't apply.  TX1 is
still a valid unconfirmed transaction operating at a fee rate of
2.1sats/vbyte.

That said, I'm not an expert on how packages and package fee rates are
calculated in Bitcoin Core, so I am speculating a bit.  And, because I'm
talking with Matt, it's more likely that I'm mistaken.  AFAIK, any rules
about CPFP's behaviour in Bitcoin Core is undocumented.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

2018-11-24 Thread Russell O'Connor via bitcoin-dev
On Fri, Nov 23, 2018 at 12:03 AM Anthony Towns  wrote:

> On Wed, Nov 21, 2018 at 12:07:30PM -0500, Russell O'Connor via bitcoin-dev
> wrote:
> > Given that we want to move away from OP_CODESEPARATOR, because each call
> to
> > this operation effectively takes O(script-size) time, we need a
> replacement for
> > the functionality it currently provides.  While perhaps the original
> motivation
> > for OP_CODESEPARTOR is surrounded in mystery, it currently can be used
> (or
> > perhaps abused) for the task of creating signature that covers, not only
> which
> > input is being signed, but which specific branch within that input
> Script code
> > is being signed for.
>
> Would it be sufficient to sign the position within the script of the
> last OP_CODESEPARATOR? That is, if your script is:
>
> I think that covers all the behaviour you can currently achieve with
> CODESEP (which is pretty limited since every sig effectively commits
> to the full redeem script, and you can't commit to subsets of the
> signature/witness), and it keeps the things you can do with the various
> features a bit orthogonal:
>

Thanks for bringing this up.  I was thinking the same thing as well, that
yes that should be sufficient to cover the semantics of OP_CODESEPARATOR.
Though to be more precise you would sign the position of the last
_executed_ OP_CODESEPARATOR.

That said, while I agree the above is a superior realization of the
OP_CODESEPARATOR, given that we are probably going to support
OP_CODESEPARATOR inside legacy P2SH scripts indefinitely, it is probably
better to keep the existing akward implementation of OP_CODESEPARATOR in
future versions of Script.  (At least until we decide to stop mangling the
Script consensus code with more and more flag combinations and decide it is
better to cut and paste code for new versions of Script to help ensure we
don't make consensus changes to legacy behaviour).


> [0] (I think I'm going to claim "MAST" stands for "merkelized alternative
>  script tree" these days, since they're not "abstract syntax trees")
>

:thumbs-up:

Sorry for hijacking the thread about OP_MASK and friends.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

2018-11-23 Thread Russell O'Connor via bitcoin-dev
On Thu, Nov 22, 2018 at 3:53 PM Johnson Lau  wrote:

> Assuming a script size of 128 bytes (including SHA256 padding), 2^20
> scripts is 134MB. Double it to 268MB for the merkle branch hashes. With
> roughly 100MB/s, this should take 2.5s (or 42min for 30 levels). However,
> memory use is not considered.
>
> >each call to this operation effectively takes O(script-size) time
> I’m not sure if this is correct. Actually,
> CTransactionSignatureSerializer() scans every script for OP_CODESEPARATOR.
> Scripts with and without OP_CODESEPARATOR should take exactly the same
> O(script-size) time (see https://github.com/bitcoin/bitcoin/pull/14786)
> Also, this is no longer a concern under segwit (BIP143), which
> CTransactionSignatureSerializer() is not used. Actually, OP_CODESEPARATOR
> under segwit is way simpler than the proposed OP_MASK. If one finds OP_MASK
> acceptable, there should be no reason to reject OP_CODESEPARATOR.
>

Even still, each call to OP_CODESEPARATOR / OP_CHECKSIG pair requires
recomputing a new #5. scriptCode from BIP 143, and hence computes a new
transaction digest.  I understood that this issue was the main motivation
for wanting to deprecate OP_CODESEPARATOR and remove it from later versions
of script.

However, given that we are looking at a combinatorial explosion in SIGHASH
flag combinations already, coupled with existing SigOp limitations, maybe
the cost of recomputing scriptCode with OP_CODESEPARATOR isn't such a big
deal.

And even if we choose remove the behavior of OP_CODESEPARATOR in new
versions of Script, it seems more than 30 layers of sequential OP_IFs can
be MASTified, so there is no need to use OP_CODESEPARATOR within that limit.

>One suggestion I heard (I think I heard it from Pieter) to achieve the
above is to add an internal counter that increments on every control flow
operator,……...

> If I have to choose among OP_CODESEPARATOR and “flow operator counting”,
> I’d rather choose OP_CODESEPARATOR. At least we don’t need to add more
> lines to the consensus code, just for something that is mostly archivable
> with MAST.
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

2018-11-23 Thread Russell O'Connor via bitcoin-dev
I see, so your suggestion is that a sequence of OP_IF ... OP_ENDIF can be
replaced by a Merklized Script tree of that depth in practice.

I'm concerned that at script creation time it takes exponential time to
complete a Merkle root of depth 'n'.  Can anyone provide benchmarks or
estimates of how long it takes to compute a Merkle root of a full tree of
various depths on typical consumer hardware?  I would guess things stop
becoming practical at a depth of 20-30.

On Thu, Nov 22, 2018 at 9:28 AM Johnson Lau  wrote:

> With MAST in taproot, OP_IF etc become mostly redundant, with worse
> privacy. To maximise fungibility, we should encourage people to use MAST,
> instead of improve the functionality of OP_IF and further complicate the
> protocol.
>
>
> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> So my question is whether anyone can see ways in which this introduces
>> redundant flexibility, or misses obvious use cases?
>>
>
> Hopefully my comment is on-topic for this thread:
>
> Given that we want to move away from OP_CODESEPARATOR, because each call
> to this operation effectively takes O(script-size) time, we need a
> replacement for the functionality it currently provides.  While perhaps the
> original motivation for OP_CODESEPARTOR is surrounded in mystery, it
> currently can be used (or perhaps abused) for the task of creating
> signature that covers, not only which input is being signed, but which
> specific branch within that input Script code is being signed for.
>
> For example, one can place an OP_CODESEPARATOR within each branch of an IF
> block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG
> operation.  By doing so, signatures created for one clause cannot be used
> as signatures for another clause.  Since different clauses in Bitcoin
> Script may be enforcing different conditions (such as different time-locks,
> hash-locks, etc), it is useful to be able to sign in such a way that your
> signature is only valid when the conditions for a particular branch are
> satisfied.  In complex Scripts, it may not be practical or possible to use
> different public keys for every different clause. (In practice, you will be
> able to get away with fewer OP_CODESEPARATORS than one in every IF block).
>
> One suggestion I heard (I think I heard it from Pieter) to achieve the
> above is to add an internal counter that increments on every control flow
> operator, OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, and have the signature cover
> the value of this counter.  Equivalently we divide every Bitcoin Script
> program into blocks deliminated by these control flow operator and have the
> signature cover the index of the block that the OP_CHECKSIG occurs within.
> More specifically, we will want a SigHash flag to enables/disable the
> signature covering this counter.
>
> There are many different ways one might go about replacing the remaining
> useful behaviour of OP_CODESEPARATOR than the one I gave above. I would be
> happy with any solution.
> ___
> 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] Safer sighashes and more granular SIGHASH_NOINPUT

2018-11-22 Thread Russell O'Connor via bitcoin-dev
On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> So my question is whether anyone can see ways in which this introduces
> redundant flexibility, or misses obvious use cases?
>

Hopefully my comment is on-topic for this thread:

Given that we want to move away from OP_CODESEPARATOR, because each call to
this operation effectively takes O(script-size) time, we need a replacement
for the functionality it currently provides.  While perhaps the original
motivation for OP_CODESEPARTOR is surrounded in mystery, it currently can
be used (or perhaps abused) for the task of creating signature that covers,
not only which input is being signed, but which specific branch within that
input Script code is being signed for.

For example, one can place an OP_CODESEPARATOR within each branch of an IF
block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG
operation.  By doing so, signatures created for one clause cannot be used
as signatures for another clause.  Since different clauses in Bitcoin
Script may be enforcing different conditions (such as different time-locks,
hash-locks, etc), it is useful to be able to sign in such a way that your
signature is only valid when the conditions for a particular branch are
satisfied.  In complex Scripts, it may not be practical or possible to use
different public keys for every different clause. (In practice, you will be
able to get away with fewer OP_CODESEPARATORS than one in every IF block).

One suggestion I heard (I think I heard it from Pieter) to achieve the
above is to add an internal counter that increments on every control flow
operator, OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, and have the signature cover
the value of this counter.  Equivalently we divide every Bitcoin Script
program into blocks deliminated by these control flow operator and have the
signature cover the index of the block that the OP_CHECKSIG occurs within.
More specifically, we will want a SigHash flag to enables/disable the
signature covering this counter.

There are many different ways one might go about replacing the remaining
useful behaviour of OP_CODESEPARATOR than the one I gave above. I would be
happy with any solution.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-09-21 Thread Russell O'Connor via bitcoin-dev
It would be helpful to add the intermediate 'e' values computed to the
first four test vectors.

On Fri, Jul 6, 2018 at 2:08 PM, Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> over the same curve as is currently used in ECDSA:
> https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
>
> It is simply a draft specification of the signature scheme itself. It
> does not concern consensus rules, aggregation, or any other
> integration into Bitcoin - those things are left for other proposals,
> which can refer to this scheme if desirable. Standardizing the
> signature scheme is a first step towards that, and as it may be useful
> in other contexts to have a common Schnorr scheme available, it is its
> own informational BIP.
>
> If accepted, we'll work on more production-ready reference
> implementations and tests.
>
> This is joint work with several people listed in the document.
>
> Cheers,
>
> --
> Pieter
> ___
> 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] Schnorr signatures BIP

2018-08-06 Thread Russell O'Connor via bitcoin-dev
On Mon, Aug 6, 2018 at 4:39 AM, Anthony Towns  wrote:

> On Sun, Aug 05, 2018 at 10:33:52AM -0400, Russell O'Connor via bitcoin-dev
> wrote:
> > In light of this, I revise my proposed change to make the verification
> > equation
> >
> > R + sG + eP = 0.
>
> Isn't the verification equation "R + s(-G) + eP = 0" equally good, then,
> since -G is a constant? (ie, at worst it's a matter of optimising the
> verifier for -G as well as G)
>

Yes you are right.

Thanks, I withdraw my proposal.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-08-05 Thread Russell O'Connor via bitcoin-dev
Over chat it has been pointed out to me that computing the non-quadratic
residue is not the same cost as computing a quadratic residue.  As pointed
out in footnote 7 of the the proposed BIP, c^((p+1)/4) is always a
quadratic residue and must be negated to find the non-quadratic residue.

In light of this, I revise my proposed change to make the verification
equation

R + sG + eP = 0.

(by 0 in the equation above I mean the identity element for the (+)
operation, which is the point at infinity.)

This equation is suitable for batch verification.  This equation is clearly
written as a linear combination that doesn't use negation.  In most
implementations, equality comparison tests are implemented by subtraction
and a comparison with zero. By writing the verification equation this way,
we clearly see that only the comparison with zero test is needed.

For single signature verification the check becomes, compute Q := sG + eP.
Verify that Q isn't the point at infinity and Q.x = r.  Verify that Q.y is
*not* a quadratic residue. (While I was incorrect earlier about the costs
of computing a non-residue, it is the case the *verifying* a value is a
quadratic residue is the same cost as verifying a value is a non-residue.)

Effectively in my first email I was suggesting that the 'e' value in a
signature be negated from the current BIP proposal.  In this revision I am
effectively suggesting that the 's' value in a signature should be the one
that is negated instead.

On Sat, Aug 4, 2018 at 8:22 AM, Russell O'Connor 
wrote:

> I propose changing the verification equation from "Let *R = sG - eP*" to
>
> Let *R = sG + eP*
>
> This allows faster verification by avoiding negating a point (or a
> coefficient).
>
>
> If, instead of directly following the literal verification specification,
> one is instead reconstructing R from r by finding a y coordinate that is a
> quadratic residue, under the existing scheme one would verify
>
>
> *sG - eP = R*
>
> which is effectively verifying
>
>   0 = *sG - eP* - R  or 0 = R - *sG + eP*
>
> Either way one needs to negate at least one point (or one coefficient)
> because of the opposite signs between sG and eP.
>
>
> Under my proposed revised verification scheme, one would instead verify
>
>   0 = sG + eP + (-R).
>
> While it seems that this requires negating R, it does not.  Rather (-R)
> can be directly constructed from r by finding a y coordinate that is *not*
> a quadratic residue, which is precisely the same amount of work that
> construction R from r was.
>
> In either verification procedure, changing the verification equation to my
> proposal removes one negation operation from the cost of doing verification.
>
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-08-04 Thread Russell O'Connor via bitcoin-dev
I propose changing the verification equation from "Let *R = sG - eP*" to

Let *R = sG + eP*

This allows faster verification by avoiding negating a point (or a
coefficient).


If, instead of directly following the literal verification specification,
one is instead reconstructing R from r by finding a y coordinate that is a
quadratic residue, under the existing scheme one would verify


*sG - eP = R*

which is effectively verifying

  0 = *sG - eP* - R  or 0 = R - *sG + eP*

Either way one needs to negate at least one point (or one coefficient)
because of the opposite signs between sG and eP.


Under my proposed revised verification scheme, one would instead verify

  0 = sG + eP + (-R).

While it seems that this requires negating R, it does not.  Rather (-R) can
be directly constructed from r by finding a y coordinate that is *not* a
quadratic residue, which is precisely the same amount of work that
construction R from r was.

In either verification procedure, changing the verification equation to my
proposal removes one negation operation from the cost of doing verification.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] A BIP proposal for segwit addresses

2018-07-26 Thread Russell O'Connor via bitcoin-dev
I think I phrased this badly.

What I mean is that there should be a note that HRP should be specified in
lowercase, or at least mention that uppercase and lowercase HRPs are
considered equivalent and will be canonicalized to lowercase during
validation.

On Thu, Jul 26, 2018 at 9:43 AM, Russell O'Connor 
wrote:

> Hi Pieter,
>
> > The *human-readable part*, which is intended to convey the type of
> data, or anything else that is relevant to the reader. This part MUST
> contain 1 to 83 US-ASCII characters, with each character having a value in
> the range [33-126]. HRP validity may be further restricted by specific
> applications.
>
> You should also add to this section that the HRP should be lowercase.
>
> Since Bech32 forbids mixed-case and otherwise converts everything to
> lowercase, it is good to warn upfront against using uppercase in the HRP.
>
> I know the BIP is marked as final, but this wouldn't be a normative change.
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] A BIP proposal for segwit addresses

2018-07-26 Thread Russell O'Connor via bitcoin-dev
Hi Pieter,

> The *human-readable part*, which is intended to convey the type of data,
or anything else that is relevant to the reader. This part MUST contain 1
to 83 US-ASCII characters, with each character having a value in the range
[33-126]. HRP validity may be further restricted by specific applications.

You should also add to this section that the HRP should be lowercase.

Since Bech32 forbids mixed-case and otherwise converts everything to
lowercase, it is good to warn upfront against using uppercase in the HRP.

I know the BIP is marked as final, but this wouldn't be a normative change.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Multiparty signatures

2018-07-19 Thread Russell O'Connor via bitcoin-dev
On Thu, Jul 19, 2018 at 8:16 AM, Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>  you can't birthday attack something where there's only a single variable
> that you can modify.
>

When engaging in a multiparty signature, the attacker can more than one
variable to modify.  When you are party to a multi-party signature (for
example, in some sort of coin-join protocol) it could be that every other
participant in the multi-party signature is, in fact, the same single
attacker representing themselves as multiple participants.  This is how the
attacker gets their hands on multiple variables.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-07-08 Thread Russell O'Connor via bitcoin-dev
On Fri, Jul 6, 2018 at 6:00 PM, Gregory Maxwell  wrote:

> On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev
>  wrote:
> > If the inputs to hash were reordered as hash(bytes(dG) || bytes(x(R)) ||
> m)
> > then there is an opportunity for SHA256 expander to be partially
> prefilled
> > for a fixed public key.  This could provide a little benefit, especially
> > when multiple signatures for a single public key need to be generated
> and/or
> > verified.  If all things are otherwise equal, perhaps this alternate
> order
> > is better.
>
> There is a minor design preference to have message before nonce when
> H() is a MD-style hash function.  Say the attacker knows some weakness
> in H and can find pairs of messages m and m' so that the compression
> function results in the same midstate.  He could then ask you to sign
> m but get a signature that also works for m'.   If the signer
> controlled R value comes first, then this doesn't work.The pubkey
> being where it is in the current design just follows from the idea
> that it is just logically prepended on the message.  I don't think the
> pubkey is sufficiently attacker controlled that the above argument
> would apply,  so H(P || R.x || m) would be okay.
>
> BUT, the sha256 compression function reads 64 bytes at a time. PRM
> would not let you precompute a whole compression function run, but
> instead would just let you hardwire part of the expander in a pubkey
> dependant way-- an optimization I'm pretty confident virtually no one
> would use.  (Hardwiring to a constant, yes. Hardwiring to a reused
> dynamic value that comes in from the network, no)
>

Right.  I readily admit my proposal has extremely marginal efficiency
benefits. However, I didn't realize there is also an extremely marginal
security benefit to placing the nonce in front of everything.  Although
these things are so marginal that it is perhaps a waste of time to even be
considering them, I think I'd judge the extremely marginal security benefit
to exceed the value of the extremely marginal efficiency gain.  It's
probably best to leave the nonce at the beginning after all.


> If instead the hash function were defined as using 31 zeros then
> P||R||m (or P || 31 zeros bytes || R || m, I'm not sure what would be
> better), an entire midstate could be cached for different pubkeys. m
> is often 32 bytes, sadly- - but the final compression run in that case
> would only be the constant update with the length and
> almost-all-zeros + constant length, is an easy optimization. (Bitcoin
> core even has it for computing sha256(sha256())).
>

I did consider this, however the 31 bytes of zeros, plus the SHA256 padding
means we would need to compress *three* blocks in general instead of the
current proposal of just two blocks.  This burden seems to exceed the
benefit of maybe sometimes getting a slightly fast
two-blocks-with-lots-of-zeros when public keys are reused. I wouldn't
recommend it.

There is an alternative of just dropping the SHA-256 length padding.  This
would still be secure in this context because the data is of fixed size.
However, I doubt it is worth breaking the API of every SHA-256 library in
existence to enable that.


> [I'm not really sure if I was clear, so I'll try TLDRing it:  I think
> optimizing sha256 where part of the input is constant is realistic,
> optimizing midstate reuse is realistic, optimizing where part is
> reused is less realistic.  If we insert padding, and put P first, we
> can make it possible to midstate cache P,  and the 'extra' compression
> function run ends up with all constant input, so it could be made
> faster.]
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr signatures BIP

2018-07-06 Thread Russell O'Connor via bitcoin-dev
Some quick comments:

Signing
>
> To sign:
>
>- Let *k = int(hash(bytes(d) || m)) mod n*[8
>
> 
>].
>- Let *R = kG*.
>- If *jacobi(y(R)) ≠ 1*, let *k = n - k*.
>- Let *e = int(hash(bytes(x(R)) || bytes(dG) || m)) mod n*.
>- The signature is *bytes(x(R)) || bytes(k + ex mod n)*.
>
> Can we avoid mutable variables in these specification?  I know this is
commonly done in RFCs, but I think it is fairly confusing to have `k`
defined in two different ways within a single specification.
Let's let k' = k when jacobi(y(R)) = 1 and let k' = n - k when jacobi(y(R))
= -1.  Note that this ensures that jacobi(y(k'G)) = 1.

Also you've sort of left it undefined what to do when k = 0.  According to
the current specification, you will produce an invalid signature.  The
expected result is that you should win a 1000 BTC prize.

One solution is to let k = *1 + int(hash(bytes(d) || m)) mod (n-1)*.
Alternatively you could let k' = 1 when k = 0.  Or you could just make a
note that signature generation fails with this message and private key pair
when this happens.

Let *e = int(hash(bytes(x(R)) || bytes(dG) || m)) mod n*.
>

P = dG should probably be noted somewhere in the text.  I.e. this signature
is generated for the public key P = dG.

If the inputs to hash were reordered as *hash(bytes(dG) || bytes(x(R)) ||
m)* then there is an opportunity for SHA256 expander to be partially
prefilled for a fixed public key.  This could provide a little benefit,
especially when multiple signatures for a single public key need to be
generated and/or verified.  If all things are otherwise equal, perhaps this
alternate order is better.

 The signature is *bytes(x(R)) || bytes(k + ex mod n)*.


You haven't defined `x`.  I'm guessing you mean `d` instead.

> Optimizations
>
> *Jacobian coordinates*
>
>- *oncurve(P)* can be implemented as *y2 = x3 + 7z6 mod p*.
>
> oncurve(P) requires that `P` be on the curve and not infinity.  You need
another condition here to ensure that `P` is not infinity.


On Fri, Jul 6, 2018 at 2:08 PM, Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here is a proposed BIP for 64-byte elliptic curve Schnorr signatures,
> over the same curve as is currently used in ECDSA:
> https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
>
> It is simply a draft specification of the signature scheme itself. It
> does not concern consensus rules, aggregation, or any other
> integration into Bitcoin - those things are left for other proposals,
> which can refer to this scheme if desirable. Standardizing the
> signature scheme is a first step towards that, and as it may be useful
> in other contexts to have a common Schnorr scheme available, it is its
> own informational BIP.
>
> If accepted, we'll work on more production-ready reference
> implementations and tests.
>
> This is joint work with several people listed in the document.
>
> Cheers,
>
> --
> Pieter
> ___
> 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] New serialization/encoding format for key material

2018-06-15 Thread Russell O'Connor via bitcoin-dev
> For codes designed for length 341 (the first length enough to support
> 512 bits of data):
> * correct 1 error = 3 checksum characters
> * correct 2 errors = 7 checksum characters
> * correct 3 errors = 11 checksum characters
> * correct 4 errors = 15 checksum characters
> * correct 5 errors = 19 checksum characters
> * ...
> * correct 7 errors = 26 checksum characters (~ length * 1.25)
> * correct 13 errors = 51 checksum characters (~ length * 1.5)
> * correct 28 errors = 102 checksum characters (~ length * 2)
>
> So it really boils down to a trade-off between length of the code, and
> recovery properties.
>

At the risk of making the proposal more complex, I wonder if it might be
better to support multiple checksum variants?  The trade-off between code
length and recovery seems to be largely determined by the user's medium of
storage, which is likely to vary from person to person.  I personally would
probably be interested in the 51 or even 102 character checksums variants.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] New serialization/encoding format for key material

2018-06-13 Thread Russell O'Connor via bitcoin-dev
On Tue, May 29, 2018 at 5:13 AM, Jonas Schnelli via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi
>
> If 520 bits are present, first 256 bits are the BIP32 chain code, to
> second 264
> bits (33 bytes) define the public key (according to BIP32)
>

In a 33 byte compressed public key, only 1 bit from the first byte conveys
information.  The other 7 bits can be discarded.  This will allow you to
reduce the bech32 encoded result by one character.
___
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

2018-06-01 Thread 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

2018-06-01 Thread 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


Re: [bitcoin-dev] Making OP_TRUE standard?

2018-05-21 Thread Russell O'Connor via bitcoin-dev
In the thread "Revisting BIP 125 RBF policy" @
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015717.html
and
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015797.html
I propose replacing rule 3 with a rule that instead demands that the
replacement package fee rate exceeds the package fee rate of the original
transactions, and that there is an absolute fee bump of the particular
transaction being replaced that covers the min-fee rate times the size of
the mempool churn's data size.

Perhaps this would address your issue too Rusty.

On Sun, May 20, 2018 at 11:44 PM, Rusty Russell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Jim Posen  writes:
> > I believe OP_CSV with a relative locktime of 0 could be used to enforce
> RBF
> > on the spending tx?
>
> Marco points out that if the parent is RBF, this child inherits it, so
> we're actually good here.
>
> However, Matt Corallo points out that you can block RBF will a
> large-but-lowball tx, as BIP 125 points out:
>
>will be replaced by a new transaction...:
>
>3. The replacement transaction pays an absolute fee of at least the sum
>   paid by the original transactions.
>
> I understand implementing a single mempool requires these kind of
> up-front decisions on which tx is "better", but I wonder about the
> consequences of dropping this heuristic?  Peter?
>
> Thanks!
> 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/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] MAST/Schnorr related soft-forks

2018-05-10 Thread Russell O'Connor via bitcoin-dev
Thanks for writing this up Anthony.

Do you think that a CHECKSIGFROMSTACK proposal should be included within
this discussion of signature soft-forks, or do you see it as an unrelated
issue?

CHECKSIGFROMSTACK enables some forms of (more) efficent MPC (See
http://people.csail.mit.edu/ranjit/papers/scd.pdf), enables poor-man's
covenants, and I believe the lightning folks are interested in it as well
for some constant space storage scheme.

On Thu, May 10, 2018 at 8:10 AM, Anthony Towns via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello world,
>
> After the core dev meetup in March I wrote up some notes of where I
> think things stand for signing stuff post-Schnorr. It was mostly for my
> own benefit but maybe it's helpful for others too, so...
>
> They're just notes, so may assume a fair bit of background to be able to
> understand the meaning of the bullet points. In particular, note that I'm
> using "schnorr" just to describe the signature algorithm, and the terms
> "key aggregation" to describe turning an n-of-n key multisig setup into
> a single key setup, and "signature aggregation" to describe combining
> signatures from many inputs/transactions together: those are often all
> just called "schnorr signatures" in various places.
>
>
> Anyway! I think it's fair to split the ideas around up as follows:
>
> 1) Schnorr CHECKSIG
>
>   Benefits:
> - opportunity to change signature encoding from DER to save a few
>   bytes per signature, and have fixed size signatures making tx size
>   calculations easier
>
> - enables n-of-n multisig key aggregation (a single pubkey and
>   signature gives n-of-n security; setup non-interactively via muSig,
>   or semi-interactively via proof of possession of private key;
>   interactive signature protocol)
>
> - enables m-of-n multisig key aggregation with interactive setup and
>   interactive signature protocol, and possibly substantial storage
>   requirements for participating signers
>
> - enables scriptless scripts and discreet log contracts via
>   key aggregation and interactive
>
> - enables payment decorrelation for lightning
>
> - enables batch validation of signatures, which substantially reduces
>   computational cost of signature verification, provided a single
>   "all sigs valid" or "some sig(s) invalid" output (rather than
>   "sig number 5 is invalid") is sufficient
>
> - better than ecdsa due to reducing signature malleability
>   (and possibly due to having a security proof that has had more
>   review?)
>
>Approaches:
>  - bump segwit version to replace P2WPKH
>  - replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY
>  - hardfork to allowing existing addresses to be solved via Schnorr sig
>as alternative to ECDSA
>
> 2) Merkelized Abstract Syntax Trees
>
>Two main benefits for enabling MAST:
> - logarithmic scaling for scripts with many alternative paths
> - only reveals (approximate) number of alternative execution branches,
>   not what they may have been
>
>Approaches:
> - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and treat an
>   item remaining on the alt stack at the end of script exeution as a
>   script and do tail-recursion into it (BIP 116, 117)
> - bump the segwit version and introduce a "pay-to-merkelized-script"
>   address form (BIP 114)
>
> 3) Taproot
>
>Requirements:
> - only feasible if Schnorr is available (required in order to make the
>   pubkey spend actually be a multisig spend)
> - andytoshi has written up a security proof at
>   https://github.com/apoelstra/taproot
>
>Benefits:
> - combines pay-to-pubkey and pay-to-script in a single address,
>   improving privacy
> - allows choice of whether to use pubkey or script at spend time,
>   allowing for more efficient spends (via pubkey) without reducing
>   flexibility (via script)
>
>Approaches:
> - bump segwit version and introduce a "pay-to-taproot" address form
>
> 4) Graftroot
>
>Requirements:
> - only really feasible if Schnorr is implemented first, so that
>   multiple signers can be required via a single pubkey/signature
> - people seem to want a security proof for this; not sure if that's
>   hard or straightforward
>
>Benefits:
> - allows delegation of authorisation to spend an output already
>   on the blockchain
> - constant scaling for scripts with many alternative paths
>   (better than MAST's logarithmic scaling)
> - only reveals the possibility of alternative execution branches,
>   not what they may have been or if any actually existed
>
>Drawbacks:
> - requires signing keys to be online when constructing scripts (cannot
>   do complicated pay to cold wallet without warming it up)
> - requires storing signatures for scripts (if you were able to
>   reconstruct the sigs, 

Re: [bitcoin-dev] BIP sighash_noinput

2018-05-01 Thread Russell O'Connor via bitcoin-dev
At the risk of bikeshedding, shouldn't NOINPUT also zero out the
hashSequence so that its behaviour is consistent with ANYONECANPAY?

On Mon, Apr 30, 2018 at 12:29 PM, Christian Decker via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi all,
>
> I'd like to pick up the discussion from a few months ago, and propose a new
> sighash flag, `SIGHASH_NOINPUT`, that removes the commitment to the
> previous
> output. This was previously mentioned on the list by Joseph Poon [1], but
> was
> never formally proposed, so I wrote a proposal [2].
>
> We have long known that `SIGHASH_NOINPUT` would be a great fit for
> Lightning.
> They enable simple watch-towers, i.e., outsource the need to watch the
> blockchain for channel closures, and react appropriately if our
> counterparty
> misbehaves. In addition to this we just released the eltoo [3,4] paper
> which
> describes a simplified update mechanism that can be used in Lightning, and
> other
> off-chain contracts, with any number of participants.
>
> By not committing to the previous output being spent by the transaction,
> we can
> rebind an input to point to any outpoint with a matching output script and
> value. The binding therefore is no longer explicit through a reference, but
> through script compatibility, and the transaction ID reference in the
> input is a
> hint to validators. The sighash flag is meant to enable some off-chain
> use-cases
> and should not be used unless the tradeoffs are well-known. In particular
> we
> suggest using contract specific key-pairs, in order to avoid having any
> unwanted
> rebinding opportunities.
>
> The proposal is very minimalistic, and simple. However, there are a few
> things
> where we'd like to hear the input of the wider community with regards to
> the
> implementation details though. We had some discussions internally on
> whether to
> use a separate opcode or a sighash flag, some feeling that the sighash flag
> could lead to some confusion with existing wallets, but given that we have
> `SIGHASH_NONE`, and that existing wallets will not sign things with unknown
> flags, we decided to go the sighash way. Another thing is that we still
> commit
> to the amount of the outpoint being spent. The rationale behind this is
> that,
> while rebinding to outpoints with the same value maintains the value
> relationship between input and output, we will probably not want to bind to
> something with a different value and suddenly pay a gigantic fee.
>
> The deployment part of the proposal is left vague on purpose in order not
> to
> collide with any other proposals. It should be possible to introduce it by
> bumping the segwit script version and adding the new behavior.
>
> I hope the proposal is well received, and I'm looking forward to discussing
> variants and tradeoffs here. I think the applications we proposed so far
> are
> quite interesting, and I'm sure there are many more we can enable with this
> change.
>
> Cheers,
> Christian
>
> [1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
> 2016-February/012460.html
> [2] https://github.com/cdecker/bips/blob/noinput/bip-xyz.mediawiki
> [3] https://blockstream.com/2018/04/30/eltoo-next-lightning.html
> [4] https://blockstream.com/eltoo.pdf
> ___
> 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] Revisiting BIP 125 RBF policy.

2018-03-08 Thread Russell O'Connor via bitcoin-dev
On Thu, Mar 8, 2018 at 1:34 PM, Peter Todd  wrote:

> On Thu, Mar 08, 2018 at 10:39:46AM -0500, Russell O'Connor wrote:
> > On Thu, Mar 1, 2018 at 10:11 AM, Peter Todd  wrote:
> > > I mean, I think in general solving this problem is probably not
> possible.
> > > Basically, the fundamental problem is someone else has consumed network
> > > bandwidth that should be paid for with fees. What you're trying to do
> is
> > > replace a transaction without paying those fees, which is identical to
> > > what an
> > > attacker is trying to do, and thus any such scheme will be as
> vulnerable to
> > > attack as not having that protection in the first place.
> > >
> > > ...which does give you an out: maybe the attack isn't important enough
> to
> > > matter. :)
> > >
> >
> > Thanks, that makes sense.
> >
> > I still think it is worthwhile pursuing this proposed change in RBF
> policy
> > as it would seem that the current policy is problematic in practice today
> > where participants are just performing normal transactions and are not
> > trying to attack each other.
>
> But that's not a good argument: whether or not normal users are trying to
> attack each other has nothing to do with whether or not you're opening up
> an
> attack by relaxing anti-DoS protections.
>

I'm not suggesting removing the anti-DoS protections.  I'm suggesting that
replaced transaction require a fee increase of at least the min-fee-rate
times the size of all the transactions being ejected (in addition to the
other proposed requirements).


> Equally, how often are normal users who aren't attacking each other
> creating
> issues anyway? You can always have your wallet code just skip use of RBF
>
replacements in the event that someone does spend an unconfirmed output that
> you sent them; how often does this actually happen in practice?


Just ask rhavar.  It happens regularly.

Not many wallets let you spend unconfirmed outputs that you didn't create.
>

The problem is with institutional wallets sweeping incoming payments.  It
seems that in practice they are happy to sweep unconfirmed outputs.

Setting all of the above aside for a moment.  We need to understand that
rational miners are going to prefer to transactions with higher package fee
rates regardless of whatever your personal preferred RBF policy is.  If we
do not bring the RBF policy to alignment with what is economically
rational, then miners are going to change their own policies anyways,
probably all in slightly different ways.  It behooves everyone to develop a
reasonable standard RBF policy, that is still robust against possible DoS
vectors, and aligns with miner incentives, so that all participants know
what behaviour they can reasonably expect.  It is simply a bonus that this
change in RBF policy also partially mitigates the problem of pinned
transactions.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Revisiting BIP 125 RBF policy.

2018-03-08 Thread Russell O'Connor via bitcoin-dev
On Thu, Mar 1, 2018 at 10:11 AM, Peter Todd  wrote:

> On Tue, Feb 27, 2018 at 11:25:59AM -0500, Russell O'Connor wrote:
> > When you say that you don't think it is possible to solve, do you mean
> that
> > there is a specific problem with this proposal of replacing transactions
> > when offered a new transaction whose fee rate exceeds the package fee
> rate
> > of the original transaction (and ensuring that the fee increase covers
> the
> > size of the transactions being ejected)?  Is your concern only about the
> > ability to computing and track the package fee rate for transactions
> within
> > the mempool or is there some other issue you foresee?
>
> I mean, I think in general solving this problem is probably not possible.
> Basically, the fundamental problem is someone else has consumed network
> bandwidth that should be paid for with fees. What you're trying to do is
> replace a transaction without paying those fees, which is identical to
> what an
> attacker is trying to do, and thus any such scheme will be as vulnerable to
> attack as not having that protection in the first place.
>
> ...which does give you an out: maybe the attack isn't important enough to
> matter. :)
>

Thanks, that makes sense.

I still think it is worthwhile pursuing this proposed change in RBF policy
as it would seem that the current policy is problematic in practice today
where participants are just performing normal transactions and are not
trying to attack each other.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Revisiting BIP 125 RBF policy.

2018-02-27 Thread Russell O'Connor via bitcoin-dev
On Mon, Feb 12, 2018 at 6:42 PM, Peter Todd  wrote:

>
> Ah ok, I misunderstood and didn't realise you were talking about the case
> where
> Alice re-spends her unconfirmed payment. Unfortunately I don't think that
> case
> is possible to solve without putting some kind of restriction on spending
> unconfirmed outputs; with a restriction it's fairly simple to solve.


When you say that you don't think it is possible to solve, do you mean that
there is a specific problem with this proposal of replacing transactions
when offered a new transaction whose fee rate exceeds the package fee rate
of the original transaction (and ensuring that the fee increase covers the
size of the transactions being ejected)?  Is your concern only about the
ability to computing and track the package fee rate for transactions within
the mempool or is there some other issue you foresee?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Revisiting BIP 125 RBF policy.

2018-02-14 Thread Russell O'Connor via bitcoin-dev
On Mon, Feb 12, 2018 at 6:42 PM, Peter Todd  wrote:

> On Mon, Feb 12, 2018 at 06:19:40PM -0500, Russell O'Connor wrote:
> > Surely CPFP is already computing the package-fee rates of mempool
> > transactions.  That is the value we need to compute.
>
> True, maybe we can just reuse the CPFP calculation now. That said, AFAIK
> that's
> only done in the miner code, not the mempool, so that may not be trivial to
> actually do.
>

Do you (or anyone else) know if the package fee rate is considered when
ejecting transactions from the bottom of the mempool when the mempool gets
too large?
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


  1   2   >