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

[Anthony Towns via bitcoin-dev]

On Thu, Dec 05, 2019 at 03:24:46PM -0500, Russell O'Connor wrote:

Thanks for the careful write up! That matches what I was thinking.

> This analysis suggests that we should amend CODESEPARATORs behaviour to update
> an accumulator (presumably a running hash value), so that all executed
> CODESEPARATOR positions end up covered by the signature.

On IRC, gmaxwell suggests "OP_BREADCRUMB" as a name for (something like)
this functionality.

(I think it's a barely plausible stretch to use the name "CODESEPARATOR"
for marking a position in the script -- that separates what was before
and after, at least; anything more general seems like it warrants a
better name though)

> That would provide a
> solution to the above problem for those cases where taproot's MAST cannot be
> used.  I'm not sure if it is better to propose such an amendment to
> CODESEPARATOR's behaviour now, or to propose to soft-fork in such optional
> behaviour at a later time.
> However, what I said above was even too simplified.  

FWIW, I think it's too soon to propose this because (a) it's not clear
there's a practical need for it, (b) it's not clear the functionality is
quite right (opcode vs more automatic sighash flag?), and (c) as you say,
it's not clear it's powerful enough.

> In general, a policy of the form.
>     (Exists w[1]. C[1](w[1]) && PK[1,1](w[1]) && ... && PK[1,m[1]](w[1]) || 
> ...
> || (Exists w[n]. C[n](w[n]) && PK[n,1](w[n]) && ... && PK[n,m[n]](w[n]))
> where each term could possibly be parameterized by some witness value (though
> at the moment there isn't enough functionality in Script to parameterize the
> pubkeys in any reasonably way and it maybe isn't even possible to parameterise
> the conditions in any reasonable way).  In general, you might want your
> signature to cover (some function of) this witness value.  This suggests that
> we would actually want a CODESEPARATOR variant that pushes a stack item into
> the accumulator that gets covered by the signature rather than pushing the
> CODESEPARATOR position.  Though at this point the name CODESEPARATOR is
> probably not suitable, even if it subsumes the functionality.

> Again, I'm not
> sure if it is better to propose such a replacement for CODESEPARATOR's
> behaviour now, or to propose to soft-fork in such optional behaviour at a 
> later
> time.

Last bit first, it seems pretty clear to me that this is too novel an
idea to propose it immediately -- we should explore the problem space
more first to see what's the best way of doing it before coding it into
consensus. And (guessing) I think the tapscript upgrade methods should
be fine for handling this later.

I think the annex is also not general enough for what you're thinking
here, in that it wouldn't allow for one signature to constrain the witness
data more than some other signature -- so you'd need to determine all
the constraints for all signatures to finish filling out the annex,
and could only then start signing.

I think you could conceivably do any/all of:

 * commit to a hash of all the witness data that hasn't been popped off
   the stack ("suffix" commitment -- the data will be used by later script
   opcodes)
 * commit to a hash of all the witness data that has been popped off the
   stack ("prefix" commitment -- this is the data that's been used by
   earlier script opcodes)
 * commit to the hash of the current stack

That would be expensive, but still doable as O(1) per opcode / stack
element. I think any other masking would mean you'd have potentially
O(size of witness data) or O(size of stack) runtime per signature which
I think would be unacceptable...

I guess a general implementation to at least think about the possibilities
might be an "OP_DATACOMMIT" opcode that pops an element from the stack,
does hash_"DataCommit"(element), and then any later signatures commit
to that value (maybe with OP_0 OP_DATACOMMIT allowing you to get back to
the default state). You'd either need to write your script carefully to
commit to witness data you're using elsewhere, or have some other new
opcodes to do that more conveniently...

CODESEP at position "x" in the script is equivalent to " DATACOMMIT"
here, I think. "BREADCRUMB .. BREADCRUMB" could be something like:

   OP_0 TOALT [at start of script]
   ..
   FROMALT x CAT SHA256 DUP TOALT DATACOMMIT   
   ..
   FROMALT y CAT SHA256 DUP TOALT DATACOMMIT   

if the altstack was otherwise unused, I guess; so the accumulator
behaviour probably warrants something better.

It also more or less gives you CHECKSIGFROMSTACK behaviour by doing
"SWAP OP_DATACOMMIT OP_CHECKSIG" and a SIGHASH_NONE|ANYPREVOUTANYSCRIPT
signature.

But that seems like a plausible generalisation to think about?

Cheers,
aj

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

Re: [bitcoin-dev] easypaysy - A layer-two protocol to send payments without addresses

[ZmnSCPxj via bitcoin-dev]

Good morning Jose,


> > It also means that to register an account, you need to either own some 
> > Bitcoins, or rent some Bitcoins to serve as signalling (and then 
> > potentially have to change your account identifier later when the lease 
> > expires).
>
> I don’t understand what you mean by ‘renting’ Bitcoins.
> Once you commit the account transaction, the account ID never changes.
> (Also, you don’t need to own Bitcoins if you use a Master Easypaysy Account. 
> See my comments later on).

If you have 0 Bitcoins, you need to have *some* Bitcoins from somewhere else 
(perhaps a service provider) in order to back the initial funding transaction 
output.
If you create Master Easypaysy account by paying fiat to some service provider 
that then uses its Bitcoins to fund your Easypaysy account, but requires some 
sort of shared control over the money in it, I simply call this "renting" the 
Bitcoin, as presumably the service provider would want to get its coins back 
from you.

If you are referring to the use of a service provider, then the service 
provider at least partially controls your account and if it ceases to exist or 
refuses to continue doing business with you, you need to transfer your account 
identifier somehow (i.e. end of lease).

>
> > Finally, use of the blockchain layer is costly; given that payees must be 
> > online at any time payers wish to pay, it may do better to just use 
> > Lightning instead,
>
> That is not the case.
> When using non-interactive payments, the payee doesn’t need to be online at 
> all.
> Even for interactive payments, it depends on the protocol you use.
>
> For Bitmessage, or email, or even MQTT you don’t need to be online 
> simultaneously. (The interactive protocol(s) is still open, however, those 
> are just some hypothetical examples):

You could indicate use of some kind of pay-to-contract, then have the payer 
send the contract text to the payee so that the payee can claim the funds later.

> Anyway, when using interactive payments, the payee has the option to specify 
> an LN invoice and/or a bitcoin address.
>
> > which has the same requirement, but moves payments to a separate layer as 
> > well, and requires only a single onchain transaction to construct a channel 
> > (easypaysy seems to require at least 2, one to anchor the account pubkeys, 
> > the other to give the basic "activation" information for the account).
>
> Easypaysy accounts don’t need 2 TXs. They need funding plus a TX for the 
> account information itself.
> So, you need an UTXO -to fund the account- and a TX.

Yes, that is why I count it as 2 transactions: one transaction to host the 
funding UTXO that is referred to in the account identifier, and the other 
transaction is what broadcasts the account information (in particular, the 
funding UTXO is a P2SH and the transaction that spends it is the one that 
reveals the 2 pubkeys you require).

In contrast, Lightning Network requires only the funding UTXO (which requires 
that short channel IDs include the transaction output index, as a single 
funding transaction can fund multiple Lightning Network channels).

> But the UTXO can be one of many in the same transaction.
> So, you could fund multiple accounts with a single TX.

So can Lightning Network channels: multiple channels can be funded by a single 
funding transactions (C-Lightning supports this, but not as a single command 
yet, it requires some low-level fiddling).

> > Also, one of the contact-information protocols supported should probably be 
> > Tor hidden services, instead of `https`. Tor hidden services have better 
> > useability (no need for port forwarding or registering DNS from some 
> > centralized service), with privacy as a bonus.
>
> Easypaysy is protocol agnostic (for now). So, Tor is definitely a possibility.

I suggest being Tor-centric instead.

>
> > Further it seems insufficient to only encode block and tx index. I think it 
> > should also encode output index, to also allow a single transaction to 
> > anchor multiple accounts. Also consider using the Lightning encoding of 
> > identifying an output: 543847x636x2
>
> There is really no need to specify an additional output.
> If I am right, you can’t have more than one OP_RETURN per transaction.

This does not mesh with your earlier claim:

> But the UTXO can be one of many in the same transaction.

My understanding is that the account identifier refers to the funding TXO (and 
funding transactions do not have an `OP_RETURN`, so I fail to see the relevance 
of that restriction).
If the funding transaction can have many UTXOs that are individually funding 
TXOs of multiple Easypaysy accounts, then you need to refer to *which* TXO of 
that funding transaction is what you are using.

>
> On the other hand, as you can see in the white paper “4.2 Master accounts”, 
> these type of accounts allow for up to 2048 accounts per transaction.
>
> The format of the ID in this case is: btc@master_idx.slave_id/checksum
>

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

[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 

[bitcoin-dev] easypaysy - A layer-two protocol to send payments without addresses

[Jose Femenías Cañuelo via bitcoin-dev]

Hi ZmnSCPxj

first of all, excuse me for my delayed answer. 

I think I posted to the wrong address the first time (I’m mainly a lurker in 
the list, so I make gotchas like that…)

Let me address your points.

> It also means that to register an account, you need to either own some 
> Bitcoins, or rent some Bitcoins to serve as signalling (and then potentially 
> have to change your account identifier later when the lease expires). 

I don’t understand what you mean by ‘renting’ Bitcoins. 
Once you commit the account transaction, the account ID never changes.
(Also, you don’t need to own Bitcoins if you use a Master Easypaysy Account. 
See my comments later on).



> Finally, use of the blockchain layer is costly; given that payees must be 
> online at any time payers wish to pay, it may do better to just use Lightning 
> instead,

That is not the case. 
When using non-interactive payments, the payee doesn’t need to be online at all.
Even for interactive payments, it depends on the protocol you use.

For Bitmessage, or email, or even MQTT you don’t need to be online 
simultaneously. (The interactive protocol(s) is still open, however, those are 
just some hypothetical examples):

Anyway, when using interactive payments, the payee has the option to specify an 
LN invoice and/or a bitcoin address.



> which has the same requirement, but moves payments to a separate layer as 
> well, and requires only a single onchain transaction to construct a channel 
> (easypaysy seems to require at least 2, one to anchor the account pubkeys, 
> the other to give the basic "activation" information for the account). 

Easypaysy accounts don’t need 2 TXs. They need funding plus a TX for the 
account information itself.
So, you need an UTXO -to fund the account- and a TX. 
But the UTXO can be one of many in the same transaction. 
So, you could fund multiple accounts with a single TX.


> Also, one of the contact-information protocols supported should probably be 
> Tor hidden services, instead of `https`. Tor hidden services have better 
> useability (no need for port forwarding or registering DNS from some 
> centralized service), with privacy as a bonus. 
Easypaysy is protocol agnostic (for now). So, Tor is definitely a possibility.


> Further it seems insufficient to only encode block and tx index. I think it 
> should also encode output index, to also allow a single transaction to anchor 
> multiple accounts. Also consider using the Lightning encoding of identifying 
> an output: 543847x636x2 
There is really no need to specify an additional output.
If I am right, you can’t have more than one OP_RETURN per transaction.

On the other hand, as you can see in the white paper “4.2 Master accounts”, 
these type of accounts allow for up to 2048 accounts per transaction.

The format of the ID in this case is: btc@master_idx.slave_id/checksum

The master_idx is an ordinal pointer (not positional) to the Master TX, while 
the slave_id points to one of the 2048 transactions within the account (whose 
information is stored elsewhere, protected by a Merkle root committed in the 
Master Tx)

There is a little bit more to it that seems appropriate to discuss here, please 
have a look at page 25 of the white paper.

Thanks for your input.


Best regards,

José Femenías
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] easypaysy - A layer-two protocol to send payments without addresses

[Jose Femenías Cañuelo via bitcoin-dev]

> Hello José,
> 
> Just a quick question, this is fully decentralized?
> Greetings,
> 
> Tim Blokdijk


Tim,

it is fully decentralized indeed. 
Every user is in charge of creating and maintaining his own account.

Regards,

José Femenías___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev