Re: [bitcoin-dev] Blind Statechains

2020-06-12 Thread Ruben Somsen via bitcoin-dev
Hi Tom,

Blind signatures are certainly a nice feature, great to see that you're
considering it.

>So each new owner of a UTXO must receive, store and verify the full
sequence of previous owner backup transactions to make sure that no
previous owner has asked the SE to sign a transaction that could be used to
steal the UTXO. This may end up making wallets more bloated and clunky,
given that ownership of a UTXO could change hands thousands of times
off-chain.

Users would have to validate the history of the chain regardless, even if
it wasn't blind, to verify whether the statechain entity hasn't been
cheating, so the main difference would be in unblinding the data.

One of my original ideas was to use the transitory key to derive the
secrets that blind the signatures (basically like an HD wallet). The
statechain entity would then store and serve blind signatures, and any new
owner would download and unblind/verify them using the transitory key (no
extensive peer-to-peer transfer needed). It's possible to make the
off-chain transactions themselves deterministic, so they can just be
generated by the client without any additional data transfer. The only
potentially unique thing in a transaction is the refund address, but this
can be the same key as the ownership key on the statechain, tweaked with
the transitory key via Diffie-Hellman (to ensure it's not linkable if it
goes on-chain).

The general downside of this method is that all transactions are exposed to
anyone who learns the transitory key -- not just for the current
transactions (which can always be leaked no matter what you do), but also
all future transactions in that particular statechain. However, I should
note there doesn't actually seem to be much to learn, because the history
of each statechain is actually quite uninformative. The money just goes
from one pseudonymous owner to the next.

Of course you now have scheme that changes the transitory key with each
step, so I instead suggest you introduce a secondary "blinding key" to
achieve what I described.

I'm not sure whether this can also apply to 2P-ECDSA, but with Schnorr the
statechain entity wouldn't even learn the address for the funding
transaction, so it wouldn't be able to tell which UTXO it controls by
watching the blockchain. Ideally, this functionality would be preserved to
ensure the statechain entity can't be aware of the funds it's holding.

Another thing to note is that you won't know when a statechain has been
pegged out, so pruning will be impossible. You may wish to consider some
kind of liveness rule where one statechain transaction needs to be made per
year. If they miss the deadline, they're just forced on-chain, which is not
terrible, in any case.

Hope this helps!

Cheers,
Ruben



On Fri, Jun 12, 2020 at 9:23 PM Tom Trevethan via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello,
>
> A statechain implementation and service co-signs 'backup' (off-chain)
> transactions to transfer ownership of a UTXO from one owner to the next. A
> suggested here
> https://medium.com/@RubenSomsen/statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39
> , this service (the statechain entity or SE) can be engineered to be
> 'blind' to the transactions it is signing (i.e. it does not and cannot know
> the details of the transactions it is signing) which can give significant
> privacy benefits. It would enable more private off-chain coin-swaps, and
> make collusion more difficult.
>
> The only downside of a blind SE is that it can no longer enforce the rules
> governing the sequence of backup transactions it co-signs as owners can ask
> the SE to cosign any transaction. So each new owner of a UTXO must receive,
> store and verify the full sequence of previous owner backup transactions to
> make sure that no previous owner has asked the SE to sign a transaction
> that could be used to steal the UTXO. This may end up making wallets more
> bloated and clunky, given that ownership of a UTXO could change hands
> thousands of times off-chain.
>
> In the case of a multisig, and Schnorr signatures, existing blind Schnorr
> protocols could be used to implement a blind SE, however we are opting to
> use two-party ECDSA (because there is no Schnorr yet, and in any case ECDSA
> will give a much bigger anonymity set). There is no current 2P ECDSA
> protocol that enables one of the two signers to be completely blinded, but
> it seems that this would require only minor modifications to an existing 2P
> ECDSA scheme (outlined here
> https://github.com/commerceblock/mercury/blob/master/doc/blind_2p_ecdsa.md
> based on Lindell 2017 https://eprint.iacr.org/2017/552 ).
>
> Any comments on any of this gratefully received.
>
> Tom
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

2020-06-01 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>If Alice is paying to a non-SAS aware payee

Yeah, I agree that this use case is not possible without a third
transaction (preferably from the timelocked side, in the case of SAS). My
point was merely that you can swap and simultaneously merge some of your
outputs into the post-swap non-timelocked output, though perhaps that is
not very useful.

Cheers,
Ruben



On Mon, Jun 1, 2020 at 4:34 AM ZmnSCPxj  wrote:

> Good morning Ruben,
>
>
> >
> > That assumes there will be a second transaction. With SAS I believe we
> can avoid that, and make it look like this:
> >
> >  +---+
> > Alice ---|   |--- Bob
> > Alice ---|   |
> >   Bob ---|   |
> >  +---+
>
> If Alice is paying to a non-SAS aware payee that just provides an onchain
> address (i.e. all current payees today), then the 2-of-2 output it gets
> from the swap (both of whose keys it learns at the end of the swap) is
> **not** the payee onchain address.
> And it cannot just hand over both private keys, because the payee will
> still want unambiguous ownership of the entire UTXO.
> So it needs a second transaction anyway.
> (with Schnorr then Alice and payee Carol can act as a single entity/taker
> to Bob, a la Lightning Nodelets using Composable MuSig, but that is a
> pretty big increase in protocol complexity)
>
> If Alice does not want to store the remote-generated privkey as well, and
> use only an HD key, then it also has to make the second transaction.
> Alice might want to provide the same assurances as current wallets that
> memorizing a 12-word or so mnemonic is sufficient backup for all the funds
> (other than funds currently being swapped), and so would not want to leave
> any funds in a 2-of-2.
>
> If Bob is operating as a maker, then it also cannot directly use the
> 2-of-2 output it gets from the swap, and has to make a new 2-of-2 output,
> for the *next* taker that arrives to request its services.
>
> So there is always going to be a second transaction in a SwapMarket
> system, I think.
>
>
> What SAS / private key turnover gets us is that there is not a *third*
> transaction to move from a 1-of-1 to the next address that makers and
> takers will be moving anyway, and that the protocol does not have to add
> communication provisions for special things like adding maker inputs or
> specifying all destination addresses for the second stage and so on,
> because those can be done unilaterally once the private key is turned over.
>
>
> > >A thing I have been trying to work out is whether SAS can be done with
> more than one participant, like in S6
> >
> > S6 requires timelocks for each output in order to function, so I doubt
> it can be made to work with SAS.
>
> Hmmm right right.
>
> Naively it seems both chaining SAS/private key turnover to multiple
> makers, and a multi-maker S6 augmented with private key turnover, would
> result in the same number of transactions onchain, but I probably have to
> go draw some diagrams or something first.
>
> But S6 has the mild advantage that all the funding transactions paying to
> 2-of-2s *can* appear on the same block, whereas chaining swaps will have a
> particular order of when the transactions appear onchain, which might be
> used to derive the order of swaps.
> On the other hand, funds claiming in S6 is also ordered in time, so
> someone paying attention to the mempool could guess as well the order of
> swaps.
>
>
> Regards,
> ZmnSCPxj
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

2020-05-31 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>Just to be clear, you mean we can use the MuSig key-combination protocol
for the non-timelocked SAS output, but (of course) not the signing protocol
which is inherently Schnorr. Then knowledge of both of the original private
keys is enough to derive the single combined private key.

That's correct.

>basically private key handover gets us PayJoin for free

That assumes there will be a second transaction. With SAS I believe we can
avoid that, and make it look like this:

 +---+
Alice ---|   |--- Bob
Alice ---|   |
  Bob ---|   |
 +---+

This is basically what I was trying to explain in my previous email: "I
believe PayJoin can also be applied to the non-timelocked side. This does
require adding a transaction that undoes the PayJoin in case the swap gets
aborted, which means MuSig can't be used. Everything else stays the same:
only one tx if successful, and no timelock (= instant settlement)"

I don't have a strong opinion on whether it is actually useful to combine
CoinSwap with PayJoin.

>A thing I have been trying to work out is whether SAS can be done with
more than one participant, like in S6

S6 requires timelocks for each output in order to function, so I doubt it
can be made to work with SAS.

I've also tried applying SAS to partially blind swaps and ran into
likability issues, though it's less clear to me whether there is some
fundamental reason why it couldn't work there.

Cheers,
Ruben

On Sun, May 31, 2020 at 4:31 AM ZmnSCPxj  wrote:

> Good morning Ruben and Chris,
>
> > >For a much greater anonymity set we can use 2-party ECDSA to create
> 2-of-2 multisignature addresses that look the same as regular
> single-signature addresses
> >
> > This may perhaps be counter-intuitive, but SAS doesn't actually require
> multisig for one of the two outputs, so a single key will suffice. ECDSA is
> a signing algorithm that doesn't support single key multisig (at least not
> without 2p-ECDSA), but notice how for the non-timelocked SAS output we
> never actually have to sign anything together with the other party. We swap
> one of the two keys, and the final owner will create a signature completely
> on their own. No multisig required, which means we can simply use MuSig,
> even today without Schnorr.
>
> Just to be clear, you mean we can use the MuSig key-combination protocol
> for the non-timelocked SAS output, but (of course) not the signing protocol
> which is inherently Schnorr.
>
> Then knowledge of both of the original private keys is enough to derive
> the single combined private key.
>
> > Of course the other output will still have to be a 2-of-2, for which you
> rightly note 2p-ECDSA could be considered. It may also be interesting to
> combine a swap with the opening of a Lightning channel. E.g. Alice and Bob
> want to open a channel with 1 BTC each, but Alice funds it in her entirety
> with 2 BTC, and Bob gives 1 BTC to Alice in a swap. This makes it difficult
> to tell Bob entered the Lightning Network, especially if the channel is
> opened in a state that isn't perfectly balanced. And Alice will gain an
> uncorrelated single key output.
>
> Dual-funding could be done by a single-funding Lightning open followed by
> an onchain-to-offchain swap.
> Though the onchain swap would have to be done, at least currently, with
> hashes.
>
> > >=== PayJoin with CoinSwap ===
> >
> > While it's probably clear how to do it on the timelocked side of SAS, I
> believe PayJoin can also be applied to the non-timelocked side. This does
> require adding a transaction that undoes the PayJoin in case the swap gets
> aborted, which means MuSig can't be used. Everything else stays the same:
> only one tx if successful, and no timelock (= instant settlement). I can
> explain it in detail, if it happens to catch your interest.
>
> I am not in fact convinced that PayJoin-with-CoinSwap adds *that* much
> privacy.
>
> These transactions:
>
>  +---+  +---+
> Alice ---|   |--|   |--- Bob
> Alice ---|   |  |   |
>   Bob ---|   |  +---+
>  +---+
>
> Are not really much different in coin ownership analysis from these:
>
>  +---++---+
> Alice ---|   ||   |--- Bob
> Alice ---|   | +--|   |
>  +---+ |  +---+
>   Bob -+
>
> The latter is possible due to private key handover, the intermediate
> output becomes owned solely by Bob and Bob can add many more inputs to that
> second transaction unilaterally for even greater confusion to chain
> analysis, basically private key handover gets us PayJoin for free.
> It also removes the need for Bob to reveal additional UTXOs to Alice
> during the swap protocol; yes PoDLE mitigates the privacy probing attack
> that Alice can mount on Bob, but it is helpful to remember this is "only" a
> mitigation.
>
> Now of course things are different if Alice is paying some exact amount to
> Carol, and Alice wants to dissociate her funds from the payment.
> The difference 

Re: [bitcoin-dev] Design for a CoinSwap implementation for massively improving Bitcoin privacy and fungibility

2020-05-30 Thread Ruben Somsen via bitcoin-dev
Hey Chris,

Excellent write-up. I learned a few new things while reading this
(particularly how to overcome the heuristics for address reuse and address
types), so thank you for that.

I have a few thoughts about how what you wrote relates to Succinct Atomic
Swaps (SAS)[0]. Perhaps it's useful.

>For a much greater anonymity set we can use 2-party ECDSA to create 2-of-2
multisignature addresses that look the same as regular single-signature
addresses

This may perhaps be counter-intuitive, but SAS doesn't actually require
multisig for one of the two outputs, so a single key will suffice. ECDSA is
a signing algorithm that doesn't support single key multisig (at least not
without 2p-ECDSA), but notice how for the non-timelocked SAS output we
never actually have to sign anything together with the other party. We swap
one of the two keys, and the final owner will create a signature completely
on their own. No multisig required, which means we can simply use MuSig,
even today without Schnorr.

Of course the other output will still have to be a 2-of-2, for which you
rightly note 2p-ECDSA could be considered. It may also be interesting to
combine a swap with the opening of a Lightning channel. E.g. Alice and Bob
want to open a channel with 1 BTC each, but Alice funds it in her entirety
with 2 BTC, and Bob gives 1 BTC to Alice in a swap. This makes it difficult
to tell Bob entered the Lightning Network, especially if the channel is
opened in a state that isn't perfectly balanced. And Alice will gain an
uncorrelated single key output.

As a side note, we could use the same MuSig observation on 2-of-2 outputs
that need multisig by turning the script into (A & B) OR MuSig(A,B), which
would shave off quite a few bytes by allowing single sig spending once the
private key is handed over, but this would also make the output stick out
like a sore thumb... Only useful if privacy is not a concern.

>=== Multi-transaction CoinSwaps to avoid amount correlation ===

This can apply cleanly to SAS, and can even be done without passing on any
extra secrets by generating a sharedSecret (Diffie-Hellman key exchange).

Non-timelocked:
CoinSwap AddressB = aliceSecret + bobSecret
CoinSwap AddressC = aliceSecret + bobSecret + hash(sharedSecret,0)*G
CoinSwap AddressD  = aliceSecret + bobSecret + hash(sharedSecret,1)*G

The above is MuSig compatible (single key outputs), there are no timelocks
to worry about, and the addresses cannot be linked on-chain.

>they would still need to watch the chain and respond in case a
hash-time-locked contract transaction is broadcasted

Small detail, but it should be noted that this would require the atomic
swap to be set up in a specific way with relative timelocks.

>=== PayJoin with CoinSwap ===

While it's probably clear how to do it on the timelocked side of SAS, I
believe PayJoin can also be applied to the non-timelocked side. This does
require adding a transaction that undoes the PayJoin in case the swap gets
aborted, which means MuSig can't be used. Everything else stays the same:
only one tx if successful, and no timelock (= instant settlement). I can
explain it in detail, if it happens to catch your interest.

Cheers,
Ruben


[0]  Succinct Atomic Swaps (SAS)
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017846.html

On Mon, May 25, 2020 at 3:21 PM Chris Belcher via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> === Abstract ===
>
> Imagine a future where a user Alice has bitcoins and wants to send them
> with maximal privacy, so she creates a special kind of transaction. For
> anyone looking at the blockchain her transaction appears completely
> normal with her coins seemingly going from address A to address B. But
> in reality her coins end up in address Z which is entirely unconnected
> to either A or B.
>
> Now imagine another user, Carol, who isn't too bothered by privacy and
> sends her bitcoin using a regular wallet which exists today. But because
> Carol's transaction looks exactly the same as Alice's, anybody analyzing
> the blockchain must now deal with the possibility that Carol's
> transaction actually sent her coins to a totally unconnected address. So
> Carol's privacy is improved even though she didn't change her behaviour,
> and perhaps had never even heard of this software.
>
> In a world where advertisers, social media and other companies want to
> collect all of Alice's and Carol's data, such privacy improvement would
> be incredibly valuable. And also the doubt added to every transaction
> would greatly boost the fungibility of bitcoin and so make it a better
> form of money.
>
> This undetectable privacy can be developed today by implementing
> CoinSwap, although by itself that isn't enough. There must be many
> building blocks which together make a good system. The software could be
> standalone as a kind of bitcoin mixing app, but it could also be a
> library that existing wallets can implement allowing their users to send
> Bitcoin 

Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-15 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>The proper response here is that Bob should broadcast success tx before
the refund tx #1 becomes valid.

That's right. And even if Bob neglects to do that, it still won't cause
chaos for Alice as long as she chooses the path for refund tx #2.

>at least part of the fund must be lost in fees and Bob can still suffer a
small loss

Yes, after protocol completion Alice can broadcast one more transaction
that is paid for by Bob, and Bob would have to respond with another
transaction of his own. As you said, bring-your-own-fees would be better
here (also see FAQ question "Can't Alice just publish the revoke_tx after
protocol completion?").

>the server should take Alice position and the client should take Bob
position [...] a client will want to make multiple CoinSwaps in sequence

I think this can be summarized as: whoever is planning to spend their UTXO
first should be Bob.

In your protocol it might make sense for the server and client to swap
roles depending on what the client plans to do. If they plan to swap again
soon, they can be Bob, if they don't, they're Alice.

But there's also another consideration: whoever is less likely to abort the
protocol should be Bob.

Clients can be unreliable. If clients are Bob, they can waste Alice's
resources by initiating the protocol and aborting (which imo is more severe
than the risk of the revoke tx getting published). Whereas if the client is
Alice, she'd be first to commit resources before the server commits
anything.

>ensure the txo is spent before refund tx #1 becoms valid

Yes, this is important. Luckily, pretty much all the options we discussed
could be applied here, including sighash_single + anyonecanpay. In your
specific example this seems preferable to adding a change output and making
multiple transactions with different RBF amounts, especially since this
only concerns a situation where the protocol stalls at a specific step
(after the success tx).

And I agree with your general assessment that three transactions are
required in order to pay a third party. This could be done from either side
of the swap, but of course it makes more sense to pay from the timelock
side and get rid of the online requirement.

Cheers,
Ruben

On Fri, May 15, 2020 at 6:39 AM ZmnSCPxj  wrote:

> Good morning Ruben,
>
> > Hi ZmnSCPxj,
> >
> > >on completion of the protocol, if Bob lets the refund tx#1 become valid
> (i.e. does not spend the BTC txo) then Alice can broadcast it, putting both
> their funds into chaos
> >
> > You forget, refund tx #1 has a script (which btw won't be visible with
> taproot): "Alice & Bob OR Alice in +1 day" (relative) so if Alice
> broadcasts it after protocol completion, she is just giving Bob the key to
> her LTC (note: if she's wise she'd move the LTC beforehand), but Bob
> doesn't lose the BTC because he has both keys and can just react before the
> relative timelock expires. No chaos.
>
> Ah, that explains the existence of the Alice && Bob clause in that output
> then.
>
> The attack is now as follows:
>
> * Alice completes the protocol up to handing over `sigSuccessAlice` to Bob.
> * Bob returns the `secretBob`.
> * Alice stalls the protocol and never sends the `Alice` privkey, and waits
> for 1 day, then sneaks the refund tx #1 and spends the LTC via direct miner
> collusion.
>
> The proper response here is that Bob should broadcast success tx before
> the refund tx #1 becomes valid.
> (Which I think is the point: chaos can only occur if you let backouts
> become valid, and it is the best policy for Bob to just spend the BTC txo
> well before the timeout.
> Even if the protocol is completed, without a bring-your-own-fees that lets
> you malleate the tx (i.e. CPFP hooks still require the transction itself to
> reduce the fund by at least the minimum feerate), at least part of the fund
> must be lost in fees and Bob can still suffer a small loss of funds.)
>
> --
>
> Tangentially, I now think in the case of client-server CoinSwap, the
> server should take Alice position and the client should take Bob position.
>
> Suppose a client wants to do some mixing of its own received coins.
> It should not depend on only one server, as the server might secretly be a
> surveillor (or hacked by a surveillor) and recording swaps.
> Thus, a client will want to make multiple CoinSwaps in sequence, to
> obscure its history.
>
> (Do note the objections under "Directionality" in
> https://zmnscpxj.github.io/bitcoin/multiswap.html though; a counter to
> this objections is that the analysis there is only applicable if the
> surveillor already identified the CoinSwap sequence, but hopefully the
> increased steganography of CoinSwaps means they are not identifiable
> anyway.)
>
> Since Bob really should spend its received coin before a timeout, it is
> best for Bob to be the client; it is likely that the client will need to
> swap "soon" again, meaning it has to redirect the funds to a new 2-of-2
> anyway.
>
> For the final swap, the client can then 

Re: [bitcoin-dev] TLA+ specification for Succint Atomic Swap

2020-05-14 Thread Ruben Somsen via bitcoin-dev
Hi Dmitry,

>But it should be noted that it is not enough that Bob publishes success_tx
before refund_tx_1 became valid. The success_tx needs to be confirmed
before refund_tx_1 became valid.

Agreed, my write-up would benefit from pointing this out more explicitly.

Cheers,
Ruben

On Thu, May 14, 2020 at 9:05 AM Dmitry Petukhov  wrote:

> В Thu, 14 May 2020 07:31:13 +0200
> Ruben Somsen  wrote:
>
> > Hi Dmitry,
> >
> > >While refund_tx_1 is in the mempool, Bob gives success_tx to the
> > >friendly miner
> >
> > I see, so you're talking about prior to protocol completion, right
> > after Alice sends Bob the success_tx. The reason this is not an issue
> > is because Alice and Bob both had to misbehave in order for this to
> > happen. Bob is misbehaving here because he should have published the
> > success_tx before refund_tx_1 became valid, and Alice is misbehaving
> > here because she should have sent the revoke_tx (which invalidates
> > the success_tx) followed by refund_tx_2 (revealing her secret only
> > AFTER Bob can no longer claim the BTC). In other words: yes, the
> > protocol can fail if Alice and Bob together work towards that goal. A
> > feature, not a bug. This won't happen if either of them doesn't want
> > it to. I imagine this is difficult to model.
>
> Right. But it should be noted that it is not enough that Bob publishes
> success_tx before refund_tx_1 became valid. The success_tx needs to be
> confirmed before refund_tx_1 became valid.
>
> Only Bob can spend success_tx so this is unlikely to be the practical
> problem, unless the original fee of success_tx is too small and Bob
> epically screws up CPFP-ing it.
>
> > >Bob will receive BTC, and the LTC can be locked forever, but Bob
> > >doesn't
> > care, he got his BTC.
> >
> > No, because diagram step 5 comes before step 6 -- Alice won't give
> > her key until she learns secretBob.
>
> I somehow missed it, and steps 5 and 6 in the diagram was not modelled
> at all (on the other hand, it made the model simpler and I had
> something working relatively quick). I now made the `signers_map` into
> variable that can be changed to give Bob the ability to sign for Alice.
>
> With that change, step 6 can be modelled, but this will add a bunch of
> new txs to the model (each Alice spend will have 'Bob unilateral
> override' case)
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] TLA+ specification for Succint Atomic Swap

2020-05-13 Thread Ruben Somsen via bitcoin-dev
Hi Dmitry,

>While refund_tx_1 is in the mempool, Bob gives success_tx to the friendly
miner

I see, so you're talking about prior to protocol completion, right after
Alice sends Bob the success_tx. The reason this is not an issue is because
Alice and Bob both had to misbehave in order for this to happen. Bob is
misbehaving here because he should have published the success_tx before
refund_tx_1 became valid, and Alice is misbehaving here because she should
have sent the revoke_tx (which invalidates the success_tx) followed by
refund_tx_2 (revealing her secret only AFTER Bob can no longer claim the
BTC). In other words: yes, the protocol can fail if Alice and Bob together
work towards that goal. A feature, not a bug. This won't happen if either
of them doesn't want it to. I imagine this is difficult to model.

>As I understand, this is a way to deny Alice to use refund_tx_1.

That is correct, and it also denies refund_tx_2 by making the revoke_tx
directly spendable by Bob.

>could Bob just spend the Alice output of the very first, "commitment"
transaction that locks BTC

Yes, he can. This is what makes it possible to complete the protocol in
merely two transactions.

>Bob will receive BTC, and the LTC can be locked forever, but Bob doesn't
care, he got his BTC.

No, because diagram step 5 comes before step 6 -- Alice won't give her key
until she learns secretBob.

I hope this clarifies it!

Cheers,
Ruben

On Thu, May 14, 2020 at 6:49 AM Dmitry Petukhov  wrote:

> В Wed, 13 May 2020 21:03:17 +0200
> Ruben Somsen  wrote:
>
> > Or perhaps you're referring to the issue ZmnSCPxj pointed out after
> > that, where refund transaction #1 and the success transaction could
> > both become valid at the same time. It would make sense for the test
> > to pick up on that, but I believe that is ultimately also not an
> > issue (see my last reply in the thread).
>
> This one.
>
> The issue as I see it: Bob can not broadcast success_tx and wait until
> Alice has broadcasted refund_tx_1. While refund_tx_1 is in the mempool,
> Bob gives success_tx to the friendly miner to have a chance to
> invalidate success_tx. Bob already learned secretAlice, so he grabs
> his LTC back. If the Bob-friendly miner has luck, success_tx is
> confirmed while refund_tx_1 is invalidated, and Bob now have both LTC
> and BTC, while Alice is out of her BTC.
>
> > >I did not understand what the destination of Alice cooperative
> > >spend
> > of refund_tx#1 will be
> >
> > This transaction can be spent by Alice & Bob right away or by Alice a
> > day later (in relative time, so the tx has to confirm first). The
> > Alice & Bob condition is there purely to ensure that Bob can spend
> > the money before Alice once he receives her key at the end of the
> > protocol.
>
> Ah, so this is possible because of the step 5 in the diagram: ``Alice
> gives Bob her key ("Alice")'' -- As I understand, this is a way to deny
> Alice to use refund_tx_1.
>
> Then if Alice gives her _key_ to Bob before Bob has to share secretBob
> via success_tx, could Bob just spend the Alice output of the
> very first, "commitment" transaction that locks BTC ? Bob will receive
> BTC, and the LTC can be locked forever, but Bob doesn't care, he got
> his BTC.
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] TLA+ specification for Succint Atomic Swap

2020-05-13 Thread Ruben Somsen via bitcoin-dev
Hi Dmitry,

Thanks for creating a specification for testing, I appreciate the interest!

>The checking of the model encoded in the specification can successfully
detect the violation of 'no mutual secret knowledge' invariant when one of
the participant can bypass mempool and give the transaction directly to the
miner (this problem was pointed out by ZmnSCPxj in the original SAS thread
[2])

I'm not sure if I follow. The issue ZmnSCPxj described about bypassing the
mempool was not a violation. It was merely a "nuisance" strategy that
causes Alice to have to abort in three transactions. Also note that I
subsequently pointed out in the thread that this strategy does not work,
because Alice is supposed to abort sooner than that if Bob still has not
locked up any funds.

Or perhaps you're referring to the issue ZmnSCPxj pointed out after that,
where refund transaction #1 and the success transaction could both become
valid at the same time. It would make sense for the test to pick up on
that, but I believe that is ultimately also not an issue (see my last reply
in the thread).

>I did not understand what the destination of Alice cooperative spend
of refund_tx#1 will be

This transaction can be spent by Alice & Bob right away or by Alice a day
later (in relative time, so the tx has to confirm first). The Alice & Bob
condition is there purely to ensure that Bob can spend the money before
Alice once he receives her key at the end of the protocol.

If it helps, you could model this transaction as two separate transactions
instead:
txA: 1 day absolute timelock to Alice & Bob (reveals secretAlice), which
can then be spent by
txB: +1 day relative timelock to Alice

This should be functionally equivalent. Also note that the protocol should
fully function if refund tx #1 did not exist at all. It merely serves to
save block space in certain refund scenarios.

>it would be great to have an established framework for modelling of the
behavior in Bitcoin-like blockchain networks. In particular, having a model
of mempool-related behavior would help to reason about difficult RBF/CPFP
issues

A laudable goal. Good luck with your efforts.

Cheers,
Ruben

On Wed, May 13, 2020 at 7:07 PM Dmitry Petukhov via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> The Succint Atomic Swap contract presented by Ruben Somsen recently has
> drawn much interest.
>
> I personally am interested in the smart contracts realizeable in the
> UTXO model, and also interested in applying formal methods to the
> design and implementation of such contracts.
>
> I think that having formal specifications for the contracts and to be
> able to machine-check the properties of these specifications is very
> valuable, as it can uncover the corner cases that might be difficult to
> uncover otherwise.
>
> The SAS contract is complex enough that it may benefit from formal
> specification and machine checking.
>
> I created a specification in TLA+ [1] specification language based on
> the explanation and the diagram given by Ruben.
>
> The checking of the model encoded in the specification can successfully
> detect the violation of 'no mutual secret knowledge' invariant when one
> of the participant can bypass mempool and give the transaction directly
> to the miner (this problem was pointed out by ZmnSCPxj in the original
> SAS thread [2])
>
> There's one transition that was unclear how to model, though: I did not
> understand what the destination of Alice cooperative spend of
> refund_tx#1 will be, so this transition is not modelled.
>
> I believe there can be more invariants and temporal properties of the
> model that can be checked. At the moment the temporal properties
> checking does not work, as I didn't master TLA+ enough yet. The safety
> invariants checking should work fine, though, but more work needed to
> devise and add the invariants.
>
> In the future, it would be great to have an established framework for
> modelling of the behavior in Bitcoin-like blockchain networks.
> In particular, having a model of mempool-related behavior would help to
> reason about difficult RBF/CPFP issues. The specification I present
> models the mempool, but in a simple way, without regards to the fees.
>
> The specification can be found in this github repository:
> https://github.com/dgpv/SASwap_TLAplus_spec
>
> There could be mistakes or omissions in the specified model, I hope
> that public review can help find these.
>
> It would be great to receive comments, suggestions and corrections,
> especially from people experienced in formal methods and TLA+, as this
> is only my second finished TLA+ spec and only my third project using
> formal methods (I created bitcoin transaction deserialization code in
> Ada/SPARK before that [3]). Please use the github issues or off-list
> mail to discuss if the matter is not interesting to the general
> bitcoin-dev list audience.
>
> [1] https://lamport.azurewebsites.net/tla/tla.html
>
> [2]
>
> 

Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-13 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>on completion of the protocol, if Bob lets the refund tx#1 become valid
(i.e. does not spend the BTC txo) then Alice can broadcast it, putting both
their funds into chaos

You forget, refund tx #1 has a script (which btw won't be visible with
taproot): "Alice & Bob OR Alice in +1 day" (relative) so if Alice
broadcasts it after protocol completion, she is just giving Bob the key to
her LTC (note: if she's wise she'd move the LTC beforehand), but Bob
doesn't lose the BTC because he has both keys and can just react before the
relative timelock expires. No chaos.

>This is why we eventually decided in Lightning to use two CPFP outpoints
rather than one

I appreciate the explanation. I see the problem now, and yes, that does
seem like a headache.

Cheers,
Ruben

On Wed, May 13, 2020 at 1:39 PM ZmnSCPxj  wrote:

> Good morning Ruben,
>
> > Hi ZmnSCPxj,
> >
> > >potentially both Alice and Bob know all the secrets on the LTC side and
> end up competing over it
> >
> > That's exactly right.
> >
> > >Bob can thus give a copy of the revoke tx with signature directly to
> its favorite miner, forcing Alice to take 3 transactions
> >
> > Note that the timelock on the revoke tx is longer than the timelock on
> refund tx #1. The idea is that Alice aborts the protocol by publishing
> refund tx #1 if the protocol hasn't reached step 4 in the svg by the time
> it becomes valid. This should entirely mitigate the issue you're describing.
>
> But if refund tx #1 at all exists, then you drop to the same issue you
> objected to with my proposal, which is that, on completion of the protocol,
> if Bob lets the refund tx#1 become valid (i.e. does not spend the BTC txo)
> then Alice can broadcast it, putting both their funds into chaos.
>
> So you might as well just use my counterproposal instead, which is
> simpler, gets bring-your-own-fees for free, etc.
>
> I suppose there is some *slight* improvement in that with your proposal,
> Alice *can* use revoke tx -> refund tx #2, but still, if Alice is insane
> then it could very well mess with the protocol by instead using refund tx
> #1.
> Thus, if Bob wants to survive in an environment where Alices are possibly
> insane (e.g. the real world), it should do everything in its power to
> ensure that the BTC txo is spent before the timeout of refund tx #1, if
> refund tx #1 exists at all.
> And if Bob is already going to do that, then Alice and Bob might as well
> just use my counterproposal etc etc.
>
> > >adding two CPFP outputs (one for each participant)
> >
> > There seems to be a situation where RBF can be disabled by the other
> party, but I'm not sure I see it... Why would a single output spendable by
> either key be insufficient?
>
> If one party quickly broadcasts a long chain of low-feerate transactions
> on top of the single output, then the output is "pinned".
>
> Low feerate means it is undesirable for miners to mine it, because it pays
> low for the amount of blockspace it has.
> But because there is a long chain of transactions, the absolute fee of
> that chain can be sizable, and we have a rule in RBF which, paraphrased,
> goes something like "the replacing transaction should also have a higher
> absolute fee than *all* the transactions it replaces", meaning the fee jump
> that the other side has to offer *has to be* pretty big.
>
> If the other outputs of the tx are then multisig, then the pinning
> participant can simply refuse to sign for those, and if the existing txes
> spending the other outputs are relative-time-locked, they cannot be used to
> CPFP the revoke tx onchain.
>
> This is why we eventually decided in Lightning to use two CPFP outpoints
> rather than one, and are also realizing just how much of a headache the RBF
> rules are, sigh.
>
> Still, in your proposed protocol the dependent transactions are all
> relative-timelocked, so timely confirmation of the revoke tx is not
> necessary, unlike in the case of Lightning where all HTLCs have to use an
> absolute timelock because we have to coordinate multiple HTLCs in
> forwarding and violation of the timelocks can lead to headaches and fund
> loss and so on.
> So maybe a single hook output, or even none at all, is workable.
>
> >
> > >We could use `SIGHASH_SINGLE | SIGHASH_ANYONECANPAY` as well
> >
> > Allowing others to add inputs/outputs would introduce malleability.
> Refund tx #2 and the timeout tx would become invalid.
>
> Ah, right, you still need `SIGHASH_ANYPREVOUT`/`SIGHASH_NOINPUT` for that.
>
> > >Bob cannot safely perform step 2 before getting both signatures for the
> revoke tx
> >
> > That's right, as you guessed, he does receive a copy of the signed
> revoke tx at protocol start.
> >
> > >>alternatively Bob can just spend before the timelock expires.
> > >This seems to be the safest alternative
> >
> > I agree not giving Alice time to publish the revoke tx is safest, but
> one does not preclude the other. The revoke tx is on an absolute timelock,
> so spending it before that time 

Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-13 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>potentially both Alice and Bob know all the secrets on the LTC side and
end up competing over it

That's exactly right.

>Bob can thus give a copy of the revoke tx with signature directly to its
favorite miner, forcing Alice to take 3 transactions

Note that the timelock on the revoke tx is longer than the timelock on
refund tx #1. The idea is that Alice aborts the protocol by publishing
refund tx #1 if the protocol hasn't reached step 4 in the svg by the time
it becomes valid. This should entirely mitigate the issue you're describing.

>adding two CPFP outputs (one for each participant)

There seems to be a situation where RBF can be disabled by the other party,
but I'm not sure I see it... Why would a single output spendable by either
key be insufficient?

>We could use `SIGHASH_SINGLE | SIGHASH_ANYONECANPAY` as well

Allowing others to add inputs/outputs would introduce malleability. Refund
tx #2 and the timeout tx would become invalid.

>Bob cannot safely perform step 2 before getting both signatures for the
revoke tx

That's right, as you guessed, he does receive a copy of the signed revoke
tx at protocol start.

>>alternatively Bob can just spend before the timelock expires.
>This seems to be the safest alternative

I agree not giving Alice time to publish the revoke tx is safest, but one
does not preclude the other. The revoke tx is on an absolute timelock, so
spending it before that time means you don't have anything to worry about,
and spending it later means you'll have to be online and keep an eye out.
If staying online is not a problem, then fee wise that seems preferable. As
long as less than half of all valid (i.e. the timelock was reached) revoke
transactions get broadcast, you'll be saving on fees.

Cheers,
Ruben

On Wed, May 13, 2020 at 11:57 AM Ruben Somsen  wrote:

> Hi Chris,
>
> Thanks for taking a look :)
>
> >it also improves privacy because the coins could stay unspend for a long
> time, potentially indefinitely
>
> Excellent point. The pre-swap setup transactions would still be subject to
> timing/amount analysis, but it's clearly a lot less problematic than the
> traditional 4 tx swap. And Payswap may be able to mitigate the amount
> analysis.
>
> >Using relative timelocks and private key handover for old-style coinswaps
> would give us the same two-transaction effect
>
> I agree, Lloyd pointed out the same thing. One thing to add is that such a
> setup would result in four on-chain transactions if the protocol is
> aborted, due to the need to invalidate the refund transaction.
>
> >the idea of private key handover was mentioned as early as 2016 in the
> original Lightning Network paper
>
> Interesting! Thanks for pointing that out.
>
> Cheers,
> Ruben
>
> On Wed, May 13, 2020 at 10:39 AM ZmnSCPxj  wrote:
>
>> Good morning Ruben,
>>
>> > >If the shortened refund transaction exists (labeled "refund
>> transaction #1" in the SVG) then the same issue still occurs
>> >
>> > Yes, but there is one crucial difference: at that point in the protocol
>> (Bob has the success transaction and then stops cooperating) Alice and Bob
>> both had the opportunity not to take that path. Bob could have sent the
>> success transaction, and Alice could have waited and sent the revoke
>> transaction. They would essentially be "colluding" to fail.
>>
>> Okay, so the concern is basically, that Bob misses the deadline, then
>> Alice feels obligated to reclaim the funds.
>> In your proposal, the tx competition is between the secret-revealing
>> success TX and the non-secret-revealing revoke tx.
>> Whereas in my counterproposal, under the same conditions, the tx
>> competition is between the secret-revealing success tx and the
>> secret-revealing backout tx, and both transactions becoming visible on P2P
>> network means potentially both Alice and Bob know all the secrets on the
>> LTC side and end up competing over it, RBFing each other until the entire
>> fund goes to miners.
>>
>>
>> > >Without the refund#1 in your proposal, Bob refusing cooperation after
>> Alice puts the BTC into lock for 3 days and 2 further onchain transactions
>> >
>> > I'm not sure if I correctly understood what you're saying, but it's as
>> follows:
>> >
>> > Refund #1 can only safely be used before the signed success tx is given
>> to Bob. The cost to Alice at this point if Bob aborts is two on-chain
>> transactions while Bob hasn't put anything on-chain yet.
>> >
>> > Refund #2 needs to be used after Bob receives the signed success tx.
>> The cost to Alice is now three transactions, but Bob also went-on-chain by
>> this point, so causing this wasn't costless to Bob and is thus a similar
>> failure mode.
>>
>> I think it is not accurate that Bob is already on-chain before Alice can
>> be forced to use 3 transactions to fail.
>>
>> The revoke tx signatures are shared at step 0 of your protocol
>> description.
>> Thus Bob has a copy of the revoke tx that is valid once Alice signs and
>> confirms the funding 

Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-13 Thread Ruben Somsen via bitcoin-dev
Hi Chris,

Thanks for taking a look :)

>it also improves privacy because the coins could stay unspend for a long
time, potentially indefinitely

Excellent point. The pre-swap setup transactions would still be subject to
timing/amount analysis, but it's clearly a lot less problematic than the
traditional 4 tx swap. And Payswap may be able to mitigate the amount
analysis.

>Using relative timelocks and private key handover for old-style coinswaps
would give us the same two-transaction effect

I agree, Lloyd pointed out the same thing. One thing to add is that such a
setup would result in four on-chain transactions if the protocol is
aborted, due to the need to invalidate the refund transaction.

>the idea of private key handover was mentioned as early as 2016 in the
original Lightning Network paper

Interesting! Thanks for pointing that out.

Cheers,
Ruben

On Wed, May 13, 2020 at 10:39 AM ZmnSCPxj  wrote:

> Good morning Ruben,
>
> > >If the shortened refund transaction exists (labeled "refund transaction
> #1" in the SVG) then the same issue still occurs
> >
> > Yes, but there is one crucial difference: at that point in the protocol
> (Bob has the success transaction and then stops cooperating) Alice and Bob
> both had the opportunity not to take that path. Bob could have sent the
> success transaction, and Alice could have waited and sent the revoke
> transaction. They would essentially be "colluding" to fail.
>
> Okay, so the concern is basically, that Bob misses the deadline, then
> Alice feels obligated to reclaim the funds.
> In your proposal, the tx competition is between the secret-revealing
> success TX and the non-secret-revealing revoke tx.
> Whereas in my counterproposal, under the same conditions, the tx
> competition is between the secret-revealing success tx and the
> secret-revealing backout tx, and both transactions becoming visible on P2P
> network means potentially both Alice and Bob know all the secrets on the
> LTC side and end up competing over it, RBFing each other until the entire
> fund goes to miners.
>
>
> > >Without the refund#1 in your proposal, Bob refusing cooperation after
> Alice puts the BTC into lock for 3 days and 2 further onchain transactions
> >
> > I'm not sure if I correctly understood what you're saying, but it's as
> follows:
> >
> > Refund #1 can only safely be used before the signed success tx is given
> to Bob. The cost to Alice at this point if Bob aborts is two on-chain
> transactions while Bob hasn't put anything on-chain yet.
> >
> > Refund #2 needs to be used after Bob receives the signed success tx. The
> cost to Alice is now three transactions, but Bob also went-on-chain by this
> point, so causing this wasn't costless to Bob and is thus a similar failure
> mode.
>
> I think it is not accurate that Bob is already on-chain before Alice can
> be forced to use 3 transactions to fail.
>
> The revoke tx signatures are shared at step 0 of your protocol description.
> Thus Bob has a copy of the revoke tx that is valid once Alice signs and
> confirms the funding transaction.
> Bob can thus give a copy of the revoke tx with signature directly to its
> favorite miner, forcing Alice to take 3 transactions to back out of the
> swap.
>
> Since Bob gave the tx directly to its favorite miner (TANSTAAGM: "There
> ain't no such thing as a global mempool"), Alice will only know about this
> event when the revoke tx is confirmed once, at which point it is very
> difficult to reverse, even if Alice has a refund#1 tx prepared.
>
> Bob can do this before step 2 in your protocol description, meaning before
> Bob locks up any funds, so Bob can do this for free, and will even use
> funds going back to Alice to pay for confirmation of the revoke tx.
> Because Bob can do this for free, there is no disincentive for trolling
> Bobs to exist whose sole life goal is to just grief possible Alices.
>
> This can be slightly mitigated by adding two CPFP outputs (one for each
> participant) and using the minimum relayable feerate for the revoke tx so
> that Bob is forced to bring its own fees in order to incentivize miners.
> This is similar to the "bring your own fees" currently proposed for
> Lightning, but note the recent hand-wringing about the various problems
> this adds to mempools and CPFP and RBF rules and etc etc:
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-April/017757.html
>
> We could use `SIGHASH_SINGLE | SIGHASH_ANYONECANPAY` as well for a
> bring-your-own-fees, but that is not `SIGHASH_ALL` and thus marks the
> transaction graph as special.
> And forcing bring-your-own-fees means neither Alice nor Bob can swap all
> their funds in a single operation, they have to keep a reserve.
>
>
> Bob cannot safely perform step 2 before getting both signatures for the
> revoke tx, as without Bob having access to the rveoke tx, if Bob locks up
> LTC, Alice can stop responding and lock both their funds indefinitely with
> Bob not having any way to recover its funds, 

Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-12 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>If the shortened refund transaction exists (labeled "refund transaction
#1" in the SVG) then the same issue still occurs

Yes, but there is one crucial difference: at that point in the protocol
(Bob has the success transaction and then stops cooperating) Alice and Bob
both had the opportunity not to take that path. Bob could have sent the
success transaction, and Alice could have waited and sent the revoke
transaction. They would essentially be "colluding" to fail.

>Without the refund#1 in your proposal, Bob refusing cooperation after
Alice puts the BTC into lock for 3 days and 2 further onchain transactions

I'm not sure if I correctly understood what you're saying, but it's as
follows:

Refund #1 can only safely be used before the signed success tx is given to
Bob. The cost to Alice at this point if Bob aborts is two on-chain
transactions while Bob hasn't put anything on-chain yet.

Refund #2 needs to be used after Bob receives the signed success tx. The
cost to Alice is now three transactions, but Bob also went-on-chain by this
point, so causing this wasn't costless to Bob and is thus a similar failure
mode.

>my formulation allows any of the result transactions to be CPFP directly
by their beneficiaries

Yes, that is indeed very nice. The way I set it up, insufficient fees can
unfortunately cause delays, but they should not be able to cause losses.

>there is still an onlineness requirement in case Bob does not complete the
protocol

Yes, that is very much the design. Alice needs to be on time with claiming
her refund (and revealing her secret), otherwise Bob takes it.

>I have not seen the 2-tx variant video yet, as I prefer to read than listen

The video is not required, it just restates what is in the write-up. I
personally find it easier to understand concepts from video, but I seem to
be in the minority when I ask other devs about this. But let me reiterate
one part you might be confused about (though you probably mostly get it
already):

The online requirement I was alluding to doesn't expire, and is
specifically how the 2 tx SAS protocol is performed. Bob never broadcasts
the success transaction (unless he prefers not to have to be online, i.e.
the 3 tx SAS protocol) and instead Alice and Bob swap their keys: first Bob
hands over secretAlice, then Alice hands over her key. Now the swap is
complete, but Bob has to remain online to make sure Alice never attempts to
broadcast her refund tx. It doesn't expire either because of the relative
timelocks.

Just take a look at the slide 6m8s into the video:
https://youtu.be/TlCxpdNScCA?t=6m8s

I also agree with your observation that alternatively Bob can just spend
before the timelock expires.

>Regardless, the overall protocol of using 3 clauses in the swap, and
reusing the privkey as the payment secret demanded by the pointlocks, is
still a significant innovation.

I'm glad you like it :)

>In the context of CoinSwap, a proposal is that a CoinSwap server would
provide swapping service to incoming clients.

That is an excellent use case that takes good advantage of the asymmetry of
SAS. I completely agree with your observation that the "Bob" side is
perfect for servers (online and/or spending again soon) and the "Alice"
side is perfect for clients (settled in 1 tx). I similarly hope that this
may pave the way for a practical implementation of Payswap between
merchants and customers!

Cheers,
Ruben

On Tue, May 12, 2020 at 5:06 PM ZmnSCPxj  wrote:

> Good morning Ruben,
>
> > >Would this not work?
> >
> > I considered and rejected that model for the following reason: there are
> moments where both Alice and Bob can claim the BTC. If they both attempt to
> do so, it also reveals both secrets, causing the LTC to also be claimable
> by both parties. This chaotic scenario is a failure mode that did not seem
> acceptable to me. The revoke transaction was specifically added to mitigate
> that issue (invalidating any attempt of Bob to claim the coins and reveal
> his secret). That said, it doesn't particularly seem in either party's
> interest wait until a moment where two timelocks become valid, so maybe it
> is not quite as bad as I thought. However, it still means that the
> incompetence/malevolence of one party can lead to losses for both parties.
> I have my doubts a gain in privacy in the uncooperative case is worth that
> risk.
> >
> > Of course it also reverts the protocol to 3 transactions, instead of 2,
> but regardless, not having to watch the chain is probably more practical in
> many cases. As an aside, if both chains support timelocks then we can
> ensure that the more expensive chain only receives one transaction.
>
> If the shortened refund transaction exists (labeled "refund transaction
> #1" in the SVG) then the same issue still occurs: after 1 day it is
> possible for either success or refund#1 to be broadcasted, leading to
> revelation of both secrets, leading to the same failure mode you described.
>
> Without the refund#1 

Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-12 Thread Ruben Somsen via bitcoin-dev
Hi Lloyd,

>In my opinion, this protocol is theoretical breakthrough as well as a
practical protocol. Well done!

Thanks for the kind praise, and for providing a summary of what you think
makes the protocol useful. Your different perspective is undoubtedly useful
for others who are trying to understand it.

>We might call this a "Forced Refund *TLC"

Good description, I like it.

>The advantages that Ruben's two tx protocol has over this is that
timelocks and monitoring is only needed on one of the chains.

Well put, and I agree with your point that the traditional 4 tx protocol
can also be turned into 2 tx with an online requirement. One minor thing to
add is that this would make the 4 tx protocol more clunky in the
non-cooperative case (a 4 tx timeout). In the SAS protocol it comes at no
cost.

Cheers,
Ruben

On Tue, May 12, 2020 at 1:30 PM Ruben Somsen  wrote:

> Hi ZmnSCPxj,
>
> >Would this not work?
>
> I considered and rejected that model for the following reason: there are
> moments where both Alice and Bob can claim the BTC. If they both attempt to
> do so, it also reveals both secrets, causing the LTC to also be claimable
> by both parties. This chaotic scenario is a failure mode that did not seem
> acceptable to me. The revoke transaction was specifically added to mitigate
> that issue (invalidating any attempt of Bob to claim the coins and reveal
> his secret). That said, it doesn't particularly seem in either party's
> interest wait until a moment where two timelocks become valid, so maybe it
> is not quite as bad as I thought. However, it still means that the
> incompetence/malevolence of one party can lead to losses for both parties.
> I have my doubts a gain in privacy in the uncooperative case is worth that
> risk.
>
> Of course it also reverts the protocol to 3 transactions, instead of 2,
> but regardless, not having to watch the chain is probably more practical in
> many cases. As an aside, if both chains support timelocks then we can
> ensure that the more expensive chain only receives one transaction.
>
> >if relative locktimes are used as often as absolute locktimes for
> block-sniping-prevention and a decent Scriptless Script system, then all
> protocol aborts should be doable with no information leaks
>
> I see your point, interesting observation.
>
> >A sidenote as well, that if Alice typically uses an HD wallet, the UTXO
> on the LTC side would not be in that HD, and if Alice wants to cold-store
> the LTC, it should move the money as well into an HD pubkey.
>
> Agreed, I had that listed as one of the disadvantages: "Access to money is
> contingent on remembering secrets (backup complexity)"
>
> Cheers,
> Ruben
>
>
> On Tue, May 12, 2020 at 8:50 AM Lloyd Fournier 
> wrote:
>
>> A quick correction to my post:
>>
>>>
>>> Here's where the truly novel part comes in. Ruben solves this by
>>> extending the standard *TLC contract:
>>> 1. Bob redeem with secret
>>> 2. Alice refund after T1
>>> 3. Bob redeem without secret after T2
>>>
>>> This is actually:
>>
>> 1. Bob redeem with redeem secret
>> 2. Alice refund after T1 with refund secret
>> 3. Bob redeem without secret after T2
>>
>> The fact that Alice reveals a secret when she refunds is crucial.
>>
>> LL
>>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-12 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>Would this not work?

I considered and rejected that model for the following reason: there are
moments where both Alice and Bob can claim the BTC. If they both attempt to
do so, it also reveals both secrets, causing the LTC to also be claimable
by both parties. This chaotic scenario is a failure mode that did not seem
acceptable to me. The revoke transaction was specifically added to mitigate
that issue (invalidating any attempt of Bob to claim the coins and reveal
his secret). That said, it doesn't particularly seem in either party's
interest wait until a moment where two timelocks become valid, so maybe it
is not quite as bad as I thought. However, it still means that the
incompetence/malevolence of one party can lead to losses for both parties.
I have my doubts a gain in privacy in the uncooperative case is worth that
risk.

Of course it also reverts the protocol to 3 transactions, instead of 2, but
regardless, not having to watch the chain is probably more practical in
many cases. As an aside, if both chains support timelocks then we can
ensure that the more expensive chain only receives one transaction.

>if relative locktimes are used as often as absolute locktimes for
block-sniping-prevention and a decent Scriptless Script system, then all
protocol aborts should be doable with no information leaks

I see your point, interesting observation.

>A sidenote as well, that if Alice typically uses an HD wallet, the UTXO on
the LTC side would not be in that HD, and if Alice wants to cold-store the
LTC, it should move the money as well into an HD pubkey.

Agreed, I had that listed as one of the disadvantages: "Access to money is
contingent on remembering secrets (backup complexity)"

Cheers,
Ruben


On Tue, May 12, 2020 at 8:50 AM Lloyd Fournier 
wrote:

> A quick correction to my post:
>
>>
>> Here's where the truly novel part comes in. Ruben solves this by
>> extending the standard *TLC contract:
>> 1. Bob redeem with secret
>> 2. Alice refund after T1
>> 3. Bob redeem without secret after T2
>>
>> This is actually:
>
> 1. Bob redeem with redeem secret
> 2. Alice refund after T1 with refund secret
> 3. Bob redeem without secret after T2
>
> The fact that Alice reveals a secret when she refunds is crucial.
>
> LL
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-11 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

Thanks for your feedback :)

>CoinSwap for privacy is practically a "cross" chain atomic swap with the same 
>chain and token for both sides of the swap

I agree, I didn't mean to imply that was new, only that this protocol
makes it more efficient.

>"Instead, Bob simply hands secretBob to Alice" is basically the same as 
>private key turnover

Thanks for the link. I will add it to the links at the bottom of the
write-up, as I agree it's related. Do note there are a few key
differences:

- The swap is set up in an "asymmetric" way with only timelocks on one
side, so on the other side the swap *never* expires
- The timelocks are set up in such a way that the swap does not expire
unless Alice starts the relative timelock countdown (the revoke
transaction)
- This relative timelock setup comes practically for free, because the
asymmetry naturally requires that kind of setup

>The "OR Alice in +1 day" branch can be implemented, at least on Bitcoin and 
>similar blockchains, by signing a specific `nSequence`

"OR Alice in +1 day" is "refund transaction #1" from the diagram. If
I'm not mistaken, the change you are suggesting is exactly how "refund
transaction #2" is constructed. Note that #1 and #2 serve the same
purpose. Strictly speaking, #1 is not needed at all, but it's there to
give Alice the option to back out of the swap in two transactions as
opposed to three.

>It strikes me that the relative locktime is unnecessary on the output of this 
>refund tx

I believe I addressed this in the FAQ section (the question about
absolute timelocks). An absolute timelock is possible, but you then
need to make absolutely sure that the revoke transaction confirms in
time, otherwise the protocol can fail (namely after Bob has received a
copy of the success transaction and just waits and does nothing). You
also lose the ability to keep the channel open indefinitely.

>having a variety of different versions of the transactions with different 
>feerates could be used

That's a good point.

>As long as the one resolving a particular side of the swap is the one that 
>ocmpletes the signature (which I believe holds true for all branches?)

Unfortunately this does not hold for the revoke transaction. It would
be a bit awkward if Alice had a high fee copy after the protocol
completes. She could send it to the blockchain and essentially Bob
would be paying for it. I'm not as concerned about the other
transactions, because those could all be bumped with CPFP if needed,
but having different feerates would be nice.

And a general comment about privacy: it seems inevitable that some
information will be leaked if the protocol does not complete
cooperatively. As long as the cooperative case is not traceable, that
seems about as good as it can get. That's my view, at least. I'd be
curious to hear if you see that differently.

Cheers,
Ruben



On Mon, May 11, 2020 at 6:45 PM ZmnSCPxj  wrote:
>
> Good morning Ruben,
>
> CoinSwap for privacy is practically a "cross" chain atomic swap with the same 
> chain and token for both sides of the swap, see also this set of ideas: 
> https://github.com/AdamISZ/CoinSwapCS/issues/53
>
> "Instead, Bob simply hands secretBob to Alice" is basically the same as 
> private key turnover, as best as I can understand it, and gives significant 
> advantages, also described in passing here: 
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017816.html
>
> Overall, this looks very much like a working CoinSwap as well.
>
> The Refund tx does not need anything more than a 2-of-2 script.
> The "OR Alice in +1 day" branch can be implemented, at least on Bitcoin and 
> similar blockchains, by signing a specific `nSequence`, or if the chain 
> forking predates BIP68, by using absolute locktimes and signing a specific 
> `nLockTime`, with the destination being just "Alice".
> This should help privacy, as now all `scriptPubKey`s will be 2-of-2 (or P2PKH 
> with 2p-ECDSA).
>
> (It strikes me that the relative locktime is unnecessary on the output of 
> this refund tx --- as long as both participants agree on either Alice or Bob 
> having a longer locktime, you can just use the locktime on the refund tx 
> directly as backout; see the topic "`nLockTime`-protected Backouts" on the 
> CoinSwapCS issue link)
>
> If you are willing to accept protocol complexity, having a variety of 
> different versions of the transactions with different feerates could be used 
> rather than the Decker-Russell-Osuntokun "eltoo" bring-your-own-fees method.
> In terms of privacy this is better as you would not be using anything other 
> than the most boring `SIGHASH_ALL` signing flag, whereas the 
> Decker-Russell-Osuntokun will be identifiable onchain (and thus possibly flag 
> the transaction as "of interest" to surveillors) due to use of 
> `SIGHASH_ANYPREVOUT`.
> As long as the one resolving a particular side of the swap is the one that 
> ocmpletes the signature (which I believe holds true for all branches?) 

[bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-11 Thread Ruben Somsen via bitcoin-dev
Works today with single signer ECDSA adaptor signatures[0], or with
Schnorr + MuSig.

Diagram here:
https://gist.github.com/RubenSomsen/8853a66a64825716f51b409be528355f#file-succinctatomicswap-svg


Advantages:

- Requires merely two on-chain transactions for successful completion,
as opposed to four
- Scriptless, and one of the chains doesn't need to support timelocks
- Can be used for efficient privacy swaps, e.g. Payswap[1]


Disadvantages:

- Access to money is contingent on remembering secrets (backup complexity)
- Online/watchtower requirement for the timelock supporting chain (not
needed with 3 tx protocol)


Protocol steps:


0.) Alice & Bob pre-sign the following transactions, with exception of
the signatures in [brackets]:

- success_tx (money to Bob): [sigSuccessAlice] + [sigSuccessBob]
- revoke_tx (timelock): sigRevokeAlice + sigRevokeBob, which must then
be spent by:
  -- refund_tx (relative timelock, refund to Alice): [sigRefundAlice]
+ {sigRefundBob}
  -- timeout_tx (longer relative timelock, money to Bob):
sigTimeoutAlice + [sigTimeoutBob]

{sigRefundBob} is an adaptor signature, which requires secretAlice to complete


1.) Alice proceeds to lock up 1 BTC with Bob, using keyAlice & keyBob as pubkeys

If protocol is aborted after step 1:

- Alice publishes the revoke_tx, followed by the refund_tx &
sigRefundBob, to get her BTC back
- If Alice neglects to publish the refund_tx in time, Bob will claim
the BTC with the timeout_tx


2.) Bob locks up altcoins with Alice, using secretAlice & secretBob as pubkeys

If protocol is aborted after step 2:

- Once Alice publishes sigRefundBob, Bob learns secretAlice and
regains control over the altcoins


3.) Protocol completion:

- Alice hands adaptor signature {sigSuccessAlice} to Bob, which
requires secretBob to complete
- Bob could now claim the BTC via the success_tx, reveal secretBob,
and thus give Alice control over the altcoins (= 3 tx protocol)
- Instead, Bob simply hands secretBob to Alice
- Likewise, Alice hands keyAlice to Bob to forego her claim on the refund_tx
- Bob continues to monitor the chain, because he'll have to respond if
Alice ever publishes the revoke_tx


More graceful protocol failure:

If the protocol aborts after step 1, Alice would have been forced to
make three transactions in total, while Bob has made none. We can
reduce that to two by introducing a second refund_tx with timelock
that can be published ahead of the revoke_tx and directly spends from
the funding transaction. Publishing this transaction would also reveal
secretAlice to Bob via an adaptor signature. In the 3 tx protocol,
this output can go directly to Alice. In the 2 tx protocol with
online/watchtower requirement, this output needs a script: spendable
by Alice + Bob right away OR by Alice after a relative timelock. It is
important to note that this transaction must NOT be published during
step 3. Once Bob can complete the success_tx, the revoke_tx is needed
to invalidate the success_tx prior to revealing secretAlice.


FAQ:

- Why not allow Alice to still claim the altcoins if she accidentally
lets Bob publish the timeout_tx?

Alice could send the revoke_tx at the same time, revealing both
secrets and causing likely losses. This can be solved by adding yet
another transaction, but it wouldn't be efficient and wouldn't
motivate Alice to behave.

- Is it possible to implement this protocol on chains which only
support absolute timelocks?

Yes, but then Bob must spend his swapped coins before the timelock
expires (or use the 3 tx protocol). Be aware that the revoke_tx MUST
confirm before the timeout_tx becomes valid, which may become a
problem if fees suddenly rise. The refund_tx can also not be allowed
to CPFP the timeout_tx, as they must confirm independently in order to
invalidate the success_tx first.

- Can't Alice just publish the revoke_tx after protocol completion?

Yes, she'd first have to move the altcoins (to invalidate
secretAlice), and could then try to claim the BTC by publishing the
revoke_tx, forcing Bob to react on-chain before the refund_tx becomes
valid. The eltoo[2] method of paying for fees (requires
sighash_anyprevout) or a second CPFP-able output may be an improvement
here (and also mitigates fee rising issues), but note that this also
increases the required amount of tx data if the protocol doesn't
complete successfully.

- Can this be made to work with hash locks?

Yes, by making the altcoins spendable via sigAlice + preimageBob OR
sigBob + preimageAlice, and ensuring the contracts on the BTC side
reveal either pre-image. Do note that this is not scriptless and will
thus increase the transaction size.


Open question:

Perhaps it's possible to perform an atomic swap in and out of
Lightning with only a single on-chain transaction. This would require
some kind of secondary set of HTLCs, allowing the sender to cancel a
Lightning payment by revealing a secret after a certain period of
time.


-- Ruben Somsen




Thanks to Lloyd Fournier for 

Re: [bitcoin-dev] Statechain implementations

2020-03-28 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

the current owner can ask the statechain entity to sign an alternative to
> the first stage, with 0 relative locktime


Unless I am misunderstanding something, this seems to run into the problem
that the original first stage transaction is already out there (and its
relative timelock started ticking). There is no mechanism ensuring that the
new tx will have precedence. And even if it did work, I doubt it's cleaner
than doing a cooperative peg-out that simultaneously happens to peg back
in, creating a brand new statechain UTXO with no history.

Cheers,
Ruben

On Sat, Mar 28, 2020 at 6:38 PM Ruben Somsen  wrote:

> Hi Bob,
>
> Looks like we're largely thinking along the same lines.
>
> It's unlikely that a party sending a UTXO to another party will have a
>> UTXO of exactly the right size that's needed
>
>
> My original proposal uses adaptor signatures to ensure swapping UTXOs is
> atomic. All parties choose a secret, then they all make adaptor signatures,
> then they reveal their secret to the statechain entity. The SE then
> publishes the signatures, causing everyone to learn the secret. And if the
> SE doesn't publish, it simply means the transfer didn't occur.
>
> But taking a step back and thinking about an MVP, it may be easier to make
> it more like a fully audited transparent blockchain where multiple users
> create a combined transaction of all the UTXOs they want to swap, which is
> published together with all the corresponding Bitcoin transactions. Then
> adaptor signatures aren't needed.
>
> The downside of that method is that you lose the ability to only validate
> the history of the coins you hold (scalability win). For this to be
> possible, you need to keep the history of every individual UTXO completely
> separate. I still think that is where we eventually want to end up (as well
> as having blind signatures), but it adds a lot of complexity (adaptor
> signatures, sparse merkle trees with non-inclusion proofs...).
>
> The natural solution is to decompose your outputs in a binary decomposition
>
>
> I fully agree, but on top of that I think we also need Lightning,
> because
>
> This same mechanism can also be used to pay the SE for its service through
>> a different UTXO than the one being transferred.
>
>
> My conclusion was that opening a Lightning channel on top of a statechain
> makes more sense for this (as ZmnSCPxj explained in his reply to you). If
> we expect BTC fees to go up, we can't expect the statechain to hold UTXOs
> that are small enough to be used to pay for statechain fees.
>
> More on this in my Breaking Bitcoin 2019 talk (timestamped link):
> https://youtu.be/09HcYRjDkMA?t=850
>
> a logical enhancement would be to use some kind of single-use seal
>
>
> Any kind of system where users transfer ownership through signatures will
> resemble single-use seals, so I'd say that's inevitable! :)
>
> Cheers,
> Ruben
>
>
> On Sat, Mar 28, 2020 at 3:42 AM ZmnSCPxj via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Good morning Bob,
>>
>> > Big picture, it seems to me this idea is workable and very interesting.
>> I see
>> > three likely enhancements that will be necessary or desirable:
>> > 1. Atomic swap of multiple UTXOs, and binary decomposition of value in
>> lots
>> > 2. Key exchange ("addresses") to facilitate a secure comms path from
>> > sender -> receiver
>> >
>> > 3. (Optional) single-use seals to close old state
>> >
>> >
>> > (1) It's unlikely that a party sending a UTXO to another party will
>> have a UTXO
>> > of exactly the right size that's needed, already locked into the
>> statechain. If
>> > he has to create the UTXO first and then lock it into the statechain,
>> the
>> > statechain solution is no better than an on-chain send. And once the
>> receiver
>> > has the UTXO, it's unlikely that he will want to send exactly that same
>> amount
>> > to another receiver later. This isn't a problem in Lightning where
>> amounts can
>> > be arbitrarily updated. As a consequence, I think Lightning is more
>> valuable for
>> > small-value payments, and statechains will be more valuable for larger
>> values.
>> >
>> > The natural solution is to decompose your outputs in a binary
>> decomposition,
>> > having e.g. UTXOs with 1048576 satoshis, another with 2097152 satoshis,
>> and so
>> > on. Then when I want to send, I select the appropriate UTXOs as a binary
>> > decomposition of the value I want to send, with a "lot size" of 1048576
>> > satoshis, or the dust limit. The notion of "lots" like this is common in
>> > traditional markets...many stocks are bought and sold in lots of 100,
>> and forex
>> > is traded in lots of $100,000. Users of a statechain therefore need
>> log(V)
>> > available UTXOs locked into the statechain, where V is their value in
>> BTC.
>> > Having fixed lot sizes like this also makes coinjoin-type uses more
>> viable. The
>> > statechain could also assist in dividing a UTXO into two utxos of the
>> next lot
>> > 

Re: [bitcoin-dev] Statechain implementations

2020-03-28 Thread Ruben Somsen via bitcoin-dev
Hi Bob,

Looks like we're largely thinking along the same lines.

It's unlikely that a party sending a UTXO to another party will have a UTXO
> of exactly the right size that's needed


My original proposal uses adaptor signatures to ensure swapping UTXOs is
atomic. All parties choose a secret, then they all make adaptor signatures,
then they reveal their secret to the statechain entity. The SE then
publishes the signatures, causing everyone to learn the secret. And if the
SE doesn't publish, it simply means the transfer didn't occur.

But taking a step back and thinking about an MVP, it may be easier to make
it more like a fully audited transparent blockchain where multiple users
create a combined transaction of all the UTXOs they want to swap, which is
published together with all the corresponding Bitcoin transactions. Then
adaptor signatures aren't needed.

The downside of that method is that you lose the ability to only validate
the history of the coins you hold (scalability win). For this to be
possible, you need to keep the history of every individual UTXO completely
separate. I still think that is where we eventually want to end up (as well
as having blind signatures), but it adds a lot of complexity (adaptor
signatures, sparse merkle trees with non-inclusion proofs...).

The natural solution is to decompose your outputs in a binary decomposition


I fully agree, but on top of that I think we also need Lightning,
because

This same mechanism can also be used to pay the SE for its service through
> a different UTXO than the one being transferred.


My conclusion was that opening a Lightning channel on top of a statechain
makes more sense for this (as ZmnSCPxj explained in his reply to you). If
we expect BTC fees to go up, we can't expect the statechain to hold UTXOs
that are small enough to be used to pay for statechain fees.

More on this in my Breaking Bitcoin 2019 talk (timestamped link):
https://youtu.be/09HcYRjDkMA?t=850

a logical enhancement would be to use some kind of single-use seal


Any kind of system where users transfer ownership through signatures will
resemble single-use seals, so I'd say that's inevitable! :)

Cheers,
Ruben


On Sat, Mar 28, 2020 at 3:42 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Bob,
>
> > Big picture, it seems to me this idea is workable and very interesting.
> I see
> > three likely enhancements that will be necessary or desirable:
> > 1. Atomic swap of multiple UTXOs, and binary decomposition of value in
> lots
> > 2. Key exchange ("addresses") to facilitate a secure comms path from
> > sender -> receiver
> >
> > 3. (Optional) single-use seals to close old state
> >
> >
> > (1) It's unlikely that a party sending a UTXO to another party will have
> a UTXO
> > of exactly the right size that's needed, already locked into the
> statechain. If
> > he has to create the UTXO first and then lock it into the statechain, the
> > statechain solution is no better than an on-chain send. And once the
> receiver
> > has the UTXO, it's unlikely that he will want to send exactly that same
> amount
> > to another receiver later. This isn't a problem in Lightning where
> amounts can
> > be arbitrarily updated. As a consequence, I think Lightning is more
> valuable for
> > small-value payments, and statechains will be more valuable for larger
> values.
> >
> > The natural solution is to decompose your outputs in a binary
> decomposition,
> > having e.g. UTXOs with 1048576 satoshis, another with 2097152 satoshis,
> and so
> > on. Then when I want to send, I select the appropriate UTXOs as a binary
> > decomposition of the value I want to send, with a "lot size" of 1048576
> > satoshis, or the dust limit. The notion of "lots" like this is common in
> > traditional markets...many stocks are bought and sold in lots of 100,
> and forex
> > is traded in lots of $100,000. Users of a statechain therefore need
> log(V)
> > available UTXOs locked into the statechain, where V is their value in
> BTC.
> > Having fixed lot sizes like this also makes coinjoin-type uses more
> viable. The
> > statechain could also assist in dividing a UTXO into two utxos of the
> next lot
> > size down, so that I have the right UTXOs to hit the value I want to
> send.
>
> My understanding of statechains is that nothing prevents the statechain
> from internally having multiple UTXOs divided from a single large onchain
> UTXO.
>
> Indeed, a statechain can act much like a federated blockchain, and the
> interface to the statechain could be for its clients to send a Bitcoin
> transaction to it spending 1 or more of the UTXOs currently instantiated
> inside the statechain.
> Then the statechain validates the client Bitcoin transaction, updates its
> state and republishes it to its clients, removing the
> (internal-to-statechain-only) UTXOs spent, and inserting the new UTXOs of
> the incoming transaction.
>
> For example, suppose I have a 1BTC onchain UTXO that I 

Re: [bitcoin-dev] Statechain implementations

2020-03-27 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

I appreciate the input.

>Any standardness issue can be fixed by embedding it in a P2WSH / P2SH, you
can use an `OP_TRUE` `redeemScript`, for instance.

Good point. I guess the conversation I recall reading must have been about
avoiding p2sh in order to lower the tx size.

>broadcast a non-RBF child transaction with tiny fee, so that it and its
parent transaction will be accepted into mempools but would not be
replaceable

I believe this is solved by inherited signalling. As long as the kickoff tx
is RBF enabled (and unconfirmed), any transaction spending it automatically
inherits its RBF status. See:
https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki#Summary

>The broadcasting of the kickoff simply means that the first stage cannot
be easily changed

I see what you're saying. Yeah, it does ruin the stages. If the kickoff tx
hits the chain, you'd probably just want to "refresh" the UTXO by agreeing
with the statechain entity to spend it to a new statechain 2-of-2 UTXO
on-chain, thus removing all prior owners. Ideally you'd want it to be more
costly to CPFP the kickoff tx than it is to refresh the UTXO, so the
defender is at an advantage. The statechain entity should probably pay for
every refresh ("insurance"), since the actual owner isn't at fault.

Cheers,
Ruben


On Fri, Mar 27, 2020 at 2:46 AM ZmnSCPxj  wrote:

> Good morning Ruben,
>
> > Hey Christian,
> >
> > Thanks for chiming in :)
> >
> > >It might be worth adopting the late fee binding we have in eltoo
> >
> > That is where my thinking originally went as well, but then I remembered
> that this alters the txid, causing the settlement tx to become invalid.
> What I am suggesting should be functionally the same (albeit less
> space-efficient): a secondary output that can be spent by anyone, which can
> be used to fee bump the kickoff tx with CPFP. I believe this same idea was
> considered for Lightning as well at some point. Do you happen to recall if
> there was some kind of non-standardness issue with it?
>
> Any standardness issue can be fixed by embedding it in a P2WSH / P2SH, you
> can use an `OP_TRUE` `redeemScript`, for instance.
>
> Using an `OP_TRUE` `redeemScript` would allow any third party to make you
> cry by opportunistically spending such an output.
> For example your Bitcoin-network peer could notice you broadcasting such a
> transaction with an `OP_TRUE` output, see you spend that output with a
> CPFP-RBF-ed child transaction, then instead of further broadcasting the
> child transaction, instead broadcast a non-RBF child transaction with tiny
> fee, so that it and its parent transaction will be accepted into mempools
> but would not be replaceable with a higher-feerate child transaction
> (because not RBF-flagged).
> Thus, some portion of mempools will contain this poisoned low-fee child
> transaction and prevent the parent from being confirmed (because the
> parent+child fees are not enough to justify being put in a block).
> Which I suppose is an argument for Full RBF aka
> ignore-the-RBF-flag-and-always-RBF.
>
> The solution that I remember being proposed for this in Lightning was to
> give each participant its own attach-your-fees output that only that
> participant can spend, which works for Lightning because the set of
> participants in a channel is permanently fixed, but probably not for
> statechains.
>
> --
>
> The broadcasting of the kickoff simply means that the first stage cannot
> be easily changed, and you might still be able to make further updates by
> updating only the later stages, until the last stage is confirmable, so the
> kickoff being broadcast simply creates a "dead man walking" statechain.
> However, the implementation complexity would probably increase
> tremendously.
>
>
> Regards,
> ZmnSCPxj
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Statechain implementations

2020-03-26 Thread Ruben Somsen via bitcoin-dev
Hey Christian,

Thanks for chiming in :)

>It might be worth adopting the late fee binding we have in eltoo

That is where my thinking originally went as well, but then I remembered
that this alters the txid, causing the settlement tx to become invalid.
What I am suggesting should be functionally the same (albeit less
space-efficient): a secondary output that can be spent by anyone, which can
be used to fee bump the kickoff tx with CPFP. I believe this same idea was
considered for Lightning as well at some point. Do you happen to recall if
there was some kind of non-standardness issue with it?

>Wouldn't that result in a changing pubkey at each update, and thus require
an onchain move to be committed?

I have yet to take a closer look at the math, but my understanding is that
the same key (x) gets redistributed. First x = s1 + o1 and after the
transfer x = s2 + o2 (not the actual math, but it demonstrates how the
transitory key can change from o1 to o2). Assuming s1 is then thrown away
(trust assumption), o1 becomes harmless information.

Cheers,
Ruben

On Thu, Mar 26, 2020 at 6:17 PM Greg Sanders  wrote:

> > Wouldn't that result in a changing pubkey at each update, and thus
> require an onchain move to be committed?
>
> Suggestion was in line with original proposal where no keys are changing
> ever, just not presupposing existence of MuSig.
>
> On Thu, Mar 26, 2020 at 1:15 PM Christian Decker via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Ruben Somsen via bitcoin-dev 
>> writes:
>> > Regarding modification 1, I agree with ZmnSCPxj that
>> > Decker-Wattenhofer is your next best option, given that eltoo is not
>> > yet available. But if you are going to use a kickoff transaction, keep
>> > in mind that every previous owner will have a copy of it. Because of
>> > this, you can't include a fee, and will instead need to have a second
>> > output for CPFP. This way a previous owner will at least have to pay
>> > the fee if they want to publish it. Note that it's still an
>> > improvement, because even if the kickoff transaction gets posted, it
>> > basically becomes no different than what it would have been, had you
>> > not used a kickoff transaction at all.
>>
>> It might be worth adopting the late fee binding we have in eltoo by
>> having the kickoff transaction input spending the funding tx signed with
>> sighash_single. This works because we only have 1 input and 1 output
>> that we really care about, and can allow others to attach fees at
>> will. That'd at least remove the need to guess the feerate days or
>> months in advance and thus having to overestimate.
>>
>> > Regarding modification 2, I like it a lot conceptually. It hadn't
>> > occurred to me before, and it's a clear security improvement. The only
>> > question is something Greg Sanders mentioned: whether it's enough to
>> > justify the added complexity of using 2P ECDSA. The alternative would
>> > be to simply use a regular 2-of-2 multisig (until Schnorr arrives,
>> > possibly).
>>
>> Wouldn't that result in a changing pubkey at each update, and thus
>> require an onchain move to be committed?
>>
>> > I'm looking forward to seeing statechains become a reality.
>>
>> That'd indeed be great :-)
>>
>> Cheers,
>> Christian
>> ___
>> 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] Statechain implementations

2020-03-26 Thread Ruben Somsen via bitcoin-dev
Hi Tom,

Nice to see you working on this.

Regarding modification 1, I agree with ZmnSCPxj that Decker-Wattenhofer is
your next best option, given that eltoo is not yet available. But if you
are going to use a kickoff transaction, keep in mind that every previous
owner will have a copy of it. Because of this, you can't include a fee, and
will instead need to have a second output for CPFP. This way a previous
owner will at least have to pay the fee if they want to publish it. Note
that it's still an improvement, because even if the kickoff transaction
gets posted, it basically becomes no different than what it would have
been, had you not used a kickoff transaction at all.

Regarding modification 2, I like it a lot conceptually. It hadn't occurred
to me before, and it's a clear security improvement. The only question is
something Greg Sanders mentioned: whether it's enough to justify the added
complexity of using 2P ECDSA. The alternative would be to simply use a
regular 2-of-2 multisig (until Schnorr arrives, possibly).

I'm looking forward to seeing statechains become a reality.

Cheers,
Ruben

On Thu, Mar 26, 2020 at 5:20 AM Albert via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi,
>
> Great to see some work in this direction, here's some thoughts on your
> keygen scheme:
>
> In the scenario where Owner1=Owner2, that is, one of the owners sends some
> coins to itself, that owner would get to know both x1*s1 and
> x2*s2=x2*s1*o2_inv*o1, and, because he already knows o1 and o2, that
> implies knowledge of both x1*s1 and x2*s1 where x1 and x2 are random
> numbers sampled from an uniform distribution. Once the owner has these two
> numbers, he can just sum these together to obtain s1*(x1+x2).
> Now, because of the central limit theorem, the distribution of x1+x2
> should approximate a normal one, concretely an Irwin–Hall distribution,
> with that approximation getting better when more numbers are collected
> through iterations of the protocol. Once you've collected enough numbers to
> approximate a normal well enough (looking at Irwin Hall distribution
> graphs^[1] you can observe that with less than 10 samples the distribution
> is already pretty similar to a normal one), it should be possible to
> drastically reduce the search space and apply brute force to guess the
> value of \sum x and, consequently, s1.
>
> Practically, it's possible that the search space is still too large for
> brute-force to be fruitful, so this attack might not work, but it shows
> that there is information leakage in every protocol iteration.
>
> On another note, if you are not already aware of, something which might be
> worth looking into is the possibility of further trust-minimising the SE
> role by forcing it's code to be run inside an AWS oracle or a hardware
> isolated processor such as SGX.
>
> Albert
>
> [1] https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution
>
> On Wed, Mar 25, 2020, at 9:52 PM, Tom Trevethan via bitcoin-dev wrote:
>
> Hi all,
>
> We are starting to work on an implementation of the statechains concept (
> https://medium.com/@RubenSomsen/statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39),
> with particular interest in using the protocol enable the change of
> ownership (novation) of an individual position in an active discreet log
> contract (DLC) without an on-chain transaction, and without needing the
> cooperation of the counterparty. The protocol as outlined by Ruben requires
> features not currently available in Bitcoin (like SIGHASH_NOINPUT), and it
> is uncertain when (or even if) this will be added. So we are looking at
> variants that would work with current Bitcoin functionality, and it would
> be good to get some feedback on them.
>
> There are two main modifications we are looking at:
> 1. Instead of an eltoo-based backup/refund transaction (enabling the
> current owner to claim the UTXO in case the statechain entity disappears)
> we propose using a decrementing nLocktime for backup transactions as the
> output changes hands. Here, the first owner gets a backup transaction with
> an nLocktime at some future height (h0), then the next owner gets a backup
> transaction with nLocktime (h0-c) where c is a confirmation window. This
> approach has the downside of limiting the lifetime of the UTXO, but it also
> doesn't require the current owner to be always online.
>
> 2. Replacing the 2-of-2 multisig output (paying to statechain entity SE
> key and transitory key) with a single P2(W)PKH output where the public key
> shared between the SE and the current owner. The SE and the current owner
> can then sign with a 2-of-2 ECDSA MPC. This enables each owner to generate
> their own private key share, and the SE changes their key share at each
> change of ownership (with the shared public key remaining the same). This
> works as follows (.G is EC point multiplication, * is scalar
> multiplication):
>
> KeyGen:
>
> a. Owner 1 generates private key share o1 

Re: [bitcoin-dev] Blind Merged Mining with covenants ( sighash_anyprevout / op_ctv )

2019-12-26 Thread Ruben Somsen via bitcoin-dev
Hello Nick,

Thank you for your interest.

It is quite different. Unlike MainStay, BMM isn't federation controlled.
It's a decentralized consensus mechanism that can function entirely without
a federation. BMM blocks are chosen by the highest bidder, which can be
anyone.

Note that it would be entirely possible for federations to issue two-way
pegged tokens on this decentralized chain, but keep in mind you'll have two
chains to worry about in terms of reorg potential (i.e. slow peg-outs).

Cheers,
Ruben

On Thu, Dec 26, 2019 at 1:32 PM Nick Gregory  wrote:

> This not similar to MainStay?
>
> https://commerceblock.readthedocs.io/en/latest/mainstay/index.html
>
> https://mainstay.xyz
>
>
> On Thu, Dec 26, 2019 at 2:25 AM Ruben Somsen via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Blind Merged Mining (BMM) is the idea of committing the hash of another
>> blockchain into a unique location on the Bitcoin blockchain, and paying a
>> Bitcoin fee to miners for the privilege of deciding this hash and capturing
>> the fees inside the other blockchain. Since miners don’t have to know what
>> the hash represents and are simply incentivized to choose the highest
>> bidder, it requires no extra validation on their part (“blind”). This idea
>> was originally conceived of by Paul Sztorc, but required a specific soft
>> fork. [0]
>>
>> In essence, BMM is a mechanism that allows external blockchains
>> (altcoins, tokens) to outsource their mining to the Bitcoin blockchain.
>> Instead of burning electricity with ASICs, they pay bitcoins to miners, who
>> in turn will perform Proof-of-Work (PoW) for the privilege of obtaining
>> this payment. This increases the total PoW on the Bitcoin blockchain, which
>> adds to the security of the Bitcoin network. It's an easy consensus
>> mechanism to implement, and simple to mine, only requiring full node
>> software for both chains and some bitcoins.
>>
>> While it may be hard to justify this as a soft fork, it turns out that
>> the inclusion of sighash_anyprevout (previously sighash_noinput) into
>> Bitcoin is sufficient to make BMM work, because, as noted by Anthony Towns
>> [1], sighash_anyprevout allows for the creation of op_checktemplateverify
>> (op_ctv, previously op_securethebag) style covenants [2]. With that, we can
>> generate the following without any trusted setup:
>>
>> - A long string of sighash_anyprevout transactions, each only spendable
>> by the next (the spending signature is placed in the output script, making
>> it a covenant)
>> - RBF enabled and signed with sighash flags single, anyonecanpay, and
>> anyprevout, allowing the addition of inputs and outputs in order to pay
>> fees (similar to fees in eltoo [3])
>> - A relative locktime of one block, ensuring only one transaction gets
>> mined per block
>>
>> A complete transaction flow diagram can be found here:
>>
>> https://gist.github.com/RubenSomsen/5e4be6d18e5fa526b17d8b34906b16a5#file-bmm-svg
>>
>> (Note that op_ctv instead of sighash_anyprevout would require the use of
>> CPFP, because all outputs need to be pre-defined.)
>>
>> This setup generates a unique location for the hash, which can be freely
>> competed for by anyone with the help of RBF. The hash can be committed into
>> the fee paying output via taproot. If the block corresponding to the hash
>> is not revealed or invalid, then the BMM block simply gets orphaned, just
>> like in Sztorc’s proposal.
>>
>> While the Bitcoin blockchain will be unaware of the BMM chain, the
>> opposite does not have to be true. This enables some interesting
>> possibilities. For instance, you could make a conditional BMM token
>> transfer that only goes through if a specific Bitcoin transaction occurs
>> within a certain period of time, thus enabling atomic swaps (especially
>> useful when combined with asset issuance/colored coins/pegged tokens). It
>> would also be possible to create contracts based on Bitcoin’s hashrate and
>> such.
>>
>> It seems inevitable that this chain will need some kind of native token
>> in order to pay for fees. This makes me uneasy. The fairest and least
>> speculation-inducing method I can think of is a perpetual one-way peg,
>> where at any time 1 BTC can be burned for 1 token, essentially preserving
>> the 21M coin limit. Coins that are burned will never return, benefiting all
>> BTC holders equally. Holding BTC will always be preferable, because the
>> option to move is always open to you. This should disincentivize
>> speculation -- it only makes sense to move coins if they serve an immediate
>

[bitcoin-dev] Blind Merged Mining with covenants ( sighash_anyprevout / op_ctv )

2019-12-25 Thread Ruben Somsen via bitcoin-dev
Blind Merged Mining (BMM) is the idea of committing the hash of another
blockchain into a unique location on the Bitcoin blockchain, and paying a
Bitcoin fee to miners for the privilege of deciding this hash and capturing
the fees inside the other blockchain. Since miners don’t have to know what
the hash represents and are simply incentivized to choose the highest
bidder, it requires no extra validation on their part (“blind”). This idea
was originally conceived of by Paul Sztorc, but required a specific soft
fork. [0]

In essence, BMM is a mechanism that allows external blockchains (altcoins,
tokens) to outsource their mining to the Bitcoin blockchain. Instead of
burning electricity with ASICs, they pay bitcoins to miners, who in turn
will perform Proof-of-Work (PoW) for the privilege of obtaining this
payment. This increases the total PoW on the Bitcoin blockchain, which adds
to the security of the Bitcoin network. It's an easy consensus mechanism to
implement, and simple to mine, only requiring full node software for both
chains and some bitcoins.

While it may be hard to justify this as a soft fork, it turns out that the
inclusion of sighash_anyprevout (previously sighash_noinput) into Bitcoin
is sufficient to make BMM work, because, as noted by Anthony Towns [1],
sighash_anyprevout allows for the creation of op_checktemplateverify
(op_ctv, previously op_securethebag) style covenants [2]. With that, we can
generate the following without any trusted setup:

- A long string of sighash_anyprevout transactions, each only spendable by
the next (the spending signature is placed in the output script, making it
a covenant)
- RBF enabled and signed with sighash flags single, anyonecanpay, and
anyprevout, allowing the addition of inputs and outputs in order to pay
fees (similar to fees in eltoo [3])
- A relative locktime of one block, ensuring only one transaction gets
mined per block

A complete transaction flow diagram can be found here:
https://gist.github.com/RubenSomsen/5e4be6d18e5fa526b17d8b34906b16a5#file-bmm-svg

(Note that op_ctv instead of sighash_anyprevout would require the use of
CPFP, because all outputs need to be pre-defined.)

This setup generates a unique location for the hash, which can be freely
competed for by anyone with the help of RBF. The hash can be committed into
the fee paying output via taproot. If the block corresponding to the hash
is not revealed or invalid, then the BMM block simply gets orphaned, just
like in Sztorc’s proposal.

While the Bitcoin blockchain will be unaware of the BMM chain, the opposite
does not have to be true. This enables some interesting possibilities. For
instance, you could make a conditional BMM token transfer that only goes
through if a specific Bitcoin transaction occurs within a certain period of
time, thus enabling atomic swaps (especially useful when combined with
asset issuance/colored coins/pegged tokens). It would also be possible to
create contracts based on Bitcoin’s hashrate and such.

It seems inevitable that this chain will need some kind of native token in
order to pay for fees. This makes me uneasy. The fairest and least
speculation-inducing method I can think of is a perpetual one-way peg,
where at any time 1 BTC can be burned for 1 token, essentially preserving
the 21M coin limit. Coins that are burned will never return, benefiting all
BTC holders equally. Holding BTC will always be preferable, because the
option to move is always open to you. This should disincentivize
speculation -- it only makes sense to move coins if they serve an immediate
purpose.

Given the lack of a block subsidy, there may not be enough impetus to move
the chain forward instead of enacting a reorg. However, BMM reorgs are
somewhat unique in that they will have to compete for the same unique
location that the original chain is using. A 10-block reorg would take 100
minutes on average to catch up, during which the original chain won’t move
forward. If fee pressure of new transactions is targeted exclusively
towards the original chain during this time [4], there would be forward
pressure that makes reorgs more expensive. Whether this mitigation is
sufficient is an open question.

Finally, it is worth asking whether BMM interferes too much with the
existing incentive structure of Bitcoin. I don’t have a clear answer, but
it should be noted that a much more inefficient version of BMM is already
possible today. One could simply use up lots of block space instead of
specifying a unique location for the hash, as demonstrated by Veriblock
[5]. I therefore believe that the same argument as adding data via
op_return applies here -- if it’s not supported, more wasteful methods may
be utilized instead.

Some technical details (thanks to Anthony Towns for providing his insights):

- Since the exact signature is committed to ahead of time, private key
security is actually irrelevant. You can simply use G to replace both R and
P instead of the usual s = r + e*p. This means 

Re: [bitcoin-dev] PoW fraud proofs without a soft fork

2019-09-10 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>I suppose the critical difference is that invalid inflation can fool the SPV 
>node, the fullnode will not be so fooled.

That is correct. If you sybil the SPV node, you can break any
consensus rule you like. I believe this is inherent to fraud proofs in
general, because you skip consensus checks unless you're able to
receive a fraud proof.

But note that my goal in the comparison was to assert that there is no
security difference between committing or not committing the utreexo
hash into a block. The attack your describe works in either situation,
so my conclusion remains that committing the hash adds no security.

Other weaknesses compared to full nodes are:
- the SPV nodes rely on the existence of a healthy network of utreexo
supporting full nodes
- at least one honest block needs to be mined
- consensus slows down, because you need to allow time for an honest
minority to produce a block

Cheers,
Ruben

On Mon, Sep 9, 2019 at 8:58 AM ZmnSCPxj  wrote:
>
> Good morning Ruben,
>
> Yes, I suppose that is correct.
>
> I suppose the critical difference is that invalid inflation can fool the SPV 
> node, the fullnode will not be so fooled.
>
> A somewhat larger-scale attack is to force a miner-supported 
> miner-subsidy-increase / blocksize-increase hard fork.
> If enough such SPV nodes can be sybilled, they can be forced to use the hard 
> fork, which might incentivize them to support the hard fork rather than 
> back-compatible consensus chain.
>
> Regards,
> ZmnSCPxj
>
> > Hi ZmnSCPxj,
> >
> > Thank you for your comments. You raise an important point that I should 
> > clarify.
> >
> > > 1.  In event of a sybil attack, a fullnode will stall and think the 
> > > blockchain has no more miners.
> >
> > You can still attack the full node by feeding it a minority PoW chain,
> > then it won't stall.
> >
> > > 2.  In event of a sybil attack, an SPV, even using this style, will 
> > > follow the false blockchain.
> >
> > Correct, but this false blockchain does need to have valid PoW.
> >
> > So in both cases valid PoW is required to fool nodes. The one
> > difference is that for a full node, the blocks themselves also need to
> > be valid (except for the fact that they are in a minority chain), but
> > the end result is still that a victim can be successfully double spent
> > and lose money.
> >
> > I hope this clarifies why I consider the security for these two
> > situations to be roughly equivalent. In either situation, victims can
> > be fooled into accepting invalid payments.
> >
> > Cheers,
> > Ruben
> >
> > On Mon, Sep 9, 2019 at 6:14 AM ZmnSCPxj zmnsc...@protonmail.com wrote:
> >
> > > Good morning Ruben,
> > >
> > > > One might intuitively feel that the lack of a commitment is unsafe,
> > > > but there seems to be no impact on security (only bandwidth). The 
> > > > only
> > > > way you can be fooled is if all peers lie to you (Sybil), causing 
> > > > you
> > > > to follow a malicious minority chain. But even full nodes (or the
> > > > committed version of PoW fraud proofs) can be fooled in this way if
> > > > they are denied access to the valid most PoW chain. If there are
> > > > additional security concerns I overlooked, I’d love to hear them.
> > > >
> > >
> > > I think it would be better to more precisely say that:
> > >
> > > 1.  In event of a sybil attack, a fullnode will stall and think the 
> > > blockchain has no more miners.
> > > 2.  In event of a sybil attack, an SPV, even using this style, will 
> > > follow the false blockchain.
> > >
> > > This has some differences when considering automated systems.
> > > Onchain automated payment processing systems, which use a fullnode, will 
> > > refuse to acknowledge any incoming payments.
> > > This will lead to noisy complaints from clients of the automated payment 
> > > processor, but this is a good thing since it warns the automated payment 
> > > processor of the possibility of this attack occurring on them.
> > > The use of a timeout wherein if the fullnode is unable to see a new block 
> > > for, say, 6 hours, could be done, to warn higher-layer management systems 
> > > to pay attention.
> > > While it is sometimes the case that the real network will be unable to 
> > > find a new block for hours at a time, this warning can be used to confirm 
> > > if such an event is occurring, rather than a sybil attack targeting that 
> > > fullnode.
> > > On the other hand, such a payment processing system, which uses an SPV 
> > > with PoW fraud proofs, will be able to at least see incoming payments, 
> > > and continue to release product in exchange for payment.
> > > Yet this is precisely a point of attack, where the automated payment 
> > > processing system is sybilled and then false payments are given to the 
> > > payment processor on the attack chain, which are double-spent on the 
> > > global consensus chain.
> > > And the automated system may very well not be able to notice this.
> > > Regards,
> > 

[bitcoin-dev] PoW fraud proofs without a soft fork

2019-09-07 Thread Ruben Somsen via bitcoin-dev
After looking more deeply into Tadge Dryja’s utreexo work [0], it has
become clear to me that this opens up a way to implement PoW fraud
proofs [1] without a soft fork. With utreexo, we can efficiently
verify state transitions between blocks. Verifying a block from a
valid utreexo hash requires only about a megabyte worth of merkle
proofs.

PoW fraud proofs assume that block N is valid if no miner has tried to
fork it (read my original post for details [1]). We can extend that
assumption to the utreexo hash of block N, and use that to verify fork
block N+1, and reject it if the block is invalid, with just 2-3MB of
data.

For simplicity, I’ll first start by explaining a version with
commitments (which would require a soft fork).

When a fork (i.e. a PoW fraud proof) occurs at height N+1, indicating
that the block might be invalid, you’d need to download:

1. block N+1 from the most PoW chain (~1-2MB)
2. the utreexo hash commitment inside of block N (e.g. a merkle path
to the coinbase)
3. the utreexo merkle proofs which prove that all inputs of N+1 are
part of the UTXO set (~1MB)

Of course step 2 requires a soft fork, but we can also do a
non-committed version by relying on the assumption that at least one
of your peers is honest and then evaluate disagreements.

We simply replace step 2 above with the following:
2. [Download] the utreexo hash of block N from all your peers

If it turns out that one of your peers disagrees on what the correct
hash is, you find the last utreexo hash where that peer still agreed,
let’s say block M, and you simply execute the same three steps to find
out which peer is wrong: download block M+1, then get the merkle
proofs to verify whether the peer correctly transitioned their utreexo
hash from M to M+1.

One might intuitively feel that the lack of a commitment is unsafe,
but there seems to be no impact on security (only bandwidth). The only
way you can be fooled is if all peers lie to you (Sybil), causing you
to follow a malicious minority chain. But even full nodes (or the
committed version of PoW fraud proofs) can be fooled in this way if
they are denied access to the valid most PoW chain. If there are
additional security concerns I overlooked, I’d love to hear them.

In short, utreexo can enable PoW fraud proofs without a soft fork. At
the cost of downloading a couple of MB per stale block (and per
malicious peer), an SPV client gains the ability to (eventually)
reject the most PoW chain as long as one honest block gets mined,
thereby increasing its security beyond 51% honest miners.

Finally, while I think this goes without saying, I’d like to reiterate
that this is by no means a replacement for running a full node. You’re
depending on other full nodes to do full verification and assuming at
least some of the miners are honest. If everyone did this, Bitcoin
would not be secure.

-- Ruben Somsen


[0] Utreexo paper: https://eprint.iacr.org/2019/611.pdf

[1] Improving SPV security with PoW fraud proofs:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-April/016873.html
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Formalizing Blind Statechains as a minimalistic blind signing server

2019-06-14 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,


>Basically, the "Stale Factory" and "Broken Factory" problems.

I see, I'll have to read up on those.


>Combining it via MuSig is probably best, as the server is now unable to 
>recognize even the pubkey (assuming it never is informed `X`).

Yes, that's the current thinking. See also:
https://twitter.com/SomsenRuben/status/1138199578996555784 (sorry no
time to make a gist)


>As the server is blinded, it cannot determine anything about the message being 
>signed.

Yes, you could build a non-blind variant with scripting, but that
would be quite different.


>a simple scripting that allows "if somebody provides x of H(x) plus signature 
>A, sign a blinded message M1, else if after 2:30PM PST on Jun 24 2019 if 
>somebody provides signature of B, sign a blinded message M2" could still 
>potentially be useful

I believe adaptor signatures are enough to replace hashing. A time
lock could potentially be added with some very basic scripting, but my
feeling is still that this is better avoided. We're essentially
relying on the Bitcoin blockchain for that, because the off-chain
transactions can be encumbered by any script you like.


>anything that can be done with a UTXO onchain, can also be done offchain via 
>any updateable offchain cryptocurrency system

You're right that I didn't properly point to the key difference, which
is transfer of UTXO ownership. Other off-chain systems don't allow you
to go from e.g. 2-of-2 to 3-of-3, but of course we're adding a
federation in order to make this happen, so it's not exactly a fair
comparison.


>(I should probably look up the authors of the Statechains paper to make my 
>naming convention consistent)

That would be "Somsen". I am the sole author.


>By presenting those "further transactions" to the offchain system, we can 
>provide an argument that the offchain system can just "append" those "further 
>transactions" to the existing unilateral-case transactions, then cut-through 
>the further transactions on its next update

That's an interesting way of looking at it. This is currently achieved
in Statechains by making the top-level on the Statechain N-of-N, so
all participants of the "further transactions" have to agree in order
to achieve full cut-through on the Statechain. In practice this would
mean that the final signature requested from the server is a
"cooperative close".


Cheers,
Ruben


On Thu, Jun 13, 2019 at 3:22 AM ZmnSCPxj  wrote:
>
> Good morning Ruben,
> > > an early draft
> >
> > I meant an early draft of Statechains, sorry if that was confusing.
> > But yes, it's essentially no different from channel factories without
> > eltoo.
>
> Sorry, I am referring to current issues with channel factories, which were 
> not addressed in the original channel factories paper.
> Basically, the "Stale Factory" and "Broken Factory" problems.
> Broken factory seems unsolvable.
> Stale factory is fixable if the channels within the factory use 
> `SIGHASH_NOINPUT` (assuming it gets into Bitcoin) for all unilateral paths 
> (use `SIGHASH_ALL` for cooperative paths).
>
> >
> > > If `SIGHASH_ANYPREVOUT` ends up requiring a chaperone signature, it seems 
> > > this transitory/common key can be used for the chaperone.
> >
> > That is a good point. One thing I have not yet fully analysed are the
> > privacy considerations. Perhaps we don't want to reveal X on-chain.
>
> On reflection, probably best not to.
> It requires a script that reveals the pubkeys.
> And it now becomes possible for the server to monitor the blockchain for 
> revelation of server pubkey in a spend path.
> This will let the server know, after-the-fact, that it was signing blockchain 
> transactions.
> This might not let it preemptively censor or otherwise disrupt, but it 
> *could* sell the private fact that a statechain was used.
> Combining it via MuSig is probably best, as the server is now unable to 
> recognize even the pubkey (assuming it never is informed `X`).
>
> >
> > > This would be nearer to my own Smart Contracts Unchained
> >
> > Adding scripting is not my preferred approach. The beauty of the
> > system is that the server doesn't evaluate any scripts whatsoever.
>
> On reflection, this is probably best.
> As the server is blinded, it cannot determine anything about the message 
> being signed.
>
> On the other cognition sub-agent, however, a simple scripting that allows "if 
> somebody provides x of H(x) plus signature A, sign a blinded message M1, else 
> if after 2:30PM PST on Jun 24 2019 if somebody provides signature of B, sign 
> a blinded message M2" could still potentially be useful, and might allow 
> "programmable escrow" like I imagine Smart Contracts Unchained could allow.
>
> >
> > That being said, Smart Contracts Unchained (SCU) can be inserted quite
> > elegantly as a separate smart contracting layer.
> >
> > The observation is that anything that can be done with a UTXO
> > on-chain, can also be done off-chain via Statechains, including SCU.
>
> The Real (TM) 

Re: [bitcoin-dev] Formalizing Blind Statechains as a minimalistic blind signing server

2019-06-12 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,


Thanks for the reply. Sorry to keep you waiting, Coredev and Breaking
Bitcoin have been keeping me busy.

Transcript from Coredev (thanks Bryan):
http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2019-06-07-statechains/

Blind Statechains at Breaking Bitcoin:
https://www.youtube.com/watch?v=DqhxPWsJFZE=4h59m4s


>an early draft

I meant an early draft of Statechains, sorry if that was confusing.
But yes, it's essentially no different from channel factories without
eltoo.


>If `SIGHASH_ANYPREVOUT` ends up requiring a chaperone signature, it seems this 
>transitory/common key can be used for the chaperone.

That is a good point. One thing I have not yet fully analysed are the
privacy considerations. Perhaps we don't want to reveal X on-chain.


>This would be nearer to my own Smart Contracts Unchained

Adding scripting is not my preferred approach. The beauty of the
system is that the server doesn't evaluate any scripts whatsoever.

That being said, Smart Contracts Unchained (SCU) can be inserted quite
elegantly as a separate smart contracting layer.

The observation is that anything that can be done with a UTXO
on-chain, can also be done off-chain via Statechains, including SCU.

If SCU is a single (N-of-N or (1-of-N + escrow)) key, you can simply
use this as the userKey (as well as inside the off-chain eltoo tx).

It's pretty interesting how smart contracting can be added like this.
Cool stuff, ZmnSCPxj. I'll definitely be thinking about this more.


Cheers,
Ruben

On Thu, Jun 6, 2019 at 8:32 AM ZmnSCPxj  wrote:
>
> Good morning Ruben,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On Thursday, June 6, 2019 1:20 PM, Ruben Somsen  wrote:
>
> > Hi ZmnSCPxj,
> >
> > Thank you for your comments.
> >
> > > Of note, is that a Decker-Russell-Osuntokun construction ("eltoo") is not 
> > > strictly required. We can still make use of the Decker-Wattenhofer 
> > > construction instead.
> >
> > Yes, an early draft (from before the eltoo paper) was using that
> > construction, but it seemed quite unwieldy. Timelocks have to be long,
> > nesting adds more transactions, channels expire faster with more use,
> > and tx fee handling is more complex. But you make a good point that if
> > SIGHASH_ANYPREVOUT turns out to be too controversial (or for
> > supporting older altcoins), this would be a potential fallback.
>
> The lack of `SIGHASH_ANYPREVOUT` does make it difficult to operate a channel 
> factory.
> Factory operations would still require the signatures of all participants, 
> but once a participant has released its signature, it cannot be sure whether 
> its channels should be rooted on the previous factory state or the next (i.e. 
> the [Stale Factory 
> problem](https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-April/001974.html)
>  ).
> This is fixable if we use `SIGHASH_ANYPREVOUT` on channel update transactions.
> Alternately without that flag we can run channels rooted on both the previous 
> and next factory states, which actually is similar to what we need to do for 
> splice-in (so we could reuse that code, possibly).
>
> >
> > > This still admits the possibility of an exit scam once a few "big enough" 
> > > swaps are in position to be stolen, trading off earned reputation for 
> > > cold-stored cash.
> >
> > That is correct. The worst case for security still comes down to
> > having to trust the federation, but the transitory key, as well as the
> > blind signature scheme, does add an interesting layer of separation
> > that makes it essentially "non-custodial". The article I linked has
> > more on this.
>
> Of note is that this is roughly the same as the common key in my own Smart 
> Contracts Unchained.
>
> If `SIGHASH_ANYPREVOUT` ends up requiring a chaperone signature, it seems 
> this transitory/common key can be used for the chaperone.
>
> Going further on Smart Contracts Unchained, I observe that the below:
>
> > // Start new signature chain
> > (1) requestNewKey(userPubkey) => returns a new serverPubkey and registers 
> > it to userPubkey
> > // Extend existing chain
> > (2) requestBlindSig(userSignature, blindedMessage, nextUserPubkey) => 
> > returns blindSignature, registers the serverPubkey to nextUserPubkey
>
> Can be generalized, such that instead of pubKeys and their signatures, we 
> have validation programs and their witnesses.
>
> For example, instead of userPubkey and nextUserPubkey we have a userScript 
> and nextUserScript, with userSignature replaced by a userWitness.
>
> This would be nearer to my own Smart Contracts Unchained, though without 
> committing to the smart contract onchain, only offchain in the server.
>
>
>
> >
> > Cheers,
> > Ruben
> >
> > On Thu, Jun 6, 2019 at 2:09 AM ZmnSCPxj zmnsc...@protonmail.com wrote:
> >
> > > Good morning Ruben,
> > >
> > > > At
> > > > Scaling Bitcoin ‘18 [1] I briefly mentioned utilizing blind signatures
> > > > [2] to make the entity unaware of what it's signing. I now 

Re: [bitcoin-dev] Formalizing Blind Statechains as a minimalistic blind signing server

2019-06-06 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

Thank you for your comments.

>Of note, is that a Decker-Russell-Osuntokun construction ("eltoo") is not 
>*strictly* required. We can still make use of the Decker-Wattenhofer 
>construction instead.

Yes, an early draft (from before the eltoo paper) was using that
construction, but it seemed quite unwieldy. Timelocks have to be long,
nesting adds more transactions, channels expire faster with more use,
and tx fee handling is more complex. But you make a good point that if
SIGHASH_ANYPREVOUT turns out to be too controversial (or for
supporting older altcoins), this would be a potential fallback.

>This still admits the possibility of an exit scam once a few "big enough" 
>swaps are in position to be stolen, trading off earned reputation for 
>cold-stored cash.

That is correct. The worst case for security still comes down to
having to trust the federation, but the transitory key, as well as the
blind signature scheme, does add an interesting layer of separation
that makes it essentially "non-custodial". The article I linked has
more on this.

Cheers,
Ruben

On Thu, Jun 6, 2019 at 2:09 AM ZmnSCPxj  wrote:
>
> Good morning Ruben,
>
> > At
> > Scaling Bitcoin ‘18 [1] I briefly mentioned utilizing blind signatures
> > [2] to make the entity unaware of what it's signing. I now think this
> > is the more interesting approach. The functionality can be described
> > fairly elegantly as follows.
>
> I agree.
> I had no interest in Statechains at all before, but now that you have blind 
> signing servers, this is significantly more interesting.
>
>
> >
> > Blind signing server with two functions users can call:
> >
> > // Start new signature chain
> > (1) requestNewKey(userPubkey) => returns a new serverPubkey and
> > registers it to userPubkey
> >
> > // Extend existing chain
> > (2) requestBlindSig(userSignature, blindedMessage, nextUserPubkey) =>
> > returns blindSignature, registers the serverPubkey to nextUserPubkey
> >
> > The resulting output is a public ECC chain (one blindSignature per
> > user, one chain per serverPubkey) of blindly signed messages,
> > requested by users (1, 2, 3, etc.):
> >
> > userSignature1(blindedMessage1, userPubkey2) => blindSignature1
> > userSignature2(blindedMessage2, userPubkey3) => blindSignature2
> > etc.
> >
> > Assuming the server is honest (more on this below), we can use it to
> > transfer over the signing rights of a private key without actually
> > changing the key itself.
> >
> > The functionality is general and therefore suitable for more than just
> > Bitcoin, but let's walk through the primary envisioned use case where
> > we transfer the ownership of a Bitcoin UTXO off-chain. Note that the
> > server is kept completely unaware that it's handling a BTC
> > transaction, since it's signing blindly:
> >
> > -   B uses function (1) with userPubkey = B to request serverPubkey A
> > -   B then generates transitory key X, and creates a single MuSig key AX
> > (key X is called “transitory” because its private key will later be 
> > passed on)
> >
> > -   B prepares tx1: 1BTC to AX (he doesn't send it yet)
> > -   B creates tx2: an eltoo tx [3] that assigns the 1BTC back to B 
> > (off-chain)
>
> Of note, is that a Decker-Russell-Osuntokun construction ("eltoo") is not 
> *strictly* required.
> We can still make use of the Decker-Wattenhofer construction instead.
>
> The core of Decker-Wattenhofer is a sequence of decrementing-`nSequence` 
> update systems.
> Number of maximum updates is limited by the starting `nSequence`, however if 
> we put an update system inside an update system, we can "reset" the 
> `nSequence` of the inner update system by updating the outer update system.
> We can chain this concept further and add more update systems nested inside 
> update systems to gain more leverage from the maximum relative wait time.
>
> As we expect fewer updates are needed for statechains than e.g. actual 
> Lightning channels (your given CoinSwap protocol is "only" two updates, for 
> instance) this is usually a good tradeoff,
>
> It is thus possible to use statechains in case `SIGHASH_ANYPREVOUT` is too 
> controversial to get into Bitcoin, provided Schnorr (definitely 
> uncontroversial) does get into Bitcoin.
>
> > A and B can collude to take the money from C, but since all instances
> > of userSignature and blindSignature are published openly, cheating is
> > publicly detectable (e.g. the server signed two messages from B
> > instead of one).
>
> This still admits the possibility of an exit scam once a few "big enough" 
> swaps are in position to be stolen, trading off earned reputation for 
> cold-stored cash.
>
> >
> > Trust can be distributed by turning the server into a multisig
> > threshold key, so serverPubkey A becomes e.g. 8-of-12 multisig. This
> > means security can be on par with federated sidechains [5], and is
> > similar to how ZmnSCPxj replaced the escrow key with a federation in
> > “Smart 

[bitcoin-dev] Formalizing Blind Statechains as a minimalistic blind signing server

2019-06-04 Thread Ruben Somsen via bitcoin-dev
Hi everyone,

For those who are unfamiliar, Statechains enable the transfer UTXOs
off-chain with the help of a Statechain entity (trusted server(s))
without giving them full custodial control over your coins [0]. At
Scaling Bitcoin ‘18 [1] I briefly mentioned utilizing blind signatures
[2] to make the entity unaware of what it's signing. I now think this
is the more interesting approach. The functionality can be described
fairly elegantly as follows.

Blind signing server with two functions users can call:

// Start new signature chain
(1) requestNewKey(userPubkey) => returns a new serverPubkey and
registers it to userPubkey

// Extend existing chain
(2) requestBlindSig(userSignature, blindedMessage, nextUserPubkey) =>
returns blindSignature, registers the serverPubkey to nextUserPubkey

The resulting output is a public ECC chain (one blindSignature per
user, one chain per serverPubkey) of blindly signed messages,
requested by users (1, 2, 3, etc.):

userSignature1(blindedMessage1, userPubkey2) => blindSignature1
userSignature2(blindedMessage2, userPubkey3) => blindSignature2
etc.

Assuming the server is honest (more on this below), we can use it to
transfer over the signing rights of a private key without actually
changing the key itself.

The functionality is general and therefore suitable for more than just
Bitcoin, but let's walk through the primary envisioned use case where
we transfer the ownership of a Bitcoin UTXO off-chain. Note that the
server is kept completely unaware that it's handling a BTC
transaction, since it's signing blindly:

- B uses function (1) with userPubkey = B to request serverPubkey A
- B then generates transitory key X, and creates a single MuSig key AX
(key X is called “transitory” because its private key will later be passed on)
- B prepares tx1: 1BTC to AX (he doesn't send it yet)
- B creates tx2: an eltoo tx [3] that assigns the 1BTC back to B (off-chain)
- B uses (2) with nextUserPubkey = B and blindedMessage = tx2
- B sends tx1 to the blockchain and waits for it to confirm
- B receives a key from C in order to prepare a payment
- B creates tx3: an eltoo tx (with higher priority) with 1BTC to C (off-chain)
- B uses (2) with nextUserPubkey = C and blindedMessage = tx3
- B passes the private key of X (the transitory key) on to C
- C takes blinded tx2 and tx3 from the public server output and
unblinds them with X
- C only accepts the payment if everything is in order [4]

Even if the server goes offline, C can still get the money by sending
tx3 to the blockchain.

A and B can collude to take the money from C, but since all instances
of userSignature and blindSignature are published openly, cheating is
publicly detectable (e.g. the server signed two messages from B
instead of one).

Trust can be distributed by turning the server into a multisig
threshold key, so serverPubkey A becomes e.g. 8-of-12 multisig. This
means security can be on par with federated sidechains [5], and is
similar to how ZmnSCPxj replaced the escrow key with a federation in
“Smart Contracts Unchained” [6].

Lastly, by utilizing adaptor signatures [7], the userSignature can be
tied to the blindSignature. In fact, this can be done for any number
of signatures, allowing multiple signing sessions to take place
atomically [8]. This denies the server the ability to selectively
publish one signature and not the other, allowing safe atomic swaps
via the server.

Essentially, anything that requires UTXO ownership can be achieved
off-chain via Blind Statechains. Coinjoin, Lightning channel
opening/adjusting/closing, Discreet Log Contract style bets [9],
cross-chain atomic swaps, etc. Since the blind signing server
functionality is non-specific to Bitcoin, it'll be useful for
non-cryptocurrency related use cases as well, but I have not given
this a lot of thought.

I also recently published a more high-level overview of Statechains
here, which may be of interest:
https://medium.com/@RubenSomsen/statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39

-- Ruben Somsen



[0] Statechains paper:
https://github.com/RubenSomsen/rubensomsen.github.io/blob/master/img/statechains.pdf

[1] Statechains Scaling Bitcoin ‘18: http://youtu.be/FI9cwksTrQs?t=47m36s
Transcript:
http://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/statechains/

[2] Blind signatures, Jonas Nick:
http://diyhpl.us/wiki/transcripts/building-on-bitcoin/2018/blind-signatures-and-scriptless-scripts/

[3] eltoo: https://blockstream.com/eltoo.pdf

[4] Similar to client-side validation, Peter Todd:
https://diyhpl.us/wiki/transcripts/scalingbitcoin/milan/client-side-validation/

[5] Sidechains Appendix A, federated peg: https://blockstream.com/sidechains.pdf

[6] Smart Contracts Unchained ,ZmnSCPxj:
https://zmnscpxj.github.io/bitcoin/unchained.html

[7] Adaptor signatures, Andrew Poelstra:
http://diyhpl.us/wiki/transcripts/layer2-summit/2018/scriptless-scripts/

[8] Adam Gibson (Waxwing) separately made a similar observation on his
blog: 

Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs

2019-04-22 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,


Allow me to reply to your post in mixed order (fraud proofs first):


>But peers can be set up to allow you to hear of all chains while denying you 
>proof of the invalidity of some UTXO.

I don't believe this is fundamentally different. In either scenario
you end up on the wrong chain if all your peers are lying to you. One
happens by omission of a fraud proof, while the other happens by
omission of a valid longest chain.


>This is precisely the "data unavailability claim" that shot down the previous 
>fraud proofs

The "data unavailability" issue I was referring to, and which I
believe is the reason why fraud proofs were abandoned, is the
following:

- Alice downloads a block with her full node, but the block is
incomplete (e.g. a transaction is missing).
- Alice reports this to Bob's SPV fraud proof client, who verifies
this by requesting the transaction from the network.
- If Bob can't download it, he rejects the block.
- If Bob can download it, either Alice was malicious, or a miner was
temporarily withholding the data.
- Since Bob can't be certain Alice was being malicious, Bob can't ban
her, which results in a DoS vector where SPV fraud proof clients can
be forced to download all blocks.

We circumvent the data unavailability problem here completely, since
we are only questioning the validity of blocks which are involved in a
fork (expensive and/or rare), and we are simply always downloading
them in full.

If my arguments above hold up, we can use fraud proof commitments as
described in segwit BIP141 [0] instead of UTXO set commitments, which
seems like the more elegant way to achieve the desired outcome.


>Perhaps in combination with BIP157/158 it may be possible, if the filters 
>contain UTXO spends and a BIP158 filter was committed to on-chain. Then a 
>proof of absence could be done by revealing all the BIP158 filters from the 
>UTXO creation to the block being validated, as well as the blocks whose BIP158 
>filters matched the UTXO and revealing that no, they actually do not spend the 
>UTXO.

Yes, I mentioned something similar to Laolu, but it does seem
computationally expensive to run every input in a block through the
filter of every past block. The fact that BIP157/158 can function
without commitments is also why I suspected we may not necessarily
need UTXO set commitments.


>UTXO sets can only be validated by actually running the entire blockchain, 
>i.e. fullnoding.

It seems to me you can validate uncommitted UTXO sets by comparing
them. Download and compare UTXO set hashes from multiple peers. If
they disagree on a certain block, download that block and the relevant
merkle path(s) from the previous block's UTXO set, and then verify who
is right. Ban the peer who lied. Note that unlike fraud proofs, it is
not possible to lie by omission, but it does assume one of your peers
is honest. Of course this does nothing to dispute your earlier point
that this may not be all that efficient (e.g. full nodes keeping
merkle paths of all prior states).


>What BIP157 does is summarize data that is within a block, thus validating 
>them can be done simply by downloading the block in question.
>UTXO sets summarize data in the entire blockchain, hence proper validation 
>requires downloading the entire blockchain.
Thus it cannot be a comparison point.

It's still possible to lie by omission. Let's say a miner spends some
coins in block N, and spends the exact same coins again in block N+1,
making block N+1 invalid. If the filter for block N is maliciously
constructed, you won't notice the spend in block N, causing you to
think block N+1 is valid. In short, you're still relying on one of
your peers to give you a correct filter. If all your peers lie, you
can always be deceived.


>Tangentially, we cannot just magically commit to anything on the blockchain. 
>[...] if you are adding new information to be committed, that may increase the 
>resource usage of fullnodes. [...] This is probably still better than BIP37 
>but we should still be aware the additional load on fullnodes.

I agree with all this.


To summarize, this is my current understanding of our options for
enabling light clients to verify a single block in isolation:
1. UTXO set commitments (complex, more resource usage to full nodes)
2. BIP157/158 commitments (expensive for clients to check all filters
to get exclusion proofs)
3. BIP141 fraud proof commitments (assumes fraud proofs will be passed
on to the SPV client)

The debate is still open on whether the options above can be done
without actually committing them into blocks via a soft fork. My
current hunch is "yes" for 1 and 2, and "no" for 3, which would be
unfortunate, because 3 currently seems to me like the more elegant
solution.


-- Ruben Somsen


[0] 
https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#Compact_fraud_proof_for_SPV_nodes


>UTXO sets can only be validated by actually running the entire blockchain, 
>i.e. fullnoding.
>What BIP157 does is 

Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs

2019-04-20 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj,

>There is no safe way to use UTXO sets without identifying who is telling you 
>those sets are valid, or making it expensive to lie
>The first option requires trust and is weaker than SPV, the second requires 
>committing to a proof-of-work

Olaoluwa Osuntokun's BIP157 manages to function without a commitment:
"If the client receives conflicting filter headers from different
peers for any block and filter type, it SHOULD interrogate them to
determine which is faulty."

I am wondering if the same logic can be applied to UTXO sets or the
fraud proofs I just described.

>This makes no sense
>or you trust that every peer you have is not omitting the proof.

It's the latter, you trust every peer you have is not omitting the
proof. It requires one honest peer. The reason this is acceptable is
because you're already making that assumption. If none of your peers
are honest, you have no guarantee of hearing about the chain with the
most PoW.

Again, this is not a new observation. I am just recalling the fraud
proof debate from when it was being considered for segwit (though of
course it's possible I got some details wrong).

-- Ruben Somsen

On Sat, Apr 20, 2019 at 3:59 AM ZmnSCPxj  wrote:
>
> Good morning,
>
>
> > > As I understand it, this requires that UTXO commitments be mandatory.
> >
> > Perhaps UTXO sets can be made useful without committing them. I have
> > some very loose thoughts on the subject, I consider it an open
> > question.
>
> There is no safe way to use UTXO sets without identifying who is telling you 
> those sets are valid, or making it expensive to lie.
> The first option requires trust and is weaker than SPV, the second requires 
> committing to a proof-of-work (and probably best to fold it into the Bitcoin 
> blockchain if so).
>
> You would get the UTXO commitment from the previous block (if the UTXO 
> commitment is in the coinbase, then all you need is the Merkle proof of the 
> coinbase).
>
>
> >
> > > More difficult is: how can an SPV node acquire the UTXO set at a 
> > > particular block?
> >
> > I think you are asking fair questions about how the UTXO set
> > commitments would work in practice, and how viable that makes it. I'm
> > not sure. The most comprehensive work I have seen on this topic has
> > been the utreexo proposal by Tadge Dryja:
> > https://www.youtube.com/watch?v=edRun-6ubCc
> >
> > Actually, now that I think about it... As an alternative to UTXO set
> > commitments, the old fraud proofs idea for segwit can be applied here.
> >
> > We get miners to commit to the location of the UTXOs that are being
> > spent (e.g. transaction 5 in block 12). This allows full nodes to
> > succinctly prove invalidity to SPV clients in the following ways:
> >
> > -   a committed location does not contain the stated UTXO
> > -   the UTXO has already been spent in a prior block
> >
> > If no fraud proofs are given, then the inputs can be assumed to be 
> > valid.
> >
> > As you may recall, these kinds of fraud proofs were abandoned mainly
> > because the data unavailability claim could only be verified by
> > downloading the data, resulting in a DoS vector where all blocks had
> > to be downloaded. This problem does not seem to apply here, because we
> > are only interested in blocks which have forks, so it's more doable to
> > download them.
>
> This makes no sense.
> In order to validate block N, you need to know that every UTXO spent by a 
> transaction in block N is valid.
> The UTXO you want to validate is located in some other block, not on the 
> single block you are verifying.
>
> Thus the non-existent fraud proof can only be validated by loading the block 
> of the UTXO purported to be spent, and every block between that and the 
> current block you are verifying, i.e. fullnode.
> Either that or you trust that every peer you have is not omitting the proof.
>
> Regards,
> ZmnSCPxj
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs

2019-04-19 Thread Ruben Somsen via bitcoin-dev
Hi ZmnSCPxj and Ethan,

I apologize if my initial explanation was confusing, but it looks like
you figured it out. For every fork, SPV clients only have to download
one block. If there is a fork after block N, this means there are two
blocks at N+1. You only download and verify N+1 from the longer chain.

>Mining a block which will never be accepted is an expensive way to make SPV 
>clients download validate and discard ~2-4 megabytes of data

Absolutely, hence the name "PoW fraud proof". It gets naturally
created by honest miners and is prohibitively expensive to forge.

>SPV clients may not even learn about these splits because it requires that 
>someone relay the split to them. Honest full nodes should not relay such 
>splits.

You could perform a fully valid repeated 1-block reorg from the top of
the chain. So at least theoretically you could get an honest network
to relay every split.

>Having SPV clients slow down or become full nodes when a malicious miner with 
>significant mining power is attempting to disrupt the network is probably a 
>best case outcome.

That is an excellent point.

>As I understand it, this requires that UTXO commitments be mandatory.

Perhaps UTXO sets can be made useful without committing them. I have
some very loose thoughts on the subject, I consider it an open
question.

> More difficult is: how can an SPV node acquire the UTXO set at a particular 
> block?

I think you are asking fair questions about how the UTXO set
commitments would work in practice, and how viable that makes it. I'm
not sure. The most comprehensive work I have seen on this topic has
been the utreexo proposal by Tadge Dryja:
https://www.youtube.com/watch?v=edRun-6ubCc

Actually, now that I think about it... As an alternative to UTXO set
commitments, the old fraud proofs idea for segwit can be applied here.

We get miners to commit to the location of the UTXOs that are being
spent (e.g. transaction 5 in block 12). This allows full nodes to
succinctly prove invalidity to SPV clients in the following ways:

- a committed location does not contain the stated UTXO
- the UTXO has already been spent in a prior block

If no fraud proofs are given, then the inputs can be assumed to be valid.

As you may recall, these kinds of fraud proofs were abandoned mainly
because the data unavailability claim could only be verified by
downloading the data, resulting in a DoS vector where all blocks had
to be downloaded. This problem does not seem to apply here, because we
are only interested in blocks which have forks, so it's more doable to
download them.

-- Ruben Somsen

On Fri, Apr 19, 2019 at 6:48 AM ZmnSCPxj  wrote:
>
> Good morning Ethan,
>
> > My above email contains an error. The SPV client needs to only
> > download S+1, not S+1 and S+2.
> >
> > I agree with you that a weakness of this approach is a miner can make
> > SPV clients do substantially more work. However:
> >
> > 1.  Mining a block which will never be accepted is an expensive way to
> > make SPV clients download, validate and discard ~2-4 megabytes of
> > data. There are far less expensive ways of wasting the resources of
> > SPV clients. Its unclear why someone would want to do this instead of
> > just packeting full nodes or SPV servers like we saw with the recent
> > DDoS attacks against electrum servers.
> >
> > 2.  SPV clients may not even learn about these splits because it
> > requires that someone relay the split to them. Honest full nodes
> > should not relay such splits. To their bitcoin's worth the attacker
> > must also connect to lots of SPV clients.
> >
> > 3.  Having SPV clients slow down or become full nodes when a malicious
> > miner with significant mining power is attempting to disrupt the
> > network is probably a best case outcome. I would prefer this failure
> > mode to the current SPV behavior which is to just go with the
> > "longest" chain.
>
>
> I understand.
> It seems a reasonable point to do so.
>
> As I understand it, this requires that UTXO commitments be mandatory.
> In particular, if UTXO commitments were not mandatory, it would be trivial to 
> force chainsplits at heights where a UTXO commitment was not made, and force 
> an SPV node to download more blocks backwards until a block with a UTXO 
> commitment is found.
>
> More difficult is: how can an SPV node acquire the UTXO set at a particular 
> block?
> Fullnodes automatically update their UTXO set at each block they accept as 
> tip.
> Reversing the blocks to update the UTXO set at a particular past time would 
> require a good amount of CPU and memory.
> Thus any service that can provide the actual UTXO set at each block would 
> potentially be attackable by simply requesting enough past blocks.
>
>
> Regards,
> ZmnSCPxj
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Improving SPV security with PoW fraud proofs

2019-04-18 Thread Ruben Somsen via bitcoin-dev
Simplified-Payment-Verification (SPV) is secure under the assumption
that the chain with the most Proof-of-Work (PoW) is valid. As many
have pointed out before, and attacks like Segwit2x have shown, this is
not a safe assumption. What I propose below improves this assumption
-- invalid blocks will be rejected as long as there are enough honest
miners to create a block within a reasonable time frame. This still
doesn’t fully inoculate SPV clients against dishonest miners, but is a
clear improvement over regular SPV (and compatible with the privacy
improvements of BIP157[0]).

The idea is that a fork is an indication of potential misbehavior --
its block header can serve as a PoW fraud proof. Conversely, the lack
of a fork is an indication that a block is valid. If a fork is created
from a block at height N, this means a subset of miners may disagree
on the validity of block N+1. If SPV clients download and verify this
block, they can judge for themselves whether or not the chain should
be rejected. Of course it could simply be a natural fork, in which
case we continue following the chain with the most PoW.

The way Bitcoin currently works, it is impossible to verify the
validity of block N+1 without knowing the UTXO set at block N, even if
you are willing to assume that block N (and everything before it) is
valid. This would change with the introduction of UTXO set
commitments, allowing block N+1 to be validated by verifying whether
its inputs are present in the UTXO set that was committed to in block
N. An open question is whether a similar result can be achieved
without a soft fork that commits to the UTXO set[0][1].

If an invalid block is created and only 10% of the miners are honest,
on average it would take 100 minutes for a valid block to appear.
During this time, the SPV client will be following the invalid chain
and see roughly 9 confirmations before the chain gets rejected. It may
therefore be prudent to wait for a number of confirmations that
corresponds to the time it may take for the conservative percentage of
miners that you think may behave honestly to create a block (including
variance).

If users do not wait and happen to accept payments from an invalid
chain during this time, these payments could get reverted. This is a
weakness, but still seems preferably to continually following an
invalid chain. As long as a reasonable number of miners remains
honest, a dishonest majority can only temporarily control the network,
and their blocks (and all coins gained from it) will eventually be
rejected.

-- Ruben Somsen


[0] Olaoluwa Osuntokun, BIP 157: Client Side Block Filtering,
https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki

[1] Peter Todd, TXO commitments do not need a soft-fork to be useful,
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013591.html
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Safer NOINPUT with output tagging

2018-12-19 Thread Ruben Somsen via bitcoin-dev
Hi Johnson,

The design considerations here seem similar to the ML discussion of
whether Graftroot should be optional [1].

>While this seems fully compatible with eltoo, is there any other proposals 
>require NOINPUT, and is adversely affected by either way of tagging?

As far as I can tell it should be compatible with Statechains [2],
since it pretty much mirrors Eltoo in setup.

My understanding is somewhat lacking, so perhaps I am missing the
mark, but it is not completely clear to me how this affects
fungibility if taproot gets added and the setup and trigger tx for
Eltoo get combined into a single transaction. Would the NOINPUT
spending condition be hidden inside the taproot commitment?

Cheers,
Ruben Somsen

[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016006.html
[2]  
https://www.reddit.com/r/Bitcoin/comments/9nhjea/eli51525faq_for_statechains_offchain_transfer_of/

On Mon, Dec 17, 2018 at 8:20 PM Johnson Lau via bitcoin-dev
 wrote:
>
> NOINPUT is very powerful, but the tradeoff is the risks of signature replay. 
> While the key holders are expected not to reuse key pair, little could be 
> done to stop payers to reuse an address. Unfortunately, key-pair reuse has 
> been a social and technical norm since the creation of Bitcoin (the first tx 
> made in block 170 reused the previous public key). I don’t see any hope to 
> change this norm any time soon, if possible at all.
>
> As the people who are designing the layer-1 protocol, we could always blame 
> the payer and/or payee for their stupidity, just like those people laughed at 
> victims of Ethereum dumb contracts (DAO, Parity multisig, etc). The existing 
> bitcoin script language is so restrictive. It disallows many useful smart 
> contracts, but at the same time prevented many dumb contracts. After all, 
> “smart” and “dumb” are non-technical judgement. The DAO contract has always 
> been faithfully executed. It’s dumb only for those invested in the project. 
> For me, it was just a comedy show.
>
> So NOINPUT brings us more smart contract capacity, and at the same time we 
> are one step closer to dumb contracts. The target is to find a design that 
> exactly enables the smart contracts we want, while minimising the risks of 
> misuse.
>
> The risk I am trying to mitigate is a payer mistakenly pay to a previous 
> address with the exactly same amount, and the previous UTXO has been spent 
> using NOINPUT. Accidental double payment is not uncommon. Even if the payee 
> was honest and willing to refund, the money might have been spent with a 
> replayed NOINPUT signature. Once people lost a significant amount of money 
> this way, payers (mostly exchanges) may refuse to send money to anything 
> other than P2PKH, native-P2WPKH and native-P2WSH (as the only 3 types without 
> possibility of NOINPUT)
>
> The proposed solution is that an output must be “tagged” for it to be 
> spendable with NOINPUT, and the “tag” must be made explicitly by the payer. 
> There are 2 possible ways to do the tagging:
>
> 1. A certain bit in the tx version must be set
> 2. A certain bit in the scriptPubKey must be set
>
> I will analyse the pros and cons later.
>
> Using eltoo as example. The setup utxo is a simple 2-of-2 multisig, and 
> should not be tagged. This makes it indistinguishable from normal 1-of-1 
> utxo. The trigger tx, which spends the setup utxo, should be tagged, so the 
> update txs could spend the trigger utxo with NOINPUT. Similarly, all update 
> txs should be tagged, so they could be spent by other update txs and 
> settlement tx with NOINPUT. As the final destination, there is no need to tag 
> in the settlement tx.
>
> In payer’s perspective, tagging means “I believe this address is for 
> one-time-use only” Since we can’t control how other people manage their 
> addresses, we should never do tagging when paying to other people.
>
> I mentioned 2 ways of tagging, and they have pros and cons. First of all, 
> tagging in either way should not complicate the eltoo protocol in anyway, nor 
> bring extra block space overhead.
>
> A clear advantage of tagging with scriptPubKey is we could tag on a 
> per-output basis. However, scriptPubKey tagging is only possible with 
> native-segwit, not P2SH. That means we have to disallow NOINPUT in 
> P2SH-segwit (Otherwise, *all* P2SH addresses would become “risky” for payers) 
> This should be ok for eltoo, since it has no reason to use P2SH-segwit in 
> intermediate txs, which is more expensive.
>
> Another problem with scriptPubKey tagging is all the existing bech32 
> implementations will not understand the special tag, and will pay to a tagged 
> address as usual. An upgrade would be needed for them to refuse sending to 
> tagged addresses by default.
>
> On the other hand, tagging with tx version will also protect P2SH-segwit, and 
> all existing wallets are protected by default. However, it is somewhat a 
> layer violation and you could only tag all or none output in the 

Re: [bitcoin-dev] Guiding transaction fees towards a more censorship resistant outcome

2018-09-06 Thread Ruben Somsen via bitcoin-dev
Hi Damian,

>Where you say "create transactions which are only valid if they are mined on 
>top of a specific block." - in practice, does that usually means at any height 
>above a specific block?

Those details aren't important for the point I was trying to make.
BIP115 allows the transaction to be mined at any height, which is
probably as far as you can take this, realistically. What I think
you'll find in practice, is that the more specific you are in how you
want your transaction to be mined, the higher the chance that your
transaction will inadvertently become unmineable.

A perhaps more general point that I realized after posting, is that
fee pressure towards censorship resistance happens naturally if the
system provides anonymity. If the target transaction that miners wish
to censor is indistinguishable from other anonymous transactions, then
miners will have no choice but to censor every anonymous transaction,
so the end result is very similar to what I imagined linking
transactions would do.

-- Ruben Somsen
On Thu, Sep 6, 2018 at 5:48 PM Damian Williamson  wrote:
>
> Humour me please,
>
>
> Where you say "create transactions which are only valid if they are mined on 
> top of a specific block." - in practice, does that usually means at any 
> height above a specific block?
>
> 
> From: bitcoin-dev-boun...@lists.linuxfoundation.org 
>  on behalf of Ruben Somsen via 
> bitcoin-dev 
> Sent: Sunday, 2 September 2018 3:26:54 AM
> To: bitcoin-dev@lists.linuxfoundation.org
> Subject: [bitcoin-dev] Guiding transaction fees towards a more censorship 
> resistant outcome
>
> When a user creates a transaction with a fee attached, they are
> incentivizing miners to add this transaction to the blockchain. The
> task is usually not very specific -- as long as it ends up in a valid
> chain with the most Proof-of-Work, miners get paid. The payment is an
> incentive for miners to act in the way that users desire.
>
> To the user, there’s an individual benefit: their transaction gets
> added. To the network, there’s a shared benefit: all fees add to the
> security of other transactions in the chain. Miners can choose to
> ignore the incentives, but they would be leaving money on the table
> (and eventually get replaced by more competitive miners).
>
> Transactions from Bitcoin Core are slightly more specific about what
> they ask miners to do. Every transaction is only valid at a block
> height that is one higher than the last block. This incentivizes
> miners to build on top of the last block, instead of going back and
> reorganizing the blockchain. This is especially important in a future
> scenario where the fee reward is larger than the block reward.
>
> BIP 115* by Luke-jr is even more specific. It enables users to create
> transactions which are only valid if they are mined on top of a
> specific block. While originally designed as a form of replay
> protection, it actually serves as a deterrent for miners to reorganize
> the blockchain. If they orphan a block, it will invalidate
> transactions that demanded the inclusion of the orphaned block. This
> increases the cost of intentionally reorganizing the blockchain.
>
> Coinjoin**, the act of combining payments of multiple users into a
> single transaction, can be seen as yet another method for users to be
> more specific. The fate of their payments are now intertwined with
> that of others. If miners wish to censor a single payment, they have
> to reject the entire transaction, and the associated fee amount.
> Techniques like mimblewimble simplify this process, by making coinjoin
> non-interactive.
>
> This brings us to a theoretical scenario where:
>
> - every block contains only a single coinjoin transaction
> - the validity of this transaction depends on the inclusion of a
> specific previous block
> - the block reward is negligible compared to transaction fees
>
> In this scenario, if miners wish to undo a specific transaction that
> happened two blocks ago, they would have to create three empty blocks
> (receiving negligible compensation) in order to overtake the longest
> chain. And even then, users can still refuse to let their new
> transactions be mined on top of the empty blocks, disincentivizing
> such behavior completely.
>
> While not easy to achieve in practice (e.g. resolving natural forks
> becomes more complicated), it demonstrates that users can become more
> empowered than they are today, benefitting censorship resistance***.
> It is this line of thinking that I wish to convey. Perhaps it may
> inspire further ideas in this direction.
>
> -- Ruben Somsen
>
>
> * BIP 115: 
> https://apc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.c